Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Singular Extensions, Nullmove deepsearch

Author: Robert Hyatt

Date: 14:13:12 02/18/99

Go up one level in this thread


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.

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.19 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.