Solving heads-up limit hold’em poker

A game of Texas hold 'em. Image from Wikipedia.

From one of my previous posts, I talked about the poker playing computer Claudico as it played against human opponents for nearly two weeks. The results came in with the four human players winning $732,713 over the computer out of $170 million that was bet during play. However, the number is very insignificant compared to the $170 million played so the scientists behind Claudico is considering that this might be a tie. Humans are still better at imperfect information games than computers but not by much. It may only take a little longer for computers to master it.

On January 9th, 2015, "Heads-up limit hold’em poker is solved" was published in the Science journal as the first article to prove that a "nontrivial imperfect-information game played competitively by humans" can be beaten by a computer (Bowling, Burch, Johanson, & Tammelin, 2015). The difference between Claudico and research done here is the type of poker been played. Claudico is programmed to deal with heads-up no limit hold’em poker where bets and raises have no limit. This means Claudico has to deal with 10¹⁶¹ information sets, or possible outcomes. Heads-up limit hold’em poker limits how much can be bet and reduces the amount of possible outcomes down to 3.19 × 10¹⁴. Even though this amount seems trivial compared to Claudico, it's a first step into solving the world of imperfect games.

The paper uses a method called Counterfactual regret minimization (CFR). It approximates the Nash Equilibrium, the best strategy of winning the game, by using two regret-minimizing algorithms. The program plays itself and calculates the detrimental effects of not picking the best option. It tries to minimize the negative effects, regrets, in order to find the best deterministic strategy. The problem was storing the regret values of all the possible outcomes. To do so requires 262 TB of storage. To fix this problem, Bowling et al. truncated the decimals into integers and implemented compression methods to bring down the required storage down to a workable 17 TB.

References

Bowling, M., Burch, N., Johanson, M., & Tammelin, O. (2015). Heads-up limit hold'em poker is solved. Science, 347(6218), 145-149. doi:http://dx.doi.org/10.1126/science.1259433
 
Maynard, J. (2015, May 10). CMU AI Claudico Is Good At Poker But Not Good Enough For World's Best Human Players. Retrieved May 11, 2015, from http://www.techtimes.com/articles/51946/20150510/cmu-ai-claudico-good-poker-enough-worlds-best-human-players.htm

Walters, K., & Watts, E. (2015, April 24). Brains Vs. Artificial Intelligence. Retrieved May 11, 2015, from http://www.cmu.edu/news/stories/archives/2015/april/computer-faces-poker-pros.htm