/*
    Protector -- a UCI chess engine

    Copyright (C) 2009-2010 Raimund Heid (Raimund_Heid@yahoo.com)

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.

*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <time.h>
#include <math.h>
#include "search.h"
#include "matesearch.h"
#include "io.h"
#include "movegeneration.h"
#include "hash.h"
#include "evaluation.h"
#include "book.h"
#include "coordination.h"

#ifdef INCLUDE_TABLEBASE_ACCESS
#include "tablebase.h"
#endif

/* #define DEBUG_THREAD_COORDINATION */
/* #define CRV_CHECK */
#define QUIESCENCE_FUTILITY_CUT /* */
/* #define FUTILITY_CUTOFF_VALUE */
#define EXTEND_PIECE_SWAP       /* */
#define AGRESSIVE_HISTORY_PRUNING       /* */
#define EXTEND_ON_THREATS       /* */
#define PASSIVE_DEFENCE_MOVES   /* */
#define EXTEND_CONNECTED_MOVES  /* */
#define STATIC_NULLMOVE_CUTS    /* */
#define NULLMOVE_EXTRA_REDUCTION        /* */
#define TEST_FOREIGN_KILLERS    /* */
#define SINGLE_MOVE_EXTENSION   /* */
/* #define HASHTABLE_IN_QS */

extern bool resetGlobalHashtable;
const int FAIL_LOW_MARGIN = 50; /* was 20 */
int THREAT_LIMIT = DEFAULT_THREAT_LIMIT;
const int HASH_DEPTH_OFFSET = 3;

Move crv[MAX_DEPTH];
UINT64 crvHash;
INT32 checkTimeCount = 0;

int quietMoveCountLimit[32];    /* number of quiet moves to be examined @ specific restDepth */
int quietPvMoveReduction[64][64];       /* [restDepth][moveCount] */
int quietMoveReduction[64][64]; /* [restDepth][moveCount] */
int futilityMargin[16][64];     /* [restDepth][moveCount] */

static int searchBest(Variation * variation, int alpha, int beta,
                      const int ply, const int restDepth, const bool pvNode,
                      const bool reduction, PrincipalVariation * pv,
                      Move excludeMove);

INLINE static void checkTime(Variation * variation)
{
   variation->timestamp = getTimestamp();

   if (variation->timeLimit != 0 &&
       variation->timestamp - variation->startTime >= variation->timeLimit &&
       variation->searchStatus == SEARCH_STATUS_RUNNING &&
       variation->ponderMode == FALSE)
   {
      variation->searchStatus = SEARCH_STATUS_TERMINATE;

#ifdef DEBUG_THREAD_COORDINATION
      logDebug
         ("Time limit reached (time=%lu ms, limit=%lu ms)).\n",
          variation->timestamp - variation->startTime, variation->timeLimit);
#endif
   }

   if ((checkTimeCount++ % 10) == 0 && variation->handleSearchEvent != 0)
   {
      variation->handleSearchEvent(SEARCHEVENT_STATISTICS_UPDATE, variation);
   }
}

INLINE static void initPlyInfo(PlyInfo * info)
{
   info->quietMove = FALSE;
   info->staticValueAvailable = FALSE;
}

INLINE static bool hasDangerousPawns(const Position * position,
                                     const Color color)
{
   if (color == WHITE)
   {
      return (bool)
         ((position->piecesOfType[WHITE_PAWN] & squaresOfRank[RANK_7]) !=
          EMPTY_BITBOARD);
   }
   else
   {
      return (bool)
         ((position->piecesOfType[BLACK_PAWN] & squaresOfRank[RANK_2]) !=
          EMPTY_BITBOARD);
   }
}

static INLINE int getStaticValue(Variation * variation, const int ply)
{
   PlyInfo *pi = &variation->plyInfo[ply];

   if (pi->staticValueAvailable == FALSE)
   {
      EvaluationBase base;

      pi->staticValue =
         getValue(&variation->singlePosition, &base, variation->pawnHashtable,
                  variation->kingsafetyHashtable);
      pi->staticValueAvailable = TRUE;
   }

   return pi->staticValue;
}

