Move best = MOVE_NONE;
};
+ // Breadcrumbs are used to mark nodes as being searched by a given thread.
+ struct Breadcrumb {
+ std::atomic<Thread*> thread;
+ std::atomic<Key> key;
+ };
+ std::array<Breadcrumb, 1024> breadcrumbs;
+
+ // ThreadHolding keeps track of which thread left breadcrumbs at the given node for potential reductions.
+ // A free node will be marked upon entering the moves loop, and unmarked upon leaving that loop, by the ctor/dtor of this struct.
+ struct ThreadHolding {
+ explicit ThreadHolding(Thread* thisThread, Key posKey, int ply) {
+ location = ply < 8 ? &breadcrumbs[posKey & (breadcrumbs.size() - 1)] : nullptr;
+ otherThread = false;
+ owning = false;
+ if (location)
+ {
+ // see if another already marked this location, if not, mark it ourselves.
+ Thread* tmp = (*location).thread.load(std::memory_order_relaxed);
+ if (tmp == nullptr)
+ {
+ (*location).thread.store(thisThread, std::memory_order_relaxed);
+ (*location).key.store(posKey, std::memory_order_relaxed);
+ owning = true;
+ }
+ else if ( tmp != thisThread
+ && (*location).key.load(std::memory_order_relaxed) == posKey)
+ otherThread = true;
+ }
+ }
+
+ ~ThreadHolding() {
+ if (owning) // free the marked location.
+ (*location).thread.store(nullptr, std::memory_order_relaxed);
+ }
+
+ bool marked() { return otherThread; }
+
+ private:
+ Breadcrumb* location;
+ bool otherThread, owning;
+ };
+
template <NodeType NT>
Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode);
bestValue = delta = alpha = -VALUE_INFINITE;
beta = VALUE_INFINITE;
- size_t multiPV = Options["MultiPV"];
- Skill skill(Options["Skill Level"]);
+ multiPV = Options["MultiPV"];
+ // Pick integer skill levels, but non-deterministically round up or down
+ // such that the average integer skill corresponds to the input floating point one.
+ PRNG rng(now());
+ int intLevel = int(Options["Skill Level"]) +
+ ((Options["Skill Level"] - int(Options["Skill Level"])) * 1024 > rng.rand<unsigned>() % 1024 ? 1 : 0);
+ Skill skill(intLevel);
// When playing with strength handicap enable MultiPV search that we will
// use behind the scenes to retrieve a set of possible moves.
}
else if (ttHit)
{
- // Never assume anything on values stored in TT
+ // Never assume anything about values stored in TT
ss->staticEval = eval = tte->eval();
if (eval == VALUE_NONE)
ss->staticEval = eval = evaluate(pos);
moveCountPruning = false;
ttCapture = ttMove && pos.capture_or_promotion(ttMove);
+ // Mark this node as being searched.
+ ThreadHolding th(thisThread, posKey, ss->ply);
+
// Step 12. Loop through all pseudo-legal moves until no moves remain
// or a beta cutoff occurs.
while ((move = mp.next_move(moveCountPruning)) != MOVE_NONE)
sync_cout << "info depth " << depth / ONE_PLY
<< " currmove " << UCI::move(move, pos.is_chess960())
<< " currmovenumber " << moveCount + thisThread->pvIdx << sync_endl;
+
+ // In MultiPV mode also skip moves which will be searched later as PV moves
+ if (rootNode && std::count(thisThread->rootMoves.begin() + thisThread->pvIdx + 1,
+ thisThread->rootMoves.begin() + thisThread->multiPV, move))
+ continue;
+
if (PvNode)
(ss+1)->pv = nullptr;
// Multi-cut pruning
// Our ttMove is assumed to fail high, and now we failed high also on a reduced
// search without the ttMove. So we assume this expected Cut-node is not singular,
- // that is multiple moves fail high, and we can prune the whole subtree by returning
- // the hard beta bound.
- else if (cutNode && singularBeta > beta)
- return beta;
+ // that multiple moves fail high, and we can prune the whole subtree by returning
+ // a soft bound.
+ else if ( eval >= beta
+ && singularBeta >= beta)
+ return singularBeta;
}
// Check extension (~2 Elo)
else if ( givesCheck
- && (pos.blockers_for_king(~us) & from_sq(move) || pos.see_ge(move)))
+ && (pos.is_discovery_check_on_king(~us, move) || pos.see_ge(move)))
extension = ONE_PLY;
// Castling extension
else if ( PvNode
&& pos.rule50_count() > 18
&& depth < 3 * ONE_PLY
- && ss->ply < 3 * thisThread->rootDepth / ONE_PLY) // To avoid too deep searches
+ && ++thisThread->shuffleExts < thisThread->nodes.load(std::memory_order_relaxed) / 4) // To avoid too many extensions
extension = ONE_PLY;
// Passed pawn extension
&& !givesCheck
&& (!pos.advanced_pawn_push(move) || pos.non_pawn_material(~us) > BishopValueMg))
{
- // Move count based pruning (~30 Elo)
+ // Move count based pruning
if (moveCountPruning)
continue;
if (!pos.see_ge(move, Value(-29 * lmrDepth * lmrDepth)))
continue;
}
- else if ((!givesCheck || !extension)
- && !pos.see_ge(move, -PawnValueEg * (depth / ONE_PLY))) // (~20 Elo)
+ else if ( (!givesCheck || !extension)
+ && !pos.see_ge(move, -PawnValueEg * (depth / ONE_PLY))) // (~20 Elo)
continue;
}
{
Depth r = reduction(improving, depth, moveCount);
+ // Reduction if other threads are searching this position.
+ if (th.marked())
+ r += ONE_PLY;
+
// Decrease reduction if position is or has been on the PV
if (ttPv)
r -= 2 * ONE_PLY;
r += ONE_PLY;
// Decrease/increase reduction for moves with a good/bad history (~30 Elo)
- r -= ss->statScore / 20000 * ONE_PLY;
+ r -= ss->statScore / 16384 * ONE_PLY;
}
Depth d = clamp(newDepth - r, ONE_PLY, newDepth);
{
if (ttHit)
{
- // Never assume anything on values stored in TT
+ // Never assume anything about values stored in TT
if ((ss->staticEval = bestValue = tte->eval()) == VALUE_NONE)
ss->staticEval = bestValue = evaluate(pos);
if (dtz_available || rootMoves[0].tbScore <= VALUE_DRAW)
Cardinality = 0;
}
+ else
+ {
+ // Clean up if root_probe() and root_probe_wdl() have failed
+ for (auto& m : rootMoves)
+ m.tbRank = 0;
+ }
}
projects / stockfish / blobdiff