Tuesday, 20 March 2007

Uphill battle

I've just discovered another (much older & complete) blog that is doing exactly the same as I'm doing! Jonatan Pettersson's blog is worth a visit. Well done to him!

I have decided to implement Perft calculation to verify my move generator is correct before moving on. The technique simply counts the nodes of valid moves (that is, you have to avoid check, etc.) all the way down the tree. I found this link quite helpful.

My results are the same up to depth 4 (197281 positions), but then miserably falls apart. Not only are the numbers wrong, but the engine occasionally gets slapped over the knuckles by Windows (this is C after all). The moves that cannot occur prior to depth 5 are promotions, castling and en-passant. Logically, it must be one of these moves that is messing things up!

Well, at least the speed that I'm getting from the genMoves(), makeMove() and takeBack() functions are decent (more on that later). I hope I'm not going to spend the next few days trying to get rid of this pesky bug(s).

In the process I've also moved away from passing individual pointers and variables around and settled on a structure that defines the state of the game. The nice thing about a structure like this is that I can dump as much stuff in there without making the functions bloated in any way. Here it is:
typedef struct tag_CHESSENGINE
CHESSPIECE* chessboard[144];
int status;
CHESSPIECE* recycle;
CHESSPIECE* whiteking;
CHESSPIECE* blackking;
The pointers, whites, blacks and recycle are lists to ALL the pieces, while whiteking and blackking are pointers to the kings for quickly verifying illegal moves that leaves the king in check. The recycle list is useful to avoid any malloc() calls when taking back moves that resulted in captures. As the engine will only take back moves in a stack-like fashion, it is not even necessary to set the values of the piece structures as they are removed from the recycle list.

Well, back to coding.

No comments: