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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
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, a computing science 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 against Poker champion Phil Laak and fellow pro Ali Eslami, who narrowly eked out a 2-1 win.
The Alberta team sees the recent match as a victory though.
QuoteTK
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 Texas Hold 'Em is a lot more complex than Rock, Paper Scissors and Nash's theories aren't going to make you a World Champion Poker player. They simply ensure that you're likely to have some gas money for the ride home.
"Nash equilibrum programs these are the strongest that we have right now, but they don't learn."
"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."
But if or when a computer is able to master human opponents in poker, it will have far reaching applications for the field of artificial intelligence.
-
- "There are two reasons poker is different than chess. The one reason
is chance -- there are unknown cards that come out, but the biggest
problem with poker is that there's imperfect information -- the player
to act doesn't have all the information"
- poker-playing experiment last month shows how much of a challenge this is
- maybe end with a quote from a poker playing expert who says it's a
problem with humans, too. even if you're doing everything
strategically correct, you can still lose.
As it turns out, poker makes an excellent model for the kinds of real world scenarios AI researchers face, and the key to intelligent machines could well lie in the very thing that makes poker fun for human players -- uncertainty.
In order for software to be successful in poker it must learn from its opponent's behavior and adapt. Michael Bowling, a computing science professor at the University of Alberta who has helped develop some of today's cutting edge poker software, says "almost every problem you'd want to address in the real world is one of imperfect information."
In order for software to be successful in chess it simply needs to map out all possible future moves and choose the one that leads to the fastest win. While that's a complex scenario and requires serious processing power, it's still possible (Kasparov tied Deep Junior, which was capable of processing three million positions a second, in 2003 ).
Chess represents what Game Theory mathematicians refer to as "perfect information," when you look at the board you know everything there is to know about the game.
But Poker does not offer such information. "There are two reasons poker is different than chess," says Bowling. "The one reason is chance -- there are unknown cards that come out, but the biggest problem with poker is that there's imperfect information -- the player to act doesn't have all the information"
The missing information must be guessed at using all the tricks of the trade that professional poker players know. Lacking eyesight, computer's aren't yet at a point where they'll pick up on your tells. For the moment software developers are focused learning how you bet and trying to guess when you're bluffing -- and they're getting pretty good at it.
Just ask Poker champion Phil Laak and fellow pro Ali Eslami who recently went head to head with Polarius, the program developed at the University of Alberta, and only narrow eked out 2-1 victory.
How does the software do it?
Game Theory, a branch of mathematics founded by John von Neumann and further expanded 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 very player's return is maximized.
For instance, in the children's game "Rock, Paper, Scissors," the optimized strategy is randomness -- a successful player will select each of the options an equal proportion of the time in no particular order or pattern.
This state of game play is called equilibrium, there is no better strategy an 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, they simply ensure that you're likely to have some gas money for the ride home.
But if a player deviates from the randomness and begins to use a pattern, other players may recognize the pattern and exploit it to their advantage. This is essentially what computer software must learn to do -- learn other player's patterns while randomizing it's own play, making it difficult for other's to guess what it will do next.
And Texas Hold 'Em is a lot more complex than Rock, Paper Scissors.
|
