Computer Chess Club Archives


Search

Terms

Messages

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

Author: Christophe Theron

Date: 13:28:41 07/21/02

Go up one level in this thread


On July 20, 2002 at 22:39:24, Robert Hyatt wrote:

>On July 20, 2002 at 15:44:00, Christophe Theron wrote:
>
>>On July 19, 2002 at 21:42:29, Robert Hyatt wrote:
>>
>>>On July 19, 2002 at 15:25:48, Christophe Theron wrote:
>>>
>>>>On July 18, 2002 at 12:14:10, Robert Hyatt wrote:
>>>>
>>>>>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...
>>>>
>>>>
>>>>
>>>>If so, your programs loses a lot of opportunities to prune because it detects
>>>>less transpositions. But maybe it avoids some problems and is benefical in the
>>>>end, I do not know.
>>>>
>>>>And now what about a position reached thru 2 null moves?
>>>
>>>I don't do double null-move so I don't deal with it, at least in back-to-back
>>>nulls that would undo the hash update of course...
>>
>>
>>
>>OK, so you mean that when you do a null move you XOR something in the hash key
>>to keep track of this?
>
>Yes.  Otherwise I found massive "artifacts" lying around from time to time.
>Ditto for repetitions...  since I use the hash signature to detect this as
>well...
>
>
>
>>
>>I deduce this from the fact that you say that doing two null moves "undo the
>>hash update".
>>
>>I'm sorry, I know I could find this in Crafty's sources, but I have not read
>>them since years.
>>
>>Or do you mean that the null move just changes the side to move, which
>>effectively XORs something (the hash key of the side to move).
>
>I have a side to move as well.  But I found a few places where this would
>produce phoney results.  I felt it more logical to treat a position where
>a null-move was played as different from a position where it was not.  Since
>repetitions can figure into that in strange ways...
>
>I won't say it has to be done.  I simply did it to solve problems that I
>saw.  Back in the late 80's when I first did null-move in Cray Blitz in
>fact...



I guess doing the experiment again could be interesting.

I say this also for my way of doing it, which leaves the door open to problems
like the one I have described (and which I solve by a specific change in the
search algorithm) and to the problems you are talking about.





>>In this case you can get a transposition by reaching a position thru a null move
>
>Yes...  yet it isn't really the "same" position and it caused problems when
>it happened...  My MakeMove() function mangles the hash signature for all
>moves, including a null.  I use a simpler mangle for side to move, just
>a simple "complement" operation to invert all 64 hash signature bits.  Null-move
>has a unique random number to xor in.  I will stop to think about whether
>I should have more than one however...



Well, after 2 null moves (disregarding who did them), the hash key alteration
caused by the first one disappears.

But maybe that after 2 null moves it's not that important anymore (especially as
you don't allow 2 null moves in a row).



    Christophe



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