Game Theory and Poker

pkr_ennis · 30-12-2009 2:14pm #1

Howdy

I've recently become interested in Game Theory in relation to poker, and was wondering if anyone here studies this or something close to it. I've been watching videos on running gambit, and would be interested in some discussion on the topic.
C

gerry87 · 30-12-2009 5:26pm

pkr_ennis wrote: »

Howdy
I've recently become interested in Game Theory in relation to poker, and was wondering if anyone here studies this or something close to it. I've been watching videos on running gambit, and would be interested in some discussion on the topic.
C

What sort of stuff are you interested in, ring games/tournaments? You probably came across him already, but if not look for books by David Slansky.

pkr_ennis · 30-12-2009 5:38pm

I know David Sklansky thanks.

There really aren't any hard facts and figures in his books. I was looking to discuss actual game trees and how the results there relate to poker startegy.
FYI there's a good book on the subject "Mathematics of poker" bill chen and another guy I forgot the name of.

fergalr · 31-12-2009 12:04am

pkr_ennis wrote: »

I know David Sklansky thanks.

There really aren't any hard facts and figures in his books. I was looking to discuss actual game trees and how the results there relate to poker startegy.
FYI there's a good book on the subject "Mathematics of poker" bill chen and another guy I forgot the name of.

Hey there,

I'd be interested in this subject too.

I'm not much of a poker player. I read Dan Harringtons books, and Slansky, but I've only played a little casually.

I was reading a book recently called 'the logic of life'. Its a popular science economics book by Tim Harford. In it he talks about Chris ('Jesus') Ferguson using game theory to conduct analysis (monte carlo based? - he doesnt say) of poker playing technique, which he used to discover some insights about flaws in pro level play (afair something about the pros raising too much post flop with good hands to push out opposition, avoiding showdown).

I'd be very curious to know what sort of a form this analysis would have taken. How would he go about doing this? Casually googling for it, I find plenty of people saying that Ferguson knows lots about game theory, but little in the way of detail! I'd almost think it was just part of the mystique, if I hadn't read it in a reputable book.

I was interested in games when I did my CS undergrad, and just did a course on ai for games recently (minimax, AB, various tree search strategies). We had some lectures on poker, but they were didn't go into huge detail, and wasn't really GT based. (The slides for the lecture are here: http://www.csi.ucd.ie/Staff/acater/2009/comp30260/30260_L16.pdf I'm going to hope that as they are publicly accessible the lecturer (whos a decent guy) won't mind me linking).

I don't know a huge amount of game theory (read a bit of a book by Gibbons) but would like to know more about what sort of approach someone would use for poker.

On a separate, but related, topic, I was at a talk by a guy called Bruce Bueno de Mesquita where he talked about applying game theory to make real world political predictions. It didn't go into technical detail on the models he used. I'd be very interested if anyone knew of details or resources on how to go about applying game theory techniques to real world problems - implementation details on the techniques used.

pkr_ennis · 31-12-2009 11:46am

fergalr wrote: »

I was reading a book recently called 'the logic of life'. Its a popular science economics book by Tim Harford. In it he talks about Chris ('Jesus') Ferguson using game theory to conduct analysis (monte carlo based? - he doesnt say) of poker playing technique, which he used to discover some insights about flaws in pro level play (afair something about the pros raising too much post flop with good hands to push out opposition, avoiding showdown).

I'd be very curious to know what sort of a form this analysis would have taken. How would he go about doing this? Casually googling for it, I find plenty of people saying that Ferguson knows lots about game theory, but little in the way of detail! I'd almost think it was just part of the mystique, if I hadn't read it in a reputable book.

I don't know a huge amount of game theory (read a bit of a book by Gibbons) but would like to know more about what sort of approach someone would use for poker.

Chris Ferguson is one of the best poker players in the world. He was World Champion in 1999 I think. He uses GT for all his decisions. He says he never uses 'tells', which are physical givaways to the strength of a players hand, that had become a large part of the best pro's strategies. They had some Math down but it was mostly psycological based poker, and still is today, even in the biggest public game.

Now everyone is starting to use GT. What they are doing is making models of poker situations and figuring optimal play using Nash's Equilibrium and then skewing the results in relation to a playing style or a particular player's tendencies to create the best possible EV decisions.Seemingly these formula's can take pages of algebra to figure out.

Online poker has many pro players using GT. These are some of the biggest winners in the game. Ferguson said the poker world now, is like 1900 america when everyone was happy with the horse and carrige, but Henry Ford was clincking away in his garage trying to perfect his machine.

He's saying that the fututre of poker is going down this route and I wanna be a part of that. I've recently watched some training videos on using a programe called 'gambit' which it was shown to create optimal solutions to simple games, but I'm not an expert with numbers and am struggling to even construct a tree there. However, I am good at poker strategy.
C

cavedave · 31-12-2009 1:40pm

Total poker has a chapter on game theory that really only deals with the cuban missile crisis. Still it is worth a read.

RoundTower · 31-12-2009 6:48pm

here's a simple poker game. If you have studied some basic game theory, you can solve this problem.

we play with a 3-card deck. Ace beats King beats Queen.

We both put in 1 euro to the pot. You act first and your choices are to bet nothing or bet 1 euro.

If you check (bet nothing), your opponent checks too. Whoever has the best hand wins the pot of €2.

Your opponent's choices are to call the bet or fold. If he folds, you win the pot. If he calls, he puts in €1 and whoever has the best hand wins the pot of €4.

What is the equilibrium ("optimal") strategy for this game? How much money do you win (or lose) each hand if both players play the optimal strategy? How, if at all, would you change your strategy if you knew your opponent was not following his optimal strategy? Once you can answer these questions precisely, you can attempt to generalise it to a more complicated poker game.

gerry87 · 01-01-2010 7:06pm

The trouble with the poker/game theory connection is that it starts to break down pretty rapidly when you start to relax assumptions.

Most gt problems assume all agents are rational and have equal/perfect knowledge of game theory.

I remember a discussion over in the poker forum ages ago about one of the game theory problems. The Travellers Dilemmait was essentially this:

You and a friend traveling on an airline, each with a vase (the only two of their type in the world). The airline looses both and comes to each of you separately asking how much it was worth to refund you. The rules were,
1) Max price 100.
2) Min price 2.
3) If you say the same value of your friend you both get that amount.
4) Whoever says the lower price gets that price +1 and whoever says the higher price gets the low price -1.

