 |
 |
 |
 |
Writing a chess program in 99 steps
16 Repetition detection - Zobrist keys
A position is a draw (i.e. a player can claim a draw) if it occurs three times. The engine therefore has to check how often the current position has occurred in the game (or in the search tree, leading to this position) and if a position has occurred more than 2 times, then the search will return the draw score. 'Same position' here means that the pieces on the board occupy the same squares, the castling rights are the same and the en-passant target must be the same.
An effective way of comparing 2 positions is to assign some unique 64-bit signature to each position, and then compare the 64-bit signatures. We cannot capture all theoretically possible chess positions with 64 bits, but for all practical purposes, 64 seems to be enough (provided that the Zobrist keys, described below, are sufficiently random). Please refer to Robert Hyatt's on-line article on hash collisions if you want to understand why we don't need more than 64 bits.
Zobrist keys
The 64-bit signature of the chess position (stored in hashkey, a new member of the board structure) is constructed as follows:
hashkey = 0;
for (square = 0; square < 64; square++)
if (piece(square)) hashkey ^= ZOBRISTKEYS[square][piece(square)];
This shows how pieces on the board are folded into a 64-bit hash key (unique signature). The ZOBRISTKEYS are 64-bit random numbers, and initialized at program start-up. We also have to fold in the side to move, castling rights, and the en-passant target square. The technique was proposed by Albert Zobrist in 1970.
The XOR
operator has the useful
property that it acts like an on/off switch: if you XOR a value 2
times by the same bit pattern, it will return to its original value. We can
fold a white pawn on e2 into the key by:
hashkey ^= ZOBRISTKEYS[E2][WHITE_PAWN]
and we can remove the pawn by doing the same operation again.
So ZOBRISTKEYS[E2][WHITE_PAWN] is
an on/off switch for a white pawn on square e2. Note that hashing
is a one-way street: you can generate the signature for any given
position, but you cannot derive the chess position from a hash key (and
we don't need to).
Makemove and unmakemove
are now modified accordingly to update the position signature as pieces are moving
around and/or captured.
C++ has a rand()function that generates pseudo-random numbers, in the range 0 to 32767. We use it to generate 64-bit random numbers:
U64 rand64()
{
return rand()^((U64)rand()<<15)^((U64)rand()<<30)^((U64)rand()<<45)^((U64)rand()<<60);
}
To make the series of random numbers even 'more random', srand(seed) can be used to initialize rand(). For every different seed value, rand() will generate a different series of random numbers. Using the current time (i.e. the number of seconds that have elapsed since January 1, 1970) as seed for srand(), we will never get the same series of random numbers:
time_t now;
srand((unsigned int)time(&now));
In order to be able to scan all previous signatures, the signature is added to the GameLineRecord structure. Before we start a new search loop over moves, repetitionCount (a new function) will count the number of times that the current position has occurred. If it's 3 or more, the draw score is returned. All of this hardly affects speed, because the computations to update the signature and to detect repetitions are quite fast.
Also note that we don't have to go back all the way to the start position for a repetition check. The fiftyMove counter will tell us when the last irreversible move was done: we don't need to go back further than that. Also, every other position can be skipped, because positions with the other side to move cannot possibly be the same as the current position.
int repetitionCount()
{
rep = 1;
ilast = endOfSearch - fiftyMove;
for (i = endOfSearch - 2; i >= ilast; i -= 2)
if (gameLine[i].key == hashkey) rep++;
return rep;
}
One positive side-effect of having hash keys is that implementing a hash table will become an almost trivial task.
step 67: hash.h
#ifndef WINGLET_HASH_H_
#define WINGLET_HASH_H_
#include "defines.h"
// random 64-bit keys to give every position an 'almost' unique signature:
struct HashKeys
{
// total size = 1093 * 8 = 8744 bytes (minimum required is 6312):
U64 keys[64][16]; // position, piece (only 12 out of 16 piece are values used)
U64 side; // side to move (black)
U64 ep[64]; // ep targets (only 16 used)
U64 wk; // white king-side castling right
U64 wq; // white queen-side castling right
U64 bk; // black king-side castling right
U64 bq; // black queen-side castling right
void init(); // initialize the random data
U64 rand64(); // 64-bit random number generator
};
#endif
step 68: hash.cpp
#include <ctime>
#include <iostream>
#include <stdlib.h>
#include "hash.h"
#include "timer.h"
#include "protos.h"
void HashKeys::init()
{
// initialize all random 64-bit numbers
int i,j;
time_t now;
// use current time (in seconds) as random seed:
srand((unsigned int)time(&now));
for (i = 0; i < 64; i++)
{
ep[i] = rand64();
for (j = 0; j < 16; j++) keys[i][j] = rand64();
}
side = rand64();
wk = rand64();
wq = rand64();
bk = rand64();
bq = rand64();
return;
}
U64 HashKeys::rand64()
{
return rand()^((U64)rand()<<15)^((U64)rand()<<30)^((U64)rand()<<45)^((U64)rand()<<60);
}
step 69: globals.h
#ifndef WINGLET_GLOBALS_H
#define WINGLET_GLOBALS_H
#include "defines.h"
#include "board.h"
#include "hash.h"
char CMD_BUFF[MAX_CMD_BUFF];
(...)
// Search parameters start here:
int LARGE_NUMBER = KING_VALUE + 1;
int CHECKMATESCORE = KING_VALUE;
int STALEMATESCORE = 0;
int DRAWSCORE = 0;
Move NOMOVE;
HashKeys KEY;
#endif
step 70: extglobals.h
#ifndef WINGLET_EXTGLOBALS_H
#define WINGLET_EXTGLOBALS_H
#include "defines.h"
#include "board.h"
#include "hash.h"
extern char CMD_BUFF[];
extern int CMD_BUFF_COUNT;
(...)
extern Move NOMOVE;
extern HashKeys KEY;
#endif
step 71: data.cpp
#include <iostream>
#include <iomanip>
#include "defines.h"
#include "protos.h"
#include "extglobals.h"
void dataInit()
{
// ===========================================================================
// Initialization of global data at program startup.
// This function should be called only once (or else the mirrored data will be
// mirrored back again!!)
// ===========================================================================
unsigned char CHARBITSET[8];
int i, square, rank, file, arank, afile, state, slide, diaga1h8, diaga8h1, attackbit;
unsigned char state6Bit, state8Bit, attack8Bit;
Move move;
(...)
NOMOVE.moveInt = 0;
KEY.init();
return;
}
void info()
{
// your playground... display variables - meant for testing/verification purposes only
std::cout << std::endl << "============ info start ==============" << std::endl;
std::cout << "size of board, in bytes = " << sizeof(board) << std::endl;
std::cout << "Material value = " << board.Material << std::endl;
std::cout << "White castling rights = " << int(board.castleWhite) << std::endl;
std::cout << "Black castling rights = " << int(board.castleBlack) << std::endl;
std::cout << "En-passant square = " << board.epSquare << std::endl;
std::cout << "Fifty move count = " << board.fiftyMove << std::endl;
std::cout << "bitCnt of white pawns = " << bitCnt(board.whitePawns) << std::endl;
std::cout << std::endl << "bitmap of blackKnights | board.whitePawns:" << std::endl;
displayBitmap(board.blackKnights | board.whitePawns);
std::cout << "============ info end ================" << std::endl << std::endl;
return;
}
step 72: 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;
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();
};
#endif
|
|
|
 |
|
last update: Saturday 18 June 2011