Slashdot Mirror
Researchers "Solve" Texas Hold'Em, Create Perfect Robotic Player
Jason Koebler writes The best limit Texas Hold'Em poker player in the world is a robot. Given enough hands, it will never, ever lose, regardless of what its opponent does or which cards it is dealt. Researchers at the University of Alberta essentially "brute forced" the game of limit poker, in which there are roughly 3 x 10^14 possible decisions. Cepheus runs through a massive table of all of these possible permutations of the game—the table itself is 11 terabytes of data—and decides what the best move is, regardless of opponent.
Mathematically speaking, all these games which are based around predicting what your opponent might do (and possibly a random factor, like in poker) have a perfect strategy, but that perfect strategy has random factors. For instance, the mathematically perfect strategy for rock/paper/scissors is to pick "rock", "paper", and "scissors" each with 1/3 probability. There is nothing an opponent can do to get more than a 50:50 chance of beating this strategy.
Rock/paper/scissors is unusual in that the game is symmetrical: a perfect strategy can't get any better than 50:50 against anyone. That's not true of poker, though; in such a case, a perfect strategy will have a better than 50% chance of beating anyone who plays imperfectly, and a 50% chance against a perfect strategy (due to symmetry).
I'm actually quite interested in the theory of this sort of game (where there are random factors and outguessing opponents involved), and even in simple cases, the calculations can be hard. I'm reasonably interested in whether this poker strategy is a probabilistic one (that can't be outpredicted as long as the random number generator used is sufficiently high-quality), or whether it just takes the best option without randomizing (which is much easier to implement, but which can be outplayed via knowledge of the algorithm like you suggest).
(1)DOCOMEFROM!2~.2'~#1WHILE:1<-"'?.1$.2'~'"':1/.1$.2'~#0"$#65535'"$"'"'&.1$.2'~'#0$#65535'"$#0'~#32767$#1"
I'm a former professional poker player, now semi-pro and working again in the IT industry. In a game like poker, to "solve" the game, from a mathemartcal and game theory point of view, means to develop a strategy that is "unexploitable", which basically means "mistake free". If two game-theory perfect players were to play against each other, then their "expectation" would be zero, as if they were flipping a coin between each other. Neither would make a mistake, so only te randomness of the cards would determine the winner of a given hand. In the long run, both perfect players would win as often as they lose.
But in a real poker game, human players make lots of mistakes. A player who adjusts their strategy to exploit these mistakes will win vastly more than this (formerly theoretical) "perfect player". The game-theory optimal strategy is focused on not losing, rather than exploiting mistakes and winning the most.
So in an actual game, the expert human player will outperform the computer because the other humans in the game are exploitable.
In live play, especially in tournaments, computer solutions are used in poker. In particular, when the game is "heads up" (only two players), and the chips are not deep, which happens at the end of every tournament, then the correct strategy is to "jam or fold" all hands. The solution to this has been determined in a computer and top players have the table memorized.
If this subject interests you, I HIGHLY recommend "The Mathematics of Poker", by Chen and Ankenman.
Maybe so, but a lot of online casinos have some reason to kiss their feet. You see, a lot of countries have laws against "gambling", which is usually defined as playing games for money where luck is the deciding factor.
And these people just proved that luck plays no role.
So playing poker is no longer gambling. Scientifically proven.
We used to have a Bill of Rights. Now, with the rights gone, all we have left is the bill.
"What happens if someone else creates an identicly perfect robotic player and joins the table?"
Not that I know so much about Texas Hold'em but, by the look of the text, "...Given enough hands, it will never, ever lose, regardless of what its opponent does or which cards it is dealt." these researchers have discovered the equivalent of a Nash equilibrium in the game.
"If these two robots played each other wouldn't the winner be determined by pure luck?"
Key words here are "given enough hands". This means that given enough hands, they would tie.
This doesn't prove it at all. You shouldn't have been modified +5 Insightful. Over the course of a game, luck is very important. Like you get dealt the card you already have, or you get dealt crap.
Blackjack also has a perfect strategy, and of course blackjack has a great amount of luck.
I guess if you planned on playing an infinite amount of games, luck wouldn't be a part of Texas Hold Em. For somebody playing a finite amount, luck is key.
Slashdot: providing anti-social weirdos a soapbox, since 1997.