Solving Heads-up Limit Texas Hold'em

Oskari Tammelin, Neil Burch, Michael Johanson, and Michael Bowling. Solving heads-up limit Texas hold'em. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), 2015.

Download


Abstract

Cepheus is the first computer program to essentially solve a game of imperfect information that is played competitively by humans. The game it plays is heads-up limit Texas hold’em poker, a game with over 10^14 information sets, and a challenge problem for artificial intelligence for over 10 years. Cepheus was trained using a new variant of Counterfactual Regret Minimization (CFR), called CFR+, using 4800 CPUs running for 68 days. In this paper we describe in detail the engineering details required to make this computation a reality. We also prove the theoretical soundness of CFR+ and its component algorithm, regret-matching+. We further give a hint towards understanding the success of CFR+ by proving a tracking regret bound for this new regret matching algorithm. We present results showing the role of the algorithmic components and the engineering choices to the success of CFR+.


Notes

This paper is a sibling to our 2015 Science paper on solving heads-up limit Texas hold'em, which focussed on reaching the milestone of solving the game. This paper goes into more detail about the new algorithm we used, CFR+, which was invented by Oskari Tammelin. We present for the first time the theoretical proofs of convergence, empirical results in smaller games that help to tease apart the advantages of CFR+ over CFR, and a new connection to tracking regret that may help to explain why CFR+ converges so much faster than CFR.


Links

  • The Science paper, on the milestone of solving heads-up limit Texas hold'em.
  • Oskari Tammelin's CFR page. Oskari developed the CFR+ algorithm, and was part of our team for solving HULHE. His website has a fantastic demo of CFR algorithms, where you can edit the code and watch the strategies evolve in real time.

BibTeX

@InProceedings{ 2015ijcai-cfrplus,
  Title = "Solving Heads-up Limit Texas Hold'em",
  Author = "Oskari Tammelin and Neil Burch and Michael Johanson and Michael Bowling",
  Booktitle = "Proceedings of the 24th International Joint Conference on Artificial Intelligence",
  Year = "2015",
}