From c02b3a4c7a339d212d5c6f75b3b89c926d33a800 Mon Sep 17 00:00:00 2001 From: MJZ1977 <37274752+MJZ1977@users.noreply.github.com> Date: Fri, 28 Aug 2020 12:06:36 +0200 Subject: [PATCH] Add / remove leaves from search tree ttPv add if previous leaf is in search tree and we didn't find a counter move else remove the position if the leaf is the last one in search tree. STC : https://tests.stockfishchess.org/tests/view/5f49203c3def640786115314 LLR: 2.95 (-2.94,2.94) {-0.25,1.25} Total: 29968 W: 3381 L: 3195 D: 23392 Ptnml(0-2): 146, 2432, 9671, 2560, 175 LTC : https://tests.stockfishchess.org/tests/view/5f494bea3def640786115336 LLR: 2.96 (-2.94,2.94) {0.25,1.25} Total: 84952 W: 4619 L: 4333 D: 76000 Ptnml(0-2): 86, 3765, 34481, 4065, 79 closes https://github.com/official-stockfish/Stockfish/pull/3075 Bench 3527337 --- src/search.cpp | 34 ++++++++++++++++++++++++---------- src/search.h | 1 + 2 files changed, 25 insertions(+), 10 deletions(-) diff --git a/src/search.cpp b/src/search.cpp index 77447043..a2342a3c 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -597,7 +597,7 @@ namespace { Move ttMove, move, excludedMove, bestMove; Depth extension, newDepth; Value bestValue, value, ttValue, eval, maxValue, probCutBeta; - bool ttHit, ttPv, formerPv, givesCheck, improving, didLMR, priorCapture; + bool ttHit, formerPv, givesCheck, improving, didLMR, priorCapture; bool captureOrPromotion, doFullDepthSearch, moveCountPruning, ttCapture, singularQuietLMR; Piece movedPiece; @@ -644,6 +644,7 @@ namespace { assert(0 <= ss->ply && ss->ply < MAX_PLY); (ss+1)->ply = ss->ply + 1; + (ss+1)->ttPv = false; (ss+1)->excludedMove = bestMove = MOVE_NONE; (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE; Square prevSq = to_sq((ss-1)->currentMove); @@ -667,10 +668,11 @@ namespace { ttValue = ttHit ? value_from_tt(tte->value(), ss->ply, pos.rule50_count()) : VALUE_NONE; ttMove = rootNode ? thisThread->rootMoves[thisThread->pvIdx].pv[0] : ttHit ? tte->move() : MOVE_NONE; - ttPv = PvNode || (ttHit && tte->is_pv()); - formerPv = ttPv && !PvNode; + if (!excludedMove) + ss->ttPv = PvNode || (ttHit && tte->is_pv()); + formerPv = ss->ttPv && !PvNode; - if ( ttPv + if ( ss->ttPv && depth > 12 && ss->ply - 1 < MAX_LPH && !priorCapture @@ -748,7 +750,7 @@ namespace { if ( b == BOUND_EXACT || (b == BOUND_LOWER ? value >= beta : value <= alpha)) { - tte->save(posKey, value_to_tt(value, ss->ply), ttPv, b, + tte->save(posKey, value_to_tt(value, ss->ply), ss->ttPv, b, std::min(MAX_PLY - 1, depth + 6), MOVE_NONE, VALUE_NONE); @@ -798,7 +800,7 @@ namespace { else ss->staticEval = eval = -(ss-1)->staticEval + 2 * Tempo; - tte->save(posKey, VALUE_NONE, ttPv, BOUND_NONE, DEPTH_NONE, MOVE_NONE, eval); + tte->save(posKey, VALUE_NONE, ss->ttPv, BOUND_NONE, DEPTH_NONE, MOVE_NONE, eval); } // Step 7. Razoring (~1 Elo) @@ -824,7 +826,7 @@ namespace { && (ss-1)->statScore < 22977 && eval >= beta && eval >= ss->staticEval - && ss->staticEval >= beta - 30 * depth - 28 * improving + 84 * ttPv + 182 + && ss->staticEval >= beta - 30 * depth - 28 * improving + 84 * ss->ttPv + 182 && !excludedMove && pos.non_pawn_material(us) && (ss->ply >= thisThread->nmpMinPly || us != thisThread->nmpColor)) @@ -898,6 +900,8 @@ namespace { assert(probCutBeta < VALUE_INFINITE); MovePicker mp(pos, ttMove, probCutBeta - ss->staticEval, &captureHistory); int probCutCount = 0; + bool ttPv = ss->ttPv; + ss->ttPv = false; while ( (move = mp.next_move()) != MOVE_NONE && probCutCount < 2 + 2 * cutNode) @@ -938,6 +942,7 @@ namespace { return value; } } + ss->ttPv = ttPv; } // Step 11. If the position is not in TT, decrease depth by 2 @@ -1180,7 +1185,7 @@ moves_loop: // When in check, search starts from here r++; // Decrease reduction if position is or has been on the PV (~10 Elo) - if (ttPv) + if (ss->ttPv) r -= 2; if (moveCountPruning && !formerPv) @@ -1209,7 +1214,7 @@ moves_loop: // When in check, search starts from here // hence break make_move(). (~2 Elo) else if ( type_of(move) == NORMAL && !pos.see_ge(reverse_move(move))) - r -= 2 + ttPv - (type_of(movedPiece) == PAWN); + r -= 2 + ss->ttPv - (type_of(movedPiece) == PAWN); ss->statScore = thisThread->mainHistory[us][from_to(move)] + (*contHist[0])[movedPiece][to_sq(move)] @@ -1387,8 +1392,17 @@ moves_loop: // When in check, search starts from here if (PvNode) bestValue = std::min(bestValue, maxValue); + // If no good move is found and the previous position was ttPv, then the previous + // opponent move is probably good and the new position is added to the search tree. + if (bestValue <= alpha) + ss->ttPv = ss->ttPv || ((ss-1)->ttPv && depth > 3); + // Otherwise, a counter move has been found and if the position is the last leaf + // in the search tree, remove the position from the search tree. + else if (depth > 3) + ss->ttPv = ss->ttPv && (ss+1)->ttPv; + if (!excludedMove && !(rootNode && thisThread->pvIdx)) - tte->save(posKey, value_to_tt(bestValue, ss->ply), ttPv, + tte->save(posKey, value_to_tt(bestValue, ss->ply), ss->ttPv, bestValue >= beta ? BOUND_LOWER : PvNode && bestMove ? BOUND_EXACT : BOUND_UPPER, depth, bestMove, ss->staticEval); diff --git a/src/search.h b/src/search.h index 2554f3fb..79085189 100644 --- a/src/search.h +++ b/src/search.h @@ -48,6 +48,7 @@ struct Stack { int statScore; int moveCount; bool inCheck; + bool ttPv; }; -- 2.39.2