Author: Vincent Diepeveen
Date: 13:45:26 09/30/00
Go up one level in this thread
On September 30, 2000 at 10:25:47, Gian-Carlo Pascutto wrote:
>
>I've read about singular extensions a lot and have
>seen this question multiple times on CCC but there's
>still one thing that I have never seen:
>
>a good, usable description of how to actually IMPLEMENT
>them, or even psuedocode
this has been never given by Hsu, and that's exactly
what sucks.
However using what Bruce described,
first search the moves with a REDUCED depth, then
extend singular moves.
I doubt overhead is 1 ply. For DIEP it's more like 3 ply
or so. Of course if you don't always use them it costs less,
but then they work less powerful.
>So, if you use singular extensions and have used them,
>and your implementation was at least acceptable,
>please, pretty please...
I could never ever get them to work.
I personally remember that the deep blue claimed like winning 9
rating points with them, that was at a depth of like 8 ply they
searched back then. Nowadays that would be significantly less.
They work for sure to solve many tactical problems a lot sooner,
but the practical usage of them is very doubtful.
For nullmove programs some other extensions passed them on the
left and the right. Very interesting are nimzo's deep search
extensions, so extending more if you search deeper, after getting
a ply or 10 quickly.
The basic advantage of threat extensions is that if you nullmove
you see threats very cheaply anyway.
If you use singular extensions, then depending upon how bigtime you
limit them they cost more or less.
Yet basically a move which is a margin S better as *all* the other moves in
a position p is called a singular move.
that means for example that after 1.e4,h5? 2.Qxh5?? that 2..Rxh5 is a singular
move already.
So the first thing most people do is exclude captures from the singular
extensions. Secondly you can distinguish 3 types of singular extensions
roughly.
- if your best move is between alfa and beta (so a PV move) then
you have a very accurate score for your best move m: score PVscore).
So you need a quite
cheap research then (cheap because the other singular moves are
way harder to detect). You just search with a reduced depth the
other moves with a window [PVscore-S,PVscore-S+1]
now if that window doesn't fail high then you have a singular
move m.
Way more interesting to solve tricks is if there is only 1 move that
gives a beta cutoff. Yet this is real bigtime overhead.
Let's before looking to any implementation first consider this:
you want to know whether a move m is singular, knowing it gives a beta
cutoff. That means that if you search all other moves with a reduced
depth (usually depth-2) that you search ALL moves instead of a SINGLE
move. Though these singular moves work great, the overhead of this
is just too much for anyone, assuming your branching factor doesn't
suck TOO much.
If you don't use nullmove and have a brnaching factor of a factor 10
or something, then sure it doesn't matter anything, because searching
for a singular move you need n searches of 1/100 of the current search.
however if you have n other legal moves and you have a branching factor
of 2.5 or something, then searching the remaining moves with reduced
depth-2, means each tree is of size 1/2.5 * 1/2.5 = 1/6.25 = 0.18
Now if you have like 40 legal moves on average (as the average
number of moves in positions MY program searches is at least 40,
and not the reported 35 as is in most books), then 40 * 0.18 = 6.4 that's
2 additional plies just for beta singular moves. We still didn't
count the extra nodes for the extra subtree you search because of
the extension!
Just the overhead is in advance 2 ply for beta singular moves if you
have a pretty good branching factor. Obviously you must put in your
hashtable that you extended this move m, because if later this gets a PV
move, then you want to extend it again.
Now actually though it's cool to extend only moves that fail high,
this is not the same as the above definition.
For example if beta is 0.181 and this move is giving a cutoff, but the
second best move is 0.179 then we talk about a singular margin of just 0.02
depending upon what move got first.
Less overhead but not easier to do are alfa singular moves as you need
to search all nodes anyway. However here you have a similar problem as
with betasingular moves. If you want to know exactly whether they
are a margin S singular, then you need first a true score from the
best move. So you need to search the best move with a window [-infinite,alfa]
first. That sucks IMHO.
So practical the only interesting thing IMHO are the beta singular moves,
but that's not the true definition of singular moves, apart from the
PV singular moves which you can extend pretty easy, it's very tough
to extend other moves as you don't know their exact value, just a cut
value somehow.
Now there are rude methods to still apply singular moves in a very
stripped and limited way.
>(Of course, an online reference to the above is also
>good enough ;)
>
>--
>GCP
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.