Two Plus Two Older Archives  

Go Back   Two Plus Two Older Archives > General Poker Discussion > Poker Theory

Reply
 
Thread Tools Display Modes
  #1  
Old 10-04-2005, 12:48 PM
eastbay eastbay is offline
Senior Member
 
Join Date: Nov 2003
Posts: 647
Default 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
Reply With Quote
  #2  
Old 10-04-2005, 03:41 PM
poincaraux poincaraux is offline
Junior Member
 
Join Date: Jan 2004
Posts: 0
Default 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?
Reply With Quote
  #3  
Old 10-04-2005, 04:55 PM
gabbahh gabbahh is offline
Member
 
Join Date: Jun 2005
Posts: 35
Default 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.
Reply With Quote
  #4  
Old 10-04-2005, 08:23 PM
eastbay eastbay is offline
Senior Member
 
Join Date: Nov 2003
Posts: 647
Default 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
Reply With Quote
  #5  
Old 10-05-2005, 12:23 PM
poincaraux poincaraux is offline
Junior Member
 
Join Date: Jan 2004
Posts: 0
Default 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.
Reply With Quote
  #6  
Old 10-05-2005, 03:23 PM
marv marv is offline
Junior Member
 
Join Date: Aug 2004
Posts: 1
Default 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
Reply With Quote
  #7  
Old 10-05-2005, 05:40 PM
Guest
 
Posts: n/a
Default 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.
Reply With Quote
  #8  
Old 10-05-2005, 06:03 PM
Guest
 
Posts: n/a
Default 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.
Reply With Quote
  #9  
Old 10-06-2005, 11:14 AM
eastbay eastbay is offline
Senior Member
 
Join Date: Nov 2003
Posts: 647
Default 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
Reply With Quote
  #10  
Old 10-06-2005, 12:25 PM
droidboy droidboy is offline
Member
 
Join Date: Sep 2002
Location: oakland
Posts: 73
Default 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
Reply With Quote
Reply

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT -4. The time now is 12:02 PM.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2024, vBulletin Solutions Inc.