#include <algorithm>
#include <cassert>
+#include <cfloat>
#include <cmath>
#include <cstring>
#include <iostream>
// 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 };
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[2][32]; // [improving][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;
+ inline Value futility_margin(Depth d) {
+ return Value(100 * int(d));
}
// Reduction lookup tables (initialized at startup) and their access function
if (Reductions[0][0][hd][mc] > 2 * ONE_PLY)
Reductions[0][0][hd][mc] += ONE_PLY;
- }
- // 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);
+ 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(3 + 0.3 * pow(double(d ), 1.8)) * 3/4 + (2 < d && d < 5);
- FutilityMoveCounts[1][d] = int(3 + 0.3 * pow(double(d + 0.98), 1.8));
+ FutilityMoveCounts[0][d] = int(2.4 + 0.222 * pow(d + 0.0, 1.8));
+ FutilityMoveCounts[1][d] = int(3.0 + 0.3 * pow(d + 0.98, 1.8));
}
}
Threads[i]->maxPly = 0;
Threads.sleepWhileIdle = Options["Idle Threads Sleep"];
-
- // 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->run = true;
Threads.timer->notify_one(); // Wake up the recurring timer
id_loop(RootPos); // Let's start searching !
- Threads.timer->msec = 0; // Stop the timer
+ Threads.timer->run = false; // Stop the timer
Threads.sleepWhileIdle = true; // Send idle threads to sleep
if (Options["Write Search Log"])
RootMoves[i].prevScore = RootMoves[i].score;
// MultiPV loop. We perform a full root search for each PV line
- for (PVIdx = 0; PVIdx < PVSize; ++PVIdx)
+ for (PVIdx = 0; PVIdx < PVSize && !Signals.stop; ++PVIdx)
{
// Reset aspiration window starting size
if (depth >= 5)
for (size_t i = 0; i <= PVIdx; ++i)
RootMoves[i].insert_pv_in_tt(pos);
- // If search has been stopped return immediately. Sorting and
+ // If search has been stopped break immediately. Sorting and
// writing PV back to TT is safe becuase RootMoves is still
// valid, although refers to previous iteration.
if (Signals.stop)
- return;
+ break;
// When failing high/low give some update (without cluttering
// the UI) before to research.
Signals.stop = true;
// Do we have time for the next iteration? Can we stop searching now?
- if (Limits.use_time_management() && !Signals.stopOnPonderhit)
+ if (Limits.use_time_management() && !Signals.stop && !Signals.stopOnPonderhit)
{
bool stop = false; // Local variable, not the volatile Signals.stop
// Stop search early if one move seems to be much better than others
if ( depth >= 12
+ && BestMoveChanges <= DBL_EPSILON
&& !stop
&& PVSize == 1
&& bestValue > VALUE_MATED_IN_MAX_PLY
SplitPoint* splitPoint;
Key posKey;
Move ttMove, move, excludedMove, bestMove, threatMove;
- Depth ext, newDepth;
- Value bestValue, value, ttValue;
- Value eval, nullValue, futilityValue;
+ Depth ext, newDepth, predictedDepth;
+ Value bestValue, value, ttValue, eval, nullValue, futilityValue;
bool inCheck, givesCheck, pvMove, singularExtensionNode, improving;
bool captureOrPromotion, dangerous, doFullDepthSearch;
int moveCount, quietCount;
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;
// Step 5. Evaluate the position statically and update parent's gain statistics
if (inCheck)
{
- ss->staticEval = ss->evalMargin = eval = VALUE_NONE;
+ 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
- ||(ss->evalMargin = tte->eval_margin()) == VALUE_NONE)
- eval = ss->staticEval = evaluate(pos, ss->evalMargin);
+ 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)
}
else
{
- eval = ss->staticEval = evaluate(pos, ss->evalMargin);
- TT.store(posKey, VALUE_NONE, BOUND_NONE, DEPTH_NONE, MOVE_NONE,
- ss->staticEval, ss->evalMargin);
+ eval = ss->staticEval = evaluate(pos);
+ TT.store(posKey, VALUE_NONE, BOUND_NONE, DEPTH_NONE, MOVE_NONE, ss->staticEval);
}
- // Update gain for the parent non-capture move given the static position
- // evaluation before and after the move.
if ( !pos.captured_piece_type()
&& ss->staticEval != VALUE_NONE
&& (ss-1)->staticEval != VALUE_NONE
return v;
}
- // Step 7. Static null move pruning (skipped when in check)
- // 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.
+ // Step 7. Futility pruning: child node (skipped when in check)
if ( !PvNode
&& !ss->skipNullMove
- && depth < 4 * ONE_PLY
- && eval - futility_margin(depth, (ss-1)->futilityMoveCount) >= beta
+ && 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, (ss-1)->futilityMoveCount);
+ return eval - futility_margin(depth);
// Step 8. Null move search with verification search (is omitted in PV nodes)
if ( !PvNode
// 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)
+ // Step 13. Pruning at shallow depth (exclude PV nodes)
if ( !PvNode
&& !captureOrPromotion
&& !inCheck
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>(improving, depth, moveCount);
- futilityValue = ss->staticEval + ss->evalMargin + futility_margin(predictedDepth, moveCount)
- + Gains[pos.moved_piece(move)][to_sq(move)];
+ predictedDepth = newDepth - reduction<PvNode>(improving, depth, moveCount);
- if (futilityValue < beta)
+ // Futility pruning: parent node
+ if (predictedDepth < 7 * ONE_PLY)
{
- bestValue = std::max(bestValue, futilityValue);
+ futilityValue = ss->staticEval + futility_margin(predictedDepth)
+ + Value(128) + Gains[pos.moved_piece(move)][to_sq(move)];
- if (SpNode)
+ if (futilityValue <= alpha)
{
- splitPoint->mutex.lock();
- if (bestValue > splitPoint->bestValue)
- splitPoint->bestValue = bestValue;
+ bestValue = std::max(bestValue, futilityValue);
+
+ if (SpNode)
+ {
+ splitPoint->mutex.lock();
+ if (bestValue > splitPoint->bestValue)
+ splitPoint->bestValue = bestValue;
+ }
+ continue;
}
- continue;
}
// Prune moves with negative SEE at low depths
- if ( predictedDepth < 4 * ONE_PLY
- && pos.see_sign(move) < 0)
+ 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.legal(move, ci.pinned))
{
- --moveCount;
+ moveCount--;
continue;
}
TT.store(posKey, value_to_tt(bestValue, ss->ply),
bestValue >= beta ? BOUND_LOWER :
PvNode && bestMove ? BOUND_EXACT : BOUND_UPPER,
- depth, bestMove, ss->staticEval, ss->evalMargin);
+ depth, bestMove, ss->staticEval);
// Quiet best move: update killers, history and countermoves
if ( bestValue >= beta
// Evaluate the position statically
if (InCheck)
{
- ss->staticEval = ss->evalMargin = VALUE_NONE;
+ ss->staticEval = VALUE_NONE;
bestValue = futilityBase = -VALUE_INFINITE;
}
else
if (tte)
{
// Never assume anything on values stored in TT
- if ( (ss->staticEval = bestValue = tte->eval_value()) == VALUE_NONE
- ||(ss->evalMargin = tte->eval_margin()) == VALUE_NONE)
- ss->staticEval = bestValue = evaluate(pos, ss->evalMargin);
+ if ((ss->staticEval = bestValue = tte->eval_value()) == VALUE_NONE)
+ ss->staticEval = bestValue = evaluate(pos);
// Can ttValue be used as a better position evaluation?
if (ttValue != VALUE_NONE)
bestValue = ttValue;
}
else
- ss->staticEval = bestValue = evaluate(pos, ss->evalMargin);
+ ss->staticEval = bestValue = evaluate(pos);
// Stand pat. Return immediately if static value is at least beta
if (bestValue >= beta)
{
if (!tte)
TT.store(pos.key(), value_to_tt(bestValue, ss->ply), BOUND_LOWER,
- DEPTH_NONE, MOVE_NONE, ss->staticEval, ss->evalMargin);
+ DEPTH_NONE, MOVE_NONE, ss->staticEval);
return bestValue;
}
if (PvNode && bestValue > alpha)
alpha = bestValue;
- futilityBase = bestValue + ss->evalMargin + Value(128);
+ futilityBase = bestValue + Value(128);
}
// Initialize a MovePicker object for the current position, and prepare
else // Fail high
{
TT.store(posKey, value_to_tt(value, ss->ply), BOUND_LOWER,
- ttDepth, move, ss->staticEval, ss->evalMargin);
+ ttDepth, move, ss->staticEval);
return value;
}
TT.store(posKey, value_to_tt(bestValue, ss->ply),
PvNode && bestValue > oldAlpha ? BOUND_EXACT : BOUND_UPPER,
- ttDepth, bestMove, ss->staticEval, ss->evalMargin);
+ ttDepth, bestMove, ss->staticEval);
assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
// We exclude the trivial case where a sliding piece does in two moves what
// it could do in one move: eg. Ra1a2, Ra2a3.
if ( m2to == m1from
- || (m1to == m2from && !squares_aligned(m1from, m2from, m2to)))
+ || (m1to == m2from && !aligned(m1from, m2from, m2to)))
return true;
// Second one moves through the square vacated by first one
} while ( tte
&& pos.pseudo_legal(m = tte->move()) // Local copy, TT could change
- && pos.legal(m, pos.pinned_pieces())
+ && pos.legal(m, pos.pinned_pieces(pos.side_to_move()))
&& ply < MAX_PLY
&& (!pos.is_draw() || ply < 2));
tte = TT.probe(pos.key());
if (!tte || tte->move() != pv[ply]) // Don't overwrite correct entries
- TT.store(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[ply], VALUE_NONE, VALUE_NONE);
+ TT.store(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[ply], VALUE_NONE);
assert(MoveList<LEGAL>(pos).contains(pv[ply]));
&& !Signals.failedLowAtRoot
&& elapsed > TimeMgr.available_time();
- bool noMoreTime = elapsed > TimeMgr.maximum_time() - 2 * TimerResolution
+ bool noMoreTime = elapsed > TimeMgr.maximum_time() - 2 * TimerThread::Resolution
|| stillAtFirstMove;
if ( (Limits.use_time_management() && noMoreTime)