Author: Geoff
Date: 11:04:39 06/05/03
Go up one level in this thread
Hello Dan
I thought it would be too much code to post and the web page formatting would
make it tricky to read. I will give it a go anyways, here are the think(),
search(), and checkup() routines, I must have made a mistake or several ;-) in
one of these functions
Geoff
#include <stdio.h>
#include <string.h>
#include "portab.h"
#include "chess.h"
#include "globals.h"
/* see the beginning of think() */
#include <setjmp.h>
jmp_buf env;
U32 stopSearch;
U32 nullMovesMade = 0;
/****************************************************************************/
/* */
/* Function: checkUp */
/* */
/* Description: This function is called once in a while during the search. */
/* */
/* Author: G.Westwood 17/04/2003 */
/* */
/* Inputs: */
/* */
/* */
/* Outputs: */
/* NONE */
/* */
/* */
/****************************************************************************/
void checkUp(void)
{
/* is the engine's time up? if so, longjmp back to the
beginning of think(), only if no nullmoves made though */
if (nullMovesMade == 0 && get_ms() >= stopTime )
{
stopSearch = TRUE;
longjmp(env, 0);
}
}
/****************************************************************************/
/* */
/* Function: Simple Alpha Beta Search */
/* */
/* Description: This function */
/* */
/* Author: G.Westwood 14/04/2003 */
/* */
/* Inputs: */
/* U32 depth */
/* */
/* Outputs: */
/* S32 */
/* */
/* */
/****************************************************************************/
S32 search(S32 alpha, S32 beta, S32 depth, U32 doNull)
{
S32 best = -INFINITY, nullScore;
S32 value;
U32 i, j, weAreInCheck;
U32 anyLegalMoves;
U32 epTemp;
move currentMove;
S8 tempMoveStr[10];
/* we're as deep as we want to be; call quiesce() to get
a reasonable score and return it. */
if (depth <= 0)
return quiesce(alpha, beta);
nodes++;
/* if this isn't the root of the search tree (where we have
to pick a move and can't simply return 0) then check to
see if the position is a repeat. if so, we can assume that
this line is a draw and return 0. */
if (ply && reps()== 2)
return 0;
/* do some housekeeping every 1024 nodes */
if ((nodes & 1023) == 0)
checkUp();
pv_length[ply] = ply;
/* are we too deep? */
if (ply >= MAX_PLY - 1)
return evaluate(beta);
if (hply >= HIST_STACK - 1)
return evaluate(beta);
/* are we in check? if so, we want to search deeper */
weAreInCheck = inCheck(sideToMove);
if (weAreInCheck && nullMovesMade%2 != 0)
depth++;
if (doNull && !weAreInCheck && (depth >= NULL_R+1))
{
/* switch off Null move if getting towards the endgame */
if ((pieceMat[WHITE] > 500) && (pieceMat[BLACK] > 500))
{
nullMovesMade++;
/* update the rep_history just so things don't get funky: */
fifty++;
sideToMove ^= 1;
otherSide ^= 1;
epTemp = ep;
ep = -1;
/* NULL_R = 2 */
nullScore = -search(-beta, -beta+1, depth-NULL_R-1,
FALSE);
ep = epTemp;
sideToMove ^= 1;
otherSide ^= 1;
fifty--;
nullMovesMade--;
/* check to see if we can get a quick cutoff from our null move: */
if (nullScore >= beta)
return beta;
}
}
generateAllMoves();
if (followPV) /* are we following the PV? */
testMoveInPV(); /* If yes score the move high */
anyLegalMoves = FALSE;
for (i = firstMove[ply]; i < firstMove[ply + 1]; ++i)
{
sort(i);
if (ply == 1)
{
if (gen_dat[i].m.u != currentMove.u)
{
strcpy(tempMoveStr, moveString(gen_dat[i].m.b));
currentMove = gen_dat[i].m;
}
}
if (makeMove(gen_dat[i].m.b) == FALSE)
continue;
/* we have some moves we can make so flag it */
anyLegalMoves = TRUE;
/* Note the swap of alpha beta here & the 3 minus signs */
value = -search(-beta, -alpha, depth - 1, TRUE);
/* output some debug to see each move considered */
if (outputMode & SEARCH_DEBUG_OUTPUT)
moveInfoDebug(FALSE, ply, value, gen_dat[i].m.b, alpha, beta);
takeBack();
if (value > alpha)
{
/* this move is a good move, so increase the history
value so it gets ordered high next time we can
search it*/
history[gen_dat[i].m.b.from][gen_dat[i].m.b.to] += depth;
if (value >= beta)
{
return beta; /* Crucial line !! beta cutoff occurs here !! */
}
alpha = value;
/* update the PV */
if (nullMovesMade == 0)
{
pv[ply][ply] = gen_dat[i].m;
for (j = ply + 1; j < pv_length[ply + 1]; j++)
pv[ply][j] = pv[ply + 1][j];
pv_length[ply] = pv_length[ply + 1];
}
}
}
/* no legal moves? then side to move is in checkmate or stalemated */
if (!anyLegalMoves)
{
/* here if and no legal moves for the side to move, Computer or human */
if (weAreInCheck)
/* if side to move is in check has no moves and is in check that means it
has lost !
Remember the score is always positive for the side to move if it is
winning,
so return big negative number */
return -INFINITY + ply; /* not sure why we add ply here ? */
else
/* here if side to move is in stalemate, this is a draw, which might be good
or
bad depending on what the state of play is for the side to move */
return 0;
}
/* fifty move draw rule */
if (fifty >= 100)
return 0;
return alpha;
}
/****************************************************************************/
/* */
/* Function: think */
/* */
/* Description: This function */
/* */
/* Author: G.Westwood 14/04/2003 */
/* */
/* Inputs: */
/* U32 output */
/* */
/* Outputs: */
/* NONE */
/* */
/* */
/****************************************************************************/
#define EPSILON 50
void think(void)
{
U32 j, k;
S32 x, depth;
double timeDiff, nodesPerSec;
U32 startMeasureTime, stopMeasureTime;
S32 alpha = -INFINITY;
S32 beta = INFINITY;
U32 failedLastTime = FALSE;
/* try the opening book first */
if (enableOpeningBook)
{
pv[0][0].u = bookMove();
if (pv[0][0].u != -1)
return;
}
nullMovesMade = 0;
/* some code that lets us longjmp back here and return
from think() when our time is up */
stopSearch = FALSE;
setjmp(env);
if (stopSearch)
{
/* make sure to take back the entire line we were searching */
while (ply)
takeBack();
return;
}
startTime = get_ms();
stopTime = startTime + maxTime;
startMeasureTime = get_ms();
ply = 0;
nodes = 0;
memset(pv, 0, sizeof(pv)); /* clear down the PV arrray */
memset(history, 0, sizeof(history)); /* clear down the history arrray */
depth = 1;
while (depth <= maxDepth)
{
followPV = TRUE;
x = search(alpha, beta, depth, TRUE);
if (depth > 2)
{
if (x <= alpha)
{
alpha = -INFINITY;
if (failedLastTime)
beta = INFINITY;
else
beta = x + 1;
failedLastTime = TRUE;
continue;
}
else
failedLastTime = FALSE;
if (x >= beta)
{
beta = INFINITY;
if (failedLastTime)
alpha = -INFINITY;
else
alpha = x - 1;
failedLastTime = TRUE;
continue;
}
else
failedLastTime = FALSE;
alpha = x - EPSILON;
beta = x + EPSILON;
}
stopMeasureTime = get_ms();
if (outputMode & SPEED_DEBUG_OUTPUT)
printf("Nodes = %d Alpha Beta return a score of %d for move %s depth = %d
\r\n",
nodes, x, moveString(pv[0][0].b), depth);
/* output some timing debug */
timeDiff = (((double)(stopMeasureTime - startMeasureTime))/1000);
nodesPerSec = (double)(nodes+500) / (timeDiff*1000);
if (outputMode & SPEED_DEBUG_OUTPUT)
printfDebug("Time elapsed = %0.2f Secs for %d nodes Nodes/Sec = %1.0f\r\n",
timeDiff, nodes, nodesPerSec);
if (!(outputMode & XBOARD_OUTPUT) && !(outputMode & SEARCH_DEBUG_OUTPUT))
{
/* print out the principal variation */
if (npsMode)
{
if (depth == 1)
/* show Nodes per sec */
printfDebug("Ply Eval Time kNode/s Principle Variation\r\n");
printfDebug("%2d: %6d %5d %4.0f ", depth, x, (get_ms() -
startTime)/10, nodesPerSec);
}
else
{
if (depth == 1)
/* show Total Nodes*/
printfDebug("Ply Eval Time Nodes Principle Variation\r\n");
printfDebug("%2d: %6d %5d %10u ", depth, x, (get_ms() - startTime) / 10,
nodes);
}
for (k = 0; k < pv_length[0]; k++)
printfDebug("%s ", moveString(pv[0][k].b));
printfDebug("\r\n");
}
else if (outputMode & XBOARD_OUTPUT)
{
printfDebug("%d %d %d %d",
depth, x, (get_ms() - startTime) / 10, nodes);
for (j = 0; j < pv_length[0]; j++)
printfDebug(" %s", moveString(pv[0][j].b));
printfDebug("\r\n");
fflush(stdout);
}
/* if we have got a no moves condition */
if (x > 9000 || x < -9000)
break;
depth++; /* increase search depth */
}
}
This page took 0.22 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.