You find yourself in a grid-based cave. Your goal is to escape with as much gold as possible. Your enemy is an all-knowing, all-seeing posse of miners who try to capture you.

The game is played on a grid-based map as follows:

• The game starts after all miners have collectively chosen their hiding places (Possible spots are marked E. At most one miner per space).
• On each move, You can go up, down, left, or right.
• You can step on each grid square at most once.
• Some squares have special meaning:
  • S marks Your starting square (there is only one);
  • Whenever You step on a square marked G, you pick up one gold;
  • If you step on a hiding spot E where a miner is hiding, a fight ensues;
  • As soon as you step on any exit D, the game ends.

The miners may also get an extra turn. If the first hiding place You step on is unoccupied, miners may choose to relocate one of their members to a different hiding place (not on top of the player).

Each cave defines capture_prob – the probability of a miner successfully capturing You during a fight. If you are caught, the game ends; otherwise, You dispatch of the miner and continue (safe in the knowledge there is one less miner waiting for you).

The score starts at zero. 10 points are awarded for a successful escape, with 1 additional point for each gold taken. No points will be awarded in case the player gets captured or stuck on a square with no legal moves.

Your task is to accurately describe the rules of the game as a two-player zero-sum extensive form game.

Your program must accept the cave definition from standard input, and must write the resulting efg representation to standard output, i.e. the expected usage is python main.py < cave.txt.

You must not open, read or write to any files, and your standard output must contain only the efg representation without any debugging information.

You can use this template and examples to simplify your implementation.

The template uses a library written on top of pygambit and pydot to simplify the creation, and visualization of your extensive form games. You can download it directly from Github (pip install git+https://github.com/votroto/cgt_bandits.git. Then, see the examples directory).

There is no requirement to use my library. If You are feeling adventurous, you can use pygambit directly, or even use the template from last year, along with the gambit GUI. If none of the above works for You, feel free to implement the entire thing yourself.

pygambit can compute the equilibria and the value of your games; although, do not expect it to work for larger games. Implementing a better algorithm will be the subject of your second homework assignment.

Make sure that you have Graphviz installed, if you want to render the graphs locally. If you do not wish to install Graphviz, you can still print the DOT file and use an online renderer instead.

Caves have the following format

number_of_miners:int capture_prob:float\n
maze:Matrix[char]

Example

2 0.33
######
#SE-D#
#-##G#
#--E-#
######

(- empty square, S start, D destination, E possible hiding place, G gold, # wall)

• Your goal is to formulate the problem as an extensive form game, not to try to solve it, or evaluate it in any way – that will be your next assignment.
• Please, test your solutions and visualize your trees.
• There are many correct solutions. Checking whether your tree correctly describes the game is non trivial; as a result, You may receive points for incorrect solutions. We will inspect your solutions manually at most two weeks after the deadline and deduct points in case of errors.
• Be aware that all your submissions are automatically checked for plagiarism. Please read the CourseWare page on plagiarism and cheating before uploading any solutions.
• The expected length of your solution is around 150 lines of code.
• Do not worry about inventing the best path finding algorithm, or the most compact representation of the game. That is not the point of this assignment.
• Picked up gold only counts towards your score if You escape with it:
  • escape with 2 golds = 12 points
  • getting captured with 2 golds = 0 points