Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: new thoughts on verified null move

Author: Omid David Tabibi

Date: 13:55:31 11/23/02

Go up one level in this thread


On November 23, 2002 at 14:35:12, Martin Giepmans wrote:

>On November 23, 2002 at 13:42:06, Omid David Tabibi wrote:
>
>>On November 23, 2002 at 13:29:38, Martin Giepmans wrote:
>>
>>>On November 23, 2002 at 12:52:21, Omid David Tabibi wrote:
>>>
>>>>On November 23, 2002 at 11:37:25, Martin Giepmans wrote:
>>>>
>>>>>On November 23, 2002 at 08:48:36, Omid David Tabibi wrote:
>>>>>
>>>>>>On November 23, 2002 at 08:45:00, Uri Blass wrote:
>>>>>>
>>>>>>>On November 23, 2002 at 08:11:37, scott farrell wrote:
>>>>>>>
>>>>>>>>Just after other people's thoughts.
>>>>>>>>
>>>>>>>>I think Omid's work overlooked the adapative null move searching many of us do,
>>>>>>>>ie. transitioning from r=3 to r=2.
>>>>>>>>
>>>>>>>>I think adaptive null move tries to GUESS where to use r=2 to reduce the errors
>>>>>>>>that R=3 makes. I guess it depends on how often this GUESS is correct, the cost
>>>>>>>>of the verification search, and how long it takes the adaptive searching to
>>>>>>>>catch the error at the next ply.
>>>>>>>>
>>>>>>>>Has anyone looked at setting the verification search to reduced depth of 2
>>>>>>>>(rather than 1)? obviously to reduce the cost of the verification search.
>>>>>>>
>>>>>>>Omid checked it but you also reduce the gain.
>>>>>>>
>>>>>>>I think that I will look for good rules when to do the verification search so
>>>>>>>the cost will be significantly smaller but the gain is going to be the same in
>>>>>>>at least 99% of the cases.
>>>>>>>
>>>>>>
>>>>>>I'm currently working on other variations. The initial results are promising.
>>>>>>
>>>>>>>Uri
>>>>>
>>>>>I have done some tests with your method at greater depths.
>>>>>At depth 12 vrfd R=3 still had an overhead (in terms of treesize) of about
>>>>>25% compared to pure R=3.
>>>>
>>>>Of course verified R=3 will *always* construct a larger tree than standard R=3.
>>>>However, starting from a certain depth, it will always construct a smaller tree
>>>>than standard R=2.
>>>>
>>>>Take note, that while verified R=3 constructs a slightly larger tree than
>>>>standard R=3, it has a superior tactical strength to even R=2 !
>>>>
>>>>
>>>>>
>>>>>(my engine uses a simple Q-search that shouldn't give problems here)
>>>>>
>>>>>So the question is if your expectation that the treesize of R=3 and vrfd R=3
>>>>>converge at greater depths (> 11) really holds.
>>>>>
>>>>>Needs more testing, I think.
>>>>>
>>>>>Another point:
>>>>>I would expect that vrfd R=3 becomes less safe at greater depths.
>>>>>The subtrees in which you don't verify nullmove (after the verification) become
>>>>>deeper and I see no reason - on logical grounds - why this shouldn't give safety
>>>>>problems.
>>>>>Even if R=3 and vrfd R=3 converge in terms of treesize, the safety (or rather
>>>>>the lack of it) might also converge ...
>>>>>
>>>>
>>>>None will converge.
>>>
>>>That is what you hope. And hope is a good thing, for sure :)
>>>
>>
>>That's what I hope? No, actually I would be happier if the tree size of vrfd R=3
>>and std R=3 would converge! But that is impossible, since verified R=3 has the
>>verification overhead.
>>
>What I mean is that you apparently hope that at greater depths
>the tree for vrfd R=3 will only be slightly larger than the tree for pure R=3.
>>
>>>But how do you know? In your article there are no results for depths>11.
>>>
>>
>>Look at Figure 4. The deeper you go, the larger becomes the difference between
>>the tree size of vrfd R=3 and std R=2.
>>
>>
>>>>However, the deeper you go, the smaller will be the difference in tree size,  and the greater the difference in tactical strength.
>>>>
>>>Again, how do you know?
>>>
>>
>>The "backbone" of verified null move pruning is R=3. So it is natural that the
>>deeper you go, the size of the tree will be closer to standard R=3 than to
>>standard R=2 (again see Figure 4).
>>
>
>Well, it is also "natural" that the deeper you go the risk of verified
>null move will be closer to standard R=3 than to standard R=2.
>No?
>That's my point. If at depth 14 (for instance) the overhead is still something
>like 25% while the gain in terms of safety is reduced to nearly nothing
>(which I expect) than ... what did you gain?
>You can only find out if you test at larger depths.
>In a few years we will reach depth 14 even in blitz games. So it is important.
>

I cannot speak for a depth of 14, but for the depths I have tested (8, 9, 10,
and 11), vrfd R=3 was better than std R=2 in a linear form. That is, for example
in depth 10 vrfd R=3 was better than std R=2, by about the same factor that it
was better in depth 8.

Intuitively, we can look at it as following: in verified R=3 we have a reduction
of 3 (R=3), but then verify it by a reduction of 1; while in standard R=2 we
don't check a reduction of 1, and so the results will be more susceptible to
horizon effect. Of course I can not prove that this will always hold true, but
that is my best guess based on my current data.


>Martin
>
>
>>
>>>Martin
>>>>
>>>>>In any case, thanks for sharing.
>>>>>
>>>>>Martin



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