Donnerstag, Februar 15, 2007

Haskell: Chess

I recently implemented Chess in Haskell. I used a standard minmax-Algorithm and a very simple evaluation function for computing moves.

The following problems and oddities occured:

  • easiest evaluation function: difference of material on board (without any positional judgement)

  • value of the King is infinity, winning threshold a little bit less than infinity :-), because the losing player may have a material advantage, so the threshold should be infinity minus the maximal material value of all pieces but the King

  • winning "player" keeps playing instead of just capturing the king, because he can capture in the future as well and tries to maximize benefit by trying to capture other pieces

  • king is captured by naive algorithm -> delete last two moves (King tries to run away of the chessmate, but is captured nevertheless...)

  • the capturing en passant and castling rules are the worst things from a programmers point of view, because they make moves depending on previous moves, thats why I ignored both rules in my implementation

  • a depth of the game tree of 4 is already very, very slow

Have a look at my implementation at You may start trying the test functions exampleGame and exampleMateGame.



At 1:39 PM, Steffen Mazanek said...

notabene, the program has just around 200 lines of code

At 7:11 AM, Bart said...

See my notes at for some ways to improve your player. I'll be adding the rest of the referenced notes shortly, and some of my students and I are currently working up Haskell implementations based on them.

Four plys is about right for a naïve minimax player. Alpha-beta and do-undo will get you to 6 or 7 plys, and proper use of a transposition table will get you beyond that…

At 1:08 PM, Rajiv Bakulesh Shah said...

Steffen! Fantastic work!

Haskell is one of my favorite programming languages, and chess engines are some of my favorite programs. Keep it up!

I'm also developing my own chess engine, Gray Matter, from scratch. You can find my project page here. Please contact me to share ideas.



Kommentar veröffentlichen

<< Home