Using counterfactual regret minimization to create competitive multiplayer poker agents

By Nicholas Abou Risk, Duane Szafron. 2010

73 citations recorded by the source corpus.

Games are used to evaluate and advance Multiagent and Artificial Intelligence techniques. Most of these games are deterministic with perfect information (e.g. Chess and Checkers). A deterministic game has no chance element and in a perfect information game, all information is visible to all players. However, many real-world scenarios with competing agents are stochastic (non-deterministic) with imperfect information. For two-player zero-sum perfect recall games, a recent technique called Counterfactual Regret Minimization (CFR) computes strategies that are provably convergent to an ε-Nash equilibrium. A Nash equilibrium strategy is useful in two-player games since it maximizes its utility against a worst-case opponent. However, for multiplayer (three or more player) games, we lose all theoretical guarantees for CFR. However, we believe that CFR-generated agents may perform well in multiplayer games. To test this hypothesis, we used this technique to create several 3-player limit Texas Hold'em poker agents and two of them placed first and second in the 3-player event of the 2009 AAAI/IJCAI Computer Poker Competition. We also demonstrate that good strategies can be obtained by grafting sets of two-player subgame strategies to a 3-player base strategy after one of the players is eliminated.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Actor-Critic Policy Optimization in Partially Observable Multiagent Environments (2018, unknown): “competition-winning) strategies in this setting [74, 26, 48].”
Finding Optimal Abstract Strategies in Extensive-Form Games (2012, methodology): “They have been used to model a variety of scenarios including game playing (Zinkevich et al. 2008; Lanctot et al. 2009; Hoda et al. 2010; Risk and Szafron 2010), bargaining and negotiation (Lazaric, de Cote, and Gatti 2007; Gatti 2008), argumentation (Procaccia and Rosenschein 2005), and even distri”
Opponent Modeling by Expectation–Maximization and Sequence Prediction in Simplified Poker (2017, unknown): “For example, Risk and Szafron use approximate Nash equilibrium strategies in three-player limit Texas Hold'em, which they find using counterfactual regret minimization [17].”
Evaluating state-space abstractions in extensive-form games (2013, unknown): “Although it is only proven to converge to a Nash equilibrium in two-player zero-sum perfect recall games, in practice it appears robust when these constraints are violated as it has been successfully applied to multiplayer games [14], non-zero-sum games [12], and imperfect recall games [19].”
A parameterized family of equilibrium profiles for three-player kuhn poker (2013, methodology): “THREE-PLAYER KUHN POKER Three-player Kuhn poker [1] is played with a deck of 4 cards, denoted 1, 2, 3 and 4.”
Computer poker: A review (2011, methodology): “Recently the CFR algorithm was applied to the 3-player game of limit hold’em [72].”
Computing Approximate Nash Equilibria and Robust Best-Responses Using Sampling (2011, unknown): “Nonetheless, the first work on applying algorithms such as CFR to games with more than two players suggests that the NES still is a very strong strategy (Risk & Szafron, 2010).”
Self-play Monte-Carlo tree search in computer poker (2014, methodology): “In spite of this, CFR has achieved strong performance in threeplayer limit Texas Hold’em (Risk and Szafron 2010).”