Humans Can Still Out-Bluff Machines

Pcol writes "The New York Times reports that in a poker game this week between man and machine, a program called Polaris fought a close match, but lost to two well-known professional poker players. Designing a poker playing algorithm is a different and more difficult challenge for software designers than chess and checkers because of uncertainties introduced by the hidden cards held by each player and difficult-to-quantify risk-taking behaviors such as bluffing. The game-tree approach doesn't work in poker because in many situations there is no one best move and a top-notch player adapts his play over time, exploiting his opponent's behavior. Polaris build a series of "bots" that have differing personalities or styles of play, ranging from aggressive to passive. Researchers monitored the performance of three bots and then moved them in and out of the lineup like football players."

Not harder than chess

[jshriverWVU]

In poker you have a finite number of cards, that are a lot smaller than the permutation of moves in chess or checkers. Just the ability to count cards and do statistical analysis makes poker, blackjack, etc easier to compute in my opinion. Then again, if you had a deck of random cards and not a standard deck, that would make it a bit harder but that's not how it's really played. That would be like comparing it to chess with all queens.

Hang on a Minute...

[bateleur]

The implication here is that there is no (known) equilibrium mixed strategy for bluffs (because if there were then Polaris could be coded to use it).

Is that really true?! It seems very counterintuitive.

Certainly there's nothing special in general about games involving bluff. One of Von Neumann's first game theory case studies involved a simplified version of poker precisely to demonstrate how to automate bluffing.

RTFA

[evanbd]

There were ten "bots"; which bot was in use was controlled by a "coach" program. They actually ran three different programs over the course of the tournament, and that setup actually lost to the humans. The coach / agent approach is an interesting one for a variety of reasons, and it is most definitely a valid strategy.

RTFA.

[raehl]

The researchers didn't choose which bots were used themselves - they had ANOTHER 'coach' bot that moved the 'player' bots in and out.

Chance elements make this hard to judge

[_bug_]

Poker has elements of chance. Chess does not. You can play the odds to help minimize the risk of chance, but it's still there. That one two or even 5 games resulted in a win for side A versus side B is pretty much meaningless. With chance involved you really need to conduct this sort of experiment over thousands, if not millions of games, to even begin to get a handle on if there really is a "better" player in the computer code.

You can flip a coin 5 times and all 5 might be heads... doesn't mean that heads will always win. That's chance. That's poker, even if the pros and the weekend wannabes try to argue otherwise.

Re:Not harder than chess

[AuMatar]

Because there's more to a situation than your cards. There's your chip stack, your blinds, the action behind you, your opponents chip stacks, the payment structure, and your position. Pushing on 8-3 unsuited is a poor move, but there's at least two situations where it's called for- if you're far from a money boundary in the payment structure, have a small number of chips in compared to the blinds (say an M of 3-5), and all players before you folded. In this case, by pushing in you're likely to win the blinds. Especially if none of your remaining opponents have a big stack. The risk can be worth it, since it makes absolutely no difference what hand you go out on unless you reach a new money boundary, and you'll have to win at least 1 hand to do so. And with 83, you're likely to have 2 live cards if called by a high ace (AK, AQ, AJ, AT). Note that you'd only want to do this if first into the pot- someone who called the blind is too likely to call you for only an additional 2-4 big blinds.

The other situation to try it in is a squeeze play- if you have a raise and a call behind you, you have a very tight table image, and you think they don't have good hands. A raise, especially an all in raise, is signaling an extremely good hand. From a tight player, this must be respected. You can get both players to fold here if they don't have premium hands (AK, QQ-AA). This is a high risk move though, and you must have been playing extremely tight, versus people capable of laying down a good hand, to try it.

Limit Holdem

[venicebeach]

