Assignment 2: Sequence-Form LP

Implement the Sequence Form Linear Program. Your solution should work not just for the games you created in the first part of this assignment, but for any two-player zero-sum extensive form games.

We recommend you use Gurobi to solve this task, you can find its documentation here. You can also follow the instruction from the Combinatorial Optimization course on how to setup Gurobi locally. If you dislike Gurobi, you can use cvxopt.

The libraries: numpy, scipy, pygambit, and the cgt_bandits package from the previous part will also be available on BRUTE.

You must construct the LPs for each player individually. You are not allowed to simply construct the LP for one player, and then return -payoff for the other player.

• Standard output must not contain anything but the payoffs.
• Do not open, read or write to any files. (The expected usage is: python main.py < game.efg > out.txt)
• Output the payoffs of both players separated by whitespace to the standard output.

You can use this template and examples to get started.

Use the EFGs that you have created in assignment 1 for testing. If you do not have those, at least use the example from the lecture, or the simple poker implementation found in the examples of the cgt_bandits library.

• Gurobi can not handle variable names longer than 255 characters.
• By default, variables in Gurobi are constrained. Use lb=-GRB.INFINITY and ub=GRB.INFINITY to create free variables.
• Assign identifiers to actions, such that they are unique across infosets (Folding a royal flush is not equivalent to folding a high card, they must not both be named “fold”).
• There are many ways to formulate the SQF program, but you might find it easiest to lean on Gurobi's modelling API and implement the program as it was stated during the lecture (page 15).
• Modifying the tree to get v(root) is undesirable. Compute the value analogously to the “best response” condition (see lect. slides constr. 5) with σ2a = ∅.
• You can use the pygambit library to query features of EFGs such as the infosets of each player.
• You can use import_efg.efg_to_nodes(efg) from cgt_bandits to convert the EFG tree into simple dataclasses.
• The expected length of your solution is around 100 lines of code.