Game theory has a logical 'right' answer (Nash Equilibrium is 2). But almost nobody in the poker forum answered that, even after taking a few steps along the GT way of thinking most said 99 or 98.

If game theory could work for poker you probably need to have some idea of the utility of your opponents (even just the average player you find at whatever level). Even that changes between hands, like what stage of a tournament they're at.

Edit: Does anyone know how many permutations of actions there are in say a round of limit poker? For the sake of how many branches would be on a decision tree.

fergalr · 01-01-2010 7:10pm

RoundTower wrote: »

here's a simple poker game. If you have studied some basic game theory, you can solve this problem.

we play with a 3-card deck. Ace beats King beats Queen.

We both put in 1 euro to the pot. You act first and your choices are to bet nothing or bet 1 euro.

If you check (bet nothing), your opponent checks too. Whoever has the best hand wins the pot of €2.

Your opponent's choices are to call the bet or fold. If he folds, you win the pot. If he calls, he puts in €1 and whoever has the best hand wins the pot of €4.

What is the equilibrium ("optimal") strategy for this game? How much money do you win (or lose) each hand if both players play the optimal strategy? How, if at all, would you change your strategy if you knew your opponent was not following his optimal strategy? Once you can answer these questions precisely, you can attempt to generalise it to a more complicated poker game.

Roundtower:
I'd be interested to know how to go about the analysis of this game.
Like I said, I only know what I do about game theory from reading a bit of a book. (the games we saw doing the AI course were of perfect information, so it was mostly about minimax and search)

Could you clarify a few things about the setup?

* I presume players get dealt one card each, and can't see what the remaining card in the deck is.
* Are the players' cards dealt face up or face down?
I'm assuming that each players cards are dealt so that only the player can see them (like the hole cards in holdem)

In your setup, you've removed the second players ability to decide anything in the event that the first player checks.
This would seem to make the payoffs of checking for player 1 to be 1 for an ace, 0 for a king, and -1 for a queen. If the first player can't see their card, I guess that makes the payoff/ev for checking blind to be 0 - fair enough, thats pretty obvious.

Working it out what happens when the first player raises is a little trickier though.
If the first player can see their card, then whether the player raises or checks gives the second player some information. The fact that the first player acts first, but the second player doesn't know what the first players hole card is after the action, while the first player does, makes it a dynamic game of imperfect information.
I'd need to read up on this a little before I'd be able to figure out what the value is. Am I looking to find the perfect bayesian equilibrium here - if its a dynamic game of imperfect info and you are talking about an equilibrium, I presume thats what you mean?

