Autoplaying Pac-Man
Final Project Writeup
Scott "Jerry" Lawrence
jsl@absynth.com
Office 76-2116
20 May 1999
This document is available online at
<http://www.cis.rit.edu/~sdlpci/autopac>
Table Of Contents
- 1.0 Project Summary
- 1.1 Abstract
- 1.2 Rules of Pac-Man
- Figure 1: Ghost Names
- Figure 2: Pellet Points
- Figure 3: Edible Ghosts
- 1.3 Variants
- Figure 4: Puck-Man
- Figure 5: Pac-Man
- Figure 6: Piranha
- 1.4 Past Work
- MAME - Multiple Arcade Machine Emulator
- 2.0 Problem Definition
- 2.1 Goals
- 2.2 Limitations
- 3.0 Approach
- 3.1 Modifications To Pac-Man Game Program
- 3.2 Modifications To MAME
- 3.2.1 V-Blank Additions
- Figure 7: Sample GAMAME screen
- 3.2.2 Game State Gleaning
- Figure 8: Pac-Man "READY!"
- Table 1: Game state transitions
- 3.2.3 Move Injection
- 3.2.4 Emulator User Interface
- Figure 9: MAME Menu System
- Figure 10: My GA Controls
- 3.3 Genetic Algorithm Subsystem
- 3.3.1 Subsystem Interaction
- Chart 1: Flowchart of a full run
- 3.3.2 Fitness Calculation
- 3.3.3 Individuals
- 3.3.4 Child Generation
- 4.0 Results
- 4.1 Summary and Expected Results
- Table 2: Game Results
- 4.2 Single Point Crossover
- Graph 1: 1-Point, 10 Member Population
- 4.3 Double Point Crossover
- Graph 2: 2-Point, 10 Member Population
- Graph 3: 2-Point, 10 Member Population
- 4.4 Uniform Crossover
- Graph 4: Uniform, 10 Member Population
- 5.0 Future
- 5.1 Goals
- 5.2 Bugs With The Current System
- 6.0 Research References
1.0 Project Summary
1.1 Abstract
The Pac-Man arcade game was introduced to an arcade-game hungry crowd by
Namco & Midway in 1980. It has been a favorite of arcade gamers ever since.
Until recently, the only way to play it was to find someplace that had the
game still intact, usually a bowling alley, or Chuck-E-Cheese, and play it
there. Within the past 3 years however, there has been a boom of programmers
writing emulators to play these games on home personal computers. Generally
the programmers of these emulators also release the source code so that
people not working directly on the project can find out information about the
arcade games being emulated.
The game of Pac-Man is quite simple. Most, if not all, of the game
information being displayed on the screen at any one time. The state of
the game can be gleaned by looking at the screen, and the input to move
the character along the screen can be inserted into the emulator's command
structure. The information to insert can be determined from a Genetic
Algorithm.
This is similar in essence to the "rogue-o-matic" program from years ago,
which played the game Rogue by looking at the TTY output from it.
That is basically what I have done in this project, but for Pac-Man.
1.2 Rules of Pac-Man
 |
 |
| Figure 1: Ghost Names |
Figure 2: Pellet Points |
Pac-Man is a very simple game. It consists of a yellow circular character
named "Pac-Man", and four ghosts named "Blinky", "Pinky", "Inky" and "Clyde".
They can be seen in figure 1.
The game player must navigate Pac-Man around the maze on the screen, eating
up all of the 244 beige pellets for 10 points apiece, and the four larger
power pellets in each of the four corners of the screen for 50 points apiece.
These can be seen in figure 2.
 |
| Figure 3: Edible Ghosts |
If Pac-Man encounters a ghost, they kill him. However, if Pac-Man eats one
of the power-pellets, (figure 2) he can then eat the ghosts for
200, 400, 800, and 1600 points for each one sequentially eaten.
(figure 3) They are only vulnerable to this for a few seconds
after eating the power-pellet, after which they start chasing after Pac-Man again.
1.3 Variants
 |
 |
| Figure 4: Puck-Man |
Figure 5: Pac-Man |
 |
