Overreacting to a Computer Beating Poker Pros

Newspapers trumpeted a landmark event last week: a computer program beating professional poker players head-to-head at Limit Hold-Em. Parallels have been drawn to Big Blue‘s victory over Gary Kasparov roughly a decade ago.

Those parallels are not very meaningful.

First, heads-up Limit Hold-Em is a very simple version of poker — exactly the kind of game that a computer should be good at.

Second, unlike chess, which is deterministic, there is an enormous short-run luck component in poker. The variances are so high in poker that you need weeks if not months of play to confidently determine whether you are a winning player. There is no way with standard poker and two competent players that you could determine who is better in a short period of time. To try to remedy this shortcoming, the man vs. computer contest was actually run differently to lower the variance according to this report:

The matches will be duplicate matches of 500 hands of heads-up Limit Hold-Em. Each match will involve two separate human opponents playing simultaneously against Polaris. The same hands (hole cards and board cards) will be used in both matches but the humans will be dealt opposite sides of the cards. So if on the first hand one of the humans is dealt aces on the button, then Polaris will be dealt aces on the button in the first hand against the other human. If one player gets lucky in the 500 hands, their partner necessarily will be getting bad luck in their 500 hands, helping reduce to the luck factor in deciding a winner. The winner is determined by adding together the teams’ winnings (or losses). If either side [wins] by 25 small bets or more in total, then they are the winner, otherwise it is considered a draw.

This is a very clever structure (based on duplicate bridge) and greatly reduces the variance by making sure that the pairs of humans and pairs of computers receive the same set of cards. I have never seen any calculations done, but I suspect that even playing poker with duplicate hands has a huge variance in outcomes over such a short time horizon.

I actually think there are two things coming out of this poker contest that are more interesting than who won or lost: the design of the contest is very interesting, for instance.

Whenever someone wants to learn “the truth” in a world beset with randomness, reducing the variance is a critical part of solving the problem. This structure of poker where the luck of the cards is eliminated is a great example.

I could imagine lots of different settings in business or life where one could steal the insights of this duplicate poker design to learn more quickly about the world.

The second thing I find really interesting is the following: If duplicate poker reduces the luck factor in poker, is there a broader market for duplicate poker? You might think so. There is a website online where you can play duplicate poker, but I’ve never actually heard of anyone playing there.

Why is that?


John

Duplicate Poker is actually a lot of fun. I think you all should try and play it before judging it. www.duplicatepoker.com, it really is a good way to enhance your skill.

CH

In the long run, all poker will be duplicate poker. Playing duplicate poker over 500 hands will not tell you who the winning player is, especially if the hands are played by different players.

Baltimark

Certain posters should do more reading and less posting.

Let's see. . .your opinion and "experience" tell you that the sample size is too small, and that the best human players would beat a computer.

Good for you. We just had two people from the The University of Alberta Computer Poker Research Group tell you that the sample size is not too small and that the best human players don't beat the computer.

This group has been well known to the online poker community from the early rec.poker days and, I believe, they were the people behind pokibot, a poker playing bot from the IRC days that would get killed at full tables.

They are experts on the subject, and you should thank them for adding their expertise to this blog instead of saying, "It's a stupid test in the first place."

Matt

Chess is a game of total information. You know exactly what you opponent has and what moves they can make. Poker on the other hand is a game of partial information. With poker you have to make best guess at what you opponent has and then play accordingly. Additionally you have to try to get your opponent to incorrectly identify what you hold so they play incorrectly. Even if you get this right, you then have to ride your luck as even Aces against 72 is only about 80% to win.
If you simply play the odds and only raise good hands and fold bad ones you are predictable, so you have to purposefully misplay some hands....then you have to adapt your play to your opponent - are they tilting after losing a big hand? Have they raised recently? etc.
Since the mathematical elements like the odds are only a small part of the equation, for a computer to do well at this is a pretty big achievement. I would say even better that old bluey beating Kasparov given the more 'human' (for want of a better description) elements that poker requires.

Read more...

Darse Billings

First, thank you for the compliment on duplicate poker, which i devised 16 years ago and promoted in my MSc thesis (before founding the University of Alberta Computer Poker Research Group). As Mike Bowling mentioned, the format allows us to reduce the length of a match by about a factor of nine to obtain equally meaningful results.

