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
|
If the machine takeover hypothesized in the Matrix plays out like a game of chess, we're doomed. If it's more like Texas Hold 'Em we could still have a chance. However now might be good time to start thinking about scorching the sky, because software poker applications are gaining fast on human players.
But it's not there yet. The biggest problem facing game-solving software programmers is uncertainty -- what they call imperfect information. "Almost every problem you'd want to address in the real world is one of imperfect information," says Michael Bowling, Associate Professor at the University of Alberta where much of today's cutting edge poker software is being developed
IBM's Deep Blue settled the human-computer chess contest long ago when it defeated Garry Kasparov in 1997, but other games, like poker, are more mysterious. The problems of chance and randomness still have computer programmers stumped.
"It's a very heard problem to solve. We're still looking for the magic recipes," says Jonathan Schaeffer who founded the Alberta research program.
There are two reasons poker is different than chess. The one reason is chance -- there are unknown cards that come out, but the biggest with poker is that there's imperfect information -- the players don't have all the information about the game.
The missing information must be guessed at using all the tricks of the trade that professional poker players know -- a difficult task for computers to replicate.
Last month the Alberta team pitted their software in two heads up games against Poker champion Phil Laak and fellow pro Ali Eslami. While Laak and Eslami were able to eked out a 2-1 win, the Alberta team sees the recent match as a victory.
"We think this was a great success," says Bowling, "I think you need to go no further than the players to know how close we are to humans -- they were definitely scared of the program."
So how does the software do it?
John Nash, whose life inspired the movie "A Brilliant Mind," helped develop Game Theory which says that in certain games there are a set of strategies where every player's return is maximized.
For instance, in the children's game "Rock, Paper, Scissors," the best strategy is randomness -- to win you should select each of the options an equal proportion of the time in no particular order or pattern.
This is known as equilibrium -- statistically each player should win one-third of the time, lose on third of the time and tie on third of the time.
But Nash's theories aren't going to make you a World Champion Poker player because an equilibrium program isn't designed to win, it's designed to not lose. And Texas Hold 'Em is a lot more complex than Rock, Paper Scissors.
"Nash equilibrium programs these are the strongest that we have right now, but they don't learn," says Schaeffer.
"if you have obvious tells, the program is incapable of taking advantage of that and exploiting it. It will play strong poker, but it won't adapt to your playing."
One of the reasons the human players won the recent match-up is they recognized this could and were able to adapt their playing to exploit the computer.
If the program was capable of learning, it would soon have humans on the run. "It would become a cat-and-mouse game of changing strategies," says Bowling, who goes on to add that "I suspect the computer would be more on the cat side of that equation."
In the mean time the team is refining its equilibrium program and Bowling says a rematch is in works.
|