static int searchBestQuiescence(Variation * variation, int alpha, int beta,
                                const int ply, const int restDepth,
                                const bool pvNode, PrincipalVariation * pv)
{
#ifdef HASHTABLE_IN_QS
   const int oldAlpha = alpha;
   Hashentry *tableHit = NULL;
   UINT8 hashentryFlag;
   UINT8 hashDepth = (restDepth >= 0 ? 2 : 1);
#endif
   Position *position = &variation->singlePosition;
   int best = VALUE_MATED, currentValue = VALUE_MATED, historyLimit, i;
   const int VALUE_MATE_HERE = -VALUE_MATED - ply + 1;
   const int VALUE_MATED_HERE = VALUE_MATED + ply;
   Movelist movelist;
   Move currentMove, bestMove = NO_MOVE, hashmove = NO_MOVE;
   const bool inCheck = variation->plyInfo[ply - 1].currentMoveIsCheck;
   PrincipalVariation newPv;
   EvaluationBase base;

   assert(alpha >= VALUE_MATED && alpha <= -VALUE_MATED);
   assert(beta >= VALUE_MATED && beta <= -VALUE_MATED);
   assert(alpha < beta);
   assert(ply > 0 && ply < MAX_DEPTH);
   assert(restDepth < DEPTH_RESOLUTION);
   assert(passiveKingIsSafe(position));
   assert((inCheck != FALSE) == (activeKingIsSafe(position) == FALSE));

   initPlyInfo(&variation->plyInfo[ply]);
   movelist.positionalGain = &(variation->positionalGain[0]);

   base.futilityMargin[WHITE] = base.futilityMargin[BLACK] = 0;
   newPv.length = pv->length = 0;
   variation->nodes++;

   if (variation->nodes == (variation->nodes & ~((UINT64) 0xFFFF)))
   {
      checkTime(variation);
   }

   if (variation->terminate &&
       movesAreEqual(variation->bestBaseMove, NO_MOVE) == FALSE)
   {
      variation->searchStatus = SEARCH_STATUS_TERMINATE;
   }

   if (variation->searchStatus != SEARCH_STATUS_RUNNING &&
       variation->nominalDepth > 1)
   {
      return 0;
   }

   /* Check for a draw according to the 50-move-rule */
   /* ---------------------------------------------- */
   if (position->halfMoveClock > 100)
   {
      return variation->drawScore[position->activeColor];
   }

   /* Check for a draw by repetition. */
   /* ------------------------------- */
   historyLimit = POSITION_HISTORY_OFFSET + variation->ply -
      position->halfMoveClock;

   assert(historyLimit >= 0);

   for (i = POSITION_HISTORY_OFFSET + variation->ply - 4;
        i >= historyLimit; i -= 2)
   {
      if (position->hashValue == variation->positionHistory[i])
      {
         return variation->drawScore[position->activeColor];
      }
   }

#ifdef HASHTABLE_IN_QS
   /* Probe the transposition table */
   /* ----------------------------- */
   tableHit = getDatedEntry(variation->hashtable,
                            variation->singlePosition.hashValue);

   if (tableHit != NULL)
   {                            /* 45% */
      const int importance =
         getHashentryImportance(tableHit) - HASH_DEPTH_OFFSET;
      const int value = getHashentryValue(tableHit);
      const int hashValue = calcEffectiveValue(value, ply);
      const int flag = getHashentryFlag(tableHit);

      hashmove = (Move) getHashentryMove(tableHit);

      if (hashmove != NO_MOVE)
      {                         /* 81% */
         assert(moveIsPseudoLegal(position, hashmove));

         if (moveIsPseudoLegal(position, hashmove))
         {
            assert(moveIsLegal(position, hashmove));

            if (variation->handleSearchEvent != 0)
            {
               appendMoveToPv(&newPv, pv, hashmove);
            }
         }
         else
         {
            hashmove = NO_MOVE;
         }
      }

      if (flag == HASHVALUE_EVAL)
      {
         PlyInfo *pi = &variation->plyInfo[variation->ply];

         pi->staticValue = hashValue;
         pi->staticValueAvailable = TRUE;
         base.futilityMargin[WHITE] = base.futilityMargin[BLACK] = 500;
      }
      else if (pvNode == FALSE && restDepth <= importance * DEPTH_RESOLUTION)
      {                         /* 99% */
         assert(flag == HASHVALUE_UPPER_LIMIT || flag == HASHVALUE_EXACT ||
                flag == HASHVALUE_LOWER_LIMIT);
         assert(hashValue >= VALUE_MATED && hashValue < -VALUE_MATED);

         switch (flag)
         {
         case HASHVALUE_UPPER_LIMIT:
            if (hashValue <= alpha)
            {
               return (hashValue <= VALUE_ALMOST_MATED ? alpha : hashValue);
            }
            break;

         case HASHVALUE_EXACT:
            return hashValue;

         case HASHVALUE_LOWER_LIMIT:
            if (hashValue >= beta)
            {
               return (hashValue >= -VALUE_ALMOST_MATED ? beta : hashValue);
            }
            break;

         default:;
         }
      }
   }
#endif

   if (inCheck == FALSE)
   {
      assert(flipTest(position,
                      variation->pawnHashtable,
                      variation->kingsafetyHashtable) != FALSE);

      if (variation->plyInfo[ply].staticValueAvailable == FALSE)
      {
         best = getValue(position,
                         &base,
                         variation->pawnHashtable,
                         variation->kingsafetyHashtable);
         variation->plyInfo[ply].staticValue = best;
         variation->plyInfo[ply].staticValueAvailable = TRUE;
      }
      else
      {
         best = variation->plyInfo[ply].staticValue;
      }

      if (best > alpha)
      {
         alpha = best;

         if (best >= beta)
         {
#ifdef HASHTABLE_IN_QS
            setDatedEntry(variation->hashtable, position->hashValue,
                          calcHashtableValue(best, ply),
                          0, packedMove(NO_MOVE), HASHVALUE_EVAL);
#endif

            return best;
         }
      }

      currentValue = best;
   }

   if (ply >= MAX_DEPTH)
   {
      assert(flipTest(position,
                      variation->pawnHashtable,
                      variation->kingsafetyHashtable) != FALSE);

      return getStaticValue(variation, ply);
   }

   if (alpha < VALUE_MATED_HERE && inCheck == FALSE)
   {
      alpha = VALUE_MATED_HERE;

      if (alpha >= beta)
      {
         return VALUE_MATED_HERE;
      }
   }

   if (beta > VALUE_MATE_HERE)
   {
      beta = VALUE_MATE_HERE;

      if (beta <= alpha)
      {
         return VALUE_MATE_HERE;
      }
   }

   initQuiescenceMovelist(&movelist, &variation->singlePosition,
                          &variation->plyInfo[ply],
                          &variation->historyValue[0],
                          (inCheck ? hashmove : NO_MOVE), restDepth, inCheck);
   initializePlyInfo(variation);

   while ((currentMove = getNextMove(&movelist)) != NO_MOVE)
   {
      int value, newDepth =
         (inCheck ? restDepth : restDepth - DEPTH_RESOLUTION);

#ifdef QUIESCENCE_FUTILITY_CUT
      const int delta = 50 + base.futilityMargin[position->activeColor];
      int optValue = currentValue + delta +
         basicValue[position->piece[getToSquare(currentMove)]];

      if (pvNode == FALSE && inCheck == FALSE && optValue < alpha &&
          pieceType(position->piece[getToSquare(currentMove)]) != QUEEN &&
          getNewPiece(currentMove) != QUEEN &&
          (pieceType(position->piece[getFromSquare(currentMove)]) != PAWN ||
           colorRank(position->activeColor,
                     getToSquare(currentMove)) != RANK_7))
      {
         if (getNewPiece(currentMove) != NO_PIECE)
         {
            optValue +=
               basicValue[getNewPiece(currentMove)] - basicValue[PAWN];
         }

         if (getToSquare(currentMove) == position->enPassantSquare &&
             pieceType(position->piece[getFromSquare(currentMove)]) == PAWN)
         {
            optValue += basicValue[PAWN];
         }

         if (optValue < alpha && moveIsCheck(currentMove, position) == FALSE)
         {
            best = max(best, optValue);

            continue;
         }
      }
#endif

      assert(moveIsPseudoLegal(position, currentMove));

      if (makeMoveFast(variation, currentMove) != 0 ||
          passiveKingIsSafe(&variation->singlePosition) == FALSE)
      {
         unmakeLastMove(variation);

         continue;
      }

      variation->plyInfo[ply].currentMoveIsCheck =
         activeKingIsSafe(&variation->singlePosition) == FALSE;

      assert(position->piece[getToSquare(currentMove)] != NO_PIECE ||
             (getToSquare(currentMove) == position->enPassantSquare &&
              position->piece[getFromSquare(currentMove)] ==
              (PAWN | position->activeColor)) ||
             getNewPiece(currentMove) != NO_PIECE ||
             inCheck || variation->plyInfo[ply].currentMoveIsCheck);

      assert(inCheck != FALSE ||
             basicValue[position->piece[getFromSquare(currentMove)]] <=
             basicValue[position->piece[getToSquare(currentMove)]] ||
             seeMove(position, currentMove) >= 0);

      value = -searchBestQuiescence(variation, -beta, -alpha, ply + 1,
                                    newDepth, pvNode, &newPv);

      unmakeLastMove(variation);

      if (variation->searchStatus != SEARCH_STATUS_RUNNING &&
          variation->nominalDepth > 1)
      {
         return 0;
      }

      if (value > best)
      {
         best = value;
         bestMove = currentMove;

         if (variation->handleSearchEvent != 0)
         {
            appendMoveToPv(&newPv, pv, currentMove);
         }

         if (best > alpha)
         {
            alpha = best;

            if (best >= beta)
            {
               break;
            }
         }
      }
   }

   if (best == VALUE_MATED)
   {
      /* mate */

      assert(inCheck != FALSE);

      best = VALUE_MATED + ply;
   }

#ifdef HASHTABLE_IN_QS
   /* Store the value in the transposition table. */
   /* ------------------------------------------- */
   if (best > oldAlpha)
   {
      hashentryFlag =
         (best >= beta ? HASHVALUE_LOWER_LIMIT : HASHVALUE_EXACT);
   }
   else
   {
      hashentryFlag =
         (inCheck == FALSE && best == getStaticValue(variation, ply) ?
          HASHVALUE_EVAL : HASHVALUE_UPPER_LIMIT);
   }

   setDatedEntry(variation->hashtable, position->hashValue,
                 calcHashtableValue(best, ply),
                 hashDepth, packedMove(bestMove), hashentryFlag);
#endif

   return best;
}

INLINE static bool moveIsQuiet(const Move move, const Position * position)
{
   return (bool) (position->piece[getToSquare(move)] == NO_PIECE &&
                  getNewPiece(move) == NO_PIECE &&
                  (getToSquare(move) != position->enPassantSquare ||
                   pieceType(position->piece[getFromSquare(move)]) != PAWN));
}

INLINE static bool moveIsCastling(const Move move, const Position * position)
{
   return (bool) (pieceType(position->piece[getFromSquare(move)]) == KING &&
                  distance(getFromSquare(move), getToSquare(move)) == 2);
}

INLINE static bool moveAttacksSquare(const Move move, const Square square,
                                     const Position * position)
{
   const Piece piece = position->piece[getFromSquare(move)];
   Bitboard orginalMoves =
      getCaptureMoves(getFromSquare(move), piece, position->allPieces);
   Bitboard movesFromTarget =
      getCaptureMoves(getToSquare(move), piece, position->allPieces);

   return testSquare(orginalMoves, square) == FALSE &&
      testSquare(movesFromTarget, square);
}

