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
Null move in quiescence search idea from Don Beal, 1986
Moderators: hgm, Rebel, chrisw
-
- Posts: 1494
- Joined: Thu Mar 30, 2006 2:08 pm
-
- Posts: 1822
- Joined: Thu Mar 09, 2006 11:54 pm
- Location: The Netherlands
Re: Null move in quiescence search idea from Don Beal, 1986
Idea is to search on if your eval >= beta AND there is a significant threat.mjlef wrote: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
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.
-
- Posts: 4567
- Joined: Sun Mar 12, 2006 2:40 am
- Full name:
Re: Null move in quiescence search idea from Don Beal, 1986
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.mjlef wrote: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
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(beta) < VALUE_MATE_IN_MAX_PLY
&& bestValue >= beta - futility_margin(depth, 0))
{
ss->currentMove = MOVE_NULL;
pos.do_null_move<true>(st);
(ss+1)->skipNullMove = true;
nullValue = -qsearch<NonPV>(pos, ss+1, -(beta - futility_margin(depth, 0)), -(alpha - futility_margin(depth, 0)), depth-ONE_PLY);
(ss+1)->skipNullMove = false;
pos.do_null_move<false>(st);
if (nullValue >= VALUE_MATE_IN_MAX_PLY)
{
/* Do not return unproven mates */
nullValue = beta;
}
if (nullValue >= beta)
return beta;
}
}
Regards, Eelco
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
place. Therefore, if you write the code as cleverly as possible, you
are, by definition, not smart enough to debug it.
-- Brian W. Kernighan
-
- Posts: 3232
- Joined: Mon May 31, 2010 1:29 pm
- Full name: lucasart
Re: Null move in quiescence search idea from Don Beal, 1986
That must be very expensive, no ?diep wrote: Note that diep is doing giving checks in qsearch at *every* ply of the qsearch up to 32 plies deep or so.
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.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.
-
- Posts: 4567
- Joined: Sun Mar 12, 2006 2:40 am
- Full name:
Re: Null move in quiescence search idea from Don Beal, 1986
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 de Groot wrote:Code: Select all
if (nullValue >= VALUE_MATE_IN_MAX_PLY) { /* Do not return unproven mates */ nullValue = beta; } if (nullValue >= beta) return beta; } }
Eelco
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
place. Therefore, if you write the code as cleverly as possible, you
are, by definition, not smart enough to debug it.
-- Brian W. Kernighan
-
- Posts: 1822
- Joined: Thu Mar 09, 2006 11:54 pm
- Location: The Netherlands
Re: Null move in quiescence search idea from Don Beal, 1986
If you do not use a lot of chessknowledge then doing the checks is too expensive for sure.lucasart wrote:That must be very expensive, no ?diep wrote: Note that diep is doing giving checks in qsearch at *every* ply of the qsearch up to 32 plies deep or so.
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.
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.
-
- Posts: 4567
- Joined: Sun Mar 12, 2006 2:40 am
- Full name:
Re: Null move in quiescence search idea from Don Beal, 1986
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.
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.
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
place. Therefore, if you write the code as cleverly as possible, you
are, by definition, not smart enough to debug it.
-- Brian W. Kernighan
-
- Posts: 3232
- Joined: Mon May 31, 2010 1:29 pm
- Full name: lucasart
Re: Null move in quiescence search idea from Don Beal, 1986
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…
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…
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.