Re-search fail low at root?

[bob]

If I run out of time on the fail-low re-search I will play the move that did not fail low, which is typically from currentPly - 2. However, I have some heuristics in time management which give a fail low re-search more time to complete, so this happens rarely.

Unfortunately that is a _really_ bad idea. How do you know that move is not even worse at this depth? As for it happening rarely, I'll simply point out that it takes just one bad move to lose a game. Over 40-60 moves this will likely happen at least once, and that's all you need to lose that game.

I'm not sure what you mean here. I don't re-search just that move, so if there is a better move than the one that failed low, I will find it. It's not possible to have a fail low again as my window is -infinity. By "rarely", I meant, it should never happen unless there is less than 1% of game time left. Now, this raises the question of whether it is good to always burn the extra time on fail low re-searches, but a lot of strong programs seem to do something similar.

yes I do. Classic case is a position where you are winning, but there are lots of ways to lose by getting checkmated. You are at +2, but you can only keep one of the two pawns when you analyze with a deep search. So the real score is going to be around +1. If you drop alpha to -infinity, suddenly you have to search all those forced checkmates against you, burning a ton of time, while if you dropped by one pawn, you would get the true score and still prune any mates against you...

It is easy enough to test the idea, I did and I am using it today. Used it in Cray Blitz 20 years ago as well...

Ok, I'll give this another try and see if I can get better results than my last test. I probably just used bad window values.

Whatever you do, there are problems to solve. Here's one that is pretty common:

You start a search and until you get very deep you think you are winning some major material advantage. But as you near the end of the search time limit, you discover your opponent didn't really make a blunder like you had thought, and instead of winning a pawn or something, it is really just an even position. But you _thought_ you were winning a pawn, and so finally dropping back to nearly even is a fail-low condition. Using extra time here to try to save that pawn is two-edged. Perhaps you can save it, so that the time used will be well-spent. But more often, especially against computers, you really can't save it, and the extra time used is just wasted.

This is really interesting part of controlling the search, just how much time should you use on any single move?

Here is a cute position that shows the opposite type of problem:

5r1k/6p/1n2Q2p/4p//7P/PP4PK/R1B1q/ w - - 0 1

This was a position reached in Cray Blitz (white) vs Belle (black) at the 1981 ACM computer chess tournament. We were having to run in a "batch mode" because our primary computer was down, which meant (a) no pondering at all; and (b) very shallow searches.

In this position, white is tempted to play Qxb6, which looks like it wins a knight, until you get to depth 8/9 or so. Which we could easily reach back then, but not in "batch mode". The correct move is Bxh6 which leads to a forced draw.

If you use a "that is an easy move" type early search termination, on slow enough hardware, you could conclude that Qxb6 is an obvious move and that your opponent hung a knight. If you search normally, you would discover that Qxb6 loses and that Bxh6 forces a draw by repetition.

So either way, stopping early on easy moves or going longer on harder moves can get you into trouble if you do them at the wrong time or for the wrong reason.

Note only that you do not need depth 8/9 to see that Qxb6 does not win a piece and clearly smaller depth is enough.

Uri, repeat after me:

"all plies are _not_ created equal".

Once you get that point, you will stop making posts like this one. We have seen _thousands_ of positions posted here where program A needs M plies, program B needs N plies and program C needs Q plies.

So, exactly what is your point. Here is Crafty's output, which is just as legitimate as any other program you quoted above:

