Stockfish 1.8 - eval cache

[Ralph Stoesser]

One innovation in SF 1.8 is that static eval and king safety value is cached in TT.

Well, in this new code is a little bug. Whenever you enter a position not beeing in check, you should have a static eval value, either from TT or from evaluate(), everywhere in this node. But it's not always true. You can track the issue with assert() in search.cpp.

Step 9. Internal iterative deepening
When entering the IID block, first assert

Code: Select all

 if (    depth >= IIDDepth[PvNode]
        &&  ttMove == MOVE_NONE
        && (PvNode || (!isCheck && ss->eval >= beta - IIDMargin)))
    {
    	assert(isCheck || ss->eval != VALUE_NONE);
       ...

Also in step 12. Value based futility pruning.

Code: Select all

if (   !PvNode
          && !captureOrPromotion
          && !isCheck
          && !dangerous
          &&  move != ttMove
          && !move_is_castle(move))
      {
         assert(ss->eval != VALUE_NONE);
         ...

The assertions will fail. Why? Because sometimes you re-enter the node with the same ss. But every time you re-enter the node ss->eval will be cleared first. Now if you have a TT hit ss->eval will not be restored.

This can be fixed in search() by

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->currentMove = ttMove; // Can be MOVE_NONE
        ss->eval = tte->static_value(); // here is the bug fix
        return value_from_tt(tte->value(), ply);
    }

and the same in qsearch() by

Code: Select all

   if (!PvNode && tte && ok_to_use_TT(tte, depth, beta, ply))
    {
        ss->currentMove = ttMove; // Can be MOVE_NONE
        ss->eval = tte->static_value(); // here is the bug fix
        return value_from_tt(tte->value(), ply);
    }

After fixing this I asked myself, why do you need to check for tte->static_value() != VALUE_NONE here?

Code: Select all

    // Step 5. Evaluate the position statically
    // At PV nodes we do this only to update gain statistics
    isCheck = pos.is_check();
    if (!isCheck)
    {
        if (tte && tte->static_value() != VALUE_NONE)
        {
            ss->eval = tte->static_value();
            ei.kingDanger[pos.side_to_move()] = tte->king_danger();
        }
        else
            ss->eval = evaluate(pos, ei);

        refinedValue = refine_eval(tte, ss->eval, ply); // Enhance accuracy with TT value if possible
        update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);
    }

It should not be neccesary, because now every time you enter a not-in-check node, the TT entry should have a static eval value. Right, but because TranspositionTable::insert_pv() does clear the cached static value, it is still necessary. Therefore I would suggest to also store the static eval value when writing back the PV to TT. Now all tests regarding tte->static_value() can be removed.

[zamar]

Good observations Ralph!

The assertions will fail. Why? Because sometimes you re-enter the node with the same ss. But every time you re-enter the node ss->eval will be cleared first. Now if you have a TT hit ss->eval will not be restored.

Maybe the cleanest solution is not to clear ss->eval at all?

It should not be neccesary, because now every time you enter a not-in-check node, the TT entry should have a static eval value. Right, but because TranspositionTable::insert_pv() does clear the cached static value, it is still necessary. Therefore I would suggest to also store the static eval value when writing back the PV to TT. Now all tests regarding tte->static_value() can be removed.

Sounds like a fine idea unless it makes code too complicated I'll think about this.

[Ralph Stoesser]

Maybe the cleanest solution is not to clear ss->eval at all?

Maybe. There are several options to fix this. You also could call ss.init() after the TT probe.

It should not be neccesary, because now every time you enter a not-in-check node, the TT entry should have a static eval value. Right, but because TranspositionTable::insert_pv() does clear the cached static value, it is still necessary. Therefore I would suggest to also store the static eval value when writing back the PV to TT. Now all tests regarding tte->static_value() can be removed.

Sounds like a fine idea unless it makes code too complicated I'll think about this.

Should'nt be too complicated and it makes the search code less complicated. Every time you grab a TT entry in a non-check node, you are sure to have a cached static value. Imo this is how this cache should work.

BTW, this code seems unclear to me (search.ccp, line 1149)

Code: Select all

// Pass ss->eval to qsearch() and avoid an evaluate call
if (!tte || tte->static_value() == VALUE_NONE)
    TT.store(posKey, ss->eval, VALUE_TYPE_EXACT, Depth(-127*OnePly), MOVE_NONE, ss->eval, ei.kingDanger[pos.side_to_move()]);

