Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: An MTD(f) question about NULL MOVE searching

Author: Vasik Rajlich

Date: 08:36:06 07/16/04

Go up one level in this thread


On July 16, 2004 at 10:21:25, Fabien Letouzey wrote:

>
>On July 16, 2004 at 09:15:17, Vasik Rajlich wrote:
>
>>On July 16, 2004 at 07:24:28, Fabien Letouzey wrote:
>
>I am starting to get your point (I'm a bit slow).  Interestingly it
>seems to apply to plain alpha-beta as well, which never uses any
>re-search (and no PV node in my terminology, all nodes are treated in
>the same way).
>
>I am used to problems due to segmented-window algorithms (aspiration,
>PVS/NegaScout, the MTD family, ...), but this null-move topic seems
>somewhat independent!
>

I did quite a bit of thinking about this. Generally, the more segmented your
algorithm, the less flexibility you have in dealing with this (and similar)
issues.

In plain alpha-beta, you could set any criterion for a null move that you
wanted. (Ie you could require any score for the null move to be accepted.) In
PVS, you can set your requirement for a null move anywhere inside your window,
and you advocate that that required score should be at the very end of the
window. In MTD (f), you have no choice. (That I can see.)

>>Well, if you're right, then the conclusion is that MTD (f) is not compatible
>>with null move.
>
>1) We know that null move does not work in Zugzwang positions (among others).
>
>2) With some algorithms (alpha-beta, PVS), we can detect *some* (as in
>   "extremely few") cases of Zugzwang when the null-move score is the
>   best AND inside of the window.
>
>So one way of seeing your point is "why bother detecting it in only some
>cases?".

Yes, but it could also be rephrased: "in MTD (f), you cannot detect it in those
cases, how bad is this?"

Note that null move will end up in your PV (if you treat it as a normal move) in
more than just zugzwang cases. Imagine the following: white can sacrifice a
piece with Bxh7+ Kxh7 Ng5+ Kg8 Qh5, with a mating attack. Black can delay this
by throwing away a piece with .. Bb4+ axb4, and then he can play a null move
which exhausts the available depth. The final score for the variation is roughly
equal - and this could easily be your PV. Every move is "best" - right down to
the final null move.

There is no doubt that having null moves in your PVs will cause some problems -
but it will also save some nodes. That's the general null move tradeoff - the
question is if the balance is different along the PV than outside it. Basically,
MTD (f) forces you to be more aggressive with your use of null move.

>
>Indeed I expect the change to have no effect at all in practice.  At
>the same time I can't see any benefit from doing it, as we know "in
>advance" that the heuristic does not work in those cases.  The last
>word in my case is that I certainly won't allow illegal moves in my
>PVs :)
>
>For MTD(f) and other "heavily-segmented-window" algorithms, it's
>simply not possible to detect those cases anymore.  Still the impact
>should be neglieable, so I don't claim that "MTD(f) is not compatible
>with null move"!
>
>>However, I am not sure that there is anything special about the PV.
>
>Probably not, except when displaying the PV is important (analysis, debugging
>...).
>
>>Let's assume that you have a PVS engine which treats null move as you advocate,
>>and also doesn't check for mates after a null move. (Otherwise the example will
>>need to be more complicated.) A position arises where white, to play, has a
>>winning combination Bxh7+ Kxh7 Ng5+ Kg8 Qh5 and black cannot stop mate. At depth
>>X, your engine searches this variation, plays a null move for black, runs out of
>>depth, and the score is outside the A-B bounds. Are these sorts of variations
>>really less important than variations which end up inside the PV?
>
>You can even take alpha-beta as the algorithm, since this avoids additional
>issues.
>
>>Anyway, I am not sure what the answer is. It can only be tested inside a PVS
>>engine.
>
>Me neither but thanks for bringing this subject, I will certainly
>spend some time thinking about it.
>
>>One more note: aspiration search is a less extreme form of MTD (f). If your
>>search returns from the first window with a (root) fail-high or (root) fail-low,
>>you may end up with a null move in your PV. (unless you ignore information from
>>the hash table during the re-search)
>
>Indeed I make no difference between aspiration, MTD(f), etc ... when
>reasoning about a single node.  I call them "segmented-window search
>algorithms".  The same even applies to NegaScout.
>
>Also yes, there are plenty of ways one can do things differently at PV
>nodes in PVS but it seems a common opinion is that it is a bad idea.
>

I guess not accepting a null move as a valid move at PV nodes doesn't count :)

I think there is a big practical difference between MTD (f) and PVS: in MTD (f),
you are always failing at the root. PVS is also segmented, but in practice the
general case is that you don't fail at the root. In those cases, the bounds
passed to your search are usually the "true" bounds. This could be useful
information. In fact I can't rule out that this gives PVS a decisive advantage.

>>>I think it's more complex than this.  Eventually the PV is made of two
>>>"semi-PVs" (one failing high and one failigh low) that must agree on
>>>the score.  There can't be a null move at the same place in both,
>>>since the null move can only fail high in its own node (contrary to normal
>>>moves).
>
>>Yes, true. The MTD (f) "pv" consists of following the highest fail-high at each
>>node. It has the additional property that each node along this PV will have also
>>failed low during the search. Anyway, an MTD (f) engine may end up with null
>>moves along the PV.
>
>Yes.  My point was that since the second "semi-PV" cannot have a null
>move at the same place, the PV (= sequence of optimal moves) has to be
>truncated at that point.

Well, you can truncate the display of the PV, but the damage is already done ;)

>
>Now I realise that you are talking about collecting the PV from the
>transposition table whereas I always use the model of collecting the
>semi-PVs using additional memory and then computing the true PV from
>them.  It should not make any difference in the conclusions though.
>
>It would be interesting to know how often (if at all) MTD(f) engines
>encounter null moves in the main line.  Unfortunately I expect most of
>them not to store a move at all in case of a null-move fail high (but
>keep the previously-known best move instead) AND getting the PV from
>the transposition table.  In that case there is no way of knowing ...

It shouldn't be too hard to collect a "true PV" for and MTD (f) engine, although
it would be overhead and only appropriate for debugging. Anyway I am in the
middle of a massive re-write so this test just goes on top of a growing list ;)

Note that a PVS engine should behave in the same way, if you allow it to. (Ie
rather than doing a null move search at beta, do it at alpha, with a possible
re-search at alpha-beta.)

>
>>>Note that I am not a MTD(f) expert, but very interested in reasoning
>>>concerning the PV.
>
>>Yes, same here. Of course, a lot of "search conclusions" are not reflected in
>>the PV.
>
>Hence the question "does doing things more correctly in only a few
>nodes make any difference?" :)
>

As mentioned above, it's possible that the difference is not trivial.

Vas

>>Vas
>
>Fabien.



This page took 0.04 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.