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