Computer Chess Club Archives


Search

Terms

Messages

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

Author: Fabien Letouzey

Date: 07:21:25 07/16/04

Go up one level in this thread



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!

>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?".

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 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.

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 ...

>>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?" :)

>Vas

Fabien.




This page took 0.06 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.