Author: Christophe Theron
Date: 19:52:34 02/07/98
Go up one level in this thread
On February 07, 1998 at 19:49:58, Robert Hyatt wrote:
>On February 07, 1998 at 18:48:18, Thorsten Czub wrote:
>
>>>I'm not so sure. Ed has said "no null move" for Rebel. I believe Marty
>>>said the same about Mchess. Looking at Hiarcs output, it seems that it
>>>doesn't either, based on the depth of search reported...
>>>The only one I
>>>am certain about if Fritz, of course, that is a known null-mover. Bruce
>>>and I are also big users of course. I've used it since Beal's first
>>>paper
>>>on the subject in 1980-81 or so...
>>
>>If null-move is so beuatiful and works so effective and without
>>overseeing important stuff, and gives more depth , why do you think is
>>rebel and mchess and hiarcs not using it ?
>>How can rebel9 and hiarcs6 lead the ssdf-list without null-move?
>>
>
>null move is a form of forward pruning, but not the only form. The
>advantage for null-move is that it is a "domain independent" form or
>pruning... it has nothing to do with chess and works just as well in
>other games. One simple comparison is current Crafty vs Blitz IV, circa
>1977 or so. The code that selects moves to search (or, which moves to
>toss out, depending on your perspective) was over 30,000 lines of code.
>The search for Crafty, in contrast, is a few hundred lines at best. So
>the attractiveness, for me, is that it lets me write a simple, bug-free
>search, and get on to other things. It exhibits a failure here and
>there.
>So does Rebel and the others. My thinking is that if I am going to have
>to
>accept errors here and there, I'd just as soon do it with the simplest
>code
>I can.
The "null move observation" (NMO) can be used in other ways than just
doing a null move.
I call the "null move observation" (NMO) the fact that in chess, with
little exceptions, there is always a move that is better than doing
nothing (which is not allowed, but let's skip this detail). Please note
that this is not very "domain independent". For example, NMO doesn't
apply to Othello/Reversi.
When you understand this brilliant idea, you can write different
algorithms to use it.
Real null movers really do a "null" move, and call the search
recursively to see if the opponent can do something wrong to them. If
not, and if the score of this null move is "enough", they stop studying
the variation. The move just before the "null" is not a very good one,
since you refute it by doing nothing!
I think every chess player uses this idea. When I analyze a position, I
often imagine I can do several moves in a row, with no reply from my
opponent. If this sequence of move does nothing, it's not worth thinking
about it any more. This is the case when you try to figure out how to
attack the opponent's king: "First, I move my knight near the king, then
I move my queen to threaten mate". If this works, you start thinking
about: "now, what can the opponent do after I move my knight to stop the
attack?".
But there are others ways to make a good usage of the NMO.
For example, you can just look at the position with your static exchange
evaluator to see if you have a piece "en prise". If the score of the
position is very good for you (eval>=beta) and your opponent doesn't
make any threat, it's not useful to study this line (the opponent's
previous move(s) was(were) not very good). Do this kind of pruning only
when you are quite deep in the search, because it is less accurate than
a real null move!
Another related pruning technique is "Fail High Reduction". If the score
of the position is very good for you (eval>=beta) and your opponent
makes no threat, instead of pruning the line you just decrease the
search depth a little bit. Your search is faster, and (I hope) you make
few errors. This is described by R. Feldmann in "Advances in Computer
Chess 8".
As you see, the general idea behind null move and a huge familiy of
pruning techniques is trying to detect the threats.
I would bet that many people claiming that they don't use null move are
only playing with the words. They use some kind of algorithm, like the 2
mentionned above, that is only a variation around the "null move
observation".
I think that no serious chess program can be written without taking
advantage of the NMO. Of course, you see which programs I am thinking
about.
There are other ways to do forward pruning, but I think you can use them
together with the NMO pruning.
BTW, we can reach here the old debate between fast and slow programs. A
"real" null mover does not have to evaluate threats statically, so
doesn't need to use a (always slow) exchange evaluator. A program taking
advantage of the NMO by evaluating threats in every node will be slower,
but will look at less nodes.
But the two are in fact using the same idea, and from my experience it's
not clear which way is the best. You can talk about it forever. IMO the
only point is to realize the power of the NMO idea.
>>Could we discuss null move, or is null move so SURE that we don't have
>>to discuss it ? And if it is so sure, why the hell don't they use it
>>?!!?
I think they use NMO, which is the same idea. They can also use other
tricks, of course.
Christophe
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.