imperfect-information-solvers technique sourced
Regret minimization and search for imperfect-information games
Self-play algorithms that minimize counterfactual regret over information sets, refined by real-time subgame search, compute hard-to-exploit strategies that bluff and hide information and beat top humans at poker, Stratego, and Scotland Yard.
mechanism
A decision point is an information set: all histories the player cannot tell apart. CFR traverses the game tree repeatedly; at each information set it computes each action's counterfactual regret (how much better it would have done, weighted by the probability that others reach that set) and sets the next strategy by regret matching, proportional to positive cumulative regret. The average strategy converges to a Nash equilibrium in two-player zero-sum games, and Monte Carlo CFR samples the tree to scale. Large games are abstracted (bucketed hands and bet sizes) into an offline blueprint that is refined during play by subgame search: Libratus used nested subgame solving, DeepStack re-solved to a depth limit with a learned value function, and Pluribus searched a few moves ahead while letting each opponent pick among four continuation strategies at the leaves. ReBeL and Student of Games learn values over public belief states and search with them, reducing to AlphaZero-style search in perfect-information games. DeepNash instead learns a policy model-free with Regularised Nash Dynamics and no search. Outputs are mixed strategies, so the agent bluffs at calibrated rates.
limitations
- Convergence guarantees hold for two-player zero-sum games; Pluribus's six-player play works empirically without them, and cooperative or general-sum simulation games fall outside the theory.
- Large games need designed abstractions of actions and states; a simulation with continuous economies and many units has no obvious abstraction to solve.
- Runtime search costs seconds per decision (Pluribus averaged about 20 seconds per hand on two CPUs), far above per-frame budgets for many agents.
- Equilibrium play avoids being exploited rather than exploiting weak players, which can feel passive, and randomized bluffs read as arbitrary unless the game explains them.
relations
6 stored edgesAuctions
AI bidders play mixed strategies over private valuations instead of bidding a fixed fraction of value, which removes simple exploits such as always outbidding the AI by one unit.
Fog of war
AI players reason over unseen state as a belief distribution and play strategies that are hard to exploit, instead of cheating with full map knowledge or ignoring hidden units, so concealment and feints work against the AI as they would against a person.
Military operations
Deception becomes a stable part of AI play, as DeepNash bluffed with hidden unit identities in Stratego, so operational wargames could field opponents that feint and conceal force composition at calibrated rates.
Negotiation
Bargaining with hidden reservation values is an imperfect-information game; equilibrium strategies bluff and concede in ways scripted thresholds cannot.
Rival firms
Competitors with private costs or plans can bluff in price wars and market entry, and designers can measure how exploitable a fixed AI pricing script is by computing a best response against it.
Scouting knowledge
Equilibrium strategies put a value on information, so AI opponents scout, hide their own attributes, and avoid revealing them through their actions, giving the player's scouting system a real counterpart.
backlinks
computed from other recordsclaims
6 with sourcesLibratus beat top professionals at heads-up no-limit Texas hold'em (Science, January 2018).
DeepStack beat professional players with statistical significance over 44,000 hands of heads-up no-limit hold'em using recursive re-solving with a learned value function.
Pluribus beat elite professionals at six-player no-limit hold'em, winning about 5 big blinds per 100 hands over 10,000 hands; its blueprint took 8 days of Monte Carlo CFR on a 64-core server (under $150 of cloud compute) and it played on two CPUs at about 20 seconds per hand.
ReBeL combined self-play RL with search, provably converging to a Nash equilibrium in two-player zero-sum games, and reached superhuman heads-up no-limit hold'em with less domain knowledge.
DeepNash reached a top-3 all-time ranking among expert humans on the Gravon Stratego platform using model-free Regularised Nash Dynamics and no search (Science, December 2022).
Student of Games (Science Advances, November 2023) used one sound algorithm across chess, Go, heads-up no-limit poker, and Scotland Yard, beating the strongest openly available poker agent and the prior best Scotland Yard agent.