Here's a very good 2000 article from the New York Times describing David Fogel and Kumar Chellapilla's work with using evolutionary algorithms to produce a Checkers-playing neural network-based program.

Have a read for an idea of the sort of stuff Philip and I are tinkering around with.