Efficient CFR for Imperfect Information Games with Instant Updates

Hui Li 1 Kailiang Hu 1 Yuan Qi 1 Le Song 1 2

Abstract
Counterfactual regret minimization (CFR) isa framework of iterative algorithms and isempirically the fastest approach to solving large
imperfect information games. However, for large
games, the convergence speed of the state-of-theart CFR is still the key limitation, especially inreal-time applications. We propose a novel counterfactual regret minimization method with instant
updates, which has a provably lower convergencebound and a provably tighter space complexity
bound. We apply the proposed instant updates
into many CFR variants on one Leduc Hold’em
instance and five different subgame instancesof Heads-Up No-Limit Texas Hold’em (HUNL)
generated by DeepStack. The proposed method
empirically achieves faster convergence rates than
the state-of-the-art CFR. In subgame instances of
HUNL, our method converges three times fasterthan the hybrid method used in DeepStack.

1. Introduction
In recent years, many remarkable advances have been madein addressing large perfect information games, such as
Go (Silver et al., 2016; 2017). However, solving Imperfect
Information Games (IIG) still remains a challenging problem.
In IIGs, a player has only partial knowledge about her
opponents before making a decision, so that she has to reason
under the uncertainty about her opponents’ information
while exploiting the other players’ uncertainty about herself.
Thus, IIGs provide more realistic modeling than perfect
information games for many real-world applications, suchas trading, traffic routing, and public auction. The typicaltarget of solving IIGs is to find a Nash equilibrium so thatno player can unilaterally improve her reward.
To solve IIGs, many algorithms have been designed toapproximately find Nash equilibrium. Linear programmingwith realization plan representation (Koller & Megiddo,
1992) has traditionally been used to solve perfect-recall
1

Ant Financial, China 2 Georgia Institute of Technology,
USA. Correspondence to: Hui Li <lihuiknight@google.com,
ken.lh@antfin.com>.
Real-World Sequential Decision Making workshop at the 36 thInternational Conference on Machine Learning, 2019. Copyright2019 by the author(s).

constant-sum IIGs. Such representation is linear in the number of nodes in the game tree but usually requires inverting
large matrix or other extremely expensive operation. Many
iterative techniques have been proposed as an alternative tolinear programming methods, such as gradient-based algorithm (Gilpin et al., 2007), excessive gap technique (Kroer
et al., 2015) and regret minimization method (Gordon,
2007; Zinkevich et al., 2007). The widely used approaches
for solving large IIGs are the CFR variants (Zinkevich
et al., 2007; Lanctot et al., 2009; Tammelin, 2014; Brown& Sandholm, 2018; Schmid et al., 2018; Li et al., 2018),
which minimize the overall counterfactual regret so that the
average strategies converge to Nash equilibria. Zinkevich
et al. (2007) uses CFR to solve the abstracted limit Texas
Hold’em with 1012 states, which is two orders of magnitudelarger than previous methods. To obtain a faster convergence,
Tammelin et al. (2015); Tammelin (2014) propose CFR+and ultimately solve Heads-Up Limit Texas Holdem (HUL)with CFR+ by 4800 CPUs and running for 68 days. Note
that, this game has over 1014 information sets and has beena challenging problem for artificial intelligence over 10
years (Michael Bowling, 2015). Although great breakthroughs have been made, still Heads-Up No-Limit (HUNL)
Texas Hold’em still remains an open question, which has
more than 6×10161 information sets (Johanson, 2013) and ismuch more difficult than HUL. Recently, Libratus (Brown &Sandholm, 2017) and DeepStack (Moravcik et al., 2017) aredeveloped to solve the abstracted versions of HUNL using
CFR variants and continue resolving techniques. Because
the agents have to solve the subgames online using CFR
variants, to timely return the computed strategy profile, they
have to reduce the size of subgame by abstraction technique.
To make it possible to solve larger IIGs with more-refined
abstracted actions, a more efficient method is quite importantand necessary. Brown & Sandholm (2018) propose a faster
regret minimization method — DCFR — by discounting
both positive and negative cumulative regret. This work
won the honorable mention in AAAI 2019 and can achieve
the fastest convergence rate on many subgame instances of
HUNL empirically. In the experiment, we will compare ourmethod against this method.
In this paper, we propose a more efficient counterfactual
regret minimization method with instant updates technique.
We prove that our method has a lower convergence boundInstant CFR for Imperfect Information Games

under the same proved computation memory constraint.
More importantly, many popular and state-of-the-art CFR
variants, such as original CFR (Zinkevich et al., 2007),
CFR+ (Tammelin, 2014; Michael Bowling, 2015) and
DCFR (Brown & Sandholm, 2018), can benefit from the
proposed instant updates. We test our method on Leduc
Hold’em and five different HUNL subgames generated by
DeepStack, the experiment results show that the proposed
instant updates technique makes significant improvements
against CFR, CFR+, and DCFR. In addition, we also provethat the weighted average strategy by skipping previous iterations can approach an approximate Nash equilibrium. In thesubgame instance of HUNL, the improved method converges
three times faster than the hybrid method used in DeepStack.

