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.
python main.py < game.efg > out.txt
)
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.
lb=-GRB.INFINITY
and ub=GRB.INFINITY
to create free variables.
v(root)
is undesirable. Compute the value analogously to the “best response” condition (see lect. slides constr. 5) with σ2a = ∅
.
pygambit
library to query features of EFGs such as the infosets of each player.
import_efg.efg_to_nodes(efg)
from cgt_bandits
to convert the EFG tree into simple dataclasses.