Files have since been removed. If interested, please contact me for the files at sfisher@cs.unc.edu.
The executable is called genetic-chk. It takes no arguments.
There are a greal deal of files used in this program to facilitate the interaction between various modules. The executables for the checker game itself are called wischk1 and wischk2. These two executables are called from the shell script "run3." The two checkers programs communicate via several configuration files. The file "master.cfg" contains the initial board. The file "checkers.cfg" is changed with each move and represents the current status of the game. This file is removed when a program wins. The file "endboard.cfg" represents the board at the end of the game. This board is used to evaluate the fitness of a set of weights. The weights are contained in a file called default.prm. This file is changed when a more fit set of weights is discovered.
So to summarize that quickly:
The WEIGHTS struct contains twelve VALUE structures, one for each weight in the evaluation function.
Finally the population is represented as a queue of weights.
Then, we enter a loop that is the bulk of the program. Simplistically, this loop takes an already "scored" population (old population) and does a weighted random selection to select parents. Crossover and possibly mutation (not all children are mutated) are performed and the new offspring is produced. This child is scored and placed in the new population queue. This continues until an entire population is produced, at which point the loop recommences. At each pass through this loop, the most fit of the new offspring is written out to the default.prm file. This is so that if the program is terminated, we have record of the "best so far."
In more detail, we started the initial program with a population such that the scores in the population.prm file were simply 1..240 (12 weights X population size of 20). The first action in the loop is to read in the population.prm file.
The program then enters a loop that runs for half of the population size. First, it then randomly dequeues two "parents" from this old population. The random dequeue process, generates a weighted random number. This number is used to choose which parent in the population to use for breeding. The number is weighted so that there is a larger chance of picking the parents who are more 'fit'. The most fit parent has approximately a 10% chance of being picked, while the least fit parent has a chance of less than 1%. However, it is still available to be picked from the population.
Copies are made of these two parents, child1 and child2. These children are then passed to cross_parents. This function randomly selects a weight to cross and a position within the bit string of that weight where the crossover will commence. Then a crossover is performed and the new number value of that bit string is changed in the VALUE structure.
Crossover performs the crossover and then has a one in twenty chance of mutating the child. Mutate simply generates a random number (seeded off the system clock) and flips a single bit in the bit string.
Then each of these new children are evaluated. This is achieved by first writing the child's values to the default.prm file. Then a script is run that uses the weights in the default.prm file for the evaluation function. The script is entitled "run3" and is a simple shell script. It invokes a game between the child and the existing wischk program. The game terminates when someone wins or a max level (we set it to 300) of moves is met. Then the fitness function is run on the resulting board. This board is read out of the endboard.cfg file. This sequence of steps is performed on both children. The children are then enqueued in the New_Population queue according to their score.
The best child at each pass of the loop is written out so that the best-so-far is always kept track of.
After the entire new population has been created, it is written out to the population.prm file, and the whole process starts again.
Then we increased the difficulty of the checkers program. We did this by increasing the amount of time it had to search ahead for moves. Immediately our program began losing badly again. After another day of running our program was able to barely lose and occasionally tie the checkers program. It has not yet been able to reliably defeat the checkers game with increased level of difficulty.
Our program made significant progress in learning. It is now much better of a checkers player than it initially was. It would have been surprising if our program had learned to be a better player than the checkers program we were training it against. It did learn from an initial state of on ability to play checkers, to being a formidable competitor for the checkers program. The program we were training against was a very skilled checkers program, so being able to compete with it is a major accomplishment.
The bulk of the project was split into little sections, all of us working at Rich at the same time. Everytime someone finished a given function, they'd just take on another.
back to main