Stockfish 1.8 - eval cache

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Ralph Stoesser
Posts: 408
Joined: Sat Mar 06, 2010 8:28 am

Stockfish 1.8 - eval cache

Post by Ralph Stoesser » Sun Jul 18, 2010 10:34 am

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
Posts: 613
Joined: Sun Jan 18, 2009 6:03 am

Re: Stockfish 1.8 - eval cache

Post by zamar » Sun Jul 18, 2010 12:31 pm

Good observations Ralph!
Ralph Stoesser wrote: 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.
Joona Kiiski

Ralph Stoesser
Posts: 408
Joined: Sat Mar 06, 2010 8:28 am

Re: Stockfish 1.8 - eval cache

Post by Ralph Stoesser » Sun Jul 18, 2010 3:07 pm

zamar wrote: 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
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Stockfish 1.8 - eval cache

Post by mcostalba » Mon Jul 19, 2010 11:24 am

Ralph Stoesser wrote: 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
Posts: 408
Joined: Sat Mar 06, 2010 8:28 am

Re: Stockfish 1.8 - eval cache

Post by Ralph Stoesser » Mon Jul 19, 2010 9:02 pm

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
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Stockfish 1.8 - eval cache

Post by mcostalba » Tue Jul 20, 2010 6:01 am

Ralph Stoesser wrote: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
Posts: 613
Joined: Sun Jan 18, 2009 6:03 am

Re: Stockfish 1.8 - eval cache

Post by zamar » Tue Jul 20, 2010 6:54 am

mcostalba wrote: 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 :-)
Joona Kiiski

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Stockfish 1.8 - eval cache

Post by mcostalba » Tue Jul 20, 2010 6:59 am

zamar wrote:
mcostalba wrote: 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
Posts: 408
Joined: Sat Mar 06, 2010 8:28 am

Re: Stockfish 1.8 - eval cache

Post by Ralph Stoesser » Tue Jul 20, 2010 9:44 am

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
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Stockfish 1.8 - eval cache

Post by mcostalba » Tue Jul 20, 2010 9:35 pm

Ralph Stoesser wrote: 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.

Post Reply