Without the null move observation

[Desperado]

@HG + Uri

Well, i begin to realize,
that the term "standpat" has another motivation
than the nullmove observation. I looked up the meaning of standpat
which (i dont know excactly how to translate) is sth like
"carefreeness (abandon)", which implies another principle of course
than NMO.

Because i like HGs expression of "branch termination scheme (BTS)",
_my_ BTS is based on the nullmove observation, like i described it
before. If by accident, that leads to the same look in qs, like
the standpat principle, i am shocked .

My interpretation, implementation at least goes hand in hand with
the NMO.

At the moment i think there is room left for interpretation, because
no one can forbid to use the NMO as BTS.

Just my opinion so far.

Michael

[hgm]

In early versions of micro-Max I experimented with a BTS that only searches recaptures to the same square, which is basically equivalent to equating the d=1 score to the score of the best SEE-safe move. That did work reasonably, in the sense that it did get none of the horrible artifacts you get in a QS-less search that unconditionally stands pat in the leaves. But a traditional capture search was better, at least when you do some kind of move sorting. (Without that, it explodes.) Sorting the best MVV move in front (leaving all others in random order) is good enough to prevent the explosion, and make an all-capture search outperform SEE-only scoring.

In Shogi branch termination is a real problem. Capture-only searches work poorly, because they make the position less quiet, by bringing pieces in hand. The main concern seems not so much whether you will be recaptures, but whether you will be checkmated by dropping of these pieces with check. Searching check-drops in addition to the captures causes a horrible explosion with any move ordering I tried.

Some of the stronger engines do a 3-ply mate 'tsume' search (allowing only checks and check drops on ply 1 and 3, and evasions on ply 2) to see if you can deliver checkmate, before searching any capture. There seem to be static evaluations that take future captures into account (SOMA and Super-SOMA), but I never studied those.

[Sven]

[..., or are you going to redefine the term "stand-pat in QS" to mean something substantially different from "in QS, assuming no zugzwang nor in-check, the static eval can be used as a lower bound since there is almost always at least one quiet move which is better than doing nothing - knowing that this can fail sometimes".

That is not a 'redefinition', because stand pat was never defined like you mention above

Stand pat = do nothing

Nothing more, nothing less. And it works when doing something will not have a much different effect than doing nothing on the evaluation. In which case the position is known as 'quiet'. Hence stand-pat will work only in quiet positions, and you need a QS to search those first.

"Stand pat = do nothing" => where is that any different from what I wrote? Actually I even used almost the same words some postings above.

I can do nothing based on the assumption that I am not forced to worsen my position. That is equivalent to the definition I gave above, but if you don't believe it then take it as a given fact that this is what I meant so we are probably fighting about very minor differences in wording only.

Since I don't search quiet moves in QS I make an assumption about the minimum value I could expect from trying any of those, and that is exactly to apply NMO and therefore take the stand-pat score (adding resp. including a side-to-move bonus if you like - I would consider this as part of static eval!) as lower bound for searching tactical moves.

When making that assumption I can restrict it to quiet moves:
a) If all available captures are losing (or not winning, at least) then NMO implies that there must be at least one other (i.e. quiet) move that fulfils my assumption.
b) If there is one capture that improves upon the stand-pat score then NMO is not needed since stand-pat is not used.

