Author: Robert Hyatt
Date: 03:37:29 08/03/98
Go up one level in this thread
On August 03, 1998 at 05:50:04, Guido Schimmels wrote:
>
>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 -
Still sounds like it won't work. IE when I fail low on the *first* move at the
root, I relax alpha and research that move, because I want to know how bad the
score is so I can figure out how much time I should allocate beyond the normal
target.
In that case, the whole idea above fails miserably... because at ply=1 the
first move will still fail low, but I will re-search, and now it will produce
the *exact same score* it did the first time I searched it at depth=1, because
I can't use the "fail-low" hash table entry to get a true score, and I can't see
deep enough to see the real fail low problem.
So in my case, I would just repeat the same search again, although very quickly
since hopefully the good scores and bounds from other moves would be kept in the
hash table...
This page took 0.01 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.