Accelerating Nash Equilibrium Convergence in Monte Carlo Settings Through Counterfactual Value Based Fictitious Play
Authors: Qi Ju
Falin Hei
Ting Feng
Dengbing Yi
Zhemei Fang
YunFeng Luo
Venue: NeurIPS 2024 poster (2024)
Keywords: incomplete information game
Counterfactual Regret Minimization
blueprint strategy
fictitious play
Primary area: algorithmic_game_theory

Abstract: Counterfactual Regret Minimization (CFR) and its variants are widely recognized as effective algorithms for solving extensive-form imperfect information games. Recently, many improvements have been focused on enhancing the convergence speed of the CFR algorithm. However, most of these variants are not applicable under Monte Carlo (MC) conditions, making them unsuitable for training in large-scale games. We introduce a new MC-based algorithm for solving extensive-form imperfect information games, called MCCFVFP (Monte Carlo Counterfactual Value-Based Fictitious Play). MCCFVFP combines CFR’s counterfactual value calculations with fictitious play’s best response strategy, leveraging the strengths of fictitious play to gain significant advantages in games with a high proportion of dominated strategies. Experimental results show that MCCFVFP achieved convergence speeds approximately 20\%$\sim$50\% faster than the most advanced MCCFR variants in games like poker and other test games.

Accelerating Nash Equilibrium Convergence in Monte Carlo Settings Through Counterfactual Value Based Fictitious Play
Ju Q Hei Falin Feng Ting!.2 Yi Dengbing 1.2, Fang Zhemei Luo Yunfeng 1.2 School of Artificial Intelligence and Automation, Huazhong University of Science and Technology 2. National Key Laboratory of Science and Technology on Multispectral Information Processing (juqi, heifalin, fenting, yidengbing, zmfang2018, yfluo]0uust. edu. cn Corresponding author.
Abstract
Counterfactual Regret Minimization (CFR) and its variants are widely recognized effective algorithms for solving extensive-form imperfect information games. Recently, many improvements have been focused on enhancing the convergence speed of the CFR algorithm. However, most of these variants under Monte Carlo (MC) conditions, making them unsuitable for training in large- scale games. We introduce new MC-based algorithm for solving extensive-form imperfect information games, called MCCFVFP (Monte Carlo Counterfactual Value-Basee Fictitious Play). MCCFVFP combines CFR's counterfactual value calculations with fictitious play's 's best response strategy, leveraging the strengths of fictitious play to gain significant advantages in games with a high proportion of dominated strategies. Experimental results show that MCCFVFP achieved conver- gence speeds approximately 20%~500 faster than the most advanced MCCFR variants in games like poker and other test games.
applicable
Introduction
Game theory investigates mathematical models of strategic interactions among rational agents, aiming to identify a Nash Equilibrium (NE) where no participant can gain by deviating from the established strategy. For complete information games, it is possible to segment the game into smaller sub-games and apply backward induction to determine the equilibrium. In contrast, in incomplete information games, the inability to directly apply sub-game payoffs in the backward induction algorithm significantly increases the complexity of finding an equilibrium.
The Counterfactual Regret Minimization (CFR) algorithm Zinkevich er al. (007) is crucial for solving extensive-form games with incomplete information. CFR has numerous variants, such as CFR+ (FR+TTammelin [2014). Lazy CFR Zhou et al. (2018). PCFR Farina al [2021]. J, DCFR Brown and Sandholm [019a]. J. and PDCFR Xu et al. [[0224] Nevertheless, these variants typically require full traversal of the entire game tree, which is impractical for real-world applications. In contrast, games
like no-limit Texas hold' em, DouDizhu, and Mahjong have 10 102 Moravík et al. 2017]] 1083 Zha e
al. 2021]. and 121
Li al. 2020 information sets, respectively, making full traversal infeasible.
To address this, Lanctot et al. Lanctot el al. [2010) proposed Monte Carlo CFR (MCCFR), which reduces the number of game tree nodes visited in each iteration through sampling. This makes MCCFR the preferred algorithm for training large-scale games. However, most CFR variants cannot improve the convergence speed in the case of MCCFR. Only few variants, such as Discount MCCFR Brown and Sandholm [019aa and VR-MCCFR Schmid et al. 2209)) are currently suitable
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

for MCCFR. Therefore, it is crucial to study the characteristics of large-scale games and how to leverage these characteristics to accelerate the convergence of MC-based game learning algorithms.
We believe that the Fictitious Play (FP) algorithm is highly suitable for addressing large-scale incomplete information games, due to the characteristics of using the best response (BR) strategy. FP was first introduced in Brown's 1951 article Berger [007)]; Brown 1951]. The treatise The Theory of Learning in Games Fudenberg and Levine 1998 consolidated prior research, setting a standardized framework for FP. Generalized Weakened Fictitious Play (GWFP) Leslie and Collins) (2066) further established that under specific perturbations and errors, convergence to NE is attainable consistent with FP. Hendon et al. Hendon er al. [996) expanded FP to the domain of extensive- games. The development of the Full-Width Extensive- Formn Fictitious Play (XFP) algorithm [Heinrich] et al. [015], predicated on GWFP, has facilitated faster convergence in these games.
manner
Our algorithm, Monte Carlo Counterfactual Value- Fictitious Play (MCCFVFP), optimizes FP in extensive-form games by incorporating counterfactual value into the BR strategy calculations. We have theoretically proven that MCCFVFP can converge to NE, and experimentally demonstrated that in large-scale games, MCCFVFP fully leverages the high proportion of dominated strategies to achieve faster convergence speeds than MCCFR. Our code can be found GitHub
2
Notation and Preliminaries
2.1
Game Theory
2.1.1
Normal-Form Game
The normal-form game serves the foundational model in Game Theory. Let = 1, 2, :,,......... represent the set of players, where each player has finite action set A'. Player i's strategy, denoted o', is a probability distribution over A' and is represented by (1,41 1)-dimensional simplex. Here, |- indicates the cardinality of the set, and a' (a')) denotes the probability with which player selects action a'. Let 2' denote the strategy A strategy profile, o = o', represents the collection of strategies for all players, while aI (ol..... ..... oi . g ..... includes all strategies in except for that of player i. The entire set of strategy profiles is denoted by Σ = IlIE Σt, where a E E. The payoff function for player i, defined as w' Σ + R. is finite. The notation n''o', o) indicates the expected payoff to player i when they select the pure strategy of and all other players follow the strategy profile o o', Finally, define the payoff interval of the game as L = max u² (o() mi. (')).
for player such that a' >
2.1.2 Extensive-Form Games
In extensive form games, typically represented as game trees, the player set N = 1, Each node represents a possible state in the game, forming a set S, with terminal states represented by leaf nodes E Z. At each state S, the action set A(s) includes all possible actions available to a player or chance. The player function P :: S >> / U assigns each state an acting party, with e indicating chance event. Information sets I I' group states that player cannot distinguish among, reflecting their uncertainty. The payoff function Rt Z + [R maps each terminal state to payoff vector for the players. For each information set I E Ií, the behavioral strategy o oT) E RR [R(((D) defines a probability distribution over available actions.
2.1.3 Nash Equilibrium
The BR strategy of player i to their opponents' strategies o - is
6a arg max u' (a',a")).
although a mixed strategy may also become a BR strategy, it is much easier to find a pure BR strategy than mixed BR strategy in engineering implementation, the BR strategies discussed in this article are all pure BR strategies. If there are multiple BR strategies at the same time, one of them will be returned randomly. Define the exploitability e of player i in strategy profile as:
é' = u' u'(b((o o) - u²()).
(2)
and total exploitability Eieret A Nash equilibrium is a strategy profile such that 0.

---

During iterations, if the strategy's exploitability satisfies x T 1 the convergence rate of the algorithm is (T+) Additionally, the time complexity within one iteration is a critical factor affecting the convergence rate. We use (-) to describe the time complexity needed for one iteration.
2.1.4 Dominated Strategy and Clear Games
In game theory, strategic dominance occurs when one action (or strategy) is better than another action (or strategy) for one player, regardless of the opponents' actions. A classic example is the Prisoner's Dilemma, where choosing to testify always yields a higher payoff than staying silent, regardless of the opponent's decision. Here, staying silent is a dominated strategy. Formally, For player if there is a pure strategy a* and a strategy oº* E E' satisfies:
u'aa", o o) S u² "o""
Eo "oo""
then the pure strategy a²* is dominated strategy of player i. Rational players will invariably avoid choosing dominated strategy, allowing the elimination of dominated strategy from the action set A without impacting the game's NE (Samuelson [1922..
In our analysis, the proportion of dominated strategies in a game is crucial, significantly impacting the convergence speed of various algorithms. We categorize games into two distinct types based on this factor. Games where the number of dominated strategies is less than v|AA are classified clear games. This term captures a strategic landscape where the preferable choices are evident, owing to the relatively few dominated strategies. On the other hand, tangled games are defined by having number of dominated strategies greater than VIA], reflecting a more complex and nuanced strategic environment with less obvious choices. The reason for defining these categories in this way can be found in Appendix B.3 Such classification aids in comprehending game's nature and assessing the effectiveness of different algorithmic approaches.
2.2 Regret Matching and Counterfactual Regret Minimization
In normal-form games, let of be the strategy used by player i on round t. The regret of player i's action a² at time is:
T
(a') = Σ u
(a'5oz)) - n² (a.)-
(4)
t=1
The new strategy is produced by:
Ry (a)
if Enes: RZ (a) >
or4z(a')=
Eucoy (a)
(5)
otherwise,
[AP
where Riz* (a) max (R). 0). Since the probability of selecting action of41 (a) is proportional to the non-negative regret value Rit (a) for this action, this algorithm is referred to as the regret matching algorithm. Define the average strategy as θT + Σ tt, which converges to the NE
as T + 0o, with convergence rate of O (LVIA/T) In each iteration, RM requires a matrix multiplication operation, resulting in an iteration time complexity of Ø (I.A1)).
CFR is variant of RM specifically adapted for extensive-form games. The counterfactual value a(),o) is defined as the expected payoff assuming that information set / is reached and all players follow strategy a, with the exception that player acts specifically to reach I. For each action (T),, let a|ا=> represent a strategy profile identical a except that player consistently chooses action a within information set I. The counterfactual regret is then given by:
T
R²,
Σ ...
(I) (u' (1, (1,0110-0)) u² (1,o))),
(6)
t=1
where -,. is the probability of information set occurring if all players (including chance, except d) choose actions according to o,. Let R2* (I,a) max (I, a), 0). the strategy at time T + is: (1,a if E.Ex R1 (I,a)
)),)(1,0)= = Enerch (4-(1,0)
(7)
otherwise.
AUT]]
3

