---

Poker

AI Programs that Play the Game of Poker

---

AITopics > Games & Puzzles > Poker

Poker professional Phil Laak intently concentrating as he participated in the first Man-Machine Poker Championship, held at the annual AAAI conference, Vancouver, 2007. Phil and partner Ali Eslami narrowly edged out the University of Alberta computer program POLARIS. Mankind was not as fortunate in the 2008 Man-Machine match. (Picture courtesy of the Morgan Kan, of the University of Alberta Computer Poker Research Group)

"Industry executives and analysts often mistakenly talk about strategy as if it were some kind of chess match. But in chess, you have just two opponents, each with identical resources, and with luck playing a minimal role. The real world is much more like a poker game, with multiple players trying to make the best of whatever hand fortune has dealt them." (David Moschella, Computerworld, 1999)

---

Why the Game is Interesting

Poker enjoys world-wide popularity. The game offers a rich set of research challenges that are not seen in popular AI research testbeds such as checkers, chess, and Go. These include:

• hidden or imperfect information, a fundamental problem arising in many AI domains;
• deception, an important property that is critical to success;
• multiple players (two to ten), increasing the complexity of the domain;
• stochastic outcomes, introducing variance and making evaluation difficult; and
• variable payouts, forcing players to maximize their winnings rather than number of wins.

Additional Reading

"Poker has emerged as a standard benchmark ... for a number of reasons, because (1) it exhibits the richness of reasoning about a probabilistic future, how to interpret others’ actions as signals, and information hiding through careful action selection, (2) the game is unambiguously specified, (3) the game can be scaled to the desired complexity, (4) humans of a broad range of skill exist for comparison, (5) the game is fun, and (6) computers find interesting strategies automatically. For example, time-tested behaviors such as bluffing and slow play arise from the game-theoretic algorithms automatically rather than having to be explicitly programmed." (Sandholm (2010))

Computers and Poker? You Bet. Podcast (July 26, 2005). "[Jonathan Erickson of] Dr. Dobb's Journal discusses the high-stakes world of computers and Poker with Jonathan Schaeffer" This gives a nice overview of the particular challenges poker poses and a brief discussion of applications beyond poker.

"Poker is a game of imperfect knowledge, where multiple competing agents must deal with risk management, agent modeling, unreliable information and deception, much like decision-making applications in the real world. The heuristic search and evaluation methods successfully employed in chess are not helpful here." (Billings et al. (1998)) Be sure to see Table 1: Characteristics of AI problems and how they are exhibited by poker.

Playing Your Cards Right - Poker comes out of the back room and into the computer science lab. By Ivars Peterson, Science News (July 18, 1998) "Poker is an example of a game of incomplete information in which chance plays a role. Whereas a chess player sees the disposition of all the pieces all the time, a poker player sees only some of the cards -- drawn or dealt from a shuffled deck -- that are in play."

---

History

Different forms of poker have been researched academically since the 1950's, beginning with three-card Kuhn poker (Kuhn (1950)). The largest poker game to be solved (exactly) to date is Rhode Island Hold'em, a game similar to Texas Hold'em but with fewer private cards, public cards, and betting rounds (Gilpin and Sandholm (2005)). In 2003, Billings et al. came up with a near-optimal solution to Heads-Up Limit Texas Hold'em using game-theoretic approaches (Billings, et al. (2003)). The strongest computer programs to date in Texas Hold'em have typically been approximations of Nash equilibria in large abstract extensive form games. In 2007 and again in 2008, the computer poker program POLARIS developed at the University of Alberta competed against professional human players in Heads-Up Limit Texas Hold'em. While narrowly losing to Phil Laak and Ali Eslami in 2007, POLARIS defeated a team of Heads-Up expert players in 2008 at the Second Man-Machine Poker Competition (See Computer Poker Competition section for more links).

