Writing a chess program in 99 steps

17 Iterative deepening and move ordering

The alpha-beta algorithm needs good moves to start with, or else there won't be many of cut-offs, and the search speed will be quite slow. So how do we determine what moves should be tried first? This is a chicken and egg situation, we need to know good moves to find the best move! Obviously, if we already know what moves are good, then what's the point of searching in the first place?

'Good moves' are for instance moves from the principal variation, moves that cause beta cut-offs, and moves that improve alpha. An effective way to get good moves is to start with a shallow search, remember which moves were good, and use that information in a deeper search. This is the general idea of iterative deepening. If we do a 9-ply search, then we start with a 1-ply search, remember the good moves, use that information (also called 'history heuristics') for the 2-ply search, and so on, until we arrive at ply=9:

ply = 0;
for (depth = 1; depth <= maxdepth; depth++)

{

score = alphabetapvs(ply, depth, -LARGE_NUMBER, LARGE_NUMBER);

}

Of course we need some mechanism to store good moves, and use that information to sort the moves.

The first couple of iterations are going to be very fast, and the added bonus of this technique is that there is always (almost immediately) a 'best move' available to reply, in case time runs out. You might be surprised to see that a 9-ply search with iterative deepening (so start with a 1-ply search, then a 2-ply search etc, until 9) turns out to be significantly faster then doing a plain 9-ply search without iterative deepening. The only reason for this speedup is that iterative deepening gives us the information we need to order moves, resulting in a lot more cut-offs than an alpha-beta search without move ordering. If move ordering is very bad, a 9-ply search takes about 35x longer than an 8-ply search (if the branching factor is 35). If move ordering is good, this factor will be closer to 6 (or lower).

Winglet's history heuristics and move ordering is very basic. The PV from a previous iteration is stored and tried first at the next iteration. Moves that caused a beta cut-off, and moves that improved alpha are tried next. These moves are stored in two databases (one for white and one for black), indexed by the from and to field, and containing 'move scores' that can be used for sorting:

unsigned int whiteHeuristics[from][to];

unsigned int blackHeuristics[from][to];

This is how the database is updated during the search, if a beta cut-off is found:

if (val >= beta)

{

if (nextMove)

blackHeuristics[move.from][move.to] += depth*depth;

else

whiteHeuristics[move.from][move.to] += depth*depth;

}

Incrementing the score with 'depth*depth' will create a preference for moves that caused cut-offs at higher remaining depth values, because these moves are cutting larger parts of the search tree.

The move sorting algorithm is actually selecting the single next best move on the move list, rather than doing a full sort. This is done in the search algorithm, after move generation and right before making the move:

movegen();

for (i = ifirst; i < ilast; i++)

{

selectmove(i);

makeMove(i);

etc...

We are saving a lot of time by selecting the next move, instead of doing an expensive sort of all moves. Remember that most moves from the move generator will never be made (due to cut-offs).

step 77: board.h

#ifndef WINGLET_BOARD_H_

#define WINGLET_BOARD_H_

#include "defines.h"

#include "move.h"

#include "gameline.h"

#include "timer.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

       U64 hashkey;                   // Random 'almost' unique signature for current board position.

       // 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 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];

       // search variables:

       int triangularLength[MAX_PLY];

       Move triangularArray[MAX_PLY][MAX_PLY];

       Timer timer;

       U64 msStart, msStop;

       int searchDepth;

       int lastPVLength;

       Move lastPV[MAX_PLY];

       unsigned int whiteHeuristics[64][64];

       unsigned int blackHeuristics[64][64];

       BOOLTYPE followpv;

       U64 inodes;

       void init();

       int eval();

       Move think();

       int minimax(int ply, int depth);

       int alphabeta(int ply, int depth, int alpha, int beta);

       int alphabetapvs(int ply, int depth, int alpha, int beta);

       void displaySearchStats(int mode, int depth, int score);

       BOOLTYPE isEndOfgame(int &legalmoves, Move &singlemove);

       int repetitionCount();

       void mirror();

       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();

       void rememberPV();

       void selectmove(int &ply, int &i, int &depth, BOOLTYPE &followpv);

};

