Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Singular Extensions, Nullmove deepsearch

Author: Vincent Diepeveen

Date: 17:38:06 02/18/99

Go up one level in this thread


On February 18, 1999 at 17:13:12, Robert Hyatt wrote:

>On February 17, 1999 at 13:55:27, Vincent Diepeveen wrote:
>
>>On February 16, 1999 at 04:45:43, Frank Schneider wrote:
>>
>>>I experimented a little bit with nullmove deepsearch extensions and with
>>>singular extensions and now I have some questions:
>>>
>>>1. In all my tests the searchtree (#nodes to finish n iterations) increased
>>>   by a factor of 1.5 to 4. Although testresults were interesting I believe
>>>   this is too much. What are your experiences?
>>>
>>>2. Is it correct to assume that singular extensions work best if there are
>>>   only few other extension heuristics.
>>>
>>>3. How would you describe the difference between nullmove deepsearch extensions
>>>  (Donninger) and the nullmove threat detection by Deep Thought?
>>>
>>>4. Who uses
>>>   - singular extensions
>>no
>>>   - nullmove deepsearch extensions
>>no
>>>   - nullmove threat detection
>>
>>yes, if there is a mate threat i sometimes extend.
>>
>>>5. What is the best (easiest) way to implement singular extensions?
>>
>>Let's see 3 cases of SE implementation in a position where i
>>have a score for a move m, which is the best move and i
>>want to see whether it's best.
>>
>>  a) your score s is <= alfa
>>  b) your score s is > alfa and < beta
>>  c) your score s is >= beta
>>
>>Easiest case is b)
>>
>>Let's see that first, for searching with a singular difference S:
>>
>>s is a true score, so you can search ALL OTHER MOVES with a window
>>
>>[alfa,beta] = [s-S,s]
>>
>>If all scores are <= s-S then your move is singular in case b.
>>
>>Now case a. We get back a score s. We know that to be singular all moves n
>>which are unequal to m must have a lower score.
>>
>>There is however one big problem: score s is a bound. It is not
>>a true score, so in fact s could be theoretical s-i where i > 0.
>>
>>Practical with nullmove and a q-search that doesn't search all moves using
>>minimax, but prunes at >= beta, which as far as i know all programs do,
>>s is likely to be not the true score of m.
>>
>>So we must first get the TRUE score of m before deciding what its score is.
>>We then need to research m again. Eeasiest is to research with
>>[-infinite,s]
>>
>>If we get a fail high then we can assume that s is the true score.
>>If we  don't get a fail high then the new score s' is the true score of
>>move m.
>>
>>Now it will be obvious that researching with -infinite is rather silly.
>>
>>It is in fact doing a minimax search, as you remove your bound and
>>research this move with the initialy limits.
>>
>>So it is not very wise to do that at the same depth as you initially did.
>>It is wiser to research using a reduction factor for the remaining depth you
>>search with.
>>
>>Then it's obvious to see that the overhead of singular extensions is
>>depending upon your branching factor. The better your branching factor,
>>the bigger the overhead.
>>
>>This insight is easy to get:
>>
>>Suppose your branching factor is 5. then if you reduce a depth d with
>>2 ply, then that tree is more or less 1/5*5 = 1/25 part of the tree at
>>depth d.
>>
>>If your branching factor is say 2.5 to 3, then it is way more than 1/9
>>extra overhead, just for this move.
>>
>>Case c goes like case a, just that you need to search initially with
>>[s,infinite] instead of [-infinite,s].
>>
>>Let's take an easy example of a position where humans see directly the
>>problems and programs have more problems:
>>
>>r1b1k2r/p2n1ppp/1p2p3/3p2B1/P2P4/1Nn1P3/5PPP/R3KB1R w KQkq -
>>
>> r = b = k = - r   ...       1    ...
>> o - = n = o o o   ...       2    ...
>> - o - = o = - =   ...       3    ...
>> = - = o = - B -   ...       4    ...
>> O = - O - = - =   ...       5    ...
>> = N n - O - = -   ...       6    ...
>> - = - = - O O O   ...       7    ...
>> R - = - K B = R   ...       8    ...
>>position deriving from an analysis of Eric de Haan and Vincent Diepeveen
>>white to move
>>
>>Here i saw directly that white could win the piece at c3 after f3, and then
>>put pressure at c3 with bd3 kd2 and rhc1.
>>
>>That's simply an idea. so when i start searching i start with
>>
>>f3,Bb7,Bd3,Kd2 and i see that the piece gets captured after Rhc1. Now
>>that is not a computer analysis.
>>
>>For the computer to see the problem is depending upon evaluation.
>>Let's take the variation without nullmove and without hung pieces
>>evaluation and without recapture extension:
>>      normal depth
>>f3       1
>>h6       2
>>Bh4      3
>>g5       4
>>Bf2      5
>>Bb7      6
>>Bd3      7
>>Rc8      8
>>Kd2      9
>>e5       10 *
>>Rhc1     11
>>exd4     12 *
>>exd4     13
>>something 14
>>Rxc3      q-search
>>
>>Now a human sees that h6-g5 is not smart, and that g5 is forced
>>after h6, although for a computer this can be exchanged for Rc8 too.
>>
>>The singular extensions in THIS line are without a smart evaluation
>>(so material considerations) marked with a star, so: e5 and exd4.
>>
>>Questionable is what happens after
>>f3       1
>>h6       2
>>Bh4      3
>>g5       4
>>Bg3      5
>>Bb7      6
>>Bd3      7
>>Rc8      8
>>Kd2      9
>>h5       10
>>Rhc1     11
>>something 12
>>Rxc3      q-search
>>
>>Now we see that Bg3 is way better than Bf2, and therefore should get
>>objectively a singular extension. However we only see that it is better
>>AFTER we already have found it to be winning.
>>
>>Now we know how very little ply we need to find this for humans easy case
>>of getting a hung piece, we are gonna search for another way to delay
>>this combi. Even if the g5 bishop gets via h4 to g3, then still we can
>>delay things with f6 and e5 and capturing at d4.
>>
>>So the line now becomes:
>>f3       1
>>f6       2
>>Bh4      3
>>g5       4
>>Bg3      5
>>Bb7      6
>>Bd3      7
>>Rc8      8
>>Kd2      9
>>e5       10
>>Rhc1     11
>>exd4     12
>>exd4     13
>>something 14
>>Rxc3      q-search
>>
>>Now we clearly see that f6 is a clear case of a singular move here,
>>as it is the only move that delay the loss.
>>
>>I think this is a problem that is very important to realize,
>>but let's go on and take the nullmove program at the short line:
>>
>>f3       1
>>h6       2
>>Bh4      3
>>g5       4
>>Bg3      5
>>Bb7      6
>>Bd3      7
>>Rc8      8
>>Kd2      9
>>nullmove 10
>>Rhc1     11+R
>>something 12+R
>>Rxc3     q-search
>>
>>Now that's *without* any extensions yet.
>>
>>Now let's take cray blitz. It does detect for threats in nullmove.
>>And R=1 for the nullmove reduction factor. R=2 for the singular extension
>>reduction factor. Further it has recapture extensions.
>>So it sees already after Rhc1 the problems because
>>of the q-search nullmove. That is 12 ply, even without singular extensions.
>>
>>In this line however Bg3 and Bb7 should be singular extended!
>>So actually it should find it at 10 ply, if everything would be normal.
>
>I ran this test and found two things.  First, from ply=2 on, CB likes f3
>and would _never_ play anything else.  from plies 2-8 the score climbed
>slowly but white is a pawn down so it was less than zero.  At ply=9 it got a
>fail high, but no PV back so the score was -.117 at that point.  At ply=10 it
>failed high again with an evaluation of +1.5.

