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 the assignment instructions, then use the prepared templates and examples. Upload your solutions to BRUTE .

In case of any problems with the assignment, please contact Tomáš Votroubek (votroto1@fel.cvut.cz).

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:

7
9
#########
#G-----E#
#-#####-#
#S--E--D#
#-#####-#
#G-----E#
#########
2
0.5

the value of the game is 7.096774193548387.

Gambit

Installing Gambit is not necessary for the completion of your assignments, but you might find it useful for debugging.

I will show the installation procedure for 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 last year's instructions.

Go to the gambit project website, 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

deb http://dk.archive.ubuntu.com/ubuntu/ bionic main universe

Run update, then download gambit's dependencies

sudo apt-get update
sudo apt-get install -y make g++-6 libwxgtk3.0-gtk3-dev

Now simply configure, make, make install

export CC=gcc-6 CXX=g++-6 && ./configure 
make -j 4 CC=gcc-6 CXX=g++-6
sudo make install

Now you are done.

You can generate a tree and visualize it in Gambit:

  python game_tree.py < maze1.txt > maze1.efg
  gambit maze1.efg

Table of Contents

Assignment 1: Extensive-Form Games

Example

Gambit