Re-search fail low at root?

[gladius]

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?

[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?

First, what are you going to do if you run out of time and all you have is a fail low from the previous iteration? what move will you play? And what will this be based on?

Second, rather than just replacing the lower bound with -infinity and re-searching, you can do what I do and drop it in steps, so that you still get lower bound cutoffs to speed things up...

[gladius]

First, what are you going to do if you run out of time and all you have is a fail low from the previous iteration? what move will you play? And what will this be based on?

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.

Second, rather than just replacing the lower bound with -infinity and re-searching, you can do what I do and drop it in steps, so that you still get lower bound cutoffs to speed things up...

Interesting, do you find that the larger window still helps very much? Once I start hitting a pawn sized window, I've noticed very little gain.

[Tony]

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

[bob]

First, what are you going to do if you run out of time and all you have is a fail low from the previous iteration? what move will you play? And what will this be based on?

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.

Second, rather than just replacing the lower bound with -infinity and re-searching, you can do what I do and drop it in steps, so that you still get lower bound cutoffs to speed things up...

Interesting, do you find that the larger window still helps very much? Once I start hitting a pawn sized window, I've noticed very little gain.

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

[Cardoso]

adding to that what about doing also:
- if current iteration_depth>14 ->no sense doing at lower search depths where fail lows might occur more frequetely.
- first and second move failed low (their scores < root_alpha)
- (NRootMoves > 10)
then relax root_alpha as you said in steps and do a research of the same iteration.
The idea being if it failed low on first move and on the second move then problably the rest of the moves will fail low also so we save some time by avoiding search the rest of the moves with the current root_alpha.
I never tested this, but what do you think?

regards,
Alvaro

[bob]

adding to that what about doing also:
- if current iteration_depth>14 ->no sense doing at lower search depths where fail lows might occur more frequetely.
- first and second move failed low (their scores < root_alpha)
- (NRootMoves > 10)
then relax root_alpha as you said in steps and do a research of the same iteration.
The idea being if it failed low on first move and on the second move then problably the rest of the moves will fail low also so we save some time by avoiding search the rest of the moves with the current root_alpha.
I never tested this, but what do you think?

regards,
Alvaro

I've tried two approaches, one of which is similar...

1. when the first move fails low, relax alpha a bit and re-search. if it fails low again, relax farther. Repeat until alpha gets to -infinity. How many steps you use can be determined by testing. I believe that I use first a pawn, then a piece, and finally -infinity. I do this to make sure I know how bad the first move is, before moving on, so that I can intelligently decide how much extra time to use to try to "fix" the problem.

2. When the first move fails low, keep searching, the assumption being that just because the first move is suddenly significantly worse, there might be another move that will produce a score close to the original expectation. This is faster. Unless all moves fail low because you really are losing something. Then you go back and once again you can step down or drop all the way to -infinity as you choose. But until you get a score, you won't know whether you are losing a fraction of a pawn or a queen, so it is difficult to determine how much extra time to use to save something, when you don't know exactly what you are trying to save...

[gladius]

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.

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

[Uri Blass]

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.

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)

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)