Pruning based on TT score from a shallower depth

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

kelseyde123
Posts: 11
Joined: Fri Oct 06, 2023 1:10 am
Full name: Dan Kelsey

Pruning based on TT score from a shallower depth

Post by kelseyde123 »

I'm not sure if there's already a name for this idea, but here goes.

If we get a TT hit, we typically only re-use the TT score and exit early in three conditions:

1) TT flag is exact,
2) TT flag == fail-low, and TT score is <= current alpha, or
3) TT flag == fail-high, and TT score is >= current beta.

In my engine Calvin it looks like this:

Code: Select all

return entry.getDepth() >= depth &&
          ((entry.getFlag().equals(HashFlag.EXACT)) ||
          (entry.getFlag().equals(HashFlag.UPPER) && entry.getScore() <= alpha) ||
          (entry.getFlag().equals(HashFlag.LOWER) && entry.getScore() >= beta));
But could we also just re-use TT scores with a shallower depth, providing their scores were far outside our alpha-beta window by some margin?

For example, say I come across a position that was previously searched to a shallower depth, but that has a score 500 cp lower than my current alpha, or 500 cp higher than my current beta. Is it not a reasonable gamble to assume that there's little point searching any further, and cutting off early?

I'm wondering if other folks have already tried this idea before, and if so, what kind of results did you see?

Thanks!
Viz
Posts: 219
Joined: Tue Apr 09, 2024 6:24 am
Full name: Michael Chaly

Re: Pruning based on TT score from a shallower depth

Post by Viz »

Was tried, failed somewhat miserably.
Smth like this works in ethereal IIRC.
Also note, in stockfish for w/e reason > is better than >= for depth condition like this, but it's sf specific thing.
User avatar
j.t.
Posts: 252
Joined: Wed Jun 16, 2021 2:08 am
Location: Berlin
Full name: Jost Triller

Re: Pruning based on TT score from a shallower depth

Post by j.t. »

kelseyde123 wrote: Wed May 29, 2024 1:50 am But could we also just re-use TT scores with a shallower depth, providing their scores were far outside our alpha-beta window by some margin?
I do it like this: https://gitlab.com/tsoj/Nalwald/-/blob/ ... heads#L185

Code: Select all

if height > 0 and not hashResult.isEmpty:
    if hashResult.nodeType == exact and hashResult.depth >= depth:
        return hashResult.value

    let margin = hashResultFutilityMargin(depth - hashResult.depth)
    if hashResult.nodeType != upperBound:
        alpha = max(alpha, hashResult.value - margin)
    if hashResult.nodeType != lowerBound:
        beta = min(beta, hashResult.value + margin)

    if alpha >= beta:
        return alpha
Gave something between 10 and 20 elo last time I tested it.
User avatar
j.t.
Posts: 252
Joined: Wed Jun 16, 2021 2:08 am
Location: Berlin
Full name: Jost Triller

Re: Pruning based on TT score from a shallower depth

Post by j.t. »

This is basically a continuation of futility reductions by the way viewtopic.php?p=898394#p898394
Viz
Posts: 219
Joined: Tue Apr 09, 2024 6:24 am
Full name: Michael Chaly

Re: Pruning based on TT score from a shallower depth

Post by Viz »

https://tests.stockfishchess.org/tests/ ... 8cefa8d7e9
okay I managed to make one of the most disgusting abominations of a patch that was ever done (I know that <= alpha makes 50 times more sence but it didn't pass LTC and this one did).