====== Assignment 2: EFG ======

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.


===== Rules of the Game =====

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%%''.

===== Encounters =====

During an Encounter, the Guard has two options:
  - Fight to try and stop the Thief,
  - Remain hidden and 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 - \frac{0.5}{n} \) where \( n \) is the number of Encounters. The Thief knows when a fight happens, but is unaware of the Guard's sneaky hiding place changes.



===== Scoring =====

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; that means: 
  * Escape (2 pts.) with 3 golds = 5 points;
  * Get captured with 3 golds = 0 points. 

====== Extensive Form Games ======

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.


===== Requirements =====

Your program must accept the cave definition from standard input, and must write the resulting game tree to standard output, i.e. the expected usage is 
<code>
python main.py < cave.txt > game.json
</code>

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

===== Examples, Tests, Templates and Libraries =====

You can use {{ :courses:cgt:efg_2025_template.zip | our template}} and {{ :courses:cgt:efg_2024_mazes.zip | example caves }} (and {{ :courses:cgt:efg_2024_values.zip | their values }}) to simplify your implementation.

The template uses [[https://github.com/votroto/cgt_bandits|our EFG library]], [[https://gambitproject.readthedocs.io/en/latest/pyapi.html#|pygambit]] and [[https://pypi.org/project/pydot/|pydot]] to simplify the creation, and visualization of your extensive form games. You can download it directly from Github 
<code>
pip install git+https://github.com/votroto/cgt_bandits.git[dot,gambit]
</code>
Follow the installation instructions, then see the [[https://github.com/votroto/cgt_bandits/tree/main/examples | examples ]] directory.

Use ''%%pygambit%%'' to compute equilibria and values of your games, but do not expect it to work for larger games. Implementing a better algorithm will be the subject of a subsequent homework assignment.

===== Input File Format =====

Maps have the following format:

<code txt>
######
#SE-D#
#-##G#
#--E-#
######
</code>

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

===== Notes =====

  * 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 [[https://cw.fel.cvut.cz/b181/help/common/plagiarism_cheating|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.
  * We use Python 3.13 and Gambit 16.4.0 for evaluation. Please make sure you have the correct version of `pygambit` as the devs love to introduce sneaky API rewrites among their bugfix releases.