Null move in quiescence search idea from Don Beal, 1986

[mjlef]

I am a bit confused and do not see how the nullmove search test can ever pass (be >=beta). We have two cases. If bestValue>=beta, we fail high before the nullmove:

if (bestValue >= beta)
return bestValue;

Now if bestValue is <beta, then once we call the nullmove search, with a new alpha if -beta and beta of -alpha (and -bestScore for bestScore), then it will fail high based on the lines above, meaning the test will always fail.

Or did I miss something?

Mark

[diep]

I am a bit confused and do not see how the nullmove search test can ever pass (be >=beta). We have two cases. If bestValue>=beta, we fail high before the nullmove:

if (bestValue >= beta)
return bestValue;

Now if bestValue is <beta, then once we call the nullmove search, with a new alpha if -beta and beta of -alpha (and -bestScore for bestScore), then it will fail high based on the lines above, meaning the test will always fail.

Or did I miss something?

Mark

Idea is to search on if your eval >= beta AND there is a significant threat.
If we look back at publications from 80s, we see they even wrote on paper that for parallel search they wanted to split in quiescencesearch.

Some were just busy with tactics back then - which is quite understandable.

Frans Morsch about those days: "They never realized back then that the big secret from some of the commercial chessprograms under which Genius and my programs was the huge nps we managed to achieve".

Most commercial software indeed if you think about it never printed a NPS.

They got hundreds of nps a second at simple hardware in the 80s of maybe 1Mhz or so.

If we compare that then with the 512 processor transputer that Zugzwang ran at of 1Mhz each. Zugzwang searched around a 200 nps in total at the entire machine.

Logically with such a small nps they couldn't even keep the machine busy searching and then instead of getting a higher nps they started writing about splitting in Qsearch.

They got roughly the same nps at a 512 processor 1Mhz transputer like Frans Morsch out of a 1 Mhz dedicated processor.

As they just didn't realize their problem, the only publications dealt with that and infected others; even Bob got infected and spoke about splitting in qsearch in his publications from back then.

It's more than logical that some others who also were focussed upon tactics wanted to solve that entirely in quiescencesearch.

[Eelco de Groot]

I am a bit confused and do not see how the nullmove search test can ever pass (be >=beta). We have two cases. If bestValue>=beta, we fail high before the nullmove:

if (bestValue >= beta)
return bestValue;

Now if bestValue is <beta, then once we call the nullmove search, with a new alpha if -beta and beta of -alpha (and -bestScore for bestScore), then it will fail high based on the lines above, meaning the test will always fail.

Or did I miss something?

Mark

Don't be confused please The observation was correct I think. Thanks Mark for the attententive reading! I had come to the same conclusion. At least I think we mean the same thing, but the post was more about the possibilities offered by the eval trick than about the correctness of the code, as Vincent also mentions so I let it stand for now. Wondering if anybody would notice it or the thread would go under again.

But mainly I do not yet know what would be a more correct implementation.

Of course that is very difficult to determine without a lot of testing... But what the code does is can not very efficient because every call to nullmove is an immediate stand pat if you reverse the eval. In the old code at least there would be a new static eval and with small asymmetries, at least it would be different. A problem is that nullmove is supposed to be a speed up but you already do a lot of futility pruning and stand pat so maybe in a more comprehensive overhaul, combined with a shorter nullmove the regular quiescence search then should be longer than now. That is just one solution. But if you don't get it right, qsearch is already invoked as a reduced search in for instance razoring. So accuracy has to be maintained. It isn't per sé bad if the quiescence search becomes longer as long as that also would bring something extra.

As I said, you could think about making the nullmove quiescence shorter than regular quiescence, by introducing a maximum depth or more recaptures only. I already had something like that in the old versions from 2009.

But at the moment the code as it is in Rainbow serpent is less complicated than that, I only changed it a little from the above code. But not even the use of futility_margin(depth,0) here is tuned. depth is still at least ONE_PLY so maybe if I need to make it smaller I could introduce negative depths in Stockfish's futility array. It is not yet tested so that is why I had not posted about the bug.

This is current version build 53

