/*

Stockfish, a UCI chess playing engine derived from Glaurung 2.1

Copyright (C) 2004-2008 Tord Romstad (Glaurung author)

Copyright (C) 2008-2014 Marco Costalba, Joona Kiiski, Tord Romstad

Stockfish 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.

Stockfish 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 <algorithm>

#include <cassert>

#include <cfloat>

#include <cmath>

#include <cstring>

#include <iostream>

#include <sstream>

#include "book.h"

#include "evaluate.h"

#include "movegen.h"

#include "movepick.h"

#include "notation.h"

#include "search.h"

#include "timeman.h"

#include "thread.h"

#include "tt.h"

#include "ucioption.h"

namespace Search {

volatile SignalsType Signals;

LimitsType Limits;

std::vector<RootMove> RootMoves;

Position RootPos;

Color RootColor;

Time::point SearchTime;

StateStackPtr SetupStates;

}

using std::string;

using Eval::evaluate;

using namespace Search;

namespace {

// Set to true to force running with one thread. Used for debugging

const bool FakeSplit = false;

// Different node types, used as template parameter

enum NodeType { Root, PV, NonPV };

// Dynamic razoring margin based on depth

inline Value razor_margin(Depth d) { return Value(512 + 16 * d); }

// Futility lookup tables (initialized at startup) and their access functions

int FutilityMoveCounts[2][32]; // [improving][depth]

inline Value futility_margin(Depth d) {

return Value(100 * d);

}

// Reduction lookup tables (initialized at startup) and their access function

int8_t Reductions[2][2][64][64]; // [pv][improving][depth][moveNumber]

template <bool PvNode> inline Depth reduction(bool i, Depth d, int mn) {

return (Depth) Reductions[PvNode][i][std::min(int(d) / ONE_PLY, 63)][std::min(mn, 63)];

}

size_t MultiPV, PVIdx;

TimeManager TimeMgr;

double BestMoveChanges;

Value DrawValue[COLOR_NB];

HistoryStats History;

GainsStats Gains;

MovesStats Countermoves, Followupmoves;

template <NodeType NT, bool SpNode>

Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode);

template <NodeType NT, bool InCheck>

Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth);

void id_loop(Position& pos);

Value value_to_tt(Value v, int ply);

Value value_from_tt(Value v, int ply);

void update_stats(const Position& pos, Stack* ss, Move move, Depth depth, Move* quiets, int quietsCnt);

string uci_pv(const Position& pos, int depth, Value alpha, Value beta);

struct Skill {

Skill(int l) : level(l), best(MOVE_NONE) {}

~Skill() {

if (enabled()) // Swap best PV line with the sub-optimal one

std::swap(RootMoves[0], *std::find(RootMoves.begin(),

RootMoves.end(), best ? best : pick_move()));

}

bool enabled() const { return level < 20; }

bool time_to_pick(int depth) const { return depth == 1 + level; }

Move pick_move();

int level;

Move best;

};

} // namespace

/// Search::init() is called during startup to initialize various lookup tables

void Search::init() {

int d; // depth (ONE_PLY == 2)

int hd; // half depth (ONE_PLY == 1)

int mc; // moveCount

// Init reductions array

for (hd = 1; hd < 64; ++hd) for (mc = 1; mc < 64; ++mc)

{

double pvRed = 0.00 + log(double(hd)) * log(double(mc)) / 3.00;

double nonPVRed = 0.33 + log(double(hd)) * log(double(mc)) / 2.25;

Reductions[1][1][hd][mc] = int8_t( pvRed >= 1.0 ? pvRed * int(ONE_PLY) : 0);

Reductions[0][1][hd][mc] = int8_t(nonPVRed >= 1.0 ? nonPVRed * int(ONE_PLY) : 0);

Reductions[1][0][hd][mc] = Reductions[1][1][hd][mc];

Reductions[0][0][hd][mc] = Reductions[0][1][hd][mc];

if (Reductions[0][0][hd][mc] > 2 * ONE_PLY)

Reductions[0][0][hd][mc] += ONE_PLY;

else if (Reductions[0][0][hd][mc] > 1 * ONE_PLY)

Reductions[0][0][hd][mc] += ONE_PLY / 2;

}

// Init futility move count array

for (d = 0; d < 32; ++d)

{

FutilityMoveCounts[0][d] = int(2.4 + 0.222 * pow(d + 0.00, 1.8));

FutilityMoveCounts[1][d] = int(3.0 + 0.300 * pow(d + 0.98, 1.8));

}

}

/// Search::perft() is our utility to verify move generation. All the leaf nodes

/// up to the given depth are generated and counted and the sum returned.

static uint64_t perft(Position& pos, Depth depth) {

StateInfo st;

uint64_t cnt = 0;

CheckInfo ci(pos);

const bool leaf = depth == 2 * ONE_PLY;

for (MoveList<LEGAL> it(pos); *it; ++it)

{

pos.do_move(*it, st, ci, pos.gives_check(*it, ci));

cnt += leaf ? MoveList<LEGAL>(pos).size() : ::perft(pos, depth - ONE_PLY);

pos.undo_move(*it);

}

return cnt;

}

uint64_t Search::perft(Position& pos, Depth depth) {

return depth > ONE_PLY ? ::perft(pos, depth) : MoveList<LEGAL>(pos).size();

}

/// Search::think() is the external interface to Stockfish's search, and is

/// called by the main thread when the program receives the UCI 'go' command. It

/// searches from RootPos and at the end prints the "bestmove" to output.

void Search::think() {

static PolyglotBook book; // Defined static to initialize the PRNG only once

RootColor = RootPos.side_to_move();

TimeMgr.init(Limits, RootPos.game_ply(), RootColor);

int cf = Options["Contempt Factor"] * PawnValueEg / 100; // From centipawns

DrawValue[ RootColor] = VALUE_DRAW - Value(cf);

DrawValue[~RootColor] = VALUE_DRAW + Value(cf);

if (RootMoves.empty())

{

RootMoves.push_back(MOVE_NONE);

sync_cout << "info depth 0 score "

<< score_to_uci(RootPos.checkers() ? -VALUE_MATE : VALUE_DRAW)

<< sync_endl;

goto finalize;

}

if (Options["OwnBook"] && !Limits.infinite && !Limits.mate)

{

Move bookMove = book.probe(RootPos, Options["Book File"], Options["Best Book Move"]);

if (bookMove && std::count(RootMoves.begin(), RootMoves.end(), bookMove))

{

std::swap(RootMoves[0], *std::find(RootMoves.begin(), RootMoves.end(), bookMove));

goto finalize;

}

}

if (Options["Write Search Log"])

{

Log log(Options["Search Log Filename"]);

log << "\nSearching: " << RootPos.fen()

<< "\ninfinite: " << Limits.infinite

<< " ponder: " << Limits.ponder

<< " time: " << Limits.time[RootColor]

<< " increment: " << Limits.inc[RootColor]

<< " moves to go: " << Limits.movestogo

<< "\n" << std::endl;

}

// Reset the threads, still sleeping: will wake up at split time

for (size_t i = 0; i < Threads.size(); ++i)

Threads[i]->maxPly = 0;

Threads.timer->run = true;

Threads.timer->notify_one(); // Wake up the recurring timer

id_loop(RootPos); // Let's start searching !

Threads.timer->run = false; // Stop the timer

if (Options["Write Search Log"])

{

Time::point elapsed = Time::now() - SearchTime + 1;

Log log(Options["Search Log Filename"]);

log << "Nodes: " << RootPos.nodes_searched()

<< "\nNodes/second: " << RootPos.nodes_searched() * 1000 / elapsed

<< "\nBest move: " << move_to_san(RootPos, RootMoves[0].pv[0]);

StateInfo st;

RootPos.do_move(RootMoves[0].pv[0], st);

log << "\nPonder move: " << move_to_san(RootPos, RootMoves[0].pv[1]) << std::endl;

RootPos.undo_move(RootMoves[0].pv[0]);

}

finalize:

// When search is stopped this info is not printed

sync_cout << "info nodes " << RootPos.nodes_searched()

<< " time " << Time::now() - SearchTime + 1 << sync_endl;

// When we reach the maximum depth, we can arrive here without a raise of

// Signals.stop. However, if we are pondering or in an infinite search,

// the UCI protocol states that we shouldn't print the best move before the

// GUI sends a "stop" or "ponderhit" command. We therefore simply wait here

// until the GUI sends one of those commands (which also raises Signals.stop).

if (!Signals.stop && (Limits.ponder || Limits.infinite))

{

Signals.stopOnPonderhit = true;

RootPos.this_thread()->wait_for(Signals.stop);

}

// Best move could be MOVE_NONE when searching on a stalemate position

sync_cout << "bestmove " << move_to_uci(RootMoves[0].pv[0], RootPos.is_chess960())

<< " ponder " << move_to_uci(RootMoves[0].pv[1], RootPos.is_chess960())

<< sync_endl;

}

namespace {

// id_loop() is the main iterative deepening loop. It calls search() repeatedly

// with increasing depth until the allocated thinking time has been consumed,

// user stops the search, or the maximum search depth is reached.

void id_loop(Position& pos) {

Stack stack[MAX_PLY_PLUS_6], *ss = stack+2; // To allow referencing (ss-2)

int depth;

Value bestValue, alpha, beta, delta;

std::memset(ss-2, 0, 5 * sizeof(Stack));

(ss-1)->currentMove = MOVE_NULL; // Hack to skip update gains

depth = 0;

BestMoveChanges = 0;

bestValue = delta = alpha = -VALUE_INFINITE;

beta = VALUE_INFINITE;

TT.new_search();

History.clear();

Gains.clear();

Countermoves.clear();

Followupmoves.clear();

MultiPV = Options["MultiPV"];

Skill skill(Options["Skill Level"]);

// Do we have to play with skill handicap? In this case enable MultiPV search

// that we will use behind the scenes to retrieve a set of possible moves.

if (skill.enabled() && MultiPV < 4)

MultiPV = 4;

MultiPV = std::min(MultiPV, RootMoves.size());

// Iterative deepening loop until requested to stop or target depth reached

while (++depth <= MAX_PLY && !Signals.stop && (!Limits.depth || depth <= Limits.depth))

{

// Age out PV variability metric

BestMoveChanges *= 0.5;

// Save the last iteration's scores before first PV line is searched and

// all the move scores except the (new) PV are set to -VALUE_INFINITE.

for (size_t i = 0; i < RootMoves.size(); ++i)

RootMoves[i].prevScore = RootMoves[i].score;

// MultiPV loop. We perform a full root search for each PV line

for (PVIdx = 0; PVIdx < MultiPV && !Signals.stop; ++PVIdx)

{

// Reset aspiration window starting size

if (depth >= 5)

{

delta = Value(16);

alpha = std::max(RootMoves[PVIdx].prevScore - delta,-VALUE_INFINITE);

beta = std::min(RootMoves[PVIdx].prevScore + delta, VALUE_INFINITE);

}

// Start with a small aspiration window and, in the case of a fail

// high/low, re-search with a bigger window until we're not failing

// high/low anymore.

while (true)

{

bestValue = search<Root, false>(pos, ss, alpha, beta, depth * ONE_PLY, false);

// Bring the best move to the front. It is critical that sorting

// is done with a stable algorithm because all the values but the

// first and eventually the new best one are set to -VALUE_INFINITE

// and we want to keep the same order for all the moves except the

// new PV that goes to the front. Note that in case of MultiPV

// search the already searched PV lines are preserved.

std::stable_sort(RootMoves.begin() + PVIdx, RootMoves.end());

// Write PV back to transposition table in case the relevant

// entries have been overwritten during the search.

for (size_t i = 0; i <= PVIdx; ++i)

RootMoves[i].insert_pv_in_tt(pos);

// If search has been stopped break immediately. Sorting and

// writing PV back to TT is safe because RootMoves is still

// valid, although it refers to previous iteration.

if (Signals.stop)

break;

// When failing high/low give some update (without cluttering

// the UI) before a re-search.

if ( (bestValue <= alpha || bestValue >= beta)

&& Time::now() - SearchTime > 3000)

sync_cout << uci_pv(pos, depth, alpha, beta) << sync_endl;

// In case of failing low/high increase aspiration window and

// re-search, otherwise exit the loop.

if (bestValue <= alpha)

{

alpha = std::max(bestValue - delta, -VALUE_INFINITE);

Signals.failedLowAtRoot = true;

Signals.stopOnPonderhit = false;

}

else if (bestValue >= beta)

beta = std::min(bestValue + delta, VALUE_INFINITE);

else

break;

delta += delta / 2;

assert(alpha >= -VALUE_INFINITE && beta <= VALUE_INFINITE);

}

// Sort the PV lines searched so far and update the GUI

std::stable_sort(RootMoves.begin(), RootMoves.begin() + PVIdx + 1);

if (PVIdx + 1 == MultiPV || Time::now() - SearchTime > 3000)

sync_cout << uci_pv(pos, depth, alpha, beta) << sync_endl;

}

// If skill levels are enabled and time is up, pick a sub-optimal best move

if (skill.enabled() && skill.time_to_pick(depth))

skill.pick_move();

if (Options["Write Search Log"])

{

RootMove& rm = RootMoves[0];

if (skill.best != MOVE_NONE)

rm = *std::find(RootMoves.begin(), RootMoves.end(), skill.best);

Log log(Options["Search Log Filename"]);

log << pretty_pv(pos, depth, rm.score, Time::now() - SearchTime, &rm.pv[0])

<< std::endl;

}

// Have we found a "mate in x"?

if ( Limits.mate

&& bestValue >= VALUE_MATE_IN_MAX_PLY

&& VALUE_MATE - bestValue <= 2 * Limits.mate)

Signals.stop = true;

// Do we have time for the next iteration? Can we stop searching now?

if (Limits.use_time_management() && !Signals.stop && !Signals.stopOnPonderhit)

{

// Take some extra time if the best move has changed

if (depth > 4 && depth < 50 && MultiPV == 1)

TimeMgr.pv_instability(BestMoveChanges);

// Stop the search if only one legal move is available or all

// of the available time has been used.

if ( RootMoves.size() == 1

|| Time::now() - SearchTime > TimeMgr.available_time())

{

// If we are allowed to ponder do not stop the search now but

// keep pondering until the GUI sends "ponderhit" or "stop".

if (Limits.ponder)

Signals.stopOnPonderhit = true;

else

Signals.stop = true;

}

}

}

}

// search<>() is the main search function for both PV and non-PV nodes and for

// normal and SplitPoint nodes. When called just after a split point the search

// is simpler because we have already probed the hash table, done a null move

// search, and searched the first move before splitting, so we don't have to

// repeat all this work again. We also don't need to store anything to the hash

// table here: This is taken care of after we return from the split point.

template <NodeType NT, bool SpNode>

Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode) {

const bool RootNode = NT == Root;

const bool PvNode = NT == PV || NT == Root;

assert(-VALUE_INFINITE <= alpha && alpha < beta && beta <= VALUE_INFINITE);

assert(PvNode || (alpha == beta - 1));

assert(depth > DEPTH_ZERO);

Move quietsSearched[64];

StateInfo st;

const TTEntry *tte;

SplitPoint* splitPoint;

Key posKey;

Move ttMove, move, excludedMove, bestMove;

Depth ext, newDepth, predictedDepth;

Value bestValue, value, ttValue, eval, nullValue, futilityValue;

bool inCheck, givesCheck, pvMove, singularExtensionNode, improving;

bool captureOrPromotion, dangerous, doFullDepthSearch;

int moveCount, quietCount;

// Step 1. Initialize node

Thread* thisThread = pos.this_thread();

inCheck = pos.checkers();

if (SpNode)

{

splitPoint = ss->splitPoint;

bestMove = splitPoint->bestMove;

bestValue = splitPoint->bestValue;

tte = NULL;

ttMove = excludedMove = MOVE_NONE;

ttValue = VALUE_NONE;

assert(splitPoint->bestValue > -VALUE_INFINITE && splitPoint->moveCount > 0);

goto moves_loop;

}

moveCount = quietCount = 0;

bestValue = -VALUE_INFINITE;

ss->currentMove = ss->ttMove = (ss+1)->excludedMove = bestMove = MOVE_NONE;

ss->ply = (ss-1)->ply + 1;

(ss+1)->skipNullMove = false; (ss+1)->reduction = DEPTH_ZERO;

(ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE;

// Used to send selDepth info to GUI

if (PvNode && thisThread->maxPly < ss->ply)

thisThread->maxPly = ss->ply;

if (!RootNode)

{

// Step 2. Check for aborted search and immediate draw

if (Signals.stop || pos.is_draw() || ss->ply > MAX_PLY)

return ss->ply > MAX_PLY && !inCheck ? evaluate(pos) : DrawValue[pos.side_to_move()];

// Step 3. Mate distance pruning. Even if we mate at the next move our score

// would be at best mate_in(ss->ply+1), but if alpha is already bigger because

// a shorter mate was found upward in the tree then there is no need to search

// because we will never beat the current alpha. Same logic but with reversed

// signs applies also in the opposite condition of being mated instead of giving

// mate. In this case return a fail-high score.

alpha = std::max(mated_in(ss->ply), alpha);

beta = std::min(mate_in(ss->ply+1), beta);

if (alpha >= beta)

return alpha;

}

// Step 4. Transposition table lookup

// We don't want the score of a partial search to overwrite a previous full search

// TT value, so we use a different position key in case of an excluded move.

excludedMove = ss->excludedMove;

posKey = excludedMove ? pos.exclusion_key() : pos.key();

tte = TT.probe(posKey);

ss->ttMove = ttMove = RootNode ? RootMoves[PVIdx].pv[0] : tte ? tte->move() : MOVE_NONE;

ttValue = tte ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE;

// At PV nodes we check for exact scores, whilst at non-PV nodes we check for

// a fail high/low. The biggest advantage to probing at PV nodes is to have a

// smooth experience in analysis mode. We don't probe at Root nodes otherwise

// we should also update RootMoveList to avoid bogus output.

if ( !RootNode

&& tte

&& tte->depth() >= depth

&& ttValue != VALUE_NONE // Only in case of TT access race

&& ( PvNode ? tte->bound() == BOUND_EXACT

: ttValue >= beta ? (tte->bound() & BOUND_LOWER)

: (tte->bound() & BOUND_UPPER)))

{

ss->currentMove = ttMove; // Can be MOVE_NONE

// If ttMove is quiet, update killers, history, counter move and followup move on TT hit

if (ttValue >= beta && ttMove && !pos.capture_or_promotion(ttMove) && !inCheck)

update_stats(pos, ss, ttMove, depth, NULL, 0);

return ttValue;

}

// Step 5. Evaluate the position statically and update parent's gain statistics

if (inCheck)

{

ss->staticEval = eval = VALUE_NONE;

goto moves_loop;

}

else if (tte)

{

// Never assume anything on values stored in TT

if ((ss->staticEval = eval = tte->eval_value()) == VALUE_NONE)

eval = ss->staticEval = evaluate(pos);

// Can ttValue be used as a better position evaluation?

if (ttValue != VALUE_NONE)

if (tte->bound() & (ttValue > eval ? BOUND_LOWER : BOUND_UPPER))

eval = ttValue;

}

else

{

eval = ss->staticEval = evaluate(pos);

TT.store(posKey, VALUE_NONE, BOUND_NONE, DEPTH_NONE, MOVE_NONE, ss->staticEval);

}

if ( !pos.captured_piece_type()

&& ss->staticEval != VALUE_NONE

&& (ss-1)->staticEval != VALUE_NONE

&& (move = (ss-1)->currentMove) != MOVE_NULL

&& type_of(move) == NORMAL)

{

Square to = to_sq(move);

Gains.update(pos.piece_on(to), to, -(ss-1)->staticEval - ss->staticEval);

}

// Step 6. Razoring (skipped when in check)

if ( !PvNode

&& depth < 4 * ONE_PLY

&& eval + razor_margin(depth) <= alpha

&& ttMove == MOVE_NONE

&& abs(beta) < VALUE_MATE_IN_MAX_PLY

&& !pos.pawn_on_7th(pos.side_to_move()))

{

if ( depth <= ONE_PLY

&& eval + razor_margin(3 * ONE_PLY) <= alpha)

return qsearch<NonPV, false>(pos, ss, alpha, beta, DEPTH_ZERO);

Value ralpha = alpha - razor_margin(depth);

Value v = qsearch<NonPV, false>(pos, ss, ralpha, ralpha+1, DEPTH_ZERO);

if (v <= ralpha)

return v;

}

// Step 7. Futility pruning: child node (skipped when in check)

if ( !PvNode

&& !ss->skipNullMove

&& depth < 7 * ONE_PLY

&& eval - futility_margin(depth) >= beta

&& abs(beta) < VALUE_MATE_IN_MAX_PLY

&& abs(eval) < VALUE_KNOWN_WIN

&& pos.non_pawn_material(pos.side_to_move()))

return eval - futility_margin(depth);

// Step 8. Null move search with verification search (is omitted in PV nodes)

if ( !PvNode

&& !ss->skipNullMove

&& depth >= 2 * ONE_PLY

&& eval >= beta

&& abs(beta) < VALUE_MATE_IN_MAX_PLY

&& pos.non_pawn_material(pos.side_to_move()))

{

ss->currentMove = MOVE_NULL;

assert(eval - beta >= 0);

// Null move dynamic reduction based on depth and value

Depth R = 3 * ONE_PLY

+ depth / 4

+ int(eval - beta) / PawnValueMg * ONE_PLY;

pos.do_null_move(st);

(ss+1)->skipNullMove = true;

nullValue = depth-R < ONE_PLY ? -qsearch<NonPV, false>(pos, ss+1, -beta, -beta+1, DEPTH_ZERO)

: - search<NonPV, false>(pos, ss+1, -beta, -beta+1, depth-R, !cutNode);

(ss+1)->skipNullMove = false;

pos.undo_null_move();

if (nullValue >= beta)

{

// Do not return unproven mate scores

if (nullValue >= VALUE_MATE_IN_MAX_PLY)

nullValue = beta;

if (depth < 12 * ONE_PLY)

return nullValue;

// Do verification search at high depths

ss->skipNullMove = true;

Value v = depth-R < ONE_PLY ? qsearch<NonPV, false>(pos, ss, beta-1, beta, DEPTH_ZERO)

: search<NonPV, false>(pos, ss, beta-1, beta, depth-R, false);

ss->skipNullMove = false;

if (v >= beta)

return nullValue;

}

}

// Step 9. ProbCut (skipped when in check)

// If we have a very good capture (i.e. SEE > seeValues[captured_piece_type])

// and a reduced search returns a value much above beta, we can (almost) safely

// prune the previous move.

if ( !PvNode

&& depth >= 5 * ONE_PLY

&& !ss->skipNullMove

&& abs(beta) < VALUE_MATE_IN_MAX_PLY)

{

Value rbeta = std::min(beta + 200, VALUE_INFINITE);

Depth rdepth = depth - 4 * ONE_PLY;

assert(rdepth >= ONE_PLY);

assert((ss-1)->currentMove != MOVE_NONE);

assert((ss-1)->currentMove != MOVE_NULL);

MovePicker mp(pos, ttMove, History, pos.captured_piece_type());

CheckInfo ci(pos);

while ((move = mp.next_move<false>()) != MOVE_NONE)

if (pos.legal(move, ci.pinned))

{

ss->currentMove = move;

pos.do_move(move, st, ci, pos.gives_check(move, ci));

value = -search<NonPV, false>(pos, ss+1, -rbeta, -rbeta+1, rdepth, !cutNode);

pos.undo_move(move);

if (value >= rbeta)

return value;

}

}

// Step 10. Internal iterative deepening (skipped when in check)

if ( depth >= (PvNode ? 5 * ONE_PLY : 8 * ONE_PLY)

&& !ttMove

&& (PvNode || ss->staticEval + 256 >= beta))

{

Depth d = depth - 2 * ONE_PLY - (PvNode ? DEPTH_ZERO : depth / 4);

ss->skipNullMove = true;

search<PvNode ? PV : NonPV, false>(pos, ss, alpha, beta, d, true);

ss->skipNullMove = false;

tte = TT.probe(posKey);

ttMove = tte ? tte->move() : MOVE_NONE;

}

moves_loop: // When in check and at SpNode search starts from here

Square prevMoveSq = to_sq((ss-1)->currentMove);

Move countermoves[] = { Countermoves[pos.piece_on(prevMoveSq)][prevMoveSq].first,

Countermoves[pos.piece_on(prevMoveSq)][prevMoveSq].second };

Square prevOwnMoveSq = to_sq((ss-2)->currentMove);

Move followupmoves[] = { Followupmoves[pos.piece_on(prevOwnMoveSq)][prevOwnMoveSq].first,

Followupmoves[pos.piece_on(prevOwnMoveSq)][prevOwnMoveSq].second };

MovePicker mp(pos, ttMove, depth, History, countermoves, followupmoves, ss);

CheckInfo ci(pos);

value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc

improving = ss->staticEval >= (ss-2)->staticEval

|| ss->staticEval == VALUE_NONE

||(ss-2)->staticEval == VALUE_NONE;

singularExtensionNode = !RootNode

&& !SpNode

&& depth >= 8 * ONE_PLY

&& ttMove != MOVE_NONE

&& !excludedMove // Recursive singular search is not allowed

&& (tte->bound() & BOUND_LOWER)

&& tte->depth() >= depth - 3 * ONE_PLY;

// Step 11. Loop through moves

// Loop through all pseudo-legal moves until no moves remain or a beta cutoff occurs

while ((move = mp.next_move<SpNode>()) != MOVE_NONE)

{

assert(is_ok(move));

if (move == excludedMove)

continue;

// At root obey the "searchmoves" option and skip moves not listed in Root

// Move List. As a consequence any illegal move is also skipped. In MultiPV

// mode we also skip PV moves which have been already searched.

if (RootNode && !std::count(RootMoves.begin() + PVIdx, RootMoves.end(), move))

continue;

if (SpNode)

{

// Shared counter cannot be decremented later if the move turns out to be illegal

if (!pos.legal(move, ci.pinned))

continue;

moveCount = ++splitPoint->moveCount;

splitPoint->mutex.unlock();

}

else

++moveCount;

if (RootNode)

{

Signals.firstRootMove = (moveCount == 1);

if (thisThread == Threads.main() && Time::now() - SearchTime > 3000)

sync_cout << "info depth " << depth / ONE_PLY

<< " currmove " << move_to_uci(move, pos.is_chess960())

<< " currmovenumber " << moveCount + PVIdx << sync_endl;

}

ext = DEPTH_ZERO;

captureOrPromotion = pos.capture_or_promotion(move);

givesCheck = type_of(move) == NORMAL && !ci.dcCandidates

? ci.checkSq[type_of(pos.piece_on(from_sq(move)))] & to_sq(move)

: pos.gives_check(move, ci);

dangerous = givesCheck

|| type_of(move) != NORMAL

|| pos.advanced_pawn_push(move);

// Step 12. Extend checks

if (givesCheck && pos.see_sign(move) >= VALUE_ZERO)

ext = ONE_PLY;

// Singular extension search. If all moves but one fail low on a search of

// (alpha-s, beta-s), and just one fails high on (alpha, beta), then that move

// is singular and should be extended. To verify this we do a reduced search

// on all the other moves but the ttMove and if the result is lower than

// ttValue minus a margin then we extend the ttMove.

if ( singularExtensionNode

&& move == ttMove

&& !ext

&& pos.legal(move, ci.pinned)

&& abs(ttValue) < VALUE_KNOWN_WIN)

{

assert(ttValue != VALUE_NONE);

Value rBeta = ttValue - int(depth);

ss->excludedMove = move;

ss->skipNullMove = true;

value = search<NonPV, false>(pos, ss, rBeta - 1, rBeta, depth / 2, cutNode);

ss->skipNullMove = false;

ss->excludedMove = MOVE_NONE;

if (value < rBeta)

ext = ONE_PLY;

}

// Update the current move (this must be done after singular extension search)

newDepth = depth - ONE_PLY + ext;

// Step 13. Pruning at shallow depth (exclude PV nodes)

if ( !PvNode

&& !captureOrPromotion

&& !inCheck

&& !dangerous

/* && move != ttMove Already implicit in the next condition */

