Futility reductions

[Pio]

What would happen if you do the same as you do for ply 0 but for higher depths do reduced depth searches? What I had in mind was for those really bad positions with the same margins as you have do:

Depth 0 do the same as you do
Depth 1 return QS
Depth 2 and 3 return depth 1 search plus QS
Depth 4 and 5 return depth 2 search plus QS
Depth 6 and 7 return depth 3 search plus QS

I am not sure, I understand you correctly. If the newDepth (newDepth = depth - futilityReduction(alpha - staticEval - see(move))) is equal to one, then this move would already jump directly into quiesce, because I call the search with value = -search(position = newPosition, alpha = -beta, beta = -alpha, depth = newDepth - 1), so the next node would have depth == 0.

Sorry, I now see what you are doing (and you wrote it clearly). I thought of the more traditional futility close to the leaves but with many more margins and also to use the SEE as of how much the position can change as an estimate.

[j.t.]

I noticed that this idea, that you can counteract missing depth with an error margin, can be expanded to more parts of the search.
Now, instead of checking if the depth of the hash entry is at least as big as the current node depth, I just use the bounds and add a margin of error to them depending on the missing depth. Before Nalwald won 56.6% against an older version, with this change it wins 57.5% (after 2000 games).

Code: Select all

func hashResultMargin(depthDifference: Ply): Value =
    if depthDifference >= 5.Ply: return values[king]
    depthDifference.Value * 200.Value
...
if (not hashResult.isEmpty) and height > 0 and alpha > -valueInfinity:
        let margin = hashResultMargin(depth - hashResult.depth)
        case hashResult.nodeType:
        of exact:
            if hashResult.depth >= depth: return hashResult.value
        of lowerBound:
            alpha = max(alpha, hashResult.value - margin)
        of upperBound:
            beta = min(beta, hashResult.value + margin)
        else:
            assert false
        if alpha >= beta:
            return alpha

The margins are a bit bigger than for the futility reductions because I have less information (no see(move)) and less control (can't re-search if the results are bigger than alpha/beta). Though I haven't experimented much yet.