PerspectiveComputer Science

Solving imperfect-information games

Science  09 Jan 2015:
Vol. 347, Issue 6218, pp. 122-123
DOI: 10.1126/science.aaa4614

You are currently viewing the summary.

View Full Text

Via your Institution

Log in through your institution

Log in through your institution


Summary

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 operationalization 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 al. (1) 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 (26), 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.