Fold your hand, Johnny Moss. Muck your cards, Phil Ivey. Cash in your chips, Doyle Brunson. There is a new Heads-Up Limit Hold’em (HUHLE) sheriff in town. Name’s Cepheus and a more dogged, single-minded foe you are not likely to meet. Sure, Cepheus won’t win every hand from you but in the long run the varmint will never lose.
To reach this status as the world’s first unbeatable HUHLE player, Cepheus had to calculate the optimal outcome for more than one trillion zigs and zags in game play. To do that required 4,000 computer processors humming for 68 days. Fortunately, Cepheus is a computer itself. At the conclusion of all that ciphering it emerged with a bullet-proof poker algorithm.
The success of Cepheus is the latest in a steady succession of these machines taking down their human counterparts in games of skill and chance. The first time a computer defeated a world champion of a recognized intellectual activity took place in Monte Carlo in 1979. The BKG 9.8, a computer backgammon program developed by Hans Berliner at Carnegie-Mellon University, shipped across the Atlantic Ocean to take on recently crowned world champion Luigi Villa on his home turf.
Berliner came to computer backgammon through chess, a game in which he was a Grandmaster and international correspondence champion. His first efforts with BKG 9.8 were dismal and the machine would lose to just about anyone on the Pittsburgh campus who stopped in for a game. But then Berliner applied fuzzy logic that approximated chance results rather than fixed moves tied to exact reasoning. That did the trick. BKG 9.8 upped its game and in the first sit-down with Villa thumped the Italian champion 7-1 in a match to seven wins. It marked the first time a computer program mastered humanity’s best at any game, although Berliner always pointed out that the computer received much the best luck in the throws of the dice.
The next advance in artificial gaming intelligence came in 1990 when a computer program named Chinook finished runner-up to Marion Tinsley in the United States Nationals. That accomplishment earned Chinook, developed at the University of Alberta, entry into the world championships, a competition that until then had not needed to post signs reading “humans only.” In response, a new title was created for the battle for checkers supremacy – Man vs. Machine Championship.
The Ohio-born Tinsley was widely regarded as the greatest checkers player of all time. He sat down against Chinook and defeated the program 4-2 in a match with 33 draws. Still, those losses represented almost 30% of the Grandmaster’s seven defeats in a 45-year career. Tellingly, in one of Chinook’s losses the machine erred on just the tenth move of the game which prompted Tinsley to immediately observe, “You’re going to regret that.” Chinook indeed resigned following move 36. After studying the database the Alberta programmers saw that Tinsley had selected the only possible strategy to successfully capitalize on the mistake – a feat that required seeing the win 64 moves ahead.
In 1994 Tinsley and Chinook squared off for the World Championship. After six draws Tinsley had to withdraw due to complications from pancreatic cancer that would kill him several months later. Chinook was declared world champion and the computer defended the title the next year in a 32-game match against Don Lafferty, 1-0-31. Chinook was then withdrawn from competitive play so its developers could “solve” checkers and play perfectly from every position in the game. In 2007, the Alberta team announced that it had found an algorithm that insured that the best a human player could ever achieve against Chinook was a draw.
Man versus machine game competition pushed its way onto the front pages in 1996 when 12-year reigning world chess champion Garry Kasparov tangled with a chess-playing computer developed by IBM named Deep Blue. Kasparov prevailed in the six-game match 4-2 but in the process Big Blue became the first instrument of artificial intelligence to defeat a reigning world chess champion in regular time.
Deep Blue, which had been more than a decade in the making, was hauled back to the shop bowed, but not broken. The programmers upgraded the apparatus to to evaluate 200 million positions per second, bringing twice the firepower to the rematch with Kasparov in May of 1997. This time Deep Blue bested the Russian grandmaster 3 1/2 to 2 1/2. After that Deep Blue was disassembled and going forward artificial intelligence research has concentrated on developing chess software program. No computer as powerful as Deep Blue has ever faced a human world champion again.
Since Deep Blue a computer program called Quackle outpointed world champion David Boys in Scrabble, a professional Go player was toppled by a supercomputer and another IBM computer named Watson outgunned two human opponents to walk off with a $1 million first prize on the television quiz show Jeopardy! But none of these games presented the challenge to artificial intelligence researchers that poker brought to the table with it incomplete knowledge of the state of the games – a computer can not tell what cards the other player is holding.
Tackling the problem was another team of scientists from the University of Alberta in Edmonton. In addition to the essential unknown of poker, programmers also needed to grapple with bluffing and pure luck. Bluffing, an intentional misrepresentation of the facts, would seem to be a difficult obstacle for perfectly rational computers to comprehend but in fact the variable is a programmable part of game theory in computer poker. Mathematical models predict how often players should bluff to obtain maximum returns.
Random luck is not so easy to replicate. To best conquer this the programmers had Cepheus play millions of games against itself and applied counterfactual regret minimization principles against the analysis of play. In the end more than six billion hands of poker were played, more than the entire human race is considered to have dealt. Each play was assigned a “regret” value and the computer updated itself until it whittled down an algorithm to deliver the best play in every possible situation. Bad luck and bad cards will still cause Cepheus to lose hands but in the long run the algorithm will win every time.
This counterfactual regret algorithm is considered the biggest contribution of Cepheus to real-life situations beyond one-on-one Texas Hold’em. Applications of this game theory in situations of imperfect information can include medical diagnoses, military strategy, contract negotiations, financial investing and more.
And Cepheus is the master of only one kind of poker – Heads-Up Limit Hold’em. If you find yourself in a money game with the computer insist on No Limit. Or deal a little stud.