Am I on the right track, or have I seen it as more complex than it is, or did you mean it to be the simpler case where the cards are dealt face up?

fergalr · 01-01-2010 7:37pm

gerry87 wrote: »

Edit: Does anyone know how many permutations of actions there are in say a round of limit poker? For the sake of how many branches would be on a decision tree.

I think you are asking about the branching factor of a poker game here, right? How many unique choices there are at each 'ply' or move in the game?
I guess that for limit poker, its actually quite small in terms of the actions available to each player. I'd say NL poker could also be suitably 'discretised' into a relatively small number actions at each ply. Certainly compared to something like Go, or even chess.

But I would guess that where the computational complexity would occur in doing some sort of search through the outcomes isn't in the number of actions available to each player at each turn - its in the number of actions available to nature (ie chance) as each extra card comes down - that's probably what increases the complexity a lot.

In other words, a players may have only a small number of actions each (say, check, fold, bet) but then the flop comes and you draw 3 cards from 50 unknowns and the branching factor shoots up - so trying to calculate the potential outcomes of a giving action must get complex computationally.

(Haven't really thought about this, but thats what I'd guess the problem is)

Edit: when you say a 'round of poker' I'm assuming you mean a hand, rather than a round of betting, or round in a tournament etc

pkr_ennis · 01-01-2010 7:38pm

RoundTower wrote: »

here's a simple poker game. If you have studied some basic game theory, you can solve this problem.

we play with a 3-card deck. Ace beats King beats Queen.

We both put in 1 euro to the pot. You act first and your choices are to bet nothing or bet 1 euro.

If you check (bet nothing), your opponent checks too. Whoever has the best hand wins the pot of €2.

Your opponent's choices are to call the bet or fold. If he folds, you win the pot. If he calls, he puts in €1 and whoever has the best hand wins the pot of €4.

What is the equilibrium ("optimal") strategy for this game? How much money do you win (or lose) each hand if both players play the optimal strategy? How, if at all, would you change your strategy if you knew your opponent was not following his optimal strategy? Once you can answer these questions precisely, you can attempt to generalise it to a more complicated poker game.

I have zero experience working out gt solutions, however I have watched several instructional videos using the programme gambit. You build the trees and press compute 1 nash equilibirum and hey presto you get an answer.
I am having trouble working the software and haven't got it down yet. I've posted questions about it on the stox poker forums which is where I viewed the vids and hope to be working this software soon. I tried to solve the game posted here, but I suspect I've something done wrong e.g. the answer I got never bluffs and only value bets half the time with the nuts.

GT and poker mix perfectly because we can get perfect information on our opponents through a poker tracking app. Therefore being able to derive exact solutions vs a range of different opponents or their tendencies.

pkr_ennis · 01-01-2010 7:42pm

fergalr wrote: »

Could you clarify a few things about the setup?

* I presume players get dealt one card each, and can't see what the remaining card in the deck is.
* Are the players' cards dealt face up or face down?
I'm assuming that each players cards are dealt so that only the player can see them (like the hole cards in holdem)

I saw this problem before and those assumptions are correct.

pkr_ennis · 01-01-2010 7:55pm

fergalr wrote: »

Edit: when you say a 'round of poker' I'm assuming you mean a hand, rather than a round of betting, or round in a tournament etc

They mean a round of betting.
Are you asking how many decision points there would be in a round of betting in Limit Hold'em poker?
Lots and lots is the answer to that question. I mean there would be 1 infinite branch, if they had never ending stacks and kept re-raising each other.
Each player has 3 options once a bet has been placed or 2 options if facing no action. If player b re-opens the betting after player a's initial bet then this would be another 3 options player a is faced with. If they only had enough chips for 1 bet on each street the model would be smaller.

fergalr · 01-01-2010 8:25pm

pkr_ennis wrote: »

They mean a round of betting.
Are you asking how many decision points there would be in a round of betting in Limit Hold'em poker?
Lots and lots is the answer to that question. I mean there would be 1 infinite branch, if they had never ending stacks and kept re-raising each other.
Each player has 3 options once a bet has been placed or 2 options if facing no action. If player b re-opens the betting after player a's initial bet then this would be another 3 options player a is faced with. If they only had enough chips for 1 bet on each street the model would be smaller.

Just had a quick read of this paper:
http://www.cs.cmu.edu/~sandholm/tartanian.AAMAS08.pdf
which is extremely interesting, and deals with a lot of these issues.