Is that a new version of Cray Blitz?

Some months ago when i messaged you this position and asked to have
a look at it with Cray Blitz to see how SE works, you messaged me back
that it needed 12 ply for it to see that it was winning with white with f3.

You used 1 processor for it.

>Crafty needs 14 plies, about 3 minutes on my quad, to fail high on this
>position.
>
>
>>
>>Bg3 is logically explainable, but Bb7 is not.
>>
>>Now let's get to the line for nullmoveprograms when playing f6:
>>f3       1
>>f6       2
>>Bh4      3
>>g5       4
>>Bg3      5
>>Bb7      6
>>Bd3      7
>>Rc8      8
>>Kd2      9
>>e5       10
>>Rhc1     11
>>exd4     12
>>exd4     12 (recapture extension)
>>something q-search (qsearch threat detected!
>>Rxc3      q-search
>>
>>I know from Bob that
>>Cray blitz needs 12 ply to find f3 without being negative.
>>However cray blitz should see that f6 here is a singular extension
>>and that Bb7 is a singular extension. Why is f6 a singular extension?
>>Easy: because all other moves lose. however it cannot see f6 as
>>it reduces depth and therefore needs a lot more ply to see that the other
>>variation with h6 loses. So f6 is very logically to explain.
>>However, Bb7 is tougher to explain. If you don't play Bb7 then the piece
>>gets directly lost in my opinion.
>>
>>So i can't explain this, except that this line is 11 ply to see, and
>>that the 'shorter line' is the line that eats up 12 ply.
>>
>>So for cray blitz the problem is not the f6-g5-e5 line,
>>but the h6-g5 line.
>>
>>This means that effectively Cray blitz has won zero plies in seeing this
>>problem by using singular extension. The nullmove-threat detection
>>in the q-search however has won a full ply for it, and the reduction factor
>>of 1 has reduced problems with another ply.
>>
>>Yet, if we look with a more objective point of view to this problem, then we
>>see that it did not extend all singular extensions, namely it missed
>>in the h6-g5 line that Bb7 is a singular extension.
>>
>>Now we compare this singular extension to DIEP that doesn't use
>>singular extensions, nor threat detection in q-search nor recapture extension
>>nor R=1. Diep uses R=3.
>>
>>So it's likely to assume that if Singular Extensions failed in cray blitz
>>to see this from human viewpoint forced combination, that diep needs
>>
>>a) 2 ply extra the 2 ply bigger reduction factor
>>b) another ply extra for the nullmove-threat quiescencesearch
>>
>>Now what diep has is a good evaluation. I think i can say very well in
>>this position, as diep evaluates the piece at c3 quickly to be hung.
>>so after
>>
>>f3       1
>>h6       2
>>Bh4      3
>>g5       4
>>Bg3      5
>>Bb7      6
>>Bd3      7
>>Rc8      8
>>Kd2      9
>>nullmove 10
>>Rhc1     11+R
>>
>>Now diep sees that the piece is clearly hung and it gives a huge penalty.
>>
>>R=3, so 11+3 = 14 ply needed.
>>
>>Output from the parallel version (running at 1 processor, so
>>note that the number of nodes is not exactly correct as the number of
>>nodes at the first ply are not added to it yet, one should add 1 node
>>for every ply it searched to the printed number of nodes):
>>
>>PII-450 80mb hashtables.
>>        00:00 0 1 -0.58 Nb3-d2
>>        00:00 8 1 -0.44 Bf1-d3
>>        00:00 8 1 -0.43 g2-g4
>>        00:00 8 1 -0.31 Bf1-b5
>>1      36 (      0,     35)    0.00
>>        00:00 48 2 -0.74 Bf1-b5 Bc8-b7
>>        00:00 48 2 -0.43 g2-g4
>>2      59 (      0,     35)    0.01
>>        00:00 114 3 -0.83 g2-g4 Bc8-b7
>>        00:00 328 3 -0.48 Bf1-b5 Bc8-b7 Ra1-c1 Nc3xb5 a4xb5
>>3      60 (      0,     35)    0.10
>>        00:00 1134 4 -0.97 Bf1-b5 Nc3xb5 a4xb5 a7-a5
>>        00:00 1551 4 -0.63 g2-g4 h7-h5 g4xh5
>>4      61 (      0,     35)    0.31
>>        00:00 2862 5 -1.10 g2-g4 h7-h5 f2-f3 h5xg4 f3xg4
>>        00:00 5666 5 -0.66 Bf1-b5 Bc8-b7 Ra1-c1 Ra8-c8 g2-g4
>>        00:00 6403 5 -0.56 Bg5-f4 Bc8-b7 Bf4-d6
>>5      62 (      0,     35)    0.68
>>        00:00 9914 6 -0.81 Bg5-f4 Bc8-b7 Bf1-b5 g7-g6
>>        00:01 15596 6 -0.80 Bf1-d3 Bc8-b7 g2-g4 Nc3-e4 Bg5-f4
>>        00:01 27029 6 -0.70 Ra1-c1 Nc3-e4 h2-h4 h7-h6 Bg5-f4 Bc8-b7
>>6      63 (      0,     35)    1.89
>>        00:02 43433 7 -0.51 Ra1-c1 Nc3-e4 h2-h4 f7-f6 Bg5-f4 e6-e5 Bf4-h2
>>7      64 (      0,     35)    3.40
>>        00:06 115191 8 -0.51 Ra1-c1 Nc3xa4 Bf1-b5 Na4-b2 Rc1-c2 Nb2-c4 Bb5xc4 d5
>>xc4 Rc2xc4
>>8      65 (      0,     35)    7.45
>>        00:11 237937 9 -0.50 Ra1-c1 Nc3-e4 h2-h4 Nd7-f8 Nb3-d2 Ne4xg5 Bf1-b5 Bc8
>>-d7 Bb5xd7 Nf8xd7 h4xg5
>>9      66 (      0,     35)   14.70
>>        00:25 531381 10 -0.31 Ra1-c1 Nc3-e4 Bg5-f4 g7-g5 Bf4-c7 Ke8-e7 f2-f3 Ne4
>>-f6 h2-h3
>>10      67 (      0,     35)   27.95
>>        00:38 817776 11 -0.48 Ra1-c1 Nc3-e4 Bg5-f4 g7-g5 Bf4-c7 Ke8-e7 Bf1-b5 Bc
>>8-b7 f2-f3 Ne4-d6 Ke1-e2
>>11      68 (      0,     35)   50.18
>>        01:46 2334305 12 -0.45 Ra1-c1 Nc3xa4 Bf1-b5 Na4-b2 Rc1-c2 Nb2-c4 Bb5-c6
>>Ra8-b8 Bg5-f4 e6-e5 Bf4xe5 Nc4xe5 d4xe5
>>12      69 (      0,     35)  126.17
>>        03:18 4640332 13 -0.47 Ra1-c1 Nc3-e4 Bg5-f4 g7-g5 Bf4-c7 Ke8-e7 f2-f3 Ne
>>4-f6 Bf1-d3 Bc8-b7 h2-h4 Rh8-g8 Ke1-f2 g5xh4 Rh1xh4
>>        07:08 9515739 13 -0.39 f2-f3 Bc8-b7 Ke1-d2 Ra8-c8 Bf1-b5 Nc3xb5 a4xb5 Rc
>>8-a8 Rh1-c1 a7-a5 Rc1-c7 h7-h6 Bg5-f4 g7-g5
>>13      70 (      0,     35)  436.78
>>        15:09 19918887 14 0.65 f2-f3 f7-f6 Bg5-h4 g7-g5 Bh4-f2 b6-b5 a4xb5 Ra8-b
>>8 h2-h4 Ke8-e7 h4xg5 f6xg5 Ra1xa7
>>14      71 (      0,     35)  929.00
>>        20:30 27165495 15 0.62 f2-f3 h7-h6 Bg5-h4 b6-b5 a4xb5 Nd7-b6 Ke1-d2 Nc3-
>>a4 Nb3-c5 Na4-b2 Kd2-c3 Nb2-c4 e3-e4
>>15      72 (      0,     35) 1272.46
>>
>>So Diep needs 19.9M nodes to see f3 to be winning. I think branching factor
>>clearly wins here from singular extensions and all kind of threat extensions.
>>
>>Only fiddling with the nullmove reduction factor (from 3 to 2)
>>would find this problem for me 1 ply earlier, where Singular extension
>>takes care i never see this problem that quick, as i never will search
>>deep enough.
>>
>>Now singular extensions show a lot of problems
>>  a) you need a singular margin S, which means that you give a true
>>     or false definition to something being singular. For example:
>>     if i pick 0.50 pawns for S, then we will miss something that
>>     is 0.49 pawns better, even if it is a fail high singular extension.
>>  b) SE is not giving you real singular moves. Only easy cases
>>     of singular moves are recognized as you search the tree with a
>>     reduced depth. So singular moves based on a deep search cannot be
>>     used, although that are the most interesting ones, as is clear in
>>     this problem.
>>  c) the overhead of singular extensions becomes very big when your programs
>>     branching factor gets better.
>>     I found in DIEP (after say 9 ply the branching factor becomes
>>     between 2.0 to 3.0 normally spoken) singular extensions increase
>>     my branching factor
>>     considerably. So i could hardly search 10 plies after many
>>     hours, using a CORRECT implementation of singular extensions with
>>     singulair reduction factor=2, and no way to speed that up, where
>>     normally DIEP searches after 3 minutes already 11 or 12 ply.
>>  d) Near the leafs singular extensions cannot be used in a search
>>     as we work with a reduction factor, which we need otherwise we
>>     search close to minimax. I found this in DIEP a very big problem,
>>     as searching WITH singular extensions already eats up a
>>     big bunch of plies, and then another few ply are cut away. So singular
>>     extensions far in the tree form a big problem to see.
>>  c) singular extensions work to find forced combinations, but a forced
>>     combination in the eyes of a human is not necessarily having only 1
>>     forced move. A singulair position in human eyes can have 2 or more
>>     moves too.
>>  d) Singular extensions work especially well AFTER you already see the truth
>>     of something. This has to do with d). You can only detect threats
>>     based on a reduced depth. So you can only see something
>>     after it is already clear with the normal search that it is way better,
>>     as you researched it to be singular with a reduced depth that is way
>>     smaller than the big search. This is nice to get a big score, but
>>     i personally think this wasting nodes.
>>
>>Conclusion most combinations i know from games have very little easy
>>to recognize singular moves, way less than the 3 plies DIEP already gives
>>up after a few minutes. As hardware gets faster the number of extra
>>plies needed by just the Singular extension is getting larger and larger.
>>
>>I see singular extensions as a limited and very restricted
>>form of threat extensions that need a huge overhead to be detected as you
>>need a lot of extra search.
>>
>>On the other hand we see that a simplistic eval term which was already in
>>gnuchess saves a full ply of search.
>>
>>>Thanks in advance,
>>>Frank



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