Computer Chess Club Archives


Search

Terms

Messages

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

Author: Vincent Diepeveen

Date: 15:16:44 04/28/04

Go up one level in this thread


On April 28, 2004 at 13:45:05, Ed Schr÷der wrote:

>On April 28, 2004 at 01:29:30, Gerd Isenberg wrote:
>
>>On April 28, 2004 at 01:11:23, Gerd Isenberg wrote:
>>
>>>On April 27, 2004 at 21:54:49, Uri Blass wrote:
>>>
>>>>On April 27, 2004 at 21:00:22, Vincent Diepeveen wrote:
>>>>
>>>>>On April 27, 2004 at 11:43:36, JosÚ Carlos wrote:
>>>>>
>>>>>>On April 27, 2004 at 08:37:34, Tony Werten wrote:
>>>>>>
>>>>>>>On April 27, 2004 at 03:33:26, Bas Hamstra wrote:
>>>>>>>
>>>>>>>>About double nullmove: I tested this in some pawnendgames to see if it could
>>>>>>>>handle zuzwang problems, but I don't see it perform any better than normal
>>>>>>>>nullmove. Can Vincent or you post a position where double null outperforms
>>>>>>>>normal null? I agree the idea is elegant, but I just don't see it work.
>>>>>>>
>>>>>>>I switch it off in pawns only endgames. Couldn't figure out why it wasn't doing
>>>>>>>as well as it sounded.
>>>>>>
>>>>>>  I can't think about it now, but I recall this thread where an interesting
>>>>>>discussion about double null move came up:
>>>>>>
>>>>>>http://chessprogramming.org/cccsearch/ccc.php?art_id=241476
>>>>>>
>>>>>>  JosÚ C.
>>>>>
>>>>>Christophe wrote that down just to let you guys believe you should search
>>>>>fullwidth.
>>>>>
>>>>>Practical chances of it happening is small, not zero but very close to it.
>>>>>Additionally you can add a single 'if then else' condition in transposition
>>>>>table cutoff to avoid the theoretical scenario that christophe describes.
>>>>>
>>>>>Look the alternative to double nullmove is doing something dead slow like what
>>>>>Gerd is doing, or what i used to do in my draughtsprogram; a verification
>>>>>search, which is just a fullwidth search of n-R ply. So not the later posted in
>>>>>ICGA verification search. Verification search already was excisting in other
>>>>>publications than in the ICGA. So Omid just stole the name kind of for something
>>>>>working crappy :)
>>>>
>>>>No
>>>>
>>>>Omid did not steal the idea.
>>>>
>>>>You simply did not understand Omid's ideas.
>>>>Omid's idea is not mainly to detect zugzwangs but to detect tactics earlier.
>>>>
>>>>Null move pruning means that there are tactics that you need more plies to see
>>>>because of the horizon effect when you cannot detect the threat.
>>>>
>>>>With verified null move pruning you can see it 1 or 2 plies earlier.
>>>>
>>>>Doing checks in the qsearch cannot solve the problem because there is tactics
>>>>that is not based on checks.
>>>>
>>>>>
>>>>>Basically all those approaches eat shitload of nodes to say it *very* polite.
>>>>
>>>>Basically I see no reason that verification search to detect zugzwangs needs to
>>>>eat many nodes(Omid's idea is not verification search) and common sense tells me
>>>>that if the depth is reduced enough it does not eat many nodes.
>>>>
>>>>Uri
>>
>>oups, sorry for the empty reply...
>>
>>I tried double nullmove suggested by Vincent too, without any precondition like
>>eval - margin >= beta. Vincent is probably right - it seems to work great, and
>>solves a lot of test positions a few percent faster. But with some positions,
>>specially with fail-high or -low behaviour the solution needs more than the
>>double time than single nullmove in a row with verification search in my
>>program. Two examples from BT-test:
>
>What is double nullmove? I only know recursive nullmove allowing multiple
>nullmoves. I also read about "allowing 2 nullmoves in a row". What are the
>differences?
>
>I use recursive nullmove, not allowing the next ply after the nullmove to
>nullmove. So:

>  e2-e4
>  e7-e5
>  **-**     // nullmove
>  d7-d5     // do no allow nullmove
>
>When I remove that check I get a few percent speedup, results look okay.
>Ed

double nullmove:

allowed: a3 null null d5 ...
allowed: a3 null null d5 null null d4 ....
allowed: a3 null d4 null null d5 ...
etc.

NOT allowed : a3 null null null d4
NOT allowed : a3 null null d5 null null null ...

3 consecutive nullmoves in a row are not allowed, recursion is allowed of
course. That's all.

Of course i have additional conditions when to not allow nullmove;
  - when in check
  - when it is a pawn endgame (BOTH SIDES IN PAWN ENDGAME)

The huge advantage of double nullmove nowadays is that if you are in an endgame
you can still nullmove everywhere. So exchanging somewhere to some crazy
position with just 1 piece left you still can nullmove cutting the tree quickly.

There is no need for special zugzwang code in short.

Of course it will need, depending upon the reduction factors you use, a huge
extra depth to find more than 1 zugzwang.

So in diep i also nullmove when 1 side has 1 piece and the other doesn't have
anything.

The reason for that is that for example in a rook endgame in 99.99% of all cases
it's nonsense to give up a piece. I prefer to search deeper in all those
nonsense cases.

That this eats more ply to solve some testset trick like a Bxe4 somewhere, bad
luck there.





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