They are only talking about a heads up poker player which is obviously a much simpler game, but its interesting to see what they've done.

They quote a size of 10^18 nodes for the game tree for limit poker, which might answer gerry87s earlier question about the search space. I presume from the context they mean heads up poker, but its not crystal clear to me from the context. Either way, its a lot of nodes.

They do some interesting things to cut the tree size down a bit.
Firstly, they do in fact discretise the NL bets into a much smaller space of actions, to cut down the search space. That's quite interesting. Their discretisation makes sense to me, but I'm not a very good poker player - interesting to hear what others think of it. Most poker books I've read have typically mentioned only a few separate bet sizes (typically expressed as a fraction of the pot) anyway (maybe we some random noise thrown in).

The next thing they did which I thought was interesting was look for strategic symmetries in the space of cards that can be dealt, to cut down the size of natures moves that have to be considered distinctly. Thats quite interesting, be interested to read more about how they did that. They used a lossy version as well to cut the space down, grouping together similar cards using a k-means clustering (standard machine learning way of grouping together similar items). Cool stuff.

Then they use some autogenerated c++ code to calculate nash equilibrium for the imperfect game. Have to say, didn't understand that part of the paper, same thing thats stopping me from solving round towers problem, haven't seen equilibrium models for dynamic imperfect info games. Have to read up on that - anyone recommend a good tutorial?

fergalr · 01-01-2010 8:53pm

gerry87 wrote: »

The trouble with the poker/game theory connection is that it starts to break down pretty rapidly when you start to relax assumptions.

Most gt problems assume all agents are rational and have equal/perfect knowledge of game theory.

I remember a discussion over in the poker forum ages ago about one of the game theory problems. The Travellers Dilemmait was essentially this:

You and a friend traveling on an airline, each with a vase (the only two of their type in the world). The airline looses both and comes to each of you separately asking how much it was worth to refund you. The rules were,
1) Max price 100.
2) Min price 2.
3) If you say the same value of your friend you both get that amount.
4) Whoever says the lower price gets that price +1 and whoever says the higher price gets the low price -1.

Game theory has a logical 'right' answer (Nash Equilibrium is 2). But almost nobody in the poker forum answered that, even after taking a few steps along the GT way of thinking most said 99 or 98.

I know that the relevance of game theory to real life is something people argue back and forth over.

I would note though that the game you gave isn't a zero sum game. I think (perhaps without much justification) that GT results seem to me to make more real life sense when the game is zero sum.

I also think our intuition is also different from the GT results because in real life such interactions or 'games' rarely occur in a once off situation where you'll never see the other actors again. A lot of the time we only look at a single stage in a complex game and apply GT to it, ignoring the larger context which typically involves iteration or reputation which changes things a lot.

For example, while the 'correct' thing to do in a prisoners dilemma from a GT point of view is to both defect (betray the other prisoner) this conflicts with most peoples real life intuition, which is much closer to the iterated game solution - probably because if one prisoner betrayed the other in a similar real life situation there would be later reprisals of some sort - we are conditioned to assume that word will get out of the actions and to act more like its always an iterated game.

gerry87 · 01-01-2010 9:06pm

10^18 does seem a lot for heads up if it means what i think it does. Small blind folds (first outcome). Small blind calls, big blind folds (second outcome). Small blind raises... etc could there be 10^18 outcomes? Am i getting this wrong? Is it be taking into account the variations in cards as well?

I'd say no-limit would probably be even less than this, that seems to be what they're going on with the betting model.

Just skimmed, but seems interesting. Wonder if they ever put those bots into action.

fergalr · 01-01-2010 9:27pm

gerry87 wrote: »

10^18 does seem a lot for heads up if it means what i think it does. Small blind folds (first outcome). Small blind calls, big blind folds (second outcome). Small blind raises... etc could there be 10^18 outcomes? Am i getting this wrong? Is it be taking into account the variations in cards as well?

I dont know what exactly the number refers to - they don't say, nor do they seem to give a reference.

I presume they are taking into account the variations in the cards.
Perhaps they are also considering the situation where players keep reraising each other until they've exhausted their stacks (something they deal with later in their betting model by capping the number of repeated bets to 3 - on the basis that this is more than would occur in practice the vast majority of times anyway).

gerry87 wrote: »

I'd say no-limit would probably be even less than this, that seems to be what they're going on with the betting model.

Just skimmed, but seems interesting. Wonder if they ever put those bots into action.