Keep in mind these bots play Limit hold'em, where the size of the bets is fixed. No-limit hold'em, the kind you typically see on tv is a much more complex problem - size of bets add more potentially misleading information and more choices to make. (that's why its more exciting to watch than limit)

Re:RTFA.

[CyberLord Seven]

Think of it this way: the human player was playing against a "coach" who could vary his personality through the game.

Re:Hang on a Minute...

[Shaterri]

Simple bluffs are pretty straightforward to handle, but the combination of factors in poker (multiple rounds of action, shifting hand strength, complex unknown information) makes it inordinately difficult to compute Von Neumann optimal strategies. Even simpler games like (0,1) poker (both players are randomly 'dealt' a number in the 0..1 range, smallest number wins) with multiple betting rounds are remarkably difficult to solve under normal betting patterns. For more information, I heartily recommend The Mathematics of Poker by Chen and Ankenman.

poker jargon pedantry

[mr_mischief]

"is this game honest?"

well, no. not if the guy was dealt a "suited pair" from a single deck.

There's no such thing as a "suited pair" in a single deck.

You have four distinct suits, and thirteen distinct ranks. There is one card of each of the thirteen ranks in each suit, and likewise there is exactly one card of each suit at a given rank.

A "pair" is two cards of the same rank. "Suited" means two cards of the same suit. So to have a "suited pair", one must have two cards of the same rank and the same suit.

Therefore, by definition, if you have a "suited pair" and you're playing a single-deck game, the game cannot possibly be honest.

Re:Not harder than chess

[xero314]

I thought the limit only applied to the maximum be

That would be spread limit as opposed to fixed limit which is what they were actually playing. Most flop/board/community poker games played around the world are fixed limit, though stud games tend toward spread limit.

Second day was not a fair competition

[dl248]

Look at the first entry (bottom of page) on the Polaris team's blog for the second day. The day that the humans started winning:

http://www.cs.ualberta.ca/~games/poker/man-machine /Live/Day2Session1/ [ualberta.ca]

The U of A team gave the humans the logs of the first two games!

Perhaps after the entire match they could have reviewed the game logs, however this give the humans an unfair advantage during the second day. I can't believe that this isn't getting more attention -- they bascially gave the human team a huge insight into the inner workings, strategy, and tendencies of their opponent. Something that Polaris definitely did not have.

In my opinion this sours the competition and completely invalidates the final two matches. The human likely found a weakness (or two or three) and exploited it, and we can't know for sure that they would have found the weakness without those logs.

That was a huge mistake by the U of A team, and they have apparently got away with it without anyone noticing.

Re:Not harder than chess

[SIIHP]

"I'd venture to say that pot-limit omaha high is a *far* more psychological game."

You'd be wrong. I made my living for two years playing PLO almost exclusively, at a high level (fuck you UIGEA and everyone who voted for you). The general consensus among students of the game is that PLO is one of the least psychological games played. The lack of bluffing being the major reason. Bluffing occurs, but the very same reason you cite as making it more psychological is why you're wrong the number of hands played. Playing such a large number of hand (50% is insane, and I challenge you to show me some poker tracker stats of someone who wins playing 50% of their hands long term). In fact, if a computer were to win consistently, I think PLO is a game that it would play.

"I don't think there's a difference between statistical knowledge and psychology."

Then let me learn you up. Let's use PLO. I have A-A-10-J double suited. I raise pot preflop. A VERY tight player reraises, and I call. Flop come K-K-K. Against an aggro player, I can reasonably infer that my 2nd nuts is good. Against Mr. Tighty, who I have seen reraise only with large suited pairs (KKJQ, QQJ10) or rundown hands (9-10-J-Q, 10-J-Q-K) I know within a certain range what he's holding, with some certainty. I am first to act, I check, he bets, I raise, and Mr. Tighty RERAISES. Based on my assessment of his likely behavior (psychology) I can reasonably infer that he has the K. Statistically, you NEVER lay down K's full of A's, but when your read (psychology) is good and the opponent is uncreative and direct (psychology) you lay it down.

Statistically the correct play is to put it all in if you can, but by understanding the other players decision making process (psychology) you can find a fold.

You're wrong again

Re:Not harder than chess

[xero314]

There are plenty of times a pro player makes a call believing they have the worst hand, in order to bluff the hand later.

You are correct, but again this is because of statistical knowledge. A good player has determined in their own head what they believe the statistical chances are of their opponent having both a hand they can't call with and their opponent will believe that they themselves have a winning hand. Not only that the player making the call also has to determine if they odds are correct to try and set up a bluff like that in case their opponent has a draw and how good that draw is. If you are making any move in poker without first making a educated guess as to the odds, and determining that those Odds are in your favor, then you are leaving your odds up to chance and this is not how to be a successful player.

Re:Not harder than chess

[wildsurf]

It seems like the problem here might be the helplessness of artificial intelligence in the face of natural stupidity.

Douglas Adams invented a word for this:

ABOYNE (vb.) [langmaker.com] To beat an expert at a game of skill by playing so appallingly that none of his clever tactics or strategies are of any use to him.

Re:Not harder than chess

[drfireman]

You tell yourself that. But it's BS. Poker, when it comes down to it, is all about a) statistics, and b) luck. Is there a psychological component to it? Sure. But I'll bet dollars to donuts those aspects are greatly outweighed by luck and a given player's ability to evaluate the statistics on a given hand.

One of the chief reasons there are winning poker players is that there are lots of players out there who are willing to bet dollars to donuts without knowing what they're talking about. There are experienced poker players who would agree with you. They're usually pretty bitter, because they can't understand why despite having learned the statistics and having played a large enough number of hands for their skill to win out, they're long-term losers to those of us who've taken the time to understand it better.

In limit games against unskilled opponents, you're right. In other games, the psychology is much more important. And in fact, if you want to do the probabilities right, you need the psychology. There's almost no hand of interest you can analyze properly without an estimate of some quantity like "the probability this bozo would make that raise in this situation." Is it statistical analysis or psychology? Is it the sugar or the stirring?

Re:Not harder than chess

[Anonymous Coward]

opponent has 4 chances to have a king out of the 45 unseen cards

Ummm..no. The opponent has 1 chance out of the 45 unseen cards. 3 of 4 kings are already on the table.

Re:No-one MAKES a living gambling.

[joss]

Sancitmonious tripe. Those who lose money from poker do so voluntarily
so its a a form of entertainment they pay for. Professional poker
players are no more a leach on society than opera singers.