# Install uv once
curl -LsSf https://astral.sh/uv/install.sh | sh

# Optional: `uv` binary by default goes to `$HOME/.local/bin` on Linux/macOS,
# so you may need to add it to your PATH (uv may have done this for you):
export PATH="$HOME/.local/bin:$PATH"

# Install uv once
powershell -ExecutionPolicy ByPass -c "irm https://astral.sh/uv/install.ps1 | iex"
# Then open a NEW terminal window so that `uv` is on your PATH

# Download the homework zip and unzip into `hw5_pacman/`
# In your hw directory (it ships with a pyproject.toml pinned to Python 3.12)
uv sync                   # Create .venv, fetch Python 3.12 if needed, install numpy
uv run python grader.py   # Run the local grader

Pac-Man, now with ghosts.
Minimax, Expectimax.

For those of you not familiar with Pac-Man, it's a game where Pac-Man (the yellow circle with a mouth in the above figure) moves around in a maze and tries to eat as many food pellets (the small white dots) as possible, while avoiding the ghosts (the other two agents with eyes in the above figure). If Pac-Man eats all the food in a maze, it wins. The big white dots at the top-left and bottom-right corner are capsules, which give Pac-Man power to eat ghosts in a limited time window, but you won't need to worry about them until Problem 4. You can get familiar with the setting by playing a few games of classic Pac-Man, which we come to just after this introduction.

In this assignment, you will design agents for the classic version of Pac-Man, including ghosts. Along the way, you will implement both minimax and expectimax search.

The base code for this assignment contains a lot of files, which are listed towards the end of this page; you, however, do not need to go through these files to complete the assignment. These are present only to guide the more adventurous amongst you to the heart of Pac-Man. As in previous assignments, you will only be modifying submission.py.

We've created a LaTeX template here for you to use that contains the prompts for each question. If you use Overleaf, also upload pacman_multi_agent.png and minimax_depth.png from the zip, since the template includes them.

What to Submit

• Written: a PDF of your answers, typeset in LaTeX using the template above, submitted to the written assignment on Gradescope. Tag all pages correctly.
• Programming: only your submission.py, submitted to the programming assignment on Gradescope. Upload the file itself, not a zip or folder, and check that the autograder results appear.

Important Note: Please Read!

The grader.py included is useful to verify whether or not your solution crashes due to bugs or to verify Pac-Man behavior, but will not give reliable information on whether your submission will time out on any of the tests. We included a number of 0-point basic tests that will replicate the behavior of the hidden tests, but only give feedback on whether or not your solution times out. To properly ensure that your implementation will not time out, please make sure to do test submissions on Gradescope and observe the results on these 0-point tests.

First, play a game of classic Pac-Man to get a feel for the assignment:

uv run python pacman.py

Now, run the provided ReflexAgent in submission.py:

uv run python pacman.py -p ReflexAgent

uv run python pacman.py -p ReflexAgent -l test_classic

uv run python pacman.py -p ReflexAgent -k 1

uv run python pacman.py -p ReflexAgent -k 2

Note: You can never have more ghosts than the layout permits.

Options: Default ghosts are random; you can also play for fun with slightly smarter directional ghosts using -g DirectionalGhost. You can also play multiple games in a row with -n and an integer indicating the number of games to play. Turn off graphics with -q to run lots of games quickly.

Now that you are familiar enough with the interface, inspect the ReflexAgent code carefully (in submission.py) and make sure you understand what it's doing. The reflex agent code provides some helpful examples of methods that query the GameState: A GameState object specifies the full game state, including the food, capsules, agent configurations, and score changes: see submission.py for further information and helper methods, which you will be using in the actual coding part. We are giving an exhaustive and very detailed description below, for the sake of completeness and to save you from digging deeper into the starter code. The actual coding part is very small -- so please be patient if you think there is too much writing.

Note: If you wish to run the game in the terminal using a text-based interface, check out the terminal directory.

Note 2: If the action tiebreaking is done deterministically for Problems 1, 2, and 3, running on the medium_classic map may cause mostly losses. This is alright since the grader test cases don’t run on these layouts.

Problem 1: Minimax

1. Before you code up Pac-Man as a minimax agent, notice that instead of just one ghost, Pac-Man could have multiple ghosts as adversaries. We will extend the minimax algorithm from class, which had only one min stage for a single adversary, to the more general case of multiple adversaries. In particular, your minimax tree will have multiple min layers (one for each ghost) for every max layer.
   

   Formally, consider the limited depth tree minimax search with evaluation functions taught in class. Suppose there are $n+1$ agents on the board, numbered $0, \ldots, n$, where agent $0$ is Pac-Man and the rest are ghosts. Pac-Man acts as a max agent, and the ghosts act as min agents. A single depth consists of all $n+1$ agents making a move, so depth 2 search will involve Pac-Man and each ghost moving two times. In other words, a depth of 2 corresponds to a height of $2(n+1)$ in the minimax game tree (see diagram below).

   

   The diagram draws two branches per node to keep it readable. In the actual game, each node has one branch per legal action of the agent whose turn it is: up to four (North, South, East, West), and fewer when walls block the way.

   Comment: In reality, all the agents move simultaneously. In our formulation, actions at the same depth happen at the same time in the real game. To simplify things, we process Pac-Man and ghosts sequentially. You should just make sure you process all of the ghosts before decrementing the depth.

   Before diving into the recurrence, let's understand our notation. In the recurrence for $V_{\text{minmax}}(s,d)$, $s$ represents the current state, and $d$ represents the current depth in the game tree, with $d = d_{\text{max}}$ indicating the root of the tree (initial state) and decreasing as we go deeper into the tree.

   Write the recurrence for $V_{\text{minmax}}(s,d)$ in math as a piecewise function. You should express your answer in terms of the following functions:
   • $\text{IsEnd}(s)$, which tells you if $s$ is an end state.
   • $\text{Utility}(s)$, the utility of a state $s$, which is invoked at the end states.
   • $\text{Eval}(s)$, an evaluation function for the state $s$.
   • $\text{Player}(s)$, which returns the player whose turn it is in state $s$. Ensure you specify conditions like $\textrm{if}~ \text{Player}(s) = 0$ clearly.
   • $\text{Actions}(s)$, which returns the possible actions that can be taken from state $s$.
   • $\text{Succ}(s,a)$, which returns the successor state resulting from taking an action $a$ at a certain state $s$.
   You may use $n$ anywhere in your solution without explicitly passing it in as an argument. You should not have $d_{\text{max}}$ in your solution. Please stick to notations and terms as described here, and avoid introducing personal variations without clear definitions. Remember, clarity is essential. You may use any relevant notation introduced in lecture.
   Hint: It will be helpful to review the depth-limited recurrence in the "Evaluation functions" part of the Games I lecture.
   The recurrence for $V_{\text{minmax}}(s,d)$ in math as a piecewise function, in terms of the functions listed above.
2. Now fill out the MinimaxAgent class in submission.py using the above recurrence. Remember that your minimax agent (Pac-Man) should work with any number of ghosts, and your minimax tree should have multiple min layers (one for each ghost) for every max layer.
   Your code should be able to expand the game tree to any given depth. Score the leaves of your minimax tree with the supplied self.evaluation_function, which defaults to score_evaluation_function. The class MinimaxAgent extends MultiAgentSearchAgent, which gives access to self.depth and self.evaluation_function. Make sure your minimax code makes reference to these two variables where appropriate, as these variables are populated from the command line options.
   An implementation of the MinimaxAgent class in submission.py.
   Implementation Hints
   • Read the comments in submission.py thoroughly before starting to code!
   • $\text{Utility}(s)$ should be the final game score, returned from GameState.get_score.
   • The evaluation function for this part is already written (self.evaluation_function), and you should call this function without changing it. Use self.evaluation_function in your definition of $V_\text{minmax}$ wherever you used $\text{Eval}(s)$ in part $1a$. Recognize that now we're evaluating states rather than actions. Look-ahead agents evaluate future states whereas reflex agents evaluate actions from the current state.
   • Keep in mind that the recurrence from 1a gives the value of a state, while get_action must return an action.
   • Pac-Man is always agent 0, and the agents move in order of increasing agent index. Use self.index in your minimax implementation to refer to Pac-Man's index. Notice that only Pac-Man will actually be running your MinimaxAgent.
   • All states in minimax should be GameStates, either passed in to get_action or generated via GameState.generate_successor. In this assignment, you will not be abstracting to simplified states.
   • You might find the functions described in the comments to the ReflexAgent and MinimaxAgent useful.
   • If there is a tie between multiple actions for the best move, you may break the tie however you see fit.
   • The minimax values $V_\text{minmax}$ of the initial state in the minimax_classic layout are 9, 8, 7, and -492 for depths 1, 2, 3, and 4, respectively (passed into the “-a depth=[depth]” argument). If you forget -l minimax_classic, you will run on the default medium_classic layout instead, where the values are 9, 18, 27, and 36. You can use these numbers to verify whether your implementation is correct. To verify, you can print your calculated minimax value in get_action and check if the value of the initial state (first value that appears) is equal to the value listed above. Note that your Pac-Man agent will often win, despite the dire prediction of depth 4 minimax search, whose command is shown below. With depth 4, our Pac-Man agent wins 50-70% of the time. Depths 2 and 3 will give a lower win rate. Be sure to test on a large number of games using the -n and -q flags. Check the instructions in "Warmup" for more details on running multiple games in a row.

     uv run python pacman.py -p MinimaxAgent -l minimax_classic -a depth=4

   • Don't worry if your agent loses most games. The tests check your agent's moves and running time, not whether it wins. For example, on the small_classic setup used by 1b-0-basic and 2a-0-basic (two DirectionalGhosts, depth 2), our solution wins only about 10–15% of games.
   • One "depth" includes Pac-Man and all of the ghost agents.
   Further Observations

   These questions and observations are here for you to ponder upon; no need to include in the write-up.

   • On larger boards such as open_classic and medium_classic (the default), you'll find Pac-Man to be good at not dying, but quite bad at winning. It will often thrash around without making progress. It might even thrash around right next to a dot without eating it. Don't worry if you see this behavior. Why does Pac-Man thrash around right next to a dot?
     
     
     Click to see our thoughts!

     Part of the reason this happens is because there could be ties between different possible sequences of actions but no intelligent tie-breaking, as well as not having 'memory' of deciding to follow a sequence of actions. There could be other factors that also play into this as well.

Problem 2: Alpha-beta pruning

1. Make a new agent that uses alpha-beta pruning to more efficiently explore the minimax tree in AlphaBetaAgent. Again, your algorithm will be slightly more general than the two-player version from lecture, so part of the challenge is to extend the alpha-beta pruning logic appropriately to multiple ghost agents.

   You should see a speed-up: perhaps depth 3 alpha-beta will run as fast as depth 2 minimax. Depth 3 on medium_classic should take well under a tenth of a second per move:

   uv run python pacman.py -p AlphaBetaAgent -a depth=3

   To make sure your implementation does not time out on the hidden tests, check the results of the 0-point tests when you submit to Gradescope.

   The AlphaBetaAgent should compute the same minimax values as the MinimaxAgent, although it may choose different actions when there are ties. For the initial state, the minimax values are 9, 8, 7, and -492 on minimax_classic and 9, 18, 27, and 36 on the default medium_classic (the command above), for depths 1, 2, 3, and 4 respectively. You can check them by printing the value of the initial state in get_action. When comparing the speed of the two agents, use the same layout for both (for example, add -l minimax_classic to the command above).

   Prune only on strict inequality: stop exploring a node when its value is strictly greater than beta (at a max node) or strictly less than alpha (at a min node). Pruning on equality can change which of several equally good actions is chosen.

   An implementation of the AlphaBetaAgent class in submission.py.

