Computer Chess Club Archives


Search

Terms

Messages

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

Author: Vasik Rajlich

Date: 06:15:17 07/16/04

Go up one level in this thread


On July 16, 2004 at 07:24:28, Fabien Letouzey wrote:

>On July 16, 2004 at 06:33:20, Vasik Rajlich wrote:
>
>>There is one interesting caveat in comparison to PVS. A PVS engine has the
>>choice to treat null move as any normal move, or to require that the null move
>>fails high. (ie within bounds, but not fail high, is not enough) The latter is
>>somewhat logical, and IIRC this is what Crafty does.
>
>I think it's much more than somewhat logical!!!
>
>IIUC, you are talking about allowing null moves in the PV (in PVS).
>
>Imagine a PV node where null move gets the best score (inside of the
>window).  That means passing is the best option, which is the
>characteristic of Zugzwang positions.  They are exactly the positions
>in which you don't want to try null move :)
>
>One of the reasons why null-move pruning is safe is that it is only
>"kept" in incorrect lines, never in the PV.
>

Well, if you're right, then the conclusion is that MTD (f) is not compatible
with null move.

However, I am not sure that there is anything special about the PV.

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?

Anyway, I am not sure what the answer is. It can only be tested inside a PVS
engine.

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)

>>An MTD (f) engine must treat a null move as a normal move. I couldn't come up
>>with a way to circumvent this restriction. It seems to be an inherent
>>restriction of the MTD (f) search.
>
>>Another way to look at this: an MTD (f) engine must accept null moves along the
>>"pv", where "pv" is defined as following the fail-high moves, and
>>highest-scoring fail-low moves.
>
>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.

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

Vas

>Fabien.



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