linear programming for soln of games in extensive form

[marv]

[ 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

[eastbay]

[ 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

[eastbay]

[ 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

[eastbay]

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

eastbay

[marv]

[ 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

[eastbay]

[ 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

[marv]

[ 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

[eastbay]

[ 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

[marv]

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

[eastbay]

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