Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Singular Extensions, Nullmove deepsearch

Author: Vincent Diepeveen

Date: 10:55:27 02/17/99

Go up one level in this thread


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.

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