INLINE static bool movesAreConnected(const Move firstMove,
                                     const Move secondMove,
                                     Position * position)
{
   const Square firstFrom = getFromSquare(firstMove);
   const Square firstTo = getToSquare(firstMove);
   const Square secondFrom = getFromSquare(secondMove);
   const Square secondTo = getToSquare(secondMove);
   const Piece firstPiece = position->piece[firstTo];
   const Piece secondPiece = position->piece[secondFrom];
   const bool firstPieceIsSlider =
      (bool) (firstPiece & PP_SLIDING_PIECE) != 0;
   const bool secondPieceIsSlider =
      (bool) (secondPiece & PP_SLIDING_PIECE) != 0;

   if (firstTo == secondFrom)
   {
      assert(firstPieceIsSlider == secondPieceIsSlider);

      if (secondTo == firstFrom)
      {
         return FALSE;          /* avoid shuffling */
      }

      if (firstPieceIsSlider)
      {
         const Bitboard backyards = squaresBehind[firstTo][firstFrom] |
            squaresBehind[firstFrom][secondFrom];

         return (testSquare(backyards, secondTo) == FALSE);     /* slider changes direction */
      }
      else
      {
         return (bool) distance(firstFrom, secondTo) >= 2;
      }
   }

   if (secondPieceIsSlider)
   {
      const Bitboard corridor = squaresBetween[secondFrom][secondTo];

      if (testSquare(corridor, firstFrom))
      {
         return TRUE;           /* first move was clearing square */
      }
   }

   if (secondTo == firstFrom)
   {
      return TRUE;              /* first move was clearing square */
   }

   if (firstPieceIsSlider)
   {
      const Square oppKingSquare = position->king[position->activeColor];
      const Bitboard corridor = squaresBetween[firstTo][oppKingSquare];

      if (testSquare(corridor, secondFrom) &&
          (corridor & position->allPieces) == minValue[secondFrom])
      {
         return TRUE;           /* uncovered check */
      }
   }

   return FALSE;
}

INLINE static bool moveIsDefence(const Move move, const Move threatMove,
                                 Position * position)
{
   const Square threatTarget = getToSquare(threatMove);
   const Square threatFromSquare = getFromSquare(threatMove);
   const Square fromSquare = getFromSquare(move);

   if (fromSquare == threatTarget && seeMove(position, move) >= 0)
   {
      return TRUE;              /* threatened piece was moved */
   }
#ifdef PASSIVE_DEFENCE_MOVES
   else if (basicValue[position->piece[threatFromSquare]] >=
            basicValue[position->piece[fromSquare]] &&
            (position->piece[threatFromSquare] & PP_SLIDING_PIECE) != 0 &&
            distance(threatFromSquare, threatTarget) > 1)
   {
      Bitboard sliderCorridor =
         squaresBetween[threatFromSquare][threatTarget];

      assert(pieceType(position->piece[threatFromSquare]) == QUEEN ||
             pieceType(position->piece[threatFromSquare]) == ROOK ||
             pieceType(position->piece[threatFromSquare]) == BISHOP);
      assert(sliderCorridor != EMPTY_BITBOARD);

      if (testSquare(sliderCorridor, getToSquare(move)) &&
          seeMove(position, move) >= 0)
      {
         return TRUE;           /* move blocks slider */
      }
   }

   if (basicValue[position->piece[threatTarget]] > 0 &&
       basicValue[position->piece[threatFromSquare]] >=
       basicValue[position->piece[threatTarget]])
   {
      if (moveAttacksSquare(move, threatTarget, position) &&
          seeMove(position, move) >= 0)
      {
         return TRUE;           /* move defends target */
      }
   }
#endif

   return FALSE;
}

static INLINE bool isPassedPawnMove(const Square pawnSquare,
                                    const Square targetSquare,
                                    const Position * position)
{
   const Piece piece = position->piece[pawnSquare];

   if (pieceType(piece) == PAWN)
   {
      return pawnIsPassed(position, targetSquare, pieceColor(piece));
   }
   else
   {
      return FALSE;
   }
}

#ifdef FUTILITY_CUTOFF_VALUE
static INLINE int getFutilityMargin(const int restDepth, const int moveCount)
{
   return (restDepth < 16 ? futilityMargin[restDepth][min(63, moveCount)] :
           -VALUE_MATED);
}
#endif