---

The average strategy or for an information set I on iteration T is:
(1) -= T (1)((1)
Et= T2 (1)
Eventually, 3y will converge to NE with -+ oc, the convergence rate of CFR is O [LI VIAl/T) and the time complexity of one iteration of the CFR algorithm (|AA]|Z)..
There are many forms of sampling MCCER, but the most common is external sampling MCCER (ES-MCCFR) (Bronn| (2020) because of its simplicity and powerful performance. ES-MCCFR, some players are designated as traversers and others are samplers during an iteration. Traversers follow the CFR algorithm to update the regret and the average strategy of the experienced information set. On the rest of the sampler's nodes and the chance node, only one action is explored (sampled according the player's 's strategy for that iteration on the information set), and the regret and the average strategy are not updated.
2.3 Fictitious Play
FP assuming all players start with random strategy profile ōz=1, the strategy profile is updated following the iterative function:
T++1 = (1 (1-oz) o + 0,0++1
(9)
where in vanilla FP a, = 1/(t+111 1). 0 - b(o,). The convergence rate of vanilla FP in two-player Daskalakis and Pan 2014), and the time complexity of one iteration
zero-sum game may be (VT)
of the vanilla FP algorithm is Ø (LA(²). To speed up iteration, define the average Q-value of player i's action a' at time T as:
T E d (a
@a(aa)
(10)
T
the game is a two-player game, or if ut is an affine function (e.g., in a potential game), we have:
@r (a') + Σ n (di,or)
Σ
a" Σ 0
(11)
u² (d')
therefore, we can conclude that
(' max Or (a'). EA
(12)
In 2.1.3 it is noted that BR strategy of in FP is pure strategy. As result, calculating u v' o, involves simply selecting row (or column) from the payoff matrix, eliminating the need for matrix multiplication as required in RM. Consequently. the time complexity of each iteration in the FP algorithm decreases to ((AA),, representing a significant improvement over the ((AA(s) complexity in RM.
Motivation of CFVFP
Currently, the mainstream approach for large-scale games is a combination of "pre-trained blueprint strategy + real-time search." For example, Pluribus initially employs the MCCFR algorithm to establish a blueprint strategy, which it applies in the early stages of the game, and then transitions to real-time search as the game progresses Brown and Sandholm [2019b]. Similarly, in the game of Go, AlphaGo primarily used reinforcement learning to train policy and value networks, incorporating limited number of MCTS rollouts during training. However, in actual matches against human experts, AlphaGoo significantly increased the number MCTS rollouts to enhance real-time decision- making Silver et al. [0066 2017 This phenomenon can be understood from two perspectives:

---

1. The complexity of real-world games is so high that it is impossible for any single strategy (even with deep networks) to perfectly handle all game scenarios. Due to this extreme complexity, only sampling-based training methods are feasible. Many current improvements to CFR, such as CFR+ and Predictive CFR, are designed for full traversal of the game tree. While these methods accelerate convergence, they are unsuitable for sampling-ban based approaches because the inexact payoff's introduced by sampling significantly disrupt the convergence direction of each strategy update.
2. Training a blueprint strategy usually starts with sampling from the initial nodes, resulting in a higher probability of exploring early game nodes compared to leaf nodes. Consequently, while the blueprint strategy might be less effective in the later stages of the game, it often rapidly converges towards the optimal solution in the early stages due to thorough exploration.
After clarifying the specific ideas for training large-scale game AI. Next, we need to think about the characteristics of large-scale games and how to design corresponding MC-type solving algorithms based on these characteristics.
One prominent characteristic of large-scale games is that the majority of strategies are dominated. For instance, in chess and Go, top AI systems and human experts often opt for fixed openings. Similarly, professional poker players tend to fold most hands in the early rounds. Theoretically. DeepMind likens game strategies to a spinning top Czarnecki et al.) [2020), implying that only a limited subset of strategies can be considered non-dominated. MCCFR experiments show that up to 96% of strategies can be pruned in certain games Lanctot et al. 2010). Likewise, the supplementary materials of Pluribus Brown and Sandholm [2019c] reveal that around 50% of information sets are never encountered during training (indicating that unplayed strategies are almost certainly dominated, with many traversed ones also being dominated). In other words, while it cannot be proven with absolute certainty, the choices of professional players and the experimental outcomes from current advanced AIs suggest that the larger the game, the higher the likelihood that it can be classified as "clear game."
Additionally, our toy experiment clearly demonstrates that the FP algorithm is more effective for clear games compared to the RM algorithm [ We attribute this advantage to the fact that FP employs the BR strategy rather than the RM strategy during iterations, which is why we aim to incorporate this feature into the iterations of CFR.
Clear Matrix Games
Random Metri
Retiloun Way
0.0
0.0
Pacyot
log (iEgpllttabllyyyy
-2.
1.0
-15
-20
-20
2.8
255
35
25 10
log10INum of terotions)
log10/Num (terationn)
Figure 1: The figure compares the convergence rates of the RM and FP algorithms in a 100 x 100 random payoff matrix game generated from N (0. 1) distribution. In right figure, the convergence for a standard random payoff matrix is shown, while left figure illustrates the convergence in 100 x 100 random payoff matrix where the payoffs for actions to 10 are uniformly increased by (causing actions 11 to 100 to have high probability of being dominated strategies). It can be observed that in this setting, the convergence rate of the FP is very close to that of RM. Considering that the complexity of one FP iteration is only ((AA) compared to the complexity of RM, which is (I)A)2), in a clear game, the overall convergence rate of FP can actually surpass that of RM. Each scenario tested average of 30 rounds. The shaded areas represent the 90% confidence intervals for these trials. The experiments in Appendix A can also confirm our view from another perspective.
5

---

4 CFVEP Method
4.1
Counterfactual Value Fictitious Play Implementation
Our method can be easily adapted from CFR. First, there is no need to compute the counterfactual regret, instead, we define the counterfactual value:
a)) (T, + -
(T,oelr-a)-
(13)
Second, the strategy in the next iteration is a BR strategy rather than RM strategy:
o = arg max (a (T,,.
(14)
The main distinction between Qi and Ri is that Qi omits the average payoff term u² (1, oz), ), as this term does not affect identifying the maximum value of Q; This omission leads to a significant reduction in computation time. Since arg max selects the action with the highest counterfactual value, the resulting strategy each iteration is pure strategy, similar to the FP algorithm. Thus, we refer to this algorithm as Counterfactual Value-Based Fictitious Play. Additionally, the time complexity of calculating the BR strategy is notably lower than that required for computing the RM strategy.
Finally, since the update o44 is a pure strategy, (T) is either 0 or 1. This significantly increases the likelihood of triggering naive pruning. From equation 6 we see that if π. T,,(1) (7) = O, it is unnecessary to enter the sub-game tree to calculate Q1),,)). Similarly, equation 8 shows that if T',, (4) = 0, it is unnecessary to update the average strategy (I). This pruning greatly enhances the algorithm's 's
efficiency.
CFVFP employs a simple yet effective approach by using BR strategy instead of regret-matching strategy for next iteration. The convergence of CFVFP can be easily proven. First, FP's convergence
to NE classifies it as a regret minimizer Abernethy et al. (2011), which also implies that FP satisfies
Blackwell approachability Blackwell 1956]. The CFR framework shows that if an algorithm satisfies Blackwell approachability, its counterfactual regrets will converge to zero Zinkevich et al. (007]] Therefore, CFVFP inherently adheres to Blackwell approachability.
Moreover, we can directly begin with the definition of Blackwell approachability and prove that FP fulfills this criterion. The convergence rate is O [[]A[T-)] )). and the detailed proof can be found
in B.I The pseudocode for the CFVFP algorithm is provided in Appendix C.I
fully compatible with various CFR variants, including MCCFR, CFR+, and different averaging schemes Brown and Sandholm 20 resulting in a range of CFVFP variants. Consequently, we conducted series of experiments to examine the convergence rates of these CFVFP variants. As detailed in Appendix [B] the vanilla-weighted MCCFVFP, a combination of MCCFR and CFVFP, shows the fastest convergence among the variants. The pseudocode for the MCCFVFP algorithm is provided in Appendix C.2
Since CFVFP follows Blackwell approachability,
4.2 Theoretical Analysis of MCCFVFP Algorithm
We discuss the advantages of the MCCFVFP algorithm in terms of the computing resources required per information set and the algorithm's 's pruning efficiency.
The MCCFVFP algorithm is highly efficient in conserving computing resources. For example, if an information set has [A(]) = z possible actions, MCCFVFP only requires 2x + additions to process this information set, whereas MCCFR needs 6r 2 additions and 3x multiplications to complete the same calculation. This means that, for a single information set, MCCFVFP requires only about 2/9 of the computational time compared to MCCFR. Considering that Blueprint training typically traverses at least I billion nodes, MCCFVFP offers significant advantages over MCCFR in terms of engineering implementation. For a detailed proof, refer to Appendix E.
Additionally, CFVFP highly efficient in game tree pruning. Pruning is a common optimization technique used in all tree search algorithms. For instance, the Alpha-Bete algorithm in complete- information extensive-form games is a pruned version of the Min-Max algorithm, and it was a key factor in Deep Blue's s success Hsu 2002). Naive pruning is the simplest pruning method in CFR. In naive pruning, no player has a probability of reaching the current state & ",,,,, (s) = 0), the entire subtree at that state can be pruned for the current iteration without affecting regret calculations.

