implement an A* algorithm which will be used by Pac-Man, which at each step uses A* to nd the shortest path to a dot in the map, and starts moving in that direction. Design an appropriate heuristic, and make sure it is admissible. Implement a second version, which at each step uses A* to nd the shortest path to eat all the dots in the map (notice that the search space is much,much larger this time). Design an appropriate heuristic, and make sure it is admissible. For each PacManPlayer, evaluate the number of nodes it explores during the search (min, max, and average). As well as comparing it to when no heuristic is used (just run your PamManPlayer with a heuristic which always returns 0).
implement a Q-learning algorithm, to help Pac-Man learn how to play the complete game. This time, we will add ghosts to the game again. In order to implement Q-learning, the very rst thing you need is to decide on a suitable state space. Notice that if you try to have one state for each
possible conguration of the game state you would have an enormous number
of states and Q-learning would never converge (assuming you can hold the state
table in memory).