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.

Your task is to compute a Nash equilibrium of both players in mixed strategies using the Double Oracle algorithm.

Your program must accept the maze definition from standard input, and must write the expected probability of detection to standard output, i.e. the expected usage is python main.py < 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.

You can use this template and example caves (and their values ) to simplify your implementation.

Maps have the following format:

######
#SE-D#
#-##-#
#--E-#
######

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

• 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.
• Be aware that all your submissions are automatically checked for plagiarism. Please read the CourseWare page on plagiarism and cheating before uploading any solutions.
• We use Python 3.11 and Gambit 16.1.1 for evaluation.