Accurate assessment is essential for measuring progress in poker (or any other domain which contains a large amount of stochastic noise). I addressed that key issue by inventing the "Ignorant Value Assessment Tool" (DIVAT), so named because it "ignores" much of the specific context in order to filter out a large portion of the luck involved in any one poker outcome. The method focuses on the quality of the actual decisions that were made, in a mathematically rigourous manner. This analysis technique has been formally proven to be statistically unbiased. That means that it will arrive at exactly the same conclusion as playing regular poker, only a whole lot faster. It provides a powerful reduction in variance (again about a factor of nine reduction in match length), but can be applied to normal (single-sided) matches. The full technical details can be found in chapter five of my PhD thesis (http://poker.cs.ualberta.ca).

The two methods can be combined to create "duplicate DIVAT". There is some overlap (both methods address similar sources of variance), but it is then comparable to a factor of 20 reduction in match length. There were 6000 hands played in the second Man vs Machine match (each side of a hand counts as an independent data point), which equates to more than 120,000 hands of Limit Hold'em. That's significant.

But it doesn't stop there. Since we know exactly how the program will play in every situation (i.e. the mixed strategy probabilities), we can determine how the human's actions would have fared against the exact weighted distribution of hands the program *could have had* at each decision point. That affords a much better insight into how the match might have gone had things been just slightly different, and it allows a further reduction in variance comparable to duplicate or DIVAT alone. All combined, the necessary length of of a match for statistically significant results can be reduced by more than a factor of 80. Is half a million hands enough? Well, more is always better.

There certainly is variance in the outcome of any one duplicate session, for a variety of reasons i won't go into. However, if you look at the overall result of all games, it is very evident that Polaris was full credit for the win. The program earned almost 50 mb per hand (i.e. 2.5 BB/100) over 6000 hands (and post-match analysis indicates that it could have been substantially *more* under the same conditions). That compares favourably with the win rate of even the most successful players -- and they aren't playing opposition anywhere near as tough as the stoxpoker.com team.

Apart from the math, there is also the subjective assessment of the top players. Polaris's play has been lauded by some of the most successful players in the history of heads-up Limit Hold'em, including Bryce "Freedom25" Paradis (who won over 2.5 million dollars in 2007), and Matt "Hoss_TBF" Hawrilenko (who is probably the single best human player in the game). As a poker theoretician and former professional poker player myself, i have spent thousands of hours playing and studying every aspect of this subtle and highly complex game. I have exposed the limitations of every generation of our bots, until now. Despite all of my inside knowledge on how the bot was built, and despite months of systematic dissection and analysis, i have not been able to obtain any advantage against the latest generation of Polaris. I am willing to let it play my chips -- against anyone.

Hoss and Bryce are unquestionably great players, but for my money, it is Polaris FTW.

- Darse Billings.

Read more...

daviskel

It's a stupid test in the first place. Poker is not like chess in which you strive to find the best player. Poker is a contest of wills where the affects of risk are everything.

Every try to play poker without gambling? It's the same thing. Without the bet, the chance to win big or, even worse, loose big, it simply becomes a not very fun card game.

This type of pressure is uniquely human and it is what gives poker it's zing as a card game.

Computers can't feel pressure, and aren't concerned with loss so there is no challange, and hence no risk to the computer when or loose.

J B

IBM's computer was called "Deep Blue," not "Big Blue."

AJ

Actually, collusion in duplicate poker isn't all that much different some collusion on a "normal" site. The flop, turn and river all come out at once, so there is no additional information about the cards to come.

However, this makes the game painfully slow, and honestly, not that much fun.

Ryan

@ Baltimark (#21) I see the majority of dismissive posts claiming that heads-up limit hold 'em is not indicative that the computer is any better at the game of 'poker' as most people play it.

Michael Bowling

As the head of the University of Alberta's Computer Poker Research Group, I thought I'd say a bit about the variance reduction of duplicate.

The standard deviation of a typical hand of heads-up limit poker is 6 small bets.

The standard deviation of a pair of duplicate hands is 2 small bets.

This 3-fold reduction in standard deviation means that it requires 9x fewer hands to draw the same statistical conclusions. So 3000 hands of duplicate (the amount played in the competition) is the equivalent of 27000 hands of standard random-deal poker.

Polaris was up a total of 195 small bets over the course of all 6 matches. The probability of Polaris winning by that much (or more) if it was just an even-bet with the humans is 3.75%. By a standard confidence level of 95%, the result is significant.

We have further tools for reducing variance in poker (for example search for "DIVAT poker") and they confirm a statistically significant (albeit small) edge.

Of course, we don't expect the poker community to to simply take our word for it. We're expecting further challenges by the best in the world.

Read more...

Matthew

While this is noteworthy it is also of, imho, of limited relevence. Limit poker is a game of odds anyway and heads up is a very uncommon way to play. Unlike a typical hold 'em game, HE players must be in every hand, at least for the small blind, and proper play changes significantly. As a poker player, I am of course, interested in advances made in this field but I'll pay a great deal more attention when I head that one can hold its own at a table of good limit players.

Steve C

No, a computer cannot calculate odds perfectly in poker. The probability of a winning a single hand takes into account not only the probability of your pair of aces winning against an uncertain range of hands (any combination of draws, worse pairs), but probability of opponent folding the best hand to a bet on a given street, neither of which is uncertain. And then you need to take into account metagame, for example making slightly losing plays earlier in a match in the hope of manipulating an opponent's play and perception of you later in a heads up match. Dr. Levitt is correct in asserting that limit hold em is easier for computers to analyze than other forms of poker, however the point is that anyone who has played poker at a high enough level (and I don't mean those guys on ESPN, necessarily) cannot simply "play their cards" when playing skilled professionals.

HossTBF FTW.

Joe

One of the main problems with duplicate poker is collusion. Friends playing on different tables would be able to relay information about hands to each other.

Ben

Also, when discussing computer poker play, I think it's worth breaking the fundamental problems of poker down into two parts. Essentially, all forms of poker ultimately reduce to 1) putting your opponent on a range of hands, and 2) deciding how best to act given that range of hands. It seems intuitive to me that computers should do just fine at 2, if not better than humans.

Part 1 is perhaps a slightly trickier proposition, the land of "reads" that people always talk about as a foil to the "math guys" interested in game theoretic approaches. But many players these days do similar calculations for themselves based on a fairly small group of statistics - like how often a player bets or raises instead of calling, how often they raise preflop - that are compiled for them by computers. It seems to me like a pretty small step from here to fully automated play, though obviously there will be some snags.

Read more...

RH

There is a HUGE difference between poker and chess, and this is a major accomplishment.

The fact that the game is simple actually works to the detriment of the computer. The game is so simple that any poker player worth enough to get plubicity from beating knows EVERY probability on the table.

The game of Poker is played in the betting. He who predicts the other better, wins. Computers are historically bad at this because there is no easy game to calculate. You're fighting the human psychology... all 20 odd years worth of it, in many players cases.

Chris

@AaronS
Poker can't be solved like chess because of incomplete information (i.e., opponents' hole cards). Computer doesn't know if it has the winning hand at any time, until the end (when the hole cards are flipped up). It has to calculate the odds of having the best hand against a range of hands the opponents could have. The real advantages a computer has are:
1) it plays "perfectly", not going on tilt, not letting up on aggression, etc.
2) it remembers perfectly what you did and therefore can predict future play, and
3) it can vary its play (e.g., starting hands and betting) randomly to prevent you from predicting (and then exploiting) its strategy.

