AI/Genetic programming/Evolutionary chess

From HaskellWiki
< AI
Revision as of 05:18, 19 December 2006 by Chessguy (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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.

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?

Any thoughts, questions, ridicule, code offers, etc. are more than welcome. You can email me at wagner dot andrew _at_ gmail dotcom