Computer Chess Club Archives


Search

Terms

Messages

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

Author: Vasik Rajlich

Date: 10:40:52 07/16/04

Go up one level in this thread


On July 16, 2004 at 12:13:25, Fabien Letouzey wrote:

>
>On July 16, 2004 at 11:36:06, Vasik Rajlich wrote:
>
>>On July 16, 2004 at 10:21:25, Fabien Letouzey wrote:
>
>>>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.
>
>Also the more inconsistencies that must be dealt with.
>
>>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.)
>
>>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.
>
>You are right of course, thanks for correcting me.
>
>>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.
>
>>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.
>
>Actually in PVS I think of every PV node as a root.  If PV nodes really are
>different (as they seem to be regarding move ordering), that would justify doing
>other things differently as well.
>

Do you mean that you order moves differently at PV nodes? I guess I should take
a look at your code. It doesn't sound like a bad idea.

>As for the "true bounds", Tord mentionned that he used some form of "aspiration"
>together with MTD(f).  The guess part of aspiration can obviously be applied to
>any algorithm and he makes some decisions during the search depending on those
>values.  So I am not sure about the "decisive advantage" although I don't like
>the idea of MTD(f) at all.

Maybe Tord found something interesting. In MTD (f) you do have root aspiration
values, but these don't seem that useful.

>
>>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 ;)
>
>Let us know of the result!  My guess is that you will never notice any blunder
>because of it, although it might occasionally appear in the PV.
>
>>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.)
>
>I thought that's what you meant above, or are you going MTD(f)? ;)

PVS with MTD (f)-like driver. My first engine was MTD (f), and I hope that tests
will justify using small/zero width windows in at least some situations. Note
that MTD (f) is a degenerate case of PVS.

>
>>>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.
>
>It's just "forward pruning at exact-score nodes" but I don't like the sound of
>it for some reason :)
>
>>Vas
>
>Fabien.

Vas



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.