---

By analyzing the frequency of different node types in the game tree, we theoretically prove that CFVFP can significantly reduce the number nodes that need to be processed. Compared CFR, which must traverse all Ø ([S]) nodes, CFVFP only needs to traverse Ø ('V|S)) nodes. This is especially beneficial in multiplayer games, where it greaty improves the efficiency of algorithm iterations. For detailed proof, please refer to Appendix B.2
Experiments
5.1 Description of the Game and Experimental Settings
We employed various game models. such Kuhn-extension poker, Leduc-extension poker, the princess and monster game el af. [2100) and Texas Hold'em, to evaluate the performance of different algorithms. These games are widely used benchmarks for comparing algorithmic convergence rates. Kuhn-extension poker, an expanded version of the classic Kuhn poker Kuhn [1950), features an increased card count of broader range of betting actions with y options, and up to raising opportunities. Similarly, Leduc-extension poker is an advanced version of the original Ledue poker Shi and Littman (2002), allowing for flexible scaling. The princess and monster game represents a classic pursuit-evasion evasion problem. Texas Hold' em, one of the most popular poker games in the world, was also included in our analysis.
In Kuhn, Leduc, and princess and monster games, we use a random distribution as the initial strategy to initialize all algorithms. In each iteration, the strategies and regrets of all players are updated random pure
simultaneously. In MCCFR, when It O, the next stage strategy is set strategy. addition, the settings in our comparison experiment are consistent with those in previous groundbreaking works, including MCCFR Lanctot al. (201), DCFR+ Brown and Sandholm 2019a]. and PCFR Farina et al. 2021]. For engineering implementation, any node with a probability less than 10 20 during iteration will be pruned. Our Texas Hold' em experiments employed a variant of the multivalued state technique Brown et al. [2018), with an experimental setup closely mirroring that of Pluribus Brown and Sandholm (2019b). The Texas Hold'en em experiments were 32-core, 128GB memory server, while the other experiments were conducted on a single core. is important note that all times mentioned below have been converted to reflect execution single CPU core.
For comprehensive exposition of these games and additional experimental findings, please refer to Appendix F In Appendix G we compare time, number of iterations, and nodes touched as an indicator. Finally, we use nodes touched and time an indicator.
5.2 Experimental results
As shown in the Figure 2
we can demonstrate the core findings of our paper:
In small-scale problems like vanilla Kuhn, algorithms such as DCFR, PCFR, and CFR+ may outperform MCCFR and MCCFVFP. However, the game scale increases, the convergence speed of sampling based algorithms (MCCFR/MCCFVEP) gradually surpasses that of full-traversal algorithms (DCFR/PCFR/CFR-+
In our experiments, MCCFVFP consistently converged faster than MCCFR. While theoreti- cally, our algorithm might be less effective than MCCFR in tangled games, the acceleration in its implementation and the tendency of large-scale games to be clear games have led to MCCFVFP outperforming MCCFR in all tested scenarios.
Specifically, when using the number of nodes touched as a metric, MCCFVFP demonstrates a slightly faster convergence rate compared to ES-MCCFR. However, in terms of processing the same number of nodes, MCCFYFP's computation time is only about 2/9 of MCCFR's s (the underlying reasons discussed in Section E.I). As result, when factoring in the time required for game simulation, MCCFVFP achieves approximately 50% time savings compared to ES-MCCFR for similar levels of exploitability in these games.
As previously noted, algorithms such as CFR+, PCFR, and DCFR are not well-suited for large-scale games due to their reliance on full traversal, which is impractical in complex settings like Texas
7

---

Vanilla Kihn
Vaniln Leduc
50-Card 3-Action 3-Len Kuhn
110.00 (100
Trans
The lit Tin
10-Cladd L-Action I-Len Loduy
15.Cud I-Acion 144 Ledie
Step PAM
Vanilla Kuhn
Vanilla
50-Card 3-Action 3-1,en
Meda Nedtol
Nod Tricke
Teeted
10-Card L-Action L-Len Ledue
15-Card 1-Actios I-Len Ledue
Step PAM
Taudes
CFVFPlcurs)
ES-NCCHR
Figure 2: Convergence rates in Kuhn-extension Leduc-extension and princess-and -onsteeterr games are shown. In the first two rows, time measured in milliseconds (ms). The last two rows reflect the same running time but with the horizontal axis representing the number of nodes touched during iteration. All experiments tested over an average of 30 rounds. The shaded areas indicate 90% confidence intervals for the trials.
Hold' em. Therefore, in Texas Hold' em experiments, focused comparing the performance of our algorithm specifically against the traditional MCCFR method, excluding these full-traversal algorithms from testing.
In our experiments, we used 2, 3, and 6-player Texas Hold' em game setups, where each player started with 25 Big Blinds (BB) in chips. We assumed that all players would check from the start of the game through to the river stage, simulating a conservative gameplay scenario to examine strategic strengths under limited betting dynamics.
In the two-player Texas Hold' em game, convergence speed can be directly measured using exploitabil- ity. The results are shown in TT The public cards in the experiment were 5d2s9d2c7c, and after abstracting the hands, there were hand strength ranks. This sub-game contains approximately 89k information sets, with exploitability measured in BB/100. Compared to MCCFR, MCCFVFP achieved 20-30% faster convergence speed within the same time frame in the two-player Texas Hold' em game.
8

---

Training time (s)
Method
7.74
23.6
70.4
730
7246
MCCEVFP
18.8
6.15
2.68
0.776
0.289
MCCFR
25.4
9.22
3.78
0.935
0.358
Table 1: The convergence rates in two-player Texas Hold' em
Number
Public Cards
Number
Number information
Training time (6)
Number of nodes touched (M)
Battle result (BB/100)
of plavers
band
minks
scts
MCCFVFP
MCCFR
r
CI
4,3
3.3
2.7
1.390
-1,440
# 0,021
5d2s90267c
40.0
30.5
25.0
0.268
-0.277
# 0.015
432.0
301.0
246.0
0.014
-0.014
0.003
3
4.2
3.3
2.9
0.858
-0.922
* 0.026
KsQaJs3h2h
124
113k
40.0
29.9
25.6
0.182
-0,201
# 0.015
410.6
287.0
244.0
0.013
-0,020
0.004
3.6
2.1
1.7
5.380
-5.950
0.071
5d2x902c7c
69
188k
35.2
18.8
12.6
0.515
-0.454
= 0,010
374.4
185.0
144.0
0.096
-0.098
+ 0.002
2.0
1.6
7.930
-8,540
#0,092
KsQsJs3h2h
124
338k
32.0
17.7
13.6
0.935
-0.902
* 0.013
320.0
172.0
131.0
0.035
-0.023
+ 0.004
Table 2: The results of different AIs competing against each other in multiplayer games
In multiplayer situations, the exploitability cannot be directly calculated. Therefore, we use the method of mutual battles to measure the strength of different algorithms. shown in Table | the competition 1, MCCFVFP Al is randomly set player i, and all other players except player are set as MCCFR AI. Define r the rewards of the MCCFVFP AI player at competition The second setting is exactly the opposite. Player i is randomly set MCCFR AI, and the remaining players are set as MCCFVFP Al. Define 72 as rewards of the MCCFR AI player at competition 2. By comparing and r2, can roughly compare the convergence speeds of different algorithms.
In these scenarios, the MCCFVFP AI, trained for the same duration, significantly outperforms the MCCFR algorithm across all aspects. The 30 to 40 seconds training experiment is particularly important, as it closely mirrors the setup of the Pluribus experiment. experiment, the Al trained with MCCFR gained an average of 3.2 BB/100 per game, with standard error of 1.5 BB/100. In our experiment, using community cards KsQsIs3h2h, MCCFVFP gained an average of 0.932 BB/100 compared to MCCFR substantial improvement, especially considering Pluribus gained 3.2 BB/100 against human players.
the 6-player Pluribus
Conclusion
This paper introduces novel method for solving large-scale incomplete information zero-sum games: Monte Carlo Counterfactual Value- Value-Based Fictitious Play (MCCFVFP). By implementing the BR strategy in place of the regret-matchin strategy, MCCFVFP achieved convergence speeds approximately 20% to 50% faster than the most advanced MCCFR variants.
In future research, we aim to evaluate the scalability of our method and its compatibility with different CFR variants, including those incorporating deep networks Brown al. [2019]. Furthermore, given MCCFVFP's efficacy in clear games, envision developing warm start algorithm. This approach would initially use MCCFVFP to eliminate dominated strategies and then switch to algorithms that can further accelerate convergence in the later stages of training.

---

Acknowledgements
This work was supported by the National Natural Science Foundation of China (Grant No. 62103158), We would also like to extend our gratitude to Thomas Tellier for his invaluable as- sistance with our Texas Hold' em experiment. For more information, he be reached via email at thomas@gtoking. com or through his website at gtooiin.com
References
Jacob Abernethy, Peter Bartlett, and Elad Hazan. Blackwell approachability and no-regret learning are equivalent, 2011.
Ulrich Berger. Brown's 's original fictitious play. Journal of Economic Theory, 135(1):572-578, 2007.
David Blackwell. An analog of the minmax theorem for vector payoffs. Pacific Journal of Mathemat- ics, 65(1):1-8, 1956.
Noam Brown and Tuomas Sandholm. Solving imperfect-informationn games via discounted regret minimization. Proceedings of the AAAI Conference on Artificial Intelligence, 13:1829-1836 2019.
Noam Brown and Tuomas Sandholm. Superhuman ai for multiplayer poker. Science, 365(6456)8885- 890. 2019.
Noam Brown and Tuomas Sandholm. Superhuman ai for multiplayer poker. Science, (5566456)eaay24000 2019.
Noam Brown, Tuomas Sandholm, and Brandon Amos. Depth-limited solving for imperfect- information games. Advances in Neural Information Processing Systems (NeurlPS), 31, 2018.
Noam Brown, Adam Lerer, Sam Gross, and Tuomas Sandholm. Deep counterfactual regret mini- mization. In International conference on machine learning, pages 793-802. PMLR, 2019.
G. W. Brown. Iterative solution of games by fictitious play. activity analysis of production and allocation, 1951.
Noam Brown. Equilibrium finding for large adversarial imperfect-infoomation games. PhD thesis, 2020.
Wojeiech M Czarnecki, Gauthier Gidel, Brendan Tracey, Karl Tuyls, Shayegan Omidshafiei. David Balduzzi, and Max Jaderberg. Real world games look like spinning tops. Advances in Neural Information Processing Systems, 33:1 13:17443-17454, 2020.
Constantinos Daskalakis and Qinxuan Pan. A counter-example karlin's 's strong conjecture for fictitious play. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 11-20. IEBE, 2014.
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Faster game solving via predictive blackwell approachability: Connecting regret matching and mirror descent. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 3363-5371, 2021.
Drew Fudenberg and David Levine. The theory of learning games. MIT Press Books, 1998.
Johannes Heinrich, Marc Lanctot, and David Silver. Fictitious self-play in extensive-form games, In International Conference on Machine Learning, 2015.
Ebbe Hendon, Hans Jørgen Jacobsen, and Birgitte Sloth. Fictitious play in extensive form games. Games and Economic Behavior, 1772):177-202, 1996.
Hoane Feng Hsiung Hsu. Deep blue. Artificial Intelligence, 2002.
H. W Kuhn. Simplified two-person poker. Contributions to the Theory of Games, 1950.
Mare Lanctot, Kevin Waugh, Martin Zinkevich, and Michael H. Bowling. Monte carlo sampling for regret minimization extensive games. In Advances Neural Information Processing Systems 22, 2010.
10

