Author: Christophe Theron
Date: 12:44:00 07/20/02
Go up one level in this thread
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?
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).
In this case you can get a transposition by reaching a position thru a null move
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 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.