static int searchBest(Variation * variation, int alpha, int beta,
                      const int ply, const int restDepth, const bool pvNode,
                      const bool reduction, PrincipalVariation * pv,
                      Move excludeMove)
{
   const int oldAlpha = alpha;
   Position *position = &variation->singlePosition;
   int best = VALUE_MATED;
   const int VALUE_MATE_HERE = -VALUE_MATED - ply + 1;
   const int VALUE_MATED_HERE = VALUE_MATED + ply;
   Movelist movelist;
   Hashentry *tableHit = NULL;
   UINT8 hashentryFlag;
   int i, historyLimit, numMovesPlayed = 0, numQuietMoves = 0;
   Move hashmove = NO_MOVE, bestMove = NO_MOVE, threatMove = NO_MOVE;
   Move currentMove;
   Move lastMove = variation->plyInfo[ply - 1].currentMove;
   const bool inCheck = variation->plyInfo[ply - 1].currentMoveIsCheck;
   PrincipalVariation newPv;
   int historyIndexPlayed[MAX_MOVES_PER_POSITION];
   const bool dangerousPawns =
      hasDangerousPawns(position, position->activeColor);
   const int rdBasic = restDepth / DEPTH_RESOLUTION;
   bool singularExtensionNode = FALSE;
   int tableIndex = 0, hashEntryValue = 0, hashMoveDepth = 0;
   const bool extensionsAllowed = (bool)
      (ply <= min(32, variation->nominalDepth));

   initPlyInfo(&variation->plyInfo[ply]);
   movelist.positionalGain = &(variation->positionalGain[0]);

#ifdef FUTILITY_CUTOFF_VALUE
   if (variation->plyInfo[ply - 1].quietMove)
   {
      const int moveIndex = variation->plyInfo[ply - 1].indexCurrentMove;
      INT16 *storedGain = &variation->positionalGain[moveIndex];
      const INT16 currentDiff = (INT16)
         (getStaticValue(variation, ply) +
          variation->plyInfo[ply - 1].staticValue);

#ifdef VALUE_BASED_MOVESORT
      if (currentDiff > *storedGain && currentDiff <= MAX_GAIN)
      {
         *storedGain = currentDiff;
      }
      else if (*storedGain > -MAX_GAIN)
      {
         *storedGain--;
      }

      assert(abs(*storedGain) <= MAX_GAIN);
#else
      if (currentDiff > *storedGain)
      {
         *storedGain = currentDiff;
      }
      else
      {
         *storedGain--;
      }
#endif
   }
#endif

#ifdef CRV_CHECK
   bool crvFail = FALSE;

   for (i = 0; crv[i] != NO_MOVE; i++)
   {
      if (movesAreEqual(variation->plyInfo[i].currentMove, crv[i]) == FALSE)
      {
         crvFail = TRUE;
         break;
      }
   }

   if (crvFail == FALSE && i != ply)
   {
      crvFail = TRUE;
   }
#endif /* CRV_CHECK */

   if (ply + 1 > variation->selDepth)
   {
      variation->selDepth = ply + 1;
   }

   assert(alpha >= VALUE_MATED && alpha <= -VALUE_MATED);
   assert(beta >= VALUE_MATED && beta <= -VALUE_MATED);
   assert(alpha < beta);
   assert(ply > 0 && ply < MAX_DEPTH);
   assert(restDepth >= -3 * DEPTH_RESOLUTION);
   assert(passiveKingIsSafe(position));
   assert((inCheck != FALSE) == (activeKingIsSafe(position) == FALSE));

   newPv.length = pv->length = 0;
   newPv.move[0] = (UINT16) NO_MOVE;

   if (restDepth < DEPTH_RESOLUTION)
   {                            /* 63% */
      assert(excludeMove == NO_MOVE);

      return searchBestQuiescence(variation, alpha, beta, ply, 0, pvNode, pv);
   }

   variation->nodes++;

   if (variation->nodes == (variation->nodes & ~((UINT64) 0xFFFF)))
   {
      checkTime(variation);
   }

   if (variation->terminate &&
       movesAreEqual(variation->bestBaseMove, NO_MOVE) == FALSE)
   {
      variation->searchStatus = SEARCH_STATUS_TERMINATE;
   }

   if (variation->searchStatus != SEARCH_STATUS_RUNNING &&
       variation->nominalDepth > 1)
   {
      return 0;
   }

   /* Check for a draw according to the 50-move-rule */
   /* ---------------------------------------------- */
   if (position->halfMoveClock > 100)
   {
      return variation->drawScore[position->activeColor];
   }

   /* Check for a draw by repetition. */
   /* ------------------------------- */
   historyLimit = POSITION_HISTORY_OFFSET + variation->ply -
      position->halfMoveClock;

   assert(historyLimit >= 0);

   for (i = POSITION_HISTORY_OFFSET + variation->ply - 4;
        i >= historyLimit; i -= 2)
   {
      if (position->hashValue == variation->positionHistory[i])
      {
         return variation->drawScore[position->activeColor];
      }
   }

#ifdef INCLUDE_TABLEBASE_ACCESS
   /* Probe the tablebases in case of reduced material */
   /* ------------------------------------------------ */
   if (ply >= 2 && (pvNode || restDepth >= 6 * DEPTH_RESOLUTION) &&
       position->numberOfPieces[WHITE] +
       position->numberOfPieces[BLACK] <= 5 &&
       excludeMove == NO_MOVE && tbAvailable != FALSE)
   {
      int tbValue;

      tbValue = probeTablebase(position);

      if (tbValue != TABLEBASE_ERROR)
      {
         variation->tbHits++;

         if (tbValue == 0)
         {
            return variation->drawScore[position->activeColor];
         }

         return (tbValue > 0 ? tbValue - ply : tbValue + ply);
      }
   }
#endif

   if (ply >= 2 && rdBasic >= 4 && kpkpValueAvailable(position) &&
       getStaticValue(variation, ply) == 0 && excludeMove == NO_MOVE)
   {
      return 0;
   }

   /* Probe the transposition table */
   /* ----------------------------- */
   if (excludeMove == NO_MOVE || excludeMove == NULLMOVE)
   {
      do
      {
         tableHit = getIndexedDatedEntry(variation->hashtable,
                                         variation->singlePosition.hashValue,
                                         &tableIndex);

         if (tableHit != NULL)
         {                      /* 45% */
            const int importance =
               getHashentryImportance(tableHit) - HASH_DEPTH_OFFSET;

#ifdef SINGLE_MOVE_EXTENSION
            const int singleMoveExtensionDepth =
               (pvNode ? 6 : 8) * DEPTH_RESOLUTION;
#endif

            if (hashmove == NO_MOVE || importance > hashMoveDepth)
            {
               hashmove = (Move) getHashentryMove(tableHit);
               hashMoveDepth = importance;
            }

            hashEntryValue =
               calcEffectiveValue(getHashentryValue(tableHit), ply);

            if (hashmove != NO_MOVE)
            {                   /* 81% */
               assert(moveIsPseudoLegal(position, hashmove));

               if (moveIsPseudoLegal(position, hashmove))
               {
                  assert(moveIsLegal(position, hashmove));

                  if (variation->handleSearchEvent != 0)
                  {
                     appendMoveToPv(&newPv, pv, hashmove);
                  }
               }
               else
               {
                  hashmove = NO_MOVE;
               }
            }

            if (pvNode == FALSE && excludeMove != NULLMOVE &&
                restDepth <= importance * DEPTH_RESOLUTION)
            {                   /* 99% */
               const int hashValue = hashEntryValue;
               const int flag = getHashentryFlag(tableHit);

               assert(flag == HASHVALUE_UPPER_LIMIT ||
                      flag == HASHVALUE_EXACT ||
                      flag == HASHVALUE_LOWER_LIMIT);
               assert(hashValue >= VALUE_MATED && hashValue < -VALUE_MATED);

               switch (flag)
               {
               case HASHVALUE_UPPER_LIMIT:
                  if (hashValue <= alpha)
                  {
                     return (hashValue <= VALUE_ALMOST_MATED ?
                             alpha : hashValue);
                  }
                  break;

               case HASHVALUE_EXACT:
                  return hashValue;

               case HASHVALUE_LOWER_LIMIT:
                  if (hashValue >= beta)
                  {
                     return (hashValue >= -VALUE_ALMOST_MATED ?
                             beta : hashValue);
                  }
                  break;

               default:;
               }
            }

#ifdef SINGLE_MOVE_EXTENSION
            if (restDepth >= singleMoveExtensionDepth &&
                excludeMove == NO_MOVE && hashmove != NO_MOVE &&
                tableHit != NULL &&
                getHashentryFlag(tableHit) == HASHVALUE_LOWER_LIMIT &&
                /* abs(getHashentryValue(tableHit)) <=
                   2 * DEFAULTVALUE_QUEEN_OPENING && */
                importance * DEPTH_RESOLUTION >=
                restDepth - 3 * DEPTH_RESOLUTION)
            {
               singularExtensionNode = TRUE;
            }
#endif
         }
      }
      while (tableIndex < 4);
   }

   if (ply >= MAX_DEPTH)
   {
      return getStaticValue(variation, ply);
   }

   if (alpha < VALUE_MATED_HERE && inCheck == FALSE)
   {
      alpha = VALUE_MATED_HERE;

      if (alpha >= beta)
      {
         return VALUE_MATED_HERE;
      }
   }

   if (beta > VALUE_MATE_HERE)
   {
      beta = VALUE_MATE_HERE;

      if (beta <= alpha)
      {
         return VALUE_MATE_HERE;
      }
   }

   initializePlyInfo(variation);

/* Razoring */
   if (pvNode == FALSE && rdBasic <= 3 && lastMove != NULLMOVE &&
       inCheck == FALSE && hashmove == NO_MOVE && excludeMove == NO_MOVE &&
       alpha > VALUE_ALMOST_MATED && beta < -(VALUE_ALMOST_MATED) &&
       dangerousPawns == FALSE)
   {
      const static int delta[4] = { 0, 200, 225, 250 };
      const int limit = alpha - delta[rdBasic];

      if (getStaticValue(variation, ply) < limit)
      {
         const int qsValue =
            searchBestQuiescence(variation, limit - 1, limit, ply, 0,
                                 pvNode, pv);

         if (qsValue < limit)
         {
            return qsValue;
         }
      }
   }

#ifdef STATIC_NULLMOVE_CUTS
   if (pvNode == FALSE && restDepth < 4 * DEPTH_RESOLUTION &&
       inCheck == FALSE && alpha > VALUE_ALMOST_MATED &&
       beta < -(VALUE_ALMOST_MATED) && excludeMove == NO_MOVE &&
       numberOfNonPawnPieces(position, position->activeColor) >= 2)
   {
      const int limit = beta + 70 + 10 * restDepth;

      if (getStaticValue(variation, ply) > limit)
      {
         return getStaticValue(variation, ply);
      }
   }
#endif

   if (restDepth >= 2 * DEPTH_RESOLUTION && inCheck == FALSE &&
       pvNode == FALSE && alpha > VALUE_MATED && excludeMove == NO_MOVE &&
       numberOfNonPawnPieces(position, position->activeColor) >= 2 &&
       getNumberOfPieceMoves(position, position->activeColor, 6) >= 6 &&
       getStaticValue(variation, ply) >= beta - THREAT_LIMIT)
   {                            /* 16-32% */
      const int verificationReduction = 5 * DEPTH_RESOLUTION;
      int newDepth = restDepth - 3 * DEPTH_RESOLUTION;
      int nullValue;

#ifdef NULLMOVE_EXTRA_REDUCTION
      if (newDepth >= 4 * DEPTH_RESOLUTION &&
          getStaticValue(variation, ply) > beta + PAWN_VALUE_ENDGAME)
      {
         newDepth -= DEPTH_RESOLUTION;
      }

      if (restDepth >= verificationReduction)
      {
         newDepth -= (restDepth / 8) * DEPTH_RESOLUTION;
      }
#endif

      assert(flipTest(position,
                      variation->pawnHashtable,
                      variation->kingsafetyHashtable) != FALSE);

      makeMoveFast(variation, NULLMOVE);
      variation->plyInfo[ply].currentMoveIsCheck = FALSE;
      nullValue = -searchBest(variation, -beta, -beta + 1, ply + 1,
                              newDepth, pvNode, FALSE, &newPv, NO_MOVE);
      unmakeLastMove(variation);
      threatMove = (Move) newPv.move[0];

      if (restDepth - verificationReduction >= DEPTH_RESOLUTION &&
          nullValue >= beta)
      {                         /* 2% */
         const int noNullValue = searchBest(variation, alpha, beta, ply,
                                            restDepth - verificationReduction,
                                            FALSE, FALSE, &newPv, NULLMOVE);

         if (noNullValue >= beta)
         {                      /* 99% */
            return nullValue;
         }
      }
      else if (nullValue >= beta)
      {                         /* 70% */
         return min(nullValue, VALUE_MATE_HERE);
      }
#ifdef EXTEND_CONNECTED_MOVES
      else if (reduction && restDepth >= 5 * DEPTH_RESOLUTION &&
               threatMove != NO_MOVE &&
               movesAreConnected(lastMove, threatMove, position))
#else
      else if (reduction && restDepth >= 5 * DEPTH_RESOLUTION &&
               nullValue < beta - THREAT_LIMIT)
#endif
      {
         return beta - 1;
      }
   }

   /* Internal iterative deepening. */
   /* ----------------------------- */
   if (hashmove == NO_MOVE &&
       restDepth >= (pvNode ? 3 : 7) * DEPTH_RESOLUTION &&
       (pvNode ||
        (inCheck == FALSE && getStaticValue(variation, ply) >= beta - 100)))
   {
      const Move excludeHere =
         (excludeMove != NO_MOVE ? excludeMove : NULLMOVE);
      const int searchDepth =
         (pvNode ? restDepth - 2 * DEPTH_RESOLUTION : restDepth / 2);
      /* const int value = */

      searchBest(variation, alpha, beta, ply, searchDepth, pvNode,
                 FALSE, &newPv, excludeHere);

      /*
         if (value <= alpha)
         {
         searchBest(variation, VALUE_MATED, beta, ply, searchDepth, pvNode,
         FALSE, &newPv, excludeHere);

         }
       */

      if (newPv.length > 0 &&
          moveIsPseudoLegal(position, (Move) newPv.move[0]))
      {
         hashmove = (Move) newPv.move[0];
      }
   }

#ifdef TEST_FOREIGN_KILLERS
   if (ply >= 2)
   {
      variation->plyInfo[ply].killerMove3 =
         variation->plyInfo[ply - 2].killerMove1;
      variation->plyInfo[ply].killerMove4 =
         variation->plyInfo[ply - 2].killerMove2;
   }
   else
   {
#endif
      variation->plyInfo[ply].killerMove3 = NO_MOVE;
      variation->plyInfo[ply].killerMove4 = NO_MOVE;
#ifdef TEST_FOREIGN_KILLERS
   }
#endif

   initStandardMovelist(&movelist, &variation->singlePosition,
                        &variation->plyInfo[ply],
                        &variation->historyValue[0], hashmove, inCheck);

#ifdef FUTILITY_CUTOFF_VALUE
   getStaticValue(variation, ply);
#endif

   /* Loop through all moves in this node. */
   /* ------------------------------------ */
   while ((currentMove = getNextMove(&movelist)) != NO_MOVE)
   {
      const int historyIdx = historyIndex(currentMove, position);
      const int stage = moveGenerationStage[movelist.currentStage];
      int value, newDepth;
      int extension = 0, reduction = 0;
      bool check;
      const bool quietMove = moveIsQuiet(currentMove, position);
      const Square toSquare = getToSquare(currentMove);
      const bool capture = (bool) (position->piece[toSquare] != NO_PIECE);
      const bool pieceCapture = (bool)
         (capture && pieceType(position->piece[toSquare]) != PAWN);
      const bool recapture = (bool)
         (toSquare == getToSquare(lastMove) && capture &&
          (variation->plyInfo[ply - 1].captured != NO_PIECE ||
           (pieceType(position->piece[toSquare]) == PAWN &&
            variation->plyInfo[ply - 1].enPassantSquare == toSquare)));
      const bool pieceRecapture = (bool)
         (recapture && pieceCapture &&
          pieceType(variation->plyInfo[ply - 1].captured) != PAWN &&
          variation->plyInfo[ply - 1].captured != NO_PIECE);
      const bool hashMoveNode = movesAreEqual(currentMove, hashmove);

      if (excludeMove != NO_MOVE && movesAreEqual(currentMove, excludeMove))
      {
         assert(excludeMove != NULLMOVE);

         continue;              /* exclude excludeMove */
      }

#ifdef EXTEND_ON_THREATS
      variation->plyInfo[ply].indexCurrentMove = historyIdx;
      variation->plyInfo[ply].quietMove = quietMove;
#endif

      assert(moveIsPseudoLegal(position, currentMove));
      assert(hashmove == NO_MOVE || numMovesPlayed > 0 ||
             movesAreEqual(currentMove, hashmove));

      if (pvNode == FALSE && inCheck == FALSE &&
          quietMove != FALSE && dangerousPawns == FALSE &&
          numMovesPlayed >= 3 && excludeMove != NULLMOVE &&
          !isPassedPawnMove(getFromSquare(currentMove), toSquare, position) &&
          !moveIsCastling(currentMove, position) && best > VALUE_ALMOST_MATED)
      {
         const int rdIndex = min(31, restDepth);
         bool skip = (bool) (numMovesPlayed > quietMoveCountLimit[rdIndex]);

         if (skip == FALSE &&
             restDepth <= 6 * DEPTH_RESOLUTION &&
             numMovesPlayed >= rdBasic + (rdBasic & 1))
         {
            const int depthDivisor = (rdBasic + 1) / 2;
            const int limit = 70 / depthDivisor;
            const int historyValue =
               (variation->historyHitCount[historyIdx] * 100) /
               variation->historyTotalCount[historyIdx];

            skip = (bool) (historyValue < limit);
         }

         if (skip &&
             simpleMoveIsCheck(position, currentMove) == FALSE &&
             (threatMove == NO_MOVE ||
              moveIsDefence(currentMove, threatMove, position) == FALSE))
         {
            continue;
         }

#ifdef FUTILITY_CUTOFF_VALUE
         if (restDepth < 9 * DEPTH_RESOLUTION)
         {
            const int futLimit =
               getStaticValue(variation, ply) +
               variation->positionalGain[historyIdx] +
               getFutilityMargin(restDepth, numMovesPlayed);

            if (futLimit < beta &&
                simpleMoveIsCheck(position, currentMove) == FALSE &&
                (threatMove == NO_MOVE ||
                 moveIsDefence(currentMove, threatMove, position) == FALSE))
            {
               if (futLimit > best)
               {
                  best = futLimit;
               }

               continue;
            }
         }
#endif
      }

      /* Execute the current move and check if it is legal. */
      /* -------------------------------------------------- */
      if (makeMoveFast(variation, currentMove) != 0 ||
          passiveKingIsSafe(&variation->singlePosition) == FALSE)
      {
         unmakeLastMove(variation);

         continue;
      }

      /* Check the conditions for search extensions and finally */
      /* calculate the rest depth for the next ply.             */
      /* ------------------------------------------------------ */
      variation->plyInfo[ply].currentMoveIsCheck = check =
         activeKingIsSafe(&variation->singlePosition) == FALSE;

      if (inCheck && movelist.numberOfMoves <= 2)
      {
         if (movelist.numberOfMoves <= 1)
         {
            extension = DEPTH_RESOLUTION;
         }
         else if (pvNode)
         {
            extension = DEPTH_RESOLUTION / 2;
         }
      }

      if (extension == 0 && pieceRecapture)
      {
         extension = DEPTH_RESOLUTION / 2;
      }

      if (check)
      {
         extension = DEPTH_RESOLUTION;
      }
      else if (pvNode)
      {
         const Color passiveColor = opponent(position->activeColor);

         if (pieceType(position->piece[toSquare]) == PAWN &&
             (colorRank(passiveColor, toSquare) >= RANK_6 ||
              pawnIsPassed(position, toSquare, passiveColor)))
         {
            extension = DEPTH_RESOLUTION;
         }
         else if (recapture)
         {
            extension = DEPTH_RESOLUTION;
         }
         else if (pieceCapture)
         {
            if (restDepth >= 6 * DEPTH_RESOLUTION)
            {
               extension = DEPTH_RESOLUTION;
            }
            else if (numberOfNonPawnPieces(position, WHITE) <= 2 &&
                     numberOfNonPawnPieces(position, WHITE) ==
                     numberOfNonPawnPieces(position, BLACK))
            {
               extension = DEPTH_RESOLUTION;
            }
         }
      }

      if (singularExtensionNode != FALSE &&
          extensionsAllowed && extension < DEPTH_RESOLUTION && hashMoveNode)
      {
         const int limitValue = hashEntryValue - 40;

         assert(excludeMove == NO_MOVE);

         if (limitValue > VALUE_MATED && limitValue <= -VALUE_MATED)
         {
            int excludeValue;
            PrincipalVariation tmpPv;

            tmpPv.length = 0;
            tmpPv.move[0] = (UINT16) NO_MOVE;

            unmakeLastMove(variation);
            excludeValue =
               searchBest(variation, limitValue - 1, limitValue, ply,
                          restDepth / 2, FALSE, FALSE, &tmpPv, hashmove);
            makeMoveFast(variation, currentMove);
            variation->plyInfo[ply].indexCurrentMove = historyIdx;
            variation->plyInfo[ply].quietMove = quietMove;
            variation->plyInfo[ply].currentMoveIsCheck = check;

            if (excludeValue < limitValue)
            {
               extension = DEPTH_RESOLUTION;
            }
         }
      }

      newDepth = restDepth - DEPTH_RESOLUTION +
         (excludeMove != NULLMOVE || check ? extension : 0);

      if (extensionsAllowed == FALSE)
      {
         newDepth = restDepth - DEPTH_RESOLUTION;
      }

      /* History pruning */
      /* --------------- */
      if (inCheck == FALSE && extension == 0 &&
          restDepth >= 3 * DEPTH_RESOLUTION && quietMove != FALSE &&
          stage != MGS_GOOD_CAPTURES_AND_PROMOTIONS &&
          stage != MGS_KILLER_MOVES && excludeMove != NULLMOVE &&
          isPassedPawnMove(toSquare, toSquare, position) == FALSE)
      {
         const int moveIndex = min(63, numMovesPlayed);
         const int depthIndex = min(63, rdBasic);

         reduction =
            (pvNode ? quietPvMoveReduction[depthIndex][moveIndex] :
             quietMoveReduction[depthIndex][moveIndex]);
      }

      /* Recursive search */
      /* ---------------- */
      if (pvNode == FALSE || best == VALUE_MATED)
      {
         value = -searchBest(variation, -beta, -alpha, ply + 1,
                             newDepth - reduction, pvNode,
                             (bool) reduction > 0, &newPv, NO_MOVE);

         if (reduction > 0 && value > alpha)
         {
            assert(excludeMove != NULLMOVE);

            value = -searchBest(variation, -beta, -alpha, ply + 1,
                                newDepth, pvNode, FALSE, &newPv, NO_MOVE);
         }
      }
      else                      /* pvNode == TRUE && best > VALUE_MATED */
      {
         value = -searchBest(variation, -alpha - 1, -alpha, ply + 1,
                             newDepth - reduction, FALSE,
                             (bool) reduction > 0, &newPv, NO_MOVE);

         if (reduction > 0 && value > alpha)
         {
            value = -searchBest(variation, -alpha - 1, -alpha, ply + 1,
                                newDepth, FALSE, FALSE, &newPv, NO_MOVE);
         }

         if (value > alpha /*&& value < beta */ )
         {                      /* 2% */
            value = -searchBest(variation, -beta, -alpha, ply + 1,
                                newDepth, TRUE, FALSE, &newPv, NO_MOVE);
         }
      }

      assert(value >= VALUE_MATED && value <= -VALUE_MATED);

      unmakeLastMove(variation);
      numMovesPlayed++;

      if (quietMove)
      {
         assert(numQuietMoves < MAX_MOVES_PER_POSITION);

         historyIndexPlayed[numQuietMoves++] = historyIdx;

         if (value <= best)
         {
            variation->historyValue[historyIdx] = (UINT16)
               (variation->historyValue[historyIdx] -
                (variation->historyValue[historyIdx] * restDepth) / 256);
            assert(variation->historyValue[historyIdx] <= HISTORY_MAX);
         }
      }

      if (variation->searchStatus != SEARCH_STATUS_RUNNING &&
          variation->nominalDepth > 1)
      {
         return 0;
      }

      /* Calculate the parameters controlling the search tree. */
      /* ----------------------------------------------------- */
      if (value > best)
      {                         /* 32% */
         best = value;

         if (variation->handleSearchEvent != 0)
         {
            appendMoveToPv(&newPv, pv, currentMove);
         }

         if (best > alpha)
         {                      /* 63% */
            alpha = best;
            bestMove = currentMove;

            if (best >= beta)
            {                   /* 99% */
               goto finish;
            }
         }
      }
   }

   /* No legal move was found. Check if it's mate or stalemate. */
   /* --------------------------------------------------------- */
   if (best == VALUE_MATED)
   {
      if (excludeMove != NO_MOVE && excludeMove != NULLMOVE)
      {
         return beta - 1;
      }

      if (inCheck)
      {
         /* mate */

         best = VALUE_MATED + ply;
      }
      else
      {
         /* stalemate */

         best = variation->drawScore[position->activeColor];
      }
   }

 finish:

#ifdef CRV_CHECK
   if (crvFail == FALSE)
   {
      logDebug
         ("\nbestValue=%d beta=%d, rd=%d extensions=%d pvNode=%d\nbest move: ",
          best, beta, restDepth, (ply + restDepth) - variation->nominalDepth,
          pvNode);
      dumpMove(bestMove);
      dumpVariation(variation);
   }
#endif /* CRV_CHECK */

   /* Calculate the parameters controlling the move ordering. */
   /* ------------------------------------------------------- */
   if (bestMove != NO_MOVE && moveIsQuiet(bestMove, position) &&
       (excludeMove == NO_MOVE || excludeMove == NULLMOVE))
   {
      Move killerMove = bestMove;
      const Piece movingPiece = position->piece[getFromSquare(killerMove)];
      const int index = historyIndex(bestMove, position);

      assert(numQuietMoves >= 1);

      variation->historyValue[index] = (UINT16)
         (variation->historyValue[index] +
          ((HISTORY_MAX - variation->historyValue[index]) * restDepth) / 256);
      assert(variation->historyValue[index] <= HISTORY_MAX);

      setMoveValue(&killerMove, movingPiece);
      registerKillerMove(&variation->plyInfo[ply], killerMove);

      if (best >= beta)
      {
         int i;

         for (i = 0; i < numQuietMoves; i++)
         {
            const int playedIndex = historyIndexPlayed[i];

            variation->historyTotalCount[playedIndex]++;

            if (variation->historyTotalCount[playedIndex] >= HISTORY_MAX)
            {
               shrinkHistoryHitValues(variation);
            }
         }

         variation->historyHitCount[index]++;
      }
   }

   /* Store the value in the transposition table. */
   /* ------------------------------------------- */
   if ((excludeMove == NO_MOVE || excludeMove == NULLMOVE) &&
       variation->searchStatus == SEARCH_STATUS_RUNNING)

   {
      if (best > oldAlpha)
      {
         hashentryFlag =
            (best >= beta ? HASHVALUE_LOWER_LIMIT : HASHVALUE_EXACT);
      }
      else
      {
         hashentryFlag = HASHVALUE_UPPER_LIMIT;
      }

      setDatedEntry(variation->hashtable, position->hashValue,
                    calcHashtableValue(best, ply),
                    (INT8) (rdBasic + HASH_DEPTH_OFFSET),
                    packedMove(bestMove), hashentryFlag);
   }

   return best;
}

