Author: Guido Schimmels
Date: 02:50:04 08/03/98
Go up one level in this thread
On August 03, 1998 at 05:10:37, Robert Hyatt wrote:
>On August 03, 1998 at 04:10:34, Guido Schimmels wrote:
>
>>Getting a fail-low at the root is annoying, as we don't know what move to play
>>for quite a while.
>>There is in article by Schaeffer et al. ("Advances in alpha-beta searching")
>>suggesting to restart the search in these cases (setting depth to 1 again),
>>exploiting the benefits of a hash-table and finding a new best-move quickly.
>>But nobody seems to use this, why ? (or am I wrong here ?).
>>An important implementation detail not mentioned in this paper is, how to do the
>>windowing up to the search depth we restarted from - if we do aspiration as
>>normal isn't there a danger to get caught in an eternal restarting-loop ?
>>
>>- Guido -
>
>I haven't seen this, but don't see how it would work. Because it took
>the search reaching depth D to fail low in the first case. So all that
>will happen on the re-search from depth=1 is that you will fail low, then
>reduce alpha to -infinity and search again. But now the hash entry that
>says "fail low" can't be used, so you fail high or else get a valid score
>that is back in the vicinity that it was when this mess started. If you
>have to reach depth=D to fail low, searching any more at depth D-1 will
>not work, because it won't understand the position (won't have enough
>depth or extensions) to find the reason for the fail low.
>
>So there could be a danger in looping, but in reality, there is a danger
>of just wasting time, rather than trying to find a better move to replace
>the one that failed low...
Ho hum, I can give you an extract from the postscript file
"New Advances in Alpha-Beta Searching"
I downloaded from:
http://web.cs.ualberta.ca/~jonathan/pub.ai.html
"If at depth i the search fails low , restart the search back at depth 1.
Information about the previous search is
contained in the transposition table. When
the search is restarted, the best move has a bad
score allowing other moves to move ahead of
it in the ordered move list. Typically ,
the second best move now becomes best
and stays there until depth i is reached
again. By restarting the search, an
alternative best move is quickly generated,
alleviating the problems of the real-time
constraint. This idea has been successful in
the checkers program Chinook [26].
To test its effectiveness in chess, the games
played by Phoenix in the recent World
Computer Chess Championship (Hong Kong,
1995) were scrutinized. Three nontriv-
ial fail low scenarios occurred in the five
games. Phoenix was modified so that we
could see the impact of the restart
mechanism on these three positions. Note that in
the following results, for compatibility with
the results generated in the World
Championship, Phoenix is using search extensions.
1. The fail low occurred after a search of
3.1 million nodes (8 ply). Phoenix
was unable to find the correct move un-
til 10.7 million nodes had been examined.
Using restart, the program changed its mind
several times before finally finding the
right move at 8.4 million nodes.
2. The fail low occurred at 637,000 nodes (7 ply).
Without restart, the correct move was
found at 838,000 nodes. With restart, it is
found at 638,000 (3 ply) and deeper
search only confirms the move choice.
3. A fail low occurs at 4 ply and then
again at 8 ply (1,200,000 nodes).
The right move is found at 12,300,000 nodes.
W ith restart, the failure at 4 ply
restarts the search. This results in different move ordering
and dif ferent search extensions.
The correct move is found after
only 203,000 nodes! The above examples are
necessarily anecdotal. Finding inter -
esting fail low examples is difficult; there
are no test suites of fail low positions
readily available. However , these results
are consistent with experience gathered from the
Chinook program, indicating that the restart may
be a significant improvement in the
search. Not only does it quickly find better
moves in critical positions, our experience is
that in the presence of search extensions
the search results are also more
accurate."
- Guido -
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.