海角大神

If you were to spend an evening playing poker against Cepheus, a computer program developed by researchers at the University of Alberta, you wouldn't really be gambling. That's because you're guaranteed to lose.

The researchers have announced that they have essentially "solved" a popular variant of poker called Heads-up聽Limit Texas Hold'em. That is, for virtually every scenario that could arise in the game, Cepheus knows the optimal move.聽

Cepheus is the latest in a long line of poker players bred by UAlberta's聽Computer Poker Research Group, beginning in 1997 with a program called Loki.聽While these programs could all play competitively 鈥� a program called Polaris bested six human poker professionals in 2008 鈥� none managed to 鈥渟olve鈥� the game until now. CPRG's dubbed their newest program聽Cepheus, a sly reference to a constellation whose brightest star 鈥� Gamma Cephei 鈥撀爄s set to replace Polaris as the North Star a thousand years from now.聽

鈥淚t doesn鈥檛 actually need much computing power while playing,鈥� says UAlberta computer scientist Michael Bowling, who lead the research. 鈥淚t has one huge table that holds every possible decision point that can arise in the game, so all it needs to do is look up the appropriate action in the table.鈥�

While the program doesn't need much power to run, preparation for the game was a different story. Dr. Bowling鈥檚 team had 4000 CPUs 鈥渢raining鈥� Cepheus simultaneously, each one simulating six billion hands per second 鈥� that鈥檚 24 trillion hands per second total. This process lasted two months.

鈥淲e estimate that it has played more hands than all of humanity in the history of poker,鈥� Bowling says.

Cepheus represents a step forward for thinking machines 鈥� previously, programs have only been able to solve 鈥減erfect information鈥� games like tic-tac-toe, checkers, and Connect Four. In those games, past moves are known by both players. Poker, by contrast, is a family of 鈥渋mperfect information鈥� games, which means that certain aspects of the game cannot be known by both players.聽

There are only two players in Heads-up Limit Hold鈥檈m. Each player begins with a number of chips, and each is dealt a two-card hand that remains secret until the end of the game. Over a maximum of four rounds, five 鈥渃ommunity cards鈥� are dealt face-up on the table. In each round, players may 鈥渇old,鈥� 鈥渃all,鈥� or 鈥渞aise.鈥� If a player folds, the game ends and the 鈥減ot鈥� (the sum of chips wagered) goes to the other player. A player calls by matching the wagered number of chips, thus beginning the next round. If a player raises by increasing the bet, the round continues until a player folds or calls. If the game progresses to the end of the fourth round, the player with the best five-card hand 鈥� using cards from their own hand as well as the community cards 鈥� wins the pot.

Add competitive betting and bluffing to the mix, and the game becomes very hard to crack. Despite improvements in computational power and speed, the solution to the game eluded researchers for over a decade. Finally, Bowling鈥檚 team found the key in a surprisingly human concept: regret.

鈥淢any years ago, people started investigating聽鈥撀燼nd this is not just poker, this is artificial intelligence聽鈥撀燼lgorithms that minimize the amount of regret,鈥� says Jonathan Schaeffer a former CPRG leader who also led the team 聽in 2007. 鈥淭hese algorithms look at situations and come up with a decision that has, to put it simply, the best worst case. Regret minimization tries to come up with answers with the smallest amount of downside.鈥�

Cepheus plays to minimize loss, rather than maximize gain. In other words, it doesn't win every hand 鈥� in fact, it only wins the hand about 60 percent of the time聽鈥撀燽ut it reliably wins the pot over a long period of time. And if you thought Bowling鈥檚 program was casino-bound, you would be wrong. Poker is more than a game for Bowling and CPRG 鈥� to them, it is the perfect 鈥渢estbed鈥� to develop and improve artificial intelligence.

鈥淭he real world is a whole lot like a poker game,鈥� Bowling said. 鈥淥ne of the things we have to cope with in making any real world decision is uncertainty. Humans can deal with uncertainty. We鈥檙e still able to make reasonable decisions. Poker embodies that uncertainty. If we鈥檙e going to build artificial intelligence systems that can answer complex real-world problems, they need to deal with uncertainty. So looking at this through the lens of gaming is actually easier.鈥�

By expressing worldly problems as games, the same programming that allows Cepheus to dominate on the poker table could have a myriad of other uses 鈥� including cybersecurity, military strategy, and political negotiation.

鈥淕ame theory was always intended to be broadly construed,鈥� Bowling said. 鈥淭he word 鈥榞ame鈥� is actually misleading 鈥� it is really meant to represent any strategic problem-solving scenario with more than one person. One obvious example is security, which is already an area where game theory has had an impact. How do we protect things of strategic importance in a post-9/11 world? We have patrols and checkpoints and searches. These programs ask, 鈥榃hat鈥檚 the worst case that can happen, and how can we avoid that?鈥欌��

The game theory research community is also seeking out medical uses for programs like Cepheus. Tuomas Sandholm, a computer scientist and professor at Carnegie Mellon University, is working on applying game theory to epidemiology.聽

鈥淭he conceptualization is that the disease is one player, and the treater is another player,鈥� Sandholm said. 鈥淭raditionally in medicine, doctors try to give you a treatment that makes you myopically better. But here is the idea is that we can make sequential plans that may not make you myopically better, but they will drive the disease into a state where we can defeat it more effectively. Because diseases evolve or adapt to treatments in a myopic way instead of a strategic way, we can trap them.鈥�

鈥淭here are real-world applications for this, and in many ways poker is a much better game for understanding the real world because the real world is all about probabilities,鈥� said Schaeffer 鈥淪olving checkers, in some sense, was easy because the decisions were unequivocal. Here, it鈥檚 a matter of probability. Think about buying stocks 鈥� it鈥檚 not a sure thing. You鈥檙e going to read all the information you can about stocks, but it鈥檚 an educated guess. The whole world is about probability and decisions. Whether it be love or financial or war or politics, it doesn鈥檛 matter. It鈥檚 all about probabilities.鈥澛�

"" appears in the current issue of the journal Science. If you wish, , but don't get your hopes up.