Yes, Virginia, Testing is Important!

In my zeal to optimize my checkers playing program, I included a number of optimizations in the search algorithm: minimax with alpha-beta pruning, plus a memory of previous partial search trees to assist in ordering of future searches, and to skip evaluations when the results are known.  Too many optimizations, as it happens.

I wrote quite a few JUnit tests for the basic checkers board manipulation code, but wasn't sure how to go about testing the search algorithm. I wrote some very basic tests that the pruning was happening as expected, but left it at that.

I then wrote a system for evolving the neural networks, and repeated the evolution experiments described by Fogel and Chellapilla. Again, I wasn't quite sure how to evaluate the results, as I'm not yet ready to play hundreds of games online using the best evolved network as my evaluation function.

So, I studied the last generation's networks and the games they played, and noticed that they'd all played the same first move... and the same first reply... and the same next reply! The first three moves were all the same.  Wow! Did they all stumble upon the best opening moves?  Or perhaps all of the surviving networks were descended from a relatively recent network that made that choice?

I decided to confirm that initial generation of networks was much more random in its play.  Unfortunately, upon reviewing their games, I found they too played the same first three moves.  Sigh.  Back to the drawing board.

To track this down, I tried shuffling the legal move choices presented to the search algorithm, but that made no difference.  Next, I implemented minimax and compared its choices to those of my enhanced alpha-beta search. As you might expect, they didn't agree.  So, I implemented a basic alpha-beta search, which did agree with minimax.  In the course of debugging, I found several mistakes in the over optimized alpha-beta implementation, and I don't think I've found them all.  Fortunately, testing will help me figure out when I've got it wrong, and hopefully the next 1000+ generations of evolution will be more fruitful.


Popular Posts