linear programming for soln of games in extensive form
 

Does anyone have experience with this? I am familiar with the normal form LP, but the extensive form formulation ala Koller et. al. isn't clicking yet. I can't quite figure out how to formulate the constraints, or what they are in fact supposed to represent.

I can give more details, but will wait for "yeah, I've done that" before going to the trouble.

eastbay

Re: linear programming for soln of games in extensive form
 

I don't, but I will soon (it's pretty much at the top of my todo list, and I'll be starting a bit of an open-ended poker programming project in a week or so). You probably want to read the articles that Prock references here.

What are you working on?

Re: linear programming for soln of games in extensive form
 

Have u read:
Approximating Game-Theoritic Optimal Strategues for Full-scale Poker, by D.Billings, ea?
There I read they also call this LP representation the sequential form.
This sequential form is explained at the ppt at
web page

Or search on google with keywords: LP sequence form

I think it's what u need.

Re: linear programming for soln of games in extensive form
 

[ QUOTE ]
I don't, but I will soon (it's pretty much at the top of my todo list, and I'll be starting a bit of an open-ended poker programming project in a week or so). You probably want to read the articles that Prock references here.

What are you working on?

[/ QUOTE ]

I've got those. Selby comes the close to spelling it out, but there's some details he glosses over in his exposition.

I'm basically just trying to get off the ground using LP to "solve" some simple poker model games, like preflop all-in/fold as a starting point.

I've done this before using simulation and a whole slew of optimization approaches, but this is all very slow when you start adding anything non-trivial to the strategy space (like allowing multiple raise sizes or multiple betting rounds, even staying preflop.)

eastbay

Re: linear programming for soln of games in extensive form
 

[ QUOTE ]
I've got those. Selby comes the close to spelling it out, but there's some details he glosses over in his exposition.

I'm basically just trying to get off the ground using LP to "solve" some simple poker model games, like preflop all-in/fold as a starting point.

[/ QUOTE ]
That's where I'm going to start as well. I'll come back to this thread and post when I a) figure things out or b) get stuck. I'll probably write stuff in Python, but I'm comfortable in C++ and Java and I'll probably be willing to share code with the intarweb as well. It's too bad Selby only posted a couple of things to RGP.

Re: linear programming for soln of games in extensive form
 

[ QUOTE ]
Does anyone have experience with this? I am familiar with the normal form LP, but the extensive form formulation ala Koller et. al. isn't clicking yet. I can't quite figure out how to formulate the constraints, or what they are in fact supposed to represent.

I can give more details, but will wait for "yeah, I've done that" before going to the trouble.

eastbay

[/ QUOTE ]

I've done quite a bit of this.

Get your game in the form

max_x min_y x^T H y

s.t.

E x = e
F y = f
x,y >= 0

and then converting this to a standard LP is easy.

What bit is causing you grief?

Marv

Re: linear programming for soln of games in extensive form
 

After reading the info, I'm pretty sure that Selby's program is not necessarily correct for multiple betting rounds. For example, if you run with
num d=2 nr=4
(Players are given 0, or 1 where 1 beats 0, and there can be up to 4 raises)

Then you get:
Small Blind Call/Fold with 0
Small Blind Raise/Call with 1
Big Blind Fold to a raise with 0 but check/call otherwise.

Which is clearly non-optimal, since the big blind could raise after a call to push the small blind out.

Re: linear programming for soln of games in extensive form
 

This really doesn't look like linear programming is going to be a good solution, but, perhaps, some sort of gradient-descent method could be used since the variables only show up in the 1st degree in the value function.

Re: linear programming for soln of games in extensive form
 

[ QUOTE ]
[ QUOTE ]
Does anyone have experience with this? I am familiar with the normal form LP, but the extensive form formulation ala Koller et. al. isn't clicking yet. I can't quite figure out how to formulate the constraints, or what they are in fact supposed to represent.

I can give more details, but will wait for "yeah, I've done that" before going to the trouble.

eastbay

[/ QUOTE ]

I've done quite a bit of this.

Get your game in the form

max_x min_y x^T H y

s.t.

E x = e
F y = f
x,y >= 0

