Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Null-Move: Difference between R = 2 and R = 3 in action

Author: Vincent Diepeveen

Date: 07:10:52 07/16/02

Go up one level in this thread


On July 15, 2002 at 08:37:34, Omid David wrote:

The below story is like saying doing alfabetapruning is not a good idea,
because minimax gives the same value, and that
Knuth's writing, proving alfabeta to give the same value is good
to show it is giving the same value!

BTW, did you make a chessprogram of your own and is it using nullmove already?

>I don't think using double null-move is a good idea in practice, since in
>midgame the chance of zugzwang is negligible and thus it's superfluous (I doubt
>if even DIEP uses it). However the contribution of double null-move is that it
>gives legitimacy to the null-move pruning idea, proving that it _is_ a correct
>search method (anyway, no one doubts null-move nowadays).
>
>Omid.
>
>
>On July 14, 2002 at 05:28:29, Vincent Diepeveen wrote:
>
>>On July 14, 2002 at 02:44:17, Christophe Theron wrote:
>>
>>In my draughtsprogram i tried a zugzwang detection with
>>a normal search depth-2. The overhead from this is
>>*huge* though.
>>
>>*no one* is using this overhead in his chessprogram,
>>for obvious reasons.
>>
>>double nullmove is allowing you to have both a zugzwang
>>detection as well as use nullmove in an efficient combination.
>>
>>It's a very elegant solution.
>>
>>most important however, is that double nullmove was invented
>>to proof that searching with nullmove is a correct way to search.
>>
>>Nowadays we don't have this discussion a lot anymore, though
>>Schaeffer at world champs was still defending deep blue seeing more
>>than other chessprograms, even though they searched 11 to 12 ply
>>at nominal search depth, but i remember huge discussions here
>>from dudes mentionning that fullwidth 12 ply was seeing more
>>*always* than 12 ply with nullmove.
>>
>>Well, i can imagine someone coming from the checkers area, to
>>defend the principle that 12 ply fullwidth is better. In draughts/checkers
>>not detecting zugzwang is suicide, because the whole game goes about
>>it. This whereas the last time he had a chessprogram was in the 80s
>>where a 6 ply search always beated a 4 ply search and a 4 ply search always
>>beated a 2 ply search. And the 8 ply search from deep thought/chiptest
>>always beated the 6 ply searches from others.
>>
>>double nullmove therefore was in first place something to show that
>>using double nullmove IS a correct way to search in chess. Only *sometimes*
>>you need a lot of plies more. To detect a zugzwang you need 2R-2 ply
>>more than fullwidth.
>>
>>For more than 1 zugzwang and searching SMP i need to mention you usually
>>are lucky that 1 or more processors have seen nonsense lines and by
>>means of transposition solve it then. If not, then you simply need
>>a bunch of plies more. for each additional zugzwang.
>>
>>That's a price to pay, but a small price.
>>
>>
>>
>>>On July 13, 2002 at 21:26:30, Omid David wrote:
>>>
>>>>On July 13, 2002 at 11:52:36, Vincent Diepeveen wrote:
>>>>
>>>>>On July 13, 2002 at 11:09:19, Omid David wrote:
>>>>>
>>>>>>On July 13, 2002 at 10:33:19, Vincent Diepeveen wrote:
>>>>>>
>>>>>>>On July 13, 2002 at 04:47:16, Omid David wrote:
>>>>>>>
>>>>>>>>On July 13, 2002 at 02:39:38, Dann Corbit wrote:
>>>>>>>>
>>>>>>>>>On July 13, 2002 at 02:22:00, Omid David wrote:
>>>>>>>>>
>>>>>>>>>>On July 13, 2002 at 02:07:17, Vincent Diepeveen wrote:
>>>>>>>>>>
>>>>>>>>>>>I still do not understand which positions you talk about which R=2
>>>>>>>>>>>is finding and R=3 isn't.
>>>>>>>>>>
>>>>>>>>>>I read your other post, that's also my point: Although at fixed depth, R=2 is
>>>>>>>>>>much better than R=3 (see also "adaptive null-move pruning" Heinz 1999), in
>>>>>>>>>>practice R=3 performs about the same as R=2 since on many occasions it finds the
>>>>>>>>>>correct move one ply later with lower search cost.
>>>>>>>>>
>>>>>>>>>By the way, if you have not found Vincent's post on double null move you should
>>>>>>>>>look it up.  It is a clear win for sure.
>>>>>>>>
>>>>>>>>Yes it's a nice idea. But the main null-move pruning deficiency is its tactical
>>>>>>>>weakness due to horizon effect. Zugzwangs are not a major problem, and as
>>>>>>>>Vincent points out, he invented the double null-move idea just to show that
>>>>>>>>null-move pruning is OK. Now nobody doubts effectiveness of null-move pruning at
>>>>>>>>all, the only discussion nowadays is the depth reduction value.
>>>>>>>
>>>>>>>I'm missing any position where you have a problem though. Seems to me
>>>>>>>your thing is incredible weak, and or doing other dubious things which
>>>>>>>gets looked up in hashtable, after which it weakens your program.
>>>>>>>
>>>>>>>In DIEP i don't have all these problems.
>>>>>>>  - no dubious forward pruning
>>>>>>>  - no futility
>>>>>>>  - no razoring or any of these techniques.
>>>>>>>  - checks in qsearch
>>>>>>>
>>>>>>>Just PVS with nullmove R=3 and a bunch of extensions. That's it.
>>>>>>>
>>>>>>>Means that after a nullmove i don't get transpositions to positions
>>>>>>>where you have stored a score which is based upon a dubious score.
>>>>>>>
>>>>>>>Best regards,
>>>>>>>Vincent
>>>>>>
>>>>>>Why do you think there is a problem?! All the results I got are natural. I'm
>>>>>>sure even in DIEP, R=2 works better under "fixed theoretical" conditions.
>>>>>
>>>>>No it works worse, because i search at least a ply less deeply. If i search
>>>>>a ply deeper that doesn't only mean i get a ply more. Because the depth
>>>>>is already pretty decent it also means all extensions might get triggered
>>>>>a ply extra (like singular extensions).
>>>>>
>>>>>>However in practice you don't search to fixed depth and thus R=3 might be better
>>>>>>in practice.
>>>>>>
>>>>>>My only point is that "R=3 might be better than most people consider it." (Take
>>>>>>DIEP as a successful use of R=3)
>>>>>>
>>>>>>P.S.
>>>>>>Have you published anything regarding double null-move?
>>>>>
>>>>>I simply posted in CCC and RGCC. the thing is real easy.
>>>>>allow 2 nullmoves in a row always, but not 3.
>>>>>Exception is if both sides only have pawns (of course you
>>>>>can solve a few testset positions sooner by saying that
>>>>>if either side has only pawns you don't allow nullmove
>>>>>FOR BOTH SIDES, but that's in reality not so smart to do).
>>>>>
>>>>>Apart from that the normal conditions that i don't nullmove
>>>>>when in check.
>>>>>
>>>>>This in fact results in nullmove not missing zugzwangs anymore.
>>>>>Of course for more than 1 zugzwang the extra depth needed is
>>>>>pretty big.
>>>>>
>>>>>Best regards,
>>>>>Vincent
>>>>
>>>>I'd rather see such articles as "double null-move pruning" in ICCA than the
>>>>usual pure-theoretical-non-practical articles!
>>>
>>>
>>>
>>>Double null-move sounds elegant, but actually it's a zugzwang detection search
>>>at depth D-2R-2 (D=remaining depth, and R is the classic null move reduction
>>>constant).
>>>
>>>It is less flexible than a zugzwang detection search because:
>>>1) the depth is fixed to D-2R-2, so you can't adjust it to a better value (and
>>>D-2R-2 is not an optimal value).
>>>2) it's less easy to declare the conditions determining when you want to do (or
>>>avoid to do) the zugzwang detection (but this can be discussed).
>>>
>>>
>>>
>>>    Christophe



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.