static void registerNewBestMove(Variation * variation, Move * move,
                                const int value, PrincipalVariation * pv)
{
   if (variation->searchStatus == SEARCH_STATUS_RUNNING)
   {
      setMoveValue(move, value);
      variation->pv.score = value;

      if (variation->handleSearchEvent != 0)
      {
         appendMoveToPv(pv, &variation->pv, *move);
      }

      variation->bestBaseMove = *move;

      if (variation->nominalDepth > 4 &&
          variation->numberOfCurrentBaseMove > 1)
      {
         variation->bestMoveChange = TRUE;
         variation->easyMove = FALSE;
      }

      if (variation->handleSearchEvent != 0)
      {
         variation->handleSearchEvent(SEARCHEVENT_NEW_PV, variation);
      }
   }
}

#define MAX_FAILURES 4

static int getBaseMoveValue(Variation * variation, const Move move,
                            const int alpha, const int beta,
                            const bool fullWindow,
                            const int failHighCount,
                            const int aspirationWindow,
                            PrincipalVariation * pv)
{
   int depth = DEPTH_RESOLUTION * variation->nominalDepth;
   int value;

   assert(alpha >= VALUE_MATED);
   assert(alpha <= -VALUE_MATED);
   assert(beta >= VALUE_MATED);
   assert(beta <= -VALUE_MATED);
   assert(alpha < beta);

   makeMoveFast(variation, move);

   if (variation->handleSearchEvent != 0)
   {
      variation->handleSearchEvent(SEARCHEVENT_NEW_BASEMOVE, variation);
   }

   if (activeKingIsSafe(&variation->singlePosition) == FALSE)
   {
      variation->plyInfo[0].currentMoveIsCheck = TRUE;
      depth += DEPTH_RESOLUTION;
   }
   else
   {
      variation->plyInfo[0].currentMoveIsCheck = FALSE;
   }

   if (fullWindow)
   {
      value = -searchBest(variation, -beta, -alpha, 1,
                          depth - DEPTH_RESOLUTION, TRUE, FALSE, pv, NO_MOVE);

      if (value < alpha)
      {
         variation->failingHighOrLow = TRUE;
      }
   }
   else
   {
      value = -searchBest(variation, -alpha - 1, -alpha, 1,
                          depth - DEPTH_RESOLUTION, FALSE, FALSE,
                          pv, NO_MOVE);

      if (value > alpha)
      {
         variation->failingHighOrLow = TRUE;

         value = -searchBest(variation, -beta, -alpha, 1,
                             depth - DEPTH_RESOLUTION, TRUE,
                             FALSE, pv, NO_MOVE);
      }
   }

   unmakeLastMove(variation);

   if (variation->nominalDepth >= 4 && value >= beta)
   {
      Move moveCopy = move;

      registerNewBestMove(variation, &moveCopy, value, pv);
      variation->failingHighOrLow = TRUE;
   }

   if (value >= beta)
   {
      const int gap = aspirationWindow * (1 << (2 * failHighCount));
      const int extendedBeta = (failHighCount >= MAX_FAILURES ?
                                -VALUE_MATED : min(-VALUE_MATED, beta + gap));

      return getBaseMoveValue(variation, move, alpha, extendedBeta,
                              TRUE, min(MAX_FAILURES, failHighCount + 1),
                              aspirationWindow, pv);
   }
   else
   {
      return value;
   }
}