Code: Select all

              depth   time  score   variation (1)
                1     0.00   5.13   1. Qxb6    (19Knps)             
                1->   0.01   5.13   1. Qxb6    (22Knps)             
                2     0.01   4.90   1. Qxb6 Rf2(22Knps)             
                2->   0.01   4.90   1. Qxb6 Rf2(47Knps)             
                3     0.01   5.09   1. Qxb6 Rf2 2. Be3 Qxa1 3. Bxf2 Qxa2
                3->   0.02   5.09   1. Qxb6 Rf2 2. Be3 Qxa1 3. Bxf2 Qxa2
                4     0.02   5.16   1. Qxb6 Rf2 2. Qd8+ Kh7 3. Kg3  
                4->   0.02   5.16   1. Qxb6 Rf2 2. Qd8+ Kh7 3. Kg3   
                5     0.03   5.23   1. Qxb6 Rf1 2. Qd8+ Kh7 3. Qd3+ Kh8
                                    4. b4
                5->   0.03   5.23   1. Qxb6 Rf1 2. Qd8+ Kh7 3. Qd3+ Kh8
                                    4. b4
                6     0.03     -1   1. Qxb6    (329Knps)             
                6     0.03     -3   1. Qxb6    (378Knps)             
                6     0.03     -M   1. Qxb6    (414Knps)             
                6     0.04  -0.46   1. Qxb6 Rf1 2. Qd8+ Kh7 3. Qd3+ e4
                                    4. Qxf1 Qxf1
                6     0.04  -0.37   1. Bxh6 Qxa1 2. Qxb6 Qxa2 3. Qd6 Rf6
                6     0.04   0.90   1. Qe7 Rf1 2. Qd8+ Kh7 3. Qd3+ Kh8
                                    4. Qg3
                6->   0.06   0.90   1. Qe7 Rf1 2. Qd8+ Kh7 3. Qd3+ Kh8
                                    4. Qg3
                7     0.07     -1   1. Qe7     (1.2Mnps)             
                7     0.07     -3   1. Qe7     (1.2Mnps)             
                7     0.08     -M   1. Qe7     (1.4Mnps)             
                7     0.10  -3.46   1. Qe7 Rf1 2. Qd8+ Kh7 3. Qd3+ e4 4.
                                    Qxf1 Qxf1 5. Kg3
                7     0.12  -0.45   1. Bxh6 Qxa1 2. Qxb6 Qxa2 3. Qc5 Re8
                                    4. Bc1
                7     0.13  -0.26   1. Qxb6 Rf1 2. Qd8+ Kh7 3. Qd3+ e4
                                    4. Qxf1 Qxf1 5. Kg3
                7->   0.14  -0.26   1. Qxb6 Rf1 2. Qd8+ Kh7 3. Qd3+ e4
                                    4. Qxf1 Qxf1 5. Kg3
                 8     0.14  -0.61   1. Qxb6 Rf1 2. Qd8+ Kh7 3. Qd3+ e4
                                    4. Qxf1 Qxf1 5. Kg3 e3
                8     0.17  -0.35   1. Bxh6 Qxa1 2. Qg6 Rg8 3. Qxb6 Qxa2
                                    4. Be3 Qd5
                8     0.21  -0.24   1. Bf4 Qxa1 2. Bxe5 Kh7 3. Qxb6 Qxa2
                                    4. b4
                8->   0.22  -0.24   1. Bf4 Qxa1 2. Bxe5 Kh7 3. Qxb6 Qxa2
                                    4. b4
                9     0.22  -0.49   1. Bf4 Qxa1 2. Bxe5 Kh7 3. Qxb6 Qxa2
                                    4. Qc7 Qf7 5. Qxf7 Rxf7
                9     0.25  -0.19   1. Bxh6 Qxa1 2. Qg6 Rg8 3. Qxb6 Qxa2
                                    4. Be3 Qd5 5. Kg3
                9->   0.32  -0.19   1. Bxh6 Qxa1 2. Qg6 Rg8 3. Qxb6 Qxa2
                                    4. Be3 Qd5 5. Kg3
               10     0.37   0.01   1. Bxh6 Qxa1 2. Qg6 Rg8 3. Bf4 Rb8
                                    4. Bxe5 Rb7 5. Qh5+ Kg8 6. Qe8+ Kh7
                                    7. Qh5+ Kg8
               10->   0.50   0.01   1. Bxh6 Qxa1 2. Qg6 Rg8 3. Bf4 Rb8
                                    4. Bxe5 Rb7 5. Qh5+ Kg8 6. Qe8+ Kh7
                                    7. Qh5+ Kg8

