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 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.