Author: Robert Hyatt
Date: 17:34:19 03/11/99
Go up one level in this thread
On March 11, 1999 at 18:39:20, William Bryant wrote:
>Following several discussions over the last 6 to 12 months, plus David Levy's
>1993 book "How Computers Play Chess", I think I have the basic idea for
>implementing aspiration windowing.
>
>By using the score returned from the previous iteration +/- some search interval
>(from 1/3 to 1 pawn, YMMV), you try to create faster cutoffs and therefore a
>quicker search. If you fail high (score greater than initial beta, ie previous
>score + interval), you research with a window of (beta, beta+1), and if you fail
>high again with a window of (beta+1, Mate). If you fail low, you research with
>a window of (-Mate, alpha).
No.. I think you are mixing two different things (1) aspiration window search
and (b) PVS/NegaScout/etc.
Aspiration window searching means you choose a window at the root that is way
less than +inf,-inf. And you search using that restricted window. Of course,
if you get a value of beta back, you have to re-search with beta,+infinity as
the window, or if your window was too high and you get alpha back, you re-
search with -infinity,alpha as the window.
The +1 stuff is from PVS, where you search the first branch at any node with
alpha,beta, and search the remainder with alpha,alpha+1. If any of these fail
high, you re-search with the original alpha,beta window...
I use both together.
>
>The first research when failing high is a _very_Narrow_ window of only 1
>centipawn. Is this correct, or should it be the value of 1 pawn?
>
>Any comments or suggestions would be appreciated.
>This is the basic idea in pseudocode/code as I understand it.
>
>long InitialAlpha = -Mate;
>long InitialBeta = Mate;
>long Window = 40; // 4/10 of a pawn
>
>for (long Depth = 1; Depth <= MaxSearchDepth; Depth ++) {
> score = absearch(InitialAlpha, InitialBeta, Depth);
>
> if (score >= InitialBeta) { //Fail High
> score = absearch(InitialBeta, InitialBeta + 1, Depth);
> if (score >= InitialBeta +1)
> score = absearch(InitialBeta + 1, Mate, Depth);
> }
> else if (score < InitialAlpha) //Fail Low
> score = absearch(-Mate, InitialAlpha, Depth);
>
> InitialAlpha = score - Window;
> InitialBeta = score + Window;
>
> if (OutOfTime)
> break;
>}
>
>
>Thanks,
>
>William Bryant
>wbryant@ix.netcom.com
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.