linear programming for soln of games in extensive form

[eastbay]

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

[poincaraux]

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?

[eastbay]

[ 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

[poincaraux]

[ 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.

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.

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.

[droidboy]

[ 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

[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

[gabbahh]

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.

[marv]

[ 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