 |
 |
 |
 |
Writing a chess program in 99 steps
step 54: globals.h
(...)
BitMap KINGSHIELD_STRONG_B[64];
BitMap KINGSHIELD_WEAK_W[64];
BitMap KINGSHIELD_WEAK_B[64];
BitMap WHITE_SQUARES;
BitMap BLACK_SQUARES;
// Search parameters start here:
int LARGE_NUMBER = KING_VALUE;
#endif
step 55: extglobals.h
(...)
extern BitMap KINGSHIELD_STRONG_W[];
extern BitMap KINGSHIELD_STRONG_B[];
extern BitMap KINGSHIELD_WEAK_W[];
extern BitMap KINGSHIELD_WEAK_B[];
extern BitMap WHITE_SQUARES;
extern BitMap BLACK_SQUARES;
extern int LARGE_NUMBER;
#endif
step 56: 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
// 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);
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
step 57: search.cpp
#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 ** later **
// The search stops if (whatever comes first):
// **later** - there is no legal move (checkmate or stalemate)
// **later** - there is only one legal move (in this case we don't need to search)
// **later** - time is up
// **later** - the search is interrupted by the user, or by winboard
// - the search depth is reached
int score;
timer.init();
displaySearchStats(1, 0, 0); // display console header
inodes = 0;
msStart = timer.getms();
// score = minimax(0, searchDepth);
// score = alphabeta(0, searchDepth, -LARGE_NUMBER, LARGE_NUMBER);
score = alphabetapvs(0, searchDepth, -LARGE_NUMBER, LARGE_NUMBER);
msStop = timer.getms();
displaySearchStats(2, searchDepth, score);
return (triangularArray[0][0]);
}
int Board::alphabetapvs(int ply, int depth, int alpha, int beta)
{
// PV search
int i, j, movesfound, val;
triangularLength[ply] = ply;
if (depth == 0) return board.eval();
movesfound = 0;
moveBufLen[ply+1] = movegen(moveBufLen[ply]);
for (i = moveBufLen[ply]; i < moveBufLen[ply+1]; i++)
{
makeMove(moveBuffer[i]);
{
if (!isOtherKingAttacked())
{
inodes++;
if (!ply) displaySearchStats(3, ply, i);
if (movesfound)
{
val = -alphabetapvs(ply+1, depth-1, -alpha-1, -alpha);
if ((val > alpha) && (val < beta))
{
val = -alphabetapvs(ply+1, depth - 1, -beta, -alpha); // In case of failure, proceed with normal alphabeta
}
}
else val = -alphabetapvs(ply+1, depth-1, -beta, -alpha); // Normal alphabeta
unmakeMove(moveBuffer[i]);
if (val >= beta)
{
return beta;
}
if (val > alpha)
{
alpha = val; // both sides want to maximize from *their* perspective
movesfound++;
triangularArray[ply][ply] = moveBuffer[i]; // save this move
for (j = ply + 1; j < triangularLength[ply + 1]; j++)
{
triangularArray[ply][j] = triangularArray[ply+1][j]; // and append the latest best PV from deeper plies
}
triangularLength[ply] = triangularLength[ply + 1];
if (!ply)
{
msStop = timer.getms();
displaySearchStats(2, depth, val);
}
}
}
else unmakeMove(moveBuffer[i]);
}
}
return alpha;
}
int Board::alphabeta(int ply, int depth, int alpha, int beta)
{
// Negascout
int i, j, val;
triangularLength[ply] = ply;
if (depth == 0) return board.eval();
moveBufLen[ply+1] = movegen(moveBufLen[ply]);
for (i = moveBufLen[ply]; i < moveBufLen[ply+1]; i++)
{
makeMove(moveBuffer[i]);
{
if (!isOtherKingAttacked())
{
inodes++;
if (!ply) displaySearchStats(3, ply, i);
val = -alphabeta(ply+1, depth-1, -beta, -alpha);
unmakeMove(moveBuffer[i]);
if (val >= beta)
{
return beta;
}
if (val > alpha)
{
alpha = val; // both sides want to maximize from *their* perspective
triangularArray[ply][ply] = moveBuffer[i]; // save this move
for (j = ply + 1; j < triangularLength[ply + 1]; j++)
{
triangularArray[ply][j] = triangularArray[ply+1][j]; // and append the latest best PV from deeper plies
}
triangularLength[ply] = triangularLength[ply + 1];
if (!ply)
{
msStop = timer.getms();
displaySearchStats(2, depth, val);
}
}
}
else unmakeMove(moveBuffer[i]);
}
}
return alpha;
}
int Board::minimax(int ply, int depth)
{
// Negamax
int i, j, val, best;
best = -LARGE_NUMBER;
triangularLength[ply] = ply;
if (depth == 0) return board.eval();
moveBufLen[ply+1] = movegen(moveBufLen[ply]);
for (i = moveBufLen[ply]; i < moveBufLen[ply+1]; i++)
{
makeMove(moveBuffer[i]);
{
if (!isOtherKingAttacked())
{
inodes++;
if (!ply) displaySearchStats(3, ply, i);
val = -minimax(ply+1, depth-1); // note the minus sign
unmakeMove(moveBuffer[i]);
if (val > best) // both sides want to maximize from *their* perspective
{
best = val;
triangularArray[ply][ply] = moveBuffer[i]; // save this move
for (j = ply + 1; j < triangularLength[ply + 1]; j++)
{
triangularArray[ply][j] = triangularArray[ply+1][j]; // and append the latest best PV from deeper plies
}
triangularLength[ply] = triangularLength[ply + 1];
if (!ply)
{
msStop = timer.getms();
displaySearchStats(2, depth, val);
}
}
}
else unmakeMove(moveBuffer[i]);
}
}
return best;
}
void Board::displaySearchStats(int mode, int depth, int score)
{
// displays various search statistics
// only to be used at 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
int i;
U64 dt, hh, mm, ss;
switch (mode)
{
case 1:
std::cout << "depth score nodes time knps PV" << std::endl;
break;
case 2:
dt = msStop - msStart;
// 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
if (dt > 3600000)
{
hh = dt/3600000;
mm = (dt - 3600000*hh)/60000;
ss = (dt - 3600000*hh - 60000*mm)/1000;
printf("%02d%c", hh, ':');
printf("%02d%c", mm, ':');
printf("%02d ", ss);
}
else if (dt > 60000)
{
mm = dt/60000;
ss = (dt - 60000*mm)/1000;
printf(" %02d%c", mm, ':');
printf("%02d ", ss);
}
else if (dt > 10000) printf(" %6.1f%c ", float(dt/1000.0), 's');
else if (dt > 1000) printf(" %6.2f%c ", float(dt/1000.0), 's');
else if (dt > 0) printf(" %5d%s ", dt, "ms");
else printf(" 0%s ", "ms");
// search speed
if (dt > 0) std::cout << std::setw(5) << (inodes/dt) << " ";
else std::cout << " - ";
// PV
for (i = 0; i < triangularLength[0]; i++)
{
displayMove(triangularArray[0][i]);
std::cout << " ";
}
std::cout << std::endl;
std::cout.flush();
break;
case 3:
printf("%12s (%2d/%2d)%16s", " ", score+1, moveBufLen[depth+1]-moveBufLen[depth], " ");
displayMove(moveBuffer[score + moveBufLen[depth]]);
printf("...\r");
break;
default: break;
}
return;
}
|
|
|
 |
|
last update: Saturday 11 June 2011