Assignment 3: SQF

Implement the Sequence Form Linear Program (the program is also extracted here ) to compute the value of any two-player zero-sum extensive form game.

You can use this template and examples to get started.

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.

The libraries: numpy, scipy, pygambit, cvxopt will also be available on BRUTE, and you can still use the cgt_bandits package from the previous part to parse the EFGs.

Your program must accept the game definition in an efg format from standard input, and must write its value to standard output, i.e. the expected usage is python main.py < game.efg > out.txt.

You must not open, read or write to any files, and your standard output must contain only the value of the game without any debugging information.

• Use the EFGs that you have created in Assignment 1 for testing.
• Gurobi can not handle variable names longer than 255 characters.
• 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”).
• You can use the pygambit library to query features of EFGs such as the infosets of each player.
• The expected length of your solution is around 100 lines of code.
• We use Python 3.9 and Gambit 16.0.2 for evaluation (Gambit 16.1.0 contains breaking changes!)