Solving Heads-up Limit Texas Hold'em

Many real-world problems require agents to make decisions while being uncertain about the outcome of their actions. Designing autonomous agents that can act effectively despite such uncertainty is a fundamental challenge in... [ view full abstract ]

Many real-world problems require agents to make decisions while being uncertain about the outcome of their actions. Designing autonomous agents that can act effectively despite such uncertainty is a fundamental challenge in artificial intelligence research. 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 decision points, that has been a challenge problem for artificial intelligence for over 10 years. Cepheus was trained using a new variant of Counterfactual Regret Minimization (CFR), called CFR+. CFR+ is space efficient, and improves on the speed of CFR, but using CFR+ to solve a game of this size still poses a challenge both in terms of computation time and space. For instance, a naive approach to solving this game would require 262 TiB of data storage. We address the engineering challenges required to make this computation a reality through efficient data compression and distributed computing, using 4800 CPUs running for 68 days. We also prove the theoretical soundness of CFR+ and its component algorithm, regretmatching+. 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+.