AI/Genetic programming/Evolutionary chess

Remark from Adrew Wagner by e-mail:

[This] page should probably just be deleted, as the idea never went anywhere.

So, for about 2 years or so, I've been batting around the idea of what it would look like to apply genetic programming to chess. Here's a non-technical overview I wrote a few months ago, sketching out some of my ideas.

https://sourceforge.net/docman/display_doc.php?docid=34518&group_id=174995

So, I've been thinking that Haskell would be a great platform on which to build this idea. To be a little more technical about it than I was in that overview, here's some more haskell-ish ideas.

What I'm thinking is, suppose I have this function:

ChessMachine :: ChessPosition -> ChessProgram -> ChessMove

ChessMachine would simply describe an abstract virtual machine which could take commands from the chess program, and always produce a move. This sounds harder than it is. Suppose it were passed the empty program. Now you say, surely this can't return a legal move. But all it has to do is simply generate the legal moves of the position, and return the head of that list. And now we see how any program can be guaranteed to produce a move: its operations should ultimately manipulate the list of legal moves in order to choose one.

ChessPosition is pretty simple. Any chess position can be described with a basic string - for example, the starting position can be represented as:

"rnbkqbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w - - 0 1".

I won't bore you with all the technical details, but you can kind of guess what some of it means.

ChessProgram would be an s-expression representing a chess program. Now, naturally, it's not going to be a full-fledged 3d-piece tournament program, but more like an algorithm. One which manipulates the chess machine in order to "choose" a move. This would probably be represented with a Tree ChessNode monad, where ChessNode could be a number of different things, depending on exactly how I implement the ChessMachine, and what commands I want to be able to operate on it.

So really, ChessMachine winds up being a parser, in a lot of ways. It could have its own state, and it takes the commands and evaluates them, and outputs a result, which is always of the type ChessMove. Anybody know of a language that's good at parsing? Preferably one where functions can be passed around as objects easily?

Anyway, once I have ChessMachine, then the fun begins. The next step is to start with the evolutionary stuff, because now we just have a Koza-esque genetic programming problem. I'm thinking I can start with a set of positions where we KNOW what the answer is (like mate-in-1 type positions). Then the fitness would simply be a measure of how many of those problems the program can get correct. Once we've got a program that can perform pretty well on that, hopefully we will have some the ChessMachine meta-language developed well enough that we can start pitting this program against itself in evolutionary fashion, trying to improve it in less clearly-defined ways. One nice thing about this is that our goal is NOT to produce an engine which processes millions of positions. If we were doing that, there are probably better languages for bit-twiddling optimizations. But since we want any program we produce to only look at a relatively small number of positions, the length of time it takes to evaluate a population by playing full games shouldn't be too bad. In theory. I hope. We would just need something like:

Match :: ChessProgram -> ChessProgram -> Result

Then we could pit the programs from the population against each other, and see how they perform.

Any thoughts, questions, ridicule, code offers, etc. are more than welcome. You can email me at wagner dot andrew _at_ gmail dotcom. You can also catch me on #haskell as chessguy. In the meantime, I'll try to keep this wiki page up to date with further ideas.

Tuesday, December 19: opqdonut on #haskell showed me some code he used to evolve a team for a simple combat model. Several things impressed me about this code. For one, there were some great examples for me on how to do random generation. That's an area i struggle in. I was also impressed with how simple he made it. His model wasn't some massive complicated thing. I need to put some thought into trying to simplify mine, if possible. One thing I do want to do in my project which he didn't seem to is focus on code re-use. I hope that, in the end, I'll have somewhat reusable modules for at least chess functionality and generalized genetic stuff.