Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Zero-width Window Null Move Search

Author: Robert Hyatt

Date: 07:08:22 06/16/98

Go up one level in this thread


On June 16, 1998 at 02:21:21, Dezhi Zhao wrote:

>
>On June 15, 1998 at 13:06:18, Vincent Diepeveen wrote:
>
>>
>>On June 15, 1998 at 04:52:16, Dezhi Zhao wrote:
>>
>>>In some earlier posts by Don Dailey and others, they mentioned
>>>about zero-width window null move search and said it's an efficent
>>>way to implement null move search. So I compared the zero-width null
>>>move to the original full-width with my Xiangqi (Chinese chess) PVS
>>>engine.
>>>Here is the results of playing 20 moves (same path for both method,
>>>without opening book) from the initial position.
>>>
>>>The m/c usually searches 2 to 4M nodes for each posoition.
>>>If the transposition table is cleared between searches, the savings
>>>of zero-width are generally around serveral hundreds of nodes,
>>>and the max is 9K for one position.
>>>If the transposition table is partially cleared (keep only last
>>>iteration
>>>entries) between searches, the savings become hard to interpret. You
>>>save several hundreds of nodes in a postion, lose that in the
>>>following position, and ocassionally lose much more than than previous
>>>saving (save 8.4K and lose 140K in the next for example).
>>>
>>>I think that the savings are negligible, which are caused by the fact
>>>that in PVS most of the nodes are of zero-width window already.
>>>
>>>These results also remind me of the word "vapor-ware" that Dr. Hyatt
>>>called NegaScout over PVS.  So I checked Crafty 14.13 again,  and found
>>>that Crafty uses full-width window null move search. Why? My best guess
>>>is that Dr. Hyatt has done extensive tests over null move search
>>>abnormaly
>>>as he mentioned several times in CCC, and found null move search window
>>>is
>>>related to the abnormaly. Am I right?
>>
>>It all depends on how much do you extend when you have a nullmove
>>search, and do you do checks in q-search?
>>
>>If you don't extend too much and don't do checks in q-search, then
>>it will not make much different i guess.
>>
>I don't extend much. Currently only check and mate extensions are applied.
>I will add capture/recapture extensions latter and do the experiment again.
>>
>>I use a higher reduction factor to limit the number of nodes needed for
>>q-search. Diep extends so many stupid lines that R=2 versus R=3 saves
>>me a ply sometimes, but average many tens of %
>
>I had similar results with R = 3. However I found R = 3 produces weak
>moves in defensive (behind) positions.
>>
>>Now that i use R=3 instead of R=2 i still  see the difference
>>between zero window of nullmove anymore, but less than with R=2.
>I use R = 2. Althougth R = 3
>>
>>The difference however is still there in favor for the zero window nullmove,
>>because you only need that >= beta bound.
>Yes. The impleamentation is easy, just 1 line to be modified. Hovever
>the difference is hard to tell in my tests.  I got an impression that it helps
>in highly tactical positions in the order of Kilo/Mega and if you keep
>the old transposition entries between search, you lose the savings
>in the next search. What concerns me more than the elusive speedup is
>the null move search abnormaly. It *MIGHT* be related to null move search
>window. I have no enough experience on that.  Hopefully after Dr. Hyatt
>finishing the experiment, he could give a conclusion on this.
>
>
>Best Regards
>
>Dezhi Zhao
>
>
>
>>
>>Greetings,
>>Vincent


as promised, I tested this on crafty yesterday, but CCC was dead in the
water so I couldn't post the results.  I ran the 24 position Bratko-
Kopec test to a fixed depth of 9 plies, using a single processor search
to provide repeatable node counts.  here is the results using the normal
null-move search that is in crafty:  (window=[alpha,beta]):

total positions searched..........        24
number right......................        19
number wrong......................         5
total nodes searched..............34195953.0
average search depth..............       9.0
nodes per second..................     75316

and here are the results obtained by modifying the null-move search
window to be [beta-1,beta]:

total positions searched..........        24
number right......................        19
number wrong......................         5
total nodes searched..............34195500.0
average search depth..............       9.0
nodes per second..................     75476

so this is an improvement of 493 nodes.  :)

As I said before, nearly 100% of the searches in PVS are made with a
window of alpha,alpha+1, so that this change doesn't have much effect
at all. less than 1/1000th of one percent in fact...



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