Writing a chess program in 99 steps

12  Making the moves

Making and unmaking moves is mostly about good housekeeping & administration of the board variables. Not all chess moves follow the same rules, and there are quite some exceptions that need to be dealt with (think of pawn moves, promotions, castlings, etc). This means that testing and verification is very important at this stage (using perft and special purpose debugging functions) - it's just too easy to make mistakes here. Solely for the purpose of debugging (un)makemove, I have added a function debugMoves, to checks consistency of most board variables after making and unmaking moves. This function can be activated at compile time with by uncommenting the compiler directive WINGLET_DEBUG_MOVES.

How moves are stored

We need to store all generated moves at different search depths (plies), so we can trace our way back to the root and search another branch of the tree without having to generate the moves  again.  There is always going to be one set of moves for each ply that we need to store (see diagram below). To keep track of which moves in moveBuffer belong to which ply, another array is introduced: moveBufLen This array is populated in such a way that we can easily find the moves for a specific ply, as follows:

for (i = board.moveBufLen[ply]; i < board.moveBufLen[ply+1]; i++)

The move list is made part of the board structure. Keeping all search related data together would make it easier later to implement a parallel search algorithm (in case you want to embark on such a project). The current search line plus moves that have actually been played (the game line) are stored in a separate array, gameLine. This array also keeps track of the en-passant square and castling rights, so they can be copied back into the board structure when backing up moves.

step 35: gameline.h

---

#ifndef WINGLET_GAMELINE_H_

#define WINGLET_GAMELINE_H_

 

#include "move.h"

 

struct GameLineRecord

{

       Move move;

       unsigned char castleWhite;     // White's castle status, CANCASTLEOO = 1, CANCASTLEOOO = 2

       unsigned char castleBlack;     // Black's castle status, CANCASTLEOO = 1, CANCASTLEOOO = 2

       int epSquare;                  // En-passant target square after double pawn move

       int fiftyMove;                 // Moves since the last pawn move or capture

};

 

#endif

---

 

step 36: board.h

---

#ifndef WINGLET_BOARD_H_

#define WINGLET_BOARD_H_

 

#include "defines.h"

#include "move.h"

#include "gameline.h"

 

struct Board

{

       BitMap whiteKing, whiteQueens, whiteRooks, whiteBishops, whiteKnights, whitePawns;

       BitMap blackKing, blackQueens, blackRooks, blackBishops, blackKnights, blackPawns;

       BitMap whitePieces, blackPieces, occupiedSquares;

 

       unsigned char nextMove;        // WHITE_MOVE or BLACK_MOVE

       unsigned char castleWhite;     // White's castle status, CANCASTLEOO = 1, CANCASTLEOOO = 2

       unsigned char castleBlack;     // Black's castle status, CANCASTLEOO = 1, CANCASTLEOOO = 2

       int epSquare;                  // En-passant target square after double pawn move

       int fiftyMove;                              // Moves since the last pawn move or capture

 

       // additional variables:

       int Material;                  // incrementally updated, total material on board,

                                   // in centipawns, from white’s side of view

       int square[64];                // incrementally updated, this array is usefull if we want to

                                                          // probe what kind of piece is on a particular square.

       BOOLTYPE viewRotated;          // only used for displaying the board. TRUE or FALSE.

 

       // storing game and search moves:

       Move moveBuffer[MAX_MOV_BUFF]; // all generated moves of the current search tree are stored in this array.

       int moveBufLen[MAX_PLY];       // this arrays keeps track of which moves belong to which ply

       int endOfGame;                 // index for board.gameLine

       int endOfSearch;               // index for board.gameLine

       GameLineRecord gameLine[MAX_GAME_LINE];

 

       void init();

       void initFromSquares(int input[64], unsigned char next, int fiftyM, int castleW, int castleB, int epSq);

       void initFromFen(char fen[], char fencolor[], char fencastling[], char fenenpassant[], int fenhalfmoveclock, int fenfullmovenumber);

       void display();

};

 

#endif

---

 

Adding timers

After the makeMove & unmakeMove algorithms have been implemented, it's good to have a way of measuring the 'back-bone speed' of the engine, i.e. how long a 'perft' (see below) takes in real time.  I added a timer structure with corresponding methods. Using it is easy, you call timer.getms() before and after the section you want to time, and then calculate the time difference:

msStart = timer.getms();

perftcount = perft(number);

msStop = timer.getms();

std::cout << "nodes = " << perftcount << ", " << msStop - msStart << " ms, ";

Don't get too excited when you see high knods/s counts for perft (it's not unusual to see more than 10 million nodes per second for perft, or more than 10000 knods/s, depending on your hardware).  This speed is going to drop significantly when doing real searches and evaluating leaf nodes.

Perft, measuring speed and verify correctness

Perft was first introduced in an early version of Crafty and since then has become a 'standard' test for chess engines. The original intent was to verify correctness of the move generator and (un)makemove, but it is nowadays also used to compare computational speed of different move and board implementations.

Perft does a raw node count, up to some specified depth, by doing a full tree search. The procedure is very similar to a search (except for the absence of tree cut-offs), and instead of evaluating at the leaves, we just count the leaf nodes.  Here are some test positions with results.  

step 39: perft.cpp

last update: Saturday 11 June 2011