====== Assignment 1: Double Oracle ======

You are a Thief in a grid-based maze. Your goal is to escape unseen. Your opponent must place a sensor to maximize the chance of your detection.

The game is played on a grid-based map as follows: 
  * The Thief starts at the square marked 'S' and must reach any destination 'D';
  * The guards pick one sensor position out of the possible spots marked 'E';
  * Thief moves only ''%%up%%'', ''%%down%%'', ''%%left%%'', or ''%%right%%'';
  * Stepping on a sensor means guaranteed detection.
  * Being detected results in a reward -1 to the thief. Otherwise the reward is 0.

====== Double Oracle Algorithm ======

Your task is to compute an eps-Nash equilibrium of both players in mixed strategies using the {{ :courses:cgt:cgt_tpzs.pdf |Double Oracle algorithm}}.

===== Requirements =====

Your program must accept the maze definition from standard input, and must write the **expected probability of detection** (reward from the opponent's perspective) to standard output, i.e. the expected usage is ''%%python main.py eps < cave.txt > visibility.txt%%''.

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

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

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

Maps have the following format:

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

(''%%-%%'' empty square,  ''%%S%%'' start,  ''%%D%%'' destination,  ''%%E%%'' possible sensor spot, ''%%#%%'' wall)

===== Notes =====

  * Formulate everything from the perspective of a Thief that is minimizing the expected chance of detection. It's easy to get lost in the probabilities if you are not consistent.
  * The expected length of your solution is around 180 lines of code.
  * Please, test your solutions before uploading. 
  * 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.
  * We use Python 3.13, Scipy 1.15, Numpy 2.2 for evaluation.