---

David S. Leslie and E. J. Collins. Generalised weakened fictitious play. Games and Economic Behavior, 56(2):285-299, 2006.
Junjie Li, Sotetsu Koyamada, Qiwei Ye, Guoqing Liu, and Hsiao Wuen Hon. Suphx: Mastering mahjong with deep reinforcement learning. 2020.
Matej Moravík, Martin Schmid, Neil Burch, Viliam Lis, and Michael Bowling. Deepstack: Expert- level artificial intelligence in no-limit poker. Science, 356(6337):508, 2017.
Larry Samuelson, Dominated strategies and common knowledge. Games and Economic Behavior, 4(2):284-313, 1992.
Martin Schmid, Neil Burch, Mare Lanctot, Matej Moravcik, Rudolf Kadlec, and Michael Bowling. Variance reduction in monte carlo counterfactual regret minimization (vr-meefr) for extensive form games using baselines. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 2157-2164, 2019.
Jiefu Shi and Michael L. Littman. Abstraction methods for game theoretic poker. In International Conference on Computers and Games, 2002.
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, L. Sifre, George van den Driessche, Julian Schritwieser,, Ioannis Antonoglou, Vedavyas Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy P. Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of go with 2016.
deep neural networks and tree search. Nature,
David Silver, Julian Schrittwieser, Karen Simonyan, loannis Antonoglou, and Demis Hassabis. Mastering the game go without human knowledge. Nature, 550(7676)3354 359, 2017.
Oskari Tammelin. Solving large imperfect information games using cfr+. Eprint Arxiv, 2014.
Hang Xu, Kai Li, Bingyun Liu, Haobo Fu, Qiang Fu, Junliang Xing, and Jian Cheng. Mini- mizing weighted counterfactual regret with optimistic online mirror descent. arXiv preprint arXiv:2404. 13891, 2024.
Daochen Zha, Jingru Xie, Wenye Ma, Sheng Zhang, and Ji Liu. Douzero: Mastering doudizhu with self-play deep reinforcement learning, 2021.
Yichi Zhou, Tongzheng Ren, Jialian Li, Dong Yan, and Jun Zhu. Lazy-cfr: fast and near optimal regret minimization for extensive games with imperfect information. 2018.
M. Zinkevich, M. Johanson, M. Bowling, and C. Piccione. Regret minimization in games with incomplete information. Oidsooks.nips.c 10:1729-1736, 2007.

---

