Most people are at least familiar with the video game Pac-Man. If not, then this is a piece of culture that you should be aware of and you can read about it at: https://en.wikipedia.org/wiki/Pac-Man
You can also find many free version of Pac-Man on the web if you want to try it out.
Your homework assignment is to write a short description of how Pac-Man can be modeled as an MDP. This requires that you clearly specify the state space , the action space , the transition function , and the reward function .
Note that specifying the transition function will require making some assumptions about how the ghosts move. For this purpose, your MDP model should assume that the ghost movement is controlled as follows.
When a ghost first enters the board from the center box it picks a direction at random and moves in that direction.
A ghost only changes directions when it reaches a wall.
When a ghost reaches a wall, it picks randomly among the possible directions and begins moving in the randomly selected direction.
Note that the actual movement of the ghosts in Pac-Man does not follow these rules, but you can assume these rules for the purposes of this assignment.
For the purposes of defining the reward function, you can assume that Pac-Man gets 1 point for eating a dot, gets 100 points for eating a ghost, and 1000 points for clearing a board and moving to the next board. You can assume that no additional points are possible.
Produce a SHORT write-up about your MDP. You should use your discretion regarding the level of detail to provide for the transition function. You should indicate any details that are omitted for brevity and it should be clear that those details could easily be defined.
