Author: Robert Hyatt
Date: 16:40:53 06/10/98
Go up one level in this thread
On June 10, 1998 at 16:33:26, Don Dailey wrote: >On June 08, 1998 at 11:26:52, Robert Hyatt wrote: > >>On June 08, 1998 at 03:03:37, Roland Pfister wrote: >> >>>Last week we discussed what to do and not do in a nullmove subtree. >>>My program Patzer used to not extend in such a branch. Bob argued >>>against it and it sounded ok to me. >>> >>>At the weekend I tried both versions and the result is that if Patzer >>>doesn't extend it is a little bit faster, but not much. But in some >>>positions it sees the solution one iteration later! >>> >>>So I changed my program to extend even in nullmove branches. >>>Thanks Bob. >>> >>>Roland >> >>Here's another "crazy one" to try. In Cray Blitz, I very carefully >>chose >>where to try a null move (non-recursive, only allowing *one* in any one >>path). I never tried it on a "PV" node for example, since such a node >>can >>not really have a null move played. And to do so would mean that the >>null >>move search might fail high (as we hope) or it might return a score >>between >>alpha and beta, but we couldn't keep it. So I simply disallowed it. >> >>I started off doing this in Crafty, but by accident, disabled the test, >>and >>the search ran faster overall. That is I *always* try a null-move >>search, >>except for when the "null-move transposition table trick" says to not >>try >>one. And surprisingly, it was/is faster. If you aren't doing this, you >>should try it... and let me know if it is faster or slower. I was >>surprised, >>and it simplified the code a bit as well since I no longer have to worry >>about >>whether a node is "ALL", "CUT" or "PV" now... and that code is now >>gone... > >Hi Bob, > >I'm pretty interested in this stuff and have played around with >all kinds of variations. > >Is my understanding correct that you are always trying a null move, >regardless of the static score? For me it seems to work best to >have a static score very close (or above) beta. The algorithm as >I once saw it in the ICCA journal used a half pawn margin. > I try it everywhere... and I use the normal alpha/beta bound, but reduce the depth by 2 plies above the normal 1 ply you would use. >Here are a couple of other ideas I would like feedback from you >and any others who have implemented null move if you are interested >in commenting. > >I found it slightly faster to simply do a test search with a zero >width alpha/beta window around beta. The idea being I only care >if we get a beta cutoff on the null move search. I'm not using >the result of one of these searches to tighten the Alpha side of >the bound either. With MTD this is a non issue but I found >it works find even with conventional alpha/beta. 99.9999% of my searches are with alpha,alpha+1 anyway, so there is no narrower window I can use, since I am using classic PVS already... and I can't tighten alpha as a result... > >I also tried using a "cheat margin" on the null move search to >coax a few more cutoffs from the search. I reasoned that if the >static (stand pat) score was already above beta, I could relax >the null move search, since it normally overstates the case anyway. >An example is setting the zero width window to be (beta-8, beta-7) >and prunning if a get a fail hi. The search must always return >the static evaluation score instead of the null move results which >is fine since I never do the search if the score is not already >above beta. > >My findings on this is that it was stable (no strange effects as >long as all your lazy evaluation and margins was correctly implemented), >and was a LARGE speedup even with small margins. The bad news >is that the speedup balanced out the benefit almost perfectly. I >could not distinguish the difference in playing strength. > >I've also experimented with the idea of not using recursion as you >seem to be doing. This should guarantee (except in zugzwang) you >NEVER lose more than you null move depth in tactics you can see, >but testing never proved one was better than the other although the >recursive version was naturally faster. Did you find a speed >difference? recursive is faster... and doesn't seem to hurt more than it helps... Null move misses some things, which is why CB is still tactically stronger than Crafty, giving it a huge hardware advantage to work, because CB uses R=1 non-recursive, so it has few null-move failures. But Crafty can go deeper overall, so this might well balance out and be better as it is now being done... so far I like it... > >Depth-3 selectivity does not work for me, although others report >great results. I always get nice speedups but find the program >weakens just enough to measure. Even when I'm very careful about >endgames and special case things. Bruce and I played some games last year with ferret using r=2 and then r=3 and we could tell no difference strength-wise... > >My biggest improvement is to not use null move near leaf nodes of >the main search. A "global" static attack test seems to be a very >nice improvement. It must be tuned but not too strict. It makes >the search much faster and it benefits from the speed. I can >easily measure the improvement in testing. It turns out that I >actually pick up a few things null move misses although visa-versa >is also true. I can only do a couple levels of these, then null >move is superior for its ability to see longer range threats. > >The basic idea of our static routine (much of it designed by Larry >Kaufman) is that we notice the highest valued piece attacked, and >then assume part of its value will be returned, so if a queen is >attacked, we assume only 2/3 of a queen is attacked. This is a >major speedup and the assumption is very good for all the pieces. >There is a value that seems to be on the threshold of right and >wrong, and it can be found by noticing a sudden drop in problem >solution depth when you get too agressive (like 1/2 attacked value.) > >I have long held that null move is not the right thing to do, and >yet I have no improvement to suggest and still use it myself. For >the time being it seems the best at long term threats, but not >quite right for short term threats. yes, although I found that as I refined things in Crafty, to get to the speed level where I am now, the null-move related losses generally have disappeared... at 4-5 plies, they will kill you.. but I generally do 7-9 in blitz, and simply don't get burned by this, at least to the point where I notice it.. > >- Don
This page took 0.03 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.