"Real life consists of bluffing, of little tactics of deception, of asking yourself what is the other man going to think I mean to do", said the great mathematician John von Neumann.

This uncertainty seldom appears in chess, checkers or other "perfect information" games, where all information is on the board for all players to see, but it's fundamental in "imperfect information" games, like poker.

These games are then great tests for computers designed to make hard decisions in real life, spurring scientists to a decade-long search for machines capable, of playing poker.

This search reached a milestone in January, with a publication in the Science journal.

A team led by Prof. Michael Bowling of the University of Alberta announced that their algorithm, called Cepheus, essentially solved the popular Texas hold'em poker.

The variant it plays (called heads up limit) features two players, fixed bets and fixed number of raises.

Simpler than full-scale hold'em, but challenging enough for real people to play competitively, and much more complicated than any imperfect information game ever solved.

Intuitively, Cepheus learned to play somewhat like people do: making choices, seeing how they play out, checking, in hindsight, what the best course of action would have been, then refining its strategy.

Of course, there are differences. For one, people efficiently recognize patterns, building player instincts and experience to guide their moves; whereas a computer must learn what to do in each of the trillions of possible situations, but has a mathematical guarantee to be heading for perfection.

Secondly, computers play much faster, quickly becoming immensely experienced: it is estimated that, in its two months of "learning", Cepheus played more hands of poker than the whole humanity combined ever did.

Cepheus' strategy does more than beating top-level human players (computers have done that for some years): it' is "perfect". It doesn't always win---nobody can in a game of chance---but it does the best anyone can do, be robust: in the long run it does not lose money, regardless of the adversary.

The scientists proved that any opponent playing against Cepheus for long enough (even for a lifetime) could hope at best to break even.

But poker is only a benchmark: Prof. Bowling says he researches computers that "make decisions for which we normally would expect we need humans". For instance, treatment recommendations for chronic diseases, like diabetes, would be an ideal application of the Cepheus algorithm. "Doctors need to make recommendations in a robust manner despite tons of uncertainty and only a small amount of information about the patient," explains Bowling.

Moreover, these treatments are long-run affairs, being carried out on many diverse people for their entire lives.

The algorithm would interpret daily measurements of blood sugar level as game moves and suggest a treatment with the least risks and best results for patients.

But Cepheus cannot undertake a task as difficult as diabetes--yet. It will not be too long, though, "maybe 10 years", Bowling says, "before people can use their phones to tweak their treatment in between visiting a doctor".

In the meantime, you can challenge Cepheus for a few hands of poker on the University of Alberta website. Fair warning: it has a perfect strategy, so don't get your hopes too high.


Image
URL: https://www.flickr.com/photos/evanblaser/8476189033
Credit: Evan Blaser/flickr
Licensing: creative commons - attribution (CC-BY)