 |
 |
 |
 |
Writing a chess program in 99 steps
20 Time control and running test suites
Most chess games are played under some time constraints, which means
that we need to define how much computer time is going to be allocated for the next move, and
we also need to have a way to (properly) interrupt the search when our
time is up. When implementing time control in a chess engine,
there are a number of issues that need to be addressed:
1) Computer time allocated for the current move. This will be
discussed in the next section, when we connect the engine to Winboard.
For now, it is sufficient to implement a new user command 'time n', it
defines the maximum search time per move (n is in units of seconds).
The global parameter STOPFRAC will prevent
starting a new iteration if the STOPFRAC-fraction
of the time has passed. I have set this value to 0.7. So if
70% of the total allocated time has passed, we don't start a new
iteration at the next ply level. Chances are that this iteration
will not be completed anyhow, and in that case it's probably better to
save our time for the next turn. If you want to maximize the
allocated thinking time (e.g. when running a test suite), just set
this value to 1.0.
The search will stop when the required depth is reached (set with '
sd n') or if time is up (set with 'time n'),
whichever comes first.
2) Checking the remaining time during search (peek at the clock).
Peeking at the clock is done based on number of nodes searched.
UPDATEINTERVAL defines how often we peek at the clock, in
units of nodes searched between peeks.
countdown (counting down from UPDATEINTERVAL
to 0) keeps track of the number of nodes searched between peeks.
When countdown <= 0
the search calls readClockAndInput()
to check if time is up, or if there is input (from the user or winboard)
that needs to be attended and it resets countdown.
A timedout flag is set if there is no time
left or if we need to exit the search for any other reason.
UPDATEINTERVAL is currently set at 100000, which
means that the peek frequency is roughly 10x per second.
This parameter can be changed, which might be desirable for extremely
long search times, or needed for extremely short search times.
3) Appropriately exit from the search, when time is up.
This is done by returning zero if the timedout
flag is set:
if (timedout) return 0;
However, we cannot just exit the search from any location,
because this could leave the board in an undefined state.
We need to
ensure that we leave the board in the same state
as when it entered the function. For instance, a return
statement cannot be placed between
makeMove and
unmakeMove.
4) Where is our best move if we have to exit the search
prematurely?
This one is easy to answer, because we already have an array
lastPV, that will always get updated with the latest
PV.
We always have our best move available in
lastPV[0], at any time.
Running test suites
If a maximum search depth and maximum search time can be defined, then it also makes sense to automatically run a number of test positions and check how the engine performs under different circumstances. The purpose of running test suites (reading FEN positions from a file, and analyze each of them, using the current search parameters) is to verify if the engine indeed plays the best moves, or to tune search and evaluation parameters. Some test suites are specifically designed to measure chess engine playing strength, or test engines against possible weaknesses.
We already can read FEN-strings from a file, so all that remains to be done is loop over all positions in a file, analyze each of them (using the current depth and time parameters) and write the results in a file for later analysis. During test runs, engine output is simply temporarily redirected to a log-file (called '<prefix>.log', where <prefix> is the test suite filename prefix). The command to run a test suite is simply: test 'filename'.
We can use BT2450.pgn to estimate winglet's ELO-rating. This suite was developed by Hubert Bednorz and Fred Toennissen to measure the tactical capability of chess engines. The engine is given 15 minutes to analyze each position. If a position is solved, the solution time is recorded in seconds. It doesn't count as a solution if the engine finds the move and then changes its mind. If the engine finds the move, changes its mind then finds the move again, that 2nd time is used. Any solution that is not found scores as 900 seconds. The 30 times are averaged and subtracted from 2450 to give the estimated ELO rating. So, if no solution is found, the estimated ELO rating will be 2450-900=1550. If the average time is 8 minutes (480 seconds), then the estimated ELO rating is 2450-480=1970. The suite has 30 test positions. Note that this file must be placed in the correct folder in order for winglet to find it, which is your main project folder (one level up from the Debug or Release folder).
To do the test yourself, start the
program and type 'sd 999' (to make sure search depth is set at
its maximum value), 'time 900' (900 seconds equals 15 minutes)
and then 'test BT2450.pgn'.
Beware, this test is going to take 30 x 15 minutes = 7.5 hours!
The table below summarizes my results, resulting in an estimated ELO-rating of 2030.
(note that winglet only has a basic search & evaluation, and no hash tables):
B2450.pgn BT2450 best move: Winglet final move: found at ply: found after (seconds): ply after 15 min: BT2450 score:
(lower is better)position #1 Nxg7 Rf2 5 0.031 10 900 position #2 Bxb6 Bxb6 16 394 17 394 position #3 Re6 Re6 10 416 11 416 position #4 Qf7 Rb1 4 420 10 900 position #5 Ka6 Kc5 11 0.967 17 900 position #6 e3 e3 10 119 12 119 position #7 Rd6 Rc2 10 241 10 900 position #8 Rxc6+ Rxc6+ 8 3 12 3 position #9 g5 g5 10 121 11 121 position #10 Rxg7+ Bh6 5 0.047 11 900 position #11 Qxh2+ Qxh2+ 11 326 13 326 position #12 Qe4 b6 11 765 11 900 position #13 Nb4 Nb4 7 7 10 7 position #14 Rxh7 Rxh7 12 35 13 35 position #15 Rg6 Rg6 4 0 13 0 position #16 g6 Rxc4 1 0 13 900 position #17 Qxf4 Rxf4 10 276 11 900 position #18 d6 a5 9 0.203 17 900 position #19 f3 f3 11 68 13 68 position #20 Ra2 Ng5 4 0.016 11 900 position #21 Re6 Re6 7 2 11 2 position #22 a3 a3 9 3 12 3 position #23 Qf6 Bh6 4 0 14 900 position #24 g6 g6 11 12 15 12 position #25 Nd3 Nd3 12 8 13 8 position #26 f5 f5 3 0.016 10 0.016 position #27 Bb4 Qxe4 1 0 12 900 position #28 Ne4 Ne4 7 2.53 11 2.53 position #29 Ke1 Ke1 7 0.765 12 0.765 position #30 f4 f4 13 273 14 273 average: 420 est'd ELO-rating: 2030 nodes searched: 34,146,907,009
One way of improving an engine is to run this type of tests suites, and
try to figure out why some solutions were not found (in above test, 12
out of 30 solutions were not found !). It may simply be caused by
a lack of speed, or there might be a bug or weakness in the search &
evaluation that needs to be fixed. Another important performance indicator
is the time (or nodes visited) it took before a correct solution was
found. The goal is of course to visit less nodes without loss of
accuracy (which is equivalent to finding the solution faster, which is
equivalent to a higher ELO-rating).
step 95: protos.h
#ifndef WINGLET_PROTOS_H
#define WINGLET_PROTOS_H
#include "board.h"
#include "move.h"
unsigned int bitCnt(BitMap);
int captgen(int);
void dataInit();
void displayBitmap(BitMap);
void displayMove(Move &);
void displayPV();
BOOLTYPE doCommand(const char *);
unsigned int firstOne(BitMap);
void info();
BOOLTYPE isAttacked(BitMap &, const unsigned char &);
BOOLTYPE isOtherKingAttacked();
BOOLTYPE isOwnKingAttacked();
BOOLTYPE isValidTextMove(char *, Move &);
unsigned int lastOne(BitMap);
void makeBlackPromotion(unsigned int, unsigned int &);
void makeCapture(unsigned int &, unsigned int &);
void makeMove(Move &);
void makeWhitePromotion(unsigned int, unsigned int &);
int movegen(int);
void mstostring(U64 dt, char *);
U64 perft(int, int);
void readCommands();
BOOLTYPE readFen(char *, int);
void setup();
void setupFen(char *, char *, char *, char *, int , int );
void test(char *);
BOOLTYPE toSan(Move &, char *);
void unmakeBlackPromotion(unsigned int, unsigned int &);
void unmakeCapture(unsigned int &, unsigned int &);
void unmakeMove(Move &);
void unmakeWhitePromotion(unsigned int, unsigned int &);
#endif
step 96: 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 square[64]; // incrementally updated, this array is usefull if we want to
// probe what kind of piece is on a particular square.
int Material; // incrementally updated, total material balance on board,
// in centipawns, from white’s side of view
int totalWhitePawns; // sum of P material value for white (in centipawns)
int totalBlackPawns; // sum of P material value for black (in centipawns)
int totalWhitePieces; // sum of Q+R+B+N material value for white (in centipawns)
int totalBlackPieces; // sum of Q+R+B+N material value for black (in centipawns)
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;
BOOLTYPE allownull;
U64 inodes;
U64 countdown;
U64 maxTime;
BOOLTYPE timedout;
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);
int qsearch(int ply, 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 display();
void rememberPV();
void selectmove(int &ply, int &i, int &depth, BOOLTYPE &followpv);
void addCaptScore(int &ifirst, int &index);
int SEE(Move &move);
BitMap attacksTo(int &target);
BitMap revealNextAttacker(BitMap &attackers, BitMap &nonremoved, int &target, int &heading);
void readClockAndInput();
};
#endif
step 97: globals.h
(...)
// Nullmove parameters:extern const int NULLMOVE_REDUCTION = 4; // equivalent to R=3
// Material (excluding pawns) must be > NULLMOVE_LIMIT to allow a nullmove:
// Setting this value to 299 ensures that null moves are not done if the
// side to move has no major or minor pieces
extern const int NULLMOVE_LIMIT = KNIGHT_VALUE - 1;
// peek interval in searched node units
int UPDATEINTERVAL = 100000;
// don't start a new iteration if STOPFRAC fraction of our max search time has passed:
double STOPFRAC = 0.7;
// keep track of stdout (writing to a file or to the console):
int TOCONSOLE;
#endif
step 98: extglobals.h
(...)
extern const int NULLMOVE_REDUCTION;
extern const int NULLMOVE_LIMIT;
extern int UPDATEINTERVAL;
extern double STOPFRAC;
extern int TOCONSOLE;
#endif
step 99: command.cpp
(...)
// =================================================================
// help, h, or ?: show this help
// =================================================================
if ((!strcmp(buf, "help")) || (!strcmp(buf, "h")) || (!strcmp(buf, "?")))
{
std::cout << std::endl << "help:" << std::endl;
std::cout << "black : BLACK to move" << std::endl;
std::cout << "cc : play computer-to-computer " << std::endl;
std::cout << "d : display board " << std::endl;
std::cout << "exit : exit program " << std::endl;
std::cout << "eval : show static evaluation of this position" << std::endl;
std::cout << "game : show game moves " << std::endl;
std::cout << "go : computer next move " << std::endl;
std::cout << "help, h, or ? : show this help " << std::endl;
std::cout << "info : display variables (for testing purposes)" << std::endl;
std::cout << "move e2e4, or h7h8q : enter a move (use this format)" << std::endl;
std::cout << "moves : show all legal moves" << std::endl;
std::cout << "new : start new game" << std::endl;
std::cout << "perf : benchmark a number of key functions" << std::endl;
std::cout << "perft n : calculate raw number of nodes from here, depth n " << std::endl;
std::cout << "quit : exit program " << std::endl;
std::cout << "r : rotate board " << std::endl;
std::cout << "readfen filename n : reads #-th FEN position from filename" << std::endl;
#ifdef WINGLET_VERBOSE_SEE
std::cout << "qsearch : shows sorted capture movelist" << std::endl;
#endif
std::cout << "sd n : set the search depth to n" << std::endl;
std::cout << "setup : setup board... " << std::endl;
std::cout << "test filename : starts search on all FEN position in 'filename'" << std::endl;
std::cout << " using current time & search depth parameters" << std::endl;
std::cout << " output is written in filename.log" << std::endl;
std::cout << "time s : time per move in seconds" << std::endl;
std::cout << "undo : take back last move" << std::endl;
std::cout << "white : WHITE to move" << std::endl;
std::cout << std::endl;
CMD_BUFF_COUNT = '\0';
return true;
}
(...)
// =================================================================
// test filename : starts search on all FEN position in 'filename'
// using current time & search depth parameters
// output is written in test.log
// =================================================================
if (!strncmp(buf, "test", 4))
{
sscanf(buf+4,"%s", userinput);
board.init();
test(userinput);
CMD_BUFF_COUNT = '\0';
return true;
}
// =================================================================
// time s : time per move in seconds
// =================================================================
if (!strncmp(buf, "time", 4))
{
number = (int)board.maxTime / 1000;
sscanf(buf+4,"%d", &number);
if (number < 1) number = 1;
std::cout << "winglet> search time " << number << " seconds" << std::endl;
board.maxTime = number * 1000; // conversion to ms
CMD_BUFF_COUNT = '\0';
return true;
}
(...)
step 100: peek.cpp
#include <conio.h>
#include "extglobals.h"
#include "timer.h"
void Board::readClockAndInput()
{
// check if we need to stop, because time is up, or because the user has hit the keyboard.
// UPDATEINTERVAL defines how often this check is done in terms of nodes searched.
// For example, if the search speed is 1000 knods per second, then a value of UPDATEINTERVAL = 100000
// will result in 10 checks per second (or 0.1s time intervals)
countdown = UPDATEINTERVAL;
if ((timer.getms()-msStart > maxTime) || _kbhit())
{
timedout = true;
return;
}
return;
}
step 101: 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;
board.searchDepth = 16; // default for startup
board.maxTime = 2000; // default for startup, milliseconds
(...)
TOCONSOLE = 1;
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;
}
|
|
|
 |
|
last update: Friday 09 September 2011