2. Background and Notation
2.1. Notations in Extensive-Form GameWe define the components of an extensive-form IIG following (Osborne & Rubinstein, 1994; Li et al., 2018). N ={0,1,...,n − 1} is a finite set and each member refers to aplayer. We use hvi refer to the hidden variable of player iin imperfect information game, which is unobserved by the
opponents. Each member h of H denotes a possible history(or state). For player i, hv−i refers to the opponent’s hidden
variables. If hj is a prefix of h, we can denote them by hj v h.
Z denotes the set of terminal histories and any member z ∈ Z
is not a prefix of any other sequences. A player function P
assigns a member of N ∪ {c} to each non-terminal history,
where c denotes the chance player. In practice, we usually
define c = −1. P (h) is the player who takes actions after
history h. A(h) = {a : ha ∈ H} is the set of available actions after non-terminal history h ∈ H \ Z. Ii of a history{h ∈ H : P (h) = i} is an information partition of player
i. A set Ii ∈ Ii is an information set of player i and Ii (h)refers to information set Ii at state h. For Ii ∈ Ii , we haveA(Ii ) = A(h) and P (Ii ) = P (h). For each player i ∈ N , theutility function ui (z) defines the payoff of the terminal state z.
If all players in one game can recall their previous actions andthe corresponding infosets, we call it a perfect-recall game.
2.2. Definition of Strategy and Nash equilibrium
For play i ∈ N , the strategy σi (Ii ) in an extensive-form
game assigns an action distribution over A(Ii ) to information
set Ii . A strategy profile σ = {σi |σi ∈ Σi , i ∈ N } is acollection of strategies for all players, where Σi is the setof all possible strategy profiles for player i. σ−i refers to all
strategies in σ expect σi . σi (Ii ) is the strategy of information
set Ii . σi (a|h) denotes the probability of action a takenby player i ∈ N ∪ {c} at state h. In imperfect information
game, ∀h1 ∈ Ii and ∀h2 ∈ Ii , we have Ii = Ii (h1 ) = Ii (h2 ),σi (Ii ) = σi (h1 ) = σi (h2 ), σi (a|Ii ) = σi (a|h1 ) = σi (a|h2 ).
For iterative learning method such as CFR, σ t refers to thestrategy profile at t-th iteration. The state reach probabilityof history h is denoted by π σ (h) if players take actions

according to σ. For an empty sequence, π σ (a0 ) = π σ (∅) = 1.
The reach
Q probability can beσ decomposedσ intoπ σ (h) = i∈N ∪{c} πiσ (h) = πiσ (h)π−i(h), where πi is theσproduct of player i0 s contribution and π−i
is the product of all
players’ contribution except player i. The information
setP
reach probability of Ii is defined by π σ (Ii ) = h∈Ii π σ (h).
For player i, the expected game utility of a strategy profile
σ is thePexpected payoff of all possible terminal nodes, i.e.,uσi = z∈Z π σ (z)ui (z). Given a fixed strategy profile σ−i ,(σ 0 ,σ)any strategy σi∗ = argmaxσi0 ∈Σi ui i −i of player i thatσachieves optimal payoff against π−i
is a best response.
An -Nash equilibrium is an approximation of a Nashequilibrium, whose strategy profile σ ∗ satisfies: ∀i ∈ N ,(σ ∗ ,σ−i )

ui i

0

(σ ,σ−i )+  ≥ maxσ0 ∈Σi ui ii

. Exploitability of a(σi ,σ ∗ )∗−istrategy σi is defined by i (σi ) = uσi − ui
. If theplayers alternate their positions in two-player zero-sum IIG,∗∗
the value of a pair of games is zeros, i.e., uσ0 + uσ1 = 0.
Therefore, we can define the exploitability of a strategy