&& bestValue > VALUE_MATED_IN_MAX_PLY)

{

// Move count based pruning

if ( depth < 16 * ONE_PLY

&& moveCount >= FutilityMoveCounts[improving][depth] )

{

if (SpNode)

splitPoint->mutex.lock();

continue;

}

predictedDepth = newDepth - reduction<PvNode>(improving, depth, moveCount);

// Futility pruning: parent node

if (predictedDepth < 7 * ONE_PLY)

{

futilityValue = ss->staticEval + futility_margin(predictedDepth)

+ 128 + Gains[pos.moved_piece(move)][to_sq(move)];

if (futilityValue <= alpha)

{

bestValue = std::max(bestValue, futilityValue);

if (SpNode)

{

splitPoint->mutex.lock();

if (bestValue > splitPoint->bestValue)

splitPoint->bestValue = bestValue;

}

continue;

}

}

// Prune moves with negative SEE at low depths

if (predictedDepth < 4 * ONE_PLY && pos.see_sign(move) < VALUE_ZERO)

{

if (SpNode)

splitPoint->mutex.lock();

continue;

}

}

// Check for legality just before making the move

if (!RootNode && !SpNode && !pos.legal(move, ci.pinned))

{

moveCount--;

continue;

}

pvMove = PvNode && moveCount == 1;

