counterfactual regret minimization
In plain wordsA method for working out near-unbeatable strategies in games with hidden information, like poker, by repeatedly playing against itself and shifting each decision toward the moves it most regrets not making.
An iterative algorithm for approximating a Nash equilibrium in two-player zero-sum games of imperfect information, such as poker. It traverses the game tree repeatedly in self-playself-play, n.: Training an AI by having it play against copies of itself, so it always has an opponent at its own level and can keep improving without human examples.; at each information set — a decision point as seen by the player to move, who cannot observe hidden cards — it computes counterfactual regretregret, n.: How much worse a learner did than it could have done had it known the best choice from the start — the price of having to learn by trying., how much better each action would have done, weighted by the probability that the opponent and chance reach that point, and updates the local strategy by regret matching, playing actions in proportion to their positive accumulated regret. Minimizing regret locally at every information set bounds overall regret, so the average strategy over iterations converges to an equilibrium. Variants made it scale: Monte Carlo CFR samples parts of the tree, CFR+ converges much faster, abstraction shrinks the game, and Deep CFR replaces tables with neural networks. CFR-based programs essentially solved heads-up limit Texas hold'em (Cepheus, 2015), beat professional players at heads-up no-limit hold'em (DeepStack and Libratus, 2017) and beat elite professionals at six-player no-limit hold'em (Pluribus, 2019).
We abstracted bet sizes to five options so CFR could converge on a laptop overnight.
Origin
Introduced by Martin Zinkevich, Michael Johanson, Michael Bowling and Carmelo Piccione of the University of Alberta in 'Regret Minimization in Games with Incomplete Information' (NIPS 2007), building on Sergiu Hart and Andreu Mas-Colell's regret matching (2000). Oskari Tammelin's CFR+ (2014) powered Cepheus, and Noam Brown and Tuomas Sandholm's Libratus and Pluribus extended the approach.
Usage note
Unlike AlphaZeroAlphaZero, prop. n.: A 2017 DeepMind program that taught itself chess, shogi and Go from nothing but the rules by playing against itself, and within hours of training beat the strongest existing programs.-style search, CFR reasons explicitly about hidden information and mixes its actions so that opponents cannot exploit predictable play — which is why equilibrium poker strategies bluff at calculated frequencies.
Related
- regretregret, n.: How much worse a learner did than it could have done had it known the best choice from the start — the price of having to learn by trying.
- self-playself-play, n.: Training an AI by having it play against copies of itself, so it always has an opponent at its own level and can keep improving without human examples.
- multi-agent reinforcement learningmulti-agent reinforcement learning, n.: Reinforcement learning with several AI agents learning at once in a shared world, where each must adapt to the others — as teammates, rivals or both.
- game treegame tree, n.: A branching diagram of every way a game could unfold: each point is a position, each branch a possible move, and the tips of the branches are wins, losses or draws.
- minimaxminimax, n.: A way for a game-playing program to choose moves by assuming the opponent will always make their best reply, and picking the move whose worst-case outcome is best.
- Monte Carlo tree searchMonte Carlo tree search, n.: A way for a game-playing program to choose a move by simulating many possible continuations, focusing on the most promising lines, and picking the move that worked out best on average.
Sources
- Zinkevich, M., Johanson, M., Bowling, M. & Piccione, C. (2007). Regret Minimization in Games with Incomplete Information. Advances in Neural Information Processing Systems 20.
- Bowling, M., Burch, N., Johanson, M. & Tammelin, O. (2015). Heads-up limit hold'em poker is solved. Science 347(6218), 145–149.
- Brown, N. & Sandholm, T. (2019). Superhuman AI for multiplayer poker. Science 365(6456), 885–890.
Mentioned in
multi-agent reinforcement learningmulti-agent reinforcement learning, n.: Reinforcement learning with several AI agents learning at once in a shared world, where each must adapt to the others — as teammates, rivals or both., self-playself-play, n.: Training an AI by having it play against copies of itself, so it always has an opponent at its own level and can keep improving without human examples., regretregret, n.: How much worse a learner did than it could have done had it known the best choice from the start — the price of having to learn by trying.