DeepStack is an artificial intelligence computer program designed to play two-player poker, specifically heads up no-limit Texas hold 'em.[1] It is the first computer program to outplay human professionals in this game.
Background
editPoker is a key benchmark game in academic community and substantial amount of research was done to find optimal strategies against worst case adversaries.[2] While human professionals have been outplayed in large perfect information games, such as Chess, decades before, imperfect information games require much more complex recursive reasoning. Prior popular approaches relied mainly on simplification of the game by using abstractions. However, abstractions in imperfect-information games often result in highly-exploitable strategies. Instead, DeepStack uses several algorithmic innovations, such as the use of neural networks and continual resolving. The program was developed by an international team from Charles University, Czech Technical University and University of Alberta.
Algorithm
editAt the core of the program is the use of neural networks for determining the value of specific card combinations. The networks are trained only on a small number of games states and are used to generalize to situations not seen during training. The program uses search with the neural networks and continual resolving to ensure strategy found at each step is consistent with the strategy used in previous steps. The search procedure uses counterfactual regret minimization[3] to iteratively update strategy in its lookahead tree, and the neural networks are used for leaf evaluation. The leaf evaluation avoids reasoning about the entire remainder of the game by substituting the computation beyond a certain depth with a fast approximate estimate.
2016 tournament with professional players
editIn a study completed December 2016, DeepStack defeated 11 professional poker players by playing 44,000 hands of poker. Over all games played, DeepStack won 49 big blinds/100 (always folding would only lose 75 bb/100), over four standard deviations from zero, making it the first computer program to beat professional poker players in heads-up no-limit Texas hold'em poker.[citation needed]
Competing approaches
editConcurrently with DeepStack, a competing approach from Carnegie Mellon University research group was published, called Libratus. On January 11 to 31, 2017, Libratus was pitted in a tournament against four top-class human poker players.[4] The algorithm was also published in Science.[5] Libratus does not use neural networks for leaf evaluation. Experts argue that using learning with neural networks (as done by DeepStack) is more general[6] and it has been indeed used in subsequent works that generalize to other games with imperfect information[7]
Reception by the poker community
editDara O'Kearney, an Irish poker professional who completed 456 hands, claimed that DeepStack played in a style similar to one used by some human players, based on game theory. [8]
See also
editReferences
edit- ^ Moravcik, Matej; Schmid, Martin; Burch, Neil; Lisy, Viliam; Morrill, Dustin; Bard, Nolan; Davis, Trevor; Waugh, Kevin; Johanson, Michael; Bowling, Michael (2017). "Deepstack: Expert-level artificial intelligence in heads-up no-limit poker" (PDF). Science. 356 (6337): 508–513. arXiv:1701.01724. Bibcode:2017Sci...356..508M. doi:10.1126/science.aam6960. PMID 28254783. S2CID 1586260.
- ^ Rubin, Jonathan; Watson, Ian (2011). "Computer poker: A review". Artificial Intelligence. 175 (5–6): 958–987. doi:10.1016/j.artint.2010.12.005.
- ^ Zinkevich, Martin; Johanson, Michael; Bowling, Michael; Piccione, Carmelo (2007). "Regret minimization in games with incomplete information". Advances in Neural Information Processing Systems. 20.
- ^ Spice, Byron; Allen, Garrett (January 4, 2017). "Upping the Ante: Top Poker Pros Face Off vs. Artificial Intelligence". Carnegie Mellon University. Retrieved 2017-01-12.
- ^ Brown, Noam; Sandholm, Tuomas (2018). "Superhuman AI for heads-up no-limit poker: Libratus beats top professionals". Science. 359 (6374): 418–424. Bibcode:2018Sci...359..418B. doi:10.1126/science.aao1733. PMID 29249696. S2CID 5003977.
- ^ Metz, Cade. "Rival AIs Battle to Rule Poker (and Global Politics)". Wired. Retrieved 6 April 2022.
- ^ Brown, Noam; Bakhtin, Anton; Lerer, Adam; Gong, Qucheng (2020). "Combining deep reinforcement learning and search for imperfect-information games". Advances in Neural Information Processing Systems. 33: 17057–17069. arXiv:2007.13544.
- ^ Johnston, Ia (2 March 2017). "AI's defeat of pro poker players a 'paradigm shift', say scientists". Independent. Retrieved 6 April 2022.