ss->currentMove = move;

if (!SpNode && !captureOrPromotion && quietCount < 64)

quietsSearched[quietCount++] = move;

// Step 14. Make the move

pos.do_move(move, st, ci, givesCheck);

// Step 15. Reduced depth search (LMR). If the move fails high it will be

// re-searched at full depth.

if ( depth >= 3 * ONE_PLY

&& !pvMove

&& !captureOrPromotion

&& move != ttMove

&& move != ss->killers[0]

&& move != ss->killers[1])

{

ss->reduction = reduction<PvNode>(improving, depth, moveCount);

if (!PvNode && cutNode)

ss->reduction += ONE_PLY;

else if (History[pos.piece_on(to_sq(move))][to_sq(move)] < 0)

ss->reduction += ONE_PLY / 2;

if (move == countermoves[0] || move == countermoves[1])

ss->reduction = std::max(DEPTH_ZERO, ss->reduction - ONE_PLY);

Depth d = std::max(newDepth - ss->reduction, ONE_PLY);

if (SpNode)

alpha = splitPoint->alpha;

value = -search<NonPV, false>(pos, ss+1, -(alpha+1), -alpha, d, true);

// Re-search at intermediate depth if reduction is very high

if (value > alpha && ss->reduction >= 4 * ONE_PLY)

{

Depth d2 = std::max(newDepth - 2 * ONE_PLY, ONE_PLY);

value = -search<NonPV, false>(pos, ss+1, -(alpha+1), -alpha, d2, true);

}

doFullDepthSearch = (value > alpha && ss->reduction != DEPTH_ZERO);

ss->reduction = DEPTH_ZERO;

}

