Transposition table based cutoffs

[Witek]

Hi,
normally after probing TT we do something like:

Code: Select all

if (!PvNode & ttEntry.depth >= depth)
{
    if ((ttEntry.bounds == Bounds::Exact) ||
        (ttEntry.bounds == Bounds::Lower && ttScore >= beta) ||
        (ttEntry.bounds == Bounds::Upper && ttScore <= alpha))
    {
        return ttScore;
    }
}

At least the code looks like that in SF, Ethereal, Koivisto, and probably some other engines too.

However, when I did something more fancy:

Code: Select all

if (!PvNode & ttEntry.depth >= depth)
{
    if (ttEntry.bounds == Bounds::Exact)
    {
        return ttScore;
    }
    else if (ttEntry.bounds == Bounds::Upper)
    {
        if (ttScore <= alpha) return alpha;
        if (ttScore < beta) beta = ttScore;
    }
    else if (ttEntry.bounds == Bounds::Lower)
    {
        if (ttScore >= beta) return beta;
        if (ttScore > alpha) alpha = ttScore;
    }
}

I got +21.5 +/- 10.9 Elo gain, 100% LOS.

Am I missing something, or just found some new way to speedup the search?

[Mergi]

Not a good idea. There's already a similar thread with some reasons as to why not do it. http://www.talkchess.com/forum3/viewtopic.php?t=59856

However the returned score from the TT is not completely useless either. Even if you don't make a cutoff, you can still use it to improve your static evaluation of the current position.

Code: Select all

if ((ttEntry.bounds == Bounds::Upper && staticEval > ttScore) || (ttEntry.bounds == Bounds::Lower && staticEval < ttScore)) {
  staticEval = ttScore;
}

[abulmo2]

Shifting alpha and beta bounds on non pvnodes is useless (I suppose you are using pvs and not plain alphabeta). On non pv nodes beta=alpha+1, so if you increase the alpha value or decrease the beta value you should get a cutoff.

[j.t.]

I did something similar as well, and I believe I saw this in other engines, too.
Nalwald/search.nim#L163:

Code: Select all

    # update alpha, beta or value based on hash table result
    if (not hashResult.isEmpty) and height > 0 and (alpha > -valueInfinity or beta < valueInfinity):
        if hashResult.depth >= depth:
            case hashResult.nodeType:
            of exact:
                return hashResult.value
            of lowerBound:
                alpha = max(alpha, hashResult.value)
            of upperBound:
                beta = min(beta, hashResult.value)
            if alpha >= beta:
                return alpha

If it works for you, keep it.

[hgm]

I suppose this only works in combination with fail-hard, where beta would be returned when the score of the node is raised to above beta? Otherwise is would seem very wrong.

[Joost Buijs]

However, when I did something more fancy:

Code: Select all

if (!PvNode & ttEntry.depth >= depth)
{
    if (ttEntry.bounds == Bounds::Exact)
    {
        return ttScore;
    }
    else if (ttEntry.bounds == Bounds::Upper)
    {
        if (ttScore <= alpha) return alpha;
        if (ttScore < beta) beta = ttScore;
    }
    else if (ttEntry.bounds == Bounds::Lower)
    {
        if (ttScore >= beta) return beta;
        if (ttScore > alpha) alpha = ttScore;
    }
}

I got +21.5 +/- 10.9 Elo gain, 100% LOS.

Am I missing something, or just found some new way to speedup the search?

You use this in nonPV nodes, so alpha equals beta-1, so (ttScore <= alpha) is the same as (ttScore < beta) and (ttScore >= beta) is the same as (ttScore > alpha). I don't see how this could do anything at all, if it does you must be entering nonPV nodes with wrong alpha beta values.

[hgm]

You assume he is using PVS. But perhaps this is just vanilla alpha-beta.

[Joost Buijs]

Yes, this could be an exception. Not many people are using vanilla A-B these days, I completely forgot about it's existence.

[Witek]

I'm using PVS, not vanilla AB, in fail-soft version. Indeed, adjusting alpha/beta does not change anything, like Joost noticed. What does matter though is whether I return alpha/beta/TT score on cutoff (depending on bounds) instead of TT score always. In the former case I observe 20 Elo gain. It's a bit weird, because it does not fit the fail-soft framework.

[pedrox]

I'm using PVS, not vanilla AB, in fail-soft version. Indeed, adjusting alpha/beta does not change anything, like Joost noticed. What does matter though is whether I return alpha/beta/TT score on cutoff (depending on bounds) instead of TT score always. In the former case I observe 20 Elo gain. It's a bit weird, because it does not fit the fail-soft framework.

I have tried it several times and I always have the same result as you.

I have not been able to take advantage of the result of the tables to improve the static evaluation either.

I have also tried cutting on pv_nodes except when there is an exact (so that the pv is not truncated). This seems to be somewhat better for me.