Since 2006, the annual Computer Poker Competition has pitted state of the art computer programs against each other in a number of different variants of Texas Hold'em. Heads-Up Limit Texas Hold'em was the first game to be played and continues to have strong entrants every year. The more recent Heads-Up No Limit and Multi-Player Limit Texas Hold'em categories remain challenging areas for ongoing research.

Additional Reading

"In this paper, we present a review of recent algorithms and approaches in the area of computer poker, along with a survey of the autonomous poker agents that have resulted from this research. We begin with the first serious attempts to create strong computerised poker players by constructing knowledge-based and simulation-based systems. This is followed by the use of computational game theory to construct robust poker agents and the advances that have been made in this area. Approaches to constructing exploitive agents are reviewed and the challenging problems of creating accurate and dynamic opponent models are addressed. Finally, we conclude with a selection of alternative approaches that have received attention in previously published material and the interesting problems that they pose." (Rubin and Watson (2010))

$8.9m poker prize up for grabs - humans only please: Why can't a bot play at this level? By Robert Blincoe, The Register (November 5 2010) "But has poker bot development reached a level where a bot could be in with a shout for this [World Series of Poker 2010 final] prize? The short answer is not yet, unless it got lucky."

Ante Up, Human: The Adventures of Polaris, the Poker-Playing Robot By Julie Rehmeyer, Wired, Issue 16.2. Tells the story of the 2008 match between POLARIS and IJay "doughnutz" Palansky.

The Poker Machine By Tim Harford, FT Magazine, 6 May 2006. An engaging overview of the history of the World Championship, the core challenges in poker, and the state-of-the-art poker bots as of 2006.

---

AI Advances

Many of the advances in poker AI research have come from new algorithms for solving extensive form games. Some notable techniques include Koller et al.'s linear programming approach (Koller et al. (1994)) and Gilpin et al.'s excessive gap technique (Gilpin et al. (2007)). The current state-of-the-art approach is the Counterfactual Regret Minimization (CFR) algorithm (Zinkevich et al. (2008)). CFR is an iterative algorithm whose memory efficiency allows for much larger extensive games to be solved that were otherwise intractable.

While these techniques have produced some of the strongest poker agents to date, they are typically employed off-line to compute a single, static strategy that that does not adjust to an opponent's mistakes or tendencies. Often, more utility can be earned in poker by modelling an opponent's behavior and exploiting weaknesses in his or her play. One approach is to estimate values of a parametric opponent model and then compute a strategy that exploits this model. Some work in this area includes Billings et al.'s Vexbot program (Billings et al. (2004)), Johanson and Bowling's Data Biased Response technique (Johanson and Bowling (2009)), and Ganfried and Sandholm's Deviation-Based Best Response (Ganzfried and Sandholm (2011)). Alternatively, one can estimate performance of individual candidates from a pool of agents and select the agent that is believed to perform the best against the particular opponent. Examples include Hoehn et al.'s strategy learning approach (Hoehn et al. (2005)) and Bowling et al.'s importance sampling (Bowling et al. (2008)). While progress is being made, these techniques are still behind the equilibrium-based approaches and effective opponent modelling remains a challenging problem.

