players improves. Even against the top 20% tier of players in this experiment, Cepheus’ winrate of 87mbb/g
is higher than against any of our historical agents. It
even exceeds 50mbb/g, a commonly cited benchmark
for what a professional poker player seeks to win from a
In this paper, we announced that heads-up limit Texas
hold’em poker is essentially weakly solved. This is the first
nontrivial imperfect information game played competitively by humans to be solved. Even still, the reader may
ask what is the ultimate significance of solving poker? The
breakthroughs behind this result are general algorithmic
advances that make game-theoretic reasoning in large-scale
models of any sort more tractable. And, while seemingly
playful, game theory has always been envisioned to have
serious implications, for example, its early impact on cold
31 More recently, there has been a surge in game-theoretic applications involving security, including systems
being deployed for airport checkpoints, air marshall scheduling, and coast guard patrolling.
43 CFR algorithms, based
on those described in this paper, have been used for robust
decision-making in settings where there is no apparent
adversary, with potential application to medical decision
15 With real life decision-making settings almost
always involving uncertainty and missing information, algorithmic advances, such as those needed to solve poker, are
needed to drive future applications. However, we also echo
a response attributed to Alan Turing in defense of his own
work in games, “It would be disingenuous of us to disguise
the fact that the principal motive which prompted the work
was the sheer fun of the thing.”
The author order is alphabetical reflecting equal contribution by the authors. The idea of CFR+ and compressing the
regrets and strategy originated with Oskari Tammelin.
This research was supported by Natural Sciences and
Engineering Research Council (NSERC), Alberta Innovates
Technology Futures (AITF) through the Alberta Innovates
1. Poker: A big deal. The Economist,
Economist Newspaper Ltd., London,
December 22, 31–38, 2007.
2. Allis, V. L. A Knowledge-Based
Approach to Connect-Four. The Game
is Solved: White Wins. Master’s thesis,
Vrije Universiteit, Amsterdam, The
3. Allis, V.L. Searching for Solutions in
Games and Artificial Intelligence. PhD
thesis, Vrije Universiteit Amsterdam,
The Netherlands, 1994.
4. Babbage, C. Passages from the Life
of a Philosopher. Longman, Green,
Longman, Roberts, and Green,
London, 1864. Chapter 34.
5. Billings, D., Burch, N., Davidson, A.,
Holte, R.C., Schaeffer, J., Schauenberg, T.,
Szafron, D. Approximating game-theoretic optimal strategies for full-scale poker. IJCAI, (2003), 661–668.
6. Billings, D., Davidson, A., Schaeffer, J.,
Szafron, D. The challenge of poker.
Artificial Intelligence 134, 1–2 (2002),
7. Borel, E., Ville, J. Applications de la
théorie des probabilités aux jeux de
hasard. Gauthier-Villars, 1938.
8. Bowling, M., Burch, N., Johanson, M.,
Tammelin, O. The cepheus website,
9. Bowling, M., Burch, N., Johanson, M.,
Tammelin, O. Heads-up limit hold’em
poker is solved. Science 347, 6218
(Jan. 2015), 145–149.
10. Bowling, M., Burch, N., Johanson, M.,
Tammelin, O. Heads-up limit hold’em
poker is solved: Supplementary online
material, January 2015.
11. Bowling, M., Johanson, M., Burch, N.,
Szafron, D. Strategy evaluation in
extensive games with importance
sampling. ICML, (2008), 72–79.
12. Bronowski, J. Ascent of man.
Documentary, 1973. Episode 13.
13. Buro, M. Solving the oshi-zumo game.
Adv. in Comp. Games 135, (2004)
14. Campbell, M., Hoane, A.J. Jr., Hsu, F.
Deep blue. Artificial Intelligence 134,
(Jan. 2002), 57–83.
15. Chen, k., Bowling, M. Tractable
objectives for robust policy
optimization. Adv. Neural Inf. Process.
Syst. (NIPS) 25, (2012), 2078–2086.
16. Craig, M. The Professor, the Banker,
and the Suicide King: Inside the
Richest Poker Game of All Time.
Grand Central Publishing, New York,
17. Ferrucci, D. Introduction to “this is
watson.” IBM J. Res. Dev 56, 3. 4 (May
2012) 1:1–1: 15.
18. Gilpin, A., Hoda, S., Peña, J., Sandholm, T.
Gradient-based algorithms for finding
nash equilibria in extensive form
games. WINE, (2007), 57–69.
19. Gilpin, A., Sandholm, T. Lossless
abstraction of imperfect information
games. J. ACM 54, 5 (2007).
20. Jackson, E. Slumbot: An
implementation of counterfactual
regret minimization on commodity
hardware. In Proceedings of the 2012
Computer Poker Symposium. (2012).
21. Johanson, M., Bard, N. Burch, N.,
Bowling, M. Finding optimal abstract
strategies in extensive form games.
AAAI, (2012), 1371–1379.
22. Johanson, M., Bard, N., Lanctot, M.,
Gibson, R., Bowling, M. Efficient Nash
equilibrium approximation through
Monte Carlo counterfactual regret
minimization. AAMAS (2012).
23. Johanson, M., Waugh, K., Bowling, M.,
Zinkevich, M. Accelerating best
response calculation in large extensive
games. IJCAI (2011), 258–265.
24. Johanson, M.B. Robust Strategies
and Counter-Strategies: From
Superhuman to Optimal Play.
PhD thesis, University of Alberta,
Edmonton, Alberta, Canada, 2016.
25. Karmarkar, N. A new polynomial-time algorithm for linear
programming. In Proceedings of the
Sixteenth Annual ACM Symposium
on Theory of Computing (1984),
ACM, New York, NY, 302–311.
26. Koller, D., Megiddo, N. The complexity
of two-person zero-sum games in
extensive form. Games Econ. Behav 4,
4 (1992), 528–552.
27. Koller, D., Megiddo, N., von Stengel, B.
Efficient computation of equilibria for
extensive two-person games. Games
Econ. Behav 14, 2 (1996).
28. Koller, D., Pfeffer, A. Representations
and solutions for game-theoretic
problems. Artificial Intelligence 94,
29. Kuhn, H. Simplified two-person
poker. In Contributions to the Theory
of Games, volume 1 of Annals of
mathematics studies. H. Kuhn and A.
Tucker, eds. Princeton University Press,
Princeton, New Jersey, 1950, 97–103.
30. Mirowski, P. What were von
neumann and morgenstern trying
to accomplish? In Toward a
History of Game Theory. Weintraub,
ed. Duke University Press, 1992,
113–147. Mirowski cites Turing as
author of the paragraph containing
this remark. The paragraph
appeared in [ 46], in a chapter
with Turing listed as one of three
contributors. Which parts of the
chapter are the work of which
contributor, particularly the
introductory material containing
this quote, is not made explicit.
31. Morgenstern, O. The cold war is cold
poker. N. Y. Times Mag. (Feb. 5 1961)
32. Nash, J.F., Shapley, L.S. A simple
3-person poker game. In Contributions
to the Theory of Games I. Princeton
University Press, Princeton, New
Jersey, 1950, 105–116.
0–19% 20–39% 40–59% 60–79% 80–100%
Tier of humans
225 195 119 106 87
Figure 6. Games played by humans and Cepheus. Humans were
divided equally into five skill groups, and the column and error bar
indicates the group’s average loss to Cepheus in mbb/g.
Centre for Machine Learning (AICML), and was only possible
due to computing resources provided by Compute Canada
and Calcul Québec. The authors would like to thank all of
the current and past members of the University of Alberta
Computer Poker Research Group (CPRG), where the idea
to solve heads-up limit Texas hold’em was first discussed;
Jonathan Schaeffer, Robert Holte, Duane Szafron, and
Alex Brown for comments on early drafts of this article; and
Bryce Paradis for insights into the conventional wisdom of
top human poker players.