I'm crazy enough to want to take a completely different approach to chess programming from most everybody. I want to actually evolve chess algorithms, using evolutionary computation techniques. Personally, I think there's something fundamentally flawed with the way most computer engines work. The process millions of positions per second, yet still only manage play that is comparable to the world's greatest human players.

Anyway, so that's where this project is going. Along the way, I'd also like to develop tools to make it easy for other developers to come behind me and write other chess engines in haskell.

So far I've written a little Chessboard class, which (hopefully) makes it easy to define a board structure, with a few operations, and get a working move generator (tricky business). You can also, theoretically, override some of the default functionality if your particular chessboard data structure does something more efficiently. So far, this move generator is intentionally only a first, very rough approximation. I just wanted to get something written that typechecks and is somewhat flexible.

My to-do list:
1. instantiate ChessBoard class (8 hours)
 - (DONE) I created a simple data structure around Data.Map that can be used as a chessboard.
2. implement move generation test suite (8 hours)
 - (DONE) I've pulled in an old move generation test suite that I wrote several years ago, and used HUnit to turn those positions in to Tests.
3. bugfix move generator (40 hours)
 - Using the above, I'll fine-tune my move generation until it can pass all the tests
4. add pointer to Rose Tree Zipper (16 hours)
 - (DONE) On a completely different track, I want to take the Rose tree zipper from Yi (http://code.haskell.org/yi/Data/Tree/Zipper.hs) and modify it. Basically, I want to add a "pointer" to the zipper, that always points to one of the child nodes of the focal point, so that instead of writing 'down x', I can just write 'down', and it will know where to go. This will be helpful when doing the next step...
  - This code can be improved, definitely. I wound up pretty much re-building the Yi code from scratch, in my own zipper. To do: make more utility functions for the zipper itself, abstract the pointer stuff into arbitrary state for the zipper (data TreeLoc a b = Loc { ... , zipper_state :: b})
5. write TraversalProgram grammar and interpreter (8 hours)
 - This is the meat of the idea, but a pretty easy part. Basically now a program will just be an expression in a particular grammar, which tells how to walk around the game tree. When the traversal ends, that will be the branch the engine chooses to walk towards. And algebraic data types are very easy to generate random values for. So basically, I'll have something like:
     data TraversalProgram = Left | Right | Down | Up | If BoolExpr TraversalProgram TraversalProgram | Sequence TraversalProgram TraversalProgram
     interpret :: TraversalProgram -> State (Tree ChessBoard) ()
     chooseMove :: TraversalProgram -> ChessBoard -> Move
     chooseMove prog board = getMove (evalState prog (Loc (genGameTree board) Top))
     -- where getMove knows how to get the move that will move towards the resulting descendant
6. instantiate Arbitrary (2 hours)
 - This grammar will need to be an instance of Arbitrary, in order to generate random programs
7. implement an arena (16 hours)
 - Provide a way for two programs to play each other, and see which wins
8. implement fitness mechanism for a pool (16 hours)
 - A way for a pool of programs to compete with each other and be ranked from most fit to least fit
9. implement breeding (16 hours)
 - I'll be stealing from some of my own code for this: http://catenova.org/~awagner/GPLib/
10. implement winboard protocol (16 hours)
 - This is a simple existing communication protocol for chess engines which will allow me to easily drop a GUI and a connection to online chess servers onto a chess engine

File list:
 - Board.hs - instance of the Chessboard class, based around Data.Map
 - Chess.hs - Old code, for reference only
 - Chessboard.hs - Chessboard class
 - TestHarness.hs - Pulls in the epd test suite and turns it into tests
 - Zipper.hs - Rose tree zipper 
 - alphabeta.hs - Another class I've been playing with that makes it easy to add alphabeta functionality
 - perftsuite.epd - The actual epd test suite
 - TreeTraversal - A simple algebraic data type representing a traversal around a rose tree