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.
That is why it is limit poker. Besides all games have limits acknowledged or not.
Think of the robot as the house, it might not win everytime but it always wins in the long run.
The thing about this robot is that it only wins over time and many hands. The best you can do with another robot is to tie. But that's all in the long run and assumes you have deep enough pockets to keep playing through the losing hands. The odds don't hold up for individual games played in isolation. Texas Hold'Em is very dependent on the draw of the cards and that randomness makes it impossible to win every time. This robot won't win every single hand so it's maybe not so hard to beat in the short term over a few hands if you get a lucky draw. But in the long run it will win (or tie if it's playing another robot).
From the article: "So, is online poker now dead? Destined to be crushed by robots? Not quite: No limit Texas Hold'Em—in which any amount of bet in any dollar amount can be made—is by far the most popular, and while robots can play that game quite well, we're no where close to solving it. Limit poker has roughly 3 x 10^14 permutations; no limit poker has 3 x 10^48, which is many orders of magnitude harder to solve."
Fantasy remains a human right; we make in our measure and in our derivative mode... -- JRR Tolkien
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.
"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.
They have found a non-exploitable strategy, not a maximally exploiting one.
This strategy will win less from an imperfect opponent than a strategy which maximally exploits that opponent's weaknesses. However, there is no strategy which can exploit a weakness in the strategy they have developed.