Solving imperfect-information games

摘要

Imperfect-information games model settings where players have private information. Tremendous progress has been made in solving such games over the past 20 years, especially since the Annual Computer Poker Competition was established in 2006, where programs play each other. This progress can fuel the opera-tionalization of seminal game-theoretic solution concepts into detailed game models, powering a host of applications in business (e.g., auctions and negotiations), medicine (e.g., making sophisticated sequential plans against diseases), (cyber)security, and other domains. On page 145 of this issue, Bowling et til. (7) report on having computed a strategy for two-player limit Texas Hold'em poker that is so close to optimal that, at the pace a human plays poker, it cannot be beaten with statistical significance in a lifetime. While strong strategies have been computed for larger imperfect-information games as well (2-6), this is, to my knowledge, the largest imperfect-information game essentially solved to date, and the first one competitively played by humans that has now been essentially solved.