Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Null-Move: Difference between R = 2 and R = 3 in action

Author: Robert Hyatt

Date: 09:14:10 07/18/02

Go up one level in this thread


On July 18, 2002 at 05:58:56, Vincent Diepeveen wrote:

>On July 17, 2002 at 13:18:40, Christophe Theron wrote:
>
>>On July 16, 2002 at 11:01:23, Vincent Diepeveen wrote:
>>
>>>On July 15, 2002 at 13:11:09, Christophe Theron wrote:
>>>
>>>>On July 15, 2002 at 08:37:34, Omid David wrote:
>>>>
>>>>>I don't think using double null-move is a good idea in practice, since in
>>>>>midgame the chance of zugzwang is negligible and thus it's superfluous (I doubt
>>>>>if even DIEP uses it). However the contribution of double null-move is that it
>>>>>gives legitimacy to the null-move pruning idea, proving that it _is_ a correct
>>>>>search method (anyway, no one doubts null-move nowadays).
>>>>
>>>>
>>>>
>>>>Why does double null move prove that null move is a correct search method????
>>>>
>>>>Doing two null moves in a row means going back to standard search (a search not
>>>>involving an illegal move like null move is).
>>>>
>>>>I fail to see how it legitimates null move.
>>>
>>>Double nullmove legitimates (duh can't you use easier to spell words)
>>>itself, for the obvious reason that it is provable now that a search
>>>depth of n ply, where i may pick n, is going to solve any problem you
>>>give it.
>>
>>
>>
>>OK, I see now.
>>
>>However, it is not true.
>>
>>Due to a nasty interaction with the hash table algorithms, just allowing 2 null
>>moves in a row will NOT solve any problem.
>
>What you refer to is a practical impossibility (assuming you have
>a efficient search) :
>
>  your assumption is that from a root position r
>  with transition of some moves to position p, side stm to move and
>  depthleft=d:
>
>  r ==> p(stm,d)
>
>  that you visit this position with properties that
>  before this move you have made 1 nullmove or less.
>
>  so ==> r , nullmove , p
>
>  Now a major problem for such an event to occur is that
>  after 1 nullmove, sides change the side to move.

Why is this a problem?  IE in my case, position P reached thru a path
with a null-move and position P reached thru a path without null-move
are _unique_ positions...



>
>However i don't know how you do this in tiger, but what we are
>interested in is the mainline. We aren't interested in a bunch
>of stupid moves which can go to this position x.
>
>In fact we already don't reach it by stupid moves because in
>DIEP i directly try the nullmove, before searching other moves.
>
>So we would already have had a cutoff before getting to p with stm
>to move and >= d.
>
>Secondly, i want to see zugzwang in mainline, i don't care for
>sidelines.
>
>So from a mainline
>  r , firstmove , nullmove , p(stm,d)
>
>Somehow you claim that you managed to get in p without already
>getting a cutoff by nullmove?
>
>That's impossible, because you would already have had a cutoff!
>
>Now the second position where we *do* find a zugzwang:
>
>r , firstmove , nullmove , nullmove , p(stm,d)
>
>Your assumption is now that somehow we get with transposition of hashtable
>a cutoff. That means you already searched p *somehow* with >= d for stm,
>before in the tree. that means that you did get a fail low after:
>
>r , firstmove , nullmove  score < beta,
>
>otherwise a transposition is not possible to position p(stm,d).
>
>Now let's take a look at *which* position we got the < beta score:
>
>r , firstmove , p(stm,d+R+2) nullmove
>
>If we already get a score < beta *somehow* in position p(stm,> d)
>that means obviously we already caught the zugzwang, so we still
>find the zugzwang then by means of transposition after
>
>r , firstmove , transposition , p(stm,<= d)
>
>Best regards,
>Vincent
>
>
>>It is necessary, in order to solve any problem, to add some logic in the HT
>>algorithms, or to disable the HT completely.
>>
>>
>>
>>    Christophe
>>
>>
>>
>>
>>>Normal nullmove, if you remember the discussions a few years ago,
>>>especially around 98 and 99, it was told to be an inferior way of
>>>search, because for *any* selfpicked depth n for the nullmove search
>>>it could conclude less than a small outdated fullwidth search, so was
>>>the theory.
>>>
>>>This is not true of course.
>>>
>>>Reality is that only a few problems need a bit bigger search depth
>>>with double nullmove, and most are far endgames.
>>>
>>>In middlegame it's very seldom one needs 3 ply more than a fullwidth
>>>search would get.
>>>
>>>Note that getting a fullwidth search of more than 12 ply is impossible
>>>whereas most get 14-15 ply with nullmove nowadays easily in tournament
>>>practice.
>>>
>>>DIEP's probably only exception here, it needs a supercomputer to get
>>>that depth ;)
>>>
>>>
>>>
>>>
>>>>
>>>>
>>>>    Christophe



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