What I insist on, though, is that making use of the NMO is not necessarily the same as applying "Null Move Pruning", as Bob seemed to imply. The term "Null Move" in "Null Move Observation", however, is kind of overloaded here and tends to provoke such wording discussions (but I did not coin NMO so I'm not the one to blame ...).

Null Move Pruning makes the same assumption (making the best move is usually better than not moving == NMO), and does a trick on top of that (do a shallow search beginning with the opponent moving twice, since we did not make a move ourselves).

Sven

[Sven]

I looked up the meaning of standpat
which (i dont know excactly how to translate) is sth like
"carefreeness (abandon)", which implies another principle of course
than NMO.

Hi Michael

Where did you find that? What I find is sth. like: "be steadfast in one's opinions, be resolute in one's ideas", "refuse to abandon one's opinion or belief", or in german "stur bleiben, nicht nachgeben". That's exactly NMO: I rely on having at least one move that improves my situation upon not moving, so in case of QS I can take the stand-pat score and refuse to give it away. In case of NMP I can take the best the opponent can get when moving twice, see it from my viewpoint and take it as a lower bound (hoping - or verifying - that I'm not in zugzwang) which I don't give away, and if that causes a cutoff then I'm lucky since I saved a lot of effort.

Sven

[bob]

Sorry, that is NOT null-move. ..

Well, a "null-move" is what it is. A move that passes the right to move,
without changing other attributes of the position.
There is no further criteria for a move to be defined as nullmove.

Correct, but the "null-move-observation" is not based on "making a null move". It is based on one side making two moves in succession. Your code is NOT meeting that criterion. So you are using a null-move, but you are NOT using "the null-move-observation."

...The null-move-observation, as defined by Beal, was simply "If one side makes two consecutive moves without an intervening move by the opponent, and he can not produce a significant advantage by doing so, then his position is very bad, or, in our parlance, the side playing the null have a very strong position.

In the above, there is no "second consecutive move" so there is no "null-move-observation criterion that has been satisfied. You have to do a null-move and then let the opponent move again, else it is not a valid "null-move search."

...

_For me_, the null move observation is, that there is a better move to
be expected than the nullmove. Nothing more nothing less. Like:

doNullmove()
value = -blackBoxValue()
undoNullmove()

"How" the value will be produced, by search or evaluation, isnt the matter of the assumption,
that at least one real move will produce a better result.

That is YOUR definition. You should use something else, because the null-move observation has been defined for a LONG time now, and has a standard meaning.

The only matter is to get a reasonable value for the nullmove.
Then you can check, based on the nullmove observation, and as logical
consequence of its definition, that a value resulting from a nullmove
and above beta is probably a fail high node.

IMHO, Michael

All I can say is that is not how it has been used since the 80's when Beal first wrote about it. And it CERTAINLY is not how we use it in null-move search, which relies on the null-move-observation to be effective.

Null-move search is based on the idea that the null-move-observation is SO STRONG, one can use a reduced search and it STILL holds to be true. If I need to search 20 plies deep from this position, I can play a null-move, reduce the depth significantly, and if the score STILL comes back "good" then I don't need to search further. But that two moves in a row is the key. Not the null-move itself to establish a stand-pat score or whatever.

[bob]

Well, if you really talk of the "null-move-observation", there is
a clear NO. The null-move-observation is the fundamental
base of every quiescence search in todays standard search techniques.

I simply disagree. Beal used that term in a very specific way when he first wrote about the null-move-observation in the 80's. I don't consider the q-search to use "null-move" in any shape, form, or fashion. This stand-pat stuff really has NOTHING to do with null-move. You call a static eval to establish a lower bound for the node. If the lower bound is still >= beta, you are finished. If not, you can try other moves such as captures or checks to see if you can raise that bound. Not one "thought" about "null-move" in that description, much less "the null-move-observation" which has to do with the huge advantage playing two moves in a row gives you. Simple example is that you can capture anything that is attacked, for free, even with the queen. Because you capture on move one, and retreat on move two. If such an opportunity is given to you, and you STILL have a score <= alpha, you are pretty much screwed. It is SO powerful, we can reduce the search depth, AND the search effort, and STILL accurately prove this position is good/bad.

In context to pruning and reduction techniques it may be possible to
reallocate the gain to other known algorithms like mentioned by Matthew
or like Bob said, an improved LM-technique may do the job.

Michael

I don't agree. The null-move observation is, simply "If I pass, and let my opponent make two moves in succession, and he STILL can not come up with a winning advantage, then his position is very bad, and mine is very good."

