Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: new thoughts on verified null move

Author: Uri Blass

Date: 09:38:48 11/24/02

Go up one level in this thread


On November 24, 2002 at 12:20:02, Omid David Tabibi wrote:

>On November 24, 2002 at 11:05:24, Robert Hyatt wrote:
>
>>On November 24, 2002 at 07:01:46, Omid David Tabibi wrote:
>>
>>>On November 23, 2002 at 23:33:39, Tony Werten wrote:
>>>
>>>>On November 23, 2002 at 23:14:52, Omid David Tabibi wrote:
>>>>
>>>>>On November 23, 2002 at 22:25:02, Tony Werten wrote:
>>>>>
>>>>>>On November 23, 2002 at 22:14:27, Omid David Tabibi wrote:
>>>>>>
>>>>>>>On November 23, 2002 at 21:50:01, Tony Werten wrote:
>>>>>>>
>>>>>>>>On November 23, 2002 at 21:24:08, Omid David Tabibi wrote:
>>>>>>>>
>>>>>>>>>On November 23, 2002 at 21:09:36, Tony Werten wrote:
>>>>>>>>>
>>>>>>>>>>On November 23, 2002 at 20:52:01, Omid David Tabibi wrote:
>>>>>>>>>>
>>>>>>>>>>>On November 23, 2002 at 20:00:15, Tony Werten wrote:
>>>>>>>>>>>
>>>>>>>>>>>>On November 23, 2002 at 11:11:16, Christophe Theron wrote:
>>>>>>>>>>>>
>>>>>>>>>>>>>On November 23, 2002 at 09:22:37, jefkaan wrote:
>>>>>>>>>>>>>
>>>>>>>>>>>>>>oops, wasn't finished yet..
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>are done by using the results of the positional eval
>>>>>>>>>>>>>>>to prune the q-search,
>>>>>>>>>>>>>>and there using only material eval
>>>>>>>>>>>>>> (haven't tried it out yet, and wouldn't
>>>>>>>>>>>>>>know how to do it, but it's only an idea,
>>>>>>>>>>>>>>you know.. to explore options of
>>>>>>>>>>>>>>more effective branch factor reducements
>>>>>>>>>>>>>>and efficient programming (besides
>>>>>>>>>>>>>>lousy solutions as inline assembler
>>>>>>>>>>>>>>and bitboards..
>>>>>>>>>>>>>>:)
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>Yes Chess Tiger does much more pruning than known (published) techniques.
>>>>>>>>>>>>>
>>>>>>>>>>>>>I think other top programs do it also.
>>>>>>>>>>>>>
>>>>>>>>>>>>>I still fail to see why the efficiency of an algorithm depends on what your
>>>>>>>>>>>>>QSearch does.
>>>>>>>>>>>>>
>>>>>>>>>>>>>If your pruning algorithm is good, it will increase the strength of the program
>>>>>>>>>>>>>regardless on how good your QSearch is.
>>>>>>>>>>>>>
>>>>>>>>>>>>>If your QSearch is smart, then it will increase the strength even more.
>>>>>>>>>>>>>
>>>>>>>>>>>>>I don't like the idea that some algorithms that have almost nothing to do with
>>>>>>>>>>>>>each other would have such an influence on each other. It is indeed possible and
>>>>>>>>>>>>>it probably happens all the time, but it's hard to work with such hypothesis in
>>>>>>>>>>>>>mind.
>>>>>>>>>>>>>
>>>>>>>>>>>>>I think it's better to first assume that the kind of QSearch you do will not
>>>>>>>>>>>>>interfere with the quality of the pruning algorithm used before the QSearch.
>>>>>>>>>>>>>
>>>>>>>>>>>>>If your QSearch sucks, it's not because you are doing a lot of pruning in the
>>>>>>>>>>>>>"full width" part of the search. It's because it sucks.
>>>>>>>>>>>>
>>>>>>>>>>>>The paper does prove that the more your (q)search sucks, the better your pruning
>>>>>>>>>>>>algoritm seems. But that's not really news.
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>Does it prove that?! No, it's just my impression based on the data gathered so
>>>>>>>>>>>far. Maybe a reduction of 2 (instead of 1) in case of fail-high report, will
>>>>>>>>>>>work better in programs with heavy extensions and quiescence.
>>>>>>>>>>
>>>>>>>>>>A reduction of 20% seems to be working best in XiniX ( heavy qsearch).
>>>>>>>>>
>>>>>>>>>What do you mean by 20%? (you used a reduction of 1 or 2 in case of fail-high
>>>>>>>>>report?)
>>>>>>>>
>>>>>>>>In case of a fail high I reduce the depth with 20%. ( doesn't work in your silly
>>>>>>>>program :)
>>>>>>>>
>>>>>>>
>>>>>>>Anyway, no matter what the reduction is, you are using verified null-move
>>>>>>>pruning, which is good :-) In my paper I just gave a new null-move pruning
>>>>>>>framework; feel free to play with the values that best fit your program.
>>>>>>
>>>>>>It's a no brainer to implement. If it's not bad then it's worth investigating.
>>>>>>
>>>>>>>
>>>>>>>Even better values do exist. I've been working on them for some time and will
>>>>>>>publish them in near future.
>>>>>>
>>>>>>If I might give an advice. For first reviews, send them it to some active
>>>>>>chessprogrammers, and not to academic has beens. It will save you a lot of
>>>>>>typework. ( you have been quite active on this forum lately )
>>>>>>
>>>>>
>>>>>I will. However, after posting a new method, several days of "heavy presence"
>>>>>will always be needed to clear things up and answer the questions...
>>>>
>>>>Yes, that's good.
>>>>
>>>>I just think that sending your algoritm to Robert (I think we were using this in
>>>>74 ), Gian Carlo ( Can't work, just implemented it in 3 seconds ) and me (
>>>>didn't crash my program, must be a good idea ) would have given you some "real"
>>>>input.
>>>>
>>>
>>>Yes, I agree. At least I would have changed my too optimistic comment "it can be
>>>implemented by merely adding a few lines of code"! It is a few lines of
>>>pseudo-code, but practically needs some more tuning to find the best reduction
>>>values...
>>>
>>>
>>
>>It wasn't really "too optimistic".  But it is probably easier for me than
>>most, as I am already using internal iterative deepening, which means I can
>>call search recursively for the same position/ply, without wrecking things.
>>
>>That simplifies the code in that I don't do the little block of verification
>>code plus a goto that you used, I simply recursively call search when the
>>null-move search fails high and the "ok-to-verify" flag is set.  However, to
>>be efficient, I wanted to modify my "do_null" flag I pass to each successive
>>search() call, so that it would include "do_null & verify" to avoid adding a
>>new search parameter.  That was a bit messier than I originally thought and
>>that is the only thing that caused my initial attempt to produce errors, in that
>>I simply blew the two flags out at times and did extra verification searches
>>when I shouldn't have due to the bug.
>>
>>BTW, when I get this working, I have a huge cluster of quad xeons.  I can
>>certainly re-run all your test positions with Crafty, and let 'em run 32 at
>>a time to depth 12, 13, and 14 to see what happens...  If you want to send me
>>your positions, I should probably re-run the 9, 10 and 11 tests as well to get
>>a baseline comparison between crafty and your program also...  but I have plenty
>>of machine time to run deeper tests...
>>
>
>Testing this idea at depths of +12 will shed more light on performance of this
>algorithm in deeper searches. Because of its simple data structure Genesis is a
>slow searcher (about 100k NPS on my 733 MHz) and so I couldn't afford a search
>deeper than 11 plies. But it would be great if you run deeper tests with Crafty.

I do not think that the fact that genesis is a slow searcher prevents search
of more than 11 plies.

Fritz can get usually at least 18 plies in some hours.
If the problem is time then it is still possible that other people test genesis
with search of 12,13 and 14 plies(I do not plan to do it but I guess that you
may find other volunteers to test)

Uri



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