From 626b1f8c6adc6c6b1bd7dc30109cd7fa5f3c44d8 Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Sat, 10 Apr 2010 10:32:17 +0100 Subject: [PATCH] Avoid TT cutoffs at root of null zugzwang verification This patch fixes an issue with zugzwang well explained by Tord: "Assume that a zugzwang position occurs at iteration N, at a search depth d, with d < 6*OnePly. The null move search fails high, and no verification search is done, because the depth is too small. The position gets stored in the transposition table with a good score and a depth of d. Now, consider what happens when the same position occurs at iteration N+1, this time with a depth of d+OnePly (i.e. one ply deeper than at the previous iteration). Once again, the null move search fails high. The point is that the verification search will also fail high, because of an instant transposition table cutoff caused by the value stored in the TT during the previous iteration." With this patch we simply do not allow TT cutoffs at the root node of a null move verification search if the TT value was found by a null search. Signed-off-by: Marco Costalba --- src/search.cpp | 18 +++++++++++------- 1 file changed, 11 insertions(+), 7 deletions(-) diff --git a/src/search.cpp b/src/search.cpp index cd874ff8..3f843641 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -294,7 +294,7 @@ namespace { Depth extension(const Position&, Move, bool, bool, bool, bool, bool, bool*); bool ok_to_do_nullmove(const Position& pos); bool ok_to_prune(const Position& pos, Move m, Move threat); - bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply); + bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply, bool allowNullmove); Value refine_eval(const TTEntry* tte, Value defaultEval, int ply); void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount); void update_killers(Move m, SearchStack& ss); @@ -1299,7 +1299,7 @@ namespace { tte = TT.retrieve(posKey); ttMove = (tte ? tte->move() : MOVE_NONE); - if (tte && ok_to_use_TT(tte, depth, beta, ply)) + if (tte && ok_to_use_TT(tte, depth, beta, ply, allowNullmove)) { ss[ply].currentMove = ttMove; // Can be MOVE_NONE return value_from_tt(tte->value(), ply); @@ -1625,7 +1625,7 @@ namespace { tte = TT.retrieve(pos.get_key()); ttMove = (tte ? tte->move() : MOVE_NONE); - if (!pvNode && tte && ok_to_use_TT(tte, depth, beta, ply)) + if (!pvNode && tte && ok_to_use_TT(tte, depth, beta, ply, true)) { assert(tte->type() != VALUE_TYPE_EVAL); @@ -2306,14 +2306,18 @@ namespace { } - // ok_to_use_TT() returns true if a transposition table score - // can be used at a given point in search. + // ok_to_use_TT() returns true if a transposition table score can be used at a + // given point in search. To avoid zugzwang issues TT cutoffs at the root node + // of a null move verification search are not allowed if the TT value was found + // by a null search, this is implemented testing allowNullmove and TT entry type. - bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) { + bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply, bool allowNullmove) { Value v = value_from_tt(tte->value(), ply); - return ( tte->depth() >= depth + return (allowNullmove || !(tte->type() & VALUE_TYPE_NULL)) + + && ( tte->depth() >= depth || v >= Max(value_mate_in(PLY_MAX), beta) || v < Min(value_mated_in(PLY_MAX), beta)) -- 2.39.2