A Pacman Contest!

Our AI class has one final contest. We need to design and code Pacman agents to play against other student agents. The winner will claim all bragging rights!

Enough of defense.
Onto enemy terrain.
Capture all their food!

We are supposed to code a team that consists of 2 agents that work collectively (or separately, if you choose to) to win the game.

The map of the game is divided into 2 symmetric halves. One team starts in Red, the other in Blue. Each team must eat all the food (dots) in the opponent's half of the map, and protect food in their own half. If your agent is currently inside your own half, it will be displayed as a Ghost that can defeat invading Pacman agents. If it is inside the opponent's half, it will be displayed as Pacman, who is vulnerable to opponent ghosts. A defeated Pacman agent will respawn in it is initial starting position in its own half.

In this post, I will be describing my journey of developing my team of badass Pacman agents.

Names

The most difficult part is always coming up with good names for your agents. I googled the best duos in history, and combined the results with a few suggestions I came up with on my own. I ran a Twitter poll to ask for friend's input. Here are the voting results:

Twitter Poll Results

My favorites were Bonnie and Clyde, but I was having doubts. Although they did not get any votes, I am currently going with the Agent 47 and Subject 6 from Hitman, but that might be temporary.

Intro

We are provided 2 simple agent implementations for reference. The agents are an Offensive and a Defensive Reflex agents. A reflex agent is an agent that makes a greedy decision that maximizes its immediate gains. For example, if a reflex agent cares about eating food the most, it will always move toward the closest food.

Modifying the behaviour of a reflex agent is as simple as defining what "gain" is for that agent. Given some state of the game, an agent has at most 4 possible actions to take: Left, Right, Up, and Down. (It could be less than 4 if there were walls next to the agent). A reflex agent will calculate a score for each of the 4 actions, and will then choose to perform the action with the maximum score, to maximize its gain. How the agent calculates that score is what makes each reflex agent unique.

Calculating the score is usually done through defining a list of what is described as features. Each feature is basically a measurement for some element of the game. Examples of features are:

• Whether the position has food or not.
• Distance to closest food.
• Distance to closest opponent.
• Number of enemies.
• Number of food remaining.

When you have defined a set of features you care about, you assign a weight of importance to each feature. Your total score is the weighted sum of all features. Let me walk you through a simple example. The Offensive agent cares about eating food as fast as possible. Here is how its feature weights might look like:

• 100: Whether the position has food or not.
• -1: Distance to closest food.

The agent will examine all 4 (or less) possible actions, and calculate the score like follows: Suppose I go Left, if the new position has food, I will eat it and get 100 points, but depending on where the next closest food will be, I will lose 1 point for each step I will need to take toward it. This is repeated for all possible actions and the action that has the maximum score is carried out. So if the features for the actions looked like:

• Left: Has food, and distance to next closest food is 10.
• Right Does not have food, and distance to next closest food is 1.
• Up: Does not have food, and distance to next closest food is 100.
• Down: Has food, and distance to next closest food is 5.

The scores will be:

• Left: 100 * (1) + 10 * (-1) = 90.
• Right 100 * (0) + 1 * (-1) = -1.
• Up: 100 * (0) + 100 * (-1) = -100.
• Down: 100 * (1) + 5 * (-1) = 95.

The agent will choose to go Down, because it has the maximum score. Notice that the features and the weights convey the agent's goal of eating food as fast as possible. The Defensive agent, on the other hand, might define different features that convey bias toward defensive actions.

Uncertainty

The first issue I will have to deal with is uncertainty in some of the measurements in the game. The game puts some restrictions on agents' abilities to make the game more realistic, and less deterministic. For instance, an agent trying to read an opponent's position will not always get a correct reading. The game adds noise to the readings of opponent positions. For example, if an opponent is at position (4, 7) (Row 4 and Column 7), then the agent might get a reading that says (4, 9) or (3, 6), or some other reading that deviates from the true position by a small amount. If you are wondering how is this more realistic, well, it is easy to see that not all measurements in the world are accurate. Any sensor that measures something has an error rate, and that is what the game is trying to mimic. Each agent has a sensor for measuring opponent's distances, and that sensor makes a small error if the distance is larger than 5.

To account for this uncertainty in some of these measurements, I have used what is called a Markov Model. Without going into technical details, a Markov model basically allows you to have a probabilistic sense on where the ghost might be, by repeatedly answering the following 2 questions for each position the ghost might be in, on the map:

1. What is the probability that the ghost moved into this position given its previous position?
2. After you get a sensor measurement, how likely is it to get the reading you just got if the ghost is at this position?

If you are wondering what the previous position is, it is simply the position that we choose to believe the ghost is at each turn after we answer the 2 questions. Initially, we know where the ghost starts at, and after each turn, we will answer the 2 questions, and then decide that the ghost is probably at some position. Of course this is a probabilistic model, so it can be wrong.

From Chance to Glory

Random Agent

Without further due, I introduce you to my first agent. The Random agent! This agent simply goes in any direction randomly. This agent is guaranteed to lose against almost any smart opponent (and by smart I mean simply non random), but I wanted to set it up as a building block to my next agent.

My random agents (red team) VS the Offensive and Defensive agents (blue team).

You can see how my 2 agents (red and orange ghosts) go up and down randomly, while the opponent's offensive agent is eating dots at my half of the map, and their defensive agent is lurking back in their half, daring one of my agents to come close.
P.S., You might have noticed that the name of my team does not relate to the name of my agents. I know I should change it, but I will keep it this way for now.

Random Agent with Inference

Remember the uncertainty issue mentioned above? It is time to do something about it. I implemented a simple inference model. My agents are still moving randomly, but now they have a slightly better idea where the opponent agents are. The colored boxes in the following GIF represent my agents' beliefs of where the opponent agents might be. Notice how the beliefs for each ghost have different opacity. For the dark blue ghost, the red boxes show these beliefs. The more opaque the box, the higher the belief. Notice also how the boxes increase and decrease in number, that is because as the opponent moves, it could end up in many different positions, so my agents' beliefs decrease and expand to cover more positions the opponent might be in. Conversely, when my agents get a new noisy read of the opponents' positions, their beliefs grow larger.

My random agents have beliefs about opponent agent positions.

Copycat Agent

So far, my random agents were as useless as "ueue" in "queue". It is time to make them a little bit smarter. I started by copying the behaviour of the Offensive and Defensive agents, but remember, my agents can reason about their opponents' positions much better than their opponents can reason about theirs. My team wins around 8 of each 10 games using these agents, and that is a mere result of the probabilistic belief!

Offensive and Defensive agents with Inference

Fun Timeout

Here is a Tom and Jerry team I created on the side:

OffDef Agent

Looking at the Copycat Agent GIF, I can see at least two things wrong with my agents. Do you see any? For starters, my offensive agent (red) was closer to the opponent's dark blue agent than my defensive agent (orange) in the middle of the map. Instead of going back just a few steps to attack the opponent, it continued moving forward to get food, because that is what it cares about, food! The second issue is that my agents' beliefs about the dark blue agent after it respawned were all over the place, even though we know that the opponent agent has just been captured and therefore will respawn in its initial position. The agents should be 100% sure where a respawning opponent is.

The agent closest to the opponent's territory switches to offense. When the offensive orange agent was captured, the defensive red agent switched to offense.

Using the current agent, I was able to achieve the top place for a few days.

Leaderboard

What else can we do?