A A Toy Example of RM not Performing Well in Clear Game
In training, RM and its variants do not perform well in the clear games, which we attribute excessive exploration of dominated strategies by RM. For instance, consider the rack-paper-seeisoors (RPS) game, where an additional action, Leaky Rock (LR), is introduced for player 1. Set the payoff of action LR to be 0.1 less than that of action Rock (R) (making LR a dominated strategy that no rational player would choose):
0
1
1
1
1
1
0
-1
add action LR
0
-1
(15)
-1
1
0
1
0.1
-1.1
0.9
Assuming that player 1 starts with an average strategy and player2 takes scissors in the first round,
player I's payoff ut' = 0.225. The regret value R (R)
0.225 0.775, R (S)
0 - 0.225 = -02225, R (P) -1 0.225 = -1--.. 1.2225, R (LR) = 0 0.225 = 0.675, Under the RM algorithm, the probability of selecting Rock in the next iteration becomes: o (R) 0.534, and for the Leaky Rock action: (LR) 0.466. Despite LR being dominated strategy, RM still assigns nearly half the selection probability, arguably wasting nearly half the computational resources. However, in Fictitious Play (FP), the LR action would never be chosen.
B Convergence of CFVEP
B.1 Blackwell Approachahility Game
Definition 1 A Blackwell approachability game in normal-form two-player games can be described as a tuple S', ,5²), where E is a strategy profile, u is the payoff function, and S = R1A' is closed convex target cone. The Player i's regret vector of the strategy profile a is Re (a) E for each component R² (az) = u² (az; u² (o),
, Or E A't the average regret vector for players
i to take actions at T time a is Rr
T
R T Σ R((o)
(16)
At each time t, the two players interact in this order:
Player chooses a strategy of E E,,
Player 2 chooses an action of E E², which can depend adversarially on all the o¹ output far;
Player 1 gets the vector value payoff (ot) E ER..
The goal of Player I is select actions
Σl such that matter what actions of oz.... E E² played by Player 2, the average payoff vector converges to the target set S!.
min #ES1
Rt112
0
as +
(17)
Before explaining how choose the action o, ensure this goal achieve, we first need to define the forceable half-space:
Definition Let H. C Rd as half-space, that is, for some a E R {a E Rd a $ b). In Blackwell approachability games, the halfspace H is said to be force- able if there exists strategy g²* E of Player i that guarantees that the regret vector R (o) is in H no matter the strategy played by Player -i, such
such that
R' (a in ,0 _00 E VoT E Σー
(18)
And gi^ forcing action for H.
Blackwell's approachability theorem states the following.
12

---

R2
H
S
Figure 3: The difference between RM and FP (CFVFP in normal-form game) in two-dimensional plane
Theorem Goal can be attained if and only if every halfspace Hi 2 S is forceable.
The relationship between Blackwell approachability and no-regret learning is:
Theorem Any strategy (algorithm) that achieves Blackwell approachability can be converted into an algorithm that achieves no-regret, and vice versa Abernethy al. (2017)
Let o. be the average strategy of player i:
(19)
In a two-player zero-sum game, the exploitability of the average strategy o at time of player i dj max.'a (a') Brown [2020). Obviously, the regret value is always greater than the exploitability:
lim er T-x00
lim T-000
Σ
ct < lim Σ min || Rirll2= =0
(20)
T0000
BEST
VEN
So, if the algorithm achieves Blackwell approachability, the average strategy o. will converge to equilibrium with T + co. The rate of convergence is ctp S R2 < T.AAA/VT
B.2 Fictitious Play achieves Blackwell Approachability
We first prove that FP achieves Blackwell approachability in a two-player zero-sum game. Define Ri be the maximum portion of vector R R. R.. o 0. we find the point y/ = Ri R.
in RRA' and let
R: + be the normal vector, then can determine half-space by
R v.
and t/;
R +.
HP {z EZER' (R) wb)) 2 - (R, +b)) TTb
(21)
Because Ri 2/, Ri
(R; - -T, $b = 0, therefore:
H¹ = fz + TR' mmm 50
(22)
For any point s' S there is (R. ss) S 0. Then we need prove that a forcing action for H. indeed exists. According to Definition 2, we need to find of E' that achieves R (of41, HiP for any o. I-t For simplicity, let l = [u' (aI, .... 1
13

---

we rewrite the regret vector as R (0 = = - 1, we are looking for a o E E' such that:
(ott11 o E HH
R max
(c,o(t1) 1
0
Rixmax
(e, 1)
R Ri.maxx
_
Ri max
(e, (2ottt)) )
|2g.max ||
00
(23)
R
Rl.max
l
(e, 50
Rg
Rl.max
[
max
e
00
[
max
We obtain the strategy 0f41
Ri-max [
that guarantees HP to be forceable half space. And
the action with the highest regret value is actually the BR strategy Brown [2020], so FP achieves Blackwell approachability. Figure shows the difference in forceable half spaces for BR and RM strategies in the two-dimensional plane. According to BR strategy is also regret minimizer in normal-form game. Therefore, replacing the RM strategy with the BR strategy in CFR does not affect the convergence of the algorithm.
B.3 The convergence speed of FP and clear games
However, it is important note that the convergence point of FP differs from that of RM Specifically,
the convergence point for FP is the R2 max while for RM it v/RM R R R The
relationship between these two points can be expressed ||v:RM la V
[A]. The convergence
rate of RM is O (LVIAI/T) Consequently, the overall convergence rate for FP is O (LIAI/T).
In Section 3 we have analyzed that the RM strategy may select a dominated strategy, whereas FP will not. Therefore, representing the complexity of the problem using [A] for FP is inaceurate. If an action a' is dominated strategy, then it cannot be the best response, i.c., b(o) * a'. Hence, in FP, we can replace |A| with And, where A AA' is the set of non-dominated strategies in the game. This adjustment leads the FP convergence rate being O (L]Anal/VT])
We now define a "clear game" as follows: when the number of non-dominated strategies in a game satisfies [Anal < vIAA), the game is considered clear game. In Figure [ the square root 100 is 10, aligning with theoretical expectations. In clear games, even when the number of iterations is used as a measure, the convergence speed FP will outperform that of RM.
C Pseudocode
C.1 CFVFP
The pseudocode here does not join the rest of the variants, nor does consider cases other than two-player zero-sum.
C.2 MCCFVFP
Since MCCFVFP will directly sample actions on opportunity nodes, the efficiency of the MCCFVFP algorithm will be higher than CFVFP. The pseudocode of MCCEVEP is shown in pscudocode 2
14

---

Algorithm CFVFP(s, n. )
1: i' = 0 or क" then
2: return [0, 0]
3: end if
4: if' E Z then
5: return [u (5) (
6: end if
7: Define 1 as the information set to which s belongs
8: [0
9: if P()) c then
10:
for A(s) do
11: r' -PFRRs + + ,,)
(ps)
13: end for return
15:
else
if' P(s) = p1 then
17:
To π π
Ps.Pa Po P1.Pa P2
19:
else
Tas No n² T
21:
Pa.Po Po P2.P1
22:
end
23:
if
To = then
24:
= CFVFP(s + (
25:
r(po) = (p,)
26:
(1) = ((t- 1-- (1) of
27:
else if n
then
28:
for a E A((T) do
29:
r' = CFVFP(s + n,
30:
(I, =
r
31:
if a (1) then
32:
r(po) r'
33:
end end for
34:
35:
of (T) = max ma Q (I
36:
else
37:
for E A(I) do nr = (T,a)
38:
39:
r' CFVFP(s 7.)
40:
(I, = (T (p.)
41:
r(po) = r(pp) r
42:
r(p.) r(p.) + (I,a)
43:
end for
44:
of' (7) ((1 1)o{= (f)+
45:
of (T) = x 0 (T,a)
46:
end if
47:
end if return
48:
D
Comparison between variants of CFVFP
D.1
CFVEP variants
We integrated CFVFP with RM+ and MC variants, resulting in four distinct combinations: CFVFP, CFVFP+, MCCFVFP, and MCCFVFP+. Figure illustrates that MCCFVEP and MCCFVFP+ consistently outperform CFVFP and CFVFP+ in terms of results. However, the performance of
15

---

Algorithm 2 MC
1: i' then
2: return 0]
3: end if
4: if E Z then
5:
return [u' (s)x", ((()),)
6: end if
7: Define 1 as the information set to which s belongs
8: [0,0]
9: if P(s) = then
10: a~o
11: =-PMCCFR(s + +0,
return
13: else
if P(s) = p1 then
15:
π π²²
Ps.Po Po P1.P2
17:
else
Ta No x2, = Po P2.P1
19:
end if
21:
if To then
22:
y'= MCCCFCPPs ((()),
23:
r(pa) = =r'(po)
24:
of (1) = ((t 1--1))22000 +o, of (1))/t
25:
else if n. 0 then
26:
for a E A(1) do
27:
r' = MCCFVFP(s a.
28:
(I, = Q (I,
29:
op* (I) then r(p)) r'
30:
31:
end
32:
end for
33:
"P (1) = max (I) (1 (1,a)
34:
else
35:
for
a E A(I) do T; (I)
36:
37:
= MCCFVFP(( + x)
38:
(I, = (T=1(T r'
39:
r(po) r(p)) tr'(p))
40:
r(p=) = r(p)) + tr' (1,
41:
end for
42:
a.' (T) = ((t 1) (T) + o (T))/t f = arg max ap Q (I,
43:
end
45:
end if
46: return r
MCCFVFP and MCCFVFP+ varies across different problem sets. Based on these observations, ultimately selected the more conservative MCCFVFP method.
D.2 Weighted Averaging Schemes for CFVFP
Different weights of CFVFP will also have significant impact on the results. The weight is introduced into (T):):
Q (Q) + w (I,0z) if m²) = (1)
(24)
otherwise.
16

---

3-Card 1-Action Lan tedue
10-Card L-Aztion I-ien Kuhn
0.0
-15
lg15Explatbbiig
-05
25
3.0
-2.0
nodes touched
168
nodes touched
3-Card 1-Mction Len Leduc
10 L-tction 1: Kuhn
0.5
log 1001000xoooo. Milkkalble
MCCPy
-25
-2.0
timelmm))
106
time.ms)
126
Figure 4: Convergence rate of MCCEVFP variants in different games
Common Wi values are Wi = 1, Wi = log l, W/ = f,, w) = f2 The Figures 5 show the experimental results with different weights. In the comparison of four common w/, convergence is faster when
1-Len
10
-1.52
-0.50
-1.75
-0.75
S-2.00
11.00
-2.25
-1.25
-2.50
-1.50
-275
1.75
-2.00
-2.25
-1.0
0.5
1.2
02
3.2
nodes touched
touched
L-Action 1-tan
-0.50
-150
MCL/VE lowe
MCMV las
sqare
1..00
+1.25
250
2775
1.75
-2.00
60
0.6
1.0
Emelms)
diooimi
166
Figure 5: Convergence rate of different weighted average schemes for CFVFP
Wt =
E Proof of conclusion in theoretical analysis of CFVFP algorithm
E.1 Time Complexity of CFR and CFVFP in an Information Set
Due to its significantly streamlined calculation process, CFVEP requires far less computation per information set compared to CFR Consider information set with possible actions, denoted as A(T) = a1, ..,..., Oz- If the counterfactual payoff w(J, a) for each action is known, then:
The calculations required for CFVEP in one information set are:
17

---

0.19
10.1)
(9.1)
F2
11.11
10.1)
10.00
(0.0)
(0.00
Figure Game tree when each node has levels and g = 3 actions. The number (M (s), +²(s)) in each node represents the probability of playerl and player2 reaching this node respectively.
1. Add the counterfactual payoff u' (1l1)1)))) to the counterfactual value Q7 a), this step requires x additions;
2. Find the maximum value Q (1) (get BR strategy), this step requires a comparisons;
3. Update the BR strategy to the average strategy, this step requires addition;
total of 2x + additions.
The calculations required for CFR in one information set are:
1. Get average counterfactual payoff (I) from w' (I,orlz-a) and strategy (I),,, this step needs x multiplications and additions;
2. Get regret value R(T, a). this step needs x additions;
3. Multiply the regret value R(T, a) by (T! and add to the average regret value Rr a). this step needs additions and multiplications;
4. Compared Regret value with 0, this step needs comparisons;
5. Add up the positive regret values, this step needs x additions;
6. Get regret matching strategy, this step multiplications:
7. Update the RM strategy to the average strategy, this step needs additions;
A total of 6z 2 additions and 3æ multiplications. It can be seen that in one information set, CFVFP only takes 2/9 of the time CFR.
E.2 Number of nodes touched in one iteration
In a deterministic game tree with h levels and g actions per node (no chance nodes), such as g h scenario depicted in Figure 6 nodes are categorized into four distinct types (sall (St, $g. Sb. sy)).
The probability of all players reaching this node is (red node s,);
The probability of all players reaching this node 0 (green node sg). and these nodes can be pruned;
The probability of the current player reaching this node is 1, and the probability of other players is 0 (blue node s,);
The probability that the current player reaches this node is 0, and the probability of other players is (yellow node s,);
We define the nodes that must be touched as $pass=(e, The figure shows that each level has single red node, with yellow and green nodes following a blue node, which is derived from red and
18

---

yellow nodes. The function F) quantifies the count of each node type across layers to h.
Fh (5r) =1
Fh (sg) = -gEn-1 (5g) + (g 1 Fh (5b) (9-1)) (8t) + - (sy)
(25)
Fn (sy) = Fh-1 (16)
the general term formula for blue node Sb in the h layer is:
Fn (s)) = (g 11 (8,) + - (8y)
= =g 1)1 -
(26)
= (g - 1) + + ((g - 1) + gf sf (bb))
after simplification:
((h 2
(x)2(8)) (g 1)
(27)
The number of nodes that need be touched Spass in the level game tree is:
Fh (spuss) = Ph. (st) - Fn (5%) + Fh (sy)
(28)
=1+ Fh. (36) Fh-1 (sb)
Leh 1(h-2)/2
[(b-3)/2]
F = 1 (g 1)
Σ
g + (g 1)
Σ
g".
(29)
i=0
The number of node san the entire level game tree is:
g" 1 g"
(satt))
Σ
(30)
In two-player game, it can be approximately considered that (sa(s / (Spus)) so CFVFP only needs touch O (VIsi) nodes in one iteration. Extending the results to multi-player games,
CFVFP only needs to touch O ( (WV[si) nodes. At the same time, CFR must traverse all ([S)) nodes.
F Experiment Supplementary Notes
F1 Description of the game
F111
Kuln-ertensionLLetuu--eeeeioo poker
We have made improvements to Kuhn and Leduc Poker:
1. The original Ledue and Kuhn poker types are 3 cards, and in the improved game the types are x 2 3 cards;
2. The original Ledue and Kuhn can only raise one fixed chip, but in the improved game is allowed to raise 2 chips of various sizes. The Bet Action raise size here adopts an equal proportional sequence in multiples of 2. For example, when the blind bet is and y 4, the allowed raise action [1, 2, 4, 8]:
3. The original Leduc and Kuhn can only raise once in round. After one player raises, the rest of the players can only choose to call fold, and cannot raise larger bet. the improved game, it can be raised up to times.
19

---

F.1.2 Princess and Monster
Princess and monster (PAM) is a game in which two players chase and escape in dungeon with obstacles 4-connected grid diagram of m n). The game rule is:
The two players are monster and princess, and each player knows the structure of the dungeon and which rooms can be accessed.
They can only exist in one particular dungeon at a time, and they all know the number of their current dungeon (grid).
The monster's goal is to find and capture the princess as soon as possible.
The princess's goal to escape the monster as much as possible.
The actions they can choose are:
the initial stage, monster and princess can choose any birth room to start the game; In the following process, monster and princess choose to space per step in four directions, up, down, left and right, or stay in place. When moving, they cannot exceed the dungeon boundary or enter impassable rooms.
Result of the game:
the same time, if the monster and princess appear in the same dungeon, the game ends. The princess survives the round and gets n utilities, and the corresponding monster gets utilities.
If the monster does not capture the princess within certain number of steps (such as N move), the game ends directly. The princess earns N utilities and the monster earns -N utilities.
Figure The structure of the dungeon.
As shown in Figure 7 we set the dungeon to 3x3 grid, with inaccessible rooms in the upper left and right corners.
F22 The Rest of the Experimental Results
We measured the number of information sets and the number of nodes in different games in Table 3 and there are rest of the experimental results in Figure R
G The difference between time, nodes touched and iterations as indicator
In previous papers, many convergence analyses were performed based on the number of iterations T. which is obviously unfair to the sampling CFR/CFVEP algorithm. For sampling algorithms, many studies have used the number of nodes to analyze the convergence of the algorithm, but these studies have ignored the inconsistent calculation time of different nodes and the inconsistent number of information sets that have passed through the same node. The cost of an iteration CFR/CFVEP is divided into two parts: the game tree traversal cost and the RM/BR strategy cost calculated on the information set:
On each information set: It is necessary to calculate the RM/BR strategy and update the average strategy for the passed information set. These costs have been detailed in E..
20

---

Game name
Information set
Number of nodes
RPS
2
13
3 C P L Kuhn
12
55
C P L. Kuhn
60
1891
C L Kuhn
200
22051
3 C. P.3 I. Kuhn
48
271
7C333L Kuhn
112
1891
7C533L Kuhn
364
6427
15 3 Kuhn
780
32131
C Kuhn
1920
80011
3 C Leduc
288
1945
7 C Leduc
1512
25985
15 C Leduc
6480
255601
25 C Leduc
18900
1 1180001
3 C P Leduc
1680
12529
7 C P Leduc
9016
172313
15 C Leduc
41160
1712521
C. Leduc
6399
49384
7 P Leduc
34587
685280
15 C P Leduc
158355
6831856
4 round PAM
224
68815
round PAM
794
715655
round PAM
2804
7447021
Table 3: Information sets and node number record for different games
12000149.
Figure 8: Convergence rate in Leddnc-xtennsion, Kuhn-extension, Here Action and Len are both 1.
There are three types of nodes on each game tree node, of which need get the counterfactual utility of each player. The difference is:
On the player node, the counterfactual utility needs to be obtained on this type of node u² (s, 0x) or/r-aa) and multiplied by the strategy return.
On opportunity nodes, in this type of node need get virtual utility w' (Llaz) and multiplied by opportunity node probability.
On the end point node, it is necessary to solve the final income according to the node on this type of node.
When passing through the same number of nodes, different algorithms do not pass through the same number of information sets. For example, when using the CFR algorithm train vanilla Kuhn poker (assuming no pruning), one iteration passes through 55 nodes (24 player nodes. I random node, 30
21

---

leaf nodes), and calculate regret matching strategies on 12 information sets, at this time, the ratio of information set calculation and node calculation is 12:55. While using MCCFR the calculation passes through 10 nodes (4 player nodes, random node, 5 leaf nodes), and calculate regret matching strategies on 4 information sets, the ratio of information set calculation and node calculation 4:10. And the computing time is different at different decision, opportunity, and end point nodes. Therefore, measuring the performance of the algorithm by the number nodes passed does not objectively reflect the ability of the algorithm.
22

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: I believe that the abstract and introduction accurately reflect the contribution and scope of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: At the end of the paper we pointed out that our algorithm needs larger-scale experiments and is combined with more CFR variants.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
23

---

Answer: [NA]
Justification: think the theory about CFVFP has been well proven, but is just a conjecture that the large game is clear game. The correctness of this conjecture needs to be verified in more problems.
Guidelines:
The answer NA means that the paper does include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We have made our code available for inspection and reproduction
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
24

---

reproducible, they Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification: The code we provide can ensure that the results of this paper are reproduced, but this paper relies on the assumption that large-scale games are a clear game, which not necessarily 100% certain in large-scale games.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
mublicc/uuiee/CCdeSuuuiii sww.:/oubbbiiioooooooooooo. for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/mipss.cc/pulli/guiddee htt///CooSSSeiiaaeeeeeee ssisssssicyyyyy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permirted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [No]
Justification: Our Texas Hold' em experiments were conducted using commercial solver, so we are unable to share this part of the code. However, the experiments on smaller-scale games have been made publicly available.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
All our experiments are labeled with confidence intervals.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
25

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CL, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide a detailed account the resources required for all experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer:
[Yes]
Justification:
We believe that our research complies with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work is very theoretical and there is no need to discuss social implications.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
26

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our research does not cover this aspect.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
27

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: together in the submitted code.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "Pt8ccwwCPG", "reviewer": "Reviewer_H6L6", "summary": "The paper introduces a new algorithm called Monte Carlo Counterfactual Value-Based Fictitious Play (MCCFVFP) for solving extensive-form imperfect information games. This algorithm combines the counterfactual value calculations of Counterfactual Regret Minimization (CFR) with the best response strategy of Fictitious Play (FP). The authors demonstrate that MCCFVFP accelerates convergence to Nash Equilibrium (NE) significantly faster than existing Monte Carlo CFR (MCCFR) variants, especially in games with a high proportion of dominated strategies. They highlight its superior performance in large-scale settings, such as two-player limit short deck Texas Hold’em poker, where the blueprint strategy developed by MCCFVFP outperforms that developed by MCCFR.", "questions": "1）In Figure 2, the author only compared CFR+. I believe DCFR and PCFR should also be compared.\n\n2）How sensitive is MCCFVFP to the proportion of dominated strategies in a game? Is there a clear threshold where it starts to outperform MCCFR?\n\n3）Have you investigated how MCCFVFP performs in multi-player games beyond two players?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "The paper introduces an interesting integration of CFR's counterfactual value calculations with FP’s best response strategy, creating an approach to accelerating convergence in Monte Carlo settings. This combination provides a new perspective on solving extensive-form games. The theoretical proofs and experimental results are robust, showing evidence of MCCFVFP’s good performance in both convergence speed and practical application to large-scale games. The proposed algorithm has implications for the field of game theory and artificial intelligence, particularly in developing efficient strategies for large-scale, imperfect information games. This can have practical applications in various domains, including poker and other strategic games.", "weaknesses": "I believe the biggest drawback of this paper is its writing. Only readers with a deep understanding of CFR can comprehend the content of the article relatively smoothly. I think the author needs to include more background information in the main text, especially since it is currently only 8 pages long, and NeurIPS allows up to 9 pages.\n\nThe article contains numerous undefined symbols and typos, which greatly hinder the reader's understanding. It gives the impression that it was written in haste and requires thorough proofreading.\n\nLine 58: ****\n\nLine 72: u^i has never been defined.\n\nLine 107: L has never been defined.\n\nLine 157: R_i^i\n\nLine 175: The same sentence appears twice.\n\nLine 192: 6x−Ittakes2\n\nLine 279: Table 1 liner\n\n...", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your meticulous reading of the paper and for raising very valuable new questions.\n\n## Paper Writing\n\nRegarding the typos in paper writing, we will thoroughly revise the paper.\n1. **** At line 58, there is a hidden GitHub link. In the camera ready version, this link will be displayed.\n2. The definitions of these notions are all in Appendix A and will be incorporated into the main text in the revised version. Here, I will briefly explain the meanings of these symbols. Define $\\Sigma^i$ as the strategy set of player $i$, where $\\sigma^i\\in\\Sigma^i$. A strategy profile $\\sigma=\\mathop{\\times}\\limits_{i\\in \\mathcal{N}}\\sigma^i$ is a collection of strategies for all players, $\\sigma^{-i}=(\\sigma^1,\\dots,\\sigma^{i-1},\\sigma^{i+1},\\dots)$ refers to all strategies in $\\sigma$ except player $i$. $\\Sigma=\\mathop{\\times}\\limits_{i\\in \\mathcal{N}}\\Sigma^i$ denotes the set of strategy profile, $\\sigma\\in\\Sigma$. Define $u^i: \\Sigma \\rightarrow \\mathbb{R}$ as the finite payoff function.  $L=\\max_{\\sigma\\in\\Sigma,i\\in\\mathcal{N}}u^i(\\sigma)-\\min_{\\sigma\\in\\Sigma,i\\in\\mathcal{N}}u^i(\\sigma)$ represents the payoff interval of the game. Let $\\sigma_t^i$ be the strategy used by player $i$ on round $t$. The average overall regret of player $i$'s action $a^i$ at time $T$ is:\n$\\bar{R}_T^i(a^i)=\\frac{1}{T}{\\sum}u^{i}(a^i,\\sigma^{-i}_t)-u^{i}(\\sigma_t)$  \n   \n3. The errors at line 175, 192, and 279 will be corrected in the camera ready version.\nIndeed, as you said, I mistook the limit on the number of pages of the paper and placed some definitions and notions in Appendix A, which made our work less reader-friendly. I will re-adjust the writing order in the revised version and provide more detailed explanations of the basic definitions, the purpose, and the significance of the paper. My outline of the revisions is in our global response part 1 \"Regarding Writing\".\n\n## Question 1 \"DCFR and PCFR should also be compared\"\n\nThis is a very valuable suggestion. We have made extensive modifications to the experimental part. DCFR, DMCCFR, and PCFR have all been added as baseline algorithms. In addition to adding the comparison baseline, we added three new games: vanilla Kuhn, vanilla Leduc, and  10-Card 1-Action 1-Len Leduc. In larger-scale games (15-card 1-action 1-len Leduc / 50-card 3-action 3-len Kuhn / PAM), these newly added baseline algorithms are still inferior to the MCCFVFP and CFVFP algorithms proposed by us. You can refer to our global response part 3 \"Experiments\" for details. \n\n## Question 2 \"Is there a clear threshold where it starts to outperform MCCFR?\"\n\nThis question is very interesting and meaningful. Define $\\mathcal{A^i_\\text{nd}}\\subseteq \\mathcal{A^i}$ to represent the set of non-dominated strategies in a normal-form game. We proved that the threshold between tangled game and clear game is $|\\mathcal{A_\\text{nd}}|\\le \\sqrt{|\\mathcal{A}|}$ (In global response part 2 \"The definition of clear games\"). In our toy problem (a normal-form game with 100 actions), it is exactly $10\\%$. So, thank you very much for your suggestion, which prevented us from missing a guiding conclusion for the paper. The proof will be added to the camera-ready version of the paper.\n\nHowever, we can only find the threshold of clear-game in normal-form games. Discovering a clear threshold in extensive-form games is extremely complex. We consider this to be a very valuable study and will attempt to solve this problem in future work. \n\n## Question 3 \"Have you investigated how MCCFVFP performs in multi-player games?\"\n\nThe direction you proposed is very insightful. I would like to briefly restate the theory of our paper: CFVFP is a Blackwell Approachability method, which means that in multiplayer games, CFVFP, like CFR, can converge to a coarse correlated equilibrium [1].\n\nIn the latest research, we developed a commercial Texas Hold'em solver based on MCCFVFP (already online), completing the performance of MCCFVFP in multiplayer games. In 3-player and 6-player Texas Hold'em subgame, the performance of MCCFVFP exceeds the traditional MCCFR algorithm by approximately 40%. For more results, you can refer to our global response part 3 \"Experiments\" for details.\n\n[1] Zhang H, Lerer A, Brown N. Equilibrium finding in normal-form games via greedy regret minimization[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2022, 36(9): 9484-9492.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ATF5FUFOGt", "reviewer": "Reviewer_KPRH", "summary": "The paper proposes a new algorithm for solving extensive-form imperfect information games that relies on Monte Carlo (MC) simulations. The method abbreviated MCCFVFP combines MC settings with Counterfactual Regret Minimization (CFR) and the best response strategy of fictious play. Experimental evaluation demonstrate its speed advantage over the state-of-the-art competitors, in particular in clear games (i.e. games in which the vast majority of strategies are dominated ones).", "questions": "-- See points 1 and 2 in weaknesses\n-- The results for tangeled games are not so strong as for the clear games. At the same time tangeled games are intuitively much more complex than clear games, which shows certain limitations of the proposed method. Please comment on that.\n\n-- Random games with 21845 nodes do not seem to be challenging. Would the conclusions hold for much larger random games?\n-- In section 5.3. the numbers of stored information sets of both methods are equal. Is it really the case or there is a mistake there?", "limitations": "The limitations are not explicitly specified.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The method clearly outperforms competitive approaches in terms of convergence speed. The method is particularly well suited for clear games, i.e. the ones with over 90% of dominated strategies, as reported by the authors.", "weaknesses": "1. The paper has not been carefully revised before submission and there are certain issues that hinder is smooth reading and understanding. For instance, $u^i$ is not explicitly defined in the paper (I assume it is the payoff of player $i$) and in some cases is a one-argument function, in other case a two-argument one (cf. eq. 2). Similarly, $R_{T}^{i,+}$ in eq. 5.\n\n2. A discussion in section 5.2.1. is rather accidental. Some plots in Fig. 2 are addressed while the other are not mentioned (e.g. Princess and Monster plots).\n\n3. RM is not explicitly defined in the paper – it is only defined in the appendix", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are extremely thankful to the reviewer for their feedback and very insightful questions. We address them below.\n\n## Weakness 1&3 Paper writing\n\nThe issues you pointed out are crucial for improving the paper's readability. We will carefully revise the paper. And I think it's necessary for me to rewrite the Introduction and Notation and Preliminaries sections. The specific revision outline can be referred to (in our global response part 1 'Paper Writing').\n\nFor the specific problems you pointed out. Define $\\Sigma^i$ as the strategy set of player $i$, where $\\sigma^i\\in\\Sigma^i$. A strategy profile $\\sigma=\\mathop{\\times}\\limits_{i\\in \\mathcal{N}}\\sigma^i$ is a collection of strategies for all players, $\\sigma^{-i}=(\\sigma^1,\\dots,\\sigma^{i-1},\\sigma^{i+1},\\dots)$ refers to all strategies in $\\sigma$ except player $i$. $\\Sigma=\\mathop{\\times}\\limits_{i\\in \\mathcal{N}}\\Sigma^i$ denotes the set of strategy profile, $\\sigma\\in\\Sigma$. Define $u^i: \\Sigma \\rightarrow \\mathbb{R}$ as the finite payoff function. We write  $u^i(\\sigma^i, \\sigma^{-i})$ for the expected payoff to Player $i$ if they select pure strategy $\\sigma^i$ and all other players play the strategy profile $\\sigma^{-i}$. Let $\\sigma_t^i$ be the strategy used by player $i$ on round $t$. The average overall regret of player $i$'s action $a^i$ at time $T$ is $\\bar{R}_{T}^{i}(a^i)=\\frac{1}{T} \\sum u^{i}\\left(a^i, \\sigma^{-i}_t\\right)-u^{i}\\left(\\sigma_t\\right)$.\n\nThe definitions of these notions are all in Appendix A and will be incorporated into the main text in the revised version. I'm sorry for the bad reading experience.\n\n## Weakness 2  Some plots in Fig. 2 are addressed while the other are not mentioned\n\nThe issue you pointed out is indeed significant. We briefly introduce the functions of the unmentioned pictures in the section 5.2. The experimental result of PAM is to indicate that although the convergence speed of CFR+ algorithms was considered to exceed CFR, there are still some specific games (such as PAM) where the convergence speed of CFR+ is slower than the vallina CFR. However our proposed MCCFVFP and CFVFP are not affected. And 50 Card 3 Action 3 Len Kuhn shows that our algorithm has good performance in different games. These explanations will be added to the revised paper.\n\n## Q1: The results for tangled games are not so strong as for clear games. At the same time tangled games are intuitively much more complex than clear games, which shows certain limitations of the proposed method.\n\nThis question is very valuable. We don't think there are limitations to our algorithm in most cases. Firstly, the  training metric of the algorithm in Figure 1 uses the number of iterations. In the caption of this figure 1, we also clearly pointed out that the time complexity of one iteration of the FP algorithm is $\\mathscr{O}(|\\mathcal{A}|) $ and that of the RM algorithm is $\\mathscr{O}(|\\mathcal{A}|^2)$. If you take this into consideration, there is no significant difference in the convergence speed between FP and RM.\n\nSecondly, in lines 137-145 of the paper, we used many examples to illustrate that the proportion of dominated strategies in large scale games may be very high. So for actual games (such as Texas Hold'em), MCCFVFP will be a more suitable method. Moreover, in the latest experimental progress, we have developed a commercial multiplayer Texas Hold'em solver based on the MCCFVFP algorithm, and this solver is already online. We tested the effects of the MCCFVFP algorithm and the MCCFR algorithm in 2/3/6player no-limit Texas Hold'em in this solver. In these settings, the convergence speed of MCCFVFP leads MCCFR by 40%-50% (In global response part 3 \"Experiments\").\n\nFinally, lines 190-196 of the paper (and Appendix G.1) state that the implementation of MCCFVFP is particularly simple. It only requires 2/9 of the operation time of MCCFR.\n\nBased on the above factors, we don't think the use of MCCFVFP will be limited. Moreover, in our experiments, no case indicates that the convergence speed of MCCFR is faster than that of MCCFVFP.\n\n## Q2.1 Random games with 21845 nodes do not seem to be challenging\n\nWe don't think this will affect the effectiveness of our algorithm. This part of the content only shows that our theory is still valid in extensive-form games. The reason why no larger-scale experiments were conducted is that this experiment needs to generate the entire game tree before running and store the reward of all leaf nodes in the memory. It cannot calculate the reward of each leaf node in real-time searching according to the game process like other games, so using python to expand the scale is a little bit difficult. But we believe this scale is sufficient to explain our point of view.\n\n## Q2.2 In section 5.3, the numbers of stored information sets of both methods are equal.\n\nThe issue you pointed out is correct. This is attributed to my negligence in code development. Thank you very much for pointing out this problem. In the original version of the paper, we used the Openspiel framework developed by Deepmind for development. In this framework, the final strategy was not pruned. So 299376 is the number of information sets of the entire game, not the number of actually explored non-dominated nodes. We have updated all the content of this part. As mentioned earlier, we have developed a Texas Hold'em GTO solver based on MCCFVFP and conducted a comprehensive re-experiment. For details, you can refer to global response part 3 \"Experiments\".", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jHLTFHVDHe", "reviewer": "Reviewer_APT4", "summary": "The paper introduces a novel algorithm, Monte Carlo Counterfactual Value-Based Fictitious Play (MCCFVFP). This algorithm aims to accelerate the convergence of Nash Equilibria in extensive-form imperfect information games. MCCFVFP combines the counterfactual value calculations from Counterfactual Regret Minimization (CFR) with the best response strategy from Fictitious Play (FP). The authors claim that MCCFVFP achieves up to three times faster convergence compared to advanced MCCFR variants and significantly outperforms them in large-scale games with a high proportion of dominated strategies.", "questions": "Can the authors describe a bit about the comparison between MCCFVFP with reinforcement learning approaches for extensive form imperfect information games?", "limitations": "yes", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper introduces a unique and novel combination of counterfactual value calculations with fictitious play, leveraging strengths from both methods.\n- The theoretical analysis proving the convergence of MCCFVFP adds a strong foundation to the empirical results.\n- MCCFVFP is shown to achieve significantly faster convergence rates in extensive-form games, particularly in scenarios with a high proportion of dominated strategies.", "weaknesses": "The paper could provide a more detailed comparison with a broader range of existing algorithms beyond MCCFR variants to establish a more comprehensive performance baseline.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments and observations on our work. Below we address the questions raised and the discussed weaknesses:\n\n## Provide a more detailed comparison:\n\nWe update the experimental evaluation part (in global response part 3 'Experiments'), we compared our algorithm with different algorithms including DCFR and PCFR, both of which are classified as CFR rather than variants of MCCFR. I'm not sure if you want me to compare the algorithm with some reinforcement learning (RL) methods. However, generally, these methods do not perform as well as CFR, the no-regret learning algorithms [1], in imperfect information games, and there are significant differences in their usage. Therefore, we do not consider comparing our algorithm with RL algorithms for now.\n\n## Describe about the comparison between MCCFVFP with RL approaches:\n\nThis is a very insightful viewpoint and also a future research direction for us. Firstly, the purposes of RL and game learning algorithms are different. RL algorithms generally require the environment to provide a reward function, and the goal of RL algorithms is to find a strategy to obtain more rewards. In game learning algorithms, the environment does not provide a fixed reward function, and the goal of game algorithms is to learn a Nash equilibrium strategy, while the Nash equilibrium strategy is often not the case with the most rewards (such as the famous Prisoner's Dilemma).\nHowever, the algorithm proposed in this paper has many similarities to the Q-learning algorithm in RL at the implementation level, including the definition of Q-values and the update method of the Q-value table. So, how to modify our algorithm(MCCFVFP) to make it conform to the current mainstream RL framework and be used to solve a wider range of problems is an interesting research direction. We will also continue to work on this in the future.\n\n[1] Brown N, Sandholm T. Superhuman AI for multiplayer poker[J]. Science, 2019, 365(6456): 885-890.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
# Global Response to All Reviewers

We thank all the reviewers for the detailed comments and constructive feedback. We found that many reviewers pointed out the same issues, including the writing of the paper, the related problems of clear-game, and the experimental part. Here, we will explain the problems in these three aspects uniformly.

## Paper Writing

We will proofread our paper in the revised version to ensure there are no typos. We will:
1. Rewrite the Introduction sections of the paper, ensuring that the background and purpose are clearer to make the advantages/disadvantages of the algorithm more obvious.
2. Update the Notation and Preliminaries sections of the paper. Move the definitions of Normal-form Game and RM from Appendix A to the main text to ensure the readability of the paper and enable people who are not familiar with CFR to understand the theoretical basis of the paper.

## The definition of clear games

In the original paper, we defined a game with a non-dominated strategy proportion of less than 10% a clear game. This definition is not scientific. We try to find a more appropriate explanation theoretically. Define $\mathcal{A^i_\text{nd}}\subseteq \mathcal{A^i}$ to represent the set of non-dominated strategies in the game. We have theoretically proved that, in normal-form games, the convergence speed of CFVFP is $\mathcal{O}\left( L|\mathcal{A_\text{nd}}|/\sqrt{T}\right)$, and the convergence speed of RM is $\mathcal{O}\left(L\sqrt{|\mathcal{A}|}/\sqrt{T} \right)$ , where $L=\max_{\sigma\in\Sigma,i\in\mathcal{N}}u^i(\sigma)-\min_{\sigma\in\Sigma,i\in\mathcal{N}}u^i(\sigma)$ represents the payoff interval of the game. Now we define a clear game as follows: When the number of non-dominated strategies of a game satisfies:
$$|\mathcal{A_\text{nd}}|\le \sqrt{|\mathcal{A}|}$$
The game is called a clear game. So in a matrix game with 100 actions, this proportion is exactly $10\%$, which is consistent with the conclusion of our toy experiment in paper. We will add this proof to the appendix and more experiments to verify the reliability of this proportion.

## Experiments

All reviewers pointed out that our experimental results were not sufficient (including game size setting / number of players / baseline selection). This is a very important suggestion, so we added more experimental results to the content of Section 5.2 and Section 5.3 of the paper. 

### Section 5.2

In terms of the comparison baseline, DCFR, DMCCFR[1], and PCFR[2] were all added to the experiment. In addition, we added three new games: original kuhn, original leduc, and 10-leduc. In these experiments, we can prove the core viewpoint of our paper:
1. DCFR/PCFR/CFR+ may defeat MCCFR/MCCFVFP in small-scale problems such as  vanilla Kuhn. However, as the game scale expands. The convergence speed of sampling based algorithms (MCCFR/MCCFVFP) will gradually exceed that of full-traversal algorithms (DCFR/PCFR/CFR+).
2. In our experiments, the convergence speed of MCCFVFP is consistently faster than that of MCCFR. This implies that although our algorithm might theoretically be less effective than MCCFR in tangled games, considering the acceleration in the implementation of our algorithm and the fact that large-scale games tend to be clear games, our algorithm has always outperformed MCCFR in our experiments.
The new experimental results can be found in Figure 1 of the provided PDF. The code used in the paper will also be updated.

### Section 5.3

We have great news. We developed a commercial Texas Hold'em GTO solver based on the MCCFVFP algorithm, and this solver is already online. This solver can handle up to 6-player, 52-card no-limit Texas Hold'em. The ability to process games has been enhanced from approximately 300k information sets in the original paper to a maximum of about 170M information sets. In the latest experiments, we used this Texas Hold'em solver framework to test the performance of MCCFVFP in multiplayer large-scale games. In the 3-player and 6-player Texas Hold'em sub-games, the performance of MCCFVFP surpassed the traditional MCCFR algorithm, leading by approximately 40%.

Our experiments were conducted on the sub-game (river) of Texas Hold'em. All players call the big blind in preflop, then check until the river, with uniform card distribution and a 25BB stack depth.

1. In a two-player Texas Hold'em game, we can directly represent the convergence speed through exploitability. The results can be referred to in Table 2 of the PDF. The public cards in the experiment are 5d 2s 9d 2c 7c. After abstracting the hands, there are 69 strength ranks. This sub-game has approximately 89k information sets, and the unit of exploitability is BB/100.

2. In multiplayer situations, the exploitability cannot be directly calculated. Therefore, we use the method of mutual battles to measure the strength of different algorithms. In the competition 1, MCCFVFP AI is randomly set as player $i$, and all other players except player $i$ are set as MCCFR AI. Define $r_1$ as the rewards of the MCCFVFP AI player at competition 1. The second setting is exactly the opposite. Player $i$ is randomly set as MCCFR AI, and the remaining players are set as MCCFVFP AI. Define $r_2$ as the rewards of the MCCFR AI player at competition 2. By comparing $r_1$ and $r_2$, we can roughly compare the convergence speeds of different algorithms. The results can be referred to in Table 3 of the PDF. 

Full details will also be included in the camera-ready version. 

[1] Brown N, Sandholm T. Solving imperfect-information games via discounted regret minimization[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2019, 33(01): 1829-1836.

[2] Farina G, Kroer C, Sandholm T. Faster game solving via predictive blackwell approachability: Connecting regret matching and mirror descent[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2021, 35(6): 5363-5371.

Meta-review: The paper introduces a new algorithm for solving extensive-form imperfect information games. The algorithm combines, in a novel way, Monte Carlo counterfactual regret minimization and fictitious play, achieving faster convergence to Nash Equilibrium in the experiments. The experimental results are justified by theoretical analysis of the algorithm. All reviewers agreed that the proposed algorithm is novel and interesting, and the results are promissing. 

That said, most reviewers expressed concerns about writing and presentation, providing recommendations and guidelines about improvements. Also, some reviewers were concerned that comprehending the paper requires a non-trivial background in the literature on game theory and state of the art algorithms in the field. 

The authors provided detailed feedback on the reviewers' concerns, and suggested constructive ways for preparing the paper for publications, and the reviewers appeared to be convinced by the authors' feedback. Based on the expressed concerns and proposed improvement and corrections, I recommend acceptance as a poster.
Decision: Accept (poster)