====== Assignment 1: Extensive-Form Games ======
Your goal will be to formalize a problem as an extensive-form game and solve it using an LP solver. Start by reading {{ :courses:cgt:efg2021.pdf |the assignment instructions}}, then use {{ :courses:cgt:efg2021.zip |the prepared templates and examples}}. Upload your solutions to [[ http://cw.felk.cvut.cz/upload/|BRUTE ]].

<note tip>In case of any problems with the assignment, please contact Tomáš Votroubek (''votroto1@fel.cvut.cz'').</note>

  * Please use Python versions between 3.6 and 3.7.3-1. Thanks for pointing that out!
  * Information set numbers should be 32-bit integers.
  * Read from //stdin// and write for //stdout//. The expected usage is: ''python game_tree.py < maze.txt > tree.efg''.

====== Example =====
Example for the first part:

<code>
7
9
#########
#G-----E#
#-#####-#
#S--E--D#
#-#####-#
#G-----E#
#########
2
0.5
</code>
the value of the game is ''7.096774193548387''. 
====== Gambit ======

<note>Installing Gambit is not necessary for the completion of your assignments, but you might find it useful for debugging.
</note>
I will show the installation procedure for [[https://ubuntu.com/download/desktop|Ubuntu 20.04.3 LTS]]. Spin it up in a VM if you want to follow along. If this does not work for you, try [[https://cw.fel.cvut.cz/b201/courses/be4m36mas/assignment2-game#gambit|last year's instructions]].

Go to [[http://www.gambit-project.org/|the gambit project website]], download [[https://sourceforge.net/projects/gambit/files/gambit16/16.0.1/gambit-16.0.1.tar.gz/download|the Gambit 16 tarball]], decompress it, and open a terminal inside the folder.

Gambit is an aging software now and needs an older compiler. Open ''/etc/apt/sources.list'' as root (e.g. with ''sudo vi'') and add 
<code>
deb http://dk.archive.ubuntu.com/ubuntu/ bionic main universe
</code>

Run update, then download gambit's dependencies
<code>
sudo apt-get update
sudo apt-get install -y make g++-6 libwxgtk3.0-gtk3-dev
</code>

Now simply configure, make, make install
<code>
export CC=gcc-6 CXX=g++-6 && ./configure 
make -j 4 CC=gcc-6 CXX=g++-6
sudo make install
</code>
**Now you are done.**

You can generate a tree and visualize it in Gambit:
<code>
  python game_tree.py < maze1.txt > maze1.efg
  gambit maze1.efg
</code>