Author: Dezhi Zhao
Date: 03:54:49 08/05/98
Go up one level in this thread
On August 03, 1998 at 12:26:50, Robert Hyatt wrote: >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. :) Hi! I tried the fail-low-restart today on several fail-low positions. Unlike Dr. Hyatt's recursive implementation, I just relax alpha and search from ply = 1 to i where we fail low, regardless of fail-lows at ply = 1 to i - 1. It seems to me that fail-low-restart provides no savings if we want to search to ply = i where we fail-low, but it may be a trick to control time. In one of the positions, my program failed low at ply = 10 with 3.1M nodes, normal research found a new best move with another 7.7M nodes. The old best move sticked there form ply = 1 to 9, due to horizontal effect. The restart method found the new move with another 8.4 M nodes (ply 10). However restart method *began* to find the new move at ply 5 (~2M nodes), which is perhaps what Dr. Schaeffer really implied. The article did not mention that the restart needs to go back to ply = i. Therefore, if you are willing to take the risk, you may get the new best move found at ply < i and save a lot of time. For other fail-lows due to tight alpha, in 2 positions the restart method saved less than 10%, but in other 3 positions it losed 10%. Best Regards Dezhi Zhao
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.