Hah - I'd say that's the question on everyone's mind :-)
I'm sure they wouldn't be adverse to running it as a bot if they could - came across another instance where they said that they had built something that played one of the party poker games very well (near optimally), but the game structure was altered before they could make money - hmm! That would imply they actually went through the hassle of wiring it up to party poker (screen scraping or something similar - I presume there isn't an exposed api ! )

I'd wonder how good a bot would actually need to be before it could start making a profit on the small stakes cash tables - probably wouldn't need to even be that smart. You mightn't even need to do such sophisticated GT analysis to produce a bot with positive expectation for easier games - simpler learning approaches might work etc - I've no idea whats out there, but I'm sure a lot of people have put time and effort into it.
With the level of analysis thats in the published work I've come across in a quick google, it'd make me quite wary about what might be out there.

gerry87 · 01-01-2010 11:39pm

fergalr wrote: »

I dont know what exactly the number refers to - they don't say, nor do they seem to give a reference.

I presume they are taking into account the variations in the cards.
Perhaps they are also considering the situation where players keep reraising each other until they've exhausted their stacks (something they deal with later in their betting model by capping the number of repeated bets to 3 - on the basis that this is more than would occur in practice the vast majority of times anyway).

Hah - I'd say that's the question on everyone's mind :-)
I'm sure they wouldn't be adverse to running it as a bot if they could - came across another instance where they said that they had built something that played one of the party poker games very well (near optimally), but the game structure was altered before they could make money - hmm! That would imply they actually went through the hassle of wiring it up to party poker (screen scraping or something similar - I presume there isn't an exposed api ! )

I'd wonder how good a bot would actually need to be before it could start making a profit on the small stakes cash tables - probably wouldn't need to even be that smart. You mightn't even need to do such sophisticated GT analysis to produce a bot with positive expectation for easier games - simpler learning approaches might work etc - I've no idea whats out there, but I'm sure a lot of people have put time and effort into it.
With the level of analysis thats in the published work I've come across in a quick google, it'd make me quite wary about what might be out there.

On micro-limits a basic strategy would probably do alright.

if (Aces or Kings)
    All-Inski
else
    Check/Fold

Wonder if a tournament bot would be easier, if you just made it play tight premium hands until its in the money, then hand it over to you... sure its basically how i play.

Think we're getting away from OP's topic a little!

pkr_ennis · 02-01-2010 12:51am

gerry87 wrote: »

Think we're getting away from OP's topic a little!

Not at all. I just wish I was up on all this math stuff. From what I understand of bots and the sort, it's obvious there has to be some profitable activity, especially in the small stakes, but poker sites have software to catch them out so I think their activity has been limited for a while, although some of the top minds have to be doing this. It's money for nothing, well almost. There are bots that can almost beat top proffesional players. I heard there is a school in Canada that has the best, it had several matches at the WSOP with top pro's and beat at least 1 of them. Here's a link to some chat and the like.
http://www.stoxpoker.com/blogentry_more.php?blogid=3740&langid=1&memberblog=#MORE
By the way, playing just aces and kings is obv a terrible strategy as you'll get pwned over over by the man who has the GT down and knows your super tight tendencies lol.

gerry87 · 02-01-2010 2:03am

pkr_ennis wrote: »

Not at all. I just wish I was up on all this math stuff. From what I understand of bots and the sort, it's obvious there has to be some profitable activity, especially in the small stakes, but poker sites have software to catch them out so I think their activity has been limited for a while, although some of the top minds have to be doing this. It's money for nothing, well almost. There are bots that can almost beat top proffesional players. I heard there is a school in Canada that has the best, it had several matches at the WSOP with top pro's and beat at least 1 of them. Here's a link to some chat and the like.
http://www.stoxpoker.com/blogentry_more.php?blogid=3740&langid=1&memberblog=#MORE
By the way, playing just aces and kings is obv a terrible strategy as you'll get pwned over over by the man who has the GT down and knows your super tight tendencies lol.

For aces you'd need about 40 big blinds in the pot whenever you hit, so its probably not ideal, still more likely to happen at microstakes, at .01/.02 its only 80cent!

At .01/.02 you aren't likely to come across folk that have thought about game theory! Generally people either won't notice or won't stay at the table long enough to notice. The rake might eat you up tho. As fergal said, a simple expected value game might work but not at the higher stakes.

I'm sure you'd have to throw a random element into the algo to stop them picking up, i've heard them banning people for things like not taking any breaks for 24+ hours straight.

But as you say clearly the amount of research people put into this, there's probably a little more too it. But... i've got a great idea for a roulette bot!

pkr_ennis · 02-01-2010 2:19am

gerry87 wrote: »

For aces you'd need about 40 big blinds in the pot whenever you hit, so its probably not ideal, still more likely to happen at microstakes, at .01/.02 its only 80cent!

At .01/.02 you aren't likely to come across folk that have thought about game theory! Generally people either won't notice or won't stay at the table long enough to notice. The rake might eat you up tho. As fergal said, a simple expected value game might work but not at the higher stakes.

I'm sure you'd have to throw a random element into the algo to stop them picking up, i've heard them banning people for things like not taking any breaks for 24+ hours straight.

But as you say clearly the amount of research people put into this, there's probably a little more too it. But... i've got a great idea for a roulette bot!

I guess there is a good chance to beat those micro games. As you said there is no-one watching how well the other is playing.

Roulette bot is not gonna work as the game isn't zero sum, and the outcome is completely random. A backgammon bot is easy I imagine as there is a programme that plays the game perfectly.

Bots are against the rules of the game so. . .

RoundTower · 02-01-2010 2:35am

fergalr wrote: »

Roundtower:
I'd be interested to know how to go about the analysis of this game.
Like I said, I only know what I do about game theory from reading a bit of a book. (the games we saw doing the AI course were of perfect information, so it was mostly about minimax and search)

Could you clarify a few things about the setup?

* I presume players get dealt one card each, and can't see what the remaining card in the deck is.
* Are the players' cards dealt face up or face down?
I'm assuming that each players cards are dealt so that only the player can see them (like the hole cards in holdem)

yes you are right in your assumptions. there is no complicated number-crunching involved, you should need a pen and paper at most.

fergalr · 02-01-2010 2:51am

pkr_ennis wrote: »

Not at all. I just wish I was up on all this math stuff. From what I understand of bots and the sort, it's obvious there has to be some profitable activity, especially in the small stakes, but poker sites have software to catch them out so I think their activity has been limited for a while, although some of the top minds have to be doing this. It's money for nothing, well almost.

I imagine that most of the countermeasures to stop bots involve making it really hard to write something that programmatically plays the game, and making it hard from a software engineering point of view to maintain a working bot.
For example, if you change the client interface subtly but frequently, you'd make it so that a bot based on screen scraping would need constant updating to keep running. You could also make your poker client watch out for other programs that are running while it runs etc, but someone would work around that by running it in a VM. Ultimately though, if you own a poker website, by changing your protocol or client you could probably frustrate someone thats trying to maintain a bot to the point where they'd make their money easier by writing software.
I imagine another thing you could do is simply track the amount of games played by each client - if it exceeds a certain threshold per month, they are probably a bot.

I guess someone running a poker website could do more sophisticated things such as looking for patterns in their players play to look for people that play deterministically, as an attempt to catch bots, but I'd imagine this wouldn't be worth their while - probably easy to write a bot with sufficient randomness to throw this stuff off.

Still, just by making the bot<->game communication awkward enough, changing it frequently enough, and watching to make sure no one plays too many games, you'd probably make the whole exercise less profitable for the bot writers than if they just wrote software for a living.

Or maybe there's a lot of people living large from poker bots, I dunno :-)

pkr_ennis wrote: »

There are bots that can almost beat top proffesional players. I heard there is a school in Canada that has the best, it had several matches at the WSOP with top pro's and beat at least 1 of them.

Are you sure about that? Is this for a limited heads-up game, or for the full game?

Whatever about playing simple strategies, I'd be very surprised to hear poker bots are good enough to beat top pros.
Thats not what I took from the link you gave - and from the stuff I linked to previously, I'd have thought really good poker play was still quite a bit away.

Its a very hard problem to solve. Perfect play for full NL holdem (as opposed to heads up) even hand by hand, sounds like its still well intractable; and even if you have AI thats finding some approximation of hand by hand equilibrium strategies, theres a lot of other hard stuff they would ideally be doing too that a real world player would (such as opponent modelling to maximise the winnings, or strategising about the overall state of the game - reasoning about blinds going up, the changing game of their opponents etc things that its very hard to account for in a bot, and things that might be necessary to be competitive with the best players)

pkr_ennis wrote: »

Here's a link to some chat and the like.
http://www.stoxpoker.com/blogentry_more.php?blogid=3740&langid=1&memberblog=#MORE
By the way, playing just aces and kings is obv a terrible strategy as you'll get pwned over over by the man who has the GT down and knows your super tight tendencies lol.

Well - from what I understand of the game theory approaches as discussed so far, they are more concerned with figuring out what the best mixed strategy is to play - so whats the mathematically soundest thing to do every time - and not so much considering what your opponent does.

I understand the idea of modifying the probabilities of the model on account of the opponents behaviour to exploit your opponent too, but from what I can see, thats a whole other can of worms?

fergalr · 02-01-2010 2:55am

pkr_ennis wrote: »

I guess there is a good chance to beat those micro games. As you said there is no-one watching how well the other is playing.

Roulette bot is not gonna work as the game isn't zero sum, and the outcome is completely random. A backgammon bot is easy I imagine as there is a programme that plays the game perfectly.

Bots are against the rules of the game so. . .

I'm pretty sure the thing about a roulette bot was a joke :-)
Being a game where perfect play is negative expectation, its very easy to write a bot... but impossible to write one that makes money :-)

Unless you can find some flaw in the random number generator.
Or, as the legend goes, do some clever physics modelling to use the fact that bets don't close until some time after the ball has being launched, but before it stops, to get a numerical edge.

fergalr · 02-01-2010 2:56am

RoundTower wrote: »

yes you are right in your assumptions. there is no complicated number-crunching involved, you should need a pen and paper at most.

Cool - Ill just have to read up on how to solve games of that type (dynamic, imperfect information).
Could you recommend a good tutorial, or source of information?

gerry87 · 02-01-2010 3:34am

RoundTower wrote: »

here's a simple poker game. If you have studied some basic game theory, you can solve this problem.

we play with a 3-card deck. Ace beats King beats Queen.

We both put in 1 euro to the pot. You act first and your choices are to bet nothing or bet 1 euro.

If you check (bet nothing), your opponent checks too. Whoever has the best hand wins the pot of €2.

Your opponent's choices are to call the bet or fold. If he folds, you win the pot. If he calls, he puts in €1 and whoever has the best hand wins the pot of €4.

What is the equilibrium ("optimal") strategy for this game? How much money do you win (or lose) each hand if both players play the optimal strategy? How, if at all, would you change your strategy if you knew your opponent was not following his optimal strategy? Once you can answer these questions precisely, you can attempt to generalise it to a more complicated poker game.

My Guess (I took it from the first euro was already in the pot.):

I have a queen I check-
EV(checking) = 0
EV(betting) = P(he has a ace)(-1) + P(he has a king & thinks i have a queen)(-1) + P(he has a king & thinks i have a ace)(+2)
EV(betting) = .5(-1) + (.5*.5)(-1) + P(.5*.5)(+2) = -.25

I have ace I bet-
EV(checking) = +2
EV(Betting) = P(he has a queen)(+2) + P(he has a king & thinks i have a queen)(+4) + P(he has a king & thinks i have a ace)(+2)
EV(Betting) = .5(+2) + (.5*.5)(+3) + (.5*.5)(+2) = 2.25

I have a king I check-
EV(checking) = P(he has a queen)(2) + P(he has a ace)(0)
EV(checking) = .5(2) + .5(0) = 1
EV(betting) = P(he has a queen)(2) + P(he has a ace)(-1)
EV(betting) = .5(2) + .5(-1) = 0

Ace - EV(2.25)
King - EV(1)
Queen - EV(0)

EV(Game) = (1/3)*2.25 + (1/3)*1 + (1/3)*0 = 1.0833

Anywhere near?

pkr_ennis · 02-01-2010 3:53am

fergalr wrote: »

Well - from what I understand of the game theory approaches as discussed so far, they are more concerned with figuring out what the best mixed strategy is to play - so whats the mathematically soundest thing to do every time - and not so much considering what your opponent does.

I understand the idea of modifying the probabilities of the model on account of the opponents behaviour to exploit your opponent too, but from what I can see, thats a whole other can of worms?

I think you got exactly what I'm looking for here anyway. Mixed strategy coupled with the correct adjustments is a killer strategy. Not sure how possible it is though. It looks like the bot guys replicate complex poker situations and simplify to come to an approximate answer.

fergalr · 02-01-2010 4:42am

gerry87 wrote: »

My Guess (I took it from the first euro was already in the pot.):

I have ace I bet-
EV(checking) = +2
EV(Betting) = P(he has a queen)(+2) + P(he has a king & thinks i have a queen)(+4) + P(he has a king & thinks i have a ace)(+2)
EV(Betting) = .5(+2) + (.5*.5)(+3) + (.5*.5)(+2) = 2.25

Just looking at the situation where player 1 has an Ace here.

The only thing that I don't understand is why you assign '(.5*.5)' as the value for 'P(he has a king & thinks I have an ace)'
I understand that the probability is .5 that player2 has a king, if player1 has either the ace or queen.
But I don't understand why the value for 'thinks I have an ace' (ie: 'player2 thinks player1 has an ace') is .5

Doesn't player1 provide information to player2 when player1 chooses to either raise or to check? Given that player1 knows what player1s card is, and that knowing what player1s card is probably influences player1s actions, how can player2 assign .5 to 'thinks player1 has an ace' after player1 has acted? It would have been .5 if all player2 knew was that player2 had a king, but given that player2 knows player2 has a king AND that player2 knows player1 decided to raise, as opposed to check, surely that value of 'thinks player1 has an ace' must change from .5?
I would have thought there was a feedback effect here in the model that would have to be analysed (and that would hopefully converge to a value that could be used)?
How does that work?

Again, I'm not familiar with this type of analysis, so maybe you know more than me.

pkr_ennis · 02-01-2010 1:55pm

RoundTower wrote: »

What is the equilibrium ("optimal") strategy for this game?

Not taking money into account-

Player 1 bets ace everytime
Player 1 checks king everytime
Player 1 bets queen 50% of the time
Player 2 calls ace everytime
Player 2 calls king 50% of the time and
Player 2 folds queen everytime.

gerry87 · 02-01-2010 2:39pm

fergalr wrote: »

Just looking at the situation where player 1 has an Ace here.

The only thing that I don't understand is why you assign '(.5*.5)' as the value for 'P(he has a king & thinks I have an ace)'
I understand that the probability is .5 that player2 has a king, if player1 has either the ace or queen.
But I don't understand why the value for 'thinks I have an ace' (ie: 'player2 thinks player1 has an ace') is .5

Doesn't player1 provide information to player2 when player1 chooses to either raise or to check? Given that player1 knows what player1s card is, and that knowing what player1s card is probably influences player1s actions, how can player2 assign .5 to 'thinks player1 has an ace' after player1 has acted? It would have been .5 if all player2 knew was that player2 had a king, but given that player2 knows player2 has a king AND that player2 knows player1 decided to raise, as opposed to check, surely that value of 'thinks player1 has an ace' must change from .5?
I would have thought there was a feedback effect here in the model that would have to be analysed (and that would hopefully converge to a value that could be used)?
How does that work?

Again, I'm not familiar with this type of analysis, so maybe you know more than me.

You're probably right, first pass I was taking it that player 2 wasn't getting any signals. So there's the .5 chance he has a king. Then from his point of view you either have an ace or a queen, each P=.5, so half the time he'll call and half the time he'll fold. Similar to in pkr_ennis's strategy above where he says 'player 2 calls king 50% of the time' - hell call when he thinks i have a queen and fold when he thinks i have an ace.

RoundTower · 02-01-2010 3:37pm

here's how you solve this problem:

there is nothing to be gained from checking with an Ace, so you should always bet.
there is nothing to be gained from betting with a King, so you should always check.
with a Queen you should adpot a mixed strategy, either check or bet. let's say you bet with probability x, 0 <= x <= 1

for him, he should always call with an Ace and fold with a Queen. He should call with a King some of the time - enough that you don't get to win the pot every time with a Queen, but he also doesn't want to pay you off every time you have an ace. So say he calls with probability y.

Then there are 6 possibilities for how the cards get dealt, all equrobable. When you have an Ace and he has a Queen, for example, you make €1. When you have a Queen and he has an Ace, you lose €2 x of the time and lose €1 (1-x) of the time, so on average you make €(-2x -1(1-x)) which is €(-x-1). You can also find the outcomes for the other four possibilities too, and average them together to get the expectation of the game. You should get (x + y - 3xy)/6.

Now to find the optimal x, you need to know that you should choose x such that it you are indifferent to his choice of y, in other words, the terms containing y should sum to 0. So y - 3xy = 0 for all y, therefore x = 1/3. Similarly you should get y = 1/3, and the expectation of the game should be that you, on average, make one eighteenth of a euro. He expects to lose one eighteenth of a euro on average

Now you could see how the game changes if you have a different choice, for example if the bet amount was €2 instead of €1, or more interestingly, if you had a choice to check, bet €1 or bet €2.

Game Theory and Poker

Comments