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.