I don't see that concept in q-search. That's not the same as either standing pat, or trying a check or capture.

What you are talking about is null move pruning (null move search, null move heuristic). The term "null move observation" seems to be a more general term, forming the base for null move pruning as well as other techniques, e.g. Fail high reductions (see bottom of page 2 and also the next page):

Later, Beal (1989) again looked at his idea of the Null Move Heuristic (NMH). NMH is based on the observation that in many games and game like applications for the side to move there is almost always a better alternative (move) than doing nothing (the null move). We call this the Null Move Observation (NMO).
[...]
In this paper we describe a new selective search heuristic, called Fail High Reductions (FHR).
[...]
Like the NMH, FHR is based on the NMO.

That proves my statement about NMO being a more general term, even though NMP was first and the term NMO came up later. CPW gives an overview of techniques based on NMO. I hope nobody is going to rewrite all those definitions now ...

I don't see how that "proves" anything. You can't use a paper that "references" an idea, possibly incorrectly, to define the term that was defined by Beal first, so far as I know.

Clearly the stand-pat principle in QS is based on the same NMO, or are you going to redefine the term "stand-pat in QS" to mean something substantially different from "in QS, assuming no zugzwang nor in-check, the static eval can be used as a lower bound since there is almost always at least one quiet move which is better than doing nothing - knowing that this can fail sometimes".

That is exactly what stand-pat is, and it is exactly what "null-move-observation" is not... I have beal's paper (I refereed a draft of it when he wrote it). I'll try to locate it when I get to my office and post the definition as it appears...

What else are we all doing for years?

Wondering why this must be explained to you

Sven

Because what you are explaining is wrong based on original usage???

[bob]

Well, if you really talk of the "null-move-observation", there is
a clear NO. The null-move-observation is the fundamental
base of every quiescence search in todays standard search techniques.

In context to pruning and reduction techniques it may be possible to
reallocate the gain to other known algorithms like mentioned by Matthew
or like Bob said, an improved LM-technique may do the job.

Michael

I disagree.
The qsearch is not based on the observation that you usually have something better than null move but on the observation that non captures usually do not have a significant effect on the evaluation.

I expect similiar qsearch to work also in games when there is often nothing better than null move but you have a set of moves that gives a big change in the evaluation that you try them in the qsearch.

I also do not believe that you need normal qsearch for 2800 engines and using some good static exchange evaluator instead of the qsearch may be enough to get a 2800 engine that is clearly weaker than the engines of today.

Uri

That's a key point. Q-search is not even remotely related to "I have something better." It is about NOTHING more than trying to reach a tactically quiet position so the static evaluation can return an accurate score without having to consider dynamic things like sequences of captures or checks or whatever.

[hgm]

"Stand pat = do nothing" => where is that any different from what I wrote? Actually I even used almost the same words some postings above.

Well, how to say...

in QS, assuming no zugzwang nor in-check, the static eval can be used as a lower bound since there is almost always at least one quiet move which is better than doing nothing - knowing that this can fail sometimes

You really don't see any difference between that and "do nothing"? Seems to me the words "assuming", "lower bound", "better than" play a prominent role that does not seem to be covered in any way by "do nothing"...

I can do nothing based on the assumption that I am not forced to worsen my position. That is equivalent to the definition I gave above, but if you don't believe it then take it as a given fact that this is what I meant so we are probably fighting about very minor differences in wording only.

How about doing nothing not based on any assumption at all, but because you did not feel like doing something? I don't think this is only semantics. In addition to the examples I gave before where the null-move assumption is invalid, and you can still do stand pat, it is also easy to cook up examples where the null-move assumption is absolutely valid, (null move being guaranteed to always be the worst move by a very large margin), and yet standing pat on the current evaluation would give you a program that plays like cr*p. There is just no logical connection at all between the null-move assumption and whether stand-pat is a successful branch-termination strategy.