| Figure 6: Piranha |
Namco and Midway released a few different versions of the game. These different
versions are called "variants". There are also bootlegged versions made without
permission from other companies. Shown in figure 4 is one of the
variants, and arguably the first Pac-Man version to be released, called "Puck-Man".
Most Pac-Man
variants have an extensive power-up self test or POST, but this one has a very
quick one, implying that they hadn't written that test completely yet. It also
has a more complex and harder map than standard Pac-Man, as seen in figure
5.
Just to show other variants, see figure 6. It is a from
the game "Piranha", which may be a bootlegged version of Pac-Man. Not much is
known about it, other than it differs from Pac-Man in that the maze and graphics
are different, and not much else.
1.4 Past Work
Luckilly, this project was not the first to try something like this. If you
look at the project, "Pac-Tape", you will see a brute force attempt at
finishing Pac-Man boards. It works, somewhat, but it does have its problems.
It is very slow, and is not very robust. It has a single way to solve
the problem, and nothing else.
[Gulger]
1.5 MAME - Multiple Arcade Machine Emulator
MAME is an emulator which first appeared about 2 years ago in May of 1997,
supporting only
Pac-Man, a few variants, and a few other games that worked on the same
hardware. Since then, it has been widely supported by programmers to enhance
its performance, port it to different computers, and add in other games. The
support team probably consists of about 100 people now, and the emulator
supports over 1,300 games.
The latest version (v0.35 beta 12)from earlier this month takes about 2 hours to
compile on my Pentium 133 running Windows 95 down to a 6.5 megabyte executable.
[Buffoni]
Pac-Tape was last updated around January of 1998, and used MAME version 0.28.
Luckilly, there are archives online of the older MAME versions.
Springtime of last year, I had made a modified version of the MAME source and
executable for a friend in Europe, to help him debug his Pac-Man modification.
This used MAME version 0.30. It is on this source body that I have built my
Genetic Algorithm Pac-Man Emulator.
[Lawrence]
Since I had experience with both of these source bodies, I was able to add onto
this MAME source, both self-designed code, and some code borrowed from the
Pac-Tape project to produce this final version which I have now. It was not
necessary to use the latest version of MAME, as the emulation core used for
the Pac-Man games has not been touched for well over a year anyway. It would also
have taken a significant amount of time and effort to trim down the latest
executable to something more manageable.
The executable I'm using takes about 2 minutes to compile, and is only around 250kb.
2.0 Problem Definition
2.1 Goals
The goal of this project is to write a Genetic Algorithm system that will sit
in the MAME emulator, that will learn good patterns (movements of the Pac-Man
character in the game) to solve each level of the game. Different population
sizes of movement strings, crossover methods, and mutation amounts should be
employed to be applied to the population manipulations. The deterministic
characteristic of Pac-Man will help us to find good strings without having
to deal with the random element of the game, since there is none.
2.2 Limitations
When working on this, I decided that I did not want to modify any of the
game program that dealt with game play or performance at all. I wanted
the GA routines to find strings of movements that can be used on the real
arcade machines, if someone was patient enough to learn them.
3.0 Approach
3.1 Modifications To Pac-Man Game Program
I originally
was going to modify the game roms to skip over the POST in the beginning of
the rom, but I eventually opted to not do this, as I didn't have the time
or the knowledge to do so.
Therefore all of the modifications done are on the MAME emulator itself.
The game program roms used are of the original unmodified game.
3.2 Modifications To MAME
 |
| Figure 7: Sample GAMAME screen |
3.2.1 V-Blank Additions
After each time the emulation draws the screen, there is a routine that gets
run, to update the emulation state. I tapped into this so that the GA routines
states could be kept in sync with the emulation. It is in here that I check
to see if a decision should be made for the input injection, as well as displaying
on-screen statistics about the state of the GA routines.
My modified emulation of Pac-Man can be seen in figure 7 above.
On the top line you see some information in cyan.
First on the line is the game state. In this example, it is "PLAY", meaning
that the
emulation is running through an input string to determine its fitness.
Next is a "1", meaning the first board. If Pac-Man clears this board, that
will increment to "2", and so on.
Next is a "88", showing the number of input steps used so far in this run.
That is to say that the decision routine has determined 88 times that there
can be a direction change input to the system.
Next is "G0", showing that generation 0 is currently being tested. Once all
of the individuals are tested in a generation, then children are produced,
and this number is incremented.
Next is "I08 20", showing that out of a population size of 20, individual
number 8 is currently being tested.
On the next line are four elements. The first of which is the white number
1980.
This is from the Pac-Man game itself. That is the score so far for this run.
Next in orange are two numbers. These are (from left to right) the previous
individual's score, and the best score so far. The prior of these two is not
necessarily of any real use.
Next are the letters "WSNE" in various colors. These show the decision making
of the routines. Letters in red show directions that Pac-Man can move to from
his current location. The letter in Cyan shows where he has decided to move.
In the snapshot above, Pac-Man can move West and East, and he has decided to
move East from his current position.
3.2.2 Game State Gleaning
 |
