Warning

This page is located in archive.

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.

In case of any problems with this assignment, with BRUTE, the template or the library, please send me an email (votroto1@fel.cvut.cz).

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.

courses/cgt/assignment2.txt · Last modified: 2022/11/26 13:52 by votroto1