You are a Thief in a grid-based cave. Your goal is to escape with as much gold as possible. There is a Guard who wants to stop You.

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

• The Guard starts the game by choosing a hiding place;
• On each move, the Thief can go up, down, left, or right;
• The Thief can step on each grid square at most once;
• The Guard cannot see the Thief's path;
• Some squares have special meaning:
  • S marks the Thief's starting square (there is only one);
  • Whenever the Thief steps on a square marked G, they pick up one gold;
  • Stepping on a hiding spot E where the Guard is hiding, starts an Encounter;
  • The game ends as soon as the Thief steps on any exit D.

During an Encounter, the Guard has two options:

1. Fight to try and stop the Thief,
2. Sneak to a different hiding place.

If the Thief loses a fight, the game ends immediately; otherwise the Thief is free to continue with all the collected gold. The probability that the Guard wins a fight starts at 50 % and increases with each Encounter according to the formula 1 - 0.5/n where n is the number of Encounters.

The score starts at zero. The Thief gets two points for a successful escape, and one additional point for each gold stolen. No points will be awarded in case the Thief loses a fight or gets stuck on a square with no legal moves.

This game is much more complex than the previous and developing best-response oracles is not so easy. Instead, Your task is to accurately describe the rules of the game as a two-player zero-sum extensive form game, such that it can be solved by a generic algorithm You will implement in the next homework assignment.

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 > game.efg.

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 our template and example caves (and their values ) 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).

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.

Maps have the following format:

######
#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 (2 pts.) with 3 golds = 5 points
  • getting captured with 3 golds = 0 points
• We use Python 3.11 and Gambit 16.1.1 for evaluation.