Okay, let's analyze a section and propose a patch.

  1. Selected Area: Step 8, Futility Pruning (child node).
  2. Current Implementation:
    1
    2
    3
    4
    5
    6
    7
    8
    // Step 8. Futility pruning: child node
    // The depth condition is important for mate finding.
    if (!ss->ttPv && depth < 14
        && eval - futility_margin(depth, cutNode && !ss->ttHit, improving, opponentWorsening)
               - (ss - 1)->statScore / 301 + 37 - std::abs(correctionValue) / 139878
             >= beta
        && eval >= beta && (!ttData.move || ttCapture) && !is_loss(beta) && !is_win(eval))
        return beta + (eval - beta) / 3;
    
    This code performs futility pruning at shallow depths in non-PV nodes. It estimates if the current static evaluation (eval), adjusted by various factors (futility margin, previous move stats, correction history), is so high relative to beta that no move is likely to raise alpha above beta. A crucial condition is (!ttData.move || ttCapture). This prevents pruning if the transposition table suggests a quiet move (ttData.move exists and !ttCapture). The rationale is that the TT move might be the only move saving the position from failing low, even if the static eval looks high.
  3. Analysis and Improvement Idea:
    The (!ttData.move || ttCapture) condition is a safeguard against pruning a critical quiet move suggested by the TT. However, the reliability of the TT move depends on the depth at which it was stored. If the TT entry has a very shallow depth (ttData.depth) compared to the current search depth (depth), its suggested quiet move might be less trustworthy or less relevant at the current depth. We could potentially allow futility pruning even when a quiet TT move exists, if that TT entry is significantly shallower than the current search depth. This might allow pruning in cases where a shallow, potentially outdated quiet TT move prevents it, while still respecting deeper TT entries.

    Let's relax the condition slightly: allow pruning if the TT move is quiet (!ttCapture) but the TT entry depth (ttData.depth) is considerably less than the current search depth (depth). For example, if ttData.depth < depth - 4.

    The original condition is (!ttData.move || ttCapture).
    The modified condition would be (!ttData.move || ttCapture || (ttData.move && !ttCapture && ttData.depth < depth - 4)).
    This simplifies logically to (ttCapture || !ttData.move || ttData.depth < depth - 4).

  4. Final Patch:

search.cpp:

// Step 8. Futility pruning: child node
// The depth condition is important for mate finding.
if (!ss->ttPv && depth < 14
    && eval - futility_margin(depth, cutNode && !ss->ttHit, improving, opponentWorsening)
           - (ss - 1)->statScore / 301 + 37 - std::abs(correctionValue) / 139878
         >= beta
    && eval >= beta && (!ttData.move || ttCapture) && !is_loss(beta) && !is_win(eval))
    return beta + (eval - beta) / 3;

// Step 9. Null move search with verification search

Improved search.cpp:

// Step 8. Futility pruning: child node
// The depth condition is important for mate finding.
if (!ss->ttPv && depth < 14
    && eval - futility_margin(depth, cutNode && !ss->ttHit, improving, opponentWorsening)
           - (ss - 1)->statScore / 301 + 37 - std::abs(correctionValue) / 139878
         >= beta
    && eval >= beta && (ttCapture || !ttData.move || ttData.depth < depth - 4) && !is_loss(beta) && !is_win(eval))
    return beta + (eval - beta) / 3;

// Step 9. Null move search with verification search
Edit

Pub: 26 Apr 2025 13:59 UTC

Views: 105