Stockfish 1.8 - eval cache

[Ralph Stoesser]

To ask in a more general way: Every time you visit a non-check node and have no TT entry you must call evaluate(). Now if the chance is high that you will revisit the node later, couldn't it be usefull to pre-store the static_value in TT now? On the other hand I don't expect to gain much in terms of playing strength by eval pre-caching. Moreover I think it would be not so easy to predict whether a node would be revisited later.

I don't expect too much gain too, but it worths to give it a try.

Because should be a non functional change we don't need real games, just measure speed.

Btw, regarding predicting whether a node will be revisited later or not w.r.t TT: I've tried PreSearch (Schaeffer Paper: http://webdocs.cs.ualberta.ca/~jonathan ... Search.pdf) in SF 1.8.

It somehow works (no Elo loss), but I could not squeeze Elo gain out of it. I've tried to find a way to predict whether a node would be revisited later or not, but no success.

[mcostalba]

To ask in a more general way: Every time you visit a non-check node and have no TT entry you must call evaluate(). Now if the chance is high that you will revisit the node later, couldn't it be usefull to pre-store the static_value in TT now? On the other hand I don't expect to gain much in terms of playing strength by eval pre-caching. Moreover I think it would be not so easy to predict whether a node would be revisited later.

I don't expect too much gain too, but it worths to give it a try.

Because should be a non functional change we don't need real games, just measure speed.

Btw, regarding predicting whether a node will be revisited later or not w.r.t TT: I've tried PreSearch (Schaeffer Paper: http://webdocs.cs.ualberta.ca/~jonathan ... Search.pdf) in SF 1.8.

It somehow works (no Elo loss), but I could not squeeze Elo gain out of it. I've tried to find a way to predict whether a node would be revisited later or not, but no success.

We took a more direct approach: I made the patch and Joona tested its speed: around +0.8% of speed increase, not a lot but we like the solution anyhow, so it will go in

[Ralph Stoesser]

We took a more direct approach: I made the patch and Joona tested its speed: around +0.8% of speed increase, not a lot but we like the solution anyhow, so it will go in

Nice.

I like it too, because it makes the search() code cleaner. No more special cases for hand over static value to qsearch() or search().

[Ralph Stoesser]

It seems there are more problems regarding the search stack management.

Example: You save ss->threatMove from a null search fail low and later in step 12: Futility pruning, where you would need the threat move, it is gone.

[rvida]

It seems there are more problems regarding the search stack management.

Example: You save ss->threatMove from a null search fail low and later in step 12: Futility pruning, where you would need the threat move, it is gone.

In Critter I do not store threatMove in the search stack at all, I just keep it in a local variable. For smp search I pass it through split point structure.

Maybe this will work in SF too.

Richard

[Ralph Stoesser]

I assume they already have fixed it together with the ss->eval bug.

In general I would say it's a good idea to handle the threat move via the search stack. It's more flexible. For example you can easily try out the Botvinnik-Markoff Extension.

[mcostalba]

Thanks Ralph for spotting this and thanks Richard for the suggested fix.

[Ralph Stoesser]

A stylistically remark regarding the search stack variables ss->bestMove and ss->currentMove. You somehow mix up these variables semantically in search() and qsearch(). There is no bug, but at first look the usage of those variables seems unclear or even wrong.

The current move is actual the move you search deeper in the tree. The best move is the best move found at a ply.

The move you store in the TT is the best move. Therefore, when you have a TT hit, you should store the TT move back in ss->bestMove, not in ss->currentMove.

search(), TT hit (same in qsearch())

Code: Select all

if (!PvNode && tte && ok_to_use_TT(tte, depth, beta, ply))
{
    // Refresh tte entry to avoid aging
    TT.store(posKey, tte->value(), tte->type(), tte->depth(), ttMove, tte->static_value(), tte->king_danger());

    ss->bestMove = ttMove; // Can be MOVE_NONE
    return value_from_tt(tte->value(), ply);
}

search(), threat move storage from null move search fail low

Code: Select all

        else
        {
            // The null move failed low, which means that we may be faced with
            // some kind of threat. If the previous move was reduced, check if
            // the move that refuted the null move was somehow connected to the
            // move which was reduced. If a connection is found, return a fail
            // low score (which will cause the reduced move to fail high in the
            // parent node, which will trigger a re-search with full depth).
            if (nullValue == value_mated_in(ply + 2))
                mateThreat = true;

            ss->threatMove = (ss+1)->bestMove;
            if (   depth < ThreatDepth
                && (ss-1)->reduction
                && connected_moves(pos, (ss-1)->currentMove, ss->threatMove))
                return beta - 1;
        }

search(), IID, ttMove storage

Code: Select all

    // Step 9. Internal iterative deepening
    if (    depth >= IIDDepth[PvNode]
        &&  ttMove == MOVE_NONE
        && (PvNode || (!isCheck && ss->eval >= beta - IIDMargin)))
    {
        Depth d = (PvNode ? depth - 2 * OnePly : depth / 2);

        ss->skipNullMove = true;
        search<PvNode>(pos, ss, alpha, beta, d, ply);
        ss->skipNullMove = false;

        ttMove = ss->bestMove;
        tte = TT.retrieve(posKey);
    }

[mcostalba]

The move you store in the TT is the best move. Therefore, when you have a TT hit, you should store the TT move back in ss->bestMove, not in ss->currentMove.

Thanks. Patch applied.

[Ralph Stoesser]

Again a little something from search.cpp.

In root_search() you compute

depth = (Iteration - 2) * OnePly + InitialDepth;

nested within the fail low and the move loop.

Depth computation could be done in Step 1. Initialize node.
No reason to compute it within any loops.