Search
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:
up
down
left
right
S
G
E
D
During an Encounter, the Guard has two options:
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.
1 - 0.5/n
n
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.
efg
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).
pip install git+https://github.com/votroto/cgt_bandits.git
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.
pygambit
Maps have the following format:
###### #SE-D# #-##G# #--E-# ######
(- empty square, S start, D destination, E possible hiding place, G gold, # wall)
-
#