#endif

step 78: sortmoves.cpp

#include <iostream>

#include "defines.h"

#include "protos.h"

#include "board.h"

void Board::selectmove(int &ply, int &i, int &depth, BOOLTYPE &followpv)

{

       int j, k;

       unsigned int best;

       Move temp;

       // re-orders the move list so that the best move is selected as the next move to try.

       if (followpv && depth > 1)

       {

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

              {

                     if (moveBuffer[j].moveInt == lastPV[ply].moveInt)

                     {

                           temp.moveInt = moveBuffer[j].moveInt;

                           moveBuffer[j].moveInt = moveBuffer[i].moveInt;

                           moveBuffer[i].moveInt = temp.moveInt;

                           return;

                     }

              }

       }

       if (nextMove)

       {

              best = blackHeuristics[moveBuffer[i].getFrom()][moveBuffer[i].getTosq()];

              j = i;

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

              {

                     if (blackHeuristics[moveBuffer[k].getFrom()][moveBuffer[k].getTosq()] > best)

                     {

                           best = blackHeuristics[moveBuffer[k].getFrom()][moveBuffer[k].getTosq()];

                           j = k;

                     }

              }

              if (j > i)

              {

                     temp.moveInt = moveBuffer[j].moveInt;

                     moveBuffer[j].moveInt = moveBuffer[i].moveInt;

                     moveBuffer[i].moveInt = temp.moveInt;

              }

       }

       else

       {

              best = whiteHeuristics[moveBuffer[i].getFrom()][moveBuffer[i].getTosq()];

              j = i;

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

              {

                     if (whiteHeuristics[moveBuffer[k].getFrom()][moveBuffer[k].getTosq()] > best)

                     {

                           best = whiteHeuristics[moveBuffer[k].getFrom()][moveBuffer[k].getTosq()];

                           j = k;

                     }

              }

              if (j > i)

              {

                     temp.moveInt = moveBuffer[j].moveInt;

                     moveBuffer[j].moveInt = moveBuffer[i].moveInt;

                     moveBuffer[i].moveInt = temp.moveInt;

              }

       }

       return;

}

last update: Sunday 03 July 2011

Writing a chess program in 99 steps

17 Iterative deepening and move ordering

ply = 0; for (depth = 1; depth <= maxdepth; depth++)

{

score = alphabetapvs(ply, depth, -LARGE_NUMBER, LARGE_NUMBER);

}

unsigned int whiteHeuristics[from][to];

unsigned int blackHeuristics[from][to];

if (val >= beta)

{

if (nextMove)

blackHeuristics[move.from][move.to] += depth*depth;

else

whiteHeuristics[move.from][move.to] += depth*depth;

}

movegen();

for (i = ifirst; i < ilast; i++)

{

selectmove(i);

makeMove(i);

etc...

step 77: board.h

#ifndef WINGLET_BOARD_H_

#define WINGLET_BOARD_H_

#include "defines.h"

#include "move.h"

#include "gameline.h"

#include "timer.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

U64 hashkey; // Random 'almost' unique signature for current board position.

// 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 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];

// search variables:

int triangularLength[MAX_PLY];

Move triangularArray[MAX_PLY][MAX_PLY];

Timer timer;

U64 msStart, msStop;

int searchDepth;

int lastPVLength;

Move lastPV[MAX_PLY];

unsigned int whiteHeuristics[64][64];

unsigned int blackHeuristics[64][64];

BOOLTYPE followpv;

U64 inodes;

void init();

int eval();

Move think();

int minimax(int ply, int depth);

int alphabeta(int ply, int depth, int alpha, int beta);

int alphabetapvs(int ply, int depth, int alpha, int beta);

void displaySearchStats(int mode, int depth, int score);

BOOLTYPE isEndOfgame(int &legalmoves, Move &singlemove);

int repetitionCount();

void mirror();

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();

void rememberPV();

void selectmove(int &ply, int &i, int &depth, BOOLTYPE &followpv);

};

#endif

ply = 0;
for (depth = 1; depth <= maxdepth; depth++)