static void exploreBaseMoves(Variation * variation, Movelist * basemoves,
                             const int aspirationWindow)
{
   int best = VALUE_MATED;
   int alpha = max(VALUE_MATED, variation->previousBest - aspirationWindow);
   int ply = 0;
   Position *position = &variation->singlePosition;
   const bool fullWindow = (bool) (variation->nominalDepth <= 1);
   PrincipalVariation pv;
   int failLowCount = 0;
   bool exactValueFound = FALSE;

   initializeMoveValues(basemoves);
   variation->failingHighOrLow = FALSE;
   variation->selDepth = variation->nominalDepth;
   initPlyInfo(&variation->plyInfo[ply]);
   getStaticValue(variation, ply);

   do
   {
      best = VALUE_MATED;

      for (variation->numberOfCurrentBaseMove = 1;
           variation->numberOfCurrentBaseMove <= basemoves->numberOfMoves;
           variation->numberOfCurrentBaseMove++)
      {
         int value;
         const int icm = variation->numberOfCurrentBaseMove - 1;
         const int baseValue = max(alpha, variation->previousBest);
         const int beta = min(-VALUE_MATED, baseValue + aspirationWindow);
         const bool pvNode =
            (bool) (icm == 0 || fullWindow || failLowCount > 0);

         variation->currentBaseMove = basemoves->moves[icm];
         variation->plyInfo[ply].indexCurrentMove =
            historyIndex(variation->currentBaseMove, position);

         value = getBaseMoveValue(variation, basemoves->moves[icm],
                                  alpha, beta, pvNode, 0, aspirationWindow,
                                  &pv);

         if (variation->searchStatus != SEARCH_STATUS_RUNNING &&
             variation->nominalDepth > 1)
         {
            break;
         }

         if (value > best || fullWindow)
         {
            setMoveValue(&basemoves->moves[icm], value);
         }

         /* Report fail lows */
         if (icm == 0 && value > best && value <= alpha)
         {
            registerNewBestMove(variation, &basemoves->moves[icm], value,
                                &pv);
         }

         if (value > best)
         {
            best = value;

            if (best > alpha)
            {
               exactValueFound = TRUE;
               failLowCount = 0;
               variation->failingHighOrLow = (bool)
                  (best < variation->previousBest - FAIL_LOW_MARGIN);

               if (fullWindow == FALSE)
               {
                  alpha = best;
               }

               registerNewBestMove(variation, &basemoves->moves[icm], best,
                                   &pv);
            }
         }
      }

      if (exactValueFound == FALSE)
      {
         failLowCount = min(MAX_FAILURES, failLowCount + 1);
         alpha -= aspirationWindow * (1 << (2 * failLowCount));
         alpha = (failLowCount >= MAX_FAILURES ?
                  VALUE_MATED : max(VALUE_MATED, alpha));
         variation->failingHighOrLow = TRUE;
         sortMoves(basemoves);
         initializeMoveValues(basemoves);
      }
   }
   while (variation->searchStatus == SEARCH_STATUS_RUNNING &&
          exactValueFound == FALSE);

   sortMoves(basemoves);

   if (fullWindow &&
       (basemoves->numberOfMoves < 2 ||
        getMoveValue(basemoves->moves[0]) >
        getMoveValue(basemoves->moves[1]) + 150))
   {
      variation->easyMove = TRUE;
   }
}

