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.