====== 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
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)
===== 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!)