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.