Author: Vincent Diepeveen
Date: 15:59:28 06/29/98
Go up one level in this thread
On June 29, 1998 at 15:38:00, Robert Hyatt wrote: >On June 29, 1998 at 15:03:34, Peter Kasinski wrote: > >>Could someone please explain - what does "null move R=2" mean? >>I realize this is a naive question. I actually added (what I thought was) a >>null-move logic to my program and now I wonder. >>In my code I first try a NULL move at all levels of the tree provided that last >>move was not NULL and that a (basic) zugzwang-detection test is passed. >> >>Thank you. >> >>PK. > >R=2 is simple. In a normal search, you make a move, and then call >search recursively as in value=-Search(-beta,-alpha,depth-1,etc.); > >After a null-move, you call search: > > value=-Search(-beta,-alpha,depth-1-R,etc); > >which means that you search two plies less deeply below the null than >you normally would. That's where the big savings come from, that R=2. >R=1 is more conservative. R=3 is more speculative... It doesn't matter what R you use. The more you reduce (that is what R says), the better your extensions and evaluation needs to be and the more you need to do in quiescencesearch. That's how you can see it too. You don't evaluate pins? Poor you you'll not detect them, last couple of plies. You don't do checks in q-search? Poor you you won't see mates last couple of plies. You try in fact to detect threats by giving your opponent a chance to make a move twice. So if you don't do moves that threaten you you're dead meat with nullmove last few plies. So if your search is poor in detecting threats then you can compensate that by searching deeply, that's what most programs do. Instead of detecting threats smart you simply can search another couple of plies deeper. That's only possible if your evaluation is fast, and you directly see the weakness of those programs: as soon as they play opponents that do all kind of threats then they're dead meat (tactically) when getting outsearched. Now the good new is that the chance of missing threads is limited. Very limited. Even so limited that most programs which have a quick evaluation simply don't evaluate hung pieces too much nor pins. This means that usually using nullmove doesn't give problems. There is one exception and that's zugzwang. Nullmove with reduced depth means that you need even more plies to find zugzwang. You can easily detect zugzwang by doing 2 nullmoves (as described extensively in rgcc by me), but the more you reduce the more plies you need to detect zugzwang, and in endgames with little pieces (where zugzwang is more likely) you can simply turn it off. So the weak point of nullmove is the depth reduction you do depending on the number of tactics you pick up. So the bigger this R is the harder it'll get to pick up threats. Reduction factor 3 means that last 4 plies you can simply prune. If you take into account that nullmove decreases branching factor *considerably*, then it's easy to see that the faster your hardware the more attractive nullmove will be. Instead of the Knuth theoretical branching factor of around 4.0 (hashtables reduce considerably at huge depths) in chess, You suddenly get at huge depths branching factor 2.0 - 3.0 (first couple of ply way bigger, especially ply 1). Vincent
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.