Pac-Man is a completely deterministic game. As
shown in my last video on the game, all of the ghosts' movements are based off of where Pac-Man
currently is in the maze. Therefore, with the right knowledge, you can predict exactly where
any of the ghosts will move at any time. Or can you? When Pac-Man eats a power pellet, the ghosts
become frightened and seem to move in a random, unpredictable pattern. This is the only time
a random number generator is used in the game: to determine which direction a ghost will turn
at an intersection in the maze while frightened. While still deterministic, it is the
only non-predictable element of Pac-Man. This video will go under a deep analysis of
the game's RNG function, and how the ghosts tend to behave in this situation. We'll find
that frightened ghosts do tend to gravitate towards a certain section of the maze after
all. The random number generator, or RNG, is responsible for, well, generating random
numbers. The processor running the game's code doesn't have a little coin to flip or a dice
to roll to get any source of randomness, so this feature has to be programmed via software. And
it turns out that writing a program or a function to come up with numbers randomly is quite
difficult--you could argue it is impossible. Writing code to generate random numbers is
essentially like creating a list of instructions on how to calculate a certain value. In that case,
it isn't truly random--it's still deterministic. However, the end result looks random enough
that it can be treated as if it really were random--pseudo-random if you will. Pac-Man has
a very basic RNG function, but with a twist. There is a 16-bit value in memory that is treated
as the RNG index. This is set to zero at the start of the game, and at the start of each level. This
index is used as a seed value to generate the next index, which overwrites the old one. For example,
the very first index generated is the number 1. The RNG function takes the number 0 as
its input, and outputs the number 1. Then, the next time a random number is needed,
it uses the number 1 as its input. In this case, if 1 is its input, the output will be the number
6. Like I said, the rule is very simple. We take the input index, multiply it by 5, and add 1.
That's it! Well, and also modulo by 8192. Which just means, if the result is greater than 8192,
divide it by 8192 and then take the remainder. For example, the eighth RNG index is 7544. If
we multiply that by 5 and add 1, we get 37721. Divide that by 8192 to get 4 with a remainder
of 4953. So the ninth RNG index is 4953. This function does an alright job at generating
random numbers. There are times where it's quite obvious what the pattern is (especially at the
start with 0, 1, 6, 31), but most of the time it's fine. What's important though is the distribution
of the numbers. Are all numbers equally likely to be generated? It turns out that, yes, they are.
At least all numbers less than 8192 of course. This function will run through all 8192
numbers between 0 and 8191 before it repeats. The last number in the pattern being 4915. This
is a good quality for an RNG function to have, since it means that there is no bias towards
certain outputs. At least at a single, random access. (There may be strong correlations
if you want to generate more than one random number at a time, but that's not going to
be a problem for us for multiple reasons.) However, notice that I have been calling these
RNG indices, and not the RNG outputs themselves. That's because this index is not the true
output of the function. It's just a helper value that is used to create the output. This
index is used as an offset into the game's code to grab a single byte--that's the output.
It's not an index into a table of any sorts either. The first 8192 bytes of the assembly
code of Pac-Man is used as the RNG output. Most of the bytes here are machine code that
represents the assembly instructions that make up the various functions in the game's code--none
of which have anything to do with random numbers. Here's an analogy: suppose you were told
to come up with a random English word. It would be like using the same function for the
index here, but then using that index to look up a word in your favorite book. If your input index
was 6189, you'd calculate your output index to be 6370, so you'd find the 6370th word in the book.
While this method of looking up a byte definitely removes the correlation between successive random
numbers, it impacts the uniformity of the output. I mean, imagine how much more likely you are
to randomly pick the word "the" from your book! Here is a chart that displays how many of
each of the 256 different bytes there are in the first 8 kilobytes of the game's code. As
you can see, this is hilariously non-uniform. For a uniform distribution, each number
should appear 32 times. However, zero appears over 600 times. That's because
there's some empty spaces in the code, which are just filled with nothing but zeros. The
number 77 also appears a lot, even more than zero. This is because this corresponds to the byte
$4D, and the memory region from $4D00 to $4DFF is where most of the game's main variables are
held. So each instruction that wants to read or write to any of those variables is going
to make the byte $4D show up in the code. Some numbers just don't show up at all in the
first 8 kilobytes, like 65, 141, 146, and 186. Now, this may look bad, but fortunately
there's a catch that almost saves this. The only reason the RNG function is used is to
determine what direction a frightened ghost moves at an intersection. Well, there's only four
possible options: up, down, left, or right. This can be represented with only
two bits. The actual mapping of these bits to directions is 00 for right,
01 for down, 10 for left, and 11 for up. Because of this, the only part of the output of
this RNG function that's really important is the bottom two bits! So let's regroup all of these
outputs based only on their bottom two bits. Okay that's a little better, I guess? I mean the
last distribution set a really low bar to beat. You would expect a uniform distribution to output
each of the 4 options 2048 times out of 8192. While the 00 bits corresponding to "right"
are almost there, the others are just way off. The bits 11 corresponding to "up" are only
1338, which is just 16.3% of the total. This is one of two flaws of the frightened ghosts'
behaviors--the RNG function that governs their movement is not uniform. The directions
"left" and "down" are heavily biased for, while "up" is very heavily biased against.
So you'd think this would mean the ghosts would just favor the bottom left corner of
the maze then, right? Well not so fast... Real quick, in case you are interested,
here is the RNG function itself. Only 13 assembly instructions, that's how you know
its simple. Here is where the old index is loaded into the CPU. The index gets multiplied by five
here. And incremented by one. Here's the modulo by 8192--done by logically ANDing the upper 8 bits
of the index with $1F--essentially truncating the index to 13 bits. That index is used to grab a
byte from the game's ROM, and then the new index is stored to memory, overwriting the old one. It's
unfortunate that this function is found at $2A23 in the game's code, outside of the reach of the
RNG index which is limited to $1FFF. Which means the bytes that make up the RNG function can't
be themselves the output of the RNG function. So the frightened ghosts use the RNG output
to determine which direction to move at an intersection. What if they can't physically move
in that direction? Suppose a ghost was at this intersection, but the RNG told the ghost to move
up. There's a wall there, so what happens now? Instead of generating another random number,
the ghost will just try the next direction in a clockwise order. In this case, the
ghost will instead try to move right. But oops, ghosts can't turn around 180 degrees
either! This ghost approached the intersection from the right, so it can't choose to go right
here. This direction is no good, and it tries the next direction. It tries moving down next,
which is actually a valid direction to move. This results in a very biased decision. If the
ghost were to roll an RNG value that corresponds to "up", "right", or "down", they all correspond
to going "down". The only way a ghost can go left at this intersection if they are coming in from
the right is if "left" is chosen from the start. According to the chart we made earlier, this
would be a 29.9% chance. This leaves a whopping 70.1% chance for the ghost to choose to move
down. This is the second flaw of the frightened ghosts' behaviors--the allocation of random
numbers to directions is not uniform either. We can use this information to create a table
of probabilities for each intersection type. Since the RNG is biased itself, none of
these situations are symmetrical at all. First, it's worth pointing
something else out right now. Frightened ghosts don't call the RNG at just
the intersection tiles in the maze. They call the RNG every time the move from one tile
to another, even well inside the tunnels. Since the ghosts are blocked by walls on two
sides, and they can't turn around 180 degrees, there is only one valid direction to move.
This is actually somewhat notable, because by calling the RNG function even in these trivial
cases, it changes the RNG index value. This can help with shuffling up the index to prevent
any noticeable patterns from emerging (say, by observing which direction ghosts are moving
to predict which directions will be chosen next). But anyway. There are six types of tunnel
tiles--two straight tunnels and four corners. For each of these tiles, a ghost can enter it
from two different directions, which results in 12 possibilities. These 12 cases can be grouped into
four sets: one where "right" is the only valid option, one for "down", "left", and "up" as well.
Trivially, even though the distribution of random numbers results in this sort of distribution
of directions, the only valid direction is straight forward, and a ghost has a 100% chance of
continuing in the direction it was already moving. Where it gets interesting is the 3-way
intersections. There are four types of 3-way intersections, and a ghost could enter
from one of the 3 sides, which results in 12 more different cases. These can again be split
into sets corresponding to which two directions are actually valid. There are six of these sets,
and this is what the likeliness of a ghost turning in each direction is. Now, the two sets that are
split between two opposite directions aren't too bad. This is because each direction picks up the
weight of one of its neighboring directions. The most fair case is when a ghost has to pick between
moving up or down--a random direction of "left" or "up" results in a 46.3% chance of going up, while
a random direction of "right" or "down" gives a 53.7% of going down. The other four sets for
picking two adjacent directions are ridiculously lopsided though. They are all basically 3-to-1
odds for picking one direction over another. The worst offender is left versus up--a frightened
ghost only has a 16.3% of choosing to move up! Finally we have the 4-way intersection,
of which a ghost can enter from all four different directions. Here's what those
distributions look like. In all four cases, it is about twice as likely that the ghost will
turn left from its perspective in the maze. This is because the only invalid direction
is doing a 180 and backtracking--this gets rotated 90 degrees clockwise, which
corresponds to turning to the ghosts' left. Now how can we use this information to figure out
where the ghosts are more likely to go? I know this isn't a very practical question, since ghosts
don't get around very much while frightened, and in the later levels they don't become frightened
at all. But I think it could be a fun exercise. The best way to analyze this problem
in my opinion is with a Markov chain. If you don't know what a Markov
chain is, here is a quick overview. Suppose you have some sort of process that can
exist in one of several states. We can represent these states as a set of vertices in a graph. So
here we have three different states: A, B, and C. And in this process, at every step in
time, the current state can change. The probability of changing into a different state
is determined strictly by the current state. Let's say if you are currently in state A, you have a
50/50 chance of switching to state B or state C. We can represent these state transitions
as weighted, directed edges in this graph. Similarly, if you are in state B, you may
have a 30% chance of changing to state C, 60% chance of changing to state A, and
even a 10% chance of staying in state B. We represent this with a self-edge from B to B.
And so on. This is a Markov chain. We can sort of simulate an instance of this process here by, say,
starting in state A, and then moving from state to state based on the probabilities denoted by the
edges coming out of the node of the current state. Just do this like a million times and then
tally up how many times each state was visited, and you can find the average time spent in each
state. With a really large graph, this can take exponentially longer to converge on a meaningful
value though, so there is a better way to do this. We can start with a "mass" of 100 on state A,
and then divvy up the mass proportional to the outgoing edges on each vertex. In this case,
100 gets split up 50/50 to both states B and C. This leaves state A empty with zero, since states
B and C were previously empty. Then on the next step, State A has 0 mass so it doesn't give out
anything. State B gives 60% of its 50 to state A, 30% to state C, and keeps 10% to itself. While
State C gives 30% to state A, 50% to state B, and keeps 20% to itself. With this step, now state
A has a mass of 45, state B has 30, and state C has 25. Keep stepping through time like this and
eventually the numbers will converge on a steady state fairly quickly (as long as the chain is a
special kind of chain known as "ergodic" which isn't important to explain in this video, but you
can look up more about it if you're interested). The fun thing though, is that, if the Markov
chain is ergodic, then this is the steady state of the chain; it doesn't matter what the initial
conditions were. We started with a mass of 100 on state A, but we could start with a mass of 100
on state B or state C, and we would arrive to the same steady state. So what we can do, is build
a Markov chain that represents each intersection in the Pac-Man maze as a vertex in the graph,
and the edges will be the paths between them. The weights of the edges will be the
biased probabilities that I showed earlier. Then we can plop down a mass of 100 frightened
ghosts anywhere in the graph and iterate the whole thing over and over until we reach a steady
state. This will essentially give us a heat map of where the frightened ghosts like to hang out
in the maze. So, let's do it! It shouldn't be too hard. Since the tunnels between the intersections
are somewhat superfluous, I'll omit them at first. I'll add them back in later once we understand
what's going on and we know everything is working properly. First, we can make one vertex in
our graph for each intersection in the maze. We'll need two edges for each path
between them, one for each direction. Then all we need to do is fill in all the edge
weights with the RNG direction probabilities, right? Well, not so fast. Let's
look at a single intersection. This vertex has three edges coming out of it,
representing the three directions a ghost can move out of this intersection. But we know
that a ghost cannot turn around 180 degrees. When a ghost enters a 3-way intersection, it
really only has two choices to go, not three. This is because we haven't captured the entire
state of a ghost with our vertices. Not only do they need to represent the position of the ghosts
within the maze, they also have to encode which direction they are traveling too. This means
that each intersection in the maze needs a set of vertices corresponding to it--one for each
direction the ghost can approach the intersection. Three-way intersections will have three
vertices and 4-way intersections will have four vertices each. I'll put little
arrows inside to make it clearer. Now we can hook up the edges properly. If a
ghost is approaching this intersection from the right, this will be represent by this
vertex, since the ghost is moving left. If approaching from the left, this vertex, and
approaching upwards, this one. Now the outgoing edges. If the ghost is approaching upwards,
it can go either left or right. From the left, it can continue moving right, or go down. And from
the right, it can go down, or move on to the left. Now we can apply the edge weights with
the percentages calculated earlier. A ghost entering this intersection from the right
can go left with 30% chance, and down with a 70% chance. And so on, you get the idea. You can also
see that having these intersections split into multiple vertices allows the different approach
directions to affect the direction probabilities. Here the ghost has a 70% chance of going down
if entering from the right, but if entering from the left, it only has a 29% chance. We just
have to break down each intersection like this. This is a lot more complicated, but this is due
to the restriction that the ghosts just can't go backwards. Now, before we calculate the steady
state, we need to add the straight paths back in. We can't just ignore them completely because the
distance between every intersection isn't equal. A ghost will spend a longer time in a longer
path, like those at the bottom of the maze, simply because they take longer to
traverse. So what we really need to do is represent each tile in the maze as a
set of vertices, not just each intersection. This is pretty trivial to do, since a
ghost can only move forward in a tunnel. Each tunnel tile will have two vertices associated
with it, one each for what direction the ghost is moving. Then, we just connect each of the
directions together with a probability of 1. Essentially what this does, is forwards all of
the ghosts that turned a certain direction at one intersection to the next intersection
without allowing them to turn around. It also delays them from reaching the next
intersection proportional to the length of the path between the two intersections. But now we can
finally simulate the frightened ghosts' behavior with this behemoth of a Markov chain. For the
sake of this video, I am going to simplify what this graph looks like. Since we are ultimately
interested in where the ghosts are in the maze, we don't really need to know what direction
they are moving. Therefore, I am going to take all of the vertices that correspond to each
tile and group them up into these meta-vertices. The mass of these meta-vertices is just the
combined mass of the vertices inside of it, which represents how many ghosts are currently
on this tile, regardless of what direction they are facing. And I'm not showing the edges of the
graph anymore because it's pretty intuitive that adjacent vertices in the maze connect to each
other. Now, instead of plopping down 100 ghosts in a single tile, I'm going to put 50 ghosts
each on the two tiles right by the ghost house. For each tile, 25 will be facing left, and
25 will be facing right. If you know why this might be important, or want to give your best
guess, post about it in the comments! Anyway, here we go! The ghosts slowly disperse throughout
the maze. Since I picked 100 ghosts, the mass for each tile represents the percentage of the time
you will find a frightened ghost on said tile. You're more likely to find a ghost at an
intersection as opposed to a tunnel just because there are more ways to approach
those tiles, but you might be able to see that there is another pattern appearing. The
distribution appears not to be symmetric at all! I know at the start I said to hold on, the ghosts
might not just favor the bottom left of the maze, but it turns out that is exactly the case.
In fact, a frightened ghost is six times more likely to be found in the bottom left as
opposed to the top right. That is, if given a large enough amount of time, which is way longer
than you would ever experience in-game, but hey. Now, what is the root cause for this bottom-left
bias? Remember, there were two flaws to the ghosts' behavior. With this Markov chain, we can
tinker with the probabilities and separate and isolate those two different properties
and see what kind of affect they have. First, lets start with fixing both problems.
Here I'll set the probabilities of choosing a direction to be a perfect 50/50
split at all 3-way intersections, and a perfect 1/3 chance for each direction at
a 4-way intersection. Simulating this maze, we see that the distribution of ghosts is pretty much
uniform. Like I mentioned before, ghosts would be more likely to be at an intersection just due to
having more ways to approach the tile. This also shows that one of these two flaws is definitely
the culprit. Let's fix the RNG function first. Here I'll change the probability of a ghost
rolling one of the four directions to be a perfect 25% chance each. The ghost will still pivot that
option 90 degrees if it would move backwards or turn into a wall, meaning that some intersections
are still split 75 to 25. It looks like the ghosts still prefer the bottom left corner, but not
by as much. This sort of makes sense. Yes, the method of pivoting the direction to take
is heavily biased to turning left, but it is rotationally symmetric. Each biased movement
rule is part of a set of four rules that are 90 degrees apart from one another, and they should
all cancel out over time. The only reason they don't completely cancel out is because the maze
itself isn't 90 degrees rotationally symmetric. This produces small biases in certain locations
just due to the shape of the maze itself. Now let's see if we isolate the other variable.
In this case, I kept the biased RNG function, but removed the rule about pivoting the direction.
If the ghost rolls a direction that would make it hit a wall or turn around backwards, it
rolls again until it picks a valid direction. Aha, here's the culprit! In fact, this ends with
an even worse distribution than the unmodified version. The pivoting mechanic allows for a chance
to "break free" from the bias of the RNG function. For example, at this intersection, since
a ghost approaching from the left can't go back to the left, normally, if it rolls
a "left", it will end up going up instead. Even though "up" has the worst odds on
its own, the fact that left is blocked practically triples the probability a ghost will
turn up here. Without this boost, a ghost only has a 23% chance instead of a 46% chance of
going up. This makes it very unlikely that a ghost will hang out at the top of the maze for any
substantial amount of time in these circumstances. Finally, I just want to make sure, is this
all accurate? Markov chains are cool and all, but was this a proper way to represent the
behaviors of the frightened ghosts? Well, there's only one way to find out. Instead of simulating
in a sandbox, let's try running the actual game! Only a minimal amount of tinkering with the game
will make this easy to test. Just force the ghosts to always be frightened, and move Pac-Man out
of bounds so that he can't eat any of them. Then, I'll just let the ghosts do their thing and
sample their positions every few minutes or so. Speed up the game up as fast as I can
make it go, and have it run for hours. After recording thousands of data points of
where the ghosts are, we can plot a heat map out of it. Here's what my results were. And hey,
that's shockingly similar! It turns out math is useful after all. But is it really? The only way
we can realize this bias is by making the ghosts frightened for way longer than they were intended
to be. In reality, the main factor that determines where a frightened ghost is in the maze, is where
the ghost is when Pac-Man eats the power pellet. I think the more meaningful rule to come away with
this is: frightened ghosts prefer to turn left from their point of view. The only exceptions
to this are when they are moving to the right into a wall, where they will slightly prefer
turning to their right to go down, and when they are moving downwards into a wall, where they
will slightly prefer turning right to go left. And then ultimately, none of this information
matters at all in the later levels, since ghosts overcome their fears and no longer become
frightened even after a power pellet is eaten. Thank you for watching! This episode of
Retro Game Mechanics Explained was made possible by supporters of the channel via
Patreon. If you would like to help support the video-making process, you can become a
patron for as little as one dollar a month. Patrons get early access to videos as
well as behind the scenes content such as creator commentary. I appreciate
every little bit I get, so thank you!
