futility cut-offs
Alessandro Damiani
Hi!
I don't know the correct definition J. Schaeffer gave, but I have found
three different definitions of futility cut-offs:
1.) the authors of Zugzwang says: in the quiescence search the slow
static evaluation is avoided, if the following condition is true:
material+MAXPOS<alpha OR material-MAXPOS>beta,
where MAXPOS is the maximum positional score.
2.) J. C. Weill (Ecume, Cumulus, Joker) says:
if depth=1 & evaluate(Position)<alpha-delta ->
return ((alpha-delta) max Quiescence(alpha,beta)) min beta
fi,
where 0<delta. The quiescence search has to search checks too, in the
first layer.
3.) in a paper about selective extensions in Chinese Chess (mixture of
1.) and 2.)):
if depth=1 & material<alpha-MAXPOS ->
return ((alpha-MAXPOS) max Quiescence(alpha,beta)) min beta
fi,
The quiescence search has to search checks too, in the first layer.
I think the correct definition is 3.). Am I wrong? Did someone make
tests about futility cut-offs with deep search?
Alessandro
Robert Hyatt
Alessandro Damiani (adam...@g26.ethz.ch) wrote:
: Hi!
: I don't know the correct definition J. Schaeffer gave, but I have found
: three different definitions of futility cut-offs:
: 1.) the authors of Zugzwang says: in the quiescence search the slow
: static evaluation is avoided, if the following condition is true:
: material+MAXPOS<alpha OR material-MAXPOS>beta,
: where MAXPOS is the maximum positional score.
This is not really a cutoff. It is the first stage of a "lazy
evaluation" because if the material score is outside the alpha/
beta window, *and* the best/worst positional score we've computed
so far wouldn't bring the total score inside the window, there's
no need to do the evaluation at all. But this isn't really called
"futility cutoffs" by most of us.
: 2.) J. C. Weill (Ecume, Cumulus, Joker) says:
: if depth=1 & evaluate(Position)<alpha-delta ->
: return ((alpha-delta) max Quiescence(alpha,beta)) min beta
: fi,
: where 0<delta. The quiescence search has to search checks too, in the
: first layer.
This is the classic definition. If you are so far behind, and the
current move is not a tactical move that might win the material back,
you can discard this move as a "futile" move and go to the next one.
It does introduce errors.
I use a slight variation of this, and have for a long time. Rather
than simply giving up on the current move, I reduce the depth by one
and continue searching, to be fairly *sure* that this move won't
win the material back..
: 3.) in a paper about selective extensions in Chinese Chess (mixture of
: 1.) and 2.)):
: if depth=1 & material<alpha-MAXPOS ->
: return ((alpha-MAXPOS) max Quiescence(alpha,beta)) min beta
: fi,
: The quiescence search has to search checks too, in the first layer.
: I think the correct definition is 3.). Am I wrong? Did someone make
: tests about futility cut-offs with deep search?
There's one more definition. In the quiescence search, it is possible
to eliminate some captures as "futile". If the current material is
way less than alpha, and the piece being captured won't bring the score
above alpha, then it can be called a "futile" capture and tossed out.
There are other ways to make this more accurate, such as using a
static exchange evaluator to more accurately quantify the expected material
gain/loss from a capture.
: Alessandro
--
Robert Hyatt Computer and Information Sciences
hy...@cis.uab.edu University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170
Alessandro Damiani
Robert Hyatt wrote:
>
> Alessandro Damiani (adam...@g26.ethz.ch) wrote:
> : Hi!
>
> : I don't know the correct definition J. Schaeffer gave, but I have found
> : three different definitions of futility cut-offs:
>
[...]
> There's one more definition. In the quiescence search, it is possible
> to eliminate some captures as "futile". If the current material is
> way less than alpha, and the piece being captured won't bring the score
> above alpha, then it can be called a "futile" capture and tossed out.
> There are other ways to make this more accurate, such as using a
> static exchange evaluator to more accurately quantify the expected material
> gain/loss from a capture.
I tried out the (most selective) quiescence search I have found from G.
Schruefer`s "Minimax-Suchen":
proc Quiescence (alpha, beta : int) : int
[[ posval:= evaluate(position); if posval>=beta -> return posval fi;
best:= posval; alpha:= alpha max best;
n:= GenCaptures; i:= 0;
do i#n & best<beta ->
{ m.i is the current move}
winlimit:= posval+EGain(m.i);
if winlimit>alpha ->
make(m.i);
if winlimit<beta -> value:= -Quiescence(-winlimit,-alpha)
[] winlimit>=beta -> value:= -Quiescence(-beta,-alpha)
fi;
unmake(m.i)
[] winlimit<=alpha ->
value:= winlimit
fi;
if value>best ->
best:= value; alpha:= alpha max best
fi;
i:= i+1
od;
return best
]]
with EGain(m : Move):= SwapOff(m.from,m.to).
This quiescence search is very fast, but the problem is the positional
evaluation: if a capture has winlimit<=alpha then it is not searched,
although this move could be the best - if we look at the positional
score. So the best move is randomly chosen between those moves which has
the same material score. Now, I have developed a better quiescence
search (I think). This quiescence search is part of my chess program
Fortress (if there is a better one, please post it!) If somebody is
interested I will post it here.
utu...@hotmail.com
In article <346C3E...@g26.ethz.ch>,
Alessandro Damiani <adam...@g26.ethz.ch> wrote:
>
> Hi!
>
> I don't know the correct definition J. Schaeffer gave, but I have found
> three different definitions of futility cut-offs:
>
> static evaluation is avoided, if the following condition is true:
>
> material+MAXPOS<alpha OR material-MAXPOS>beta,
>
> where MAXPOS is the maximum positional score.
Obviously, this is a kind of evaluation window technique ("lazy
evaluation") which is in no way related to a futility cut-off.
>
> 2.) J. C. Weill (Ecume, Cumulus, Joker) says:
>
> if depth=1 & evaluate(Position)<alpha-delta ->
> return ((alpha-delta) max Quiescence(alpha,beta)) min beta
> fi,
>
> where 0<delta. The quiescence search has to search checks too, in the
> first layer.
>
> 3.) in a paper about selective extensions in Chinese Chess (mixture of
> 1.) and 2.)):
>
> if depth=1 & material<alpha-MAXPOS ->
> return ((alpha-MAXPOS) max Quiescence(alpha,beta)) min beta
> fi,
>
> The quiescence search has to search checks too, in the first layer.
>
> I think the correct definition is 3.). Am I wrong? Did someone make
> tests about futility cut-offs with deep search?
I would prefer definition (2). As far as I know, it's standard to take the
result of the static evaluation for the estimate instead of the very rough
estimate as represented by material in (3).
Regards, Uli
>
> Alessandro
-------------------==== Posted via Deja News ====-----------------------
http://www.dejanews.com/ Search, Read, Post to Usenet
Edward Screven
Alessandro Damiani wrote:
this is different than my qsearch implementation in two ways.
first, if i decide that a move is futile, i prune it completely.
it can never be the move selected at that node, and it does not
affect the score returned. if all moves are pruned, then the
returned value will be the static evaluation.
second, i use a different pruning decision expression. i prune
qsearch move m if
[1] VictimValue(m) + PositionalElasticity <= alpha; OR
[2] StaticExchange(m) <= T, where T is small constant near zero.
"PositionalElasticity" is just the term i use to name an estimated
upper bound on the per-move change in positional score. a typical
value for T might 0.10 pawns. (it makes sense for me to use a
fractional pawn value because my static exchanger takes into account
piece square table values.)
At one point I did use a merged form of [1] and [2], however it
seemed to suffer from too many errors, probably because my static
exchange evaluator doesn't account for pins and the like.
as a side note: i don't actually do this pruning in the body of
qsearch. it's implemented in my move generator. this is a win
for me because i generate captures by iterating over victims. [1]
is implemented by just skipping victims that aren't valuable enough.
[2] is implemented by a swapoff algorithm that avoids considering
captures by more valuable attackers if the less valuable attacker
capture is pruned.
- edward screven