Null-move zugzwang avoidance, Jun '95 ICCAJ
brucemo
There's an article in the June '95 ICCA Journal, entitled "A null-move
technique impervious to zugzwang." It's by Stefan Plenkner.
I stumbled across this while I was looking for something else last night,
and figured I'd give the article a closer look. I've heard rumors that the
technique described in the article has some problems, so I hadn't
experiemented with this, but now my interest is piqued and I figured I ask
around and see if I can find the source of these rumors.
The article is not very clearly written, so I'm having to guess a little
bit about what is being suggested. Apparently, the technique is to do a
null-move search like normal, but if you come back with a value that will
let you prune, you do a verification search. In the verification search,
if you use a R=2 null-move search, you apparently do an R=3 verification
search, which is a normal search in which you can't skip a move at the
root. If this comes back with a value that lets you prune, you prune,
otherwise you assume you were in zugzwang, so you don't prune. One other
thing: this verification search has null-move turned absolutely OFF within
it, so you can't do any null moves inside this verification search.
The article provides three test examples. They are all cases where
null-move screws up. Times are given for solution given three test
programs: 1) a program with null moves absolutely turned off (this is
called in the article "brute force"), 2) a program with null moves turned
on even in low-material endings, and 3) a program that utilizes this new
technique.
In all cases the new technique is faster than brute force, and both the new
technique and brute force are faster than null move. In two cases,
null-move did not return a solution.
I'm skeptical of this technique for a few reasons.
1) I see no statistics as to how fast this technique is in cases where you
don't have this horrible null move pathology. If null move lets you reach
depth D in X seconds, and brute force lets you reach depth D in 5X seconds,
and this technique lets you reach depth D in 3X seconds, I am going to
stick with null move. Maybe if it gets to depth D in 1.03X seconds I'd do
it, but there is nothing to suggest that this extra null-move-disabled
verification search doesn't add way more than 3% overhead in the common
case. I suspect this technique would result in a big slowdown, since there
are a lot of cases now where you do a quick null-move search and
immediately prune. In the new case you'd have to do another search after
that, this one with a lot more nodes since you can't use null-move
internally (maybe you could break with the article and use null-move
internally, but this re-search might still be expensive).
2) I see no statistics as to how often null-move pathological cases happen
-- in other words, has the program been strengthened or weakened? Sure, we
all know of cases where a program gets attacked and doesn't see the attack
until too late, because of null-move, but how often does this happen
really, and would you even still be in the game at that point if you hadn't
been using null-move, perhaps you would have gotten blasted already because
of decreased search depth? Increased accuracy is a great thing, but it is
probably not worth markedly reduced search speed, and it may not be worth
even minimally reduced search speed.
If anyone has experiemented with this new technique, please post results.
bruce
Robert Hyatt
brucemo (bru...@nwlink.com) wrote:
: There's an article in the June '95 ICCA Journal, entitled "A null-move
I tried it 6-8 months ago when it first surfaced. I personally didn't like
it because it is still a shallower search, just not a null-move search. It
looks at more nodes as a result, and often discards the null-move search fail
high when it shouldn't. More at the end of this on null-move in general...
I think either Mark or John suggested this to me. It was trivial to add,
but is way conservative I think.
:
: 2) I see no statistics as to how often null-move pathological cases happen
: -- in other words, has the program been strengthened or weakened? Sure, we
: all know of cases where a program gets attacked and doesn't see the attack
: until too late, because of null-move, but how often does this happen
: really, and would you even still be in the game at that point if you hadn't
: been using null-move, perhaps you would have gotten blasted already because
: of decreased search depth? Increased accuracy is a great thing, but it is
: probably not worth markedly reduced search speed, and it may not be worth
: even minimally reduced search speed.
:
: If anyone has experiemented with this new technique, please post results.
:
: bruce
Many ask about null-move, and one of the most common things I hear is how
"null-move makes a tactical search go deep." It turns out this is wrong.
What really happens is that null-move makes a program play better *positionally*
and *not* tactically. why? Because null-move really makes most programs take
an additional ply or two (or sometimes way more) to find a tactical move that
a non-null-move program will find much earlier. however, the overall search
depth is much deeper, although the tactical lines are somewhat "damaged" by
the null-move. The benefit, however, is the increased depth, which aids
positional chess (if you do tip evaluation of course.. :) ). So what if
null-move lets you search 1 ply deeper in the middlegame. tactically it takes
that extra ply and then some to make up for what null-move overlooks. But
that extra ply sure is nice when you see that you get a passed pawn, or a
strong outpost, or something you wouldn't see with a shallower search. Lots
of ideas about eliminating the "error" in null-move search have surfaced. All
are ideas that make it more conservative. I've learned to live with it and
work on speed and knowledge to offset the errors this produces. Against humans
I think it's devastating. Against other computers, it becomes more risky
because of the sometimes silly horizon effects it introduces tactically...
Bob
Joe Stella
brucemo <bru...@nwlink.com> wrote:
>There's an article in the June '95 ICCA Journal, entitled "A null-move
>technique impervious to zugzwang." It's by Stefan Plenkner.
>[...]
>If anyone has experiemented with this new technique, please post results.
>bruce
I experimented with this when the article first came out. I think
I get the best results if I do a simple null move search in the midgame,
but do the verification test in the endgame. When the endgame is
just king and pawn, I shut off null moves altogether. This seems to
offer a good balance between speed and the possibility of overlooking
something.
Joe Stella
Chris Whittington
brucemo <bru...@nwlink.com> wrote:
>
> There's an article in the June '95 ICCA Journal, entitled "A null-move
> technique impervious to zugzwang." It's by Stefan Plenkner.
>
Its one of the problems of 'knowledge'.
Whatever you program costs processor time.
Its a trade off between the benefits of the knowledge (ie. finding
stuff that wouldn't otherwise be found), and its cost (ie slowing
down the search in all those other cases).
It seems to me that the more knowledge there is in a program, the
greater the problem, since additional knowledge increments are likely
to give 'less' and cost 'more'.
Maybe Gillgasch and pre-processing is ultimately more effective :(
Or where is the balance ?
Or does loadsa knowledge win in the end ?
My jury is still out.
Chris Whittington
>
> 2) I see no statistics as to how often null-move pathological cases happen
> -- in other words, has the program been strengthened or weakened? Sure, we
> all know of cases where a program gets attacked and doesn't see the attack
> until too late, because of null-move, but how often does this happen
> really, and would you even still be in the game at that point if you hadn't
> been using null-move, perhaps you would have gotten blasted already because
> of decreased search depth? Increased accuracy is a great thing, but it is
> probably not worth markedly reduced search speed, and it may not be worth
> even minimally reduced search speed.
>
brucemo
Joe Stella wrote:
> I experimented with this when the article first came out. I think
> I get the best results if I do a simple null move search in the midgame,
> but do the verification test in the endgame. When the endgame is
> just king and pawn, I shut off null moves altogether. This seems to
> offer a good balance between speed and the possibility of overlooking
> something.
I do null move all the way to K+P, then I turn it off.
It'd be interesting to know how this verification search affects your
speed. Does this make you closer to the speed you'd get with null move
clear off, or are you closer to where you'd get with it turned on? If
you're only 10% slower than null move this way, sounds like it might be
worth doing, because minor-piece zugzwangs do happen, but if you are 2X
slower than you'd be with null move, maybe it'd be a good idea to just
concede the games with zugzwang elements, eh?
bruce
Joe Stella
brucemo <bru...@nwlink.com> wrote:
>It'd be interesting to know how this verification search affects your
>speed. Does this make you closer to the speed you'd get with null move
>clear off, or are you closer to where you'd get with it turned on?
>[...]
>bruce
I tested this with verification search always on vs. always off, and
the difference seems to be about 7% on average.
This makes sense to me, because it involves doing a depth reduced (r=2)
search; so at most it can only add as much time as it would take to do a
complete search to depth d-2 where d is the depth of the main search.
Even if your branching factor is as low as 3, this will therefore add
1/9 of the search time, or 11% worst case. If the branching factor is
bigger, the percentage will be less. And you don't do the verification
search all the time, so this should also make it less.
Just as a side note, I allow null moves to occur during the verification
search (but not on the current ply, of course, because then the verification
search will be the same as the null move search). I tested this on the
well-known position where White plays Rd1 followed by Rf1 to checkmate
Black -- you probably know it, but if anyone wants me to post it I can
dig it up...
Joe Stella
Jay Scott
In article <58amds$m...@juniper.cis.uab.edu>, Robert Hyatt (hy...@crafty.cis.uab.edu) wrote:
>Many ask about null-move, and one of the most common things I hear is how
>"null-move makes a tactical search go deep." It turns out this is wrong.
>What really happens is that null-move makes a program play better *positionally*
>and *not* tactically. why? Because null-move really makes most programs take
>an additional ply or two (or sometimes way more) to find a tactical move that
>a non-null-move program will find much earlier. however, the overall search
>depth is much deeper, although the tactical lines are somewhat "damaged" by
>the null-move. The benefit, however, is the increased depth, which aids
>positional chess (if you do tip evaluation of course.. :) ).
Hmm. So how do you explain that Fritz is so strong?
Jay Scott <j...@forum.swarthmore.edu>
Machine Learning in Games:
http://forum.swarthmore.edu/~jay/learn-game/index.html
Robert Hyatt
Jay Scott (j...@forum.swarthmore.edu) wrote:
: In article <58amds$m...@juniper.cis.uab.edu>, Robert Hyatt (hy...@crafty.cis.uab.edu) wrote:
: >Many ask about null-move, and one of the most common things I hear is how
: >"null-move makes a tactical search go deep." It turns out this is wrong.
: >What really happens is that null-move makes a program play better *positionally*
: >and *not* tactically. why? Because null-move really makes most programs take
: >an additional ply or two (or sometimes way more) to find a tactical move that
: >a non-null-move program will find much earlier. however, the overall search
: >depth is much deeper, although the tactical lines are somewhat "damaged" by
: >the null-move. The benefit, however, is the increased depth, which aids
: >positional chess (if you do tip evaluation of course.. :) ).
: Hmm. So how do you explain that Fritz is so strong?
:
: Jay Scott <j...@forum.swarthmore.edu>
:
: Machine Learning in Games:
: http://forum.swarthmore.edu/~jay/learn-game/index.html
Because he's doing some clever forward-pruning too... and gets a ply or
two more than the next closest program. However, his forward pruning also
causes problems. It's a very good program. It's not the *best* by a
fair amount however...
Jay Scott
In article <32AA77...@nwlink.com>, brucemo (bru...@nwlink.com) wrote:
>I do null move all the way to K+P, then I turn it off.
How well does it work in same-color B+P endings? Key lines
in those endings tend to feature zugzwang.
Robert Hyatt
Jay Scott (j...@forum.swarthmore.edu) wrote:
Crafty does the same, that is, it uses null-move until there are no
pieces for the side in question and only then turns null-move off. I'm
sure there are errors, but the extra 2 plies or so make the errors fade
away in most cases... I haven't seen a problem in the games I've analyzed
to date... although that certainly doesn't mean there aren't plenty...
Bob
mclane
j...@forum.swarthmore.edu (Jay Scott) wrote:
>In article <58amds$m...@juniper.cis.uab.edu>, Robert Hyatt (hy...@crafty.cis.uab.edu) wrote:
>>Many ask about null-move, and one of the most common things I hear is how
>>"null-move makes a tactical search go deep." It turns out this is wrong.
>>What really happens is that null-move makes a program play better *positionally*
>>and *not* tactically. why? Because null-move really makes most programs take
>>an additional ply or two (or sometimes way more) to find a tactical move that
>>a non-null-move program will find much earlier. however, the overall search
>>depth is much deeper, although the tactical lines are somewhat "damaged" by
>>the null-move. The benefit, however, is the increased depth, which aids
>>positional chess (if you do tip evaluation of course.. :) ).
>Hmm. So how do you explain that Fritz is so strong?
SO strong?!
Depends what you understand on strong!
Now you will answer: ELO-rating.
Ok, If you are a dino and I am a mice, you can kill me with one
foot-step.
But maybe tomorrow all dino's are killed because a asteroid falls
on earth and only the small animals will survive.
If the mass is the ELO, than you are right: Fritz has much ELO like
the dino is very big.
But if evolution is the scale, than the dino will die.
Null-move and pre-processing has not much to do with chess.
It has something to do with NOT PLAYING CHESS.
It has something to do with search-ideas.
Being a capitalist has nothing to do with being a
good-fair-human-being.
If somebody is rich it does not imply that he is very intelligent.
In a society where we have many freedom and some rules, induviduals
that cheat and lie will win (in the first period) very clever against
the ones that do not cheat.
Capitalism is making money out of the fact that other people have no
rights, no money or were born into a poor country.
Using them as a working - instrument for me, using humans liike
machines, using them to PRODUCE wery cheap, and then to sell it into
rich countrys, makes a real capitalist.
But this has nothing to do with life.
Like Null-move has nothing to do with chess.
Capitalists are like null-movers, they profit without knowing about
the reasons. And they are not interested in knowing..Everything that
counts is ELO / MONEY.
brucemo
Jay Scott wrote:
>
> In article <58amds$m...@juniper.cis.uab.edu>, Robert Hyatt (hy...@crafty.cis.uab.edu) wrote:
> >"null-move makes a tactical search go deep." It turns out this is wrong.
> >What really happens is that null-move makes a program play better *positionally*
> >and *not* tactically. why? Because null-move really makes most programs take
> >an additional ply or two (or sometimes way more) to find a tactical move that
> >a non-null-move program will find much earlier. however, the overall search
> >depth is much deeper, although the tactical lines are somewhat "damaged" by
> >the null-move. The benefit, however, is the increased depth, which aids
> >positional chess (if you do tip evaluation of course.. :) ).
>
Responding to Hyatt, whose post is probably stuck in Germany again.
Null move does make tactical search faster. Take it out and check your WAC scores, Bob.
bruce
Robert Hyatt
mclane (mcl...@prima.ruhr.de) wrote:
: j...@forum.swarthmore.edu (Jay Scott) wrote:
:
: >In article <58amds$m...@juniper.cis.uab.edu>, Robert Hyatt (hy...@crafty.cis.uab.edu) wrote:
: >>"null-move makes a tactical search go deep." It turns out this is wrong.
: >>What really happens is that null-move makes a program play better *positionally*
: >>and *not* tactically. why? Because null-move really makes most programs take
: >>an additional ply or two (or sometimes way more) to find a tactical move that
: >>a non-null-move program will find much earlier. however, the overall search
: >>depth is much deeper, although the tactical lines are somewhat "damaged" by
: >>the null-move. The benefit, however, is the increased depth, which aids
: >>positional chess (if you do tip evaluation of course.. :) ).
: >Hmm. So how do you explain that Fritz is so strong?
:
: SO strong?!
Do I conclude that (a) you don't like capitalists; (b) you don't like
null-move; (c) you don't like capitalists or null-move; or (d) something
else. Thats all I could parse from the above. :)
Robert Hyatt
brucemo (bru...@nwlink.com) wrote:
: Jay Scott wrote:
: >
: > In article <58amds$m...@juniper.cis.uab.edu>, Robert Hyatt (hy...@crafty.cis.uab.edu) wrote:
: > >"null-move makes a tactical search go deep." It turns out this is wrong.
: > >What really happens is that null-move makes a program play better *positionally*
: > >and *not* tactically. why? Because null-move really makes most programs take
: > >an additional ply or two (or sometimes way more) to find a tactical move that
: > >a non-null-move program will find much earlier. however, the overall search
: > >depth is much deeper, although the tactical lines are somewhat "damaged" by
: > >the null-move. The benefit, however, is the increased depth, which aids
: > >positional chess (if you do tip evaluation of course.. :) ).
: > Hmm. So how do you explain that Fritz is so strong?
:
:
: Null move does make tactical search faster. Take it out and check your WAC scores, Bob.
:
: bruce
I'd partially agree. However it also makes most positions take at least one
ply deeper to solve than without null-move. I've come to consider null-move
a "wash" tactically, but the extra 1-2 plies along lines where the current
score is not "way out of bounds" seems to really help positional play a lot.
Bob
brucemo
Jay Scott wrote:
>
> In article <32AA77...@nwlink.com>, brucemo (bru...@nwlink.com) wrote:
> >I do null move all the way to K+P, then I turn it off.
>
> How well does it work in same-color B+P endings? Key lines
> in those endings tend to feature zugzwang.
>
>
> Machine Learning in Games:
> http://forum.swarthmore.edu/~jay/learn-game/index.html
Sometimes it makes mistakes, and my program loses.
bruce
brucemo
Robert Hyatt wrote:
>
> brucemo (bru...@nwlink.com) wrote:
> : Null move does make tactical search faster. Take it out and check your WAC scores, Bob.
> I'd partially agree. However it also makes most positions take at least one
> ply deeper to solve than without null-move. I've come to consider null-move
> a "wash" tactically, but the extra 1-2 plies along lines where the current
> score is not "way out of bounds" seems to really help positional play a lot.
I made a new post for this topic, before I found this.
What the new post says, using more words, is that I tried WAC at 30 seconds a move and found
that "plies to solve" was the same in 90% of the cases.
bruce
brucemo
mclane wrote:
> Tactics are not that important if you play okish positional chess.
> See Rebel8. It is not really good in tactics. But top.
> Do you agree, or am I in your kill-file?!
> But all in all it is good that I quote Bob, so you can read him faster
> ....
You're not in my kill file. Tactics are obviously important. Playing
good positional chess will bring more good tactics your way, and steer
bad ones away from you, but you still have to find the good ones and
avoid the bad ones.
bruce
mclane
brucemo <bru...@nwlink.com> wrote:
>Jay Scott wrote:
>>
>> In article <58amds$m...@juniper.cis.uab.edu>, Robert Hyatt (hy...@crafty.cis.uab.edu) wrote:
>> >Many ask about null-move, and one of the most common things I hear is how
>> >"null-move makes a tactical search go deep." It turns out this is wrong.
>> >What really happens is that null-move makes a program play better *positionally*
>> >and *not* tactically. why? Because null-move really makes most programs take
>> >an additional ply or two (or sometimes way more) to find a tactical move that
>> >a non-null-move program will find much earlier. however, the overall search
>> >depth is much deeper, although the tactical lines are somewhat "damaged" by
>> >the null-move. The benefit, however, is the increased depth, which aids
>> >positional chess (if you do tip evaluation of course.. :) ).
>>
>> Hmm. So how do you explain that Fritz is so strong?
>Responding to Hyatt, whose post is probably stuck in Germany again.
Thanks!
Yes, we ate postings of Mr. Hyatt for dinner here.
>Null move does make tactical search faster. Take it out and check your WAC scores, Bob.
>bruce
mclane
hy...@crafty.cis.uab.edu (Robert Hyatt) wrote:
>mclane (mcl...@prima.ruhr.de) wrote:
>: j...@forum.swarthmore.edu (Jay Scott) wrote:
>:
>: >In article <58amds$m...@juniper.cis.uab.edu>, Robert Hyatt (hy...@crafty.cis.uab.edu) wrote:
>: >>Many ask about null-move, and one of the most common things I hear is how
>: >>"null-move makes a tactical search go deep." It turns out this is wrong.
>: >>What really happens is that null-move makes a program play better *positionally*
>: >>and *not* tactically. why? Because null-move really makes most programs take
>: >>an additional ply or two (or sometimes way more) to find a tactical move that
>: >>a non-null-move program will find much earlier. however, the overall search
>: >>depth is much deeper, although the tactical lines are somewhat "damaged" by
>: >>the null-move. The benefit, however, is the increased depth, which aids
>: >>positional chess (if you do tip evaluation of course.. :) ).
a) right
b) right
c) right
d) wrong
3 from 4 is really a good score! :-)
So you understand almost everything. Brilliant. We should mary!!
Rolf W. Tueschen
mcl...@prima.ruhr.de (mclane) wrote:
>hy...@crafty.cis.uab.edu (Robert Hyatt) wrote:
------------------------------------------------------------------------------------------------------
Nonono.
First what this has to do with chess?
Second I was there before you. Got it?
Dulcinea Tueschen
Komputer Korner
brucemo wrote:
>
> mclane wrote:
>
> > Tactics are not that important if you play okish positional chess.
> > See Rebel8. It is not really good in tactics. But top.
> > Do you agree, or am I in your kill-file?!
> > But all in all it is good that I quote Bob, so you can read him faster
> > ....
>
> good positional chess will bring more good tactics your way, and steer
> bad ones away from you, but you still have to find the good ones and
> avoid the bad ones.
>
> bruce
TACTICS and positional chess cannot be separated. Karpov tried that
against Kasparov but lost in the end.
--
Komputer Korner
The komputer that kouldn't keep a password safe from
prying eyes, kouldn't kompute the square root of 36^n,
kouldn't find the real motive in ChessBase and missed
the real learning feature of Nimzo.
Chris Whittington
Komputer Korner <kor...@netcom.ca> wrote:
>
> brucemo wrote:
> >
> > mclane wrote:
> >
> > > Tactics are not that important if you play okish positional chess.
> > > See Rebel8. It is not really good in tactics. But top.
> > > Do you agree, or am I in your kill-file?!
> > > But all in all it is good that I quote Bob, so you can read him faster
> > > ....
> >
> > You're not in my kill file. Tactics are obviously important. Playing
> > good positional chess will bring more good tactics your way, and steer
> > bad ones away from you, but you still have to find the good ones and
> > avoid the bad ones.
> >
> > bruce
>
> TACTICS and positional chess cannot be separated.
The force of Kravity holding them together, I presume ?
Aktually sinke they are konkeptual konkepts used to deskribe
a whole, the kwestion of separation or togetherness doesn't
seem aplikkable.
Chris Whittington
mclane
Chris Whittington <chr...@cpsoft.demon.co.uk> wrote:
>Komputer Korner <kor...@netcom.ca> wrote:
>>
>> brucemo wrote:
>> >
>> > You're not in my kill file. Tactics are obviously important. Playing
>> > good positional chess will bring more good tactics your way, and steer
>> > bad ones away from you, but you still have to find the good ones and
>> > avoid the bad ones.
>> >
>> > bruce
>>
>> TACTICS and positional chess cannot be separated.
>The force of Kravity holding them together, I presume ?
>Aktually sinke they are konkeptual konkepts used to deskribe
>a whole, the kwestion of separation or togetherness doesn't
>seem aplikkable.
>Chris Whittington
>> Karpov tried that
>> against Kasparov but lost in the end.
>> --
>> Komputer Korner
>>
Uff: Karpov, KK, Kasparov. Kris Krittington, Kravity ! Heaven.
Are you again drunken, Chris ?!
Or are you inspired by KK.