static void initializePawnHashtable(PawnHashInfo * pawnHashtable)
{
   int i;

   for (i = 0; i < PAWN_HASHTABLE_SIZE; i++)
   {
      pawnHashtable[i].hashValue = 0;
   }
}

static void initializeKingsafetyHashtable(KingSafetyHashInfo *
                                          kingsafetyHashtable)
{
   int i;

   for (i = 0; i < KINGSAFETY_HASHTABLE_SIZE; i++)
   {
      kingsafetyHashtable[i].hashValue = 0;
   }
}

Move search(Variation * variation, Movelist * acceptableSolutions)
{
   Movelist movelist;
   int iteration;
   long timeTarget;
   int stableIterationCount = 0;
   int stableBestMoveCount = 0;
   Move bestMove = NO_MOVE;
   UINT64 nodeCount = 0;
   bool failLow = FALSE;
   int loScore = -VALUE_MATED, hiScore = VALUE_MATED;
   int iv1 = 0, iv2 = 0, iv3 = 0;

   if (resetGlobalHashtable)
   {
      resetHashtable(variation->hashtable);
      initializePawnHashtable(variation->pawnHashtable);
      initializeKingsafetyHashtable(variation->kingsafetyHashtable);
      resetGlobalHashtable = FALSE;
   }

   resetHistoryValues(variation);
   resetHistoryHitValues(variation);
   resetGainValues(variation);

   variation->startTime = getTimestamp();
   variation->startTimeProcess = getProcessTimestamp();
   variation->timestamp = variation->startTime + 1;
   variation->tbHits = 0;
   variation->numPvUpdates = 0;
   variation->easyMove = FALSE;
   variation->terminatePondering = FALSE;
   variation->previousBest = VALUE_MATED;
   variation->bestBaseMove = NO_MOVE;
   getLegalMoves(variation, &movelist);
   initializePlyInfo(variation);

#ifdef TRACE_EVAL
   getValue(&variation->singlePosition, VALUE_MATED, -VALUE_MATED,
            variation->pawnHashtable, variation->kingsafetyHashtable);
#endif

#ifdef USE_BOOK
   if (globalBook.indexFile != NULL && globalBook.moveFile != NULL &&
       &variation->singlePosition->moveNumber <= 12)
   {
      Move bookMove = getBookmove(&globalBook,
                                  &variation->singlePosition->hashValue,
                                  &movelist);

      if (bookMove != NO_MOVE)
      {
         variation->bestBaseMove = bookMove;
         variation->searchStatus = SEARCH_STATUS_TERMINATE;
         variation->finishTime = getTimestamp();

         if (variation->handleSearchEvent != 0)
         {
            variation->handleSearchEvent(SEARCHEVENT_SEARCH_FINISHED,
                                         variation);
         }

         variation->nodes = 0;

         return variation->bestBaseMove;
      }
   }
#endif

   variation->numberOfBaseMoves = movelist.numberOfMoves;
   setMoveValue(&variation->bestBaseMove, VALUE_MATED);

   for (iteration = 1; iteration <= MAX_DEPTH; iteration++)
   {
      long calculationTime;
      int iterationValue, referenceValue, aspirationWindow;
      int scoreWidth;

      variation->bestMoveChange = FALSE;
      variation->nominalDepth = iteration;

      aspirationWindow = max(10, (abs(iv1 - iv2) + abs(iv2 - iv3)) / 2);
      exploreBaseMoves(variation, &movelist, aspirationWindow);
      calculationTime =
         (unsigned long) (getTimestamp() - variation->startTime);

      if (movesAreEqual(variation->bestBaseMove, bestMove))
      {
         stableBestMoveCount++;
      }
      else
      {
         stableBestMoveCount = 0;
      }

      bestMove = variation->bestBaseMove;
      iv3 = iv2;
      iv2 = iv1;
      iv1 = iterationValue = getMoveValue(variation->bestBaseMove);

      loScore = (calculationTime >= variation->timeTarget / 32 ?
                 min(loScore, iterationValue) : loScore);
      hiScore = (calculationTime >= variation->timeTarget / 32 ?
                 max(hiScore, iterationValue) : hiScore);
      scoreWidth = max(hiScore, variation->expectedScore) -
         min(loScore, variation->expectedScore);
      failLow = (bool) (iterationValue <
                        variation->previousBest - FAIL_LOW_MARGIN);
      referenceValue = max(variation->previousBest, variation->expectedScore);
      variation->previousBest = iterationValue;

      assert(calculationTime >= 0);

      if (acceptableSolutions != 0 &&
          listContainsMove(acceptableSolutions, variation->bestBaseMove))
      {
         stableIterationCount++;

         if (stableIterationCount == 1)
         {
            nodeCount = variation->nodes;
         }
      }
      else
      {
         stableIterationCount = 0;
         nodeCount = variation->nodes;
      }

      /* Check for a fail low. */
      /* --------------------- */

      if (variation->numberOfBaseMoves == 1)
      {
         timeTarget = variation->timeTarget / 16;
      }
      else if (failLow)
      {
         timeTarget = 4 * variation->timeTarget;

         if (calculationTime >= variation->timeTarget / 32)
         {
            variation->easyMove = FALSE;
         }
      }
      else if (variation->bestMoveChange ||
               (iterationValue < referenceValue &&
                scoreWidth >= FAIL_LOW_MARGIN))
      {
         timeTarget = variation->timeTarget;
      }
      else if (variation->easyMove && iterationValue >= referenceValue)
      {
         timeTarget = variation->timeTarget / 4;
      }
      else
      {
         timeTarget = variation->timeTarget / 2;
      }

      if (variation->searchStatus == SEARCH_STATUS_RUNNING &&
          variation->timeLimit != 0 && calculationTime >= timeTarget)
      {
#ifdef DEBUG_THREAD_COORDINATION
         logDebug
            ("Time target reached (%lu/%lu ms, %lu%%)).\n",
             calculationTime, variation->timeTarget,
             (calculationTime * 100) / variation->timeTarget);
#endif

         if (variation->ponderMode)
         {
            variation->terminatePondering = TRUE;

#ifdef DEBUG_THREAD_COORDINATION
            logDebug("Setting ponder termination flag.\n");
#endif
         }
         else
         {
            variation->searchStatus = SEARCH_STATUS_TERMINATE;

#ifdef DEBUG_THREAD_COORDINATION
            logDebug("Terminating search.\n");
#endif
         }
      }

      if (variation->searchStatus == SEARCH_STATUS_RUNNING &&
          (getMoveValue(variation->bestBaseMove) <= VALUE_MATED + iteration ||
           getMoveValue(variation->bestBaseMove) >= -VALUE_MATED - iteration))
      {
#ifdef DEBUG_THREAD_COORDINATION
         logDebug("Best value out of bounds (%d). Terminating search.\n",
                  getMoveValue(variation->bestBaseMove));
#endif
         variation->searchStatus = SEARCH_STATUS_TERMINATE;
      }

      if (variation->searchStatus == SEARCH_STATUS_RUNNING &&
          iteration == MAX_DEPTH)
      {
#ifdef DEBUG_THREAD_COORDINATION
         logDebug("Max depth reached. Terminating search.\n");
#endif
         variation->searchStatus = SEARCH_STATUS_TERMINATE;
      }

      if (variation->searchStatus != SEARCH_STATUS_RUNNING)
      {
#ifdef DEBUG_THREAD_COORDINATION
         logReport
            ("search status != SEARCH_STATUS_RUNNING -> exiting search.\n",
             getMoveValue(variation->bestBaseMove));
#endif

         break;
      }

      if (acceptableSolutions != 0 && stableIterationCount >= 1 &&
          (getMoveValue(variation->bestBaseMove) > 20000 ||
           (stableIterationCount >= 2 &&
            (getMoveValue(variation->bestBaseMove) >= 25 ||
             (getTimestamp() - variation->startTime) >= 3000))))
      {
#ifdef DEBUG_THREAD_COORDINATION
         logDebug("Solution found (value=%d). Terminating search.\n",
                  getMoveValue(variation->bestBaseMove));
#endif
         variation->searchStatus = SEARCH_STATUS_TERMINATE;

         break;
      }
   }

   variation->terminatePondering = TRUE;
   variation->searchStatus = SEARCH_STATUS_TERMINATE;
   incrementDate(variation->hashtable);
   variation->finishTime = getTimestamp();
   variation->finishTimeProcess = getProcessTimestamp();

   if (variation->handleSearchEvent != 0)
   {
      variation->handleSearchEvent(SEARCHEVENT_SEARCH_FINISHED, variation);
   }

   variation->nodes = nodeCount;

   if (statCount1 != 0 || statCount2 != 0)
   {
      logDebug("statCount1=%lld statCount2=%lld (%lld%%) \n",
               statCount1, statCount2,
               (statCount2 * 100) / max(1, statCount1));
   }

   return variation->bestBaseMove;
}