and then converting this to a standard LP is easy.

What bit is causing you grief?

Marv

[/ QUOTE ]

Consider a preflop game ala Selby.

Following Koller et al, the "chance player" at the top of the tree has 169^2 "moves," representing all possible deals. Each player has 169 information sets, and say each player has 2 moves.

Is the size of the payoff matrix really (2*169^2+1)^2? It seems like the payoff matrix should really be of size (2*169+1)^2, with the redundancy expressed in the constraint matrices used to eliminate most of the entries.

The constraint matrices seem to have 2*169^2+1 columns and 169 rows, most of which say "this choice prob. must be equal to that one, because the player can't distinguish."

That seems like a huge amount of storage to express a trivial notion that should be directly built-in to the formulation.

Maybe I'm not handling the "chance player" right somehow, but this problem seems to be coming out far larger than it needs to be.

eastbay

Re: linear programming for soln of games in extensive form
 

[ QUOTE ]


I've got those. Selby comes the close to spelling it out, but there's some details he glosses over in his exposition.

I'm basically just trying to get off the ground using LP to "solve" some simple poker model games, like preflop all-in/fold as a starting point.

I've done this before using simulation and a whole slew of optimization approaches, but this is all very slow when you start adding anything non-trivial to the strategy space (like allowing multiple raise sizes or multiple betting rounds, even staying preflop.)

eastbay

[/ QUOTE ]

I plan on posting the basic HU NL PF LP problem to A Slave to Variance fairly soon. I've got it worked out, but I'm in the middle of a move so I don't have good internet connectivity right now.

But an LP solution will not really allow you to deal with the complexity of adding multi round betting to your solution. The combinatorial explosion is too high to deal with general postflop play (you might be able to do a rank only solution though). The Selby formulation does allow for multiple bets, limit and pot limit, but doesn't allow for postflop betting at all. Strangely it doesn't do no limit directly, but you can use the code to generate reasonable solutions for jam/fold.

- Andrew

www.pokerstove.com

Re: linear programming for soln of games in extensive form
 

[ QUOTE ]
[ QUOTE ]
[ QUOTE ]
Does anyone have experience with this? I am familiar with the normal form LP, but the extensive form formulation ala Koller et. al. isn't clicking yet. I can't quite figure out how to formulate the constraints, or what they are in fact supposed to represent.

I can give more details, but will wait for "yeah, I've done that" before going to the trouble.

eastbay

[/ QUOTE ]

I've done quite a bit of this.

Get your game in the form

max_x min_y x^T H y

s.t.

E x = e
F y = f
x,y >= 0

and then converting this to a standard LP is easy.

What bit is causing you grief?

Marv

[/ QUOTE ]

Consider a preflop game ala Selby.

Following Koller et al, the "chance player" at the top of the tree has 169^2 "moves," representing all possible deals. Each player has 169 information sets, and say each player has 2 moves.

Is the size of the payoff matrix really (2*169^2+1)^2? It seems like the payoff matrix should really be of size (2*169+1)^2, with the redundancy expressed in the constraint matrices used to eliminate most of the entries.

The constraint matrices seem to have 2*169^2+1 columns and 169 rows, most of which say "this choice prob. must be equal to that one, because the player can't distinguish."

That seems like a huge amount of storage to express a trivial notion that should be directly built-in to the formulation.

Maybe I'm not handling the "chance player" right somehow, but this problem seems to be coming out far larger than it needs to be.

eastbay

[/ QUOTE ]

So the root node is a chance node with 169 kids.
Each of these is a chance node with 169 kids.
Each of these is an action node for player 1 with 2 kids.
Each of these is an action node for player 2 with 2 kids.

Below the chance nodes, at the third level in the tree there are 169 information sets for each player each with 169 nodes, and at the third level there are 169.2 information set for each, and at the leaf nodes there are 169.2.2 information sets. Each information set has 169 nodes.

So there are 169.169.2.2 leaves and hence this number of non-zeros in the payoff matrix.

There are 169.169.2 variables for player 1 and 169.169.2.2 variables for player 2, but the information set constraints mean there are really only 1/169 of these for each player.

