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.