Author: Alessandro Damiani
Date: 17:04:19 02/13/00
Go up one level in this thread
On February 13, 2000 at 11:38:44, Gian-Carlo Pascutto wrote:
>Hi all,
>
>Just for fun, I decided to convert my program to AB-conspiracy search, to see
>how I'd work out. The results were not very encouraging...
>
>I have several questions:
>
>first, does anyone here use, used, or tested with AB-conspiracy search ? If so,
>what were your results ?
>
I am interested in ABC too, but I did not start to work on it. I made some
thoughts on it. I have to do a lot of other things before.
>second, the only source of information about ABC-search that I have is the
>McAllester/Yuret paper of 1993. It is informative, but I am still wondering
>about several things. For example, I am still wondering whether the constant
>they use to vary from conspiracy depth to ply depth (page 14) has any effect
>on the actual tree shape. Also, what would be a good value for the singular
>margin ? A pawn ? Half a pawn ? Even less ?
I think the best way is to define the singular margin depending on the
ply-depth. Near the root the margin could be 1/2 pawn, while near the horizon it
could be 1/4 pawn. A linear mapping could do the work.
The idea is that a singular move at ply = 2 in a 11-ply search hardly influences
the horizon-effect.
>third, they recommend to use a quiescence search as the static evaluator. But
>the ABC-algorithm can do that kind of search automatically due to the way it
>works. So why would one use a seperate qsearch function ?
>
The forcedness in a node is defined by the number of alternatives the player
has. If he has got ten moves, which scores vary "only a bit", he is less forced
than if he would have got only three moves with about the same score. If he has
only one move without similar alternative moves he is forced at the maximum.
Now, the problem is to score the moves. All moves in a node are made and
evaluated. If you do that only with the static evaluation function you will get
wrong scores. For instance, white to move can capture the black rook. By using
only static scores you evaluate that capture as a win. But a quiescence search
could reveal that black captures your white queen, and therefore capturing the
rook is a loss!
This happens, for example, when a white knight is trapped. Every move of the
knight loses material. If you evaluate these moves with the static evaluation
function you won't see that. The quiescence search evaluates every knight move
correctly as a loss. Now, let's assume the knight has only one escape square.
There is only one move that saves the knight, all the other moves lose.
The scores of the moves could be (by evaluating with the quiescence search):
1. score(m0) = 0 (escape move)
2. score(m1) = -3 (losing knight move)
3. score(m2) = -3 (losing knight move)
4. score(m3) = -3 (a quiet pawn move, the knight will be lost)
5. score(m4) = -9 (moves the queen to an unsave square, the queen will be
lost)
In this example m0 is singular. If the scores would have been calculated only
with the static evaluation function you would get a worse measure of forcedness.
And the measure of forcedness has a great influence on the convergence of the
search!
Note that by using the quiescence search you do a 1-ply search of all moves. One
could generalize this to search all moves k plies deep. For example k:= depth-R.
With R:= 1 you get Singular Extensions (with some exceptions). Just a thought.
>My program seems to have a lot of trouble to archieve even very small conspiracy
>depths, resulting in very weak tactical play. This seems to improve as the move
>ordering gets better, which is mentioned in the article, but what about those
>cases were your ordering can't be possibly right ? (discovering tactical shots)
>Its frustrating to see the ABC search look at a position that's mate-in-three
>for half an hour and never have it realize what the winning move is just
>because it happened to look at the wrong move first. Even with good move
>ordering the results are terrible. I can beat the darned thing. Uh! Also, the
>gains of using a smaller window seem minimal.
Did you try quiescence scores? Did you try to speed up near the horizon like
described in the paper?
I had another idea: in the paper the mapping
number of alternative moves at node p -> depth at node p
is defined as
f: N -> [0,1]
n |-> f(n)
with f as described in the paper. Special cases are:
f(0) = 0,
f(n) = 1 for all b<=n (for example b:= 30)
That means a move with no alternative moves gets a depth reduction of 0 and is
searched a full ply deeper. This may produce very deep trees.
What I thought is to avoid this behaviour by transforming f into g:
g: N -> [1,c]
n |-> g(n)
where c could be c:= 3. Now we have
g(0) = 1,
g(n) = 3 for all b<=n (for example b:= 30)
This way a very forced move has a depth reduction of 1 (it is searched with
depth-1), while not forced moves with depth reduction 3 (they are searched with
depth-3).
And your search will be deep at most the search-depth set at the root. What do
you think?
Alessandro
>
>I know there are several strong programs using a variant of conspiracy-number
>search, so I am curious as to what advacements they use. Is there any
>(preferrably online) source to new developments in this domain?
>
>In short, if anybody has any experience with this kind of search, I'd very
>much like to hear about it...
>
>--
>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.