====== Assignment 1: EFG ======
**Deadline for submission to BRUTE is 14.11.2023**

You find yourself in a grid-based cave. Your goal is to escape with as much gold as possible. Your enemy is a group of miners who try to capture you.


===== The Game =====

The game is played on a grid-based map as follows: 
  *  On each move, You can go ''%%up%%'', ''%%down%%'', ''%%left%%'', or ''%%right%%''. 
  *  You can step on each grid square at most once.
  *  Miners start the game by collectively choosing their hiding places (Possible spots are marked ''%%E%%''. At most one miner per space). 
  *  Miners never move from their chosen places.
  *  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; 
    *  Stepping on a hiding spot ''%%E%%'' where a miner is hiding, starts an encounter;
    *  As soon as you step on any exit ''%%D%%'', the game ends.

The miners cannot see the player or the path he took; however, they operate as a “hivemind.” If one miner knows something, they all do. This shared knowledge includes all encounters and their results.
===== Encounters =====

During an encounter, a miner has two options:
  - Take all your gold and let you go,
  - Start a fight with you to try and capture you.

If you lose the fight, the game ends; if you win, you continue with all your gold. Each cave defines the probability ''%%capture_prob%%'' of you losing the fight.

===== Scoring =====

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


----

====== Homework Assignment 1 ======

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

===== Requirements =====

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.

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

You can use {{ :courses:cgt:efg_2023_template.zip | this template }} and {{ :courses:cgt:efg_2023_caves.zip | example caves }} (and {{ :courses:cgt:efg_2023_values.zip | their values }}) to simplify your implementation.

The template uses [[https://github.com/votroto/cgt_bandits|a library]] written on top of [[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 (''%%pip install git+https://github.com/votroto/cgt_bandits.git%%''. Then, see the [[https://github.com/votroto/cgt_bandits/tree/18c0c72679be2ee7828782b3539ab2dcfa2351c5/examples | 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.
===== Input File Format =====

Caves have the following format

<code>
number_of_miners:int capture_prob:float\n
maze:Matrix[char]
</code>

Example

<code txt>
2 0.33
######
#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.
  * 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.9 and Gambit 16.0.2 for evaluation (Gambit 16.1.0 contains breaking changes!)