Take Two

As I have noted before I have been trying to use a genetic algorithm to evolve a multi-level perceptron (MLP—a specific type of neural net) to play Connect4 better than my hand-written player. My efforts have yet to bear fruit, and my patience is wearing thin. After multiple revisions to the GA and meticulous training for over 300 generations it is still not good enough—so I’ve decided to cheat.

I freely admit that my goal is not as pure as David & Kumar’s: they wanted to find out if Blondie24 could learn to play Checkers well completely on her own, while I am only concerned with building a better AI for my Connect4 game. It occurred to me that I can train MLPs to mimic the output from my existing evaluation function and seed my GA with them. This way the starting population already have nets as good as the best I can come up with—hopefully the GA should be able to pick things up from there.

Creating training sets was pretty easy. I wrote a short program to do a depth-first search of the valid states and spit out the first ten thousand unique ones, with their associated fitness. The NSSet Objective-C class proved very useful for this.

The second step in my plan, implementing back-propagation in my MLP class, was considerably harder. I ended up spending countless hours poring over books and some code I wrote for a coursework 4–5 years ago (we were predicting USD/GBP exchange rates). Even though the resulting code is the mental equivalent of a tongue-twister—lots of indexing into tightly coupled two- and three-dimensional arrays of various lengths—I’m actually really happy with it, and I’ve decided to release it as a separate project.

Now all I have to do is write a small program to create the initial population for my GA. I’ll keep you posted.