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 is played on a grid-based map as follows:
up
, down
, left
, or right
. E
. At most one miner per space). S
marks Your starting square (there is only one); G
, you pick up one gold; E
where a miner is hiding, starts an encounter;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.
During an encounter, a miner has two options:
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.
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.
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 > 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 this 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.
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)