Brock Peabody - 2010-01-30

So far, I've finished the basic building blocks of a GP system - I have randomly generated programs, crossover, and mutation. Unfortunately, my attempts to solve Sudoku puzzles with it have been fruitless. Admittedly, I'm not giving it much help - just the puzzle as a list, and a requirement that it spit out a tuple with it's choice - but then again, that's the point. If I have to give it a lot of help (with say primitives for operating on Sudoku puzzles) then I may as well solve the problem without using GP.

My basic problem is that I cannot get any program to choose to different valid results. A program that is fed a puzzle that can choose a valid result will continue to choose that result even when fed the same puzzle but with that value filled in. So there's no way to incrementally improve the programs - I need some way to find some small difference between the programs to drive evolution. I need to force the programs to choose results that are more tightly tied to their inputs.

It struck me last night that user defined types could help. My long term goal is to allow this with template haskell. In fact, the current Value type would be completely user defined then. I expect this to be difficult learning experience, however, and would like to have a working, well tested system first. This is a lesson learned from experience with c++ templates - when doing something new, do a non templatized version first.

I realized last night that I can get most of the functionality of this without the hard work - or the elegance right now. Given the current Value type with it's ability to hold lists, tuples, etc… I can create datastructures that map on to almost anything you'd need. All I need is a new ValueType that is a regular value with a type identifier (for which I can use an Int). The user can then define functions that operate on these types and they won't be confused with their built in equivalents. By forcing outputs to be user defined types that are only derivable from the input types, I think I can draw a tighter bond between the too, and hopefully have randomly generated programs that can pick more than one right answer in a row.

Failing this, I'm going to try something easier for a while - maybe tic-tac-toe.