Author: Alessandro Damiani
Date: 07:54:32 11/19/97
Go up one level in this thread
On November 17, 1997 at 10:46:05, Ulrich Tuerke wrote:
>Hi !
>Okay, now I see the idea. In fact, if Bob got it right, then the idea is
>some kind of "fail high reduction" as suggested by Feldmann. However,
>Feldmann's suggestion is not that radical: he just reduces the number of
>plies to the horizon by 1, if score >= beta- thus still including the
>quiescence search. One would also have to account for a large number of
>exclusions to make this reasonably work (do not cut when in check, when
>the side to move has hanging pieces, and so on).
>In any case, this idea is worthwhile to experiment with it. In my
>program I implemented some similar algorithm at depth=1. This a forward
>pruning mechanism which is completely independent of null move
>heuristics.
>By the way, Feldmann's article was published in some conference
>proceedings in 1996 as far as I remember.
>
>Regards, Uli
What I really mean (in the future I will be more precise, I`m sorry) is:
if "null-move allowed" & evaluate(position)>=beta ->
search null-move and cut if possible
fi
The idea is that we can look at the null-move heuristic as
score(null-move) = evaluate(position)-MaterialThreats(opponent),
if we only evaluate material in MaterialThreats(opponent). Of course:
searching the null-move is done by an alpha-beta search, so positional
threats are detected too. Here we assume material evaluation in
MaterialThreats(opponent).
In most cases, score(null-move)<=evaluate(position) and therefore
evaluate(position)<beta => score(null-move)<beta.
This is false i.e. if the opponent has pinned pieces, where doing
nothing has a high value. I tried this idea and it seems to work.
Does somebody have the same results?
Bytheway, in my program I have combined two methods of forward pruning:
the first part is the conventional recursive null-move. The second part
is a selective(!) null-move search. Only statically safe
(swapoff(from,to)>=0) threats two higher valued pieces and winning
captures (swapoff(from,to)>0) are searched. All other moves are
simulated by assuming that there is no material win (=
score(move)-best=0 => score(move)=best). Moves of hung pieces are
simulated this way: as in H. Kaindl`s work about quiescence search and
avoiding the horizon effect we look at the maximal loss (maxLoss on
square maxPos) and the most but one loss (mboLoss on square mboPos). If
the piece on maxPos is lost (actually only pinned pieces are handled)
then the loss caused by the xray attack is calculated and compared to
mboLoss. We assume that the side to move will save the piece on maxPos,
if not lost, and set best:= evaluate(position)-mboLoss:
proc ThreatSearch (beta, depth : int) : int
[[ if incheck ->
best:= beta-1; n:= GenOutOfCheck
[] ~incheck ->
if depth<=0 ->
best:= evaluate(position); if best>=beta -> return best fi;
n:= GenCaptures
[] depth>0 ->
StaticLoss(maxLoss,maxPos,mboLoss,mboPos);
{maxLoss=0 => mboLoss=0}
if maxLoss#0->
{is piece on maxPos lost?}
pinLoss:= Pinned(maxPos);
if pinLoss<maxLoss ->
if pinLoss>mboLoss -> maxLoss:= pinLoss
[] pinLoss<=mboLoss -> maxLoss:= mboLoss
fi
fi
fi;
best:= evaluate(position)-maxLoss;
if best>=beta -> return best fi;
n:= GenCapturesAndThreats
fi
fi;
i:= 0;
do i#n & best<beta ->
{m.i is the current move}
if incheck OR Promotion(m.i) OR EnpassantCapture(m.i) OR
(Capture(m.i) & SwapOff(m.i.from,m.i.to)>0) OR
(~Capture(m.i) & SwapOff(m.i.from,m.i.to)>=0) ->
make(m.i);
value:= -ThreatSearch(-beta+1,depth-1);
unmake(m.i);
best:= best max value
fi;
i:= i+1
od;
return best
]]
In my program evaluate(position):= material+SlowEval, where SlowEval is
constant through the search: see below.
and in alpha-beta:
[[{1<=depth}
if "null-move allowed" ->
SlowEval:= EvaluateSlow(position);
if material+SlowEval>=beta ->
make(null-move);
if depth<=D ->
value:= -ThreatSearch(-beta+1,depth-1)
[] depth>D ->
value:= -AlphaBeta(-beta,-beta+1,depth-3)
fi;
unmake(null-move);
if value>=beta -> return beta fi
fi
fi
]]
Actually I use D:= 4.
With this combination of forward pruning methods I get the best results.
Some other ideas?
Bye bye
Alessandro
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.