Robert Kirk DeLisle
12 Feb 2008
The Big Picture
A neural net controls PacMan's movements through the maze and you can control the types of inputs going into the PacMan. The default version associated with the executable has no ghosts and uses a Window around PacMan with a radius of 4 tiles. This results in four tiles in each direction around him, plus the two tiles in each direction that he occupies, or 4+4+2 (4 to the right, 4 to the left, 2 for PacMan) left/right and up/down. This gives 100 total tiles. I also have the tiles that PacMan covers removed from this set, so you get 96 inputs.
Each tile can have 3 possible inputs - 1 for ghosts (-1 if a baddie, 0 if no ghost there, and 1 if a blue one), 1 for a dot/wall (-1 if there's a wall, 0 if nothing there, and 1 if a dot is there), and 1 for a pellet (0 for no pellet, 1 for a pellet). The default version you have has no ghosts (you can control the number of ghosts in the input file), so you have dots/walls and pellets as inputs for each tile. The grand total is now 96 * 2 or 192 inputs.
At each step that PacMan takes, the neural network is evaluated. The net has 4 outputs, one for each direction (up, down, left, right). The output with the highest value gives the direction that PacMan takes.
In the absence of ghosts, the game map is deterministic so yes, PacMan will take the same path when using the same neural network. The ghosts have a strong random component to their movements, so adding these will cause some random variation in PacMan's movement from run to run.
The Neural Nets are evolved using an Evolutionary Computation process. The fitness I'm using is the score that PacMan gets for one run through the maze. The time one run can take is limited (you can also control this in the parameters file). The goal is to maximize the score that PacMan gets.
I've found it most interesting to look at PacMan's navigation early in the process and compare that to what happens after it has run for a while. No surprise that early in the process PacMan's movements are more or less random - often he just drifts one direction or the other, hits a wall, and stops. Then after it has run for a while and his score is over 1000, his behavior is much more interesting. So far the maximum score I've seen (with no ghosts) is about 2600 out of a maximum of 2840.
How to get PacMan to run through the maze
Yes, you can opt to have the PacMan run after each generation using the best neural net thus far. To get this to work, while one of the application's windows is activated (the PacMan game maze is probably the best), press the 'B' key. After the current evolutionary step, PacMan will become active. You can turn it off - go back to having PacMan not run - by pressing the 'B' key again.
BE PATIENT after you press the 'B' key as the evolutionary step will have to complete before PacMan runs and sometimes this will take a while depending on how many inputs you have and how large the population is. Also, if you get impatient and hit the 'B' key a second time, you will end up toggling the display off so you'll be back where you started. Just hit the 'B' key once.
AIPac was developed in order to examine (play with) evolutionary training of a PacMan controller. I've tried to develop the simulator in as open a form as possible in order to allow modifications to the maze, the graphics, etc. I may no warranty on the quality of the code. I refer to AIPac and PMAI somewhat interchangably, so be forewarned.
The files/distributions are as follows:
AIPac_README.txt - this file
This contains just an exectuable with the minimum files necessary to get it to work. The files are:
PMAI.exe - the executable
AIPac.param - a parameters file within which you can control the behavior of the executable. I've tried to make it self-explanatory.
Resources/ - this directory contains the graphics and mazes I used for the simulator. It should be fairly flexible to allow changes, but it may not be intuitive.
This contains all the code used to develop the application along with the Resources listed above. I used Code::Blocks as my IDE, so I retained the project as-is. My version of Code::Blocks is 4639 which is current as of late 2007. I also used GCC 3.4 to compile the code. I'm certain you can use other IDEs (such as MSVC++), but I've opted for open source.
NEAT/ - This directory contains the code for evolutionary control of neural networks. NEAT is Neuro-Evolution through Augmenting Topologies, developed by Dr. Kenneth Stanley. (http://www.cs.ucf.edu/~kstanley/) This version of NEAT was developed by Mat Buckland of AI-Junkie fame (www.ai-junkie.com) and he has give me permission to include it with my distribution. (Thanks, fup!) I have used his code with minimal modifications, and as a result, it is a bit of a hack, especially CController.cpp file.
Resources/ - same as above. The graphics and maze maps necessary for the executable.
Utilities/ - my collection of programming utility classes used in this project. I tend to use these a lot in my projects.
This file shows the best results I've gotten thus far (late March 2007) with no ghosts in the maze, using a windowing method for inputs. In this input method, the neural network inputs consist of a window centered on PacMan and extending 6 tiles in each direction. This gives a 13x13 window of the game board as input. There are 4 outputs, one for each direction. The largest output determines the direction of PacMan's movement.
Here are some additional details related to AIPac that might come in useful. I've tried to put the details in the order of interest and those pieces that will get you up and running the fastest.
Remember that the Resource directory needs to be present. This has all the graphics, mazes, etc. needed for the simulator. You can control most (all, I think) of the details of where the various files are found within the parameters files, AIPac.param, but I recommend leaving things as they are until you're familiar with the program.
While the simulator is running, if you press the 'B' key, this will toggle displaying the current best PacMan controller after each generation. Remember that there will be a delay in displaying the best controller due to the fact that generations take a while to process.
Currently, I have the parameters set up for a rather lengthy evolution step. If you want to see some action more quickly, try changing the following parameters in AIPac.param:
Replicates - Typically I have this set to 5 which means that each PacMan controller will be tested 5 times and a measure of performance assessed across the multiples. Set this to a smaller number and things will run faster. The purpose of this is to account for the random nature of the ghosts. If the ghosts are not present, set this to 1 since that type of simulation is deterministic.
PopSize - Obviously, reducing population size will make things faster, although potentially less interesting.
AIType - I have this set to Windowed which defines a window around PacMan, as described in the readme file. Setting this to Global will be a very different type of AI. Specifically, the inputs defined in the section following AIType setting will be used rather than a window around PacMan. This will shrink the number of inputs significantly, but I've found it to be less interesting.
I've tried to be as descriptive as possible in the AIPac.param file. It should be largely self-explanatory.
If there are other questions or comments, please leave a message in the forum.
Vector-based inputs implemented. Walls are input as a window. Pellet inputs provide a distance and angle to each power pellet, ghost inputs provide distance, angle, and state (-1 = hunting, 1 = blue) to each ghost, dot inputs show distance and angle to the centroid of all remaining dots. All vectors assume PacMan as the origin.
EnforceIntersections was added to the control parameters. If set to 1, PM will only make a directional change at an intersection. If set to 0, PM can change direction at will. There's a bit of a speed up with this as well as enforcing smooth paths.
**Verify proper scoring for dots - the possible maximum score should be 284 dots * 10. (Ghosts and Pellets seem to be OK.)**
I found that at certain intersections mulitple dots are removed simultaneously due to a perceived overlap of the bounding box and dot tiles, but only one produced a score. A modification was made to count how many dots are removed for any particular PacMan location and the score adjusted appropriately. MapController::ModifyTileByPixel
The visualization delay was linked to the parameters file. Larger numbers cause the visualization to run more slowly so that it is easier to watch. This does not affect the actual GA portion, just the visual of PacMan running through the maze. The same delay is linked to the playable mode option.
A user playable option is now available. The parameter Mode can be set to Evolve to run an evolutionary simulation, or to Play for a Keyboard playable version. Use the arrow keys to move PacMan around the maze. All the other options remain the same.
**Fix the gate on the ghost cage - it doesn't redisplay and it may not be reset.**
A forced redraw of the entire maze was implemented any time the gate is opened or closed. This does not appear to slow the process whatsoever and in fact I can force a redraw at every frame without any noticable performance losses. This is a much easier fix than to implement specific drawing and erasing of the gate, or modification of the maze graphics.
A few bugs were fixed. Specifically, some issues with whether PowerPellets and Ghosts were visible or not were addressed.
The ability to ignore walls or dots was added to the Windowed AI. In the parameters file the following keywords control this as follows:
DotWallSingleInput - If set to 1, the input will be -1 for a wall, 0 if empty, and 1 for a dot. If set to 0, there will be two sets of inputs - one for dots one for walls.
DotsWallsOnly - If set to 0, both dots and walls will be used for inputs. If set to -1, only the walls will be seen. If set to 1, only the dots will be seen.
Windows now update during the evolution step thus preventing an freezing of the application during one epoch.
The console window now tells you whether PacMan will run or not after the current epoch and has (almost) instant feedback from pressing 'B'.
Small optimizations to speed up the simulation.
Ghosts now allowed to reevaluate their direction after PacMan eats PowerPellet. Hopefully this will discourage chance collisions forcing PacMan to be more active in pursuit.
When the console window was running a spontaneous crash would occur the seemed to stem from the Windows message queue. A DoEvents() function was implemented to allow window events to be processed while the Console was active. This seems to have solved the problem.