Communications of the ACM
Heads-Up Limit Hold'em Poker Is Solved
Credit: Getty Images
Poker is a family of games that exhibit imperfect information, where players do not have full knowledge of past events. While many perfect information games have been solved (e.g., Connect-Four and checkers), no nontrivial imperfect information game played competitively by humans has previously been solved. In this paper, we announce that the smallest variant of poker in-play, heads-up limit Texas hold'em, is now essentially weakly solved. Furthermore, this computation formally proves the common wisdom that the dealer in the game holds a significant advantage. This result was enabled by a new algorithm, CFR+, which is capable of solving extensive-form games three orders of magnitude larger than previously possible. This paper is an extended version of the original 2015 Science article,9 with additional results showing Cepheus' in-game performance against computer and human opponents.
1. Introduction
Games have been intertwined with the earliest developments in computation, game theory, and Artificial Intelligence (AI). At the very conception of computing, Babbage had detailed plans for an "automaton" capable of playing tic-tac-toe and dreamt of his Analytical Engine playing chess.4 Both Alan Turing46 and Claude Shannon,40 on paper and in hardware respectively, developed programs to play chess as validation of early ideas in computation and AI. For over a half-century, games have continued to act as testbeds for new ideas and the resulting successes have marked significant milestones in the progress of AI: For example, the checkers-playing computer program Chinook becoming the first to win a world championship title against humans,38 Deep Blue defeating Kasparov in chess,14 and Watson defeating Jennings and Rutter on Jeopardy!17 However, defeating top human players is not the same as "solving" a game, that is, computing a game-theoretically optimal solution that is incapable of losing against any opponent in a fair game. Solving games has also served as notable milestones for the advancement of AI, for example, Connect-Four2 and checkers.39
Every nontrivial game played competitively by humans that has been solved to-date is a perfect information game.a In perfect information games, all players are informed of everything that has occurred in the game prior to making a decision. Chess, checkers, and backgammon are examples of perfect information games. In imperfect information games, players do not always have full knowledge of past events (e.g., cards dealt to other players in bridge and poker, or a seller's knowledge of the value of an item in an auction). These games are more challenging, with theory, computational algorithms, and instances of solved games lagging behind results in the perfect information setting.b And, while perfect information may be a common property of parlor games, it is far less common in real-world decision making settings. In a conversation recounted by Bronkowski, John von Neumann, the founder of modern game theory, made the same observation, "Real life is not like that. Real life consists of bluffing, of little tactics of deception, of asking yourself what is the other man going to think I mean to do. And that is what games are about in my theory."12
No entries found