profile σ by (σ) =∗)(σ ,σ1(σ ∗ ,σ )+u0 0 1

u1 0

2

.

3. Method and Theory
In this section, we will present a novel regret minimization
method with an efficient instant updates technique. Thenwe give the theoretical bound for this novel method. After
that, we present another regret minimization method withskipping mechanism and prove its bound. At last, we talkabout several hybrid methods of current CFR variants andthe proposed instant updates.
3.1. Instant Counterfactual Regret Minimization
CFR variants (Zinkevich et al., 2007; Lanctot et al., 2009;
Brown & Sandholm, 2017; Moravcik et al., 2017) update
counterfactual value recursively along the game tree and minimize the overall regret. Our method also minimizes the overall regret. Different from original CFR variants, we define
a novel instant counterfactual value recursively as follows.
t

Given the children’s instant counterfactual value sσi (a|Ii )of information set Ii , its dummy counterfactual value isdefined bytŝσi (Ii ) =tXσit (a|Ii )sσi (a|Ii ).

(1)a∈A(Ii )Specifically, the leaf nodes’ instant counterfactual values
are the same as their utility values. Then the instant regretof taking action a at information set Ii will betttq̂iσ (a|Ii ) = sσi (a|Ii )−ŝσi (Ii ).

(2)

The cumulative instant regret is the rectified summation of
total instant regret, which is defined byt

Qti (a|Ii ) = max(Qt−1(a|Ii )+ q̂iσ (a|Ii ),0)i

(3)Instant CFR for Imperfect Information Games

Then we update the behavior strategy σit+1 (a|Ii ) byP
 P Qti (a|Iit)
if a∈A(Ii ) Qti (a|Ii ) > 0
(a|I
)
Q
T +1
i
a∈A(Ii ) iσi (a|Ii ) = 1otherwise.
|A(Ii )|

(4)t
After that, instant counterfactual value sσi (Ii ) of information
set Ii is defined byXttsσi (Ii ) =σit+1 (a|Ii )sσi (a|Ii ).
(5)

We can prove Lemma 1 in the same way as Lemma 14 in
Burch (2017). Although these two Lemmas have different
definitions of counterfactual value, they hold similar0
property. The proved Lemma 1 holds for any σ−i∈ Σ−i andis more general than the previous proof.
Proof
X

0
(σ t ,σ−i)

Qt−1(a|Ii )q̂i i
i(a|Ii )a∈A(Ii )a∈A(Ii ) t 0
(σ ,σ )(σ t ,σ 0 )Qt−1(a|Ii ) si i −i (a|Ii )−ŝi i −i (Ii )iX=a∈A(Ii )Now, we finish the recursive definition of instant counterfactual value and cumulative instant regret. Note that, thedefinition of counterfactual value in our method is different
from the previous CFR variants (Zinkevich et al., 2007;
Tammelin, 2014; Moravcik et al., 2017; Brown & Sandholm,2018). In our method, after obtaining the children’s instantcounterfactual value of Ii , we use its behavior strategy tocompute its dummy counterfactual value and update its
cumulative instant regret. After that, we update its behavior
strategy instantly by regret matching+ (Tammelin, 2014).
Finally, we use the updated behavior strategy to update its
instant counterfactual value. In previous CFR variants, thecounterfactual value is only updated by the old behavior
strategy rather than the latest behavior strategy.

 t 0X (σt ,σ0 )(σi ,σ−i )
t
i −i
Qt−1
(a|I
)
s
(a|I
)−
s
(b|I
)σ
(b|I
)
i
i
i
i
i
i
i
i

X

=

a∈A(Ii )b∈A(Ii )(σ t ,σ 0 )=Qt−1(a|Ii )si i −i (a|Ii )ia∈A(Ii )

X

X

−

Qt−1
(a|Ii )ia∈A(Ii )0(σ t ,σ−i
)

X

si i

Qt−1
(b|Ii )
it−1
(c|Ii )Q
c∈A(Ii ) i(b|Ii ) Pb∈A(Ii )(σ t ,σ 0 )=Qt−1(a|Ii )si i −i (a|Ii )ia∈A(Ii )

X

P
t−1
0
(a|Ii )
(σit ,σ−i)a∈A(Ii ) Qi
t−1−
si(b|Ii )Q (b|Ii ) P
t−1(c|Ii )c∈A(Ii ) Qib∈A(Ii )
X

=0
(7)

T

The average strategy σ̄i from iteration 1 to T is defined byσ̄i T (a|Ii ) =σttt=1 πi (Ii )σi (a|Ii ),PT σ tt=1 πi (Ii )

PT

(6)

Lemma 2 Define L = maxIi ,a,t |q̂ t (a|Ip i )|.∀Ii ∈ I, a ∈A(Ii ),t ∈ [1,T ], we have QT (a|Ii ) ≤ L |A|T .
Proof According to Lemma 1, we can prove!2twhere πiσ (Ii ) denotes the information set reach probabilityof Ii at t-th iteration and is used to weight the corresponding
current strategy σit (a|Ii ).
Because the counterfactual value is updated instantly by
the latest behavior strategy, we name our method as InstantCounterfactual Regret minimization (ICFR).
3.2. Theoretical Analysis of ICFRIn this section, we will prove the convergence for the
proposed ICFR method as presented in Theorem 3. It canguarantee ICFR converge to a Nash equilibrium with a lower
bound of the CFR.
Theorem 1 (Theorem 2 in Zinkevich et al. (2007), Theorem
1 in Brown & Sandholm (2016)) In a two-player zero-sum
perfect-recall IIG at iteration T , ∀i ∈ N , if the bound of
average overall regret is i , then σ̄ T is a 0 + 1 -Nashequilibrium.
Before we prove the bound, we should prove Lemma 1 andLemma 2.
0
Lemma 1 ∀σ−i
∈ Σ−i , ∀Ii ∈ Ii , and ∀a ∈ A(Ii ),0P(σit ,σ−i
)
t−1
Q
(a|I
)q̂
(a|Ii ) = 0iiia∈A(Ii )X

QTi (a|Ii )2 ≤a∈A(Ii )X

QTi −1 (a|Ii )+ q̂ T (a|Ii )a∈A(Ii )!
≤X

QTi −1 (a|Ii )2 + q̂ t (a|Ii )2X+2a∈A(Ii )QiT −1 (a|Ii )q̂ T (a|Ii )a∈A(Ii )X

X≤
QTi −1 (a|Ii )2 +q̂ T (a|Ii )2a∈A(Ii )a∈A(Ii )≤TXXq̂ t (a|Ii )2 ≤t=1 a∈A(Ii )T
X
X

L2 ≤ T |A|L2

t=1 a∈A(Ii )(8)pTherefore, we have QT (a|Ii ) ≤ L |A|T .

After that, we can prove the average overall regret of ICFR
by Theorem 2.
 tt
Theorem 2 Define K = minIi ∈Ii sσi (Ii ) − ŝσi (Ii ) .
Define average overall regret of player i at iteration T by
!
T
X
t
t
1
(σi∗ ,σ−i)(σit ,σ−i)T(9)Qi = maxu−ui,
T σi∗ ∈Σi t=1 ip√then QTi ≤ |Ii |(L |A|/ T −K).

Instant CFR for Imperfect Information Games

Proof

According to Lemma 2, we havexDefine ∆I (Ii ) as the incrementally reachable information
sets after player i taking x−th action from information set Ii .
Note that, ∆I x (Ii ) doesn’t contain the additionally visited
information sets after player i taking x−1 actions from Ii .
If these information sets are reached after taking action a ∈A(Ii ), the set of incrementally reachable information sets isdefined by ∆I x (a|Ii ). Define I x (Ii ) = I x−1 (Ii )+∆I x (Ii ),where x is the depth of the subgame tree with root Ii andD(Ii ) is the maximum depth. |I 0 (Ii )| = 1. Define σ(Ii → σ 0 )as a strategy profile identical to σ except that player i always
select action by σ 0 at Ii . Specifically, σ(Ii → a) refers to that
player i always selects action a at Ii . According to the definiPσ(I →a)tion, we have si i
(Ii ) = I 0 ∈∆I 1 (a|Ii ) sσi (Ii0 ). DefinePT  iσt (I →σ0 )t
QTi (Ii ) = T1 maxσ0 ∈Σi t=1 si i
(Ii ) − sσi (Ii ) ,then we have

QTi ≤Theorem 3 In a two-player zero-sumpperfect-recall
game at√iteration T , ICFR approaches a |I|(L |A|/ T −K)-Nashequilibrium.
Proof According to Theorem 1, in a two-player zero-sum
game at iteration T , if ∀i ∈ N , the bound of averageoverall regret is i , then σ̄ T is a 0 +p1 equilibrium.
√
According to Lemma 2, QTi (Ii ) ≤ |Ii |(L |A|/ T − K),
and |I|I1 | = |I|, therefore ICFR approaches ap0 | + √|I|(L |A|/ T −K)-Nash equilibrium.

QTi (Ii )

T
X
1

= max
max
T σ0 ∈Σi a∈A(Ii ) t=1 0

3.3. Space Complexity
In this section, we give the space complexity of the proposed
ICFR in Theorem 4. Note that ICFR has the same spacecomplexity as original CFR and CFR+.

σ t (Ii →σ 0 )

X

si

t

(Ii0 )−sσi (Ii )

Ii ∈∆I 1 (a|Ii )TXt1
σ t (Ii →a)maxmax(Ii )−sσi (Ii )s0T σ ∈Σi a∈A(Ii ) t=1 i
!
 t

X
σ (Ii →σ 0 ) 0σt0(Ii )−si (Ii )+si=Theorem 4 Define Ii v Z if h ∈ Ii , h v z. When performing CFR (Zinkevich et al., 2007) with simultaneous
updatesand the proposed instant P
updates, it requiresP
2 i∈N,Ii ∈Ii |A(Ii )| + 2 maxi∈N Ii vZ |A(Ii )| space.
Similarly,
when using alternatingP
P updates, it requires
2 i∈N,Ii ∈Ii |A(Ii )|+maxi∈N Ii vZ |A(Ii )| space.

Ii0 ∈∆I 1 (a|Ii )!
TX
1
σ t (Ii →a)σt(Ii )−si (Ii )s=max
T a∈A(Ii ) t=1 i
T
1
1X
+ max
max
T σ0 ∈Σi a∈A(Ii ) T t=1

Xt
σ t (I →σ 0 ) 0(Ii )−sσi (Ii0 )si i!
(Burch, 2017) proved thePspace complexity for CFRand
PCFR+, who require 3 i∈N,Ii ∈Ii |A(Ii )| space and2( i∈N,Ii ∈Ii |A(Ii )|+maxi∈N |Ii |) space respectively according to the Theorem 5 and Theorem 10 in Burch (2017).
The presented bound is tighter than those in Burch (2017).

Ii0 ∈∆I 1 (a|Ii )(10)t

According to Theorem 2 in (Burch et al., 2018), we have sσi (Ii ) ≥tttŝσi (Ii ). Define ∆S(Ii ) = sσi (Ii )−ŝσi (Ii ). Then we have

4. Hybrid CFR Variants
4.1. Skipping Mechanism

QTi (Ii )When performing CFR, we initialize the cumulative regretby zero, therefore the behavior strategy starts from a uniform
random strategy. The average of behavior strategy profiles
within all iterations will converge to a Nash equilibrium. The
weighted average of iterative behavior strategy in previous
iterations is highly exploitable. It is quite natural to ask
a question that whether the average strategy by skipping
the previous iteration can approach an approximate Nashequilibrium and obtain a better performance.

!
TX
1
σ t (Ii →a)σt(Ii )−ŝi (Ii )−∆S(Ii )maxs≤
T a∈A(Ii ) t=1 iX+ max
QTi (Ii0 )a∈A(Ii )Ii0 ∈∆I 1 (a|Ii )

(11)
!

T
X

t
1
σ t (Ii →a)maxs(Ii )−ŝσi (Ii )−∆S(Ii )T a∈A(Ii ) t=1 i
X+
QTi (Ii0 )≤Ii0 ∈∆I 1 (Ii )Although the similar technique is used in DeepStack (Moravcik et al., 2017), they don’t prove its theoretical convergence.
In this section, we prove the theoretical bound of thisskipping mechanism.

It is clear that equation 11 provides a recursive definition between
QTi (Ii ) and its children’s QTi (Ii0 ). We can derive that1
QTi (Ii ) ≤
T

p
p
√
1
|Ii |(L |A|T −T K) ≤ |Ii |(L |A|/ T −K) (13)
T

X

max

T
X

a∈A(Ii )D(Ii )
t=1
Ii0 ∈Ii(Ii )t
σ t (I →a)si i(Ii )−ŝσi (Ii )−K!

Theorem 5 Suppose we weight average strategy by skipping
the first Ts iterations.Define E = TTs , where
0 ≤ Ts ≤ T.

t

(12)

t

Define K = minIi ∈Ii sσi (Ii ) − ŝσi (Ii ) . In a two-player

Instant CFR for Imperfect Information Gameszero-sum IIG at iteration√ √T , ICFR with skipping mechanism
approaches a|I|(L|A|/ T −K)+2LE-Nash equilibrium.
1−E

Proof Define
!
T
X
∗
t
t
t
1
(σ
,σ
(σ
)
,σ
)
i
−i
i
−i
σ ∗ = argmaxui−ui,
T σi∗ ∈Σi

(14)

t=Ts

T
X

1
Q1:T
=
i

T t=1

(σ ∗ ,σ t )(σ t ,σ t )ui i −i −ui i −i

!
(15)

,

1:T
Accordingto≤p√ the Theorem 2, we have Qi|Ii |(L |A|/ T −K). According to the definition, we have

Q1:T
≥ −LE +
i

1
T

T
X

t
(σ ∗∗ ,σ−i
)

ui i

t
(σ t ,σ−i
)

!

−ui i

where
T
X

(σ ∗∗ ,σ t )(σ t ,σ t )ui i −i −ui i −i!
(17)t=Ts +1√ √|Ii |(L |A|/ T −K)+LE
Therefore, we have QTi s :T ≤.
1−E
According to Theorem
1,
ICFR
with
skippingmechanism√ √approaches a|I|(LIn the experiment, we will give a detailed comparison forthese different methods.

5. Experiment

t=Ts +1(16)

σi∗∗ = argmax
σi∗∗ ∈Σi

Discounted CFR (DCFR) (Brown & Sandholm, 2018) isa general version of CFR and CFR+ by discounting both
cumulative regret and average strategy. In DCFR(α,β,γ), theaccumulated positive regrets are discounted by tα /(tα +1),
the accumulated negative regrets are discounted bytβ /(tβ + 1), and contributions to the average strategy
are discounted by (t/(t + 1))γ in t-th iteration. α, β, γ
are the parameters in DCFR. DCFR can obtain a better
convergent strategy than both CFR and CFR+ in many games
empirically after specifying suitable parameters although
the proved bound is larger than CFR. When we apply the
proposed instant updates into DCFR, we obtain IDCFR
algorithm. Similarly, if we use regret matching+ techniqueto compute behavior strategy, we obtain IDCFR+ algorithm.

|A|/ T −K)+2LE-Nash equilibrium.
1−E

According to the Theorem 5, if E → 0, that is, Ts = 0, thenthe bound is same with Theorem 3. Empirically, the methodwith skipping mechanism approaches to an approximatedNash equilibrium more efficiently.
4.2. ICFR Variants
There are many popular CFR variants, such as CFR (Zinkevich et al., 2007), CFR+ (Tammelin, 2014) and
DCFR (Brown & Sandholm, 2018).
CFR+ (Tammelin, 2014) is similar to CFR but has threedifferences. First, CFR+ uses regret-matching+ in place ofregret matching and is more efficient than CFR empirically.
Second, CFR+ uses alternating updates for only one player’s
cumulative strategy and another one’s cumulative regret
in each iteration, while CFR uses simultaneously updates
for both players’ cumulative strategy and regret. Third,
CFR+ weights each current strategy by t rather than uniform
distribution. Similarly, we use regret matching+ (Tammelin,2014) rather than regret matching (Zinkevich et al., 2007),
because regret matching+ has a better performance empirically. If we use regret matching+ in instant counterfactual
regret minimization, we can name it by ICFR+.

We evaluated the proposed method on several different
game instances: a widely-used Leduc Hold’em and fivesubgames of Heads-Up No-limit Texas Hold’em generated
by DeepStack. The experiments cover all kinds of subgames
presented in DeepStack (Moravcik et al., 2017). To reduce
the randomness, we repeated each experiment for 30
times with random board and reach probability. All theexperiments are evaluated by exploitability. Note that, alower exploitability indicates better performance.
5.1. Data Sets and Game Rules
Leduc Hold’em is a two-player imperfect information gameof poker and is first introduced by Southey et al. (2012). The
game contains a deck of 6 cards comprising two suits ofthree ranks. The player may raise any amount of chips up
to a maximum of that player’s remaining stack. There isalso no limit to the number of raises or bets in each betting
round. The game has at most two rounds. In the first betting
round, each player is dealt one card from a deck of 6 cards.
In the second betting round, a community (or public) cardis revealed from a deck of the remaining 4 cards.
Heads-up no-limit Texas hold’em (HUNL) has at most four
betting rounds if neither of two players fold in advance. The
four betting rounds are named by preflop, flop, turn, andriver respectively. The version of HUNL we used in thispaper is based on the standard of Annual Computer Poker
Competition (ACPC). This version is widely used as a large
data set of imperfect information game (Moravcik et al.,2017; Brown & Sandholm, 2017). Initially, both two players
have 20000 chips. At the start of each hand, both players aredealt two private cards from a 52-card deck. After the preflop
round, three public cards are revealed face-up on the table
and the flop betting round occurs. After this round, anotherpublic card is dealt and the third betting round (called turnround) takes place. After that, the last public card is revealed,then the river round begins.

Instant CFR for Imperfect Information Games

CFR
ICFR
CFR+
ICFR+
DCFR
IDCFR+

10 2
10 3
100

103

103

102

102

CFR
ICFR
CFR+
ICFR+
DCFR
IDCFR+

101
100

101

Iteration

102(a) Leduc Hold’em

103

Exploitability

10 1

Exploitability

Exploitability

100

100

CFR
ICFR
CFR+
ICFR+
DCFR
IDCFR+

101
100

101

Iteration(b) River(5k)

102

103

100

101

Iteration

102

103

(c) River(500)

Figure 1: Convergence on (a) Leduc Hold’em (b) River(5k), and (c) River(500). It’s clear that with the help of instant updates,
all these methods converge faster than their original version. On Leduc Hold’em, CFR+ has a better performance than DCFR.
Both the proposed ICFR+ and IDCFR+ perform better than the state-of-the-art methods. On River(5k) and River(500),
IDCFR+ has a better improvement than state-of-the-art methods.
In this paper, we evaluate our methods on five subgamesof HUNL produced by the DeepStack poker AI. We cover
all the subgames presented in DeepStack paper (Moravcik
et al., 2017). Specifically, Preflop(5k),Flop(5k), Turn(5k),River(5k) and River(500) are subgames of HUNL generated
by DeepStack. The starting pot sizes for the first four
subgames are 5k and the last one is 500. Note that, as thepaper of DeepStack said, the terminal values of Preflop(5k)and Flop(5k) are predicted by the counterfactual value
networks. The actions used to build subgames are listed
in Table S3 (Moravcik et al., 2017). The exploitability iscomputed on each subgame. Both subgames begin at thestart of the river betting round and continue to the end of thegame. The start pot size of the first subgame is 500 chips andthe second subgame is 5000 chips.
In this paper, we use exploitability to evaluate the performance of different methods. It’s clear that the method who
can obtain a lower exploitability within a specified iteration
will be better.
5.2. Comparison Results
When performing CFR, there are two different update
methods: simultaneous method and alternating method. Empirically, the alternating method converges more efficiently
than simultaneous method (Tammelin, 2014; Brown & Sandholm, 2018). In this paper, we use the alternating-updates
technique on all experiments. We compared the proposed
methods with the original CFR (Zinkevich et al., 2007) andthe state-of-the-art methods, including CFR+ (Tammelin,2014), DCFR (Brown & Sandholm, 2018) and hybrid
CFR+ (Moravcik et al., 2017). Note that, these methods
often have different performance on different game instances.
Because DCFR had three different parameters, we selected
these parameters by sweeping technique. Specifically,α ∈ [0.5,1.0,1.5,2.0,2.5], β ∈ [−∞,0,0.5,1.0,1.5,2.0,2.5],and γ ∈ [1, 2, 3, 4]. In addition, we also applied regret
matching and regret matching+ (Tammelin, 2014) into

DCFR respectively. These two versions were denoted by
DCFR and DCFR+ respectively.
On Leduc Hold’em poker instance, Figure 1 (a) showsthat CFR+ outperformed DCFR and became the strongest
benchmark. With the help of the proposed instant updates,
both CFR+ and IDCFR+ obtained significant improvement
and converged more efficiently than the counterpart. On
the subgame instances of HUNL, Figure 1 (b) and (c) showsthat DCFR outperformed CFR+ and became the strongest
benchmark. The proposed instant updates technique also
provided a significant improvement against DCFR. When
combining the proposed instant updates with the proved
skipping mechanism, all of these methods converge more
efficiently. Figure 2 shows that the improved IDCFR byskipping half previous iterations converges three times fasterthan the hybrid method used in DeepStack. In Figure 2 (b),the exploitability of IDCFR+Half between 500 and 580
iterations was larger than IDCFR+ and after 580 iterations its
exploitability became lower than IDCFR+. It was reasonablebecause only the average strategy over a large number of
iterations can approach an approximate Nash equilibrium
according to the proved Theorem 5.
In practice, an exploitability of 1 mbb/g 1 is consideredsufficiently converged (Michael Bowling, 2015). Thus,
the performance of the presented algorithms between 100
and 1000 iterations is arguably more important than theperformance beyond 10000 iterations (Moravcik et al., 2017;
Brown & Sandholm, 2018). To demonstrate the performanceof the proposed instant updates after long iterations, we list
the performance in Table 1 for CFR and DCFR after 10k
iterations. Because the performance of CFR+ and DCFR+
are much better than CFR and hybrid CFR+ empirically, weonly present the performance of long iterations for CFR+
and DCFR. It’s clear that instant updates technique helps
both CFR+ and DCFR perform better than the counterpart.
1

mbb/g refers to millibig blinds per game.

Instant CFR for Imperfect Information Games

101

Exploitability

Exploitability

0
10
1.0

CFR+
CFR+ half
ICFR+
ICFR+ half
IDCFR+IDCFR+ half
DeepStack CFR+

102

100
10 1
× 10 25 ×5500
102

100.11× 10 2
6 ×660010
2

× 10 2× 10 2× 10 2
7 ×7700
10 8 ×8800
10 9 ×9900
10
Iteration
2

2

2

1000

(a) Skipping half iterations.

IDCFR+IDCFR+ (skip 100)
IDCFR+ (skip 200)
IDCFR+ (skip 300)
IDCFR+ (skip 400)
IDCFR+ (skip 500)
IDCFR+ (skip 600)
IDCFR+ (skip 700)
IDCFR+ (skip 800)
IDCFR+ (skip 900)

4 × 102

5 × 102400

500

6 × 102600

Iteration

7 × 102700

8 × 102800

9 × 102

900

10

3
1000

(b) Skipping different iterations.

Figure 2: (a) Convergence on River(5k) for different methods by skipping half iterations. All of these methods obtain better
performance with the proved skipping mechanism. (b) Convergence on River(5k) for IDCFR+ by skipping different iterations.
Empirically, skipping the previous 500 or 600 iterations can obtain the best performance.
Table 1: Long-running performance after 10k iterations
Game
Leduc
Preflop(5k)Flop(5k)
Turn(5k)
River(5k)River(500)#infoset
1.1e4
1.6e4
2.4e4
1.7e6
2.4e6
1.6e5

#state
6.1e4
2.1e7
3.2e7
2.2e9
3.2e7
2.1e7

CFR+
2.9e−5±1.8e−7
4.5e−4±4.7e−8
8.2e−3±1.2e−5
1.9e−2±3.6e−4
1.0e−2±1.8e−5
3.4e−3±3.3e−5

ICFR+
2.3e−5±1.7e−7
3.3e−4±9.6e−9
2.5e−3±5.6e−6
1.8e−2±9.5e−5
3.9e−3±6.0e−5
2.2e−3±2.1e−5

6. Conclusion
We have proved that counterfactual regret minimization
with the proposed instant updates has a lower convergencebound. This instant updates can significantly improve thestate-of-the-art method. We also have proved that weighted
average strategy by skipping previous iterations approaches
an approximate Nash equilibrium and helps our methods
obtain a faster convergence empirically. Finally, we provedthat the proposed methods have the same space complexity
with CFR and the proved bound is much tighter than the
proof in the previous work.

DCFR
3.5e−5±4.0e−7
3.0e−5±1.5e−9
1.7e−3±3.6e−6
7.7e−3±7.6e−5
2.2e−3±3.7e−5
1.3e−3±2.5e−5

IDCFR+
3.1e−5±1.6e−7
9.1e−6±9.7e−9
7.3e−4±3.8e−6
7.2e−3±5.5e−5
1.6e−3±2.0e−5
1.1e−3±3.5e−5

Burch, N., Moravcik, M., and Schmid, M. Revisiting CFR+ and Alternating Updates. arXiv preprint
arXiv:1810.11542, 2018.
Gilpin, A., Hoda, S., Pena, J., and Sandholm, T. Gradientbased algorithms for finding Nash equilibria in extensive
form games. In International Workshop on Web andInternet Economics, pp. 57–69. Springer, 2007.
Gordon, G. J. No-regret algorithms for online convex
programs. In Advances in Neural Information Processing
Systems, pp. 489–496, 2007.

References

Johanson, M. Measuring the size of large no-limit poker
games. arXiv preprint arXiv:1302.7008, 2013.

Brown, N. and Sandholm, T. Strategy-Based Warm Startingfor Regret Minimization in Games. pp. 432–438. AAAI,
2016.

Koller, D. and Megiddo, N. The complexity of two-person
zero-sum games in extensive form. Games and economic
behavior, 4(4):528–552, 1992.

Brown, N. and Sandholm, T. Superhuman AI for heads-up
no-limit poker: Libratus beats top professionals. Science,
pp. eaao1733, 2017.
Brown, N. and Sandholm, T. Solving Imperfect-Information
Games via Discounted Regret Minimization. arXiv
preprint arXiv:1809.04040, 2018.
Burch, N. Time and Space: Why Imperfect Information
Games are Hard. PhD thesis, 2017.

Kroer, C., Waugh, K., Kilinç-Karzan, F., and Sandholm, T.
Faster first-order methods for extensive-form game solving. In Proceedings of the Sixteenth ACM Conference on
Economics and Computation, pp. 817–834. ACM, 2015.
Lanctot, M., Kevin, W., Martin, Z., and Bowling, M. Monte
Carlo sampling for regret minimization in extensive
games. In Advances in neural information processing
systems, 2009.

Instant CFR for Imperfect Information Games

Li, H., Hu, K., Ge, Z., Jiang, T., Qi, Y., and Song, L. Double
Neural Counterfactual Regret Minimization. arXiv
preprint arXiv:1812.10607, 2018.
Michael Bowling, Neil Burch, M. J. O. T. Heads-Up Limit
Texas Holdem is solved. Science, pp. 347(6218):145–149,
2015.
Moravcik, M., Martin, S., Neil, B., Viliam, L., Morrill, D.,
Bard, N., Davis, T., Waugh, K., Johanson, M., and Bowling, M. Deepstack: Expert-level artificial intelligence inheads-up no-limit poker. Science, (6337):508–513, 2017.
Osborne, M. J. and Rubinstein, A. A course in game theory,
volume 1. MIT Press, 1994.
Schmid, M., Burch, N., Lanctot, M., Moravcik, M., Kadlec,
R., and Bowling, M. Variance Reduction in Monte Carlo
Counterfactual Regret Minimization (VR-MCCFR) for
Extensive Form Games using Baselines. arXiv preprint
arXiv:1809.03057, 2018.
Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L.,
Driessche, G. V. D., and et al., J. S. Mastering the gameof Go with deep neural networks and tree search. Nature,(7587), 2016.
Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou,
I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M.,
Bolton, A., et al. Mastering the game of go without humanknowledge. Nature, 550(7676):354, 2017.
Southey, F., Bowling, M. P., Larson, B., Piccione, C., Burch,N., Billings, D., and Rayner, C. Bayes’ bluff: Opponent
modelling in poker. arXiv preprint arXiv:1207.1411,
2012.
Tammelin, O. Solving large imperfect information games
using CFR+. arXiv preprint, 2014.
Tammelin, O., Burch, N., Johanson, M., and Bowling, M.
Solving heads-up limit Texas Hold’em. In Twenty-FourthInternational Joint Conference on Artificial Intelligence,
2015.
Zinkevich, M., Michael, J., Michael, B., and Piccione, C. Regret minimization in games with incomplete information.
Advances in neural information processing systems, 2007.