AI/Genetic programming/Evolutionary chess
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. In the meantime, I'll try to keep this wiki page up to date with further ideas.