If you don't eliminate the unnecessary variables (by picking a representative node in each information set at each action node), you'll have to use sparse matrix storage, and then rely on your LP solver to presolve the problem efficiently. This is uncool.

I think Alex also eliminated the unnecessary variables but then used dense storage for his simplex code (if I recall correctly).

Marv

Re: linear programming for soln of games in extensive form
 

[ QUOTE ]
[ QUOTE ]


I've got those. Selby comes the close to spelling it out, but there's some details he glosses over in his exposition.

I'm basically just trying to get off the ground using LP to "solve" some simple poker model games, like preflop all-in/fold as a starting point.

I've done this before using simulation and a whole slew of optimization approaches, but this is all very slow when you start adding anything non-trivial to the strategy space (like allowing multiple raise sizes or multiple betting rounds, even staying preflop.)

eastbay

[/ QUOTE ]

I plan on posting the basic HU NL PF LP problem to A Slave to Variance fairly soon. I've got it worked out, but I'm in the middle of a move so I don't have good internet connectivity right now.


[/ QUOTE ]

What's your strategy space look like? I can't imagine you mean full NL, with arbitrary bet sizes.

[ QUOTE ]

But an LP solution will not really allow you to deal with the complexity of adding multi round betting to your solution.

[/ QUOTE ]

No doubt. But I think you could "bucket" heavily into a reasonably number of "flop types" and still get useful answers. But I'm not even really thinking postflop yet.

I suspect I'd rather try to analyze the 3-handed all-in/fold problem before exploring postflop rounds.

eastbay

Re: linear programming for soln of games in extensive form
 

[ QUOTE ]
[ QUOTE ]
[ QUOTE ]
[ QUOTE ]
Does anyone have experience with this? I am familiar with the normal form LP, but the extensive form formulation ala Koller et. al. isn't clicking yet. I can't quite figure out how to formulate the constraints, or what they are in fact supposed to represent.

I can give more details, but will wait for "yeah, I've done that" before going to the trouble.

eastbay

[/ QUOTE ]

I've done quite a bit of this.

Get your game in the form

max_x min_y x^T H y

s.t.

E x = e
F y = f
x,y >= 0

and then converting this to a standard LP is easy.

What bit is causing you grief?

Marv

[/ QUOTE ]

Consider a preflop game ala Selby.

Following Koller et al, the "chance player" at the top of the tree has 169^2 "moves," representing all possible deals. Each player has 169 information sets, and say each player has 2 moves.

Is the size of the payoff matrix really (2*169^2+1)^2? It seems like the payoff matrix should really be of size (2*169+1)^2, with the redundancy expressed in the constraint matrices used to eliminate most of the entries.

The constraint matrices seem to have 2*169^2+1 columns and 169 rows, most of which say "this choice prob. must be equal to that one, because the player can't distinguish."

That seems like a huge amount of storage to express a trivial notion that should be directly built-in to the formulation.

Maybe I'm not handling the "chance player" right somehow, but this problem seems to be coming out far larger than it needs to be.

eastbay

[/ QUOTE ]

So the root node is a chance node with 169 kids.
Each of these is a chance node with 169 kids.
Each of these is an action node for player 1 with 2 kids.
Each of these is an action node for player 2 with 2 kids.

Below the chance nodes, at the third level in the tree there are 169 information sets for each player each with 169 nodes, and at the third level there are 169.2 information set for each, and at the leaf nodes there are 169.2.2 information sets. Each information set has 169 nodes.

So there are 169.169.2.2 leaves and hence this number of non-zeros in the payoff matrix.

There are 169.169.2 variables for player 1 and 169.169.2.2 variables for player 2, but the information set constraints mean there are really only 1/169 of these for each player.

If you don't eliminate the unnecessary variables (by picking a representative node in each information set at each action node), you'll have to use sparse matrix storage, and then rely on your LP solver to presolve the problem efficiently. This is uncool.

I think Alex also eliminated the unnecessary variables but then used dense storage for his simplex code (if I recall correctly).

Marv

[/ QUOTE ]

Agree. I'm trying the sparse representation and seeing how that goes.

