Author: Rudolf Posch
Date: 03:25:07 03/22/00
Go up one level in this thread
On March 22, 2000 at 03:19:53, Bruce Moreland wrote:
>On March 22, 2000 at 03:04:26, Rudolf Posch wrote:
>
>>One small comment: in the last line of your pseudo code you return alpha.
>>Should this line not be "return score", because if the value of the actual
>>position doesnt reach alfa you return a too high value?
>
>The code is correct as written, unless the caller does something weird.
>
>If you do "return score" it's wrong because if there are no legal moves you
>return an undefined value.
>
>And if there are legal moves, this simply returns the score for the last move
>searched.
>
>Some of these algorithms attempt to return valid scores that are outside the
>window. I've never figured out how to do this. One of the systems that tries
>to do this doesn't work with a variable depth search.
>
>I think it makes as much sense to do ...
>
> if (score >= beta)
> return beta;
>
>... as it does to do ...
>
> if (score >= beta)
> return score;
>
>At the edge of the window is just as good as outside it, and in normal alpha
>beta it's all you really "know" if your search non-trivially deep.
>
>bruce
Thank you Mr. Moreland for your comment.
The Internet is incredible: A small unknown chess programmer like me gets an
immediate reply from a well known expert (I have read many articles and books
related with you).
The problem was discussing a pseudo code, where not all lines are shown.
In my private chess program I use a local variable "best", which is initialized
with a very low value ("-mate") at the begin of the Search() procedure.
"best" is raised with every move which returns a better value as the "old best".
The "Fail Safe" - Search() procedure returns "best", best may be <=alpha (fail
low), exact or >= beta (fail high) and the move which aquired that value.
The "best" value is used in my program as a narrower bound at search
repeatitions:
- At the root node, if a "fail low" occured, the search is repeated with
Search(-mate,best+1) or if a "fail high" occured with Search(best-1,+mate).
- at NegaScout searches with null windows and "alpha < best > beta" the search
is repeated with Search(best-1,Beta).
I use further the "best" value in the hash table as "upper bound" (if best <=
alfa), and as "lower bound" (if best >= beta).
A "best" move with "best" > beta is stored in the PV (although it may not be the
very best, see sentence 2 below).
I even tried to put the "best move" with "best" < alpha in the principial
variation (PV) starting from this position, but tests showed that the progam
degrades with this measure (sentence 1 below may explain the reason).
I have thought strongly about the fail safe alfa-beta algorithm and came to 2
sentences which should be true:
1) if the search fails low and returns a move with value best <= alfa, there is
no move which is better than this move. The returned move may have a worse value
(best is an upper bound), all other moves are equal/worse as the returned move.
WHICH MOVE IS BEST IS UNKNOWN.
2) if the search fails high and returns a move with best >=beta, this move is at
least "best" good (it may have even a greater value, best is a lower bound).
There may be other moves with higher values. WHICH MOVE IS BEST, IS UNKNOWN.
If those thoughts are right,
your sentence "
>At the edge of the window is just as good as outside it, and in normal alpha
>beta it's all you really "know" if your search non-trivially deep."
"
should be constrained to the normal alfa-beta search. Fail safe Alfa Beta search
and the other improved algorithms (PVS, NS,..) (which were invented by you or
with your help) give additional information with the value "best" outside the
alpha/beta window.
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.