Mathematicians, third graders, and talkative defense department computers alike all know that there is an infallible way to play tic tac toe. A competent player can always force at least a tie against even the most savvy opponent.
In the July issue of Science, artificial intelligence researchers from the University of Alberta announced they had cracked the venerable game of checkers in the same way, identifying an infallible strategy that cannot lose.1
It doesn’t matter if the strategy is unleashed against a bumbling novice or a flawless grandmaster, it can always eke out at least a tie if not a win. In other words, any player adopting the strategy (a computer, say) makes for the most flawlessy grandmasterest checkers player of all time, period.
The proof of correctness is a computational proof that took six years to complete and was twenty-seven years in the making.
Tic tac toe and checkers are examples of deterministic games that do not involve dice, cards, or any other randomizing element, and so “leave nothing to chance”. In principle, every deterministic game, including chess, has a best possible guaranteed outcome2 and a strategy that will unfailingly obtain it. For chess, even though we know that an optimal strategy exists, the game is simply too complex for any kind of proof — by person or machine — to unearth it as of yet.
The UofA team’s accomplishment is significant, marking a major milestone in artificial intelligence research. Checkers is probably the first serious, popular game with a centuries-long history of human play to be solved, and certainly the most complex game solved to date.
Next stop: Poker
Meanwhile, the UofA’s poker research group is building Poki, a computer player for Texas Hold’em poker. Because shuffling adds an element of chance, poker cannot be solved for an infallible strategy in the same way as chess or checkers, but it can in principal still be solved for an expected-best strategy. Although no one is anywhere near solving poker, Poki is probably the world’s best poker bot. (A CMU team is also making great strides.)
Poki’s legitimate commercial incarnation is Poker Academy, a software poker tutor. An unauthorized hack of Poker Academy [original site taken down; see 2006 archive.org copy] may live an underground life as a mechanical shark in online poker rooms. (Poki’s creators have pledged not to use their bot online unidentified.)
Poker web sites take great pains to weed out bots — or at least take great pains to appear to be weeding out bots. Then again, some bot runners take great pains to avoid detection. This is a battle the poker web sites cannot possibly win.
| 1Technically, tic tac toe is “strongly solved”, meaning that the best strategy is known starting from every game position, while the UofA team succeeded in “weakly solving” checkers, meaning that they found a best strategy starting from the initial game board configuration. | |
| 2The best possible guaranteed outcome is the best outcome that can always be assured, no matter how good the opponent. |
I don’t think poker can ever be solved the way checkers was. There is an important psychological component in poker, so even a complete analysis of the poker game tree would not lead to the best poker program against a human opponent. Besides, there are simultaneous moves in poker, which means that the game can have multiple equilibria.
I’ve often wondered why anyone would play online poker against an unseen opponent. I know that many poker players have big egos and that the challenge is paramount, but they do play for money, and I don’t know how you could take the chance that the other player doesn’t have a computer helping him/her. And the computer doesn’t have to be infallible, but it doesn’t seem farfetched that computer programs exist that can significantly help human players.
Thanks Mohammad. I think you’re right, but I want to make sure I understand:
* Do you see a fundamental difference between, say, backgammon, which also includes an element of chance but no betting, and poker?
* What moves in poker are simultaneous?
I believe what I meant to say is that there is in principle an expected-best response against an optimal (unboundedly rational) opponent (i.e., expected best in a worst-case sense). This seems similar to the minimax result of checkers/chess: optimal play against an optimal opponent.
To make things easier, perhaps consider the two-player, zero sum version of the game.
There is a fundamental difference between backgammon and poker. The difference (which I mistakenly stated as having simultaneous moves) is the assymetry of information in poker. For a game like checkers or backgammon, one can use a backward induction argument to shows that there is a “best strategy” for each player: the argument would start from the leaves in the game tree and moves up, showing that for every node there is a best move, assuming we know the best strategy at any node below. This works because you can compute the payoff at any of the children given the state of the board. The argument is essentially the same for backgammon, except you need to maximize the expected payoff.
But for poker, it is a different story: if you look at the last step of the game, my best move in that step depends on the move that opponents made in previous rounds (e.g., my best strategy against an opponent who bluffs often is different from my best strategy against a conservative player), and my opponents’ best move in turn depends on mine. This, in general, creates a game with multiple equilibria.
As an example, consider a simplified version of poker as follows: the two players each get a hand which is either H (high) or L (low), independently and each with probability 1/2. Then the first player (knowing only his hand) decides to either fold (in which case he loses $1) or bet. If he bets, the second player decides to either fold (losing $1) or to bet, in which case the higher hand wins $M (M>1). If there is a tie, the tie is broken in favor of the second player. The game is zero-sum.
If I’ve done my calculations correctly, this game can have multiple equilibria when M is at most 3. For example, when M=3, for every pair (p1,p2) such that p2 is at least twice p1, there is an equilibrium in which the first player bets with probability p1 on L and bets with probability p2 on H, and the second player folds on L and bets on H. For M less than 3, there is an even more complicated equilibrium in which the first player always bets on H and bets with probability (M-1)/(M+1) on L, and the second player always bets on H and bets with probability (3-M)/(M+1) on L.
Yet another complication of poker is that it is played as a repeated game. This can change the set of equilibria of the game. For example, it could be the case that if the first player has an L hand, it’s in her best interest to fold. But then the second player can tell that when the first player bets, he has an H hand. There is no way to get around this in a one shot game, but in a repeated game, the players can build “reputation†by sometimes betting when they have a low hand to motivate the other player to bet more aggressively too.
“Do you see a fundamental difference between, say, backgammon, which also includes an element of chance but no betting, and poker?”
Backgammon is a betting game, the major skill is knowing when to double, when to accept a double, and when to refuse. Moving the pieces if relatively simple, even beginners can frequently beat good players through luck, but they lose out on the betting in the long run. However, bluffing is not possible because both players have access to the same information, so it lacks the psychological complexity of poker. It’s purely a statistical game and good software will consistently beat human players.
Thanks pumpernickel, I hadn’t thought of backgammon doubling in that way.
If poker is “the human game that is played with cards” how is it that bots can play? The bots do not observe an opponent’s blink rate or hand position in relation to his chips. Poker players stare at each other, constantly looking for ‘tells’. Just because a poker bot solves by brute force the probabilities involved in a certain hand prevailing doesn’t mean that poker is being played.
Some time ago Absolute Poker had a tournament in which one player obviously could see the hole cards of everyone else at the table. Despite much whitewashing of the event, its clear that online poker can be fraudulent.
It sounds like you are arguing against online poker in general, not just poker bots
I agree that poker may never be solved. But if the history of chess teaches us anything, it is that a sophisticated program running on a supercomputer will be able to defeat a leading poker player soon, at least in head-to-head competition. Tournament play may be another matter …
Andrew, I would have agreed with you 110% before I started to play poker and even up until the time that I thought i knew the game.
But now, after having played perhaps a 20,000 games and after having seen all kinds of things happen where people say NO way No way… 3 of us with full hands on a table betting all-in with 3 months worth of saved poker points… ha ha…
This game is a game of balls. Even when you calculate that the pot odds compared to your odds of getting the nuts is favorable, that is still only one part of the calculation.
I like what Mohammed said above about simultaneous equations happening.
I am sitting at a table with 9 people who don’t like to fold ( loose as it gets ), I have calculated my pot odds vs my card odds and am Oh so sure of my self. I have had to chase out 5 of the 9 people by indiscrinate raising ( because 9 other people holds no surety even for pocket aces.
So, now i did something that no poker robot would be able to do successfully, which is to drive out the other players based on nothing but fear ( or they think i am stupid, ha ha ).
I am now sitting at the flop, and having done the pot odds to card calc and about to make the best computer sanctioned play, when suddenly I remember that one of my two opponents is simply going to call anything that I do, in other words I can’t drive him/her out, but i can certainly raise the pot.
So, i say something kewl in chat, to rattle this player, something like the truth, “Guys stop betting now, i have pocket aces …”
He or she suspects that I have king/queen combo and really doubts i have pocket aces. Even a poker robot would calculate low odds that I have pocket aces, especially if there was an ace on the flop and my opponent already has an ace.
Andrew, the computer simply isn’t going to win this particular round, and if it is forced to drop out or go all-in against a human opponent who went all in with 2 pocket aces and an ace on the flop, the SUPERCOMPUTER LOSES.
No, if ands or butts, it simply loses. Andrew.
Someone smarter than I would say, but perfect poker play entails making the best choice from an incomplete set of data, but the fact is that if you are forced to go all-in and the odds say that you should have won, yet you lose, you’re out of there buddy.
Perhaps a computer would have a better chance on a limit table.
Just my two cents worth…
The problem with poker robots or poker computers they would need to be able to switch their betting patters and profiles how to adapt and “bluff” like changing their loose-tight and aggressive level. The component of human betting psychology is something that I assume is something that will be never matched by a computer.
We will see, but I highly doubt it!
I can see the point being made by Trevor – the variability of the incomplete data set coupled with human finagling could leave a poker bot dangling, ( oh it rhymes )… however, I think what is being said above does not necessarily apply to one poker hand.
In other words, poker calculations give odds over a number of poker hands and the more hands involved is the statistically closer that the “perfect bot” would be able to come to achieving near perfect play with an incomplete data set.
I suspect that this may be what Andrew is saying above, which doesn’t totally invalidate what Trevor might be postulating, but it does put it more squarely into the context of statistical probability when a larger number of hands are being reviewed.
Please, nobody tell my granddaughter about this … she already runs rings around me when we play checkers. No computer is needed.
In my humble opinion, poker cannot be solved “by definition”. First comparing it to backgammon is not possible. Each game of backgammon involves making many decisions (dozens), before reaching a conclusion. Hence the signal/noise ratio is relatively small and true outperformers emerge rather rapidly.
On the other hand, one hand (game )of poker is only a few decisions each time (say in no-limit holdem, 4 streets, but the space of decisions is very small as most actions are “obviously” wrong). So that the signal to noise ratio is small (tiny).
Plus, and this is a big plus, an optimal strategy is contingent on the strategy of the opponent. There is NO unique strategy (unless it is adaptive) that beats all players. But then if you play against a bot with adaptive strategy, you can adapt to him too, there is some feedback loop.
Plus, and this an even bigger plus, it is not going to be possible to “prove” that we have solved poker, because you would need to have a strategy that beats all (adaptive) strategy; yes but you need to run that for millions of hands, don’t you; because at some point one dominated strategy may improve ans starts dominating…
Poker is a closed game. Unlike chess or checkers, or even go, poker is played while only knowing incomplete information – it’s as much a psychological game as it is a game of correct strategy. Having said that, there is by definition always a right or wrong decision to make at any point during a hand or game, even if the correct decision loses money (i.e. call to a draw with good odds but miss) and so in theory, if a computer was able to take ALL information into consideration (including profiling opponents) and could adapt and play deceptively, there is no reason that a bot couldn’t be developed which could play an optimal game IMO.
Poker was already solved by a mathematician a long time ago. What casinos did to solve this was just to add one or more mazes to the existing mix and that made the trick.
Thanks for very informative post. I play poker a lot and have a lot of fun 🙂
I beat 10 times the checkers’ bot