Dan M

It almost sounds like they used Black-Scholes Option pricing as a model for their contest. I am not a math-a-magician, but I bet they could introduce some of the greeks into the computer's programming to eliminate even more of the random aspects of the game.

scottro

Duplicate poker (I've played on the site) never took off because it is very confusing even to experienced poker players. The site did a horrible job, not only in explanation of the game, but in implementation as well. And the software was very clunky and buggy to boot.

That said, heads-up limit hold'em isn't as uncommon as you might think. Go online to the various sites and take a look. I play it myself, as it is an excellent strategy trainer, and against a weak-tight opponent, it can be very lucrative.

As for the contest of man vs. computer, I like the model, but the sample size is insignificant. It would take a long, long time to play the amount of hands necessary to come up with any sort of reasonable result. And my experience tells me that the best human players would beat the computer.

Michael F. Martin

It doesn't take many hands to see variance.

200 coin flips in a row and you're more than 95% likely to see six heads or tails somewhere in the run.

Ben

I think there are a couple of reasons duplicate poker seems unlikely to take off. First off, it just seems kind of strange to be focusing on indirect competition in that way. It lacks aesthetic appeal and it seems a bit tough to figure out. Still, that's probably just an initial barrier rather than an inherent problem in the infrastructure of the game.

A bigger problem is that it's kind of contradictory: a reduction in the amount of luck involved would kill the game. Skilled players who would benefit from reduced variance aren't going to want to play at a place where the supply of bad players rapidly drys up, but that's pretty much exactly what you'd get from duplicate poker. Presumably this is why poker is big in the first place, and you don't see too much wagering on games with less obvious luck factors, e.g. chess. (Obviously there are still some chess wagers but I'd guess the handle is orders of magnitude smaller.)

Read more...