Wednesday, 14 March 2007

Generating Moves & Playing Them

The move generator was relatively painless. I decided to represent a move as a 32-bit integer (the most logical choice) and use a structure to represent the pieces. The piece structure looks as follows:
typedef struct tag_CHESSPIECE {
char type;
int position;
struct tag_CHESSPIECE* next;
struct tag_CHESSPIECE* prev;
The two pointers is used in a linked list to avoid iterating through the entire board array. It also saves me from recreating pieces when they are captured, since I simply push the captured piece onto a stack and pop it off with takeBack(). I designed both makeMove() and takeBack() to be tightly coupled, which is a great improvement on my previous attempt. Assumptions often causes problems, but it can sure boost the engine speed! There is simply no room for defensive programming in a chess engine.

The moves are represented by a 32-bit integer, specifically:
bits 00-07 stores the source square.
bits 08-15 stores the destination square.
bits 16-21 stores the captured piece, if any (0 if none is captured)
bits 22-27 stores the promoted to piece, if any (0 if none)
bit 28 is used to indicate whether the move models castling - this allows quick checking in the makeMove() and takeBack() methods.

After some tinkering, Vicki made the first valid chess move. I had some issues with pointer arithmetic, but is seems to be resolved. I cannot wait to get Vicki to play its first valid chess game!


Anonymous said...

I want to comment on "there is no room for defensive programming" because actually that is a very important part of programming a chess engine. You only have to pick the proper defense! :-) A couple of suggestions:
- use assert() a lot... every time you _think_ of a fact that is true, assert it
- have functions that verify that your objects are in a good state (e.g. all pointers in the board are valid, lists are consistens, etc.) then assert() them!
- for any value that you compute incrementally (e.g. hash key, material value, whatever) have a function that recomputes the same value from scratch, then every now and then assert() that the two values match.
This is actually fun to code and it's going to save hours and hours of debugging.

Sparky said...

I actually fully agree with you to the point that my code is currently riddled with assert statements! :-) The advantage of assert is that they can easily be removed at a later stage for that extra 1% of performance. What I do think should be avoided is unnecessary if statements or assign statements in cases where the value can be assumed to have the correct value already, but which could be checked by means of assert.

Thank you for your comment. I'll make sure I add an extra dose of asserts in the next round.