In case we have no TT entry I would expect

Code: Select all

TT.store(posKey, VALUE_NONE, VALUE_TYPE_NONE, Depth(-127*OnePly), MOVE_NONE, ss->eval, ei.kingDanger[pos.side_to_move()]);

In case we have a TT entry without static value I would expect

Code: Select all

TT.store(posKey, tte->value(), tte->type(), tte->depth(), tte->move(), ss->eval, ei.kingDanger[pos.side_to_move()]);

Can you explain why you save

value=ss->eval
value type=VALUE_TYPE_EXACT
depth=Depth(-127*OnePly)

here? I don't understand it.

[mcostalba]

Can you explain why you save

value=ss->eval
value type=VALUE_TYPE_EXACT
depth=Depth(-127*OnePly)

here? I don't understand it.

If there is no tte then should be no problem in saving the above (is not wrong), in case there is a tte I overwrite and this is not the optimal solution, but anyhow tte would be overwritten anyway at the end.

To be correct, although miss some optimization, the coundition could be set to:

Code: Select all

// Pass ss->eval to qsearch() and avoid an evaluate call
if (!tte)
    TT.store(posKey, ss->eval, VALUE_TYPE_EXACT, Depth(-127*OnePly), MOVE_NONE, ss->eval, ei.kingDanger[pos.side_to_move()]); 

[Ralph Stoesser]

Why would the entry be overwritten anyway? Don't you store value=ss->eval, value_type=VALUE_TYPE_EXACT to provoke a TT hit in the following qsearch() call?

From reading the source comment it seems you only want to hand over the static eval, but from looking at the other parameters for TT.store(..) it looks like you want more than this. But then, why hand over value=ss->eval and not value=refinedValue?

[mcostalba]

Why would the entry be overwritten anyway? Don't you store value=ss->eval, value_type=VALUE_TYPE_EXACT to provoke a TT hit in the following qsearch() call?

From reading the source comment it seems you only want to hand over the static eval, but from looking at the other parameters for TT.store(..) it looks like you want more than this. But then, why hand over value=ss->eval and not value=refinedValue?

Actually I don't want a TT hit in qsearch !

Otherwise it is useless to call qsearch in first instance. I want qsearch do _not_ return from stand pat immediately.

Now I have understood your point. Sorry I missed before.

Anyhow storing Depth(-127*OnePly) in TT I think should guarantee any TT hits will not return because TT depth would be not enough. Or am I missing something ?

[zamar]

Anyhow storing Depth(-127*OnePly) in TT I think should guarantee any TT hits will not return because TT depth would be not enough. Or am I missing something ?

I don't think that you are missing anything, so there is no bug. But I think that Ralph's suggestion is stylistically better:

Code: Select all

TT.store(posKey, VALUE_NONE, VALUE_TYPE_NONE, Depth(-127*OnePly), MOVE_NONE, ss->eval, ei.kingDanger[pos.side_to_move()]); 

BTW, to make things a bit more cleaner I think we should define a constant in tt.h:

Code: Select all

const Depth TT_DEPTH_NONE = Depth(-255);

And replace those horrible "Depth(-127*OnePly)" occurances in code

[mcostalba]

Anyhow storing Depth(-127*OnePly) in TT I think should guarantee any TT hits will not return because TT depth would be not enough. Or am I missing something ?

I don't think that you are missing anything, so there is no bug. But I think that Ralph's suggestion is stylistically better:

Code: Select all

TT.store(posKey, VALUE_NONE, VALUE_TYPE_NONE, Depth(-127*OnePly), MOVE_NONE, ss->eval, ei.kingDanger[pos.side_to_move()]); 

BTW, to make things a bit more cleaner I think we should define a constant in tt.h:

Code: Select all

const Depth TT_DEPTH_NONE = Depth(-255);

And replace those horrible "Depth(-127*OnePly)" occurances in code

Yes I'll do both.

[Ralph Stoesser]

Btw, beware of mixing up VALUE_NONE with VALUE_TYPE_EXACT, because ok_to_use_TT() would return true regardless of depth, because VALUE_NONE is the biggest possible Value.

Ok, you hand over static_value to qsearch() for the sake of saving a evaluate() call. I wonder, if it's worth to do so for razoring, wouldn't it be worth to do it also for zugzwang verification search and for internal iterative deepening?

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.

[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.