====== Assignment 2: Sequence-Form LP ======

/*Your task will be to solve two-player zero-sum extensive form games as a sequence-form LP.*/
Implement [[https://cw.fel.cvut.cz/b221/_media/courses/cgt/cgt_l05_solvingefgs_2021.pdf|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.

<note tip>In case of any problems with this assignment, with BRUTE, the template or the library, please send me an email ([[mailto:votroto1@fel.cvut.cz|votroto1@fel.cvut.cz]]).</note>

==== Libraries ====
We recommend you use Gurobi to solve this task, you can find its [[https://www.gurobi.com/documentation/9.5/quickstart_windows/cs_python.html|documentation here]].  You can also follow the instruction from the [[https://cw.fel.cvut.cz/b182/courses/ko/labs|Combinatorial Optimization course]] on how to setup Gurobi locally. If you dislike Gurobi, you can use [[https://cvxopt.org/examples/tutorial/lp.html|cvxopt]].

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

==== Requirements ====

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.

==== Template ====

You can use {{ :courses:cgt:cgt_sqf_help.zip | 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 [[https://github.com/votroto/cgt_bandits/blob/main/examples/test_poker.py|examples of the cgt_bandits library]].


==== Notes ====
  * 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 [[https://cw.fel.cvut.cz/wiki/_media/courses/cgt/cgt_l05_solvingefgs_2022.pdf|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.