/* #define DEBUG_FUT_VALUES */

static double futValue(double depth)
{
   return pow(1.25, depth);
}

static void initializeArrays(void)
{
   const double maxFutilityValue = 2048.0;
   const double factor = maxFutilityValue / futValue(15.0);
   int i, j;

   quietPvMoveReduction[0][0] = 0;
   quietMoveReduction[0][0] = 0;

   for (i = 1; i < 64; i++)
   {
      for (j = 1; j < 64; j++)
      {
         double pvReduction =
            0.5 + log((double) (i)) * log((double) (j)) / 6.0;
         double nonPvReduction =
            0.5 + log((double) (i)) * log((double) (j)) / 3.0;
         quietPvMoveReduction[i][j] =
            (int) (pvReduction >= 1.0 ?
                   floor(pvReduction * DEPTH_RESOLUTION) : 0);
         quietMoveReduction[i][j] =
            (int) (nonPvReduction >= 1.0 ?
                   floor(nonPvReduction * DEPTH_RESOLUTION) : 0);
      }
   }

   for (i = 0; i < 32; i++)
   {
      quietMoveCountLimit[i] = 3 + (1 << ((3 * i) / 8));
   }

   for (i = 0; i < 16; i++)
   {
      for (j = 0; j < 64; j++)
      {
         futilityMargin[i][j] = -2 * j;

         if (i >= 1)
         {
            double powi = futValue((double) (i));

            futilityMargin[i][j] += (int) (factor * powi);
         }

#ifdef DEBUG_FUT_VALUES
         if (j <= 2)
         {
            logDebug("fm[%d][%d]=%d\n", i, j, futilityMargin[i][j]);
         }
#endif
      }
   }

#ifdef DEBUG_FUT_VALUES
   getKeyStroke();
#endif
}

int initializeModuleSearch(void)
{
   const Move m1 = getPackedMove(F3, H5, NO_PIECE);
   const Move m2 = getPackedMove(G7, G6, NO_PIECE);
   Move ccrv[3];
   int i = 0;

   ccrv[0] = m1;
   ccrv[1] = m2;
   ccrv[2] = NO_MOVE;

   do
   {
      crv[i] = ccrv[i];
   }
   while (ccrv[i++] != NO_MOVE);

   initializeArrays();

   return 0;
}

int testModuleSearch(void)
{
   return 0;
}
