Code: Select all
/* Do the recursive negascout search (with memory). This works by calling the search
* function with a zero window bound (beta=alpha+1). This causes a quick cutoff so we
* can then do a more accurate search with better defined bounds. See Prof. Alexander
* Reinefeld's www page for a paper detailing the algorithm. */
int Search(Board * B, const int alpha, const int beta, int depth, int ply,
const int inchk, int fifty, int NullDepth, MOVE LastMove)
{
MOVE movelist[MAX_MOVES],
m,
*lastmove,
hashmove = NO_MOVE,
bestmove = NO_MOVE;
int score = -INFINITY,
best = -INFINITY,
evalscore = 0;
int NMoves,
Moveno,
newfifty = fifty + 1,
ep_carry,
p,
pto,
LegalMoves = 0,
gchk;
int newdepth,
nullreduction,
Base_Extensions = 0,
Extensions = 0,
excess = 0;
int EntryType,
EntryScore,
SEEScore;
BOOL DoNull = TRUE,
IsCapTopMove = FALSE;
FullMove Full[100];
Undo U;
BOOL threat = FALSE,
Futile = FALSE,
IsPV = FALSE,
ReduceExtensions = FALSE;
HashElt *Entry;
/* Set up the temporary (changeable) values for alpha and beta at this
* node */
int talpha = alpha,
tbeta = beta;
#ifdef DEBUG_VERIFY
KeyType CheckKey;
#endif
/* Debugging information */
#ifdef DEBUG_VERIFY
CheckKey = B->Key;
GenerateHashKey(B);
if (CheckKey != B->Key) {
fprintf(stderr, "Warning - Key Corrupted in Search()\n");
PrintBoard(*B);
while (1);
}
#endif
/* Increase the Node Count */
Nodecount++;
/* Reset the best move */
BestMoveRet = NO_MOVE;
/* Reset 'the move on this ply is a capture' flag */
IsCap[ply] = FALSE;
/* ------------==== TEST FOR DRAWN POSITIONS ====--------------- */
/* See if this is a repeated/drawn position. Do not test at top ply */
if (ply > 0 && IsDrawn(B, ply, fifty, TRUE)) {
return ((Current_Board.side == B->side) ? (DRAW_SCORE) : -(DRAW_SCORE));
}
/* -----------==== PROBE TRANSPOSITION TABLE ====------------ */
/* See if this position is in the hash table */
Entry = HashProbe(B);
/* ------------==== GET INFORMATION FROM HASH TABLE ====------------- */
/* See what we can learn from the hash table entry (if any exists). */
if (USE_HASH && Entry) {
/* Get the suggested best move from the hash entry (if there is one) */
hashmove = Entry->move;
EntryType = GetHashType(Entry->flags);
EntryScore = (int) Entry->score;
/* Only accept this hash entry if the level to which it was initially
* searched was greater than or equal to the current depth. Don't
* check at ply==0 so that we're sure we can get a return value. */
if (ply > 0 && ((int) Entry->depth >= depth || (EntryType == HASH_EXACT && IsCM(EntryScore) == 1))) {
/* This was an exact entry so return it */
switch (EntryType) {
case (HASH_EXACT):
return EntryScore;
/* This was an upper bound, but still isn't greater than
* alpha, so return a fail-low */
case (HASH_UPPER):
if (EntryScore <= talpha)
return EntryScore;
/* This was an upper bound, but was greater than alpha, so
* adjust beta if necessary */
if (EntryScore < tbeta)
tbeta = EntryScore;
break;
/* This was a lower bound, but was still greater than beta,
* so return a fail-high */
case (HASH_LOWER):
if (EntryScore >= tbeta)
return EntryScore;
/* This was a lower bound, but was not greater than beta, so
* adjust alpha if necessary */
if (EntryScore > talpha)
talpha = EntryScore;
break;
/* Check to see if we should avoid null moves */
case (HASH_NULL):
DoNull = FALSE;
break;
}
}
}
/* -----------==== TRY A NULL MOVE ====------------- */
/* Perform a NULL move if; (1) We're not on the first 2 plies (2) We are
* OK to NULL move at this position (from the hash table) (3) We haven't
* done a NULL move already (4) We're not in check (5) There are enough
* pieces left to avoid high risk of zugzwang (6) We are not rushed (7)
* We're not on a leaf node */
if (USE_NULL && ply > 1 && DoNull && NullDepth == 0 && !inchk && (nullreduction = NullOK(B, depth)) && !bRushed && depth > ONEPLY) {
/* Increase the NULL reduction by one ply to account for the fact
* that we've passed on this move. */
/* Set up temporary flags to store the board position */
ep_carry = B->ep;
B->ep = -1;
/* Do the null move reduced-depth search */
B->side = Opponent(B->side);
if (depth - nullreduction < ONEPLY)
score = -Quiesce(B, -tbeta, -tbeta + 1, ply + 1, 0, 0);
else
score = -Search(B, -tbeta, -tbeta + 1, depth - nullreduction, ply + 1, 0, 0, NullDepth + 1, NO_MOVE);
/* Put things back */
B->side = Opponent(B->side);
/* Verification Search. Here we re-search this node at a shallower
* depth if the score is >= beta. The reason we do this is simple:
* we want to make sure that this really is a strong node, and
* therefore worth chopping. This time, instead of actually making a
* NULL move, we play a proper move. Note that we don't bother doing
* this when close to the frontier nodes (this would take us into the
* qsearch). We only fail high if this second search ALSO fails
* high. */
if (score >= tbeta && depth - nullreduction >= ONEPLY)
score = Search(B, tbeta - 1, tbeta, depth - nullreduction, ply + 1, 0, fifty, NullDepth + 1, LastMove);
/* Replace the En-Passant flag */
B->ep = ep_carry;
/* If this move returned CM then we must be careful because there is
* a CM threat dangerously close! Only do this on highest skill
* level. */
if (IsCM(score) == -1 && Skill == 10)
threat = TRUE;
/* A fail high means that the positional score here is so high that
* even if the opponent is given a 'free move' then he still can't
* improve his position enough to increase the value of alpha. If
* this is the case then clearly the current position is very strong.
* In fact it is so strong that the opponent would never let it occur
* in the first place, so we should cause a cut off. */
if (score >= tbeta) {
HashUpdate(B, score, BestMoveRet, depth + ONEPLY - nullreduction, HASH_LOWER, FALSE, ply);
return score;
}
}
/* ----------==== INTERNAL ITERATIVE DEEPENING ====----------- */
/* If we're not doing a NULL move and we don't have a hash move and we're
* at least 3 ply away from the quiescence search, then try to get a good
* guess for the best move by doing a shallower search from here. */
if (USE_IID && hashmove == NO_MOVE && NullDepth == 0 && depth >= THREEPLY && Skill > 8 && !bRushed) {
score = Search(B, talpha, tbeta, depth - TWOPLY, ply, inchk, 0, 0, LastMove);
/* Re-search properly if the previous search failed low, so that we
* know we're getting a good move, not just the move with the highest
* upper bound (which is essentially random and depends on the search
* order.) */
if (score <= talpha)
score = Search(B, -CMSCORE, talpha + 1, depth - TWOPLY, ply, inchk, 0, 0, LastMove);
/* Get the suggested best move that was returned and use it as a
* hashmove */
hashmove = BestMoveRet;
}
/* ----------==== GENERATE MOVELIST ====------------ */
/* Make some moves */
if (!inchk)
lastmove = GenerateMoves(B, B->side, movelist);
else
lastmove = GenerateCheckEvasions(B, B->side, movelist, inchk);
/* Score the moves in the preliminary movelist. Don't remove illegal
* moves just yet, unless we're in check (needed for single-reply
* extension). If we're searching the root then order moves according to
* root scores instead */
NMoves = FilterMovelist(movelist, lastmove, B, Full, ply, hashmove, inchk);
/* No moves - stalemate */
BestMoveRet = NO_MOVE;
if (NMoves == 0)
return ((Current_Board.side == B->side) ? (DRAW_SCORE) : -(DRAW_SCORE));
/* -----------==== SEARCH EXTENSIONS ====------------ */
/* CM Threat extensions. We extend here if a NULL move search returned a
* checkmate threat. */
if (threat) {
Base_Extensions += CMTHREAT_EXTEND;
ThreatExtensions++;
}
/* Single Reply Extension. If there's only one possible move then
* extend. */
if (NMoves == 1) {
Base_Extensions += ONEREPLY_EXTEND;
OneReplyExtensions++;
}
/* Current Approximate Positional Score (for Razoring) if it might be
* needed */
if (USE_RAZORING && !inchk && !threat && ply > 1) {
if (IsDrawnMaterial(B))
evalscore = (Current_Board.side == WHITE ? DRAW_SCORE : -DRAW_SCORE);
else
evalscore = LazyEval(B) + IsWonGame(B);
if (B->side == BLACK)
evalscore = -evalscore;
}
/* Check to see if we should reduce extensions here as we're getting way
* too deep. Start doing this after we've extended by a total of
* MAX_EXTEND ply, or we've searched to twice the default depth,
* whichever is larger. Put the best move first. */
ReduceExtensions = (ply > (GlobalDepth + max(GlobalDepth, MAX_EXTEND)));
/* -----------==== CYCLE THROUGH MOVES - INNER LOOP ====---------- */
for (Moveno = 0; Moveno < NMoves; Moveno++) {
/* Get the highest scoring move from those left on the list. Put it
* at the top. */
SortFrom(Full, Moveno, NMoves);
m = Full[Moveno].move;
/* Keep track of the top ply move */
if (ply == 0 && (depth == (GlobalDepth * ONEPLY))) {
/* Work out the SEE score for this move */
SEEScore = SEE(B, MFrom(m), MTo(m), IsPromote(m)) * 100;
/* Set up the top two (the hash move and the largest competitor) */
if (Moveno == 0)
TopOrderScore = SEEScore;
else if (SEEScore > NextBestOrderScore || Moveno == 1)
NextBestOrderScore = SEEScore;
/* Set the top ply move that we're working on */
TopPlyMoveno = Moveno;
}
/* Identify the piece that's moving, and the piece on the target
* square */
p = PType(B->pieces[MFrom(m)]);
pto = PType(B->pieces[MTo(m)]);
/* Do the move */
U = DoMove(B, m);
/* Filter out illegal moves which leave us in check. If we're in
* check before the move then this has already been done. */
if (!inchk && InCheck(B, Opponent(B->side))) {
UndoMove(B, m, U);
continue;
}
/* This move is legal, so increase the count */
LegalMoves++;
/* Test to see if this move gives check */
gchk = GivesCheck(B, m);
/* Test for immediate CM cutoff */
if (gchk && InCM(B, gchk)) {
UndoMove(B, m, U);
HashUpdate(B, CMSCORE - ply - 1, m, depth, HASH_EXACT, FALSE, ply);
IncreaseCounts(Full[Moveno], ply, CMSCORE);
BestMoveRet = m;
if (LegalMoves == 1)
BestFirst++;
SortNodes++;
if (Post && ply == 0)
PrintThinking(CMSCORE - ply - 1, B);
return CMSCORE - ply - 1;
}
/* Test to see if this move breaks the 50 move draw chain, else
* increase the count */
if (pto != empty || IsEP(m))
IsCap[ply] = TRUE;
else
IsCap[ply] = FALSE;
if (IsCastle(m) || IsCap[ply] || p == pawn)
newfifty = 0;
else
newfifty = fifty + 1;
/* -------------==== MORE EXTENSIONS ====------------------ */
Extensions = Base_Extensions;
/* Check extension (if we're giving check this move) */
if (gchk && Skill > 2) {
Extensions += CHECK_EXTEND;
CheckExtensions++;
/* Revealed Check Extension (Not 100% accurate, but near enough)
* Test to see if the piece giving check is not the piece moving.
* (This fails if the piece moving also gives check, and is
* tested first.) */
if (gchk != p) {
Extensions += REVCHECK_EXTEND;
RevCheckExtensions++;
}
}
/* Recapture Extension. We do this in the following cases; (1) We
* are not on the first ply (obviously) (2) The last ply was a
* capture move (3) This move captures the piece that captured last
* move (4) The value of this piece equals the value of the target
* piece */
if (ply > 0 && IsCap[ply - 1] && MTo(m) == MTo(LastMove) && PieceValue[pto] == PieceValue[p] && Skill > 4) {
Extensions += RECAP_EXTEND;
RecapExtensions++;
}
/* A Pawn Push Extension is used if we're moving a pawn to within one
* rank of promotion. */
if (p == pawn && (MTo(m) <= h7 || MTo(m) >= a2) && Skill > 7) {
Extensions += PAWNPUSH_EXTEND;
PawnPushExtensions++;
}
/* Fork extension */
if (p == wknight && Count(KnightMoves[MTo(m)] & (B->BlackQueens | B->BlackRooks | Mask[B->BlackKing])) > 1)
Extensions += ONEPLY;
if (p == bknight && Count(KnightMoves[MTo(m)] & (B->WhiteQueens | B->WhiteRooks | Mask[B->WhiteKing])) > 1)
Extensions += ONEPLY;
/* Seemingly bad top ply moves are reduced when there is an obvious
* easy move. Do not do this if we are capturing or giving check, or
* if this is a shallow search. */
if (ply == 0 && bEasyMove && newdepth >= THREEPLY) {
if (Moveno == 0)
IsCapTopMove = IsCap[ply];
if (IsCap[ply] && SEEScore + EASY_MOVE_MARGIN < TopOrderScore && m != Killer1[ply] && m != Killer2[ply])
Extensions -= ONEPLY;
}
/* Reduce Extensions if we're searching too deep already */
if (ReduceExtensions)
Extensions /= 2;
/* Add on the extensions, limiting them to 1.5 plies maximum, plus
* reduce the depth to the next ply. */
newdepth = depth + min(Extensions, ONEANDAHALFPLY) - ONEPLY;
/* ----------------==== PRUNING ====-------------------- */
/* Check to see if this node might be futile. This is used in the
* subsequent algorithm. This is true if; (1) We are not in check,
* nor is this a checking move (2) We are not in danger of losing to
* CM (3) We are not capturing or promoting on this move (4) Alpha is
* not a CM score, either for or against (5) We are not on the first
* four ply, so that the search has had a chance to go bad. */
if (USE_RAZORING && !inchk && !gchk && !threat && !IsCap[ply] &&
!IsPromote(m) && !IsCM(talpha) && ply > 3)
Futile = TRUE;
else
Futile = FALSE;
/* Adaptive razoring. This is similar to futility pruning (see Heinz
* et al in various papers), except that it works at several plies,
* not just frontier and pre-frontier nodes. If the evaluation is
* significantly below alpha, and this move is futile (see above)
* then we reduce the depth to which we wish to search this node. The
* margin we use increases with increasing depth. Clearly, we need
* to be much more careful about high-depth nodes as pruning them
* could have much larger consequences. This algorithm is a bit
* dodgy, but generally seems to work OK. */
if (Futile && LegalMoves > AVOID_RAZ_NUM && newdepth >= ONEPLY) {
excess = talpha - (evalscore + ((newdepth * newdepth * RAZOR_SCALE) / 10) + RAZOR_MARGIN);
if (excess > 0) {
/* If this is well below alpha then prune by a whole ply,
* otherwise just prune by a fraction of a ply. */
if (excess > RAZOR_HARSH)
newdepth -= ONEPLY;
else
newdepth -= ((ONEPLY * excess) / RAZOR_HARSH);
RazorCuts++;
}
}
/* -----------------==== RECURSE TO THE NEXT PLY
* ====---------------- */
/* If at bottom depth then return quiescence score. Basically, we
* find a quiet position before we accept the static evaluation. This
* avoids the so-called 'horizon effect' where bad captures are
* pushed off the end of the search tree causing total mis-evaluation
* of the position. (See notes at top of Quiesce() function below). */
if (newdepth < ONEPLY)
score = -Quiesce(B, -tbeta, -talpha, ply + 1, newfifty, gchk);
/* Recurse to the next ply using negascout search heuristic */
else {
/* If this is the first move then search it properly */
#ifdef USE_PV_SEARCH
if (LegalMoves == 1)
#endif
score = -Search(B, -tbeta, -talpha, newdepth, ply + 1, gchk, newfifty, 0, m);
/* Otherwise this is NOT the first move - use Negascout search */
#ifdef USE_PV_SEARCH
else {
/* First try a zero-width search. This tests if this
* position is going to improve alpha, but does not return an
* exact score. It fails much more quickly in the (hopefully
* more probable) case that the move does NOT improve alpha. */
score = -Search(B, -talpha - 1, -talpha, newdepth, ply + 1, gchk, newfifty, 0, m);
/* Looks like this move will improve alpha */
if (score > talpha && score < tbeta && !AbortFlag)
/* .. therefore search again with sensible bounds */
score = -Search(B, -tbeta, -score, newdepth, ply + 1, gchk, newfifty, 0, m);
}
#endif
}
#ifdef DEBUG_VERIFY
CheckKey = B->Key;
GenerateHashKey(B);
if (CheckKey != B->Key) {
fprintf(stderr, "Warning - Key Corrupted in Search() iteration step, ply=%d, depth=%d\n", ply, depth);
PrintBoard(*B);
while (1);
}
#endif
/* Undo the move */
UndoMove(B, m, U);
/* ---------------==== HAVE WE IMPROVED OUR BEST SCORE?
* ====------------- */
/* Update scores */
if (!AbortFlag && score > best) {
best = score;
bestmove = m;
/* Have we improved alpha? (i.e. this an interesting move) */
if (best > talpha) {
IncreaseCounts(Full[Moveno], ply, score);
/* Fail-high cutoff. This means that this move is so good
* that it will never be played as our opponent will never
* allow it (he/she has better alternatives) so don't bother
* continuing the search. */
if (score >= tbeta) {
/* Update the hash table & return the move score */
BestMoveRet = bestmove;
SortNodes++;
HashUpdate(B, score, bestmove, depth, HASH_LOWER, threat, ply);
if (LegalMoves == 1)
BestFirst++;
return best;
}
/* Print off the PV if we're posting to XBoard and this is
* the top ply and we're not doing the IID loop. */
if (ply == 0 && (depth == (GlobalDepth * ONEPLY))) {
HashUpdate(B, score, bestmove, depth, HASH_EXACT, threat, ply);
if (Post)
PrintThinking(score, B);
}
/* We know we're in the PV Now */
IsPV = TRUE;
/* We know that this score > alpha, so improve (the
* temporary) alpha */
talpha = best;
}
/* Always store the first top ply entries (to make sure that we
* have something that we can return). Don't store every move
* because if we get a fail- low in the window search it might
* well beat the best move so far just by fluke - we might score
* Move1<100 and Move2<200, giving Move2 a better score, but of
* course the reality could be that Move1=99, Move2=0. If we're
* getting only fail-lows in the window search then we need to
* re-search the root position anyway, using the previous best
* move (the one searched first) at the top of the list. See also
* the upper bound hash stores below in the hash table update
* section. */
else if (ply == 0 && LegalMoves == 1 && (depth == (GlobalDepth * ONEPLY))) {
HashUpdate(B, score, bestmove, depth, HASH_UPPER, threat, ply);
if (Post)
PrintThinking(score, B);
}
}
/* Check for time problems and new input periodically */
if (!AbortFlag && ((Nodecount & INPUT_PERIOD) == 0 || ply < 4) && !bRushed) {
if (GlobalDepth > Params.Depth && !AnalyseMode)
AbortFlag = CheckTime(ply, score);
if (!AbortFlag) {
InputFlag = CheckUserInput();
if (InputFlag && InputFlag != INPUT_WORK_DONE)
AbortFlag = TRUE;
}
}
if (AbortFlag)
break;
}
/* Check for stalemate. Note that we've already filtered out CMs at the
* top of this function. */
if (LegalMoves == 0) {
best = ((Current_Board.side == B->side) ? (DRAW_SCORE) : -(DRAW_SCORE));
bestmove = NO_MOVE;
}
/* -------------==== UPDATE THE HASH TABLE ====-------------- */
/* We store the hashtable results as an exact value or an upper bound
* depending on whether we're in the PV or not. If we have found a move
* that increased alpha then this move is in the PV and hence is an exact
* score. Otherwise, all moves in this level are a result of fail-high
* cutoffs from the next ply, and hence all we really have is an upper
* bound on the best score. We know we can't get any better than this,
* but we don't really know how bad the score truly is. All that matters
* is that the best we could possibly get isn't good enough. Don't store
* top ply (ply=0) fail-low moves here because a fail low in the window
* search can cause bad moves to be stored instead of the best move so
* far. This is because we get only bounds, and one lower bound being
* higher than another tells us nothing about the actual scores
* themselves. (We DO score ply=0 moves if this is the first iteration,
* however, to make sure that *something* is stored!). */
if (!AbortFlag) {
if (IsPV)
HashUpdate(B, best, bestmove, depth, HASH_EXACT, threat, ply);
else if (ply > 0 || GlobalDepth == 2)
HashUpdate(B, best, bestmove, depth, HASH_UPPER, threat, ply);
}
/* If we've run out of time then print the thinking as far as we've got.
* Don't bother if we didn't actually finish searching the first move,
* though. Also don't bother if the opponent has just resigned. */
if (AbortFlag && ply == 0 && depth == (GlobalDepth * ONEPLY) && best > -INFINITY && InputFlag != INPUT_RESIGN)
PrintThinking(best, B);
/* Return the best value found */
BestMoveRet = bestmove;
return best;
}