| Figure 8: Pac-Man "READY!" |
The state of the game can be gleaned by looking on the screen.
Table 1 below
shows the state machine I used for this project. I got the state information
from the screen data. For example you look at a certain memory address in
the emulation, and look for the text string "READY!". An example of this can
be as seen in figure 8 above. Most of the code to do
this was copied from the Pac-Tape project as described above, but modified to
work for the Pac-Man variants.
| State Name |
Next State |
Transition When? |
| none |
BOOT |
Emulation reset or initialization |
| BOOT |
TEST |
Crosshatch pattern on screen |
| TEST |
DEMO |
Attract sequence starts |
| DEMO |
START |
Coin is inserted into machine |
| START |
READY |
Start button is pressed |
| READY |
PLAY |
The "READY!" Text is not on screen anymore |
| PLAY |
WIN |
Pac-Man completes eating all of the pellets in the maze |
| PLAY |
DIE |
Pac-Man gets eaten by a ghost |
Table 1: Game state transitions
3.2.3 Move Injection
There are two injection routines used, one for each "port" in the Pac-Man
hardware. The first is used just for the coin and start buttons, and is
triggered based on the state of the game system.
The second routine is for the movement inputs. This one just increments
a counter, then uses that as an index into the current injection string.
Once it has a movement from that list, it checks it against the currently
available moves. If it can't make the move it just popped off of the list,
then it increments the index, and goes for the next one, and so on until it
finds a move it can do.
3.2.4 Emulator User Interface
 |
 |
| Figure 9: MAME Menu System |
Figure 10: My GA Controls |
It was necessary to have some way of changing the parameters for the GA
subsystem without recompiling. The above is the interface added in to
accomplish just that.
Figure 9 shows the standard MAME configuration menu, which
the user can get to by hitting the [TAB] key. My menu is the bottom-most
element in the top part of the list, "GA Settings". If that is selected,
then the user is brought to the menu as seen in figure 10.
From there, they can adjust the population size, crossover style, enable
and disable mutations and on-screen display. The bottom element is
labelled "Changes". When no changes are made, this displays "set" for
its value. Once a change is made, this changes to "commit". The user
must manually commit their changes, so that they don't accidentally
change a parameter, potentially damaging their results.
3.3 Genetic Algorithm Subsystem
3.3.1 Subsystem Interaction
 |
