1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
Software routinely beats humans at Chess, but what about less mathematically precise games like Poker? For the time being, humans have the edge, but not by much. Just as early attempts by software designers to defeat Kaperov in Chess ended in failure, the first human-computer poker match goes to the humans.
But don't get your hopes up. Just as software can generally beat the pants off humans in backgammon, checkers and chess, the average poker player is unlikely to defeat the current crop of software and more sophisticated programs are expected to take down even the best poker players within a decade.
Last week's contest pitted poker champion Phil Laak and fellow pro Ali Eslami against a piece of software designed by researchers at The University of Alberta Computer Poker Research Group. The machine, known as Polaris took an early lead, but in the end Laak and Eslami managed to come out ahead 2-1.
To eliminate the luck of the draw, the Alberta researchers came up with an ingenious tournament design: Laak and Ali Eslami played in separate rooms, and their games were mirror images of one another, Eslami drew the cards that the computer received in its hands against Laak, and vice versa.
This contest was unique in that Texas Hold 'Em is different than other games in which computers has mastered humans. In chess, checkers and backgammon, the playing field starts at the same point and then branches out into an enormous, but still finite set of possible moves.
In order to be successful the software simply need to map out all possible future moves and choose the one that leads to the win -- while that's a complex sceneario and requires serious processing power, it's obviously still possible (Big Blue could see around 20 moves ahead when it played Kasperov).
But Texas Hold 'Em is considerably more complex. Not only are there a myriad of possibilities but there's another element that computers typically stumble upon -- uncertainty.
And in the case of Poker, there are two uncertainies the software must deal with -- what cards does the opponent hold and how will s/he play them?
To overcome the uncertainties of opponents, the programmers that developed Polaris couldn't use the look-ahead approach of Big Blue, instead they relied on , appropriately enough, game-theory.
Game Theory, a branch of mathematics founded by John von Neumann and formalized by John Nash, whose life inspired the movie "A Brilliant Mind," says that in certain games there will always be a set of strategies such that
there is a set of strategies such that every player's return is maximized and no player would benefit from switching to a different strategy.
In the simple game "Rock, Paper, Scissors," for example, the best strategy is to randomly select each of the options an equal proportion of the time. If any player diverted from that strategy by following a pattern or favoring one option over, the others would soon notice and adapt their own play to take advantage of it.
Texas Hold 'em is a little more complicated than "Rock, Paper, Scissors," but Nash's math still applies. With game theory, computers know to vary their play so an opponent has a hard time figuring out whether they are bluffing or employing some other strategy.
But game theory has inherent limits. In Nash equilibrium terms, success doesn't mean winning - it means not losing.
"You basically compute a formula that can at least break even in the long run, no matter what your opponent does," Billings said.
That's about where the best poker programs are today. Though the best game theory-based programs can usually hold their own against world-class human poker players, they aren't good enough to win big consistently.
Squeezing that extra bit of performance out of a computer requires combining the sheer mathematical power of game theory with the ability to observe an opponent's play and adapt to it. Many legendary poker players do that by being experts of human nature. They quickly learn the tics, gestures and other "tells" that reveal exactly what another player is up to.
A computer can't detect those, but it can keep track of how an opponent plays the game. It can observe how often an opponent tries to bluff with a weak hand, and how often she folds. Then the computer can take that information and incorporate it into the calculations that guide its own game.
"The notion of forming some sort of model of what another player is like ... is a really important problem," Nau said.
Computer scientists are only just beginning to incorporate that ability into their programs; days before their contest with Laak and Eslami, the University of Alberta researchers are still trying to tweak their program's adaptive elements. Billings will say only this about what the humans have in store: "They will be guaranteed to be seeing a lot of different styles."
Even so, Laak and Eslami are top-notch players with a deep understanding of poker's mathematical fundamentals. They should be able to keep up with the computer - this time.
|
