Author: Robert Hyatt
Date: 18:42:29 07/19/02
Go up one level in this thread
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... > >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.