Approximating Subgame Perfect Equilibrium by Minimizing Counterfactual Regret

In 2019, Pluribus beat professional human players in six-player no-limit Texas Hold'em poker game for the first time in history. For a program to decide what move to make, it can solve each case of a game for Nash equilibrium, that is, a strategy where each player cannot gain any incentive by changing their strategy. However, poker has a game tree that is too big to compute in its entirety. To tackle this problem, Pluribus used a variation of counterfactual regret minimization (CFR), which efficiently goes through the game tree and estimates a Nash equilibrium at each decision, where each player's payoff is close to that of a Nash equilibrium. Although computer programs based on CFR achieved success at estimating a Nash equilibrium in poker, Nash equilibrium are not well suited for games like poker, where each player takes turns making decisions. In such sequential games, subgame perfect equilibrium is a more appropriate solution concept. We explore modifying the CFR algorithm to estimate subgame perfect equilibrium for games like poker.