Problem 3: Expectimax

1. Random ghosts are of course not optimal minimax agents, so modeling them with minimax search is not optimal. Instead, write down the recurrence for $V_{\text{exptmax}}(s,d)$, which is the maximum expected utility against ghosts that each follow the random policy (each ghost chooses a legal move uniformly at random).
   Your recurrence should resemble that of problem 1a (including the depth argument $d$), which means that you should write it in terms of the same functions that were specified in problem 1a.
2. Now implement your recurrence from 3a. Fill in ExpectimaxAgent, where your Pac-Man agent no longer assumes ghost agents take actions that minimize Pac-Man's utility. Instead, Pac-Man tries to maximize its expected utility and assumes it is playing against multiple RandomGhosts, each of which chooses from get_legal_actions uniformly at random.

   You should now observe a more cavalier approach to close quarters with ghosts. In particular, if Pac-Man perceives that it could be trapped but might escape to grab a few more pieces of food, it will at least try.

   uv run python pacman.py -p ExpectimaxAgent -l trapped_classic -a depth=3

   You may have to run this scenario a few times to see Pac-Man's gamble pay off. Pac-Man would win half the time on average, and for this particular command, the final score would be -502 if Pac-Man loses and 532 if it wins. You can use these numbers to validate your implementation. As you implement this, think about why Pac-Man's behavior as an expectimax agent differs from its behavior as a minimax agent (i.e., why doesn't it head directly for the ghosts?). We'll ask for your thoughts later, in Problem 5.
   An implementation of the ExpectimaxAgent class in submission.py.

Problem 4: Evaluation function

1. Write a better evaluation function for Pac-Man in the provided function better_evaluation_function. The evaluation function should evaluate states rather than actions. You may use any tools at your disposal for evaluation, including the helper functions in util.py.

   We will run your ExpectimaxAgent from Problem 3 with depth 2 and your evaluation function for 50 games on the small_classic layout against two random ghosts. To receive credit, your average score over all 50 games (wins and losses both count) must be at least 1000. For reference, the default score_evaluation_function averages well below 1000, so you will need to design your own features. All 50 games together must also finish within 60 seconds.

   You can watch your agent play, or run many games quickly, with:

   uv run python pacman.py -l small_classic -p ExpectimaxAgent -a eval_fn=better -q -n 50

   This prints the average score over all games, but on different random games each time. The local grader (test 4a-1-basic) runs a fixed set of 50 games and reports your exact score on them. The hidden test (4a-1-hidden) runs 50 different games, so make sure your evaluation function works well in general and not just on the public games.

   An implementation of better_evaluation_function in submission.py whose average score over 50 games is at least 1000.

   Hints and Observations

   • Make sure your ExpectimaxAgent from Problem 3 works first, since this problem uses it.
   • Having gone through the rest of the assignment, you should play Pac-Man again yourself and think about what kinds of features you want to add to the evaluation function. How can you add multiple features to your evaluation function?
   • You may want to use the reciprocal of important values rather than the values themselves for your features.
   • The game score changes as follows: +10 for each food pellet, +200 for each scared ghost Pac-Man eats, +500 for clearing the board, −500 for dying, and −1 for each move.
   • Do not call random.seed or otherwise change the state of Python's random module: the grader seeds each game itself.
2. Clearly describe your evaluation function. Your answer should cover:
   1. Features and form: which quantities from the GameState you used, and how you combined them (for example, weights or reciprocals).
   2. Motivation: why these features should lead Pac-Man to win with a high score.
   3. What didn't work: at least one thing you tried that did worse, and why you think it did.
   Please write your thoughts in the pdf file, not in code comments.
   4–8 sentences (or a short list) covering the three points above.

Problem 5: AI (Mis)Alignment and Reward Hacking

Before diving into the problem, it would be beneficial to refer to the AI alignment module to gain deeper insights and context:

• Video
• PDF

In this problem we'll revisit the differences between our minimax and expectimax agents, and reflect upon the broader consequences of AI misalignment: when our agents don't do what we want them to do, or technically do, but cause unintended consequences along the way. Going back to Problem 3, consider the following runs of the minimax and expectimax agents on the small trapped_classic environment:

uv run python pacman.py -p MinimaxAgent -l trapped_classic -a depth=3

uv run python pacman.py -p ExpectimaxAgent -l trapped_classic -a depth=3

Be sure to run each command a few times, as there is some randomness in the environment and the agents' behaviors, and pay attention, as the episode lengths can be quite short. You can always add --frame_time 1 to the command line so the game pauses after every frame. What you should see is that the minimax agent will always rush towards the closest ghost, while the expectimax agent will occasionally be able to pick up all of the pellets and win the episode. (If you don't see this behavior, your implementations could be incorrect!) Then answer the following questions:

1. Describe why the behavior of the minimax and expectimax agents differ. In particular, why does the minimax agent, seemingly counterintuitively, always rush the closest ghost (instead of the farther ghost), while the expectimax agent (occasionally) doesn't?
   1–2 sentences on why the minimax agent always rushes the closest ghost instead of the farther ghost, and 1–2 sentences on why the expectimax agent doesn't. Be sure to state the assumption minimax makes that causes this behavior.
   
   
2. We might say that the Minimax agent suffers from an alignment problem: the agent optimizes an objective that we have designed (our state evaluation function), but in some scenarios leads to suboptimal or unintended behavior (e.g. dying instantly). Often the burden is on the designer/programmer to design an objective that more accurately captures the behavior we want from the agent across scenarios. Suggest one potential change to the default state evaluation function $\text{Eval}(s)$ (i.e. score_evaluation_function) and/or the default utility function $\text{Utility}(s)$ (i.e. the final game score) that would prevent the minimax agent from dying instantly in the trapped_classic environment, and behave more closely to that of the expectimax agent.
   1-2 sentences describing a change in the state evaluation/utility function(s) and why it would work. No need to code anything up, verify that the suggested change is actually accessible in the GameState object, or give concrete numbers; just describe the hypothetical change in the functions. An answer which suggests changes to how the game score is computed itself (which both $\text{Eval}(s)$ and $\text{Utility}(s)$ depend upon) will also be accepted.
3. Pacman's behavior above is an example of one concrete problem in AI alignment called reward hacking, which occurs when an agent satisfies some objective but may not actually fulfill the designer's intended goals, due e.g. to an imprecise definition of the objective function. As another example, a cleaning robot rewarded for minimizing the number of messes in a given space could optimize its reward function by hiding the messes under the rug. In this case, the agent finds a shortcut to optimize the reward, but the shortcut fails to attain the designer’s goals (see [1] for more examples).
   
   Even if the agent does satisfy the designer's goals, another problem can arise (again see this paper): the agent's behavior might cause negative side effects that come in conflict with broader values held by society or other stakeholders. For instance, a social media content recommendation system might aim to maximize user engagement, but in doing so, spread disinformation and conspiracy theories (since such posts get the most engagement), which is at odds with societal values.
   
   Can you think of another example of either of these problems?
   In 2-5 sentences describe another realistic scenario (outside Pacman) in which a designer might specify an objective, but the objective is either susceptible to reward hacking, or the resulting agent/model causes negative side effects. Please state if your example is an instance of reward hacking or negative side effects (or both) along with a brief justification to receive full credit.

Go Pac-Man Go!

[1] For more examples of reward hacking (or "specification gaming"), see this article from DeepMind and this list of concrete examples of reward hacking observed in the AI literature.