Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: When to do a null move search - an experiment

Author: Robert Hyatt

Date: 08:07:15 04/30/04

Go up one level in this thread


On April 30, 2004 at 02:00:57, Ed Schröder wrote:

>On April 29, 2004 at 23:25:59, Robert Hyatt wrote:
>
>>On April 29, 2004 at 16:17:34, Ed Schröder wrote:
>>
>>>On April 29, 2004 at 14:44:47, Robert Hyatt wrote:
>>>
>>>>On April 29, 2004 at 09:28:53, Ed Schröder wrote:
>>>>
>>>>>On April 29, 2004 at 07:37:23, Vincent Diepeveen wrote:
>>>>>
>>>>>[ snips ]
>>>>>
>>>>>>>This is all very poor Vince, I assume you don't play much with nowadays top
>>>>>>>programs. From 1982 to 2001 Rebel won its games by positional understanding and
>>>>>>>not by search and Rebel lost its games because it was outsearched. Today Rebel
>>>>>>>isn't outsearched at all, it now loses its games because the current top
>>>>>>>programs have a better positional understanding than Rebel.
>>>>>>>
>>>>>>>You should have a good look at the current tops, the positional progress has
>>>>>>>been great the last years. To me it all seems to indicate (provided your search
>>>>>>>is okay) the only way to make progress is to improve on chess knowledge. But
>>>>>>>what's new, I already came to that conclusion in 1986 after some intensive talks
>>>>>>>with Hans Berliner.
>>>>>
>>>>>>What i mean is Ed, is that you would not have accomplished the great results
>>>>>>with Rebel which you managed, had you just searched with a fullwidth search +
>>>>>>bunch of checks in qsearch.
>>>>>
>>>>>No of course not, brute force is silly, Rebel since day 1 has been a selective
>>>>>program. But I am getting your point, in the days before the nullmove was
>>>>>discovered Genius and Rebel had the best (static) selective search, a dominant
>>>>>factor in their successes, is that what you meant to say? If so, it is true.
>>>>>
>>>>>If only Frans had kept his mouth shut to Chrilly (Chrilly leaking nullmove in
>>>>>the ICCA journal) it is very likely Fritz would been the next Richard Lang still
>>>>>dominating all the rating lists and WCC's for the last decade. But Frans didn't
>>>>>and then all bets were off.
>>>
>>>
>>>>Chrilly wasn't the one that started the null-move search stuff.  Don Beal was
>>>>the first I recall reading although Murray Campbell also wrote a paper on the
>>>>idea.  I will try to flip through the surviving Cray Blitz source listing to see
>>>>exactly when null-move was added to it.  All I remember is Burton Wendroff
>>>>(Lachex) sending me a copy of Murray's paper and saying "try this". (this
>>>>happened while I was preparing for an ACM or WCCC event).  Of course I am
>>>>talking about R=1, non-recursive, as it was defined "in the good old days".. :)
>>>
>>>Actually Don Beal told Frans about nullmove in Cologne 1986, Don at that time
>>>only used nullmove in QS. Don did not use nullmove as we know it today, that
>>>came after Chrilly's article.
>>>
>>>Ed
>
>
>>Yes, but Campbell defined "the null-move observation" exactly as it is used
>>today (no move played, reduce depth, if it fails high, then let the search fail
>>high with no more searching.)  He even suggested that R=2 needs serious testing.
>
>Did Campbell mention recursive nullmove too? Because that's where the real
>strength of the algorithm comes from.

They discussed it and dismissed it as too risky at the search depths of that
time...  Remember that non-supercomputer programs were hitting 5-6- plies
generally...


>
>
>>Chrilly's main advancement was using the null-move observation to detect threats
>>and extend the search when the condition was met.  I don't know of anyone that
>>really does this today.  I did it back around version 9, but stopped due to the
>>high cost and low return...
>
>As far as I can remember the article was about detecting mate-threats only, I
>could be wrong. I use it, when the first nullmove returns a mate-value I extend
>one ply.
>
>My best,
>

Chrilly's idea was this:  when a normal move fails high, but a null-move fails
low (on a lowered window) then the fail-high move is likely holding off some
sort of threat that the null-move search sees quickly.  Extend.  I think this
was explained in the section "The program that knew too much" but remember that
this is from memory of a paper written/published 10+ years ago...

I used this idea in Crafty for a year or so, around version 9 or so it was
removed due to excessive overhead...

I think many do the mate score extension.  Bruce Moreland was the first I ever
recall mentioning that idea.  I got it from him several years ago.




>Ed



This page took 0.01 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.