Computer Chess Club Archives


Search

Terms

Messages

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

Author: Robert Hyatt

Date: 19:39:24 07/20/02

Go up one level in this thread


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




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


>path and thru a no-null-move path.
>
>
>
>    Christophe
>
>
>
>
>
>
>>>The problem arises when in a previous iteration you have seen a position from
>>>which you have tried a null move. The resulting search depth was so small that
>>>trying a second null move (double null move) after it was not possible (lack of
>>>depth).
>>>
>>>Unfortunately this was a zugzwang position, but as you did not have enough depth
>>>for double null move to detect it, so you store a very wrong score for the
>>>position in the HT.
>>>
>>>This problem is supposed to be solved later (with bigger depth) with the help of
>>>double null move. But look at what happens:
>>>
>>>Now you have in the HT a position with a searched depth of D, but actually it
>>>has been searched with a null move to D-R.
>>>
>>>At the next iteration, provided that now the position is encountered with a
>>>depth big enough to allow for two null moves in a row, the remaining depth after
>>>the second null move is going to be smaller than the depth stored in the HT for
>>>this position (remember that position+null+null=same position, so we are going
>>>to find this position in the HT).
>>>
>>>So the score stored in the HT is going to be brought again, and the position
>>>stored again in the same HT slot, with the same wrong score, but now with an
>>>ever bigger depth.
>>>
>>>This problem repeats at every iteration. In the end double null move FAILS to
>>>detect that zugzwang.
>>
>>
>>I don't disagree.  Note that I am not using double null and don't make any
>>claims about it at all since I don't use it.
>>
>>>
>>>Some additional logic must be added to the search algorithm to successfully
>>>detect zugzwangs.
>>>
>>>
>>>
>>>    Christophe



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