Hash result futility pruning

[j.t.]

I think it is a new method. For the times when the depth of the entry in the transposition table isn't high enough to warrant an immediate return or adjusting of alpha or beta:

Code: Select all

func hashResultFutilityMargin(depthDifference: Ply): Value =
    if depthDifference >= 5.Ply: return valueInfinity
    depthDifference.Value * 200
    
func search(..., depth: Ply): Value =
    ...
    let hashResult = hashTable.get(position.zobristKey)
    if (not hashResult.isEmpty) and height > 0 and (alpha > -valueInfinity or beta < valueInfinity):
        if hashResult.depth >= depth:
            ... # do your normal hash table stuff
        else:
            # hash result futility pruning
            let margin = hashResultFutilityMargin(depth - hashResult.depth)
            var
                noisyAlpha = alpha
                noisyBeta = beta
            if hashResult.nodeType != upperBound:
                noisyAlpha = max(noisyAlpha, hashResult.value - margin)
            if hashResult.nodeType == upperBound:
                noisyBeta = min(noisyBeta, hashResult.value + margin)
            if noisyAlpha >= noisyBeta:
                return noisyAlpha
    ...

Seems to give 10 - 20 Elo in Nalwald.

EDIT: after reading over it again, I noticed that I still don't understand why it works, so I am testing again ...

[AndrewGrant]

I think it is a new method. For the times when the depth of the entry in the transposition table isn't high enough to warrant an immediate return or adjusting of alpha or beta:

Code: Select all

func hashResultFutilityMargin(depthDifference: Ply): Value =
    if depthDifference >= 5.Ply: return valueInfinity
    depthDifference.Value * 200
    
func search(..., depth: Ply): Value =
    ...
    let hashResult = hashTable.get(position.zobristKey)
    if (not hashResult.isEmpty) and height > 0 and (alpha > -valueInfinity or beta < valueInfinity):
        if hashResult.depth >= depth:
            ... # do your normal hash table stuff
        else:
            # hash result futility pruning
            let margin = hashResultFutilityMargin(depth - hashResult.depth)
            var
                noisyAlpha = alpha
                noisyBeta = beta
            if hashResult.nodeType != upperBound:
                noisyAlpha = max(noisyAlpha, hashResult.value - margin)
            if hashResult.nodeType == upperBound:
                noisyBeta = min(noisyBeta, hashResult.value + margin)
            if noisyAlpha >= noisyBeta:
                return noisyAlpha
    ...

Seems to give 10 - 20 Elo in Nalwald.

EDIT: after reading over it again, I noticed that I still don't understand why it works, so I am testing again ...

I cannot recall his name which is bad, but an SF contributer, I think his name was Donald something, tried this in Stockfish a while back. The aim was to only do it using when ttdepth = depth - 1, to try to still prune. Might be able to dig up that data if it comes to mind.

[amanjpro]

I tried this quick in Zahak, didn't see much change... I have the feeling that this competes with aspiration window in a way, which might be the reason I didn't notice a difference?

[j.t.]

It seems like I messed up something. I am testing again and the only thing this great new idea does is to add more ugly code

[j.t.]

Update: a test with 5000 games revealed the following: 13.1 +/- 6.6
Which is good news and bad news. Good news: an idea works that I for once didn't get from chessprogramming.org, bad news: I can't get rid of this without feeling guilty of making Nalwald worse (and I want to get rid of this, because it is too much ugly code for the little Elo it gives).

[Rebel]

Hash table scores are unreliable due to the nature of AB. In the 90's for a long time I had a hash table reduction if the hash table score for a position went down with 0.50 or more. Much later with much better hardware (more games) it became clear it was an unsound idea.

[amanjpro]

After reading this again, I believe it is basically reverse futility pruning, but using search instead of eval... which can actually be much safer to perform than futility pruning... the only things I may suggest are:

- make sure that position is not in check (in other words, pruning is allowed)
- it is not pv node
- hash-depth is > 3 (so it has meaningful data)

currently testing this in Zahak

[amanjpro]

I tried this on a machine (the slower one), and it was going the right way. Then was encouraged and moved it to a more powerful machine with more cores to see the result faster, and bit it somehow had a very bad result against master

So as Ed said, probably TT is too unreliable to be used for pruning?

Here is my implementation:

https://github.com/amanjpro/zahak/commi ... df035f61d6

[Rebel]

Hash table scores are unreliable due to the nature of AB. In the 90's for a long time I had a hash table reduction if the hash table score for a position went down with 0.50 or more. Much later with much better hardware (more games) it became clear it was an unsound idea.

Reply to self -

I retried the (above) idea, -15 elo.

I tried the opposite reduce less if the tt-score went up with 0.50, small regression.

I tried it as simple as possible, if tt_score > eval score reduce less, small improvement.

[j.t.]

I tried this on a machine (the slower one), and it was going the right way. Then was encouraged and moved it to a more powerful machine with more cores to see the result faster, and bit it somehow had a very bad result against master

So as Ed said, probably TT is too unreliable to be used for pruning?

Here is my implementation:

https://github.com/amanjpro/zahak/commi ... df035f61d6

I tried limiting to hashResult.depth > 3 and also only when beta - alpha == 1 (which removes some non pv nodes from this method), they both didn't add anything. When not search positions that are in check, it got worse (like 5 Elo).