| Chart 1: Flowchart of a full run |
In the flowchart shown in chart 1 above, we can see that the
GA routines have been shoved into the flow of the MAME emulator.
Not shown in this flowchart are the GA controls menu, and the de-init
procedures for shutting down the system.
3.3.2 Fitness Calculation
Currently, the fitness is the score achieved in a game. Other calculations
to be used could factor in the length of the string, to try and find the
most efficient method to finish the game. Also, there could be penalties
calculated in based on if Pac-Man eats a power pellet, but does not eat
all four ghosts, or if it misses the fruit which appears occasionally
in the center of the board.
3.3.3 Individuals
For each individual, I store the following information:
fitness -- The fitness of the individual
score -- The score from running the input string through the emulator
steps -- number of steps completed before the end state
end_state -- the ending state from the run (DIE, WIN)
bits -- the input string consisting of 'N', 'S', 'E', 'W'.
3.3.4 Child Generation
I do the same child generation method for all 3 supported crossover methods,
This is how I generate the child
population. It is sort of a mixture between Goldberg's method,
the method learned in class, and some custom modifications.
[Goldberg]
The top 20% of the parents get copied over into the child population.
I feel it is important to have those movement strings
represented verbatim in the resulting population.
The next 80% are pairs of children from the parent population using
the selected crossover method. One parent is a completely random
individual from the parent population, while the other uses the
following function to determine an individual favoring the better
parents:
int ga_random_favoring(int fav)
{
if (fav == 0)
return 0; // just in case
return (int)sqrt( (random() % (fav * fav)) );
}
|
The population size is passed in as "fav". This gives a better
chance for the returned random number to be closer to the desired
value.
For the 1 and 2 point crossovers, I select points weighted towards the
end of the two parent strings, again using the above function. The
uniform crossover does a 50% chance check for each position in the string
to determine which parent gets to supply which child with the bistring
position.
The bottom 20% are mutations of random individuals from the population.
The mutation rate on these is 50%. That is to say, that for each
move on the move-list bitstring, it has a 50% chance to be modified.
When it is modified, it is changed to one of the four movement
directions, allowing it to be changed to what it already is. For
example, "N" can be changed to "N", "W", "E", or "S".
This was done so that there is always some genetic variety in the
population, regardless of its fitness.
4.0 Results
4.1 Expected Results and Summary
To be honest, I wasn't really expecting this to work very well. As can be seen in
the following graphs, and table, you can see that it didn't find a winning solution
even with a 8 hour run of 250 generations of 20 individuals. Here's what I think
is happening:
I think that this is doing a brute force method to find the result, but instead
of doing it logically, it is doing it randomly. That is to say that it is randmly
picking the place to try a different path, and therefore it is not doing it very
well at all. Some proof to this is the fact that a single-point crossover worked
better than a two-point crossover in 1/8 the amount of time.
With a 2-point crossover, there is more of a chance of losing the "good" part of the
path, as the data between two random positions are changed, rather than just one
position. A single point crossover has a better chance of only changing data
later in the string.
But, why should this make any difference anyway? Well, if you were to look
at two paths, by a certain step, Pac-Man can be in completely different locations
on the map. In one string, he might be in the upper left corner, and in the
other string he might be in the lower right corner. Now, all of a sudden, the
string that works amazingly well from the upper left, is put into the lower right
position, and for all intents and purposes, it is now a completely useless, random
string.
In retrospect, this is a better candidate for Genetic Programming, and not GA's.
| Crossover Method |
Pop. Size |
#Generations |
Total #games played |
Points |
Time |
| 1 point |
10 |
87 |
870 |
6200 |
2 hrs |
| 2 point |
10 |
35 |
350 |
4000 |
1 hr |
| 2 point |
20 |
57 |
1140 |
5980 |
3 hrs |
| 2 point |
20 |
250 |
5000 |
6000 |
8 hrs |
| uniform |
10 |
101 |
1010 |
5060 |
2 hrs |
Table 2: Game Results
4.2 Single-point Crossover
 |
| Graph 1: 1-Point, 10 Member Population |
The blue line is the minimum fitness for the population. The fact that it
hovers on average around 900 probably shows the fitnesses for the mutated
strings, which have no real basis for their Genetic material. Due to the small
population size, unfortunately, they have a very strong influence on the average,
shown in green.
Something interesting to note is that the red best curve jumps up to 6200 around
generation 25. This is probably due to some luck. The fact that it jumped
that high, that early I think is a complete fluke. It then remains there for
at least the next 60 generations. If this were to be expanded horizontally,
I would guess it would look like an inverse log graph, increasingly longer
numbers of generations between improvements.
4.3 Double-point Crossover
 |
| Graph 2: 2-Point, 10 Member Population |
 |
| Graph 3: 2-Point, 20 Member Population |
As with the above graph, the blue worst line hovers really low on the graph,
probably due to the circumstances I explained above.
The peak in the average in the right half of the second graph shows that a large
number of elements had fitnesses like the best graph.
These definitely show that higher populations are better for the system, as would
be expected. Unfortunately though, it takes a very long time to compute out the
fitness for a movement path, as it needs to run the emulation hardware with the
movement string as input.
4.4 Uniform Crossover
 |
| Graph 4: Uniform, 10 Member Population |
The average line in this graph is not changed much at all by the actions of the best
line, showing that most of the individuals in the population probably are similar
to the worst line, and not of the better fitness values of the best line.
5.0 Future
5.1 Goals
Future goals for this project include making the GA interface and subsystem
flexible enough to work for other games. Also, I'd like to try out some
Genetic Programming on the control input strings. I think we'd get better
results quicker if that were the case.
5.2 Bugs With The Current System
There is just one bug, a runtime bug, which I mentioned in the class
presentation, which is that the control input will occasionally halt,
and no new input will be injected into the system. I put in a temporary
workaround by means of a watchdog timer. By using this timer, if
the position of Pac-Man hasn't changed for NN frames, where NN is a value
close to 30, then the next item on the string list is injected. It was
a quick fix for now, being that it is consistent.
6.0 Research References