Since I don't search quiet moves in QS I make an assumption about the minimum value I could expect from trying any of those, and that is exactly to apply NMO and therefore take the stand-pat score (adding resp. including a side-to-move bonus if you like - I would consider this as part of static eval!) as lower bound for searching tactical moves.

When making that assumption I can restrict it to quiet moves:
a) If all available captures are losing (or not winning, at least) then NMO implies that there must be at least one other (i.e. quiet) move that fulfils my assumption.
b) If there is one capture that improves upon the stand-pat score then NMO is not needed since stand-pat is not used.

The point is that that assumption (about the minimum value) is neither necessary not sufficient to justify applying stand-pat. In fact stand-pat doesn't require any justification other than that you don't want infinite recursion, because you want an engine that works, rather than one that crashes or thinks infinitely long. So when you cannot afford to search all the way to game end, you will have to stand pat at some point. This is true no matter how valid or invalid the NMO is.

So stand-pat and the evaluation heuristic is really the basis of any finite tree search, and does not need any justification other than that you want to use tree search. The way QS works in Chess engines is simply a work-around for the fact that is is too difficult to construct a static evaluation that performs with acceptable accuracy in the presence of moves of a certain class (winning captures). So you explicitly search all the moves that could conceivably be in that class, (captures), and when none of them were found to be winning, you apparently have a position for which your evaluation does work (a 'quiet' position), which makes it safe to return the eval score. And this only works because of the fortunate fact that you will run out of eval-compromising (= 'non-quiet') moves sooner rather than later (in Chess, but not in Crazyhouse or Shogi). None of that had anything to do with NMO whatsoever.

[Desperado]

I looked up the meaning of standpat
which (i dont know excactly how to translate) is sth like
"carefreeness (abandon)", which implies another principle of course
than NMO.

Hi Michael

Where did you find that? What I find is sth. like: "be steadfast in one's opinions, be resolute in one's ideas", "refuse to abandon one's opinion or belief", or in german "stur bleiben, nicht nachgeben". That's exactly NMO: I rely on having at least one move that improves my situation upon not moving, so in case of QS I can take the stand-pat score and refuse to give it away. In case of NMP I can take the best the opponent can get when moving twice, see it from my viewpoint and take it as a lower bound (hoping - or verifying - that I'm not in zugzwang) which I don't give away, and if that causes a cutoff then I'm lucky since I saved a lot of effort.

Sven

I cannot directly reference. But if i try to explain with my own (english)
words, it is like:

standpat = "to decide to play the position like it is"

which is indeed a different concept than NMO, independant which definition
of NMO someone uses.

That allows you, to connect it with different kinds of conditions, which
then ends like

standpat = decide to play the position like it is , if "CONDITION"

"Condition" can be everything, even "no" condition at all.

examples:
==================

a: //"extra Condition" in chess used: potential fail High node

if(standpat >= beta ) return(standpat);

b: //"extra Condition" , if someone would like it
(not to talk about it, if it makes any sense pls)

if(standpat <= alpha) return(standpat)

and here the most important
------------------------------------

c: //"no extra Condition" , the most liberal and the "real" standpat

return(standpat)

// take it as it is! that is the nature of "standpat"

So, HGM is right. There is no default assumtion connected with
the definition and the term of "standpat".

In chess we just expand the basic standpat definition with an additional
condition, but that condition will give information about what
to expect, and that is the part HG did miss (imo).

Michael

[hgm]

In chess we just expand the basic standpat definition with an additional
condition, but that condition will give information about what
to expect, and that is the part HG did miss (imo).

Not sure what condition you mean. I don't see that what we do in Chess is different from the original meaning you give: "play it as it is". You either try to improve the position by playing a move, or keep it as it is. If you play a move, you don't stand pat. I don't see why the definition of what stand-pat IS should contain the condition when you should DO IT. One has nothing to do with the other.