Pac-Man Autoplayer

About the project

This is a modified version of MAME version 0.30. It is actually built upon my MAMEDEBUG hack i distributed a while ago, and on my Pac-Man info page. There are some elements borrowed from Pac-Tape, but most of it is my own design & improvement over Pac-Tape.


It's been almost three years since I last touched this project. I have abandoned it. There were a few problems and limitations with my solution of using a Genetic Algorithm to play Pac-man, which I'll discuss here..

Even though Pac-Man is deterministic (not really random), a GA solution was never really sufficient for solving it. For example, say we have two GA "Children", or sequences of moves that are 30 steps long. Each one moves Pac around the maze differently. The standard GA crossover/breeding method is to take two children, split them both at the same point (ie: 15 steps in), swap their parts, and bammo... you have two new children. The problem with doing this (which is what I did for this implementation) is that by 15 steps in (or even 3 steps in) the next move will have a completely different result. Think about if Pac were at the top of the screen for one of those and the bottom of the screen for the other. I should have done crossovers based on Pac's position in the maze... but even then, the Ghosts might be in different placements. In one child, it might be safe to go north from a specific location, but in another child, there might be a ghost there. The whole point of doing a GA, and breeding these movement paths was entirely futile. The only reason it ever got decent at playing at all was that it would randomly go through moves until it got further. It basically did a brute-force method on solving the problem, which is what GA is meant to prevent.

The optimum solution for Pac-Man (or his wife, Ms.Pac-Man, which is non-determinisitc) would be to implement a Genetic Programming solution instead of the GA solution.

As far as implementation, the code that determined when to send down control changes to the game was always pretty shaky. I should have spent more time to figure out exactly when to look for a new control change. I think what I ultimately ended up with was a "send the next control message when Pac is at a coordinate that is a multiple of 8 pixels" or something like that. (This was part of the code that was borrowed from the "Pac Tape" project, but for some reason, I felt it necessary to modify it. *shrug*)

The software was blind. This is just fine for a GA. If this were to be upgraded to use a GP with something like my small LISP interpreter, then some kind of 'vision' for Pac would be needed, so that programs like "Move forward if there is a ghost to the north" can be implemented. Regardless, this is outside of the scope of the project, and is only mentioned here to get this thought out of my head.

Software last touched: 10 May 1999

-- page setup --
still need to upload the files as they now stand

Coming soon:
19 Apr 1999
Progress report
19 Apr 1999
not online
10 May 1999
not online
Final Paper
20 May 1999
20 May 1999
.zipped C source
20 May 1999
.zip, MS-DOS executable

To build this:

You will need the standard MS-DOS MAME build environment. (DJGPP, ALLEGRO, SEAL, NASM) You can go to The MAME homepage and in their downloads section, you can get these things.