We implemented our program in C++. We learned a lesson from our project last year and did almost all of our implementation on Unix-based systems so that we did not encounter portability problems. Most of our editing was done with the text-editors Pico and Vi. We also used several other Unix programs: Perl (a programming language), Purify (an X-based memory checker), GDB (a debugger), and the "make" compiling utility.
Since our program was object-oriented and consisted of over 3700 lines of code split into 11 files we needed the make utility. Our source code defined 11 custom data types and over 150 functions. Using the make utility reduced compile time by only recompiling the parts of the program we had changed instead of recompiling all of our source code.
We divided our program into multiple files to follow the standard practice for large object oriented programs. Each class definition (Team, Maze, Pacman and Ghost) is stored in a header file and its implementation kept in a .cpp file of the same name. We also had a header file for shared definitions, common.h, and some implementation in common.cpp. Our program centered around the file main.cpp, which tied all the files together. Our makefile (run by the make utility) individually compiled each .cpp file into object code and then combined all the object code with the necessary libraries to create an executable file. After this we could launch our program just like any other application.
The entire structure of our program, including all 11 files, was in place by the first time we compiled it; however, the source code was considerably shorter. Our first stage in development was simply to implement the basic environment (the maze). We used a crude visual interface so we could verify that everything was running correctly. (This interface is still in place. See the sample game in Appendix A). At that point, we had already written our makefile, and we didn’t have to make many changes to it throughout the course of the year.
At first, our Pacmen and ghosts used only very simple algorithms to determine their movement and they played on the same maze every time. We knew that we would eventually be evolving the ghosts, but we needed to add variety to the mazes and make the Pacmen less predictable. For the mazes, we created a random maze generator that efficiently produces mazes with certain properties (for example, no dead ends and a fixed percentage of the areas as open space.). For the Pacmen, we created a variety of "personalities." A Pacman's personality determines how it moves when it has more than one safe option. (For a list of the personalities we created see Appendix B). Because of these personalities, it is rarely possible for a ghost to predict exactly how a Pacman will react in a given set of circumstances. Before each round (a round is the time it takes each ghost team to play one game), we randomly generated a maze and assigned each Pacman a personality. In a given generation, each team faced the same combination of Pacmen personalities in the same maze.
Four classes made up the bulk of our source code: Ghost, Team, Pacman, and Maze. The Pacman, Ghost, and Maze objects are fairly self-explanatory because they represent actual objects from the game environment. The Team object ensures that our ghosts will evolve to work in teams. To this end, main and the Maze class communicate through the Team class to direct the ghosts.
One of the most difficult tasks in implementing any genetic programming project is creating the language in which the competing programs are written. We finally decided to represent the ghosts’ programs as character arrays. Each character in the array represents either an instruction or a number (for a list of character command sets, see Appendix C). The programs use prefix notation, which is considerably easier to parse (prefix notation puts operators and functions before their arguments, so instead x+y, one would say +xy). Another advantage of this representation is that is easy to combine two programs: we literally replace a section in the midst of one program with a section from another program.
The above technique is the standard crossover method used in genetic programming. Our program differs from this method in that instead of evolving individuals, we evolved entire teams. To do this, we invented an algorithm to combine whole teams. The program selects teams to crossover by comparing fitnesses. The higher the fitness that a team has, the higher the probability that it will be selected for crossover. Then, the program randomly decides whether it should copy the entire team into the next generation, or, more likely, combine the team with another team, which was selected in the same manner. If it chooses to combine one team with another, our program passes through ghost by ghost and either directly copies one team's ghost to the new team, combines the two ghosts by intermixing portions of each ghosts' programs, or randomly "mutates" one of the ghosts. To mutate, the program replaces a random piece of the program with a randomly generated section of code.
At first, we ran our compiled program only on Mode or on a single processor on Pi. However, it soon became apparent that in order to collect sufficient data, we would need to run our program in parallel on a supercomputer. We decided to use Message Passing Interface (MPI), a model for parallel computing that is well suited to our problem. Pi would not support MPI and only had two processors, which would have at most doubled the speed of our program. So we asked for an account on a larger supercomputer. We received an account on Theta, which allowed us to use as many as 32 processors, which was sufficient for running our code.
Parallelizing using MPI was one of the most difficult tasks we faced because it required us to change our method of thinking and to rework our code. We chose to give each processor its own maze object and its own Pacmen. We then gave each processor the same number of ghost teams to evolve (usually 25). After each generation, every processor sends its best team to another processor so that the best code becomes mixed between all the processors. The pairs of processor that communicate with each other change after every generation so that eventually all of the processors communicate. The above changes were fairly difficult to implement, but the 32-fold speed increase was worth it. Also, parallel code is very difficult to debug. The final version of our source code is shown in Appendix E. Next year, we will probably design our code to run in parallel at the beginning of the project.