Mark Gritter (markgritter) wrote,
Mark Gritter

Sushi-Fueled Insight

I realized at dinner tonight that it is possible to do "row generation" in addition to "column generation" when finding game-theoretic optimal play using linear programming.

The LP is structured as one column per player A strategy per card. The solution variables indicate how often player A will use that strategy. The rows are maximization constraints for each player B' strategies, again per card. Each row says something of the form "if player B has card K, he can do at least as well as playing strategy S."

To solve 3CLJF I used column generation but not row generation. I started with a reduced problem and then identified extra variables (columns) that would result in a better solution for A. But I used the full set of rows.

But, just as most strategies for A have probability 0 (i.e., bad ideas), most strategies for B don't affect the outcome either, so the constraint in the corresponding row is not tight and can be eliminated. So, we can solve a problem that has reduced strategies for both A and B, then add either columns that have the potential to increase A's value or rows that have the potential to increase B's value (which we can identify using either heuristics or brute-force search.)

(Another way to look at it is that we can do column generation for A with reduced B until we arrive at an optimal for the reduced problem, then take the dual of the problem and do column generation for B with the reduced set of A strategies in the solution of the primal problem.)
Tags: linear programming, math, poker, theory
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.