eastbay

looking good
 

Alright, I've got a solution. Anyone want to compare notes?

eastbay

Re: looking good
 

[ QUOTE ]
Alright, I've got a solution. Anyone want to compare notes?


[/ QUOTE ]

What are your game's parameters?

sb/bb
choice of limit/pl/nl
depth for pl/nl
max number of raises

(I can handle the jam/fold problem and a few other twists.)

Marv

Re: looking good
 

[ QUOTE ]
[ QUOTE ]
Alright, I've got a solution. Anyone want to compare notes?


[/ QUOTE ]

What are your game's parameters?

sb/bb
choice of limit/pl/nl
depth for pl/nl
max number of raises

(I can handle the jam/fold problem and a few other twists.)

Marv

[/ QUOTE ]

Just jam/fold NL at the moment.

For stacks 5k, blinds 300/600, do you get one hand each for SB and BB with mixed strategies, namely 84s and T9o, with somewhere around .35 and .90 push probabilities?

eastbay

Re: looking good
 

[ QUOTE ]
[ QUOTE ]
[ QUOTE ]
Alright, I've got a solution. Anyone want to compare notes?


[/ QUOTE ]

What are your game's parameters?

sb/bb
choice of limit/pl/nl
depth for pl/nl
max number of raises

(I can handle the jam/fold problem and a few other twists.)

Marv

[/ QUOTE ]

Just jam/fold NL at the moment.

For stacks 5k, blinds 300/600, do you get one hand each for SB and BB with mixed strategies, namely 84s and T9o, with somewhere around .35 and .90 push probabilities?


[/ QUOTE ]

