Research map / Learning theory and algorithms / Submodular and game algorithms
Accelerating Nash Equilibrium Convergence in Monte Carlo Settings Through Counterfactual Value Based Fictitious Play
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes MCCFVFP, a Monte Carlo variant of counterfactual value-based fictitious play that replaces CFR's regret matching with best-response updates, reporting 20-50% faster convergence than MCCFR on poker and other test games.
Problem
Existing CFR accelerations (CFR+, DCFR, PCFR) require full game-tree traversal and do not carry over to Monte Carlo sampling, which is needed for large-scale imperfect-information games.
Approach
Replace the regret-matching strategy in MCCFR with a pure best-response strategy computed from accumulated counterfactual values (omitting the average-payoff term), exploiting that large games have many dominated actions and that pure BR updates allow more pruning and cheaper per-infoset computation.
Key results
- MCCFVFP reaches convergence roughly 20-30% faster than MCCFR in two-player Texas Hold'em (69 strength ranks, ~89k infosets) within the same time.
- Across tested games MCCFVFP consistently converged faster than MCCFR; about 50% time savings versus ES-MCCFR at similar exploitability is claimed.
- In 6-player Texas Hold'em head-to-head play using community cards KsQsJs3h2h, MCCFVFP gained 0.932 BB/100 over MCCFR.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace regret matching with counterfactual value-based best responses | MCCFR, producing MCCFVFP · Kuhn-extension, Leduc-extension, and princess-and-monster games | convergence speed: approximately 20\%$\sim$50\% faster | Helped |
| Replace regret matching with counterfactual value-based best responses | MCCFR, producing MCCFVFP · Two-player Texas Hold’em | convergence speed: 20--30\% faster | Helped |
| Replace regret matching with counterfactual value-based best responses | MCCFR, producing MCCFVFP · 6-player Texas Hold’em | reward versus MCCFR: 0.932 BB/100 | Helped |
| Use MCCFVFP instead of MCCFR | MCCFR · Kuhn-extension, Leduc-extension, and princess-and-monster games | time at similar exploitability: approximately 50\% time savings | Helped |
| Use MCCFVFP instead of MCCFR | MCCFR · One information set | computational time: 2/9 | Helped |
| Use MCCFVFP instead of CFVFP | CFVFP · Different games | convergence | Helped |
| Use MCCFVFP+ instead of CFVFP+ | CFVFP+ · Different games | convergence | Helped |
| Use weight w_t=1 instead of the other tested common weights (ablation) | CFVFP · Different games | convergence speed | Helped |
Surprising findings
- In small games like vanilla Kuhn, full-traversal algorithms (DCFR, PCFR, CFR+) can outperform both MCCFR and MCCFVFP.
- The authors acknowledge the method may be theoretically less effective than MCCFR in tangled games, yet it outperformed MCCFR in all tested scenarios.
Limitations
- Convergence guarantees rely on a Blackwell approachability argument restricted to two-player zero-sum games; the pseudocode does not cover multiplayer or other settings.
- Theoretical advantage depends on games being 'clear' (few non-dominated actions); the authors concede it may underperform MCCFR in tangled games.
- Texas Hold'em experiments simplify the game (players check through to the river) and use a single subgame of 89k infosets for exploitability.
Experimental setup
Datasets: Kuhn-extension poker Leduc-extension poker princess and monster game Texas Hold'em
Benchmarks: Kuhn-extension poker Leduc-extension poker princess and monster two-player Texas Hold'em (BB/100 exploitability) 6-player Texas Hold'em mutual play
Metrics: exploitability convergence speed vs time nodes touched average reward BB/100 in head-to-head play
Baselines: ES-MCCFR MCCFR CFR+ DCFR PCFR DCFR+
Builds on: Counterfactual Regret Minimization Monte Carlo CFR Fictitious Play Predictive CFR
Closest papers by meaning
- Faster Game Solving via Hyperparameter Schedules (AAAI 2026 · similarity 0.92)
- Stochastic Regret Minimization in Extensive-Form Games (ICML 2020 · similarity 0.91)
- Strategy-Based Warm Starting for Regret Minimization in Games (AAAI 2016 · similarity 0.90)
- Solving Imperfect-Information Games via Discounted Regret Minimization (AAAI 2019 · similarity 0.90)
- Variance Reduction in Monte Carlo Counterfactual Regret Minimization (VR-MCCFR) for Extensive Form Games Using Baselines (AAAI 2019 · similarity 0.90)
- Preference-CFR: Beyond Nash Equilibrium for Better Game Strategies (ICML 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.