Subversion Repositories Games.Chess Giants

Rev

Blame | Last modification | View Log | Download | RSS feed

  1. /*
  2.     Protector -- a UCI chess engine
  3.  
  4.     Copyright (C) 2009-2010 Raimund Heid (Raimund_Heid@yahoo.com)
  5.  
  6.     This program is free software: you can redistribute it and/or modify
  7.     it under the terms of the GNU General Public License as published by
  8.     the Free Software Foundation, either version 3 of the License, or
  9.     (at your option) any later version.
  10.  
  11.     This program is distributed in the hope that it will be useful,
  12.     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13.     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14.     GNU General Public License for more details.
  15.  
  16.     You should have received a copy of the GNU General Public License
  17.     along with this program.  If not, see <http://www.gnu.org/licenses/>.
  18.  
  19. */
  20.  
  21. #include <stdio.h>
  22. #include <stdlib.h>
  23. #include <string.h>
  24. #include <assert.h>
  25. #include <time.h>
  26. #include <math.h>
  27. #include "search.h"
  28. #include "matesearch.h"
  29. #include "io.h"
  30. #include "movegeneration.h"
  31. #include "hash.h"
  32. #include "evaluation.h"
  33. #include "book.h"
  34. #include "coordination.h"
  35. #include "xboard.h"
  36.  
  37. #ifdef INCLUDE_TABLEBASE_ACCESS
  38. #include "tablebase.h"
  39. #endif
  40.  
  41. /* #define DEBUG_THREAD_COORDINATION */
  42.  
  43. extern bool resetSharedHashtable;
  44. const int HASH_DEPTH_OFFSET = 3;
  45. const UINT64 GUI_NODE_COUNT_MIN = 250000;
  46.  
  47. #define NUM_FUTILITY_MARGIN_VALUES 13
  48. #define NUM_LOG_VALUES 256
  49. INT32 checkTimeCount = 0;
  50.  
  51. int quietMoveCountLimit[2][32]; /* number of quiet moves to be examined @ specific restDepth */
  52. int quietPvMoveReduction[64][64];       /* [restDepth][moveCount] */
  53. int quietMoveReduction[2][64][64];      /* [variationType][restDepth][moveCount] */
  54. int futilityMargin[NUM_FUTILITY_MARGIN_VALUES + 1];     /* [restDepth] */
  55. int maxPieceValue[16];          /* the maximal value of a piece type */
  56.  
  57. /* Prototypes */
  58. static int searchBest(Variation * variation, int alpha, int beta,
  59.                       const int ply, const int restDepth, const bool pvNode,
  60.                       const bool cutNode, Move * bestMove, Move excludeMove,
  61.                       const bool tryEarlyPrunings); // Pierre-Marie Baty -- missing const in prototype
  62.  
  63. static bool moveIsQuiet(const Move move, const Position * position)
  64. {
  65.    return (bool) (position->piece[getToSquare(move)] == NO_PIECE &&
  66.                   getNewPiece(move) == NO_PIECE &&
  67.                   (getToSquare(move) != position->enPassantSquare ||
  68.                    pieceType(position->piece[getFromSquare(move)]) != PAWN));
  69. }
  70.  
  71. static void checkTerminationConditions(Variation * variation)
  72. {
  73.    if (variation->searchStatus == SEARCH_STATUS_RUNNING)
  74.    {
  75.       if (variation->terminate != FALSE &&
  76.           (variation->iteration > 1 || variation->threadNumber > 0))
  77.       {
  78.          variation->searchStatus = SEARCH_STATUS_TERMINATE;
  79.       }
  80.    }
  81. }
  82.  
  83. bool checkNodeExclusion(int restDepth)
  84. {
  85.    return restDepth >= 6 * DEPTH_RESOLUTION && getNumberOfThreads() > 1;
  86. }
  87.  
  88. static bool hasDangerousPawns(const Position * position, const Color color)
  89. {
  90.    if (color == WHITE)
  91.    {
  92.       return (bool)
  93.          ((position->piecesOfType[WHITE_PAWN] & squaresOfRank[RANK_7]) !=
  94.           EMPTY_BITBOARD);
  95.    }
  96.    else
  97.    {
  98.       return (bool)
  99.          ((position->piecesOfType[BLACK_PAWN] & squaresOfRank[RANK_2]) !=
  100.           EMPTY_BITBOARD);
  101.    }
  102. }
  103.  
  104. int getEvalValue(Variation * variation)
  105. {
  106.    EvaluationBase base;
  107.  
  108.    base.ownColor = variation->ownColor;
  109.    return
  110.       getValue(&variation->singlePosition, &base, variation->pawnHashtable,
  111.                variation->kingsafetyHashtable);
  112. }
  113.  
  114. static int getStaticValue(Variation * variation, const int ply)
  115. {
  116.    PlyInfo *pi = &variation->plyInfo[ply];
  117.  
  118.    if (pi->staticValueAvailable == FALSE)
  119.    {
  120.       EvaluationBase base;
  121.  
  122.       base.ownColor = variation->ownColor;
  123.       pi->staticValue = pi->refinedStaticValue =
  124.          getValue(&variation->singlePosition, &base, variation->pawnHashtable,
  125.                   variation->kingsafetyHashtable);
  126.       pi->staticValueAvailable = TRUE;
  127.    }
  128.    else
  129.    {
  130.       assert(pi->staticValue == getEvalValue(variation));
  131.    }
  132.  
  133.    return pi->staticValue;
  134. }
  135.  
  136. static int getRefinedStaticValue(Variation * variation, const int ply)
  137. {
  138.    PlyInfo *pi = &variation->plyInfo[ply];
  139.  
  140.    if (pi->staticValueAvailable == FALSE)
  141.    {
  142.       EvaluationBase base;
  143.  
  144.       base.ownColor = variation->ownColor;
  145.       pi->staticValue = pi->refinedStaticValue =
  146.          getValue(&variation->singlePosition, &base, variation->pawnHashtable,
  147.                   variation->kingsafetyHashtable);
  148.       pi->staticValueAvailable = TRUE;
  149.    }
  150.    else
  151.    {
  152.       assert(pi->staticValue == getEvalValue(variation));
  153.    }
  154.  
  155.    return pi->refinedStaticValue;
  156. }
  157.  
  158. static void updateGains(Variation * variation, const int ply)
  159. {
  160.    if (variation->plyInfo[ply].gainsUpdated == FALSE &&
  161.        variation->plyInfo[ply - 1].quietMove != FALSE)
  162.    {
  163.       const int moveIndex = variation->plyInfo[ply - 1].indexCurrentMove;
  164.       INT16 *storedGain = &variation->positionalGain[moveIndex];
  165.       const INT16 currentDiff = (INT16)
  166.          (getStaticValue(variation, ply) +
  167.           variation->plyInfo[ply - 1].staticValue);
  168.  
  169.       *storedGain =
  170.          (currentDiff >= (*storedGain) ? currentDiff : (*storedGain) - 1);
  171.    }
  172.  
  173.    variation->plyInfo[ply].gainsUpdated = TRUE;
  174. }
  175.  
  176. static void updateCounterMoves(Variation * variation, const int ply,
  177.                                Move counterMove)
  178. {
  179.    if (variation->plyInfo[ply - 1].currentMove != NULLMOVE)
  180.    {
  181.       const int moveIndex = variation->plyInfo[ply - 1].indexCurrentMove;
  182.  
  183.       if (counterMove != variation->counterMove1[moveIndex])
  184.       {
  185.          variation->counterMove2[moveIndex] =
  186.             variation->counterMove1[moveIndex];
  187.          variation->counterMove1[moveIndex] = counterMove;
  188.       }
  189.    }
  190. }
  191.  
  192. static void updateFollowupMoves(Variation * variation, const int ply,
  193.                                 Move followupMove)
  194. {
  195.    if (variation->plyInfo[ply - 2].currentMove != NULLMOVE)
  196.    {
  197.       const int moveIndex = variation->plyInfo[ply - 2].indexCurrentMove;
  198.  
  199.       if (followupMove != variation->followupMove1[moveIndex])
  200.       {
  201.          variation->followupMove2[moveIndex] =
  202.             variation->followupMove1[moveIndex];
  203.          variation->followupMove1[moveIndex] = followupMove;
  204.       }
  205.    }
  206. }
  207.  
  208. static bool positionIsWellKnown(Variation * variation,
  209.                                 Position * position,
  210.                                 const UINT64 hashKey,
  211.                                 Hashentry ** bestTableHit,
  212.                                 const int ply, const int alpha,
  213.                                 const int beta, const int restDepth,
  214.                                 const bool pvNode,
  215.                                 const bool updateGainValues,
  216.                                 Move * hashmove,
  217.                                 const Move excludeMove, int *value)
  218. {
  219.    Hashentry *tableHit = getHashentry(getSharedHashtable(),
  220.                                       hashKey);
  221.  
  222.    if (tableHit != NULL)
  223.    {                            /* 45% */
  224.       const int importance = getHashentryImportance(tableHit);
  225.       const int flag = getHashentryFlag(tableHit);
  226.       const int hashEntryValue =
  227.          calcEffectiveValue(getHashentryValue(tableHit), ply);
  228.       PlyInfo *pi = &variation->plyInfo[ply];
  229.  
  230.       *bestTableHit = tableHit;
  231.       *value = hashEntryValue;
  232.  
  233.       /*
  234.          if (getHashentryStaticValue(tableHit) != getStaticValue(variation, ply))
  235.          {
  236.          logDebug("hv=%d sv=%d ev=%d\n", getHashentryStaticValue(tableHit),
  237.          getStaticValue(variation, ply), getEvalValue(variation));
  238.          dumpVariation(variation);
  239.          }
  240.        */
  241.  
  242.       assert(getHashentryStaticValue(tableHit) ==
  243.              getStaticValue(variation, ply));
  244.  
  245.       if (pi->staticValueAvailable == FALSE)
  246.       {
  247.          pi->staticValue = pi->refinedStaticValue =
  248.             getHashentryStaticValue(tableHit);
  249.          pi->staticValueAvailable = TRUE;
  250.  
  251.          if (updateGainValues)
  252.          {
  253.             updateGains(variation, ply);
  254.          }
  255.       }
  256.  
  257.       if (pvNode == FALSE && excludeMove != NULLMOVE &&
  258.           restDepth <= importance && flag != HASHVALUE_EVAL)
  259.       {                         /* 99% */
  260.          assert(flag == HASHVALUE_UPPER_LIMIT ||
  261.                 flag == HASHVALUE_EXACT || flag == HASHVALUE_LOWER_LIMIT);
  262.          assert(hashEntryValue >= VALUE_MATED &&
  263.                 hashEntryValue < -VALUE_MATED);
  264.  
  265.          switch (flag)
  266.          {
  267.          case HASHVALUE_UPPER_LIMIT:
  268.             if (hashEntryValue <= alpha)
  269.             {
  270.                *value = (hashEntryValue <= VALUE_MATED ?
  271.                          alpha : hashEntryValue);
  272.  
  273.                return TRUE;
  274.             }
  275.  
  276.             if (restDepth >= HASH_DEPTH_OFFSET &&
  277.                 hashEntryValue < getStaticValue(variation, ply))
  278.             {
  279.                variation->plyInfo[ply].refinedStaticValue = hashEntryValue;
  280.             }
  281.             break;
  282.  
  283.          case HASHVALUE_EXACT:
  284.             *value = hashEntryValue;
  285.  
  286.             return TRUE;
  287.  
  288.          case HASHVALUE_LOWER_LIMIT:
  289.             if (hashEntryValue >= beta)
  290.             {
  291.                *value = (hashEntryValue >= -VALUE_MATED ?
  292.                          beta : hashEntryValue);
  293.  
  294.                return TRUE;
  295.             }
  296.  
  297.             if (restDepth >= HASH_DEPTH_OFFSET &&
  298.                 hashEntryValue > getStaticValue(variation, ply))
  299.             {
  300.                variation->plyInfo[ply].refinedStaticValue = hashEntryValue;
  301.             }
  302.             break;
  303.  
  304.          default:;
  305.          }
  306.       }
  307.    }
  308.  
  309.    if (*bestTableHit != 0)
  310.    {
  311.       *hashmove = (Move) getHashentryMove(*bestTableHit);
  312.  
  313.       if (*hashmove != NO_MOVE)
  314.       {                         /* 81% */
  315.          assert(moveIsPseudoLegal(position, *hashmove));
  316.  
  317.          if (moveIsPseudoLegal(position, *hashmove))
  318.          {
  319.             assert(moveIsLegal(position, *hashmove));
  320.          }
  321.          else
  322.          {
  323.             *hashmove = NO_MOVE;
  324.          }
  325.       }
  326.    }
  327.  
  328.    return FALSE;
  329. }
  330.  
  331. static int searchBestQuiescence(Variation * variation, int alpha, int beta,
  332.                                 const int ply, const int restDepth,
  333.                                 Move * bestMove, const bool pvNode)
  334. {
  335.    const int oldAlpha = alpha;
  336.    UINT8 hashentryFlag;
  337.    UINT8 hashDepth = (restDepth >= 0 ? 2 : 1);
  338.    Position *position = &variation->singlePosition;
  339.    int best = VALUE_MATED, currentValue = VALUE_MATED, historyLimit, i;
  340.    const int VALUE_MATE_HERE = -VALUE_MATED - ply + 1;
  341.    const int VALUE_MATED_HERE = VALUE_MATED + ply;
  342.    Movelist movelist;
  343.    Move currentMove, bestReply, hashmove = NO_MOVE;
  344.    const bool inCheck = variation->plyInfo[ply - 1].currentMoveIsCheck;
  345.    EvaluationBase base;
  346.    Hashentry *bestTableHit = 0;
  347.    int hashValue;
  348.  
  349.    assert(alpha >= VALUE_MATED && alpha <= -VALUE_MATED);
  350.    assert(beta >= VALUE_MATED && beta <= -VALUE_MATED);
  351.    assert(alpha < beta);
  352.    assert(ply > 0 && ply < MAX_DEPTH);
  353.    assert(restDepth < DEPTH_RESOLUTION);
  354.    assert(passiveKingIsSafe(position));
  355.    assert((inCheck != FALSE) == (activeKingIsSafe(position) == FALSE));
  356.  
  357.    *bestMove = NO_MOVE;
  358.    variation->plyInfo[ply].quietMove = FALSE;   /* avoid subsequent gain updates */
  359.    variation->plyInfo[ply].pv.length = 0;
  360.    variation->plyInfo[ply].pv.move[0] = NO_MOVE;
  361.    movelist.positionalGain = &(variation->positionalGain[0]);
  362.  
  363.    variation->nodes++;
  364.    checkTerminationConditions(variation);
  365.  
  366.    if (variation->searchStatus != SEARCH_STATUS_RUNNING &&
  367.        variation->iteration > 1)
  368.    {
  369.       return 0;
  370.    }
  371.  
  372.    /* Check for a draw according to the 50-move-rule */
  373.    /* ---------------------------------------------- */
  374.    if (position->halfMoveClock > 100)
  375.    {
  376.       return variation->drawScore[position->activeColor];
  377.    }
  378.  
  379.    /* Check for a draw by repetition. */
  380.    /* ------------------------------- */
  381.    historyLimit = POSITION_HISTORY_OFFSET + variation->ply -
  382.       position->halfMoveClock;
  383.  
  384.    assert(historyLimit >= 0);
  385.  
  386.    for (i = POSITION_HISTORY_OFFSET + variation->ply - 4;
  387.         i >= historyLimit; i -= 2)
  388.    {
  389.       if (position->hashKey == variation->positionHistory[i])
  390.       {
  391.          return variation->drawScore[position->activeColor];
  392.       }
  393.    }
  394.  
  395.    /* Probe the transposition table */
  396.    /* ----------------------------- */
  397.  
  398.    if (positionIsWellKnown(variation, position, position->hashKey,
  399.                            &bestTableHit, ply, alpha, beta,
  400.                            hashDepth, pvNode, FALSE,
  401.                            &hashmove, NO_MOVE, &hashValue))
  402.    {
  403.       *bestMove = hashmove;
  404.  
  405.       return hashValue;
  406.    }
  407.  
  408.    if (hashmove != NO_MOVE && inCheck == FALSE &&
  409.        moveIsQuiet(hashmove, position))
  410.    {
  411.       hashmove = NO_MOVE;
  412.    }
  413.  
  414.    if (inCheck == FALSE)
  415.    {
  416.       const bool staticValueAvailable =
  417.          variation->plyInfo[ply].staticValueAvailable;
  418.  
  419.       assert(flipTest(position,
  420.                       variation->pawnHashtable,
  421.                       variation->kingsafetyHashtable) != FALSE);
  422.  
  423.       if (staticValueAvailable == FALSE)
  424.       {
  425.          base.ownColor = variation->ownColor;
  426.          best = getValue(position,
  427.                          &base,
  428.                          variation->pawnHashtable,
  429.                          variation->kingsafetyHashtable);
  430.          variation->plyInfo[ply].staticValue =
  431.             variation->plyInfo[ply].refinedStaticValue = best;
  432.          variation->plyInfo[ply].staticValueAvailable = TRUE;
  433.       }
  434.       else
  435.       {
  436.          best = variation->plyInfo[ply].staticValue;
  437.       }
  438.  
  439.       if (bestTableHit != 0)
  440.       {
  441.          const int flag = getHashentryFlag(bestTableHit);
  442.          const int requiredFlag = (hashValue > best ?
  443.                                    HASHVALUE_LOWER_LIMIT :
  444.                                    HASHVALUE_UPPER_LIMIT);
  445.  
  446.          if (flag == requiredFlag)
  447.          {
  448.             best = hashValue;
  449.          }
  450.       }
  451.  
  452.       if (best > alpha)
  453.       {
  454.          alpha = best;
  455.  
  456.          if (best >= beta)
  457.          {
  458.             if (staticValueAvailable == FALSE)
  459.             {
  460.                UINT8 hashentryFlag = HASHVALUE_EVAL;
  461.  
  462.                setHashentry(getSharedHashtable(), position->hashKey,
  463.                             calcHashtableValue(best, ply),
  464.                             0, packedMove(NO_MOVE), hashentryFlag,
  465.                             (INT16) getStaticValue(variation, ply));
  466.             }
  467.  
  468.             return best;
  469.          }
  470.       }
  471.  
  472.       currentValue = best;
  473.    }
  474.  
  475.    if (ply >= MAX_DEPTH)
  476.    {
  477.       assert(flipTest(position,
  478.                       variation->pawnHashtable,
  479.                       variation->kingsafetyHashtable) != FALSE);
  480.  
  481.       return getStaticValue(variation, ply);
  482.    }
  483.  
  484.    if (alpha < VALUE_MATED_HERE && inCheck == FALSE)
  485.    {
  486.       alpha = VALUE_MATED_HERE;
  487.  
  488.       if (alpha >= beta)
  489.       {
  490.          return VALUE_MATED_HERE;
  491.       }
  492.    }
  493.  
  494.    if (beta > VALUE_MATE_HERE)
  495.    {
  496.       beta = VALUE_MATE_HERE;
  497.  
  498.       if (beta <= alpha)
  499.       {
  500.          return VALUE_MATE_HERE;
  501.       }
  502.    }
  503.  
  504.    initQuiescenceMovelist(&movelist, &variation->singlePosition,
  505.                           &variation->plyInfo[ply],
  506.                           &variation->historyValue[0],
  507.                           hashmove, restDepth, inCheck);
  508.    initializePlyInfo(variation);
  509.  
  510.    while ((currentMove = getNextMove(&movelist)) != NO_MOVE)
  511.    {
  512.       int value, newDepth =
  513.          (inCheck ? restDepth : restDepth - DEPTH_RESOLUTION);
  514.       int optValue = currentValue + 43 +
  515.          maxPieceValue[position->piece[getToSquare(currentMove)]];
  516.       const Square toSquare = getToSquare(currentMove);
  517.  
  518.       if (pvNode == FALSE && inCheck == FALSE && optValue < alpha &&
  519.           optValue > VALUE_ALMOST_MATED &&
  520.           movesAreEqual(currentMove, hashmove) == FALSE &&
  521.           getNewPiece(currentMove) != (Piece) QUEEN &&
  522.           numberOfNonPawnPieces(position, position->activeColor) > 1 &&
  523.           (pieceType(position->piece[getFromSquare(currentMove)]) != PAWN ||
  524.            colorRank(position->activeColor, toSquare) != RANK_7))
  525.       {
  526.          const bool enPassant = (bool)
  527.             (toSquare == position->enPassantSquare &&
  528.              pieceType(position->piece[getFromSquare(currentMove)]) == PAWN);
  529.  
  530.          if (getNewPiece(currentMove) != NO_PIECE)
  531.          {
  532.             optValue +=
  533.                maxPieceValue[getNewPiece(currentMove)] - basicValue[PAWN];
  534.          }
  535.  
  536.          if (enPassant)
  537.          {
  538.             optValue += maxPieceValue[PAWN];
  539.          }
  540.  
  541.          if (optValue < alpha && moveIsCheck(currentMove, position) == FALSE)
  542.          {
  543.             best = max(best, optValue);
  544.  
  545.             continue;
  546.          }
  547.       }
  548.  
  549.       assert(moveIsPseudoLegal(position, currentMove));
  550.  
  551.       if (makeMoveFast(variation, currentMove) != 0 ||
  552.           passiveKingIsSafe(&variation->singlePosition) == FALSE)
  553.       {
  554.          unmakeLastMove(variation);
  555.  
  556.          continue;
  557.       }
  558.  
  559.       variation->plyInfo[ply].currentMoveIsCheck =
  560.          activeKingIsSafe(&variation->singlePosition) == FALSE;
  561.  
  562.       assert(position->piece[getToSquare(currentMove)] != NO_PIECE ||
  563.              (getToSquare(currentMove) == position->enPassantSquare &&
  564.               position->piece[getFromSquare(currentMove)] ==
  565.               (PAWN | position->activeColor)) ||
  566.              getNewPiece(currentMove) != NO_PIECE ||
  567.              inCheck || variation->plyInfo[ply].currentMoveIsCheck);
  568.  
  569.       assert(inCheck != FALSE ||
  570.              basicValue[position->piece[getFromSquare(currentMove)]] <=
  571.              basicValue[position->piece[getToSquare(currentMove)]] ||
  572.              seeMove(position, currentMove) >= 0);
  573.  
  574.       value = -searchBestQuiescence(variation, -beta, -alpha, ply + 1,
  575.                                     newDepth, &bestReply, pvNode);
  576.  
  577.       unmakeLastMove(variation);
  578.  
  579.       if (variation->searchStatus != SEARCH_STATUS_RUNNING &&
  580.           variation->iteration > 1)
  581.       {
  582.          return 0;
  583.       }
  584.  
  585.       if (value > best)
  586.       {
  587.          best = value;
  588.  
  589.          if (best > alpha)
  590.          {
  591.             alpha = best;
  592.             *bestMove = currentMove;
  593.  
  594.             if (pvNode)
  595.             {
  596.                appendMoveToPv(&(variation->plyInfo[ply].pv),
  597.                               &(variation->plyInfo[ply - 1].pv), currentMove);
  598.             }
  599.  
  600.             if (best >= beta)
  601.             {
  602.                break;
  603.             }
  604.          }
  605.       }
  606.    }
  607.  
  608.    if (best == VALUE_MATED)
  609.    {
  610.       /* mate */
  611.  
  612.       assert(inCheck != FALSE);
  613.  
  614.       best = VALUE_MATED + ply;
  615.    }
  616.  
  617.    /* Store the value in the transposition table. */
  618.    /* ------------------------------------------- */
  619.    if (best >= beta)
  620.    {
  621.       hashentryFlag = HASHVALUE_LOWER_LIMIT;
  622.    }
  623.    else
  624.    {
  625.       hashentryFlag = (best > oldAlpha && pvNode ?
  626.                        HASHVALUE_EXACT : HASHVALUE_UPPER_LIMIT);
  627.    }
  628.  
  629.    setHashentry(getSharedHashtable(), position->hashKey,
  630.                 calcHashtableValue(best, ply),
  631.                 hashDepth, packedMove(*bestMove), hashentryFlag,
  632.                 (INT16) getStaticValue(variation, ply));
  633.  
  634.    return best;
  635. }
  636.  
  637. static bool moveIsCastling(const Move move, const Position * position)
  638. {
  639.    return (bool) (pieceType(position->piece[getFromSquare(move)]) == KING &&
  640.                   distance(getFromSquare(move), getToSquare(move)) == 2);
  641. }
  642.  
  643. static bool isPassedPawnMove(const Square pawnSquare,
  644.                              const Square targetSquare,
  645.                              const Position * position)
  646. {
  647.    const Piece piece = position->piece[pawnSquare];
  648.  
  649.    if (pieceType(piece) == PAWN)
  650.    {
  651.       return pawnIsPassed(position, targetSquare, pieceColor(piece));
  652.    }
  653.    else
  654.    {
  655.       return FALSE;
  656.    }
  657. }
  658.  
  659. static int getSingleMoveExtensionDepth(const bool pvNode)
  660. {
  661.    return (pvNode ? 6 : 8) * DEPTH_RESOLUTION;
  662. }
  663.  
  664. static int searchBest(Variation * variation, int alpha, int beta,
  665.                       const int ply, const int restDepth, const bool pvNode,
  666.                       const bool cutNode, Move * bestMove, Move excludeMove,
  667.                       const bool tryEarlyPrunings)
  668. {
  669.    Position *position = &variation->singlePosition;
  670.    int best = VALUE_MATED;
  671.    const int VALUE_MATE_HERE = -VALUE_MATED - ply + 1;
  672.    const int VALUE_MATED_HERE = VALUE_MATED + ply;
  673.    const int numPieces =
  674.       numberOfNonPawnPieces(position, position->activeColor);
  675.    Movelist movelist;
  676.    UINT8 hashentryFlag;
  677.    int i, historyLimit, numMovesPlayed = 0;
  678.    Move hashmove = NO_MOVE;
  679.    Hashentry *bestTableHit = 0;
  680.    Move currentMove, bestReply;
  681.    const bool inCheck = variation->plyInfo[ply - 1].currentMoveIsCheck;
  682.    const int rdBasic = restDepth / DEPTH_RESOLUTION;
  683.    bool singularExtensionNode = FALSE;
  684.    int hashEntryValue = 0;
  685.    const UINT64 hashKey = position->hashKey;
  686.    const bool cutsAreAllowed = (bool) (abs(beta) < -(VALUE_ALMOST_MATED));
  687.    int variationType = (ply < 2 ? 1 : 0);
  688.    int quietMoveIndex[MAX_MOVES_PER_POSITION], quietMoveCount = 0;
  689.    int deferCount = 0;
  690.  
  691.    *bestMove = NO_MOVE;
  692.    variation->plyInfo[ply].quietMove = FALSE;   /* avoid subsequent gain updates */
  693.    variation->plyInfo[ply].isHashMove = FALSE;
  694.    variation->plyInfo[ply].pv.length = 0;
  695.    variation->plyInfo[ply].pv.move[0] = NO_MOVE;
  696.    movelist.positionalGain = &(variation->positionalGain[0]);
  697.  
  698.    if (ply + 1 > variation->selDepth)
  699.    {
  700.       variation->selDepth = ply + 1;
  701.    }
  702.  
  703.    assert(alpha >= VALUE_MATED && alpha <= -VALUE_MATED);
  704.    assert(beta >= VALUE_MATED && beta <= -VALUE_MATED);
  705.    assert(alpha < beta);
  706.    assert(ply > 0 && ply < MAX_DEPTH);
  707.    assert(passiveKingIsSafe(position));
  708.    assert((inCheck != FALSE) == (activeKingIsSafe(position) == FALSE));
  709.  
  710.    /* Check for a draw according to the 50-move-rule */
  711.    /* ---------------------------------------------- */
  712.    if (position->halfMoveClock > 100)
  713.    {
  714.       return variation->drawScore[position->activeColor];
  715.    }
  716.  
  717.    /* Check for a draw by repetition. */
  718.    /* ------------------------------- */
  719.    historyLimit = POSITION_HISTORY_OFFSET + variation->ply -
  720.       position->halfMoveClock;
  721.  
  722.    assert(historyLimit >= 0);
  723.  
  724.    for (i = POSITION_HISTORY_OFFSET + variation->ply - 4;
  725.         i >= historyLimit; i -= 2)
  726.    {
  727.       if (position->hashKey == variation->positionHistory[i])
  728.       {
  729.          return variation->drawScore[position->activeColor];
  730.       }
  731.    }
  732.  
  733.    if (restDepth < DEPTH_RESOLUTION)
  734.    {                            /* 63% */
  735.       int qsValue;
  736.  
  737.       qsValue =
  738.          searchBestQuiescence(variation, alpha, beta, ply, 0, bestMove,
  739.                               pvNode);
  740.  
  741.       if (inCheck == FALSE &&
  742.           variation->plyInfo[ply].staticValueAvailable != FALSE)
  743.       {
  744.          updateGains(variation, ply);
  745.       }
  746.  
  747.       return qsValue;
  748.    }
  749.  
  750.    variation->nodes++;
  751.    checkTerminationConditions(variation);
  752.  
  753.    if (variation->searchStatus != SEARCH_STATUS_RUNNING &&
  754.        variation->iteration > 1)
  755.    {
  756.       return 0;
  757.    }
  758.  
  759. #ifdef INCLUDE_TABLEBASE_ACCESS
  760.    /* Probe the tablebases in case of reduced material */
  761.    /* ------------------------------------------------ */
  762.    if (ply >= 2 && (pvNode || restDepth >= 10 * DEPTH_RESOLUTION) &&
  763.        position->numberOfPieces[WHITE] +
  764.        position->numberOfPieces[BLACK] <= 6 &&
  765.        excludeMove == NO_MOVE && tbAvailable != FALSE)
  766.    {
  767.       int tbValue;
  768.  
  769.       tbValue = probeTablebase(position);
  770.  
  771.       if (tbValue != TABLEBASE_ERROR)
  772.       {
  773.          variation->tbHits++;
  774.  
  775.          if (tbValue == 0)
  776.          {
  777.             return variation->drawScore[position->activeColor];
  778.          }
  779.  
  780.          return (tbValue > 0 ? tbValue - ply : tbValue + ply);
  781.       }
  782.    }
  783. #endif
  784.  
  785.    /* Probe the transposition table */
  786.    /* ----------------------------- */
  787.    if (excludeMove == NO_MOVE)
  788.    {
  789.       int hashValue;
  790.  
  791.       if (positionIsWellKnown(variation, position, hashKey,
  792.                               &bestTableHit, ply, alpha, beta,
  793.                               restDepth + HASH_DEPTH_OFFSET, pvNode,
  794.                               inCheck == FALSE, &hashmove, excludeMove,
  795.                               &hashValue))
  796.       {
  797.          *bestMove = hashmove;
  798.  
  799.          if (hashValue >= beta && *bestMove != NO_MOVE &&
  800.              moveIsQuiet(*bestMove, position))
  801.          {
  802.             Move killerMove = *bestMove;
  803.             const Piece movingPiece =
  804.                position->piece[getFromSquare(killerMove)];
  805.  
  806.             setMoveValue(&killerMove, movingPiece);
  807.             registerKillerMove(&variation->plyInfo[ply], killerMove);
  808.          }
  809.  
  810.          return hashValue;
  811.       }
  812.    }
  813.  
  814.    if (inCheck == FALSE)
  815.    {
  816.       updateGains(variation, ply);
  817.    }
  818.  
  819.    if (ply >= 2)
  820.    {
  821.       if (variation->plyInfo[ply].staticValue >=
  822.           variation->plyInfo[ply - 2].staticValue ||
  823.           variation->plyInfo[ply].staticValueAvailable == FALSE ||
  824.           variation->plyInfo[ply - 2].staticValueAvailable == FALSE)
  825.       {
  826.          variationType = 1;
  827.       }
  828.    }
  829.  
  830.    if (ply >= MAX_DEPTH)
  831.    {
  832.       return getStaticValue(variation, ply);
  833.    }
  834.  
  835.    if (alpha < VALUE_MATED_HERE && inCheck == FALSE)
  836.    {
  837.       alpha = VALUE_MATED_HERE;
  838.  
  839.       if (alpha >= beta)
  840.       {
  841.          return VALUE_MATED_HERE;
  842.       }
  843.    }
  844.  
  845.    if (beta > VALUE_MATE_HERE)
  846.    {
  847.       beta = VALUE_MATE_HERE;
  848.  
  849.       if (beta <= alpha)
  850.       {
  851.          return VALUE_MATE_HERE;
  852.       }
  853.    }
  854.  
  855.    initializePlyInfo(variation);
  856.  
  857.    if (tryEarlyPrunings == FALSE)
  858.    {
  859.       goto checkAvailableMoves;
  860.    }
  861.  
  862.    /* Razoring */
  863.    if (pvNode == FALSE && restDepth < 4 * DEPTH_RESOLUTION &&
  864.        inCheck == FALSE && hashmove == NO_MOVE && cutsAreAllowed &&
  865.        hasDangerousPawns(position, position->activeColor) == FALSE)
  866.    {
  867.       const int limit = alpha - (204 + 22 * restDepth);
  868.  
  869.       if (getRefinedStaticValue(variation, ply) < limit)
  870.       {
  871.          const int qsValue =
  872.             searchBestQuiescence(variation, limit - 1, limit, ply, 0,
  873.                                  bestMove, pvNode);
  874.  
  875.          if (qsValue < limit)
  876.          {
  877.             return qsValue;
  878.          }
  879.       }
  880.    }
  881.  
  882.    /* Static nullmove pruning */
  883.    if (pvNode == FALSE && restDepth < 4 * DEPTH_RESOLUTION &&
  884.        inCheck == FALSE && cutsAreAllowed && excludeMove == NO_MOVE &&
  885.        numPieces >= 2 &&
  886.        !hasDangerousPawns(position, opponent(position->activeColor)))
  887.    {
  888.       const int referenceValue =
  889.          getRefinedStaticValue(variation, ply) - (40 + 41 * restDepth);
  890.  
  891.       if (referenceValue >= beta)
  892.       {
  893.          return referenceValue;
  894.       }
  895.    }
  896.  
  897.    /* Nullmove pruning with verification */
  898.    if (restDepth >= 2 * DEPTH_RESOLUTION && inCheck == FALSE &&
  899.        pvNode == FALSE && cutsAreAllowed && excludeMove == NO_MOVE &&
  900.        numPieces >= 2 && getRefinedStaticValue(variation, ply) >= beta)
  901.    {                            /* 16-32% */
  902.       const int diff = getRefinedStaticValue(variation, ply) - beta;
  903.       const int additionalReduction = min(diff / 110, 3) * DEPTH_RESOLUTION;
  904.       const int newDepth =
  905.          restDepth - 3 * DEPTH_RESOLUTION - restDepth / 4 -
  906.          additionalReduction;
  907.       const int verificationDepth =
  908.          (numPieces >= 3 ? 12 : 6) * DEPTH_RESOLUTION;
  909.       int nullValue;
  910.  
  911.       assert(flipTest(position,
  912.                       variation->pawnHashtable,
  913.                       variation->kingsafetyHashtable) != FALSE);
  914.  
  915.       makeMoveFast(variation, NULLMOVE);
  916.       variation->plyInfo[ply].currentMoveIsCheck = FALSE;
  917.       nullValue = -searchBest(variation, -beta, -beta + 1, ply + 1,
  918.                               newDepth, pvNode, !cutNode, &bestReply,
  919.                               NO_MOVE, FALSE);
  920.       unmakeLastMove(variation);
  921.  
  922.       if (nullValue >= VALUE_MATE_HERE)
  923.       {
  924.          nullValue = beta;
  925.       }
  926.  
  927.       if (nullValue >= beta && newDepth >= DEPTH_RESOLUTION &&
  928.           restDepth >= verificationDepth)
  929.       {                         /* 2% */
  930.          const int noNullValue = searchBest(variation, alpha, beta, ply,
  931.                                             newDepth,
  932.                                             FALSE, FALSE, &bestReply,
  933.                                             NULLMOVE, FALSE);
  934.  
  935.          if (noNullValue >= beta)
  936.          {                      /* 99% */
  937.             best = nullValue;
  938.  
  939.             goto storeResult;
  940.          }
  941.       }
  942.       else if (nullValue >= beta)
  943.       {                         /* 70% */
  944.          if (numPieces >= 3)
  945.          {
  946.             best = nullValue;
  947.  
  948.             goto storeResult;
  949.          }
  950.          else
  951.          {
  952.             return nullValue;
  953.          }
  954.       }
  955.    }
  956.  
  957.    /* Try to find a quick refutation of the opponent's previous move */
  958.    if (pvNode == FALSE && cutsAreAllowed &&
  959.        restDepth >= 5 * DEPTH_RESOLUTION && excludeMove == NO_MOVE &&
  960.        inCheck == FALSE)
  961.    {
  962.       const int limit = beta + 192;
  963.       const int staticValue = getRefinedStaticValue(variation, ply);
  964.       const Move qrHashmove = (hashmove != NO_MOVE &&
  965.                                position->piece[getToSquare(hashmove)] !=
  966.                                NO_PIECE ? hashmove : NO_MOVE);
  967.  
  968.       initCaptureMovelist(&movelist, &variation->singlePosition,
  969.                           &variation->plyInfo[ply],
  970.                           &variation->historyValue[0], qrHashmove, inCheck);
  971.  
  972.       while ((currentMove = getNextMove(&movelist)) != NO_MOVE)
  973.       {
  974.          const Square toSquare = getToSquare(currentMove);
  975.          const Piece capturedPiece = position->piece[toSquare];
  976.          int moveValue;
  977.  
  978.          if (staticValue + maxPieceValue[capturedPiece] < limit - 38)
  979.          {
  980.             continue;
  981.          }
  982.  
  983.          /* Execute the current move and check if it is legal. */
  984.          /* -------------------------------------------------- */
  985.          if (makeMoveFast(variation, currentMove) != 0 ||
  986.              passiveKingIsSafe(&variation->singlePosition) == FALSE)
  987.          {
  988.             unmakeLastMove(variation);
  989.  
  990.             continue;
  991.          }
  992.  
  993.          variation->plyInfo[ply].currentMoveIsCheck =
  994.             activeKingIsSafe(&variation->singlePosition) == FALSE;
  995.          variation->plyInfo[ply].indexCurrentMove =
  996.             historyIndex(currentMove, position);
  997.          variation->plyInfo[ply].quietMove = FALSE;
  998.          variation->plyInfo[ply].isHashMove = FALSE;
  999.  
  1000.          moveValue = -searchBest(variation, -limit, -limit + 1, ply + 1,
  1001.                                  restDepth - 4 * DEPTH_RESOLUTION, FALSE,
  1002.                                  !cutNode, &bestReply, NO_MOVE, TRUE);
  1003.  
  1004.          unmakeLastMove(variation);
  1005.  
  1006.          if (moveValue >= limit)
  1007.          {
  1008.             best = moveValue;
  1009.             *bestMove = currentMove;
  1010.  
  1011.             goto storeResult;
  1012.          }
  1013.       }
  1014.    }
  1015.  
  1016.  checkAvailableMoves:
  1017.  
  1018.    /* Internal iterative deepening. */
  1019.    /* ----------------------------- */
  1020.    if (hashmove == NO_MOVE &&
  1021.        restDepth >= (pvNode ? 3 : 7) * DEPTH_RESOLUTION &&
  1022.        (pvNode || (inCheck == FALSE &&
  1023.                    getRefinedStaticValue(variation, ply) >= beta - 100)))
  1024.    {
  1025.       const Move excludeHere =
  1026.          (excludeMove != NO_MOVE ? excludeMove : NULLMOVE);
  1027.       const int searchDepth =
  1028.          (pvNode ? restDepth - 2 * DEPTH_RESOLUTION : restDepth / 2);
  1029.  
  1030.       searchBest(variation, alpha, beta, ply, searchDepth, pvNode,
  1031.                  TRUE, &bestReply, excludeHere, FALSE);
  1032.  
  1033.       if (moveIsPseudoLegal(position, bestReply))
  1034.       {
  1035.          hashmove = bestReply;
  1036.       }
  1037.  
  1038.       if (hashmove != NO_MOVE && excludeMove == NO_MOVE &&
  1039.           restDepth >= getSingleMoveExtensionDepth(pvNode))
  1040.       {
  1041.          Hashentry *tableHit = getHashentry(getSharedHashtable(),
  1042.                                             variation->singlePosition.
  1043.                                             hashKey);
  1044.  
  1045.          if (tableHit != 0)
  1046.          {
  1047.             bestTableHit = tableHit;
  1048.          }
  1049.       }
  1050.    }
  1051.  
  1052.    /* Check if the conditions for a singular extension are met */
  1053.    if (bestTableHit != 0 && excludeMove == NO_MOVE && hashmove != NO_MOVE)
  1054.    {
  1055.       const int singleMoveExtensionDepth =
  1056.          getSingleMoveExtensionDepth(pvNode);
  1057.       /* const int singleMoveExtensionDepth = 8 * DEPTH_RESOLUTION; */
  1058.       const int importance =
  1059.          getHashentryImportance(bestTableHit) - HASH_DEPTH_OFFSET;
  1060.       const int flag = getHashentryFlag(bestTableHit);
  1061.  
  1062.       if (restDepth >= singleMoveExtensionDepth &&
  1063.           importance >= restDepth - 3 * DEPTH_RESOLUTION &&
  1064.           flag != HASHVALUE_UPPER_LIMIT)
  1065.       {
  1066.          singularExtensionNode = TRUE;
  1067.          hashEntryValue =
  1068.             calcEffectiveValue(getHashentryValue(bestTableHit), ply);
  1069.       }
  1070.    }
  1071.  
  1072.    if (ply >= 1)
  1073.    {
  1074.       const int moveIndex = variation->plyInfo[ply - 1].indexCurrentMove;
  1075.  
  1076.       variation->plyInfo[ply].killerMove3 =
  1077.          variation->counterMove1[moveIndex];
  1078.       variation->plyInfo[ply].killerMove4 =
  1079.          variation->counterMove2[moveIndex];
  1080.    }
  1081.    else
  1082.    {
  1083.       variation->plyInfo[ply].killerMove3 = NO_MOVE;
  1084.       variation->plyInfo[ply].killerMove4 = NO_MOVE;
  1085.    }
  1086.  
  1087.    if (ply >= 2)
  1088.    {
  1089.       const int moveIndex = variation->plyInfo[ply - 2].indexCurrentMove;
  1090.  
  1091.       variation->plyInfo[ply].killerMove5 =
  1092.          variation->followupMove1[moveIndex];
  1093.       variation->plyInfo[ply].killerMove6 =
  1094.          variation->followupMove2[moveIndex];
  1095.    }
  1096.    else
  1097.    {
  1098.       variation->plyInfo[ply].killerMove5 = NO_MOVE;
  1099.       variation->plyInfo[ply].killerMove6 = NO_MOVE;
  1100.    }
  1101.  
  1102.    initStandardMovelist(&movelist, &variation->singlePosition,
  1103.                         &variation->plyInfo[ply],
  1104.                         &variation->historyValue[0], hashmove, inCheck);
  1105.  
  1106.    /* Ensure that a static value for this ply is available. */
  1107.    getStaticValue(variation, ply);
  1108.  
  1109.    /* Loop through all moves in this node. */
  1110.    /* ------------------------------------ */
  1111.    while ((currentMove = getNextMove(&movelist)) != NO_MOVE)
  1112.    {
  1113.       const int stage = moveGenerationStage[movelist.currentStage];
  1114.       int value = 0, newDepth;
  1115.       int extension = 0;
  1116.       const int moveIndex = min(63, numMovesPlayed);
  1117.       const int depthIndex = min(63, rdBasic);
  1118.       const int gain =
  1119.          variation->positionalGain[historyIndex(currentMove, position)];
  1120.       const int reduction =
  1121.          (pvNode ? quietPvMoveReduction[depthIndex][moveIndex] :
  1122.           quietMoveReduction[variationType][depthIndex][moveIndex] +
  1123.           (cutNode /* || gain < 0 */ ? DEPTH_RESOLUTION : 0));
  1124.       bool check;
  1125.       const bool quietMove = moveIsQuiet(currentMove, position);
  1126.       const Square toSquare = getToSquare(currentMove);
  1127.       const Piece capturedPiece = position->piece[toSquare];
  1128.       bool reduce = FALSE, nodeWasBlocked = FALSE;
  1129.  
  1130.       if (variation->searchStatus != SEARCH_STATUS_RUNNING &&
  1131.           variation->iteration > 1)
  1132.       {
  1133.          return 0;
  1134.       }
  1135.  
  1136.       if (excludeMove != NO_MOVE && movesAreEqual(currentMove, excludeMove))
  1137.       {
  1138.          assert(excludeMove != NULLMOVE);
  1139.  
  1140.          continue;              /* exclude excludeMove */
  1141.       }
  1142.  
  1143.       variation->plyInfo[ply].indexCurrentMove =
  1144.          historyIndex(currentMove, position);
  1145.       variation->plyInfo[ply].quietMove = quietMove;
  1146.       variation->plyInfo[ply].isHashMove =
  1147.          movesAreEqual(currentMove, hashmove);
  1148.  
  1149.       assert(moveIsPseudoLegal(position, currentMove));
  1150.       assert(hashmove == NO_MOVE || numMovesPlayed > 0 ||
  1151.              movesAreEqual(currentMove, hashmove));
  1152.  
  1153.       /* Optimistic futility cuts */
  1154.       if (pvNode == FALSE && inCheck == FALSE && quietMove != FALSE &&
  1155.           !isPassedPawnMove(getFromSquare(currentMove), toSquare, position) &&
  1156.           !moveIsCastling(currentMove, position) &&
  1157.           best > VALUE_ALMOST_MATED && cutsAreAllowed && restDepth < 32)
  1158.       {
  1159.          bool moveIsRelevant = FALSE;
  1160.          const int predictedDepth = restDepth - reduction;
  1161.  
  1162.          if (numMovesPlayed >= quietMoveCountLimit[variationType][restDepth])
  1163.          {
  1164.             if (simpleMoveIsCheck(position, currentMove))
  1165.             {
  1166.                moveIsRelevant = TRUE;
  1167.             }
  1168.             else
  1169.             {
  1170.                continue;
  1171.             }
  1172.          }
  1173.  
  1174.          if (moveIsRelevant == FALSE &&
  1175.              predictedDepth <= NUM_FUTILITY_MARGIN_VALUES)
  1176.          {
  1177.             const int futLimit =
  1178.                getRefinedStaticValue(variation, ply) + gain +
  1179.                futilityMargin[predictedDepth];
  1180.  
  1181.             if (futLimit < beta)
  1182.             {
  1183.                if (simpleMoveIsCheck(position, currentMove))
  1184.                {
  1185.                   moveIsRelevant = TRUE;
  1186.                }
  1187.                else
  1188.                {
  1189.                   if (futLimit > best)
  1190.                   {
  1191.                      best = futLimit;
  1192.                   }
  1193.  
  1194.                   continue;
  1195.                }
  1196.             }
  1197.          }
  1198.  
  1199.          if (moveIsRelevant == FALSE &&
  1200.              predictedDepth < 4 * DEPTH_RESOLUTION &&
  1201.              seeMove(position, currentMove) < 0 &&
  1202.              simpleMoveIsCheck(position, currentMove) == FALSE)
  1203.          {
  1204.             continue;
  1205.          }
  1206.       }
  1207.  
  1208.       /* Execute the current move and check if it is legal. */
  1209.       /* -------------------------------------------------- */
  1210.       if (makeMoveFast(variation, currentMove) != 0 ||
  1211.           passiveKingIsSafe(&variation->singlePosition) == FALSE)
  1212.       {
  1213.          unmakeLastMove(variation);
  1214.  
  1215.          continue;
  1216.       }
  1217.  
  1218.       if (numMovesPlayed > 0 && inCheck == FALSE &&
  1219.           stage == MGS_REST && deferCount < 10 &&
  1220.           checkNodeExclusion(restDepth))
  1221.       {
  1222.          if (nodeIsInUse(position->hashKey, restDepth))
  1223.          {
  1224.             deferMove(&movelist, currentMove);
  1225.             deferCount++;
  1226.             unmakeLastMove(variation);
  1227.             continue;
  1228.          }
  1229.          else
  1230.          {
  1231.             nodeWasBlocked = setNodeUsage(position->hashKey, restDepth);
  1232.          }
  1233.       }
  1234.  
  1235.       /* Check the conditions for search extensions and finally */
  1236.       /* calculate the rest depth for the next ply.             */
  1237.       /* ------------------------------------------------------ */
  1238.       variation->plyInfo[ply].currentMoveIsCheck = check =
  1239.          activeKingIsSafe(&variation->singlePosition) == FALSE;
  1240.  
  1241.       if (check)
  1242.       {
  1243.          unmakeLastMove(variation);
  1244.  
  1245.          if (seeMove(position, currentMove) >= 0)
  1246.          {
  1247.             extension = DEPTH_RESOLUTION;
  1248.          }
  1249.  
  1250.          makeMoveFast(variation, currentMove);
  1251.       }
  1252.  
  1253.       if (pvNode)
  1254.       {
  1255.          if (pieceType(position->piece[toSquare]) == PAWN &&
  1256.              pawnIsPassed(position, toSquare,
  1257.                           opponent(position->activeColor)))
  1258.          {
  1259.             extension = DEPTH_RESOLUTION;
  1260.          }
  1261.          else if (capturedPiece != NO_PIECE &&
  1262.                   pieceType(capturedPiece) != PAWN &&
  1263.                   numberOfNonPawnPieces(position, WHITE) ==
  1264.                   numberOfNonPawnPieces(position, BLACK))
  1265.          {
  1266.             extension = DEPTH_RESOLUTION;
  1267.          }
  1268.       }
  1269.  
  1270.       if (singularExtensionNode != FALSE &&
  1271.           extension < DEPTH_RESOLUTION &&
  1272.           movesAreEqual(currentMove, hashmove))
  1273.       {
  1274.          const int limitValue = hashEntryValue - (266 * restDepth) / 256;
  1275.  
  1276.          assert(excludeMove == NO_MOVE);
  1277.  
  1278.          if (limitValue > VALUE_ALMOST_MATED &&
  1279.              limitValue < -VALUE_ALMOST_MATED)
  1280.          {
  1281.             int excludeValue;
  1282.             PlyInfo pi = variation->plyInfo[ply];
  1283.  
  1284.             unmakeLastMove(variation);
  1285.             excludeValue =
  1286.                searchBest(variation, limitValue - 1, limitValue, ply,
  1287.                           restDepth / 2, FALSE, cutNode, &bestReply,
  1288.                           hashmove, FALSE);
  1289.             makeMoveFast(variation, currentMove);
  1290.             variation->plyInfo[ply] = pi;
  1291.  
  1292.             if (excludeValue < limitValue)
  1293.             {
  1294.                extension = DEPTH_RESOLUTION;
  1295.             }
  1296.          }
  1297.       }
  1298.  
  1299.       newDepth = restDepth - DEPTH_RESOLUTION + extension;
  1300.  
  1301.       /* History pruning */
  1302.       /* --------------- */
  1303.       if (inCheck == FALSE && extension == 0 &&
  1304.           restDepth >= 3 * DEPTH_RESOLUTION && quietMove != FALSE &&
  1305.           stage != MGS_GOOD_CAPTURES_AND_PROMOTIONS &&
  1306.           movesAreEqual(currentMove,
  1307.                         variation->plyInfo[ply].killerMove1) == FALSE &&
  1308.           movesAreEqual(currentMove,
  1309.                         variation->plyInfo[ply].killerMove2) == FALSE &&
  1310.           isPassedPawnMove(toSquare, toSquare, position) == FALSE)
  1311.       {
  1312.          reduce = TRUE;
  1313.       }
  1314.  
  1315.       /* Recursive search */
  1316.       /* ---------------- */
  1317.       if (pvNode && numMovesPlayed == 0)
  1318.       {
  1319.          value = -searchBest(variation, -beta, -alpha, ply + 1,
  1320.                              newDepth, pvNode, FALSE, &bestReply, NO_MOVE,
  1321.                              TRUE);
  1322.       }
  1323.       else
  1324.       {
  1325.          const Move cm1 = variation->plyInfo[ply].killerMove3;
  1326.          const Move cm2 = variation->plyInfo[ply].killerMove4;
  1327.          const bool counterMove = movesAreEqual(currentMove, cm1) ||
  1328.             movesAreEqual(currentMove, cm2);
  1329.          const int effectiveReduction =
  1330.             max(0, reduction - (counterMove ? DEPTH_RESOLUTION : 0));
  1331.          const int minRestDepth = (pvNode ? DEPTH_RESOLUTION : 0);
  1332.          const int reducedRestDepth =
  1333.             max(minRestDepth, newDepth - effectiveReduction);
  1334.  
  1335.          bool fullDepthSearch = TRUE;
  1336.  
  1337.          if (reduce && effectiveReduction > 0)
  1338.          {
  1339.             value = -searchBest(variation, -alpha - 1, -alpha, ply + 1,
  1340.                                 reducedRestDepth, FALSE, TRUE,
  1341.                                 &bestReply, NO_MOVE, TRUE);
  1342.  
  1343.             if (value > alpha && effectiveReduction >= 4 * DEPTH_RESOLUTION &&
  1344.                 stage != MGS_KILLER_MOVES)
  1345.             {
  1346.                const int limitedRestDepth =
  1347.                   max(DEPTH_RESOLUTION, newDepth - 2 * DEPTH_RESOLUTION);
  1348.  
  1349.                value = -searchBest(variation, -alpha - 1, -alpha, ply + 1,
  1350.                                    limitedRestDepth, FALSE,
  1351.                                    TRUE, &bestReply, NO_MOVE, TRUE);
  1352.             }
  1353.  
  1354.             fullDepthSearch = (bool) (value > alpha);
  1355.          }
  1356.  
  1357.          if (fullDepthSearch)
  1358.          {
  1359.             value = -searchBest(variation, -alpha - 1, -alpha, ply + 1,
  1360.                                 newDepth, FALSE, !cutNode, &bestReply,
  1361.                                 NO_MOVE, TRUE);
  1362.  
  1363.             if (pvNode && value > alpha && value < beta)
  1364.             {                   /* 2% */
  1365.                value = -searchBest(variation, -beta, -alpha, ply + 1,
  1366.                                    newDepth, TRUE, FALSE, &bestReply,
  1367.                                    NO_MOVE, TRUE);
  1368.             }
  1369.          }
  1370.       }
  1371.  
  1372.       assert(value >= VALUE_MATED && value <= -VALUE_MATED);
  1373.  
  1374.       if (nodeWasBlocked)
  1375.       {
  1376.          resetNodeUsage(position->hashKey, restDepth);
  1377.       }
  1378.  
  1379.       unmakeLastMove(variation);
  1380.       numMovesPlayed++;
  1381.  
  1382.       if (quietMove && inCheck == FALSE)
  1383.       {
  1384.          quietMoveIndex[quietMoveCount++] =
  1385.             historyIndex(currentMove, position);
  1386.       }
  1387.  
  1388.       /* Calculate the parameters controlling the search tree. */
  1389.       /* ----------------------------------------------------- */
  1390.       if (value > best)
  1391.       {                         /* 32% */
  1392.          best = value;
  1393.  
  1394.          if (best > alpha)
  1395.          {                      /* 63% */
  1396.             alpha = best;
  1397.             *bestMove = currentMove;
  1398.  
  1399.             if (pvNode)
  1400.             {
  1401.                appendMoveToPv(&(variation->plyInfo[ply].pv),
  1402.                               &(variation->plyInfo[ply - 1].pv), currentMove);
  1403.             }
  1404.  
  1405.             if (best >= beta)
  1406.             {                   /* 99% */
  1407.                break;
  1408.             }
  1409.          }
  1410.       }
  1411.    }
  1412.  
  1413.    /* No legal move was found. Check if it's mate or stalemate. */
  1414.    /* --------------------------------------------------------- */
  1415.    if (best == VALUE_MATED)
  1416.    {
  1417.       if (excludeMove != NO_MOVE && excludeMove != NULLMOVE)
  1418.       {
  1419.          return beta - 1;
  1420.       }
  1421.  
  1422.       if (inCheck)
  1423.       {
  1424.          /* mate */
  1425.  
  1426.          best = VALUE_MATED + ply;
  1427.       }
  1428.       else
  1429.       {
  1430.          /* stalemate */
  1431.  
  1432.          best = variation->drawScore[position->activeColor];
  1433.       }
  1434.    }
  1435.  
  1436.    /* Calculate the parameters controlling the move ordering. */
  1437.    /* ------------------------------------------------------- */
  1438.    if (*bestMove != NO_MOVE && moveIsQuiet(*bestMove, position) &&
  1439.        inCheck == FALSE &&
  1440.        (excludeMove == NO_MOVE || excludeMove == NULLMOVE))
  1441.    {
  1442.       Move killerMove = *bestMove;
  1443.       const Piece movingPiece = position->piece[getFromSquare(killerMove)];
  1444.       const int index = historyIndex(*bestMove, position);
  1445.       const UINT16 bestMoveValue = (UINT16)
  1446.          (variation->historyValue[index] +
  1447.           ((HISTORY_MAX - variation->historyValue[index]) * restDepth) / 256);
  1448.       int i;
  1449.  
  1450.       for (i = 0; i < quietMoveCount; i++)
  1451.       {
  1452.          const int historyIdx = quietMoveIndex[i];
  1453.  
  1454.          variation->historyValue[historyIdx] = (UINT16)
  1455.             (variation->historyValue[historyIdx] -
  1456.              (variation->historyValue[historyIdx] * restDepth) / 128);
  1457.          assert(variation->historyValue[historyIdx] <= HISTORY_MAX);
  1458.       }
  1459.  
  1460.       variation->historyValue[index] = bestMoveValue;
  1461.       assert(variation->historyValue[index] <= HISTORY_MAX);
  1462.  
  1463.       setMoveValue(&killerMove, movingPiece);
  1464.       registerKillerMove(&variation->plyInfo[ply], killerMove);
  1465.       updateCounterMoves(variation, ply, killerMove);
  1466.  
  1467.       if (ply >= 2 && variation->plyInfo[ply - 1].isHashMove)
  1468.       {
  1469.          updateFollowupMoves(variation, ply, killerMove);
  1470.       }
  1471.    }
  1472.  
  1473.  storeResult:
  1474.  
  1475.    /* Store the value in the transposition table. */
  1476.    /* ------------------------------------------- */
  1477.    if ((excludeMove == NO_MOVE || excludeMove == NULLMOVE) &&
  1478.        variation->searchStatus == SEARCH_STATUS_RUNNING)
  1479.    {
  1480.       if (best >= beta)
  1481.       {
  1482.          hashentryFlag = HASHVALUE_LOWER_LIMIT;
  1483.       }
  1484.       else
  1485.       {
  1486.          hashentryFlag = (pvNode && *bestMove != NO_MOVE ?
  1487.                           HASHVALUE_EXACT : HASHVALUE_UPPER_LIMIT);
  1488.       }
  1489.  
  1490.       setHashentry(getSharedHashtable(), hashKey,
  1491.                    calcHashtableValue(best, ply),
  1492.                    (UINT8) (restDepth + HASH_DEPTH_OFFSET),
  1493.                    packedMove(*bestMove), hashentryFlag,
  1494.                    (INT16) getStaticValue(variation, ply));
  1495.  
  1496. #ifdef SEND_HASH_ENTRIES
  1497.       if (hashentryFlag == HASHVALUE_EXACT &&
  1498.           restDepth >= minPvHashEntrySendDepth &&
  1499.           ply <= maxPvHashEntrySendHeight)
  1500.       {
  1501.          const long timestamp = getTimestamp();
  1502.          const long elapsedTime = timestamp - variation->startTime;
  1503.          const long intervalTime = timestamp - variation->hashSendTimestamp;
  1504.  
  1505.          if (elapsedTime >= minPvHashEntrySendTime &&
  1506.              intervalTime >= pvHashEntriesSendInterval)
  1507.          {
  1508.             Hashentry entry =
  1509.                constructHashEntry(hashKey, calcHashtableValue(best, ply),
  1510.                                   (INT16) getStaticValue(variation, ply),
  1511.                                   (UINT8) (restDepth + HASH_DEPTH_OFFSET),
  1512.                                   packedMove(*bestMove), 0, hashentryFlag);
  1513.  
  1514.             sendHashentry(&entry);
  1515.             variation->hashSendTimestamp = timestamp;
  1516.          }
  1517.       }
  1518. #endif
  1519.    }
  1520.  
  1521.    return best;
  1522. }
  1523.  
  1524. void copyPvFromHashtable(Variation * variation, const int pvIndex,
  1525.                          PrincipalVariation * pv, const Move bestBaseMove)
  1526. {
  1527.    Move bestMove = NO_MOVE;
  1528.  
  1529.    if (pvIndex == 0)
  1530.    {
  1531.       bestMove = bestBaseMove;
  1532.    }
  1533.    else
  1534.    {
  1535.       Hashentry *tableHit = getHashentry(getSharedHashtable(),
  1536.                                          variation->singlePosition.hashKey);
  1537.  
  1538.       if (tableHit != NULL)
  1539.       {
  1540.          Move currentMove = (Move) getHashentryMove(tableHit);
  1541.  
  1542.          if (moveIsLegal(&variation->singlePosition, currentMove))
  1543.          {
  1544.             bestMove = (Move) getHashentryMove(tableHit);
  1545.          }
  1546.       }
  1547.    }
  1548.  
  1549.    if (bestMove != NO_MOVE && pvIndex < MAX_DEPTH)
  1550.    {
  1551.       pv->move[pvIndex] = (UINT16) bestMove;
  1552.       pv->move[pvIndex + 1] = (UINT16) NO_MOVE;
  1553.       pv->length = pvIndex + 1;
  1554.       makeMove(variation, bestMove);
  1555.       copyPvFromHashtable(variation, pvIndex + 1, pv, bestBaseMove);
  1556.       unmakeLastMove(variation);
  1557.    }
  1558.    else
  1559.    {
  1560.       pv->move[pvIndex] = (UINT16) NO_MOVE;
  1561.       pv->length = pvIndex;
  1562.    }
  1563. }
  1564.  
  1565. static void copyPvToHashtable(Variation * variation,
  1566.                               PrincipalVariation * pv, const int pvIndex)
  1567. {
  1568.    Move move = (Move) pv->move[pvIndex];
  1569.  
  1570.    if (pvIndex < pv->length && moveIsLegal(&variation->singlePosition, move))
  1571.    {
  1572.       UINT8 importance = (UINT8) HASH_DEPTH_OFFSET;
  1573.       bool entryExists = FALSE;
  1574.       Move bestMove = NO_MOVE;
  1575.       Hashentry *tableHit = getHashentry(getSharedHashtable(),
  1576.                                          variation->singlePosition.hashKey);
  1577.  
  1578.       if (tableHit != 0)
  1579.       {
  1580.          bestMove = (Move) getHashentryMove(tableHit);
  1581.          importance = max(importance, getHashentryImportance(tableHit));
  1582.  
  1583.          if (bestMove != NO_MOVE && movesAreEqual(bestMove, move))
  1584.          {
  1585.             entryExists = TRUE;
  1586.          }
  1587.       }
  1588.  
  1589.       if (entryExists == FALSE)
  1590.       {
  1591.          UINT8 hashentryFlag = HASHVALUE_LOWER_LIMIT;
  1592.  
  1593.          /* Store the move in the transposition table. */
  1594.          /* ------------------------------------------- */
  1595.  
  1596.          setHashentry(getSharedHashtable(),
  1597.                       variation->singlePosition.hashKey, VALUE_MATED,
  1598.                       importance, packedMove(move),
  1599.                       hashentryFlag, getEvalValue(variation));
  1600.       }
  1601.  
  1602.       makeMove(variation, move);
  1603.       copyPvToHashtable(variation, pv, pvIndex + 1);
  1604.       unmakeLastMove(variation);
  1605.    }
  1606. }
  1607.  
  1608. static void registerBestMove(Variation * variation, Move * move,
  1609.                              const int value)
  1610. {
  1611.    if (variation->searchStatus == SEARCH_STATUS_RUNNING)
  1612.    {
  1613.       setMoveValue(move, value);
  1614.       variation->bestBaseMove = *move;
  1615.  
  1616.       if (variation->iteration > 4 && variation->numberOfCurrentBaseMove > 1)
  1617.       {
  1618.          variation->bestMoveChangeCount += 256;
  1619.       }
  1620.    }
  1621. }
  1622.  
  1623. static int getBaseMoveValue(Variation * variation, const Move move,
  1624.                             const int alpha, const int beta,
  1625.                             const bool fullWindow)
  1626. {
  1627.    int depth = DEPTH_RESOLUTION * variation->iteration;
  1628.    int value;
  1629.    Move bestReply;
  1630.  
  1631.    assert(alpha >= VALUE_MATED);
  1632.    assert(alpha <= -VALUE_MATED);
  1633.    assert(beta >= VALUE_MATED);
  1634.    assert(beta <= -VALUE_MATED);
  1635.    assert(alpha < beta);
  1636.  
  1637.    makeMoveFast(variation, move);
  1638.  
  1639.    if (variation->nodes > GUI_NODE_COUNT_MIN &&
  1640.        variation->threadNumber == 0 && variation->handleSearchEvent != 0)
  1641.    {
  1642.       getGuiSearchMutex();
  1643.       variation->handleSearchEvent(SEARCHEVENT_NEW_BASEMOVE, variation);
  1644.       releaseGuiSearchMutex();
  1645.    }
  1646.  
  1647.    if (activeKingIsSafe(&variation->singlePosition) == FALSE)
  1648.    {
  1649.       variation->plyInfo[0].currentMoveIsCheck = TRUE;
  1650.       depth += DEPTH_RESOLUTION;
  1651.    }
  1652.    else
  1653.    {
  1654.       variation->plyInfo[0].currentMoveIsCheck = FALSE;
  1655.    }
  1656.  
  1657.    if (fullWindow)
  1658.    {
  1659.       value = -searchBest(variation, -beta, -alpha, 1,
  1660.                           depth - DEPTH_RESOLUTION, TRUE, FALSE,
  1661.                           &bestReply, NO_MOVE, TRUE);
  1662.    }
  1663.    else
  1664.    {
  1665.       value = -searchBest(variation, -alpha - 1, -alpha, 1,
  1666.                           depth - DEPTH_RESOLUTION, FALSE, TRUE,
  1667.                           &bestReply, NO_MOVE, TRUE);
  1668.  
  1669.       if (value > alpha)
  1670.       {
  1671.          value = -searchBest(variation, -beta, -alpha, 1,
  1672.                              depth - DEPTH_RESOLUTION, TRUE,
  1673.                              FALSE, &bestReply, NO_MOVE, TRUE);
  1674.       }
  1675.    }
  1676.  
  1677.    unmakeLastMove(variation);
  1678.  
  1679.    return value;
  1680. }
  1681.  
  1682. int getPvScoreType(int value, int alpha, int beta)
  1683. {
  1684.    if (value <= alpha)
  1685.    {
  1686.       return HASHVALUE_UPPER_LIMIT;
  1687.    }
  1688.    else if (value >= beta)
  1689.    {
  1690.       return HASHVALUE_LOWER_LIMIT;
  1691.    }
  1692.    else
  1693.    {
  1694.       return HASHVALUE_EXACT;
  1695.    }
  1696. }
  1697.  
  1698. static void sendPvInfo(Variation * variation, const int eventType)
  1699. {
  1700.    if ((variation->nodes > GUI_NODE_COUNT_MIN ||
  1701.         eventType == SEARCHEVENT_PLY_FINISHED) &&
  1702.        variation->threadNumber == 0 && variation->handleSearchEvent != 0)
  1703.    {
  1704.       int i;
  1705.  
  1706.       getGuiSearchMutex();
  1707.  
  1708.       for (i = 0; i < numPvs && variation->pv[i].length > 0; i++)
  1709.       {
  1710.          variation->pvId = i;
  1711.          variation->handleSearchEvent(eventType, variation);
  1712.       }
  1713.  
  1714.       releaseGuiSearchMutex();
  1715.    }
  1716. }
  1717.  
  1718. static void exploreBaseMoves(Variation * variation, Movelist * basemoves,
  1719.                              const int aspirationWindow)
  1720. {
  1721.    const int previousBest = variation->previousBest;
  1722.    const int ply = 0;
  1723.    Position *position = &variation->singlePosition;
  1724.    const bool fullWindow = (bool) (variation->iteration <= 3);
  1725.    int window = aspirationWindow, best;
  1726.    bool exactValueFound = FALSE;
  1727.    const int staticValue = getEvalValue(variation);
  1728.    int alpha =
  1729.       (fullWindow ? VALUE_MATED : max(VALUE_MATED, previousBest - window));
  1730.    int beta =
  1731.       (fullWindow ? -VALUE_MATED : min(-VALUE_MATED, previousBest + window));
  1732.  
  1733.    variation->failingLow = FALSE;
  1734.    variation->selDepth = variation->iteration;
  1735.    initializePvsOfVariation(variation);
  1736.  
  1737.    do
  1738.    {
  1739.       int pvCount = 0, worstValue = VALUE_MATED;
  1740.       const int numPvLimit = min(basemoves->numberOfMoves, numPvs);
  1741.  
  1742.       initializeMoveValues(basemoves);
  1743.       resetPvsOfVariation(variation);
  1744.       best = VALUE_MATED;
  1745.  
  1746.       for (variation->numberOfCurrentBaseMove = 1;
  1747.            variation->numberOfCurrentBaseMove <= basemoves->numberOfMoves;
  1748.            variation->numberOfCurrentBaseMove++)
  1749.       {
  1750.          int value;
  1751.          const int icm = variation->numberOfCurrentBaseMove - 1;
  1752.          const bool searchBelowBest = fullWindow || numPvs > 1;
  1753.          const bool pvNode = (bool) (icm == 0 || searchBelowBest);
  1754.          const int searchAlpha = (searchBelowBest ? alpha : max(alpha, best));
  1755.  
  1756.          resetPlyInfo(variation);
  1757.          variation->currentBaseMove = basemoves->moves[icm];
  1758.          variation->plyInfo[ply].indexCurrentMove =
  1759.             historyIndex(variation->currentBaseMove, position);
  1760.  
  1761.          value = getBaseMoveValue(variation, basemoves->moves[icm],
  1762.                                   searchAlpha, beta, pvNode);
  1763.  
  1764.          if (variation->searchStatus != SEARCH_STATUS_RUNNING &&
  1765.              variation->iteration > 1)
  1766.          {
  1767.             break;
  1768.          }
  1769.  
  1770.          if (icm == 0 || value > searchAlpha)
  1771.          {
  1772.             PrincipalVariation pv;
  1773.  
  1774.             setMoveValue(&basemoves->moves[icm], value);
  1775.             pv.score = value;
  1776.             pv.scoreType = getPvScoreType(value, searchAlpha, beta);
  1777.             appendMoveToPv(&(variation->plyInfo[0].pv), &pv,
  1778.                            basemoves->moves[icm]);
  1779.             addPvByScore(variation, &pv);
  1780.  
  1781.             if (++pvCount >= numPvLimit)
  1782.             {
  1783.                sendPvInfo(variation, SEARCHEVENT_NEW_PV);
  1784.             }
  1785.  
  1786.             if (icm == 0 || value > best)
  1787.             {
  1788.                registerBestMove(variation, &basemoves->moves[icm], value);
  1789.  
  1790.                if (value > best && value < beta)
  1791.                {
  1792.                   variation->completePv = pv;
  1793.                }
  1794.             }
  1795.          }
  1796.  
  1797.          if (value > best)
  1798.          {
  1799.             best = value;
  1800.  
  1801.             if (value >= beta && numPvs == 1)
  1802.             {
  1803.                break;
  1804.             }
  1805.          }
  1806.       }
  1807.  
  1808.       /* Store the value in the transposition table. */
  1809.       /* ------------------------------------------- */
  1810.       if (variation->searchStatus == SEARCH_STATUS_RUNNING)
  1811.       {
  1812.          UINT8 hashentryFlag;
  1813.          const int depth = DEPTH_RESOLUTION * variation->iteration;
  1814.          const Move bestMove = variation->bestBaseMove;
  1815.  
  1816.          if (best > alpha)
  1817.          {
  1818.             hashentryFlag =
  1819.                (best >= beta ? HASHVALUE_LOWER_LIMIT : HASHVALUE_EXACT);
  1820.          }
  1821.          else
  1822.          {
  1823.             hashentryFlag = HASHVALUE_UPPER_LIMIT;
  1824.          }
  1825.  
  1826.          setHashentry(getSharedHashtable(), position->hashKey,
  1827.                       calcHashtableValue(best, ply),
  1828.                       (UINT8) (depth + HASH_DEPTH_OFFSET),
  1829.                       packedMove(bestMove), hashentryFlag,
  1830.                       (INT16) staticValue);
  1831.       }
  1832.  
  1833.       worstValue = (numPvs == 1 ? best :
  1834.                     max(VALUE_MATED + 3, variation->pv[numPvs - 1].score));
  1835.  
  1836.       if (best >= beta)
  1837.       {
  1838.          beta = min(-VALUE_MATED, best + window);
  1839.       }
  1840.       else if (worstValue <= alpha && worstValue > VALUE_MATED + 2)
  1841.       {
  1842.          alpha = max(VALUE_MATED, alpha - window);
  1843.          variation->failingLow = TRUE;
  1844.       }
  1845.       else
  1846.       {
  1847.          exactValueFound = TRUE;        /* exact value found */
  1848.       }
  1849.  
  1850.       window = window + window / 2;
  1851.  
  1852.       sortMoves(basemoves);
  1853.  
  1854.       assert(fullWindow == TRUE ||
  1855.              movesAreEqual(basemoves->moves[0], variation->bestBaseMove));
  1856.  
  1857.       if (variation->threadNumber == 0)
  1858.       {
  1859.          copyPvToHashtable(variation, &variation->completePv, 0);
  1860.       }
  1861.    }
  1862.    while (variation->searchStatus == SEARCH_STATUS_RUNNING &&
  1863.           exactValueFound == FALSE);
  1864.  
  1865.    variation->pv[0].score = getMoveValue(variation->bestBaseMove);
  1866.  
  1867.    if (variation->threadNumber == 0 && variation->iteration > 1 &&
  1868.        variation->completePv.length <= 1)
  1869.    {
  1870.       PrincipalVariation tmpPv;
  1871.  
  1872.       copyPvFromHashtable(variation, 0, &tmpPv, variation->bestBaseMove);
  1873.  
  1874.       if (tmpPv.length > 1)
  1875.       {
  1876.          variation->completePv = tmpPv;
  1877.       }
  1878.    }
  1879.  
  1880.    sendPvInfo(variation, SEARCHEVENT_PLY_FINISHED);
  1881. }
  1882.  
  1883. static void initializePawnHashtable(PawnHashInfo * pawnHashtable)
  1884. {
  1885.    int i;
  1886.  
  1887.    for (i = 0; i < PAWN_HASHTABLE_SIZE; i++)
  1888.    {
  1889.       pawnHashtable[i].hashKey = 0;
  1890.    }
  1891. }
  1892.  
  1893. static void initializeKingsafetyHashtable(KingSafetyHashInfo *
  1894.                                           kingsafetyHashtable)
  1895. {
  1896.    int i;
  1897.  
  1898.    for (i = 0; i < KINGSAFETY_HASHTABLE_SIZE; i++)
  1899.    {
  1900.       kingsafetyHashtable[i].hashKey = 0;
  1901.    }
  1902. }
  1903.  
  1904. static void updatePieceValues()
  1905. {
  1906.    maxPieceValue[WHITE_QUEEN] = maxPieceValue[BLACK_QUEEN] =
  1907.       max(getOpeningValue(basicValue[WHITE_QUEEN]),
  1908.           getEndgameValue(basicValue[WHITE_QUEEN])) - 42;
  1909.    maxPieceValue[WHITE_ROOK] = maxPieceValue[BLACK_ROOK] =
  1910.       max(getOpeningValue(basicValue[WHITE_ROOK]),
  1911.           getEndgameValue(basicValue[WHITE_ROOK]));
  1912.    maxPieceValue[WHITE_BISHOP] = maxPieceValue[BLACK_BISHOP] =
  1913.       max(getOpeningValue(basicValue[WHITE_BISHOP]),
  1914.           getEndgameValue(basicValue[WHITE_BISHOP]));
  1915.    maxPieceValue[WHITE_KNIGHT] = maxPieceValue[BLACK_KNIGHT] =
  1916.       max(getOpeningValue(basicValue[WHITE_KNIGHT]),
  1917.           getEndgameValue(basicValue[WHITE_KNIGHT]));
  1918.    maxPieceValue[WHITE_PAWN] = maxPieceValue[BLACK_PAWN] =
  1919.       max(getOpeningValue(basicValue[WHITE_PAWN]),
  1920.           getEndgameValue(basicValue[WHITE_PAWN]));
  1921. }
  1922.  
  1923. Move search(Variation * variation, Movelist * acceptableSolutions)
  1924. {
  1925.    Movelist movelist;
  1926.    long timeTarget;
  1927.    int stableIterationCount = 0;
  1928.    int stableBestMoveCount = 0;
  1929.    Move bestMove = NO_MOVE;
  1930.    UINT64 nodeCount = 0;
  1931.    int iv1 = 0, iv2 = 0, iv3 = 0;
  1932.  
  1933.    if (resetSharedHashtable)
  1934.    {
  1935.       resetHashtable(getSharedHashtable());
  1936.       initializePawnHashtable(variation->pawnHashtable);
  1937.       initializeKingsafetyHashtable(variation->kingsafetyHashtable);
  1938.       resetSharedHashtable = FALSE;
  1939.    }
  1940.  
  1941.    resetHistoryValues(variation);
  1942.    resetGainValues(variation);
  1943.  
  1944.    variation->ply = 0;
  1945.    variation->ownColor = variation->singlePosition.activeColor;
  1946.    variation->nodes = variation->nodesAtTimeCheck = 0;
  1947.    variation->startTimeProcess = getProcessTimestamp();
  1948.    variation->timestamp = variation->startTime + 1;
  1949.    variation->hashSendTimestamp = variation->startTime;
  1950.    variation->tbHits = 0;
  1951.    variation->numPvUpdates = 0;
  1952.    variation->terminateSearchOnPonderhit = FALSE;
  1953.    variation->previousBest = getStaticValue(variation, 0);
  1954.    variation->bestBaseMove = NO_MOVE;
  1955.    variation->failingLow = FALSE;
  1956.    movelist.positionalGain = &(variation->positionalGain[0]);
  1957.    initializePlyInfo(variation);
  1958.    getLegalMoves(variation, &movelist);
  1959.  
  1960. #ifdef TRACE_EVAL
  1961.    getValue(&variation->singlePosition, VALUE_MATED, -VALUE_MATED,
  1962.             variation->pawnHashtable, variation->kingsafetyHashtable);
  1963. #endif
  1964.  
  1965. #ifdef USE_BOOK
  1966.    if (globalBook.indexFile != NULL && globalBook.moveFile != NULL &&
  1967.        &variation->singlePosition->moveNumber <= 12)
  1968.    {
  1969.       Move bookMove = getBookmove(&globalBook,
  1970.                                   &variation->singlePosition->hashKey,
  1971.                                   &movelist);
  1972.  
  1973.       if (bookMove != NO_MOVE)
  1974.       {
  1975.          variation->bestBaseMove = bookMove;
  1976.          variation->searchStatus = SEARCH_STATUS_TERMINATE;
  1977.          variation->finishTime = getTimestamp();
  1978.  
  1979.          if (variation->handleSearchEvent != 0)
  1980.          {
  1981.             getGuiSearchMutex();
  1982.             variation->handleSearchEvent(SEARCHEVENT_SEARCH_FINISHED,
  1983.                                          variation);
  1984.             releaseGuiSearchMutex();
  1985.          }
  1986.  
  1987.          variation->nodes = 0;
  1988.  
  1989.          return variation->bestBaseMove;
  1990.       }
  1991.    }
  1992. #endif
  1993.  
  1994.    variation->numberOfBaseMoves = movelist.numberOfMoves;
  1995.    setMoveValue(&variation->bestBaseMove, VALUE_MATED);
  1996.  
  1997.    for (variation->iteration = 1; variation->iteration <= MAX_DEPTH;
  1998.         variation->iteration++)
  1999.    {
  2000.       long calculationTime;
  2001.       int iterationValue, aspirationWindow;
  2002.  
  2003.       variation->ply = 0;
  2004.  
  2005.       aspirationWindow =
  2006.          min(12, max(8, (abs(iv1 - iv2) + abs(iv2 - iv3)) / 2));
  2007.       exploreBaseMoves(variation, &movelist, aspirationWindow);
  2008.       calculationTime =
  2009.          (unsigned long) (getTimestamp() - variation->startTime);
  2010.  
  2011.       if (movesAreEqual(variation->bestBaseMove, bestMove))
  2012.       {
  2013.          stableBestMoveCount++;
  2014.       }
  2015.       else
  2016.       {
  2017.          stableBestMoveCount = 0;
  2018.       }
  2019.  
  2020.       bestMove = variation->bestBaseMove;
  2021.       iv3 = iv2;
  2022.       iv2 = iv1;
  2023.       iv1 = iterationValue = getMoveValue(variation->bestBaseMove);
  2024.  
  2025.       variation->previousBest = iterationValue;
  2026.  
  2027.       assert(calculationTime >= 0);
  2028.  
  2029.       if (acceptableSolutions != 0 &&
  2030.           listContainsMove(acceptableSolutions, variation->bestBaseMove))
  2031.       {
  2032.          stableIterationCount++;
  2033.  
  2034.          if (stableIterationCount == 1)
  2035.          {
  2036.             nodeCount = variation->nodes;
  2037.          }
  2038.       }
  2039.       else
  2040.       {
  2041.          stableIterationCount = 0;
  2042.          nodeCount = variation->nodes;
  2043.       }
  2044.  
  2045.       /* Check for a fail low. */
  2046.       /* --------------------- */
  2047.  
  2048.       if (variation->numberOfBaseMoves == 1)
  2049.       {
  2050.          timeTarget = (19 * variation->timeTarget) / 256;
  2051.       }
  2052.       else
  2053.       {
  2054.          const int timeWeight = 160 +
  2055.             (223 * variation->bestMoveChangeCount) / 256;
  2056.  
  2057.          timeTarget = (timeWeight * variation->timeTarget) / 256;
  2058.       }
  2059.  
  2060.       variation->bestMoveChangeCount =
  2061.          (17 * variation->bestMoveChangeCount) / 32;
  2062.  
  2063.       getGuiSearchMutex();
  2064.  
  2065.       if (variation->threadNumber == 0 &&
  2066.           variation->searchStatus == SEARCH_STATUS_RUNNING &&
  2067.           variation->iteration > 8 && variation->timeLimit != 0 &&
  2068.           calculationTime >= timeTarget)
  2069.       {
  2070. #ifdef DEBUG_THREAD_COORDINATION
  2071.          logDebug
  2072.             ("Time target reached (%lu/%lu ms, %lu%%)).\n",
  2073.              calculationTime, variation->timeTarget,
  2074.              (calculationTime * 100) / variation->timeTarget);
  2075. #endif
  2076.  
  2077.          if (variation->ponderMode)
  2078.          {
  2079.             variation->terminateSearchOnPonderhit = TRUE;
  2080.  
  2081. #ifdef DEBUG_THREAD_COORDINATION
  2082.             logDebug("Setting ponder termination flag.\n");
  2083. #endif
  2084.          }
  2085.          else
  2086.          {
  2087.             variation->searchStatus = SEARCH_STATUS_TERMINATE;
  2088.  
  2089. #ifdef DEBUG_THREAD_COORDINATION
  2090.             logDebug("Terminating search.\n");
  2091. #endif
  2092.          }
  2093.       }
  2094.  
  2095.       if (variation->searchStatus == SEARCH_STATUS_RUNNING &&
  2096.           (getMoveValue(variation->bestBaseMove) <=
  2097.            VALUE_MATED + variation->iteration ||
  2098.            getMoveValue(variation->bestBaseMove) >=
  2099.            -VALUE_MATED - variation->iteration))
  2100.       {
  2101. #ifdef DEBUG_THREAD_COORDINATION
  2102.          logDebug("Best value out of bounds (%d). Terminating search.\n",
  2103.                   getMoveValue(variation->bestBaseMove));
  2104. #endif
  2105.          variation->searchStatus = SEARCH_STATUS_TERMINATE;
  2106.       }
  2107.  
  2108.       if (variation->searchStatus == SEARCH_STATUS_RUNNING &&
  2109.           variation->iteration == MAX_DEPTH)
  2110.       {
  2111. #ifdef DEBUG_THREAD_COORDINATION
  2112.          logDebug("Max depth reached. Terminating search.\n");
  2113. #endif
  2114.          variation->searchStatus = SEARCH_STATUS_TERMINATE;
  2115.       }
  2116.  
  2117.       if (acceptableSolutions != 0 && stableIterationCount >= 1 &&
  2118.           (getMoveValue(variation->bestBaseMove) > 20000 ||
  2119.            (stableIterationCount >= 2 &&
  2120.             (getMoveValue(variation->bestBaseMove) >= 25 ||
  2121.              (getTimestamp() - variation->startTime) >= 3000))))
  2122.       {
  2123. #ifdef DEBUG_THREAD_COORDINATION
  2124.          logDebug("Solution found (value=%d). Terminating search.\n",
  2125.                   getMoveValue(variation->bestBaseMove));
  2126. #endif
  2127.          variation->searchStatus = SEARCH_STATUS_TERMINATE;
  2128.       }
  2129.  
  2130.       if (variation->searchStatus != SEARCH_STATUS_RUNNING)
  2131.       {
  2132.          variation->terminateSearchOnPonderhit = TRUE;
  2133.          variation->searchStatus = SEARCH_STATUS_TERMINATE;
  2134.  
  2135.          variation->finishTime = getTimestamp();
  2136.          variation->finishTimeProcess = getProcessTimestamp();
  2137.  
  2138.          if (variation->threadNumber == 0)
  2139.          {
  2140.             incrementDate(getSharedHashtable());
  2141.  
  2142.             if (variation->handleSearchEvent != 0)
  2143.             {
  2144.                variation->handleSearchEvent(SEARCHEVENT_SEARCH_FINISHED,
  2145.                                             variation);
  2146.             }
  2147.          }
  2148.       }
  2149.  
  2150.       if (variation->searchStatus != SEARCH_STATUS_RUNNING)
  2151.       {
  2152. #ifdef DEBUG_THREAD_COORDINATION
  2153.          logReport
  2154.             ("search status != SEARCH_STATUS_RUNNING -> exiting search.\n",
  2155.              getMoveValue(variation->bestBaseMove));
  2156. #endif
  2157.  
  2158.          releaseGuiSearchMutex();
  2159.          break;
  2160.       }
  2161.  
  2162.       releaseGuiSearchMutex();
  2163.    }
  2164.  
  2165.    variation->nodes = nodeCount;
  2166.  
  2167.    if (statCount1 != 0 || statCount2 != 0)
  2168.    {
  2169.       logReport("statCount1=%lld statCount2=%lld (%lld%%) \n",
  2170.                 statCount1, statCount2,
  2171.                 (statCount2 * 100) / max(1, statCount1));
  2172.    }
  2173.  
  2174.    return variation->bestBaseMove;
  2175. }
  2176.  
  2177. /* #define DEBUG_FUT_VALUES */
  2178.  
  2179. static void initializeArrays(void)
  2180. {
  2181.    int i, j;
  2182.  
  2183.    for (i = 0; i < 64; i++)
  2184.    {
  2185.       for (j = 0; j < 64; j++)
  2186.       {
  2187.          if (i == 0 || j == 0)
  2188.          {
  2189.             quietPvMoveReduction[i][j] =
  2190.                quietMoveReduction[0][i][j] = quietMoveReduction[1][i][j] = 0;
  2191.          }
  2192.          else
  2193.          {
  2194.             const double baseFactor = log((double) (i)) * log((double) (j));
  2195.             const double pvReduction = baseFactor / 2.93;
  2196.             const double nonPvReduction = 0.33 + baseFactor / 2.21;
  2197.  
  2198.             quietPvMoveReduction[i][j] =
  2199.                (int) (pvReduction >= 1.0 ?
  2200.                       floor(pvReduction * DEPTH_RESOLUTION) : 0);
  2201.             quietMoveReduction[0][i][j] =
  2202.                quietMoveReduction[1][i][j] =
  2203.                (int) (nonPvReduction >= 1.0 ?
  2204.                       floor(nonPvReduction * DEPTH_RESOLUTION) : 0);
  2205.  
  2206.             if (quietMoveReduction[0][i][j] > 2 * DEPTH_RESOLUTION)
  2207.             {
  2208.                quietMoveReduction[0][i][j] += DEPTH_RESOLUTION;
  2209.             }
  2210.             else if (quietMoveReduction[0][i][j] > DEPTH_RESOLUTION)
  2211.             {
  2212.                quietMoveReduction[0][i][j] += DEPTH_RESOLUTION / 2;
  2213.             }
  2214.          }
  2215.       }
  2216.    }
  2217.  
  2218.    for (i = 0; i < 32; i++)
  2219.    {
  2220.       quietMoveCountLimit[0][i] = (int) (2.4 + 0.231 * pow(i, 1.8));
  2221.       quietMoveCountLimit[1][i] = (int) (3.1 + 0.344 * pow(i + 0.78, 1.8));
  2222.  
  2223. #ifdef DEBUG_FUT_VALUES
  2224.       logDebug("mcl[%d]=%d\n", i, quietMoveCountLimit[i]);
  2225. #endif
  2226.    }
  2227.  
  2228.    for (i = 0; i <= NUM_FUTILITY_MARGIN_VALUES; i++)
  2229.    {
  2230.       futilityMargin[i] = (3125 * i) / 64 - 12800 / 256;
  2231.  
  2232. #ifdef DEBUG_FUT_VALUES
  2233.       if (j <= 2)
  2234.       {
  2235.          logDebug("fm[%d][%d]=%d\n", i, j, futilityMargin[i][j]);
  2236.       }
  2237. #endif
  2238.    }
  2239.  
  2240.    updatePieceValues();
  2241.  
  2242. #ifdef DEBUG_FUT_VALUES
  2243.    getKeyStroke();
  2244. #endif
  2245. }
  2246.  
  2247. int initializeModuleSearch(void)
  2248. {
  2249.    initializeArrays();
  2250.  
  2251.    return 0;
  2252. }
  2253.  
  2254. int testModuleSearch(void)
  2255. {
  2256.    return 0;
  2257. }
  2258.