Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Verified Null-Move Pruning, ICGA 25(3)

Author: Omid David Tabibi

Date: 13:07:54 11/27/02

Go up one level in this thread


On November 27, 2002 at 15:55:04, Uri Blass wrote:

>On November 27, 2002 at 15:15:50, Robert Hyatt wrote:
>
>>On November 27, 2002 at 13:48:50, Frank Phillips wrote:
>>
>>>On November 26, 2002 at 20:02:06, Robert Hyatt wrote:
>>>
>>>>On November 26, 2002 at 16:21:00, Omid David Tabibi wrote:
>>>>
>>>>>On November 26, 2002 at 15:58:06, Gian-Carlo Pascutto wrote:
>>>>>
>>>>>>On November 26, 2002 at 15:55:56, Omid David Tabibi wrote:
>>>>>>
>>>>>>>So it is reasonable that on every program starting from a certain depth >adaptive null-move pruning will always construct a smaller search tree.
>>>>>>
>>>>>>Don't you mean the other way around?
>>>>>>
>>>>>
>>>>>Yes :-)
>>>>>
>>>>>Starting from a certain depth, verified null-move pruning will always construct
>>>>>a smaller search tree than the adaptive one.
>>>>>
>>>>>
>>>>>
>>>>>>--
>>>>>>GCP
>>>>
>>>>
>>>> I am doing some testing now.  First thing I noticed is that for WAC, the
>>>>time-squared
>>>>measurement went down very significantly for your algorithm.  And I have not
>>>>modified
>>>>anything such as turning null-move off when low material happens, since your
>>>>idea will
>>>>catch the zug problems.
>>>
>>>Have you tried Fine70?
>>>
>>>Frank
>>
>>Yes...  and I told Omid that this is a strange case as if I allow null-move in
>>pawn-only
>>endings, which turns it on for fine 70 of course, things get wrecked inside the
>>search
>>somehow.  A 45 ply search fails to see that Kb1 wins where normally an 18-19 ply
>>search is enough...
>
>No surprise
>
>The idea is productive for detecting cases when there is one zugzwang but not
>for cases when there is more than one zugzwang.
>
>It is a bad idea to use it for pawn endgame.
>If you want to use it to be theoretically sound(to see everything after enough
>plies) then you need always to do verification search and not only in cases that
>verify=true.
>
>It may be possible to do verification search to reduced depth when
>verify=false(for example by depth-=3; instead of depth--;)
>if you want to protect yourself against the danger of zugzwangs in the middle
>game and only if you detect a zugzwang to search again to bigger depth.
>

In the subtree of a fail-high reported node, standard null-ove pruning is
used, which is susceptible to zugzwangs. So the algorithm might not detect a
series of zugzwangs in a variation, in special positions. I thought that such
exceptional positions might exist, and that's why I wrote "detect most
zugzwangs" ("most" instead of "all"). Anyway, in the extreme endgames, I believe
it'd be better to turn off null-move pruning altogether, since the cost of the
re-searches might be too much.

However, using a reduction of 2 on fail-high reports, we can allow using
verified null-move pruning also in the subtree, without ending up with a
large tree. This method should be completely zugzwang-proof.


>Uri



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