Belinda Smith
Belinda Smith is a science and technology journalist in Melbourne, Australia.
When it comes to games, machines have left us in the dust – we’ve been trounced at draughts, chess, even the TV quiz show Jeopardy. But clever humans still had an edge when it came to poker – until now.
A new program, Cepheus, plays the game so well you could play against it your whole life and, unless you were unbelievably lucky, still not finish on top. It is the brainchild of Michael Bowling and colleagues at the University of Alberta who published the algorithm behind their winning result in Science.
And yes – Cepheus can even bluff.
“It will almost certainly leave human opponents in its wake,” says David Dowe, a machine learning and artificial intelligence expert at Monash University.
Computer algorithms are very good at cracking those games where players know everything that has occurred before making their move – this is known in game theory as “perfect information”. Examples are Connect Four and draughts – each player can see where all pieces lie on the board. These games were solved by computers in 1998 and 2007 respectively. But poker is an imperfect-information game. A player doesn’t know what cards their opponent holds or what cards their opponent thinks they hold. Not surprisingly, it’s these unknowns that make poker extremely challenging for computers to handle.
So in 2008, Las Vegas was a little shaken up when a computer program, Polaris, beat some of its best poker pros at Texas hold ’em. But Polaris was not perfect – it occasionally lost. By rejigging its algorithm, Bowling and his poker research group have upped the ante and “solved” the game of poker while they were at it.
“Solving” a game is not quite the same as beating your opponents. When it comes to chess or Jeopardy, all IBM’s Deep Blue or Watson had to do was provide a solution superior to their human opponents – but not necessarily the perfect one. By contrast, Cepheus’s algorithms were derived as rigorously as any mathematical proof. Its solutions are unbeatable by any opponent. So poker can be said to have been solved in a way that neither chess nor Jeopardy have.
To get to its virtually unbeatable state, Cepheus had to “learn” from experience. It played the equivalent of a billion billion hands over two months, “… more poker than has been played by the entire human race,” says Bowling. And in a classical example of machine learning, it reviewed every decision, learnt which did or didn’t pay off and used that information to play as perfectly as possible.
Cepheus’s strength lies in its ability to solve problems where there is a great deal of uncertainty.
A human opponent might win individual hands if they get lucky with the cards, but Cepheus always comes out on top in the long run.
Texas hold ’em is the most popular form of poker played today and Bowling’s group restricted Cepheus to a simple version called “heads-up limit hold ’em” – it’s played with two players (heads-up) and has fixed bet sizes and number of raises (limit).
But when faced with a decision in real life, people aren’t usually limited to a set number of choices. So might a future version of Cepheus solve a no-limit version of poker? “Out of the question, ” says Bowling.
“No-limit poker is considerably more complex. The heads-up limit game has 1014 (100 trillion) possible decision points and heads-up no-limit hold ’em has 10140 decision points.” To put that number in context, there are around 1070 atoms in the universe. If every atom contained its own universe you’d have as many atoms as decision points in heads-up no-limit hold ’em poker, well beyond the capabilities of any computer.
Bowling believes the decision-making strategies Cepheus has mastered will have their greatest impact outside of the games room. Artificial intelligence has a history of beating humans at games and then going on to bigger and better things. For example, IBM’s Jeopardy-winning computer system Watson now helps optimise cancer treatment at Sloan Kettering and provides financial advice at Citicorp and ANZ.
Cepheus’s strength lies in its ability to solve problems where there is a great deal of uncertainty. For instance, if you have diabetes, calculating the wrong amount of insulin needed day-to-day can be life threatening, particularly when you take into account unforeseen changes in physical activity or diet. Working with clinicians, Bowling is already using Cepheus-like strategies to develop diabetes management policies, although he says it will be years before they are implemented.
Despite heading the poker research laboratory, Bowling says he’s not much of a poker player and has only played a few hands against his “perfect player” program. “The first time I ran for about 20 hands and I was in the lead and ready to quit, but then I played another 20 hands and lost a bunch of money, so now I’m behind,” he laughs.
You can try your hand against Cepheus at http://poker.srv.ualberta.ca/play