Not quite. (I assume the game we're considering permits precisely all-in and fold, no checking or calling.) I get one mixed hand for SB (76o, going allin 37%) and one for BB (Q6s, allin 75%). It's folding Q5s in the BB and calling Q7s.

I get the value of the game to be 86.2251 in BB's favour.
We should agree on that.

Marv

Re: looking good
 

[ QUOTE ]

Just jam/fold NL at the moment.

For stacks 5k, blinds 300/600, do you get one hand each for SB and BB with mixed strategies, namely 84s and T9o, with somewhere around .35 and .90 push probabilities?


[/ QUOTE ]

Not quite. (I assume the game we're considering permits precisely all-in and fold, no checking or calling.) I get one mixed hand for SB (76o, going allin 37%) and one for BB (Q6s, allin 75%). It's folding Q5s in the BB and calling Q7s.

I get the value of the game to be 86.2251 in BB's favour.
We should agree on that.

Marv

[/ QUOTE ]

Hmm. I'm not agreeing with that. Yes, this is precisely all-in/fold for each player.

I am getting a value of about 6.6 chips in the BB's favor. My BB is calling with more hands, Q4s+, and down to T8s+.

I guess we need to match up an expected payoff on a particular pair of strategies if we're going to figure out the discrepancy.

Are you accounting for the probability that player 2 holds a hand with common cards of player 1? I guess we could compare EV matrices, and hand holding probability matrices.

eastbay

Re: looking good
 

OK, I've posted my SB and BB strategies to
http://web.onetel.com/~marv742/HUNL/sb and http://web.onetel.com/~marv742/HUNL/bb .

The format should be fairly clear. There's a solution to a more complex problem at
http://web.onetel.com/~marv742/8cardpoker which explains the format a little.

If you can post your strategy in as easily machine readable form as possible, we can exchange and figure out why I think my BB strategy beats your SB strategy by way more than you do.

(Just in case this is the problem, I used pokerstoves equity tables rather than Alex Selby's as his seem to be wrong.)

Marv

Re: looking good
 

http://www.sitngo-analyzer.com/5k-300-600.txt

AA push1 is the probability of player 1, the SB, pushing AA. Folding is not shown but is clearly 1-.

AA call2 is the probability of player 2, the BB, calling with AA. Folding is not shown but is clearly 1-.

I am using equity tables I computed myself, but have cross-checked a few points with pokerstove and they matched identically.

When you compute the probability of player 2 picking up AA given that player 1 picked up AA, what value are you using?

eastbay

Re: looking good
 

[ QUOTE ]

When you compute the probability of player 2 picking up AA given that player 1 picked up AA, what value are you using?


[/ QUOTE ]

0.000816327

Re: looking good
 

[ QUOTE ]
[ QUOTE ]

When you compute the probability of player 2 picking up AA given that player 1 picked up AA, what value are you using?


[/ QUOTE ]

0.000816327

[/ QUOTE ]

Yep, agree.

Ok, here's a possible verification point:

For short enough stacks, BB must always call. If BB always calls, then SB must also play a pure strategy (I don't know if this is rigorous, but I find it to be true.)

If SB is playing a pure strategy, then the LP is trivial: we choose those hands that are +EV, and fold everything else.

If blinds are 1/2 and stacks 4, and BB is calling everything, SB's hands are -EV if his equity is < 3/8 vs. a random hand.

So SB's only fold hands are: 83o,42s,82o,73o,53o,63o,32s,43o,72o,52o,62o,42o,32 o.

c.f. http://www.jazbo.com/poker/huholdem.html

Do you agree and recover that solution?

eastbay

Re: looking good
 

[ QUOTE ]
[ QUOTE ]
[ QUOTE ]

When you compute the probability of player 2 picking up AA given that player 1 picked up AA, what value are you using?


[/ QUOTE ]

0.000816327

[/ QUOTE ]

Yep, agree.

Ok, here's a possible verification point:

For short enough stacks, BB must always call. If BB always calls, then SB must also play a pure strategy (I don't know if this is rigorous, but I find it to be true.)

If SB is playing a pure strategy, then the LP is trivial: we choose those hands that are +EV, and fold everything else.

If blinds are 1/2 and stacks 4, and BB is calling everything, SB's hands are -EV if his equity is < 3/8 vs. a random hand.

So SB's only fold hands are: 83o,42s,82o,73o,53o,63o,32s,43o,72o,52o,62o,42o,32 o.

c.f. http://www.jazbo.com/poker/huholdem.html

Do you agree and recover that solution?

[/ QUOTE ]

Agreed. I had a bug, and now get exactly the same strategy as you for the 300/600 problem, and a value of 6.60878 in the BB's favour, as you did.

This was a good test example.

Marv

Re: looking good
 

[ QUOTE ]
[ QUOTE ]
[ QUOTE ]
[ QUOTE ]

When you compute the probability of player 2 picking up AA given that player 1 picked up AA, what value are you using?


[/ QUOTE ]

0.000816327

[/ QUOTE ]

Yep, agree.

Ok, here's a possible verification point:

For short enough stacks, BB must always call. If BB always calls, then SB must also play a pure strategy (I don't know if this is rigorous, but I find it to be true.)

If SB is playing a pure strategy, then the LP is trivial: we choose those hands that are +EV, and fold everything else.

If blinds are 1/2 and stacks 4, and BB is calling everything, SB's hands are -EV if his equity is < 3/8 vs. a random hand.

So SB's only fold hands are: 83o,42s,82o,73o,53o,63o,32s,43o,72o,52o,62o,42o,32 o.

c.f. http://www.jazbo.com/poker/huholdem.html

Do you agree and recover that solution?

[/ QUOTE ]

Agreed. I had a bug, and now get exactly the same strategy as you for the 300/600 problem, and a value of 6.60878 in the BB's favour, as you did.

This was a good test example.

Marv

[/ QUOTE ]

Nice. Two trials is a proof. [img]/images/graemlins/smile.gif[/img]

eastbay

Re: looking good
 

[ QUOTE ]

If blinds are 1/2 and stacks 4, and BB is calling everything, SB's hands are -EV if his equity is < 3/8 vs. a random hand.

So SB's only fold hands are: 83o,42s,82o,73o,53o,63o,32s,43o,72o,52o,62o,42o,32 o.

c.f. http://www.jazbo.com/poker/huholdem.html

Do you agree and recover that solution?

eastbay

[/ QUOTE ]

Is it correct, that with blinds 1/2 with only 2 Chips and 32o SB should fold? (< 1/3 equity)