Code: Select all

    // Evaluate the position statically
    if (inCheck)
    {
        bestValue = futilityBase = -VALUE_INFINITE;
        ss->eval = evalMargin = VALUE_NONE;
        enoughMaterial = false;
    }
    else
    {
        if (tte)
        {
            assert(tte->static_value() != VALUE_NONE);

            evalMargin = tte->static_value_margin();
            ss->eval = bestValue = tte->static_value();

            // Stand pat. Return immediately if static value is at least beta
            if (bestValue >= beta)
                return bestValue;
        }
        else
        {
            if ((ss)->skipNullMove && ((ss-1)->currentMove == MOVE_NULL))
            {
                 ss->eval = bestValue = -(ss-1)->eval;
                 evalMargin = -(ss-1)->evalMargin;
                 // Do not stand pat!
             }
             else
             {
                ss->eval = bestValue = evaluate(pos, evalMargin);
                if (bestValue >= beta)
                {   // Stand pat
                     TT.store(pos.key(), value_to_tt(bestValue, ss->ply), BOUND_LOWER, DEPTH_NONE, MOVE_NONE, ss->eval, evalMargin);
                     return bestValue;
                }
             }
        }


        if (PvNode && bestValue > alpha)
            alpha = bestValue;

        futilityBase = ss->eval + evalMargin + FutilityMarginQS;
        enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMg;
		
        Value nullValue;
        bool disableNull = false;
		
        // Null move in quiescence search
        if (   !disableNull	// !inCheck is already tested
            && !PvNode
            && !ss->skipNullMove
            &&  enoughMaterial
            &&  abs&#40;beta&#41; < VALUE_MATE_IN_MAX_PLY
            &&  bestValue >= beta - futility_margin&#40;depth, 0&#41;)
         &#123;
             ss->currentMove = MOVE_NULL;
			
             pos.do_null_move<true>&#40;st&#41;;
             &#40;ss+1&#41;->skipNullMove = true;
             nullValue = -qsearch<NonPV>&#40;pos, ss+1, -&#40;beta - futility_margin&#40;depth, 0&#41;), -&#40;alpha - futility_margin&#40;depth, 0&#41;), depth-ONE_PLY&#41;;
             &#40;ss+1&#41;->skipNullMove = false;
             pos.do_null_move<false>&#40;st&#41;;
			
             if &#40;nullValue >= VALUE_MATE_IN_MAX_PLY&#41;
             &#123;
                 /* Do not return unproven mates */
                 nullValue = beta;
             &#125;
             if &#40;nullValue >= beta&#41;
                 return beta;
         &#125;
    &#125;

(Another note: Returning beta here in the nullmove search introduces an inaccuracy that is not elegant, certainly less elegant than the stand pat rule that at least returns a specific static eval rather than beta, but I am hoping that at least there is the PV search still that acts as a verification search. In the case of programs like Crafty that is already less the case. This is one reason why in Glaurung for instance in PV nodes you do not return a hash-hit, always re-search it. The PV search verifies the nullwindow searches in case of a Fail High for instance, so it helps if it is at least a little more accurate )

Regards, Eelco

[lucasart]

Note that diep is doing giving checks in qsearch at *every* ply of the qsearch up to 32 plies deep or so.

That must be very expensive, no ?

I did extensive testing with that in DiscoCheck, and concluded that doing quiet checks only at the entry of the qsearch (depth == 0) is best.

[Eelco de Groot]

Code: Select all

			
    if (nullValue >= VALUE_MATE_IN_MAX_PLY)
    {
        /* Do not return unproven mates */
        nullValue = beta;
    }
    if (nullValue >= beta)
        return beta;
  }
}

Sorry, this is still a bug of course, nullValue >= beta - futility_margin(depth, 0) would be logical. Okay, I will test that. But I have no idea if that version is 'allowed' in the sense it would not be worse than the buggy code I posted.

Eelco

[diep]

Note that diep is doing giving checks in qsearch at *every* ply of the qsearch up to 32 plies deep or so.

That must be very expensive, no ?

I did extensive testing with that in DiscoCheck, and concluded that doing quiet checks only at the entry of the qsearch (depth == 0) is best.

If you do not use a lot of chessknowledge then doing the checks is too expensive for sure.

the first check in qsearch is of course the most important one. So if you treat every position the same like i do in Diep then you sure must have a lot of code to limit all that, besides incremental attacktables.

This is not something you get 'overnight' to work.

It's fulltime work.

If you have a fast beancounter i doubt the trade-off would ever break even. In the fast beancounter i wrote which ran at 2.5 million nps single core K7 2.1Ghz in 32 bits, it is just doing a simple check at first ply of qsearch (or first 2 plies - i forgot honestely - i can check that if you're interested) and it tries at that first ply way more checks and captures than Diep. So efficiency of it is horrible compared to Diep.

Yet spending the system time to determine what to try and what not to try like i do in Diep, part of it historic code by now, that's eating too much system time for a fast beancounter that's under 840 cycles a node.

[Eelco de Groot]

I never did continue this experiment with nullmove in quiescence search. Maybe it is time to try it once more.

I just dug up this very old thread, sorry, to post that there is a newer version of Ancalagon available here It does not have nullmove in qsearch but I do try to revive Singular Extensions a little bit the way Deep Blue did it. It does need a ttMove like the simplified Rybka/ Stockfish Singular Extensions, which Deep Blue did not I suppose. I only recently learned that, these days, Stockfish stores ttMoves also in Fail Low nodes! I could not believe it at first, I could have sworn it did not.... But, this makes singular "extensions" in ALL nodes possible again with very little code changes I could just practically borrow all the existing Singular Extension code and apply it in ALL nodes in nullwindow searching.

[lucasart]

Nullmove in QS is plain stupid. I'm surprised you haven't understood that in 8 years since you started this post…

The reason no serious engine does it, is twofold: 1/ it doesn't work, 2/ it makes no sense.

In QS you aready have the stand pat option. Keep the eval and stop here. You want to introduce another option, which is not only costly, but completely futile. Instead of keeping the eval and stopping, you let the opponent play and worsen your score? A pure waste of time, as the result is guaranteed to be worse than stand pat. And before you start any handwaving argument about zugzwang, remember QS is a capture search…