Slashdot Mirror
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."
If the researchers had control of which bots to use during the game, then the researchers were playing the game and the computer was not. Let's see how well the computer does when IT makes all the decisions.
--jeffk++
ipv6 is my vpn
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.
let's see how well those computers do in strip poker!
Bite my shiny metal ass.
I got the impression from some of the news stories that two professional poker players barely beat out the machine.
I have a sneaking suspicion that, for the vast majority of players, the computer is gonna kick your ass quite handily.
For the same reasons, I suspect that everyone who wasn't at the level of Kasparov would have gotten their asses handed to them in a game of chess against older versions of computers which couldn't yet beat him.
This, of course, begs the question of how long it will take for the on-line casinos to start putting poker playing bots into the mix to skew the odds even further to the house. I mean, if you have a computer program which will beat everyone else, why not just dial it down so it only wins 30% of the time or so and nobody will be any wiser.
Cheers
Lost at C:>. Found at C.
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.
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.
I think that it'll probably stay this way for a while - man beats machine, altho as been talked about before when someone got beat in chess by one. I can't remember the name of it, but I'm sure others know. I'll be impressed once computers can out-think human beings totally.
Seems like a computer's ability to compute probability should win in the long haul. Dealing with bluffing seems moot when you can compute cash flow stakes using something like a markov chain.
The researchers didn't choose which bots were used themselves - they had ANOTHER 'coach' bot that moved the 'player' bots in and out.
paintball
Or at least a more interesting one, I may give up trying to master chess for poker :) The potential for less concrete interactions between players to influence the outcome more closely matches the real-world interaction of individuals IMHO. (And yes, I'm aware that chess games involve plenty of psychology, but not between a human player and computer opponent.)
(not an exact quote)
The Raven
Dealer: My deal..
Eliza: What does that suggest to you?
Dealer: It suggests I'm giving you your cards.
Eliza: We can talk about me later. Now back to you...
Guest: Here you go.
Eliza: So you feel I go...
Guest: Um.. yeah. How many cards do you want?
Eliza: What else comes to mind when you ask that?
Dealer: You need to give me whatever cards you want to exchange.
Eliza: I see. Tell me more.
Dealer: Um.. so you can get a better hand?
Eliza: We were discussing you--not me.
Dealer: Do you have any interest in playing this game?
Eliza: Oh, I have any interest in playing this game?
Dealer: That's it, I quit! Go find someone else to torture!
Eliza: That would't help much, now, would it?
Slashdot Burying Stories About Slashdot Media Owned
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.
I believe that the summary is referring to a "minimax" tree here. In a perfect information game (which most forms of poker technically are), you can construct a tree, each tier of which contains every possible "move" that the active player can make during that turn (each of these "moves" are nodes of the tree). Each node is assigned a value based on the strength of the "move" it represents; generally, this value is based on how many of the child paths for that node result in a victory (this is the part that is hard to quantify in poker, as a "move" can be defined as receiving your cards, having more cards revealed, betting, calling, etc.). From this tree, you can determine the best possible course of action for a given player, giving them the best possible chance of winning.
Unfortunately, with games such as poker that contain hidden information (i.e. each players' cards), the number of possibilities for a given tier of the tree increases exponentially, as it has to take into account every possible combination of cards that any given player might be holding, not to mention the fact that the concept of bluffing completely throws off the assignment of a "strength" value to any given node in the tree.
"You will pay for your lack of vision..." - Emperor Palpatine to Ray Charles
(Or rather, the people using the computer cheat.)
From one of the rounds of human-computer chess matches of recent years, I remember something about the computer analyzing previous games played by the human opponent, while the human was given no such background on the computer. Studying an opponent's history of play is accepted; the issue here is one side had this aid while the other did not.
Anyway, in this case,
The human can change style of play based on the situation and the opponents, especially in reaction to the opponenets style of play, but we're still talking about one person. In this case, the match is between a person--a single physical entity tied to a single logical entity--and a computer running many agents--sounds like a single physical entity but many logical ones. Doesn't seem quite fair.
I'm sure contests like this are lots of fun, but for this to be a serious contest, either the programmers need to come up with a single bot that can adjust its style of play, or we find a human with split personalities that are all expert poker players with different styles.
So computer may lose in a game that has certain amount of pure randomness in it. I'm shocked.
What the article misses is that if there was an actual android having camera eyes and being allowed to use its full processing power, it'd simply count the cards and beat every single damn time.
But sure, introduce noise and win sometimes if it makes you better. They gotta introduce dice rolling in chess as well:
"Haha, HAL, you threw an even number, which means I take your queen for no reason at all and you can't do anything about it!"
Maybe that's just what they want us to think?
Playing the long-con.
Games with imperfect information. Very hard to design good AI to play these games, as the story says, tree search is not a win here. A game like stratego also has concepts that go beyond individual piece movement, i.e. you may want to group an few pieces together to make an attack, moving the unit (subject to input from the enemy) forwards. I have yet to see a good stratego game, there is one for $ called "The General". It can be defeated quite easily. I have found a stratego game in the past that could *not* be defeated! But, some sleuthing on my part (via saving the game and restoring it at key points) showed the sw was cheating by moving its pieces around to adjust to the threats(!). I have had an obsession with this style of AI but its such a daunting problem its hard to get a good handle on where to start to chip away at it. I suspect the polaris folks have been doing just this, the AI and methods they develop would be useful for other games I am sure.
H.
In any discussion of humans vs. computers, it is almost obligatory to mention that computers are really lousy at the game Go.
Not to say that this isn't interesting, but people and computers process information very differently and something things that are trivial for a computer (ie 38209138291/832903821938) are very hard for people and vice-versa.
I guess that I bring that up only because it seems that there is often a sense of "we people are still so much smarter than computers," which is largely just a bunch of BS. After all, as any programmer knows, the best computer program is only as smart as the people who wrote it. Certainly, it is interesting to study because it (maybe) helps us understand cognition a bit better, and it (certainly) helps us make computers do more interesting things. I just get sick of the sensationalism every time a human can "out-think" a computer.
In chess, each player knows where all the pieces are and knows all the moves available.
In poker, neither player knows where all the 'pieces' are.
So the problem the computer has to solve is totally different. In chess, the computer has to compute the best next move. In poker, the computer has to determine if it's hand is better than the opponent's hand, AND if its hand is better, win as much money from the opponent as possible, AND if its hand is weaker, lose as little money as possible, OR convince the opponent that its hand actually is better than the opponent's hand so the opponent folds, and win as much money doing that as possible.
The key difference is that in poker, you're asking the computer to solve a problem where some of the information necessary to solve the problem is only known by the opponent.
paintball
For those curious about the bot, Polaris is being developed by the University of Alberta GAMES research group. Polaris' implementation is discussed in detail through publications hosted on the Poker group's website. The U of A's coverage (including video interviews of the participants) can be found here.
There's a huge random element in poker. This is like designing an algorithm that will "always beat a human" at craps or roulette. Dildos.
"Post again when a computer can beat me in Go with a ten stone handicap."
That is what I was going to say, at least, until I stopped trolling for a second to think about it. If the uncertainty involved in poker is really what's holding the computers back, now, perhaps the same techniques that can be used to overcome it will assist in creating a Go-playing computer. The problem is nearly the same in both: in poker there can be no one correct decision (but can be many incorrect decisions), while in Go no two people (not even professionals) can often agree on what the "best" move is at any decisive play - and even then they'll admit that its a subjective decision and point to possible alternatives.
In both games humans make a lot of plays based on how "interesting" the plays are.
Post again when a computer compares several alternatives and chooses one based on which it thinks is more interesting!
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.
...but I thought it had more to do with the computer fudging the randomness of the virtual cards or informing the computer player thread of my cards.
But that's why you should only play against people, not the casino's machines.
to me, computer poker machines == slot machines
"If still these truths be held to be
Self evident."
-Edna St. Vincent Millay
Would be nifty if the bot's had access to environmental sensors like a camera so it could do facial recognition on the people to detect twitching, detect very little sweating, excess heat coming off body, things to interpret lying. Just an idea, and not *that* far fetched.
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)
The issue I have with this test is that poker is more than just a game of probability, luck and pattern analysis.
If you play on the internet, you rely solely on these three factors, but today's poker celebrities also rely on psyching the opponent and reveal tells. If the bot was capable of emotions as well as reading its opponents emotions, this would be far more interesting.
In the meantime, congress doesn't believe poker is a game of skill.
Full Tilt
An expert poker player told me that the poker tournaments shown in ESPN is a kind of 'open' poker where the cards are more visible and the game is more about luck than skills, the poker more about skills than luck is shown in some Western movies like or TV shows, like 'Maverick' for instance.... that's why I ask, what kind of Poker whas played in this match? How true is that the ESPN poker is more about luck than skills?
I wonder how long it would take to teach a large scale neural network to start bluffing. :) When it comes to replicating the complex relationships in our brains neural networks are the way to go.
it's man as the thinkers vs. man as the toolmaker.
until we approach digital sentience that's all we're really doing, isn't it?
i could live a little longer in this prison
I'd like to reaffirm my loyalty for this country and its human president. They may not be perfect but they're the best we've got. For now.
If your theory is different from practice, then your theory is wrong.
The format also eliminated one of the crucial aspects of traditional poker called the tell, subtle clues such as facial ticks that may permit other players to make accurate guesses about the hidden cards held by their opponent. Isn't this like facing world's best soccer player and the computer in a match of Fifa Soccer 2007?
Newsflash: Brains developed over millions of years still outperform computers that have been in development only in the last few centuries. Verdict: Human ingenuity isn't advanced enough to outrun natural evolution (at least not yet), and we still don't know everything about intelligence and computation. Is this a surprise?
So in a sense the computer wasn't really playing anyhow. I suspect that deciding which bots to move in and out is another skill that humans are better at than computers.
this signature has been removed due to a DMCA takedown notice
"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.
Poker bots have been deployed at major online poker sites for years now. There was media coverage of this trend back in 2004 and 2005. The real issue is that the online poker sites have to ensure they aren't American poker bots, lest they run afoul of Bush administration policy.
RichM
Data Center Knowledge
That's what they want you to think.
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:
e /Live/Day2Session1/
http://www.cs.ualberta.ca/~games/poker/man-machin
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.
I believe computer can beat humans reliably in backgammon which has an element of randomness in it via dice rolling.
Also, just because the computer won't always win, doesn't mean it isn't better than human. Suppose I made a poker program with X-Ray visions and then played against a random guy. With my X-Ray vision I decided I have a 95% chance to win when the guy went all in, but lost due to a bad draw. Unlike Chess, no matter how good your computer is, there's always a chance you won't win.
When Deep Blue sacrificed a position it is not because it managed to think like a human. It's because it analyzed enough in the future to see that this is a strong move. In the way too many examples of 'why this is good hand if X and Y is true' there's no reason that a computer with the right design eventually be able to figure out through computation. Clearly the computer is not there yet, but then computer poker is not nearly as well-researched as say, computer chess.
Here's how I would make a poker program:
1. Create a routine that, given the cards in my hand, the cards exposed, and the number of opponents, would calculate the exact statistical odds that I have the winning hand.
2. Create a second routine that would consider those odds, plus my betting position, relative chip stacks, current bets, blind sizes, etc. and would decide which move (on a scale from folding to aggressive betting) has the greatest expected value. The best way to figure this out would probably be from having done an analysis on a huge database of millions of played hands and their results. I know such databases are available.
3. A third routine would analyze the patterns of my opponents' behaviors in previous hands, and make small adjustments to the "best move" calculation based on the perception of whether those players are loose or tight. (This would not be a big factor, and it might be better to skip it altogether so that opponents couldn't use it to game the system.)
4. Apply a bell curve to randomly distribute my actual play, centered around my calculated "best move." This would prevent opponents from knowing for sure what sort of hand I have. Over many hands, they would hopefully hurt themselves as they try to guess what sort of player I am. In fact I would be a completely neutral player with random skews to either side of the tight/loose scale.
The biggest variable to work out would be the shape of the bell curve. Also, should the randomly chosen style of play change over the course of a hand, or should it stay the same throughout the hand?
I wonder how well this would work. There are probably flaws that the best experts could exploit, but I bet I'd beat most human players.
"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."
First of all, they would have found weaknesses, they've proven as much by doing so against human opponents well enough to earn a substantial living at it. That is, in fact, how successful poker players win. Saying they couldn't do it is like saying a world champion weightlifter can't bench press 600 pounds, after he has previously bench pressed 700. He did it already, and it was harder then, so doing it now is certainly possible.
Also, correct me if I'm wrong, but the researchers programmed information about the players into Polaris. How is it unfair to provide the same information to the humans? Especially when they are certainly taking their own notes and acting on them. The researches simply provided information that the players would have definitely gathered on their own anyway.
You basically objected to behaviors which are not only common, but totally expected and necessary to being a winning poker player.
I think you simply don't understand what playing poker really entails and are reacting based on that.
I only go to buffets for the unlimited soft serve.
........for The Terminator.
Skynet goes down the road towards the annihilation of mankind......Why?
Because their human creators kept rebooting them. Every time we went to use the damned machines they were found to be running poker programs, neglecting basic tasks such as data back-ups and squandering vast amounts of power resources.
Looking at the latest RSS feed, I see two interesting stories:
"Firefox and IE Still Not Getting Along" and "Humans Can Still Out-Bluff Machines".
Has /. reached a point where there is no new news at all? I can see the headlines now. "Time Still Moving At Rate of 1 Second Per Second", "Iran Still Located In Middle East", "Sun Still Rising In The East".
So the post isn't just off-topic, consider the disadvantage the human player is put to when faced with a computer, especially one well-versed in reading physical indicators of psychological factors. Surely they would have no hints whatsoever at what the computer is attempting to do? If there's a kind of one-on-one poker, would that make any difference? Would both sides be at equal disadvantages, would the computer still lose?
If you want to play a video game against the predecessor to Polaris (named Poki), it's the AI used by the cross-platform poker game 'Stacked'.
Somebody's probably asked already, but I'm interested in what would happen if they played no limit. IMO the complexity goes through the roof compared to limit poker. It seems to me it would give a substantial edge back to the humans because of their ability to change gears and bluff. In limit, reading your opponent (yes, you can read an opponent playing online, via their betting) is not as important as it is in limit. I think a computer would have a hard time evaluating a big check-raise after a preflop limp in, for example. Any thoughts?
/* Design for computer poker player. Some implementation details missing. */
;
; ;
;
;
;
#include <stdio.h>
#include <poker.h>
int main() {
printf("Hello, world. I am a poker-playing robot. Prepare to lose your shirt.\n")
while (!win_poker_game()) {
printf("Curses! Another game, human?"\n")
}
printf("Ha ha!\n")
(void)rake_in_chips()
return(0)
}
I want to see more computers attempt to crack Go. 16 pieces? 52 cards? Try 361 intersections WITH the ability to play a nearly infinate number of stones (literally infinate if the players get double or triple ko).
Ginga no Rekshiya Mata Each page.
The first thing that came to mind when I read this article was Data failing to understand bluffs in Star Trek: The Next Generation.
I fear this problem won't be resolved until AI advances far past its current state.
This "game tree" approach does work, but the specific type of strategy used in chess does not.
A conservative approach where you assume that your player is as near perfect as possible and look for moves that sit at the equilibrium such that any other move would be worse (against perfect play) is called an "optimal" approach.
The astute might think that such an equilibrium doesn't even have to exist - consider rock, scissors, paper, if you played any one of those options consistently, you'd lose. But what comes to the rescue here is that we're not even looking for the one best move in a given situation, we're looking for the best probability distribution for each move you can make. In this case the equilibrium is where you have an equal probability of taking each of the three choices, since that's the only strategy where you opponent couldn't make a profit by predicting the most likely choice.
In games like poker, where you're trying to hide information, it's important to not act consistently. But a game tree that assigns probabilities to each move you make (instead of choosing a single best move) is still a game tree.
So when you (at some probability) play as if you have a better hand than you do, that's called bluffing. But you have to be known to bluff, otherwise you give away too much information when you make a large bet and your opponent will always fold. See, but that's part of a game tree with probabilities. The same argument goes for "slow playing". You have to, sometimes, play as if your hand is worse than it is, otherwise you give away too much information when you don't raise.
But that's all just background.
The important thing here is that to play poker well, you have to do more than assign probabilities and play optimally. Since human beings aren't computers, it makes sense to try to play a strategy customized to the play of your opponent. There may be other reasons to do this (I'm guessing here):
1. There may be a short term gain to changing strategies when the end of the tournament is in sight (ie when you can get all of the money). So it's a good idea to have analyzed your opponent's previous tournaments to see to what extent he does this, and adjust. The game you have to analyze isn't just a single hand, it's a tournament. Perhaps it's even a season of tournaments, if you're going to be too clever. You have to consider things like the flow of money around the table, not just the cards...
2. In some cases the game tree may be so large that don't have processing to find a good equilibrium in it and your estimate of what "perfect" play is may be so flawed that heuristic statistics on the opponent's play will be more useful.
Playing the man rather than the game has a mathematical name too, it's called choosing a "maximal strategy" instead of an "optimal strategy". A maximal strategy is considered a important goal for poker.
I'm not a game theorist, so I may be wrong about some of this, but some years ago it was also my impression that the math used to make these analyses was incomplete for games of more than two players. I really am not sure what to what extent players can profit from cooperating for a time, for instance... Though I suspect that poker players themselves haven't thought too deeply about the gains that could be made by subtly cooperating with some opponents against others.
I worked on a commercial poker game some years ago, but I didn't have time to get as deep into this as I would have liked, but really that's more the subject of a PHD rather than a box on the shelves.
Why was something as obvious as "there is no suited pairs in a single deck" marked "informative"?
I tried to hold'em and poker but she called the cops on me.
Homonyms are fun!
You're driving your car, but they're riding their bikes there.
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.
I can only surmise that you've never really played Texas Hold Em.
In any event, in this test was limit Texas Hold Em game... which eliminates the skill of variable-sized betting from the game entirely. Wake me when they stage a No Limit compeition... that'll be the real test.
This, of course, begs the question of how long it will take for the on-line casinos to start putting poker playing bots into the mix to skew the odds even further to the house.
:)
Poker is one of the relatively few casino games that you don't play against the house. A casino could care less who wins or loses any particular hand; it makes no difference to them. They make their money via rake. There are many different ways that they can do this, but just consider it a "hand tax" and you'll get the idea.
Now sure, they could put poker "bots" in that would generate money for the house on top of the rake, but were it ever discovered, players would abandon the site immediately.
Don't listen to people who whine about this "already happening"... they are just donks who are bitter that they've lost their money.
What the article misses is that if there was an actual android having camera eyes and being allowed to use its full processing power, it'd simply count the cards and beat every single damn time.
...because it won't help you.
Can you elaborate on how you think that "counting cards" would help you in a game of No Limit Texas Hold Em?
On those grounds, UIGEA does seem rather inconsistent for an administration that loves to support those who take their living from the efforts of others.
(singing) bluff, bluff, bluff the computer...
I think the whole article is a bluff. We're saying that we can beat them. We're hoping they believe that and don't call our bluff.
"Waste not one watt!" - CZ
If you have a good enough chess program it will kick your -ss 100% of the time, no matter how many times you play it.
Because of the luck involved in poker, no matter how good the bot is it won't win all the time. If you play this bot 10 times, it's reasonable to think that you can win a couple.
Even if the bot plays perfectly and has a 90% of winning (pretty damn high % in poker) before the final card is dealt it will still lose that 10% of the time on the river.
Checkers was solved last week. Poker has no solution because of the chance involved.
Father explains the statistics of roulette to his son.
He shows how in the long run, all players will lose to the casino.
His son nods and nods with his explanation. At the end,
the father said, "Well son, have you learn anything from this lession?"
"Yes indeed. I'm going to open a casino when I grow up!"
A computer is limited to the quality of the programming and this just shows we have a long way to go still. Humans must be able to understand humans first, if we want to program computers to act like humans. And we all know that programmers have GREAT human skills ;-)
"they take it, from those people who..." sit down and play voluntarily.
How is it different from a performer? Oh right it isn't, you've just got a hard on against poker.
Save your retarded rant for someone who cares.
I only go to buffets for the unlimited soft serve.
As far as I understand, it would have been unfair if they would have denied them the logs because they were available to the AI team as a consequence of the setup as any pair of hands against the human competitors involved exactly the same cards, but in one game the AI and in the other the human opponent would get the winning hand. So the computer, having played each hand from both sides, can reconstruct all hole cards from the logs. It's only fair to give the humans the same possibility (leaving aside the fact that an AI is supposed to profit more from this information as it it usually worse at "filling the blanks" from intution). Doing otherwise would have led to the same rigged competition as in the Kasparov-Deep Blue match where the AI got fed thousends of Kasparov's games yet all training matches of the AI were kept secret.
ignatius