Author: Robert Hyatt
Date: 09:26:50 08/03/98
Go up one level in this thread
On August 03, 1998 at 06:37:29, Robert Hyatt wrote: >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... OK... I ran a test that just finished. First, a result... on one key position, the normal crafty got to ply=10 in 7 seconds. On the same position, using this "fail-low-restart" idea, it got to ply 8 in 30 seconds. Here is what happened. In the position, crafty had just captured a pawn, and it appears that for several plies it could keep it. But the previous search, before the opponent played a non-predicted move had already found that it couldn't keep it, once it got deep enough to see why. However, this position crushed this "idea" because here is what happened: at depth=8, the first move failed low, finally seeing that the pawn could not be kept. Back to ply=1, pick a new best move, walk down to the same depth again (searching nodes that were skipped before and burning time) and this new best move also fails low. Back to ply=1, to find the 3rd best move (supposedly) which fails low. Over and over we go back, because *every* move fails low at depth=8, because the pawn can't be held. Based on this horrendous result, I write this off as useless, although I would be interested in results others get, if anyone finds this to be promising. All it did was slow me way down. In a position where the first move is the only "bad" one, it was still slower for me, probably due to a working transposition table that at least guides the search thru the second move and follows a few decent moves along the way. This code has been carefully excised from my source, however. :)
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.