Author: Don Dailey
Date: 13:33:26 06/10/98
Go up one level in this thread
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. 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. 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? 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. 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. - Don
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.