 |
 |
 |
 |
Writing a chess program in 99 steps
step 65: displaymove.cpp
#ifndef _CRT_SECURE_NO_DEPRECATE
#define _CRT_SECURE_NO_DEPRECATE
#endif
#include <iostream>
#include "defines.h"
#include "protos.h"
#include "extglobals.h"
void displayMove(Move &move)
{
// displays a single move on the console, no disambiguation
if (((move.getPiec() == WHITE_KING) && (move.isCastleOO())) || ((move.getPiec() == BLACK_KING) && (move.isCastleOO())))
{
std::cout << "O-O";
return;
};
if (((move.getPiec() == WHITE_KING) && (move.isCastleOOO())) || ((move.getPiec() == BLACK_KING) && (move.isCastleOOO())))
{
std::cout << "O-O-O";
return;
};
if (!move.isPawnmove()) std::cout << PIECECHARS[move.getPiec()];
if (move.isPawnmove() && move.isCapture()) std::cout << char('a' + FILES[move.getFrom()]-1);
if (move.isCapture()) std::cout << "x" ;
std::cout << char('a' + FILES[move.getTosq()]-1);
std::cout << RANKS[move.getTosq()];
if (move.isPromotion())
{
std::cout << "=";
std::cout << PIECECHARS[move.getProm()];
}
std::cout.flush();
return;
}
void displayPV()
{
int i;
char sanMove[12];
for (i = 0; i < board.triangularLength[0]; i++)
{
toSan(board.triangularArray[0][i], sanMove);
std::cout << sanMove << " ";
makeMove(board.triangularArray[0][i]);
}
for (i = board.triangularLength[0]-1; i >= 0; i--)
{
unmakeMove(board.triangularArray[0][i]);
}
if (i < 3) std::cout << " "; // make sure to overwrite any remaining output of mode 3
std::cout << std::endl;
std::cout.flush();
}
BOOLTYPE toSan(Move &move, char *sanMove)
{
// ===========================================================================
// toSan will convert a move into non-ambiguous SAN-notation, returned in char sanMove[].
// "move" must belong to the current "board". Returns true if successful.
// The move is compared with other moves from the current board position.
// Ambiguities can arise if two (or more) identical pieces can move to the same square.
// In such cases, the piece's initial is followed by (in this priority):
// - the from file, if it's unique,
// - or else the from rank, if it's unique
// - or else the from file and rank (this can happen after pawn promotions,
// e.g. with 4 rooks on c3, c7, a5 and e5; they all can move to c5, and then move notation would be: R3c5
// 'e.p.' is added for an en-passant capture
// '+'is added for check, '#' is added for mate.
// ===========================================================================
int i, j, k, ibuf, from, to, piece, capt, prom, ambigfile, ambigrank;
int asciiShift;
BOOLTYPE legal, check, mate, ambig;
asciiShift = (int)'a';
piece = move.getPiec();
from = move.getFrom();
to = move.getTosq();
capt = move.getCapt();
prom = move.getProm();
ibuf = 0;
ambig = false;
ambigfile = 0;
ambigrank = 0;
legal = false;
check = false;
mate = false;
sprintf(sanMove, "");
// Generate all pseudo-legal moves to be able to remove any ambiguities
// and check legality. Take the next free location in moveBufLen:
while (board.moveBufLen[ibuf+1]) ibuf++;
board.moveBufLen[ibuf+1] = movegen(board.moveBufLen[ibuf]);
// Loop over the moves to see what kind(s) of ambiguities exist, if any:
for (i = board.moveBufLen[ibuf]; i < board.moveBufLen[ibuf+1]; i++)
{
makeMove(board.moveBuffer[i]);
if (!isOtherKingAttacked())
{
if (board.moveBuffer[i].moveInt == move.moveInt)
{
legal = true;
// it is check:
if (isOwnKingAttacked())
{
check = true;
// is it checkmate?
k = 0;
board.moveBufLen[ibuf+2] = movegen(board.moveBufLen[ibuf+1]);
for (j = board.moveBufLen[ibuf+1]; j < board.moveBufLen[ibuf+2]; j++)
{
makeMove(board.moveBuffer[j]);
if (!isOtherKingAttacked()) k++;
unmakeMove(board.moveBuffer[j]);
}
if (!k) mate = true;
}
}
// two same pieces can move to the same square:
if ((board.moveBuffer[i].moveInt != move.moveInt) && (board.moveBuffer[i].getPiec() == piece) && (board.moveBuffer[i].getTosq() == to))
{
ambig = true;
if (FILES[from] == FILES[board.moveBuffer[i].getFrom()]) ambigfile++;
if (RANKS[from] == RANKS[board.moveBuffer[i].getFrom()]) ambigrank++;
}
}
unmakeMove(board.moveBuffer[i]);
}
// cleanup:
board.moveBufLen[ibuf+1] = 0;
board.moveBufLen[ibuf+2] = 0;
// construct the SAN string:
if (!legal)
{
strcpy(sanMove, "unknown");
return false;
}
else
{
// start building the string
if (!move.isPawnmove())
{
sprintf(sanMove, "%s", PIECECHARS[piece]);
if (ambig)
{
if (ambigfile)
{
if (ambigrank) sprintf(sanMove, "%s%c%d", sanMove, FILES[from] + asciiShift - 1,RANKS[from]);
else sprintf(sanMove, "%s%d", sanMove, RANKS[from]);
}
else
{
sprintf(sanMove, "%s%c", sanMove, FILES[from] + asciiShift - 1);
}
}
}
else
{
if (move.isCapture())
{
sprintf(sanMove, "%s%c", sanMove, FILES[from] + asciiShift - 1);
}
}
if (move.isCapture()) sprintf(sanMove, "%sx", sanMove);
sprintf(sanMove, "%s%c%d", sanMove, FILES[to] + asciiShift - 1, RANKS[to]);
if (move.isEnpassant()) sprintf(sanMove, "%s e.p.", sanMove);
if (move.isPromotion()) sprintf(sanMove, "%s=%s", sanMove, PIECECHARS[prom]);
if (check)
{
if (mate) sprintf(sanMove, "%s#", sanMove);
else sprintf(sanMove, "%s+", sanMove);
}
return true;
}
}
step 66: 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):
// - there is no legal move (checkmate or stalemate)
// - 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, legalmoves;
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:
// ===========================================================================
timer.init();
displaySearchStats(1, 0, 0); // display console header
moveBufLen[0] = 0;
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, pvmovesfound, val;
triangularLength[ply] = ply;
if (depth == 0) return board.eval();
movesfound = 0;
pvmovesfound = 0;
moveBufLen[ply+1] = movegen(moveBufLen[ply]);
for (i = moveBufLen[ply]; i < moveBufLen[ply+1]; i++)
{
makeMove(moveBuffer[i]);
{
if (!isOtherKingAttacked())
{
inodes++;
movesfound++;
if (!ply) displaySearchStats(3, ply, i);
if (pvmovesfound)
{
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
pvmovesfound++;
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]);
}
}
// ===========================================================================
// 50-move rule:
// ===========================================================================
if (fiftyMove >= 100) return DRAWSCORE;
// ===========================================================================
// Checkmate/stalemate detection:
// ===========================================================================
if (!movesfound)
{
if (isOwnKingAttacked()) return (-CHECKMATESCORE+ply-1);
else return (STALEMATESCORE);
}
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 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];
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(" %5dms ", dt);
else printf(" 0ms ");
// search speed
if (dt > 0) std::cout << std::setw(5) << (inodes/dt) << " ";
else std::cout << " - ";
// PV
displayPV();
break;
case 3: // Note that the numbers refer to pseudo-legal moves:
printf("%12s (%2d/%2d)%16s", " ", score+1, moveBufLen[depth+1]-moveBufLen[depth], " ");
unmakeMove(moveBuffer[score]);
toSan(moveBuffer[score], sanMove);
std::cout << sanMove;
makeMove(moveBuffer[score]);
printf("... \r");
std::cout.flush();
break;
default: break;
}
return;
}
BOOLTYPE Board::isEndOfgame(int &legalmoves, Move &singlemove)
{
// Checks if the current position is end-of-game due to:
// checkmate, stalemate, 50-move rule, or insufficient material
int whiteknights, whitebishops, whiterooks, whitequeens, whitetotalmat;
int blackknights, blackbishops, blackrooks, blackqueens, blacktotalmat;
// are we checkmating the other side?
int i;
if (isOtherKingAttacked())
{
if (nextMove) std::cout << "1-0 {Black mates}" << std::endl;
else std::cout << "1-0 {White mates}" << std::endl;
return true;
}
// how many legal moves do we have?
legalmoves = 0;
moveBufLen[0] = 0;
moveBufLen[1] = movegen(moveBufLen[0]);
for (i = moveBufLen[0]; i < moveBufLen[1]; i++)
{
makeMove(moveBuffer[i]);
if (!isOtherKingAttacked())
{
legalmoves++;
singlemove = moveBuffer[i];
}
unmakeMove(moveBuffer[i]);
}
// checkmate or stalemate?
if (!legalmoves)
{
if (isOwnKingAttacked())
{
if (nextMove) std::cout << "1-0 {White mates}" << std::endl;
else std::cout << "1-0 {Black mates}" << std::endl;
}
else std::cout << "1/2-1/2 {stalemate}" << std::endl;
return true;
}
// draw due to insufficient material:
if (!whitePawns && !blackPawns)
{
whiteknights = bitCnt(whiteKnights);
whitebishops = bitCnt(whiteBishops);
whiterooks = bitCnt(whiteRooks);
whitequeens = bitCnt(whiteQueens);
whitetotalmat = 3 * whiteknights + 3 * whitebishops + 5 * whiterooks + 10 * whitequeens;
blackknights = bitCnt(blackKnights);
blackbishops = bitCnt(blackBishops);
blackrooks = bitCnt(blackRooks);
blackqueens = bitCnt(blackQueens);
blacktotalmat = 3 * blackknights + 3 * blackbishops + 5 * blackrooks + 10 * blackqueens;
// king versus king:
if ((whitetotalmat == 0) && (blacktotalmat == 0))
{
std::cout << "1/2-1/2 {material}" << std::endl;
return true;
}
// king and knight versus king:
if (((whitetotalmat == 3) && (whiteknights == 1) && (blacktotalmat == 0)) ||
((blacktotalmat == 3) && (blackknights == 1) && (whitetotalmat == 0)))
{
std::cout << "1/2-1/2 {material}" << std::endl;
return true;
}
// 2 kings with one or more bishops, all bishops on the same colour:
if ((whitebishops + blackbishops) > 0)
{
if ((whiteknights == 0) && (whiterooks == 0) && (whitequeens == 0) &&
(blackknights == 0) && (blackrooks == 0) && (blackqueens == 0))
{
if (!((whiteBishops | blackBishops) & WHITE_SQUARES) ||
!((whiteBishops | blackBishops) & BLACK_SQUARES))
{
std::cout << "1/2-1/2 {material}" << std::endl;
return true;
}
}
}
}
if (fiftyMove >= 100)
{
std::cout << "1/2-1/2 {50-move rule}" << std::endl;
return true;
}
return false;
}
|
|
|
|
|
 |
|
last update: Friday 17 June 2011