Author: Vincent Diepeveen
Date: 00:56:08 07/15/01
Go up one level in this thread
On July 14, 2001 at 03:38:11, Uri Blass wrote: >On July 13, 2001 at 22:40:39, Robert Hyatt wrote: > >>On July 13, 2001 at 16:50:26, Uri Blass wrote: >> >>>On July 13, 2001 at 14:25:23, Robert Hyatt wrote: >>> >>>>On July 13, 2001 at 12:28:01, Steve Maughan wrote: >>>> >>>>>I'm thinking of implementing double null move in my program. Now as far as I >>>>>know the most conventional way is to do the normal null move search and if there >>>>>is a cutoff follow it with a normal search at reduced depth to confirm no >>>>>zugwag. However I do remember that someone here (Vincent?) outlined a different >>>>>way of doing double null move. Is there another way? If there is, what are the >>>>>pros and cons of each? >>>>> >>>>>Thanks, >>>>> >>>>>Steve >>>> >>>> >>>>That's the gist of it. If the position is a zugzwang position, the second >>>>null-move search will fail high, which will cause the first to fail low and >>>>you don't run into the zug problem. >>>> >>>>The downside is the cost. The second null will fail low most of the time and >>>>just generate wasted nodes. >>>> >>>>The other downside is that not all null-positions are zugzwang problems. In >>>>fact, most null-move problems are caused by the R-value which bring the horizon >>>>too close to spot a tactical threat. Double null won't find any of those... >>>> >>>>So you expend quite a bit of effort, to eliminate one small part of the total >>>>problem... >>> >>>If you search to clearly reduced depth(for example before normal search with >>>null move pruning to depth d when d>=6 you search without null move to depth >>>d/2-2) then you may be less than 1% slower. >>> >>>I believe that it is a good deal to be 1% slower in order to avoid not seeing >>>simple zunzwangs. >>> >>>I guess that you may earn 3 elo from not falling in some zunzwangs and lose only >>>1 elo from being slightly slower. >>> >>>Uri >> >> >>It is far worse than 1%, as you try a null move after _every_ null move, except >>you never do 3 in a row. If you are searching to 14 plies, and you try a null >>move at ply=2, remaining depth would be 9 (12 - R=2 - 1). If you do a null-move >>search at ply=3, remaining depth would be 6 (9 - R=2 - 1). A 6 ply search is >>non-trivial. >> >>Do a bunch of them and it is _really_ non-trivial... > >I doubt it. > >remember that we are talking about 6 plies with null move except the first move >when 2 nulls in a row is not possible because in the 6 ply search because the >remaining depth is going to be negative in this case. > >The original problem was 12 plies with null move pruning. > >You start solving a problem of 12 plies search with null move pruning by solving >a problem of 6 plies search with null move pruning except the first move. > >For every problem of 12 plies you have at most one problem of 6 plies(there are >cases when the 12 plies are after null so the first 2 nulls in a row are not >allowed and you have not 6 plies search problem). > >If you assume branching factor of 3 then it seems to me that you are only >1/3^6=1/729 slower that is less than 1%. It is even less as that, because the positions you get on the board you already have stored in transposition table of course from earlier searches. So the detection is for free. Note that theoretical the detection could go wrong, but in reality i have never had such a case. 1 position x, white to move 2 nullmove ==> white nullmoves 3 nullmove ==> black nullmoves 4 position x, white to move with reduced depth. Suppose i have now stored position X in hashtable with a score >= beta and suppose that it is based upon a nullmove in position X. So on paper you can do 3 nullmoves then in a row instead of 2. Amazingly i have never had a zugzwang fail because of this. >Uri
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.