Looking above, a 5 ply search (crafty's 5 plies, not fruit's, Glaurung's, Shredder's, Zappa's, Fritz's, prodeo's, or any other program's) thinks it is winning big time.

It then realizes it is not winning, but still thinks Qb6 is best through depth 7. No guesswork, no speculation, just a real search result. Takes a tenth of a second to figure out that Qb6 is not so good...

depth 5 is enough for free fruit and free glaurung and even old crafty can see at depth 6 that Qxb6 is bad(but needs depth 9 to find Bxh6)

All of this depends on the program. Cray Blitz needed 7 plies to find the draw, but it did not get anywhere near that due to the conditions we were running it under.

And _none_ of this was the point. This was about trying to decide whether to use more time when in trouble or not, and whether to use less time on "obvious" moves or not.

It was an example, nothing more, nothing less...

BTW it took Glaurung to depth 8 to get rid of the losing move, which just shows that plies mean different things to different programs...

New game
[d]5r1k/6p1/1n2Q2p/4p3/8/7P/PP4PK/R1B1q3 w - - 0 1

Analysis by Fruit 2.1:

1.Qe6xb6
+- (3.46) Depth: 1/1 00:00:00
1.Qe6xb6 Rf8-f2 2.Qb6-d8+ Kh8-h7
+- (3.11) Depth: 2/8 00:00:00
1.Qe6xb6 Rf8-f2 2.Bc1-e3 Qe1xa1 3.Be3xf2 Qa1xa2
+- (3.17) Depth: 3/8 00:00:00
1.Qe6xb6 Rf8-f1 2.Qb6-d8+ Kh8-h7 3.Qd8-d3+ e5-e4
+- (3.16) Depth: 4/10 00:00:00
1.Qe6xb6 Rf8-f1 2.Qb6-d8+ Kh8-h7 3.Qd8-d3+ e5-e4 4.Qd3xf1 Qe1xf1
-+ (-1.48) Depth: 5/17 00:00:00
1.Bc1xh6 Qe1xa1 2.Qe6-g6 Rf8-f7 3.Qg6xf7 g7xh6
µ (-0.79) Depth: 5/23 00:00:00


New game
5r1k/6p1/1n2Q2p/4p3/8/7P/PP4PK/R1B1q3 w - - 0 1

Analysis by Glaurung 2.0.1:

1.Qe6xb6 e5-e4
+- (4.72) Depth: 2 00:00:00
1.Qe6xb6 Rf8-f2 2.Qb6-d8+ Kh8-h7
+- (4.74) Depth: 3 00:00:00
1.Qe6xb6 Rf8-f1 2.Qb6-d8+ Kh8-h7 3.Qd8-d3+ e5-e4
+- (4.00) Depth: 4 00:00:00
1.Qe6xb6 Rf8-f1 2.Qb6-d8+ Kh8-h7 3.Qd8-d3+ e5-e4 4.Qd3xf1 Qe1xf1
µ (-0.80) Depth: 5 00:00:00
1.Qe6xb6 Rf8-f1 2.Qb6-d8+ Kh8-h7 3.Qd8-d3+ e5-e4 4.Qd3xf1 Qe1xf1
µ (-0.80) Depth: 6 00:00:01 9kN
1.Qe6xb6 Rf8-f1 2.Qb6-d8+ Kh8-h7 3.Qd8-d3+ e5-e4 4.Qd3xf1 Qe1xf1 5.Kh2-g3
³ (-0.35) Depth: 7 00:00:01 13kN
1.Qe6xb6 Rf8-f1 2.Qb6-d8+ Kh8-h7 3.Qd8-d3+ e5-e4 4.Qd3xf1 Qe1xf1 5.Kh2-g3 e4-e3
µ (-0.84) Depth: 8 00:00:01 20kN
1.Qe6xb6 Rf8-f1 2.Qb6-d8+ Kh8-h7 3.Qd8-d3+ e5-e4 4.Qd3xf1 Qe1xf1 5.a2-a4 Qf1-d3 6.Bc1-f4
= (-0.13) Depth: 9 00:00:01 44kN
1.Bc1xh6 Qe1xa1 2.Qe6-g6 g7xh6 3.Qg6xh6+ Kh8-g8 4.Qh6-g6+ Kg8-h8 5.Qg6-h6+ Kh8-g8
= (0.00) Depth: 9 00:00:01 66kN