In addition, Zinkevich et al. developed a method for reducing variance when estimating agent performance (Zinkevich et al., (2008)). By removing elements of luck during post-game analysis, DIVAT, a poker-specific version of this method, provides a more precise assessment between different poker players ((Billings and Kan (2006)). Furthermore, Johanson et al. show how to efficiently compute a full best-response to a strategy in a large extensive game (Johanson et al. (2011)). This technique can evaluate a strategy exactly in terms of its worst-case performance, or exploitability, in Heads-Up Limit Texas Hold'em, measuring precisely how far a strategy is from equilibrium.

Additional Reading

"This paper describes the design considerations and architecture of the poker program Poki. In addition to methods for hand evaluation and betting strategy, Poki uses learning techniques to construct statistical models of each opponent, and dynamically adapts to exploit observed patterns and tendencies. The result is a program capable of playing reasonably strong poker, but there remains considerable research to be done to play at world-class level." (Billings et al. (2002))

Windows, lose, draw - Alberta researchers develop a computer program that knows when you're bluffing. By Charlie Gillis. National Post (July 27, 2002). "This week, Mr. [Darse] Billings and a team of University of Alberta researchers are publicizing a poker-playing computer program that does what many a putative gambler cannot -- it successfully processes the mercurial and misleading information it receives in the heat of a game. The system represents a significant stride in artificial intelligence because it effectively guesses whether an opponent is bluffing, wavering or playing his hands arrow-straight. By doing so, it goes beyond programs developed for games such as chess and backgammon, which sift through finite sets of moves before choosing a course."

---

Frequently Asked Questions

Q: Do you think poker computers will eventually beat human players?
A: Yes. For heads-up poker this is a certainty. It's possible, given enough computing power, for computers to play "perfectly", where over a long enough match (so that luck evens out) the program provably cannot lose money. However, humans will always make some mistakes, meaning the program will have an advantage. We're still quite far from the necessary computing power for perfect play, though.

The 2008 Man-Machine competition in Vancouver, though, demonstrated that computers can already play competitively with humans, even though its still far from perfect play. And the technology is evolving rapidly. In less than one year we have made significant improvements to Polaris, and I would expect that computers would be able to beat the best poker professionals in Heads-Up Limit Hold'Em within a couple of years, if not sooner.

Games of poker involving more than two players or more betting options, such as no-limit, are still a bit further out of reach.
-Michael Bowling


Q: Should users of online poker sites be wary that some players could be robots?
A: Users of poker sites should definitely not be wary on account of our success. Our program does not play online for money and the program itself is carefully guarded for this reason. I am not an authority on the practice of programs playing on poker sites, and so can't comment on how many or the skill level of any such programs. Such practice, though, is against the terms of service of most sites and I know that sites are interested in aggressively pursuing those who violate the terms.
-Michael Bowling


Q: Can a computer really bluff like a human?
A: Computers can definitely bluff. Although they may not bluff like humans do. Bluffing falls entirely out of the mathematics of the imperfect information game, of which poker is the quintessential example. The mathematics of game theory requires that in order to play in a fashion that cannot be exploited by other players your play should not give away what cards you hold. Bluffing (and slow-playing) are key parts of a game theoretic solution since they prevent your opponent from knowing you have a strong hand when betting nor knowing you have a weak hand because you didn't bet. Since this falls out of the mathematics, we don't even have to explicitly program bluffing into our program. The program figures out how, when, and with what frequency to bluff all on its own.
-Michael Bowling


Q: Is poker-playing software harder to write than, say, chess-playing software? Why?
A: In games such as chess and chequers, players have access to all the information they need. But poker contains hidden information. How does that complicate the situation?

Poker is a very different game than Chess. Poker is a game of imperfect information, where the information a player would like to know in making their decisions (the other players' cards) is hidden. This makes poker a more challenging problem for artificial intelligence. And traditional techniques, namely search which was the centerpiece of AI in chess, cannot be readily applied in poker. As such, new techniques have been developed to handle these more challenging classes of games.

One interesting difference between high-end chess programs and high-end poker programs is when the computation happens. Polaris does the vast majority of its computation before the match starts. It uses months of computation, playing billions of hands of poker against itself, to compute a strategy for playing the game. Once in the middle of a match, it simply consults its strategy to determine how to play any given situation. Therefore its play during a match is nearly instantaneous. Chess programs do a great deal of computation during play as they search through possible moves and counter-moves. The best chess programs have to be heavily optimized for fast computation during a match. The best poker programs are heavily optimized to maximize the computing resources used before the competition. The challenges of writing software for chess and poker is quite different, rather than one being harder or easier.
-Michael Bowling


Q: The best human players try and think inside the minds of their opponents. Is this a better approach than game theory, and could computers ever do this?
A: Opponent modelling hasn't played a very significant role in the recent successes of poker playing programs, but it's maybe the most interesting challenge in poker. The notion of "perfect" play in game theory aims at a strategy that is guaranteed to not lose money in long matches. Opponent modelling or exploitive play, on the other hand, aims at something quite different: maximizing winnings against the current opponent. Top human players will draw conclusions about an opponent before they even sit down at the table by the way they dress, carry their chips, or their online nickname. These models are being constantly adapted after each observed decision of their opponent and inform a strong player's decisions. Perfect play may suggest that you should bluff in a certain situation 20% of the time, but if you knew your opponent was tight you could make more money by bluffing more often. Based on current state of the art, it's clear that humans do this very well and computers do not yet.

Can computers ever be able to do this? I think so. We're currently exploring some new ideas for exactly how this could be accomplished, and they look promising.
-Michael Bowling


Q: Does a poker robot's lack of emotion give it an advantage?
A: Naturally. Computers don't go on tilt. They don't get frustrated when getting cold cards or start to feel bullet-proof after a string of hot cards. One of the Polaris bots that played in the Man-Machine match in Vancouver exploited this fact with very aggressive play, although still game-theoretically sound. The humans struggled to respond to its extreme aggression. Whether the aggression spooked the players, pushed them into decisions they weren't used to making, or even simply was a style they hadn't seen before, we don't know. But certainly the players walked away from that match looking emotionally beat-up, while the program was oblivious to what just occurred.
-Michael Bowling

Q: Why are events like the Man-Machine Poker Match important?
A: There are two reasons to hold events like this. One is that they motivate the research. Competition is great for driving progress. Having a goal of defeating the world's best poker players forces our research group to continue to innovate, pioneer new ideas, and perfect old ones. For example, two years ago the AAAI computer poker competition (for poker-playing programs to compete against each other) was started. In just the first two years huge strides have been made in computational techniques for solving large models of strategic interactions, and this was following ten years of no change in the state of the art.

In addition to competition pushing the research forward, this competition is an attempt to establish another milestone in the progress of artificial intelligence. Computers already play chess and backgammon better than any human, and they even play perfect checkers. But what none of these games have is the degree of uncertainty that players face in a poker game, including uncertainty in what the opponents' cards are, uncertainty in what future cards will be, and uncertainty in the opponents' playing styles. We're hoping to show that the new AI techniques that we've been developing over the last ten years can effectively handle this degree of uncertainty. This isn't just a toy problem. The techniques that we and others are developing to cope with uncertainty in poker are critical for many promising applications of artificial intelligence. Decision making problems in the real world almost always involve uncertainty. For example, when we drive a car we have to cope with uncertainty in the goals of the other drivers (where are they trying to get to?), future events (when will the light change? is that a pot hole in the road?), and others' driving styles (why did he hit his breaks? is he drunk?). Business decisions also are primarily about coping with uncertainty whether it be when participating in small scale Ebay auctions or the billion dollar high-stakes FCC spectrum auctions in the United States, the type of which is now coming to Canada. These are essentially high stakes poker matches, and the ideas that underly computer programs that can beat the best human players can also allow better decision-making in these scenarios as well.
-Michael Bowling

Q: Why should the poker-playing public be interested in the Man-Machine Poker Tournament?
A: We know from [the 2007] competition that duplicate man-machine matches are both very entertaining and very educational. It is a rare opportunity to witness a world-class poker player given the opportunity to think out loud as they play. Since Polaris is not listening, watching, or even timing its opponent, the human player is free to talk about their hand, how they're playing, what they think the computer has, or trash talk all without giving away their hand. It's a bit like television poker, but the player's themselves can narrate the hand rather than announcers having to guess the player's thoughts. It is effectively a free lesson in heads-up limit hold'em from world-class players and coaches. In addition, Polaris is educational by itself. For those more mathematically minded players, Polaris takes game theoretic reasoning to its extreme. Phil Laak and Ali Eslami last year both felt they walked away having learned something from Polaris.

In addition, this is a historic opportunity to see the continuing battle of humans versus machine in games of intelligence. Computers can play a perfect game of checkers and they are superior to all humans at chess; the next round is poker. But poker is a very different game. The game is full of uncertainty that doesn't arise in chess or checkers: uncertainty in future cards, uncertainty in what your opponent holds, uncertainty in how your opponent plays. These are the reasons that computer poker programs haven't yet conquered their expert human counterparts. However, much has changed in the past two years. We believe that we are close to overtaking the best human players at heads-up limit games and this is our chance to provide. In summary, these matches are like the historic battles of Deep Blue versus Kasparov in 1996 and 1997.
-Michael Bowling

---

Related Resources

Man-Machine Poker

2008 The Second Man-Machine Poker Competition "Polaris will be pitted against some of the biggest names in the online poker world: Nick "stoxtrader" Grudzien, Matt "Hoss_TBF" Hawrilenko, and IJay "doughnutz" Palansky." results

2007 The First Man-Machine Poker Championship "For the first time ever, a poker-playing computer program challenged two top-level poker professionals in a controlled scientific experiment with real money on the line. A team of researchers from the University of Alberta improved on their reigning world champion poker software, and took it to the next level. The program, Polaris, took on two of the sharpest poker players in the world - Phil "The Unabomber" Laak and Ali Eslami." results

Poker Research

The University of Alberta Computer Poker Research Group. "Poker is an excellent domain for artificial intelligence research. It offers many new challenges since it is a game of imperfect information, where decisions must be made under conditions of uncertainty. Multiple competing agents must deal with probabilistic knowledge, risk management, deception, and opponent modeling, among other things. One of the products of our research is the implementation of a poker playing program named POLARIS." The CPRG bot Hyperborean placed in the top 3 of all 6 events of the 2010 competition AAAI Computer Poker competition.

University of Auckland Game AI group. The University of Auckland Game AI group's poker bot SartreNL (no limit) placed in 2nd in the no-limit instant run-off event of the 2010 AAAI Computer Poker competition. You can play Sartre online.

Computer Poker Competition

Annual Computer Poker Competition Homepage "The Annual Computer Poker Competition has run since 2006. Historically the competition takes place each summer at the AAAI Conference on Artificial Intelligence or at the International Joint Conference on Artificial Intelligence when it happens in North America (since AAAI is not run). The event attracts competitors, both academics and hobbyists alike, from countries around the world."

See results of past Computer Poker Competitions here.

Software and Demos

Play Sartre online "SartreNL is now available to challenge online. SartreNL achieved 2nd place in the no limit heads up runoff division of the 2010 Annual Computer Poker Competition. The latest limit version of Sartre is also available to challenge. "

Play One-card poker "One-card poker is a simple game; nonetheless it has many of the elements of more complicated games, including incomplete information, chance events, and multiple stages. And, optimal play requires behaviors like randomization and bluffing."

Play optimal Rhode Island Hold 'em "GSI (Game Shrink Interactive) plays Rhode Island Hold 'Em optimally. Rhode Island Hold 'Em is a three card poker game invented by Jiefu Shi and Michael Littman. The main difference between Rhode Island Hold 'Em and Texas Hold 'Em is the number of cards in play."

Open CFR A simple implemetation of CFR using the Leduc game. "Kevin Waugh's Open CFR implemented for the Leduc card game. The source code is written in C++ and is licensed under the Open BSD License. The README in the tarball contains information on training and playing strategies created using this code as well as some examples. There are also a handful of abstractions in the abstractions folder. "

Open PVAT An open source version of the DIVAT analysis tool for Heads-Up Limit Texas Hold'em. "This is the source code for an open source poker value aseesment tool based on Morgan Kan's Always Call DIVAT."

Compete in the Poker Bot Competition Check the website for the latest competitions, rules, and software.

Other AI Topics Games Pages

• Bridge
• Checkers
• Chess
• Crossword Puzzles
• Game Theory (@ Multi-Agent Systems)
• Go
• More Games & Puzzles
• Othello
• Overview
• Scrabble
• Traveling Salesperson & NP-Complete Problems

---

References

(Billings et al. (1998)) D. Billings, D. Papp, J. Schaeffer, and D. Szafron. Poker as a Testbed for Machine Intelligence Research. In Proceedings of AI'98, (Canadian Society for Computational Studies in Intelligence), 1998. (pdf)

(Billings et al. (2002)) D. Billings, A. Davidson, J. Schaeffer, and D. Szafron. The challenge of poker. Artificial Intelligence, January 2002 (Volume 134, Issue 1-2). (pdf)

(Billings et al. (2003)) D. Billings, N. Burch, A. Davidson, R. Holte, J. Schaeffer, T. Schauenberg, and D. Szafron. Approximating game-theoretic optimal strategies for full-scale poker. In International Joint Conference on Artificial Intelligence (IJCAI), pages 661–668, 2003. (pdf)

(Billings et al. (2004)) D. Billings, A. Davidson, T. Schauenberg, N. Burch, M. Bowling, R. Holte, J. Schaeffer, and D. Szafron. Game Tree Search with Adaptation in Stochastic Imperfect Information Games. In CG, 2004. (gzipped ps)

(Billings and Kan (2006)) D. Billings and M. Kan. Tool for the Direct Assessment of Poker Decisions. International Computer Games Association Journal, volume 29(3), pages 119–142, 2006. (ps, pdf, abstract)

(Bowling et al. (2008)) M. Bowling, M. Johanson, N. Burch, and D. Szafron. Strategy Evaluation in Extensive Games with Importance Sampling. In ICML, 2008. (pdf, icml presentation)

(Ganzfried and Sandholm (2011)) S. Ganzfried and T. Sandholm. Game Theory-Based Opponent Modelling in Large Imperfect-Information Games. In AAMAS, 2011. (pdf)

(Gilpin and Sandholm (2005)) A. Gilpin and T. Sandholm. Optimal Rhode Island hold'em poker. In AAAI national conference, pp. 1684-1685, 2005. (pdf)

(Gilpin et al. (2007)) A. Gilpin, S. Hoda, J. Pena, and T. Sandholm. Gradient-based algorithms for finding Nash equilibria in extensive form games. In 3rd International Workshop on Internet and Network Economics (WINE), 2007. (pdf)

(Hoehn et al. (2005)) B. Hoehn, F. Southey, R. C. Holte, and V. Bulitko. Effective Short-term Opponent Exploitation in Simplified Poker. In UAI, 2005. (pdf, appendix)

(Johanson and Bowling (2009)) M. Johanson and M. Bowling. Data Biased Robust Counter Strategies. In AISTATS, 2009. (pdf, presentation slides)

(Johanson et al. (2011)) M. Johanson, M. Bowling, K. Waugh, and M. Zinkevich. Accelerating Best Response Calculation in Large Extensive Games. In IJCAI, 2011. To appear. (pdf)

(Koller et al. (1994)) D. Koller, N. Megiddo, and B. von Stengel. Fast algorithms for finding randomized strategies in game trees. In Annual ACM Symposium on Theory of Computing (STOC), pages 750–759, 1994. 9 (pdf)

(Kuhn (1950)) H. W. Kuhn, Simplified two-person poker; in H. W. Kuhn and A. W. Tucker (editors), Contributions to the Theory of Games, volume 1, pages 97-103, Princeton University Press, 1950. (Google books result)

(Rubin and Watson (2010)) J. Rubin and I. Watson. Computer Poker: a review. Artificial Intelligence, 2010. (pdf, Sci Direct page)

(Sandholm (2010)) T. Sandholm. The State of Solving Large Incomplete-Information Games, and Application to Poker. Artificial Intelligence, 2010. (pdf)

(Zinkevich (2008)) M. Zinkevich, M. Johanson, M. Bowling, and C. Piccione. Regret minimization in games with incomplete information. In Advances in Neural Information Processing Systems 20 (NIPS), 2008. (pdf)