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 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.