else

doFullDepthSearch = !pvMove;

// Step 16. Full depth search, when LMR is skipped or fails high

if (doFullDepthSearch)

{

if (SpNode)

alpha = splitPoint->alpha;

value = newDepth < ONE_PLY ?

givesCheck ? -qsearch<NonPV, true>(pos, ss+1, -(alpha+1), -alpha, DEPTH_ZERO)

: -qsearch<NonPV, false>(pos, ss+1, -(alpha+1), -alpha, DEPTH_ZERO)

: - search<NonPV, false>(pos, ss+1, -(alpha+1), -alpha, newDepth, !cutNode);

}

// For PV nodes only, do a full PV search on the first move or after a fail

// high (in the latter case search only if value < beta), otherwise let the

// parent node fail low with value <= alpha and to try another move.

if (PvNode && (pvMove || (value > alpha && (RootNode || value < beta))))

value = newDepth < ONE_PLY ?

givesCheck ? -qsearch<PV, true>(pos, ss+1, -beta, -alpha, DEPTH_ZERO)

: -qsearch<PV, false>(pos, ss+1, -beta, -alpha, DEPTH_ZERO)

: - search<PV, false>(pos, ss+1, -beta, -alpha, newDepth, false);

// Step 17. Undo move

pos.undo_move(move);

assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);

// Step 18. Check for new best move

if (SpNode)

{

splitPoint->mutex.lock();

bestValue = splitPoint->bestValue;

alpha = splitPoint->alpha;

}

// Finished searching the move. If a stop or a cutoff occurred, the return

// value of the search cannot be trusted, and we return immediately without

// updating best move, PV and TT.

if (Signals.stop || thisThread->cutoff_occurred())

return VALUE_ZERO;

if (RootNode)

{

RootMove& rm = *std::find(RootMoves.begin(), RootMoves.end(), move);

// PV move or new best move ?

if (pvMove || value > alpha)

{

rm.score = value;

rm.extract_pv_from_tt(pos);

// We record how often the best move has been changed in each

// iteration. This information is used for time management: When

// the best move changes frequently, we allocate some more time.

if (!pvMove)

++BestMoveChanges;

}

else

// All other moves but the PV are set to the lowest value: this is

// not a problem when sorting because the sort is stable and the

// move position in the list is preserved - just the PV is pushed up.

rm.score = -VALUE_INFINITE;

}

if (value > bestValue)

{

bestValue = SpNode ? splitPoint->bestValue = value : value;

if (value > alpha)

{

bestMove = SpNode ? splitPoint->bestMove = move : move;

if (PvNode && value < beta) // Update alpha! Always alpha < beta

alpha = SpNode ? splitPoint->alpha = value : value;

else

{

assert(value >= beta); // Fail high

if (SpNode)

splitPoint->cutoff = true;

break;

}

}

}

// Step 19. Check for splitting the search

if ( !SpNode

&& Threads.size() >= 2

&& depth >= Threads.minimumSplitDepth

&& ( !thisThread->activeSplitPoint

|| !thisThread->activeSplitPoint->allSlavesSearching)

&& thisThread->splitPointsSize < MAX_SPLITPOINTS_PER_THREAD)

{

assert(bestValue > -VALUE_INFINITE && bestValue < beta);

thisThread->split<FakeSplit>(pos, ss, alpha, beta, &bestValue, &bestMove,

depth, moveCount, &mp, NT, cutNode);

if (Signals.stop || thisThread->cutoff_occurred())