some questions about singular search in Stockfish

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.
Post Reply
jdart
Posts: 3826
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

some questions about singular search in Stockfish

Post by jdart » Fri Nov 01, 2019 5:14 pm

I am looking again at how Stockfish does this but there are a couple of things that puzzle me.

One is that there's some code at search.cpp, line 651 to modify the hash key if a singular search is being done. But it looks like nothing is ever stored in the hash table after a singular search, due to the condition at line 1227.

Also I notice null move is disabled for a singular search but other kinds of pre-search forward pruning such as razoring and futility pruning apparently are not. So I guess a singular search could return immediately without searching any moves? That seems strange since how then do you know the hash move is singular?

--Jon

elcabesa
Posts: 815
Joined: Sun May 23, 2010 11:32 am
Contact:

Re: some questions about singular search in Stockfish

Post by elcabesa » Fri Nov 01, 2019 5:35 pm

which version of Stockfish are you looking at? it's difficult to follow if we don't know the exact version of search.cpp

regarding line 651.(posKey = pos.key() ^ Key(excludedMove << 16); // Isn't a very good hash) if you are dealing with a search that has an excluded move, give it a posKey different from a regular search.
regarding line 1227 ( if (!excludedMove) tte->save ) yes you are right, but in the past I think they were saving it in hashtable.

regarding the forward pruning not disabled in singular search I think this is a risk taken from stockfish, but it seems worth the risk. In my engine I disable the other forward pruning when doing singular search

jdart
Posts: 3826
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: some questions about singular search in Stockfish

Post by jdart » Fri Nov 01, 2019 5:38 pm


User avatar
Eelco de Groot
Posts: 4162
Joined: Sun Mar 12, 2006 1:40 am
Location: Groningen

Re: some questions about singular search in Stockfish

Post by Eelco de Groot » Sat Nov 02, 2019 2:06 pm

As far as I can see, those are good questions. Using the alternative Key I think is no longer needed but still there because in the past the result of the search with excluded move was stored, but it gave a little Elo not to do that anymore. I can't really see why it was not smplified away after that? it may have been more than two years ago. Maybe missing something, can't believe it was not tried. The alternative key is still used for saving the static eval, in Step 6, but because the static evaluation is the same with or without excluded move, storing the alternative result seems mainly a waste of space, it may increase the chances of a ttHit having two separate keys,I don't know, that does not seem very important and in case the other Key did gave ttHit there is no need to do a new static evaluation, if alternative Key gave no ttHit. I do not completely know how this works but changing it would seem fine. You do need to guard a little against returning a ttHit from the ttMove when that move is the excluded move now and you just use the one Key in excluded move search.

So if I change

Code: Select all

    excludedMove = ss->excludedMove;
    posKey = pos.key() ^ Key(excludedMove << 16); // Isn't a very good hash
    tte = TT.probe(posKey, ttHit);
    ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE;
    ttMove =  rootNode ? thisThread->rootMoves[thisThread->pvIdx].pv[0]
            : ttHit    ? tte->move() : MOVE_NONE;
    ttPv = PvNode || (ttHit && tte->is_pv());

    // At non-PV nodes we check for an early TT cutoff
    if (  !PvNode
        && ttHit
        && tte->depth() >= depth
        && ttValue != VALUE_NONE // Possible in case of TT access race
        && (ttValue >= beta ? (tte->bound() & BOUND_LOWER)
                            : (tte->bound() & BOUND_UPPER)))
    {
to

Code: Select all

    excludedMove = ss->excludedMove;
    posKey = pos.key(); /* ^ Key(excludedMove << 16); // Isn't a very good hash */
    tte = TT.probe(posKey, ttHit);
    ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE;
    ttMove =  rootNode ? thisThread->rootMoves[thisThread->pvIdx].pv[0]
            : ttHit    ? tte->move() : MOVE_NONE;
    ttPv = PvNode || (ttHit && tte->is_pv());

    // At non-PV nodes we check for an early TT cutoff
    if (   !PvNode
        &&  ttHit
        &&  tte->depth() >= depth
	&& !excludedMove
        &&  ttValue != VALUE_NONE // Possible in case of TT access race
        && (ttValue >= beta ? (tte->bound() & BOUND_LOWER)
                            : (tte->bound() & BOUND_UPPER)))
    {
the new benchnumber for 'Stockfish Dart' is
===========================
Total time (ms) : 3219
Nodes searched : 4514764
Nodes/second : 1402536
:)

It was Bench: 4959244 in the current development version, so the fact that it is smaller could be a sign of a small speedup, although that change can be basically random.
Debugging is twice as hard as writing the code in the first
place. Therefore, if you write the code as cleverly as possible, you
are, by definition, not smart enough to debug it.
-- Brian W. Kernighan

Post Reply