Question $5(3$ points$)$: Finding All the Corners

The real power of $A^{*}$ will only be apparent with a more challenging search problem. Now, it's time to formulate a new problem and design

a heuristic for it$.$

In corner mazes, there are four dots, one in each corner. Our new search problem is to find the shortest path through the maze that

touches all four corners $($whether the maze actually has food there or not$).$ Note that for some mazes like tinycorners, the shortest path

does not always go to the closest food first! Hint: the shortest path through tinycorners takes $28$ steps.

Note: Make sure to complete Question $2$ before working on Question $5,$ because Question $5$ builds upon your answer for Question $2.$

Implement the CornersProblem search problem in

searchAgents.py$.$ You will need to choose a state representation that encodes all the

information necessary to detect whether all four corners have been reached. Now, your search agent should solve:

python

pacman.py $-$l tinyCorners $-$p SearchAgent $-$a fn$=$bfs$,$prob$=$CornersProblem

python

pacman.py $-$l mediumCorners $-$p SearchAgent $-$a fn$=$bfs$,$ prob$=$CornersProblem

To receive full credit, you need to define an abstract state representation that does not encode irrelevant information $($like the position of

ghosts, where extra food is$,$ etc.$).$ In particular, do not use a Pacman GameState as a search state. Your code will be very, very slow if you

do $($and also wrong$).$

Hint: The only parts of the game state you need to reference in your implementation are the starting Pacman position and the location of

the four corners.

Our implementation of breadthFirstSearch expands just under $2000$ search nodes on mediumCorners. However, heuristics $($used with A$*$

search$)$ can reduce the amount of searching required.