New game
5r1k/6p1/1n2Q2p/4p3/8/7P/PP4PK/R1B1q3 w - - 0 1

Analysis by Crafty 19.19:

1.Qe6xb6
+- (5.42) Depth: 1/7 00:00:00
1.Qe6xb6 Rf8-f2
+- (5.04) Depth: 2/7 00:00:00
1.Qe6xb6 Rf8-f2 2.Qb6-g6
+- (5.24) Depth: 3/7 00:00:00
1.Qe6xb6 Rf8-f2 2.Qb6-b8+ Kh8-h7 3.b2-b4
+- (5.11) Depth: 4/9 00:00:00
1.Qe6xb6 Rf8-f2 2.Bc1-e3 Rf2xg2+ 3.Kh2xg2 Qe1xa1 4.Qb6-b8+ Kh8-h7 5.Qb8xe5 Qa1xa2
+- (5.26) Depth: 5/10 00:00:00
1.Qe6xb6 Rf8-f1 2.Qb6-d8+ Kh8-h7 3.Qd8-d3+ e5-e4 4.Qd3xf1 Qe1xf1
= (-0.04) Depth: 6/13 00:00:00 42kN
1.b2-b4 Qe1xb4 2.Qe6xe5 Nb6-c4 3.Qe5-e2 Qb4-c5
± (0.72) Depth: 6/13 00:00:00 206kN
1.b2-b4 Rf8-f1 2.Qe6-e8+ Kh8-h7 3.Qe8-h8+ Kh7xh8 4.g2-g3 Qe1-e2#
-+ (-#4) Depth: 7/18 00:00:00 364kN
1.Qe6-e7 Rf8-f1 2.Qe7-d8+ Kh8-h7 3.Qd8-d3+ e5-e4 4.Qd3xf1 Qe1xf1 5.b2-b4
-+ (-3.83) Depth: 7/18 00:00:01 782kN
1.Qe6xb6 Rf8-f1 2.Qb6-d8+ Kh8-h7 3.Qd8-d3+ e5-e4 4.Qd3xf1 Qe1xf1 5.b2-b4
= (0.15) Depth: 7/18 00:00:01 828kN
1.Qe6xb6 Rf8-f1 2.Qb6-d8+ Kh8-h7 3.Qd8-d3+ e5-e4 4.Qd3xf1 Qe1xf1 5.b2-b4 e4-e3
³ (-0.44) Depth: 8/23 00:00:01 962kN
1.Qe6xb6 Rf8-f1 2.Qb6-d8+ Kh8-h7 3.Qd8-d3+ e5-e4 4.Qd3xf1 Qe1xf1 5.b2-b4 e4-e3 6.a2-a4
= (-0.14) Depth: 9/25 00:00:02 1584kN
1.Qe6xb6 Rf8-f1 2.Qb6-d8+ Kh8-h7 3.Qd8-d3+ e5-e4 4.Qd3xf1 Qe1xf1 5.b2-b3 e4-e3 6.Bc1-b2 e3-e2 7.Bb2-c3
³ (-0.58) Depth: 10/25 00:00:02 2338kN
1.Bc1xh6 Qe1xa1 2.Qe6-g6 Rf8-g8 3.Bh6-f4 Rg8-b8 4.Bf4xe5 Rb8-b7 5.Qg6-e8+ Kh8-h7 6.Qe8-h5+ Kh7-g8 7.Qh5-e8+ Kg8-h7
= (0.00) Depth: 10/25 00:00:03 2778kN

(so k, 27.03.2008)

[bob]

In positions where I'm seeing a fail-low on my root window, I used to open the window all the way, and do a re-search at the same ply.

However, this seems to be non-optimal. I am now opening the window, but not re-searching the same ply. This of course means, I don't get a best move from the ply I'm searchinb, but I am consistently getting *(sometimes quite a bit) greater depth in the same amount of time, so it seems more than worth the trade-off.

For example, on this position:
[d]
My engine used to take 1 second to reach ply 13, then failed-low, and ply 14 would take about 12 seconds to reach. After my test change, it hits ply 14 at 2 seconds, and makes it out to ply 18 in 12 seconds. This looks like almost a best case scenario, but in other fail low situations I've seen, this seems to be a positive change as well.

Anybody else try to speed up the fail-low re-search?

If you have enough searchtime left, this seems to work very well. You have to test when (ie with what percentage of time left) it's better to resolve the fail low fist.

Another idea is to not notice this, and when you do run out of time (too much) restart the search to (depth-2). With the information in hashtable (and the lower depth) this should finish very fast. But I never was really happy with this. It seemed to dangerous.

I don't use it at all anymore since I started searching the first move with an open window 3 years ago. It takes a bit longer for the first move, but the tree gets more stable and the rest of the moves go faster.

Tony

There are other approaches to handling a fail low. One is to just restart the search at depth=1. The hash table UPPER entry for the fail low move should make this move fail low on every iteration (if you are lucky enough) which will find a better move quicker. But I have never had any good results trying this. Aspiration/PVS seem to hurt this because if the root bounds change as the iterations progress the second time around, they can change enough that the old "bad" move won't fail low, and then the search will think it is the best move and you are now in a cycle that won't end.

[sje]

Aspiration/PVS seem to hurt this because if the root bounds change as the iterations progress the second time around, they can change enough that the old "bad" move won't fail low, and then the search will think it is the best move and you are now in a cycle that won't end.

I've seen this before. It is bound (ha ha) to occur sooner or later if either alpha or beta is contracted and later adjustments make that iteration go forever with restarts.

Symbolic's A/B searcher uses a scheme quite similar to Crafty's, but with different increment values.

Code: Select all

static const unsigned int theDelta0 = (CTSValPawn * 1) / 3;
static const unsigned int theDelta1 = (CTSValPawn * 4) / 3;
static const unsigned int theDelta2 = (CTSValPawn * 8) / 3;

In the above, the initial window is set to the estimated score plus or minus theDelta0 (one third of a pawn). Fail low results in a retry with the alpha dropped from the original estimated score by the next delta. On the third fail low, alpha is set to negative infinity.

The same thing happens for beta. Note that both alpha and beta adjustments may occur for the same iteration.

And as Bob mentioned, attempts to optimize this by a secondary, narrowing adjustment (e.g., lowering beta when lowering alpha) are at risk for infinite looping.

[Cardoso]

Aspiration/PVS seem to hurt this because if the root bounds change as the iterations progress the second time around, they can change enough that the old "bad" move won't fail low, and then the search will think it is the best move and you are now in a cycle that won't end.

I've seen this before. It is bound (ha ha) to occur sooner or later if either alpha or beta is contracted and later adjustments make that iteration go forever with restarts.

Symbolic's A/B searcher uses a scheme quite similar to Crafty's, but with different increment values.

Code: Select all

static const unsigned int theDelta0 = (CTSValPawn * 1) / 3;
static const unsigned int theDelta1 = (CTSValPawn * 4) / 3;
static const unsigned int theDelta2 = (CTSValPawn * 8) / 3;

In the above, the initial window is set to the estimated score plus or minus theDelta0 (one third of a pawn). Fail low results in a retry with the alpha dropped from the original estimated score by the next delta. On the third fail low, alpha is set to negative infinity.

The same thing happens for beta. Note that both alpha and beta adjustments may occur for the same iteration.

And as Bob mentioned, attempts to optimize this by a secondary, narrowing adjustment (e.g., lowering beta when lowering alpha) are at risk for infinite looping.

That was exactly what happened to me. I first saw this idea in a Jonathan Schaeffer's paper. On a fail low Chinook simply restarted the iterations from depth 1. Schaeffer explained that the info in the hash table helped on finding a better move than the one that caused the fail low.
When I tried that my engine looped forever failling low.
Maybe he used the hash table in a slightly different way.

regards,
Alvaro

Here's a citation the the mentioned paper (sorry for the long post):
"3.3 Failing Low at the Root
Aspiration searching anticipates where the value of a search
lies, and selects a small search window that encompasses
those expectations. If the search returns a result within the
aspiration window, then the expectations have been realized.
Exceeding the search window is usually not a problem; the
search is more favorable than anticipated. However, under
the real-time constraints of a tournament game, a first move
that returns a result below the window (failing low) can cause
serious problems. Typically, most Alpha-Beta implementations
re-search the move to find its true score and then hunt
for better moves. Until the right move is found, there is a
danger that (time) resources will run out and the program
will be forced to move before resolving the difficulty. The
program needs to find an alternative best move quickly.
The solution is to restart the search. 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 nontrivial
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 until
10.7 million nodes had been examined. Using restart,
the program changed its mind several times before fi-
nally 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. With restart, the failure at 4 ply
restarts the search. This results in different move ordering
and different search extensions. The correct move
is found after only 203,000 nodes!
The above examples are necessarily anecdotal. Finding interesting
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."

[bob]

Aspiration/PVS seem to hurt this because if the root bounds change as the iterations progress the second time around, they can change enough that the old "bad" move won't fail low, and then the search will think it is the best move and you are now in a cycle that won't end.

I've seen this before. It is bound (ha ha) to occur sooner or later if either alpha or beta is contracted and later adjustments make that iteration go forever with restarts.

Symbolic's A/B searcher uses a scheme quite similar to Crafty's, but with different increment values.

Code: Select all

static const unsigned int theDelta0 = (CTSValPawn * 1) / 3;
static const unsigned int theDelta1 = (CTSValPawn * 4) / 3;
static const unsigned int theDelta2 = (CTSValPawn * 8) / 3;

In the above, the initial window is set to the estimated score plus or minus theDelta0 (one third of a pawn). Fail low results in a retry with the alpha dropped from the original estimated score by the next delta. On the third fail low, alpha is set to negative infinity.

The same thing happens for beta. Note that both alpha and beta adjustments may occur for the same iteration.

And as Bob mentioned, attempts to optimize this by a secondary, narrowing adjustment (e.g., lowering beta when lowering alpha) are at risk for infinite looping.

That was exactly what happened to me. I first saw this idea in a Jonathan Schaeffer's paper. On a fail low Chinook simply restarted the iterations from depth 1. Schaeffer explained that the info in the hash table helped on finding a better move than the one that caused the fail low.
When I tried that my engine looped forever failling low.
Maybe he used the hash table in a slightly different way.

regards,
Alvaro

Here's a citation the the mentioned paper (sorry for the long post):
"3.3 Failing Low at the Root
Aspiration searching anticipates where the value of a search
lies, and selects a small search window that encompasses
those expectations. If the search returns a result within the
aspiration window, then the expectations have been realized.
Exceeding the search window is usually not a problem; the
search is more favorable than anticipated. However, under
the real-time constraints of a tournament game, a first move
that returns a result below the window (failing low) can cause
serious problems. Typically, most Alpha-Beta implementations
re-search the move to find its true score and then hunt
for better moves. Until the right move is found, there is a
danger that (time) resources will run out and the program
will be forced to move before resolving the difficulty. The
program needs to find an alternative best move quickly.
The solution is to restart the search. 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 nontrivial
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 until
10.7 million nodes had been examined. Using restart,
the program changed its mind several times before fi-
nally 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. With restart, the failure at 4 ply
restarts the search. This results in different move ordering
and different search extensions. The correct move
is found after only 203,000 nodes!
The above examples are necessarily anecdotal. Finding interesting
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."

There are some serious flaws here that get overlooked. For but one example, suppose you get to depth 16 and you fail low on an alpha value of +1.3. You re-start at ply-1and so long as your alpha value is >= 1.3, that ply-16 root move should continue to fail low. But if you fail low at the root any where along the way back to depth=16, you are in trouble, because when you relax alpha anywhere along the way, if you relax it to below +1.3, the original ply-16 root move will no longer fail low, it will then become the best move again, and you are right back where you started.

I've never been able to get any version of this idea to work. And, in fact, it has been suggested that you might search the entire root move list after a fail low before you relax alpha. The problem I found with that was that if you do this, by the time you cycle back around to search the original root move with a lower bound, many of the hash table entries from that search are gone, and you now execute a less-informed search which takes more time. Best time to evaluate a move after a fail low is immediately after the fail low where you still have lots of relevant information to make the re-search more efficient.

[sje]

Best time to evaluate a move after a fail low is immediately after the fail low where you still have lots of relevant information to make the re-search more efficient.

And for fail-high as well. This is why zero width search of the second through nth moves works at all ply; at least most of the time.

[bob]

Best time to evaluate a move after a fail low is immediately after the fail low where you still have lots of relevant information to make the re-search more efficient.

And for fail-high as well. This is why zero width search of the second through nth moves works at all ply; at least most of the time.

I agree. In 1978 or so, Ken Thompson was using a variant of PVS where the first fail high was not re-searched, the idea being that if no other move fails high, then the first fail high is the best move. The problem is that if a later move fails high, then suddenly you have two possible best moves, and researching the first best move now might be slower than normal because the hash entries from that search are gone.

Belle didn't store best move in the hash table, so he didn't see this inefficiency, but I did when I tried this approach at the urging of Murray Campbell.

[Cardoso]

Best time to evaluate a move after a fail low is immediately after the fail low where you still have lots of relevant information to make the re-search more efficient.

And for fail-high as well. This is why zero width search of the second through nth moves works at all ply; at least most of the time.

I agree. In 1978 or so, Ken Thompson was using a variant of PVS where the first fail high was not re-searched, the idea being that if no other move fails high, then the first fail high is the best move. The problem is that if a later move fails high, then suddenly you have two possible best moves, and researching the first best move now might be slower than normal because the hash entries from that search are gone.

Belle didn't store best move in the hash table, so he didn't see this inefficiency, but I did when I tried this approach at the urging of Murray Campbell.

going back to Jonathan Schaeffer's idea, one thing came to my mind:
could it possibly be that the idea of restarting the iterations to depth 1 does indeed work in a fail soft search (as opposite to fail hard)?
What do you guys think about this?

Alvaro

[bob]

Best time to evaluate a move after a fail low is immediately after the fail low where you still have lots of relevant information to make the re-search more efficient.

And for fail-high as well. This is why zero width search of the second through nth moves works at all ply; at least most of the time.

I agree. In 1978 or so, Ken Thompson was using a variant of PVS where the first fail high was not re-searched, the idea being that if no other move fails high, then the first fail high is the best move. The problem is that if a later move fails high, then suddenly you have two possible best moves, and researching the first best move now might be slower than normal because the hash entries from that search are gone.

Belle didn't store best move in the hash table, so he didn't see this inefficiency, but I did when I tried this approach at the urging of Murray Campbell.

going back to Jonathan Schaeffer's idea, one thing came to my mind:
could it possibly be that the idea of restarting the iterations to depth 1 does indeed work in a fail soft search (as opposite to fail hard)?
What do you guys think about this?

Alvaro

It would still have the same potential for looping. Fail-soft is not guaranteed to back up the actual score to the root on a fail high or fail low, just something that might be more accurate than just backing up alpha or beta. But the same problem can surface if anything happens during the search to make that fail-low bound no longer valid, as now that move will appear to be the best, which is what started this problem initially...