/*

Stockfish, a UCI chess playing engine derived from Glaurung 2.1

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

Copyright (C) 2008-2013 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 <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;

// This is the minimum interval in msec between two check_time() calls

const int TimerResolution = 5;

// Different node types, used as template parameter

enum NodeType { Root, PV, NonPV, SplitPointRoot, SplitPointPV, SplitPointNonPV };

// Dynamic razoring margin based on depth

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

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

Value FutilityMargins[16][64]; // [depth][moveNumber]

int FutilityMoveCounts[32]; // [depth]

inline Value futility_margin(Depth d, int mn) {

return d < 7 * ONE_PLY ? FutilityMargins[std::max(int(d), 1)][std::min(mn, 63)]

: 2 * VALUE_INFINITE;

}

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

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

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

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

}

size_t PVSize, PVIdx;

TimeManager TimeMgr;

int BestMoveChanges;

Value DrawValue[COLOR_NB];

History Hist;

Gains Gain;

template <NodeType NT>

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

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);

bool check_is_dangerous(const Position& pos, Move move, Value futilityBase, Value beta);

bool allows(const Position& pos, Move first, Move second);

bool refutes(const Position& pos, Move first, Move second);

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 = log(double(hd)) * log(double(mc)) / 3.0;

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

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

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

}

// Init futility margins array

for (d = 1; d < 16; d++) for (mc = 0; mc < 64; mc++)

FutilityMargins[d][mc] = Value(112 * int(log(double(d * d) / 2) / log(2.0) + 1.001) - 8 * mc + 45);

// Init futility move count array

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

FutilityMoveCounts[d] = int(3.001 + 0.25 * pow(double(d), 2.0));

}

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

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

// At the last ply just return the number of legal moves (leaf nodes)

if (depth == ONE_PLY)

return MoveList<LEGAL>(pos).size();

StateInfo st;

size_t cnt = 0;

CheckInfo ci(pos);

for (MoveList<LEGAL> ml(pos); !ml.end(); ++ml)

{

pos.do_move(ml.move(), st, ci, pos.move_gives_check(ml.move(), ci));

cnt += perft(pos, depth - ONE_PLY);

pos.undo_move(ml.move());

}

return cnt;

}

/// 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);

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["Contempt Factor"] && !Options["UCI_AnalyseMode"])

{

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

cf = cf * Material::game_phase(RootPos) / PHASE_MIDGAME; // Scale down with phase

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

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

}

else

DrawValue[WHITE] = DrawValue[BLACK] = VALUE_DRAW;

if (Options["Use 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

<< std::endl;

}

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

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

Threads[i]->maxPly = 0;

Threads.sleepWhileIdle = Options["Use Sleeping Threads"];

// Set best timer interval to avoid lagging under time pressure. Timer is

// used to check for remaining available thinking time.

Threads.timer->msec =

Limits.use_time_management() ? std::min(100, std::max(TimeMgr.available_time() / 16, TimerResolution)) :

Limits.nodes ? 2 * TimerResolution

: 100;

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

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

Threads.timer->msec = 0; // Stop the timer

Threads.sleepWhileIdle = true; // Send idle threads to sleep

if (Options["Use 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 we reach max depth we arrive here even without Signals.stop is raised,

// but if we are pondering or in infinite search, according to UCI protocol,

// we shouldn't print the best move before the GUI sends a "stop" or "ponderhit"

// command. We simply wait here until GUI sends one of those commands (that

// raise 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 ss[MAX_PLY_PLUS_2];

int depth, prevBestMoveChanges;

Value bestValue, alpha, beta, delta;

memset(ss, 0, 4 * sizeof(Stack));

depth = BestMoveChanges = 0;

bestValue = delta = -VALUE_INFINITE;

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

TT.new_search();

Hist.clear();

Gain.clear();

PVSize = 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() && PVSize < 4)

PVSize = 4;

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

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

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

{

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

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

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

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

prevBestMoveChanges = BestMoveChanges; // Only sensible when PVSize == 1

BestMoveChanges = 0;

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

for (PVIdx = 0; PVIdx < PVSize; PVIdx++)

{

// Set aspiration window default width

if (depth >= 5 && abs(RootMoves[PVIdx].prevScore) < VALUE_KNOWN_WIN)

{

delta = Value(16);

alpha = RootMoves[PVIdx].prevScore - delta;

beta = RootMoves[PVIdx].prevScore + delta;

}

else

{

alpha = -VALUE_INFINITE;

beta = VALUE_INFINITE;

}

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

// research with bigger window until not failing high/low anymore.

while (true)

{

// Search starts from ss+1 to allow referencing (ss-1). This is

// needed by update gains and ss copy when splitting at Root.

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

// Bring to front the best move. 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 but 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 return immediately. Sorting and

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

// valid, although refers to previous iteration.

if (Signals.stop)

return;

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

// research, otherwise exit the loop.

if (bestValue > alpha && bestValue < beta)

break;

// Give some update (without cluttering the UI) before to research

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

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

if (abs(bestValue) >= VALUE_KNOWN_WIN)

{

alpha = -VALUE_INFINITE;

beta = VALUE_INFINITE;

}

else if (bestValue >= beta)

{

beta += delta;

delta += delta / 2;

}

else

{

Signals.failedLowAtRoot = true;

Signals.stopOnPonderhit = false;

alpha -= delta;

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 == PVSize || Time::now() - SearchTime > 3000)

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

}

// Do we need to pick now the sub-optimal best move ?

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

skill.pick_move();

if (Options["Use Search Log"])

{

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

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

<< std::endl;

}

// Do we have 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.stopOnPonderhit)

{

bool stop = false; // Local variable, not the volatile Signals.stop

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

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

TimeMgr.pv_instability(BestMoveChanges, prevBestMoveChanges);

// Stop search if most of available time is already consumed. We

// probably don't have enough time to search the first move at the

// next iteration anyway.

if (Time::now() - SearchTime > (TimeMgr.available_time() * 62) / 100)

stop = true;

// Stop search early if one move seems to be much better than others

if ( depth >= 12

&& !stop

&& PVSize == 1

&& bestValue > VALUE_MATED_IN_MAX_PLY

&& ( RootMoves.size() == 1

|| Time::now() - SearchTime > (TimeMgr.available_time() * 20) / 100))

{

Value rBeta = bestValue - 2 * PawnValueMg;

(ss+1)->excludedMove = RootMoves[0].pv[0];

(ss+1)->skipNullMove = true;

Value v = search<NonPV>(pos, ss+1, rBeta - 1, rBeta, (depth - 3) * ONE_PLY);

(ss+1)->skipNullMove = false;

(ss+1)->excludedMove = MOVE_NONE;

if (v < rBeta)

stop = true;

}

if (stop)

{

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

// keep pondering until 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, 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>

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

const bool PvNode = (NT == PV || NT == Root || NT == SplitPointPV || NT == SplitPointRoot);

const bool SpNode = (NT == SplitPointPV || NT == SplitPointNonPV || NT == SplitPointRoot);

const bool RootNode = (NT == Root || NT == SplitPointRoot);

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

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

assert(depth > DEPTH_ZERO);

Move movesSearched[64];

StateInfo st;

const TTEntry *tte;

SplitPoint* splitPoint;

Key posKey;

Move ttMove, move, excludedMove, bestMove, threatMove;

Depth ext, newDepth;

Value bestValue, value, ttValue;

Value eval, nullValue, futilityValue;

bool inCheck, givesCheck, pvMove, singularExtensionNode;

bool captureOrPromotion, dangerous, doFullDepthSearch;

int moveCount, playedMoveCount;

// Step 1. Initialize node

Thread* thisThread = pos.this_thread();

moveCount = playedMoveCount = 0;

inCheck = pos.checkers();

if (SpNode)

{

splitPoint = ss->splitPoint;

bestMove = splitPoint->bestMove;

threatMove = splitPoint->threatMove;

bestValue = splitPoint->bestValue;

tte = NULL;

ttMove = excludedMove = MOVE_NONE;

ttValue = VALUE_NONE;

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

goto split_point_start;

}

bestValue = -VALUE_INFINITE;

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

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

ss->futilityMoveCount = 0;

(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 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

// further, we will never beat 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);

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, while at non-PV nodes we check for

// a fail high/low. Biggest advantage at 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->type() == BOUND_EXACT

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

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

{

TT.refresh(tte);

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

if ( ttValue >= beta

&& ttMove

&& !pos.is_capture_or_promotion(ttMove)

&& ttMove != ss->killers[0])

{

ss->killers[1] = ss->killers[0];

ss->killers[0] = ttMove;

}

return ttValue;

}

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

if (inCheck)

ss->staticEval = ss->evalMargin = eval = VALUE_NONE;

else if (tte)

{

// Never assume anything on values stored in TT

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

||(ss->evalMargin = tte->eval_margin()) == VALUE_NONE)

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

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

if (ttValue != VALUE_NONE)

if ( ((tte->type() & BOUND_LOWER) && ttValue > eval)

|| ((tte->type() & BOUND_UPPER) && ttValue < eval))

eval = ttValue;

}

else

{

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

TT.store(posKey, VALUE_NONE, BOUND_NONE, DEPTH_NONE, MOVE_NONE,

ss->staticEval, ss->evalMargin);

}

// Update gain for the parent non-capture move given the static position

// evaluation before and after the move.

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

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

&& ss->staticEval != VALUE_NONE

&& !pos.captured_piece_type()

&& type_of(move) == NORMAL)

{

Square to = to_sq(move);

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

}

// Step 6. Razoring (is omitted in PV nodes)

if ( !PvNode

&& depth < 4 * ONE_PLY

&& !inCheck

&& eval + razor_margin(depth) < beta

&& ttMove == MOVE_NONE

&& abs(beta) < VALUE_MATE_IN_MAX_PLY

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

{

Value rbeta = beta - razor_margin(depth);

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

if (v < rbeta)

// Logically we should return (v + razor_margin(depth)), but

// surprisingly this did slightly weaker in tests.

return v;

}

// Step 7. Static null move pruning (is omitted in PV nodes)

// We're betting that the opponent doesn't have a move that will reduce

// the score by more than futility_margin(depth) if we do a null move.

if ( !PvNode

&& !ss->skipNullMove

&& depth < 4 * ONE_PLY

&& !inCheck

&& eval - futility_margin(depth, (ss-1)->futilityMoveCount) >= 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, (ss-1)->futilityMoveCount);

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

if ( !PvNode

&& !ss->skipNullMove

&& depth > ONE_PLY

&& !inCheck

&& eval >= beta

&& abs(beta) < VALUE_MATE_IN_MAX_PLY

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

{

ss->currentMove = MOVE_NULL;

// Null move dynamic reduction based on depth

Depth R = 3 * ONE_PLY + depth / 4;

// Null move dynamic reduction based on value

if (eval - PawnValueMg > beta)

R += ONE_PLY;

pos.do_null_move(st);

(ss+1)->skipNullMove = true;

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

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

(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 = search<NonPV>(pos, ss, alpha, beta, depth-R);

ss->skipNullMove = false;

if (v >= beta)

return nullValue;

}

else

{

// The null move failed low, which means that we may be faced with

// some kind of threat. If the previous move was reduced, check if

// the move that refuted the null move was somehow connected to the

// move which was reduced. If a connection is found, return a fail

// low score (which will cause the reduced move to fail high in the

// parent node, which will trigger a re-search with full depth).

threatMove = (ss+1)->currentMove;

if ( depth < 5 * ONE_PLY

&& (ss-1)->reduction

&& threatMove != MOVE_NONE

&& allows(pos, (ss-1)->currentMove, threatMove))

return beta - 1;

}

}

// Step 9. ProbCut (is omitted in PV nodes)

// 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

&& !inCheck

&& !ss->skipNullMove

&& excludedMove == MOVE_NONE

&& abs(beta) < VALUE_MATE_IN_MAX_PLY)

{

Value rbeta = beta + 200;

Depth rdepth = depth - ONE_PLY - 3 * ONE_PLY;

assert(rdepth >= ONE_PLY);

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

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

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

CheckInfo ci(pos);

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

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

{

ss->currentMove = move;

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

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

pos.undo_move(move);

if (value >= rbeta)

return value;

}

}

// Step 10. Internal iterative deepening

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

&& ttMove == MOVE_NONE

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

{

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

ss->skipNullMove = true;

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

ss->skipNullMove = false;

tte = TT.probe(posKey);

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

}

split_point_start: // At split points actual search starts from here

MovePicker mp(pos, ttMove, depth, Hist, ss, PvNode ? -VALUE_INFINITE : beta);

CheckInfo ci(pos);

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

singularExtensionNode = !RootNode

&& !SpNode

&& depth >= (PvNode ? 6 * ONE_PLY : 8 * ONE_PLY)

&& ttMove != MOVE_NONE

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

&& (tte->type() & 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 move turns out to be illegal

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

continue;

moveCount = ++splitPoint->moveCount;

splitPoint->mutex.unlock();

}

else

moveCount++;

if (RootNode)

{

Signals.firstRootMove = (moveCount == 1);

if (thisThread == Threads.main_thread() && 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.is_capture_or_promotion(move);

givesCheck = pos.move_gives_check(move, ci);

dangerous = givesCheck

|| pos.is_passed_pawn_push(move)

|| type_of(move) == CASTLE

|| ( captureOrPromotion // Entering a pawn endgame?

&& type_of(pos.piece_on(to_sq(move))) != PAWN

&& type_of(move) == NORMAL

&& ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)

- PieceValue[MG][pos.piece_on(to_sq(move))] == VALUE_ZERO));

// Step 12. Extend checks and, in PV nodes, also dangerous moves

if (PvNode && dangerous)

ext = ONE_PLY;

else if (givesCheck && pos.see_sign(move) >= 0)

ext = ONE_PLY / 2;

// 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, if result is lower than ttValue minus

// a margin then we extend ttMove.

if ( singularExtensionNode

&& move == ttMove

&& !ext

&& pos.pl_move_is_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>(pos, ss, rBeta - 1, rBeta, depth / 2);

ss->skipNullMove = false;

ss->excludedMove = MOVE_NONE;

if (value < rBeta)

ext = ONE_PLY;

}

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

newDepth = depth - ONE_PLY + ext;

// Step 13. Futility pruning (is omitted in 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[depth]

&& (!threatMove || !refutes(pos, move, threatMove)))

{

if (SpNode)

splitPoint->mutex.lock();

continue;

}

// Value based pruning

// We illogically ignore reduction condition depth >= 3*ONE_PLY for predicted depth,

// but fixing this made program slightly weaker.

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

futilityValue = ss->staticEval + ss->evalMargin + futility_margin(predictedDepth, moveCount)

+ Gain[pos.piece_moved(move)][to_sq(move)];

if (futilityValue < beta)

{

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) < 0)

{

if (SpNode)

splitPoint->mutex.lock();

continue;

}

// We have not pruned the move that will be searched, but remember how

// far in the move list we are to be more aggressive in the child node.

ss->futilityMoveCount = moveCount;

}

else

ss->futilityMoveCount = 0;

// Check for legality only before to do the move

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

{

moveCount--;

continue;

}

pvMove = PvNode && moveCount == 1;

ss->currentMove = move;

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

movesSearched[playedMoveCount++] = move;

// Step 14. Make the move

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

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

// re-searched at full depth.

if ( depth > 3 * ONE_PLY

&& !pvMove

&& !captureOrPromotion

&& !dangerous

&& move != ttMove

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

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

{

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

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

if (SpNode)

alpha = splitPoint->alpha;

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

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>(pos, ss+1, -(alpha+1), -alpha, newDepth);

}

// Only for PV nodes 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 to 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>(pos, ss+1, -beta, -alpha, newDepth);

// 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 Signals.stop is true, the search

// was aborted because the user interrupted the search or because we

// ran out of time. In this case, the return value of the search cannot

// be trusted, and we don't update the best move and/or PV.

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

return value; // To avoid returning VALUE_INFINITE

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);