From 3b8f66f8accefe86db9296fa276e4b33cdc450e2 Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Sun, 9 Jun 2013 09:43:04 +0200 Subject: [PATCH] Introduce Cut/All node definitions Follow Don Dailey definition of cut/all node: "If the previous node was a cut node, we consider this an ALL node. The only exception is for PV nodes which are a special case of ALL nodes. In the PVS framework, the first zero width window searched from a PV node is by our definition a CUT node and if you have to do a re-search then it is suddenly promoted to a PV nodes (as per PVS search) and only then can the cut and all nodes swap positions. In other words, these internal search failures can force the status of every node in the subtree to swap if it propagates back to the last PV nodes." http://talkchess.com/forum/viewtopic.php?topic_view=threads&p=519741&t=47577 With this definition we have an hit rate higher than 90% on: if (!PvNode && depth > 4 * ONE_PLY) dbg_hit_on_c(cutNode, (bestValue >= beta)); And an hit rate of just 28% on: if (!PvNode && depth > 4 * ONE_PLY) dbg_hit_on_c(!cutNode, (bestValue >= beta)); No functional change. --- src/search.cpp | 32 ++++++++++++++++---------------- src/thread.cpp | 7 ++++--- src/thread.h | 3 ++- 3 files changed, 22 insertions(+), 20 deletions(-) diff --git a/src/search.cpp b/src/search.cpp index e9c0ad26..4ca9e9b8 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -91,7 +91,7 @@ namespace { CountermovesStats Countermoves; template - Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth); + Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode); template Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth); @@ -349,7 +349,7 @@ namespace { // research with bigger window until not failing high/low anymore. while (true) { - bestValue = search(pos, ss, alpha, beta, depth * ONE_PLY); + bestValue = search(pos, ss, alpha, beta, depth * ONE_PLY, false); // Bring to front the best move. It is critical that sorting is // done with a stable algorithm because all the values but the first @@ -455,7 +455,7 @@ namespace { Value rBeta = bestValue - 2 * PawnValueMg; ss->excludedMove = RootMoves[0].pv[0]; ss->skipNullMove = true; - Value v = search(pos, ss, rBeta - 1, rBeta, (depth - 3) * ONE_PLY); + Value v = search(pos, ss, rBeta - 1, rBeta, (depth - 3) * ONE_PLY, true); ss->skipNullMove = false; ss->excludedMove = MOVE_NONE; @@ -485,7 +485,7 @@ namespace { // here: This is taken care of after we return from the split point. template - Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth) { + Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode) { const bool PvNode = (NT == PV || NT == Root || NT == SplitPointPV || NT == SplitPointRoot); const bool SpNode = (NT == SplitPointPV || NT == SplitPointNonPV || NT == SplitPointRoot); @@ -679,7 +679,7 @@ namespace { pos.do_null_move(st); (ss+1)->skipNullMove = true; nullValue = depth-R < ONE_PLY ? -qsearch(pos, ss+1, -beta, -alpha, DEPTH_ZERO) - : - search(pos, ss+1, -beta, -alpha, depth-R); + : - search(pos, ss+1, -beta, -alpha, depth-R, !cutNode); (ss+1)->skipNullMove = false; pos.undo_null_move(); @@ -694,7 +694,7 @@ namespace { // Do verification search at high depths ss->skipNullMove = true; - Value v = search(pos, ss, alpha, beta, depth-R); + Value v = search(pos, ss, alpha, beta, depth-R, false); ss->skipNullMove = false; if (v >= beta) @@ -744,7 +744,7 @@ namespace { { ss->currentMove = move; pos.do_move(move, st, ci, pos.move_gives_check(move, ci)); - value = -search(pos, ss+1, -rbeta, -rbeta+1, rdepth); + value = -search(pos, ss+1, -rbeta, -rbeta+1, rdepth, !cutNode); pos.undo_move(move); if (value >= rbeta) return value; @@ -759,7 +759,7 @@ namespace { Depth d = depth - 2 * ONE_PLY - (PvNode ? DEPTH_ZERO : depth / 4); ss->skipNullMove = true; - search(pos, ss, alpha, beta, d); + search(pos, ss, alpha, beta, d, true); ss->skipNullMove = false; tte = TT.probe(posKey); @@ -855,7 +855,7 @@ split_point_start: // At split points actual search starts from here Value rBeta = ttValue - int(depth); ss->excludedMove = move; ss->skipNullMove = true; - value = search(pos, ss, rBeta - 1, rBeta, depth / 2); + value = search(pos, ss, rBeta - 1, rBeta, depth / 2, cutNode); ss->skipNullMove = false; ss->excludedMove = MOVE_NONE; @@ -955,7 +955,7 @@ split_point_start: // At split points actual search starts from here if (SpNode) alpha = splitPoint->alpha; - value = -search(pos, ss+1, -(alpha+1), -alpha, d); + value = -search(pos, ss+1, -(alpha+1), -alpha, d, true); doFullDepthSearch = (value > alpha && ss->reduction != DEPTH_ZERO); ss->reduction = DEPTH_ZERO; @@ -972,7 +972,7 @@ split_point_start: // At split points actual search starts from here value = newDepth < ONE_PLY ? givesCheck ? -qsearch(pos, ss+1, -(alpha+1), -alpha, DEPTH_ZERO) : -qsearch(pos, ss+1, -(alpha+1), -alpha, DEPTH_ZERO) - : - search(pos, ss+1, -(alpha+1), -alpha, newDepth); + : - search(pos, ss+1, -(alpha+1), -alpha, newDepth, !cutNode); } // Only for PV nodes do a full PV search on the first move or after a fail @@ -982,7 +982,7 @@ split_point_start: // At split points actual search starts from here value = newDepth < ONE_PLY ? givesCheck ? -qsearch(pos, ss+1, -beta, -alpha, DEPTH_ZERO) : -qsearch(pos, ss+1, -beta, -alpha, DEPTH_ZERO) - : - search(pos, ss+1, -beta, -alpha, newDepth); + : - search(pos, ss+1, -beta, -alpha, newDepth, false); // Step 17. Undo move pos.undo_move(move); @@ -1057,7 +1057,7 @@ split_point_start: // At split points actual search starts from here assert(bestValue < beta); thisThread->split(pos, ss, alpha, beta, &bestValue, &bestMove, - depth, threatMove, moveCount, &mp, NT); + depth, threatMove, moveCount, &mp, NT, cutNode); if (bestValue >= beta) break; } @@ -1705,13 +1705,13 @@ void Thread::idle_loop() { switch (sp->nodeType) { case Root: - search(pos, ss, sp->alpha, sp->beta, sp->depth); + search(pos, ss, sp->alpha, sp->beta, sp->depth, sp->cutNode); break; case PV: - search(pos, ss, sp->alpha, sp->beta, sp->depth); + search(pos, ss, sp->alpha, sp->beta, sp->depth, sp->cutNode); break; case NonPV: - search(pos, ss, sp->alpha, sp->beta, sp->depth); + search(pos, ss, sp->alpha, sp->beta, sp->depth, sp->cutNode); break; default: assert(false); diff --git a/src/thread.cpp b/src/thread.cpp index b7bead9f..2b09a69f 100644 --- a/src/thread.cpp +++ b/src/thread.cpp @@ -252,7 +252,7 @@ Thread* ThreadPool::available_slave(Thread* master) const { template void Thread::split(Position& pos, Stack* ss, Value alpha, Value beta, Value* bestValue, Move* bestMove, Depth depth, Move threatMove, int moveCount, - MovePicker* movePicker, int nodeType) { + MovePicker* movePicker, int nodeType, bool cutNode) { assert(pos.pos_is_ok()); assert(*bestValue <= alpha && alpha < beta && beta <= VALUE_INFINITE); @@ -274,6 +274,7 @@ void Thread::split(Position& pos, Stack* ss, Value alpha, Value beta, Value* bes sp.alpha = alpha; sp.beta = beta; sp.nodeType = nodeType; + sp.cutNode = cutNode; sp.movePicker = movePicker; sp.moveCount = moveCount; sp.pos = &pos; @@ -339,8 +340,8 @@ void Thread::split(Position& pos, Stack* ss, Value alpha, Value beta, Value* bes } // Explicit template instantiations -template void Thread::split(Position&, Stack*, Value, Value, Value*, Move*, Depth, Move, int, MovePicker*, int); -template void Thread::split< true>(Position&, Stack*, Value, Value, Value*, Move*, Depth, Move, int, MovePicker*, int); +template void Thread::split(Position&, Stack*, Value, Value, Value*, Move*, Depth, Move, int, MovePicker*, int, bool); +template void Thread::split< true>(Position&, Stack*, Value, Value, Value*, Move*, Depth, Move, int, MovePicker*, int, bool); // wait_for_think_finished() waits for main thread to go to sleep then returns diff --git a/src/thread.h b/src/thread.h index fbd3b7f4..46c40d9b 100644 --- a/src/thread.h +++ b/src/thread.h @@ -68,6 +68,7 @@ struct SplitPoint { Value beta; int nodeType; Move threatMove; + bool cutNode; // Const pointers to shared data MovePicker* movePicker; @@ -103,7 +104,7 @@ struct Thread { template void split(Position& pos, Search::Stack* ss, Value alpha, Value beta, Value* bestValue, Move* bestMove, - Depth depth, Move threatMove, int moveCount, MovePicker* movePicker, int nodeType); + Depth depth, Move threatMove, int moveCount, MovePicker* movePicker, int nodeType, bool cutNode); SplitPoint splitPoints[MAX_SPLITPOINTS_PER_THREAD]; Material::Table materialTable; -- 2.39.5