 |
 |
 |
 |
Writing a chess program in 99 steps
step 102: test.cpp
#ifndef _CRT_SECURE_NO_DEPRECATE // suppress MS security warnings
#define _CRT_SECURE_NO_DEPRECATE
#endif
#include <io.h>
#include <iostream>
#include <string>
#include "defines.h"
#include "protos.h"
#include "extglobals.h"
void test(char *filename)
{
// runs a testsuite with current depth and time search parameters
int i, file;
U64 inodestotal;
U64 timetotal;
Timer totaltime;
std::string logfile (filename);
totaltime.init();
inodestotal = 0;
std::cout << "START OF TEST:" << std::endl;
std::cout << "MAX SEARCH DEPTH = " << board.searchDepth << std::endl;
std::cout << "MAX SEARCH TIME = " << board.maxTime/1000 << "s" << std::endl;
// construct logfile name
logfile.replace(logfile.find("."),logfile.length(),".log");
// redirect stdout to the log file
TOCONSOLE = 0;
file = _dup(_fileno(stdout)); // create a file descriptor for stdout
freopen(logfile.c_str(),"w",stdout);
std::cout << std::endl << std::endl << "+++++++++++++++++++++++++++++++++++++++" << std::endl;
std::cout << "START OF TEST:" << std::endl;
std::cout << "MAX SEARCH DEPTH = " << board.searchDepth << std::endl;
std::cout << "MAX SEARCH TIME = " << board.maxTime/1000 << "s" << std::endl;
std::cout << "+++++++++++++++++++++++++++++++++++++++" << std::endl;
i = 1;
while (readFen(filename, i))
{
// write progress to console:
_dup2(file ,_fileno(stdout));
_close(file);
printf("winglet> position #%d\n", i);
file = _dup(_fileno(stdout));
freopen(logfile.c_str(),"a",stdout);
board.display();
board.think();
inodestotal += board.inodes;
i++;
}
timetotal = totaltime.getms();
std::cout << std::endl << std::endl << "+++++++++++++++++++++++++++++++++++++++" << std::endl;
std::cout << "SUMMARY:" << std::endl;
std::cout << "TOTAL TIME SEARCHED = " << timetotal << " ms" << std::endl;
std::cout << "TOTAL NODES SEARCHED = " << inodestotal << std::endl;
std::cout << "AVG SEARCH SPEED = " << inodestotal/timetotal << " knps" << std::endl;
std::cout << "+++++++++++++++++++++++++++++++++++++++" << std::endl;
_dup2(file ,_fileno(stdout)); // reassign file descriptor
_close(file);
TOCONSOLE = 1;
return;
}
step 103: search.cpp
#ifndef _CRT_SECURE_NO_DEPRECATE
#define _CRT_SECURE_NO_DEPRECATE
#endif
#include <conio.h>
#include <stdio.h>
#include <iostream>
#include <iomanip>
#include "defines.h"
#include "extglobals.h"
#include "protos.h"
#include "board.h"
#include "timer.h"
Move Board::think()
{
// ===========================================================================
// This is the entry point for search, it is intended to drive iterative deepening
// The search stops if (whatever comes first):
// - there is no legal move (checkmate or stalemate)
// - there is only one legal move (in this case we don't need to search)
// - time is up
// - the search is interrupted by the user, or by winboard
// - the search depth is reached
// ===========================================================================
int score, legalmoves, currentdepth;
Move singlemove;
// ===========================================================================
// Check if the game has ended, or if there is only one legal move,
// because then we don't need to search:
// ===========================================================================
if (isEndOfgame(legalmoves, singlemove)) return NOMOVE;
if (legalmoves == 1)
{
std::cout << "forced move: "; displayMove(singlemove); std::cout << std::endl;
return singlemove;
}
// ===========================================================================
// There is more than legal 1 move, so prepare to search:
// ===========================================================================
lastPVLength = 0;
memset(lastPV, 0 , sizeof(lastPV));
memset(whiteHeuristics, 0, sizeof(whiteHeuristics));
memset(blackHeuristics, 0, sizeof(blackHeuristics));
inodes = 0;
countdown = UPDATEINTERVAL;
timedout = false;
// display console header
displaySearchStats(1, 0, 0);
timer.init();
msStart = timer.getms();
// iterative deepening:
for (currentdepth = 1; currentdepth <= searchDepth; currentdepth++)
{
// clear the buffers:
memset(moveBufLen, 0, sizeof(moveBufLen));
memset(moveBuffer, 0, sizeof(moveBuffer));
memset(triangularLength, 0, sizeof(triangularLength));
memset(triangularArray, 0, sizeof(triangularArray));
followpv = true;
allownull = true;
score = alphabetapvs(0, currentdepth, -LARGE_NUMBER, LARGE_NUMBER);
// now check if time is up
// if not decide if it makes sense to start another iteration:
if (timedout)
{
std::cout << std::endl;
return (lastPV[0]);
}
else
{
msStop = timer.getms();
if ((msStop - msStart) > (STOPFRAC * maxTime))
{
std::cout << " ok" << std::endl;
return (lastPV[0]);
}
}
displaySearchStats(2, currentdepth, score);
// stop searching if the current depth leads to a forced mate:
if ((score > (CHECKMATESCORE-currentdepth)) || (score < -(CHECKMATESCORE-currentdepth)))
currentdepth = searchDepth;
}
return (lastPV[0]);
}
int Board::alphabetapvs(int ply, int depth, int alpha, int beta)
{
// PV search
int i, j, movesfound, pvmovesfound, val;
triangularLength[ply] = ply;
if (depth <= 0)
{
followpv = false;
return qsearch(ply, alpha, beta);
}
// repetition check:
if (repetitionCount() >= 3) return DRAWSCORE;
// now try a null move to get an early beta cut-off:
if (!followpv && allownull)
{
if ((nextMove && (board.totalBlackPieces > NULLMOVE_LIMIT)) || (!nextMove && (board.totalWhitePieces > NULLMOVE_LIMIT)))
{
if (!isOwnKingAttacked())
{
allownull = false;
inodes++;
if (--countdown <=0) readClockAndInput();
nextMove = !nextMove;
hashkey ^= KEY.side;
val = -alphabetapvs(ply, depth - NULLMOVE_REDUCTION, -beta, -beta+1);
nextMove = !nextMove;
hashkey ^= KEY.side;
if (timedout) return 0;
allownull = true;
if (val >= beta) return val;
}
}
}
allownull = true;
movesfound = 0;
pvmovesfound = 0;
moveBufLen[ply+1] = movegen(moveBufLen[ply]);
for (i = moveBufLen[ply]; i < moveBufLen[ply+1]; i++)
{
selectmove(ply, i, depth, followpv);
makeMove(moveBuffer[i]);
{
if (!isOtherKingAttacked())
{
inodes++;
if (--countdown <=0) readClockAndInput();
movesfound++;
if (!ply) displaySearchStats(3, ply, i);
if (pvmovesfound)
{
val = -alphabetapvs(ply+1, depth-1, -alpha-1, -alpha);
if ((val > alpha) && (val < beta))
{
// in case of failure, proceed with normal alphabeta
val = -alphabetapvs(ply+1, depth - 1, -beta, -alpha);
}
}
// normal alphabeta
else val = -alphabetapvs(ply+1, depth-1, -beta, -alpha);
unmakeMove(moveBuffer[i]);
if (timedout) return 0;
if (val >= beta)
{
// update the history heuristic
if (nextMove)
blackHeuristics[moveBuffer[i].getFrom()][moveBuffer[i].getTosq()] += depth*depth;
else
whiteHeuristics[moveBuffer[i].getFrom()][moveBuffer[i].getTosq()] += depth*depth;
return beta;
}
(...)
void Board::displaySearchStats(int mode, int depth, int score)
{
// displays various search statistics
// only to be used when ply = 0
// mode = 1 : display header
// mode = 2 : display full stats, including score and latest PV
// mode = 3 : display current root move that is being searched
// depth = ply, score = loop counter in the search move list
char sanMove[12], timestring[8];
U64 dt;
dt = timer.getms() - msStart;
switch (mode)
{
case 1:
std::cout << "depth score nodes time knps PV" << std::endl;
break;
case 2:
// depth
printf("%5d ", depth);
// score
printf("%+6.2f ", float(score/100.0));
// nodes searched
if (inodes > 100000000) printf("%6.0f%c ", float(inodes/1000000.0), 'M');
else if (inodes > 10000000) printf("%6.2f%c ", float(inodes/1000000.0), 'M');
else if (inodes > 1000000) printf("%6.0f%c ", float(inodes/1000.0), 'K');
else if (inodes > 100000) printf("%6.1f%c ", float(inodes/1000.0), 'K');
else if (inodes > 10000) printf("%6.2f%c ", float(inodes/1000.0), 'K');
else printf("%7d ", inodes);
// search time
mstostring(dt, timestring);
printf("%8s ", timestring);
// search speed
if (dt > 0) std::cout << std::setw(5) << (inodes/dt) << " ";
else std::cout << " - ";
// store this PV:
rememberPV();
// display the PV
displayPV();
break;
case 3: // Note that the numbers refer to pseudo-legal moves:
if (!TOCONSOLE) break;
mstostring(dt, timestring);
printf(" (%2d/%2d) %8s ", score+1, moveBufLen[depth+1]-moveBufLen[depth], timestring);
unmakeMove(moveBuffer[score]);
toSan(moveBuffer[score], sanMove);
std::cout << sanMove;
makeMove(moveBuffer[score]);
printf("... \r");
std::cout.flush();
break;
default: break;
}
return;
}
(...)
void mstostring(U64 dt, char *timestring)
{
// convert milliseconds to a time string (hh:mm:ss, mm:ss, s, ms)
U64 hh, mm, ss;
if (dt > 3600000)
{
hh = dt/3600000;
mm = (dt - 3600000*hh)/60000;
ss = (dt - 3600000*hh - 60000*mm)/1000;
sprintf(timestring, "%02d:%02d:%02d", hh, mm, ss);
}
else if (dt > 60000)
{
mm = dt/60000;
ss = (dt - 60000*mm)/1000;
sprintf(timestring, "%02d:%02d", mm, ss);
}
else if (dt > 10000) sprintf(timestring, "%6.1f%s", float(dt/1000.0), "s");
else if (dt > 1000) sprintf(timestring, "%6.2f%s", float(dt/1000.0), "s");
else if (dt > 0) sprintf(timestring, "%5dms", dt);
else sprintf(timestring, "0ms");
return;
}
step 104: qsearch.cpp
#include "defines.h"
#include "extglobals.h"
#include "protos.h"
#include "board.h"
int Board::qsearch(int ply, int alpha, int beta)
{
// quiescence search
int i, j, val;
if (timedout) return 0;
triangularLength[ply] = ply;
if (isOwnKingAttacked()) return alphabetapvs(ply, 1, alpha, beta);
val = board.eval();
if (val >= beta) return val;
if (val > alpha) alpha = val;
// generate captures & promotions:
// captgen returns a sorted move list
moveBufLen[ply+1] = captgen(moveBufLen[ply]);
for (i = moveBufLen[ply]; i < moveBufLen[ply+1]; i++)
{
makeMove(moveBuffer[i]);
{
if (!isOtherKingAttacked())
{
inodes++;
if (--countdown <=0) readClockAndInput();
val = -qsearch(ply+1, -beta, -alpha);
unmakeMove(moveBuffer[i]);
if (val >= beta) return val;
if (val > alpha)
{
alpha = val;
triangularArray[ply][ply] = moveBuffer[i];
for (j = ply + 1; j < triangularLength[ply+1]; j++)
{
triangularArray[ply][j] = triangularArray[ply+1][j];
}
triangularLength[ply] = triangularLength[ply+1];
}
}
else unmakeMove(moveBuffer[i]);
}
}
return alpha;
}
√ you can run 'test BT2405.pgn' now. Note that it takes 7.5 hours to complete the test.
Depending on your hardware, I expect that winglets ELO rating ends up being somewhere around 2000.
|
|
|
 |
|
last update: Friday 08 July 2011