Strange Stockfish behavior?

[hyatt]

When you get to depth 25 (or whatever) you find a hash entry left from that 30 ply search, that eventually causes you to fail high at the root. You open the window, which invalidates that hash entry, and you fail low. And you will _never_ get a true score for that move that reflects the fail high, until you get to depth=30 where you stored that hash entry in the first place.

I wouldn't expect a true score that reflects the fail high, but a true score that reflects the fail low after the fail high. For what I've seen in these cases is, that if Stockfish would not abandon the move, it would fail high again, or at least have a better score than the move Stockfish is currently going back to.

I am confused by this part:

>In at least your position, there is no fail-low to resolve: the search that fails low is a widened-window search to decide the value of the move that failed high.

~UncombedCoconut

So a5 can't get a true score at the same depth it fails high? Why can it do it at the same relative depth when the user forces the move?

A move at, say, depth 19 should have the same score as when you force it and reach depth 18. Conversely, a move that has a true score at depth 18 should have the same score at depth 19 if you backtrack the move.

What we have here:

18/21	 0:12 	-0.22 	2.Nf5 a4 3.h4 Bb4 4.Qg4 axb3 5.cxb3 Nc5 6.h5 Rh8 7.Rf2 Qd7 8.g6 hxg6 9.Qxg6 Kc8 10.h6 Nxd3 11.Rxd3 Kb8 12.Rg3 (9.501.819) 750

Is Stockfish giving a true score of -0.22 to the relative depth 19 of 1...a5, so, I don't really understand why can't Stockfish give that true score to a5 at depth 19, one move before, without needing the user to force the move.

You probably don't want the "real score". You know it failed high on some value beta, which means the expected score is >= beta. Whatever you do, which could include re-searching with -inf, same-beta, the score is going to be wrong. And what if it is quite low, so that another move at depth 25 replaces it? You are fiddle-farting around and wasting a lot of time on these re-searches, and you might well never get to 30 where the move in question will again fail high and this time likely produce a real score. This is a known problem, and an old one at that. Best scheme is when you fail-high, and then fail low, you don't lower alpha and keep the score of >= beta, which is almost certainly correct. Most don't do this, and in fact I am not sure I even do it for reasons that are no longer valid. But it is the most logical approach.

So you have two cases. Move fails high and fails low. You should always keep and play this move. Move fails high, then fails low, and when you lower alpha you get an exact score. You should still play this move, but the danger is that since the score is well below the fail-high score you had, another move can still replace this move. And you end up with a worse root move. Imagine this:

move 1: exact score =+1.2
move 2: fail high score >= +1.2
move 2: fail low score <= 1.0
move 2: exact score = +0.4
move 3: fail high, score >= +.4
move 3: exact score = +.5

Ugly, eh? You play move 3, which is worse than move 1 or 2.

[Uly]

So most likely we fail low, and still abandon the move (for this iteration at least).

That's fine, and desirable, as the user didn't need to force the move to see if it would be abandoned or not. And in the cases it we don't see another fail low, the move is not abandoned, and the user doesn't need to force th move to stick with it.

I guess my annoyance is not that Stockfish abandons good moves, but that the user has to force abandoned moves to see if they're bad or not, that wastes more time when they're bad (but the user would miss the good ones if he didn't do it).

[Uly]

Imagine this:

move 1: exact score =+1.2
move 2: fail high score >= +1.2
move 2: fail low score <= 1.0
move 2: exact score = +0.4
move 3: fail high, score >= +.4
move 3: exact score = +.5

Ugly, eh? You play move 3, which is worse than move 1 or 2.

Expected behavior:

move 1: exact score =+1.2
move 2: fail high score >= +1.2
move 2 switches places with move 1 (move 1 becomes 2 and 2 becomes 1)
move 1: fail low score <= 1.0
move 1: exact score = +0.4
move 2 (used to be move 1): exact score =+1.2 (from hash)
move 3: (doesn't fail high because >+.4 <+1.2)

That's how Naum 4 does it (the part where the fail high is ordered first), and it seems to work fine. Got fail high? Reorder the moves.

[UncombedCoconut]

So it restarts the entire iteration, just so it's forced to resolve the move to an exact score? That sounds bad to me, but I wouldn't mind being proven wrong. It's more fun to try to help than to criticize.
So here's a first try. It adds the UCI option "FHFL Behavior" which can be Reject Fail High, Accept Fail High, or Restart Iteration. (Note: The compiles aren't super-fast or GTB capable.)
Does it make a positive difference?

If I've misunderstood what you want, or you want to try another idea, just let me know.

[Uly]

Thanks UncombedCoconut, here's a run of the position, with my opinion of its implications for analysis:

r2k1r2/pp1n1q1p/1npP4/4p1P1/4P3/1PbB2NP/P1P1Q1RK/3R4 b - -

Stockfish fhfl 1CPU Analysis mode 128MB

Reject Fail high

.15/19	 0:00 	-0.02 	1...Qf3 2.Qxf3 Rxf3 3.Be2 Rf8 4.Bg4 Nc8 5.Bf5 Rf7 6.Be6 Rf3 7.Re2 Bb4 8.Nf5 Nc5 9.Bg8 Rf4 10.Bxh7 Nxe4 (666.871) 762
 16/13	 0:01 	 0.00 	1...Qf3 2.Qxf3 Rxf3 3.Be2 Rf8 4.Bg4 Nc8 5.Bf5 Rf7 6.Be6 Rf3 7.Bg4 Rf8 (1.084.334) 788
 17/13	 0:02 	 0.00 	1...Qf3 2.Qxf3 Rxf3 3.Be2 Rf8 4.Bg4 Nc8 5.Bf5 Rf7 6.Be6 Rf3 7.Bg4 Rf8 (1.598.685) 793
 18/13	 0:02 	 0.00 	1...Qf3 2.Qxf3 Rxf3 3.Be2 Rf8 4.Bg4 Nc8 5.Bf5 Rf7 6.Be6 Rf3 7.Bg4 Rf8 (2.101.320) 800
 19/17	 0:05 	-0.11++	1...Qf3 2.Qxf3 Rxf3 3.Be2 Rf8 4.Bg4 Nc8 5.Bf5 Rh8 6.Nh5 Bd4 7.c3 Bxc3 8.Nf6 Nf8 9.Ng4 Bd4 (4.728.279) 798
 19/22	 0:05 	-0.08 	1...Qf3 2.Qxf3 Rxf3 3.Be2 Rf8 4.Bg4 Nc8 5.Bf5 Rh8 6.Nh5 Bd4 7.Nf6 Nf8 8.Rgd2 Ng6 9.Kg3 Be3 10.Rg2 Bxg5 11.Nxh7 Rxh7 12.Bxg6 (4.765.601) 798
 19/03	 0:15 	-0.22++	1...a5 2.Nh5 Qf3 (11.635.562) 764
 19/24	 0:24 	-0.08--	1...a5 2.a4 Qf3 3.Qxf3 Rxf3 4.Be2 Rf8 5.Bg4 Nc8 6.Nh5 Bb4 7.Ng7 Nxd6 8.c3 Bc5 9.Rgd2 Rf7 10.Ne6+ Ke7 11.Nxc5 Nxc5 12.Rxd6 Nxe4 13.Re6+ (18.647.606) 767
 19/22	 0:24 	-0.08--	1...Qf3 2.Qxf3 Rxf3 3.Be2 Rf8 4.Bg4 Nc8 5.Bf5 Rh8 6.Nh5 Bd4 7.Nf6 Nf8 8.Rgd2 Ng6 9.Kg3 Be3 10.Rg2 Bxg5 11.Nxh7 Rxh7 12.Bxg6 (18.647.606) 767
 20/13	 0:27 	 0.00 	1...Qf3 2.Qxf3 Rxf3 3.Be2 Rf8 4.Bg4 Nc8 5.Bf5 Rf7 6.Be6 Rf3 7.Bg4 Rf8 (21.288.041) 776
 21/23	 0:42 	 0.00 	1...Qf3 2.Qxf3 Rxf3 3.Be2 Rf8 4.Bg4 Rg8 5.h4 Bb4 6.Be6 Rh8 7.Nh5 Nc8 8.Nf6 Nf8 9.Bxc8 Kxc8 10.Rf2 Ne6 11.Ng4 Nc5 12.Nf6 Ne6 (34.009.307) 791

Result: Bad. Reason: User knows a5 could actually be better than Qf3, but the user knew that when seeing Stockfish went back to 1...a5 without resolving the failing move cycle, so the -0.08--'s aren't helpful.

Accept Fail high

.15/21	 0:00 	-0.35++	1...Qf3 2.Qxf3 Rxf3 3.Be2 Rf8 4.Bg4 Bb4 5.Bf5 Rf7 6.Nh5 Nc8 7.Be6 Rf8 8.Bxd7 Kxd7 9.Nf6+ Ke6 10.d7 Nb6 11.Nxh7 Rfd8 (785.128) 797
 15/18	 0:01 	-0.13--	1...Qf3 2.Qxf3 Rxf3 3.Be2 Rf8 4.Bg4 Bb4 5.Bf5 Rf7 6.Be6 Rf4 7.Bf5 Nc8 8.c3 Bxd6 9.Bxh7 Kc7 10.Bf5 (818.549) 806
 15/10	 0:01 	-0.02--	1...Qf3 2.Qxf3 Rxf3 3.Be2 Rf8 4.Bg4 Nc5 5.Bf5 Rg8 6.Ne2 (1.038.133) 801
 15/22	 0:01 	-0.06 	1...Qf3 2.Qxf3 Rxf3 3.Be2 Rf8 4.Bg4 Bb4 5.Bf5 Rf7 6.Be6 Rf4 7.Bf5 Rh4 8.Rf2 Bc5 9.Rf3 Nc8 10.Bxd7 Kxd7 11.Rf7+ Ke6 12.Rf6+ (1.229.144) 802
 16/14	 0:02 	+0.15--	1...Qf3 2.Qxf3 Rxf3 3.Be2 Rf8 4.Bg4 Bb4 5.Nh5 Nc8 6.Ng7 Nxd6 7.c3 Bc5 8.b4 (2.000.783) 815
 16/09	 0:03 	 0.00 	1...Qg6 2.Nf5 Nc8 3.Bc4 b5 4.Nh4 Qe8 5.Nf5 Qg6 (2.952.386) 794
 17/09	 0:04 	 0.00 	1...Qg6 2.Nf5 Nc8 3.Bc4 b5 4.Nh4 Qe8 5.Nf5 Qg6 (3.522.798) 791
 18/09	 0:05 	 0.00 	1...Qg6 2.Nf5 Nc8 3.Bc4 b5 4.Nh4 Qe8 5.Nf5 Qg6 (4.689.660) 787
 19/09	 0:07 	 0.00 	1...Qg6 2.Nf5 Nc8 3.Bc4 b5 4.Nh4 Qe8 5.Nf5 Qg6 (6.184.585) 779
 20/09	 0:11 	 0.00 	1...Qg6 2.Nf5 Nc8 3.Bc4 b5 4.Nh4 Qe8 5.Nf5 Qg6 (9.192.760) 777
 21/09	 0:19 	 0.00 	1...Qg6 2.Nf5 Nc8 3.Bc4 b5 4.Nh4 Qe8 5.Nf5 Qg6 (15.312.141) 773
 21/09	 0:30 	-0.11++	1...a5 2.Nf5 Bb4 3.Rg4 a4 4.Qg2 axb3 5.cxb3 Kc8 (23.515.675) 765
 21/15	 0:35 	-0.22++	1...a5 2.Nf5 Bb4 3.Rg4 a4 4.Qg2 axb3 5.cxb3 Kc8 6.g6 hxg6 7.Rxg6 Kb8 8.Rg7 Qe6 (27.244.303) 763
 21/21	 1:17 	-0.16 	1...a5 2.Nf5 Bb4 3.Qg4 a4 4.h4 axb3 5.axb3 Kc8 6.h5 Rh8 7.Kg3 Qe8 8.g6 hxg6 9.Qxg6 Qf8 10.Rf2 Kb8 11.Ne7 Qh6 (58.470.268) 758

Result: Good. I actually like this behavior, Qg6 is found better and Qf3 is discarded at some point, in my experience, such behavior improves style for analysis, in similar positions Stockfish would be the only engine to suggest Qg6, and move originality is important.

a5 took 2 iterations more to appear, though, but at depth 21 this setting found a better move faster (plywise).

...

Now, I tried clearing the hash and trying Restart Iteration, and got that analysis again, so it seems the hash wasn't cleared or something. After reloading the engine and setting Accept Fail high again, I got this:

15/19	 0:00 	-0.02 	1...Qf3 2.Qxf3 Rxf3 3.Be2 Rf8 4.Bg4 Nc8 5.Bf5 Rf7 6.Be6 Rf3 7.Re2 Bb4 8.Nf5 Nc5 9.Bg8 Rf4 10.Bxh7 Nxe4 (666.871) 762
 16/13	 0:01 	 0.00 	1...Qf3 2.Qxf3 Rxf3 3.Be2 Rf8 4.Bg4 Nc8 5.Bf5 Rf7 6.Be6 Rf3 7.Bg4 Rf8 (1.084.334) 779
 17/13	 0:02 	 0.00 	1...Qf3 2.Qxf3 Rxf3 3.Be2 Rf8 4.Bg4 Nc8 5.Bf5 Rf7 6.Be6 Rf3 7.Bg4 Rf8 (1.598.685) 792
 18/13	 0:02 	 0.00 	1...Qf3 2.Qxf3 Rxf3 3.Be2 Rf8 4.Bg4 Nc8 5.Bf5 Rf7 6.Be6 Rf3 7.Bg4 Rf8 (2.101.320) 800
 19/17	 0:05 	-0.11++	1...Qf3 2.Qxf3 Rxf3 3.Be2 Rf8 4.Bg4 Nc8 5.Bf5 Rh8 6.Nh5 Bd4 7.c3 Bxc3 8.Nf6 Nf8 9.Ng4 Bd4 (4.728.279) 796
 19/22	 0:05 	-0.08 	1...Qf3 2.Qxf3 Rxf3 3.Be2 Rf8 4.Bg4 Nc8 5.Bf5 Rh8 6.Nh5 Bd4 7.Nf6 Nf8 8.Rgd2 Ng6 9.Kg3 Be3 10.Rg2 Bxg5 11.Nxh7 Rxh7 12.Bxg6 (4.765.601) 798
 19/03	 0:15 	-0.22++	1...a5 2.Nh5 Qf3 (11.635.562) 762
 19/24	 0:24 	-0.22 	1...a5 2.a4 Qf3 3.Qxf3 Rxf3 4.Be2 Rf8 5.Bg4 Nc8 6.Nh5 Bb4 7.Ng7 Nxd6 8.c3 Bc5 9.Rgd2 Rf7 10.Ne6+ Ke7 11.Nxc5 Nxc5 12.Rxd6 Nxe4 13.Re6+ (18.647.606) 766
 20/15	 0:31 	 0.00 	1...a5 2.a4 Qf3 3.Qxf3 Rxf3 4.Be2 Rf8 5.Bg4 Rg8 6.h4 Bb4 7.Bf5 Rh8 8.Bg4 Rg8 (23.978.451) 772
 20/24	 0:31 	-0.10 	1...Qf3 2.Qxf3 Rxf3 3.Be2 Rf8 4.Bg4 Nc8 5.Bf5 Rh8 6.Nh5 Bd4 7.Nf6 Nf8 8.Rgd2 Ng6 9.Kg3 Be3 10.Rg2 Bxg5 11.Nxh7 Rxh7 12.Bxg6 Bf4+ 13.Kg4 (24.485.612) 774
 21/13	 0:38 	 0.00 	1...Qf3 2.Qxf3 Rxf3 3.Be2 Rf8 4.Bg4 Nc8 5.Bf5 Rf7 6.Be6 Rf3 7.Bg4 Rf8 (29.918.233) 782

Can't call that bad, a5 was not abandoned because it wasn't resolved, it was abandoned because it had a score of 0.00, and Qf3 had a score of -0.10. The point is that a5 was found with a real score of -0.22 at the end of iteration 19 instead of the move being abandoned.

Restart iteration

15/19	 0:00 	-0.02 	1...Qf3 2.Qxf3 Rxf3 3.Be2 Rf8 4.Bg4 Nc8 5.Bf5 Rf7 6.Be6 Rf3 7.Re2 Bb4 8.Nf5 Nc5 9.Bg8 Rf4 10.Bxh7 Nxe4 (666.871) 762
 16/13	 0:01 	 0.00 	1...Qf3 2.Qxf3 Rxf3 3.Be2 Rf8 4.Bg4 Nc8 5.Bf5 Rf7 6.Be6 Rf3 7.Bg4 Rf8 (1.084.334) 788
 17/13	 0:02 	 0.00 	1...Qf3 2.Qxf3 Rxf3 3.Be2 Rf8 4.Bg4 Nc8 5.Bf5 Rf7 6.Be6 Rf3 7.Bg4 Rf8 (1.598.685) 792
 18/13	 0:02 	 0.00 	1...Qf3 2.Qxf3 Rxf3 3.Be2 Rf8 4.Bg4 Nc8 5.Bf5 Rf7 6.Be6 Rf3 7.Bg4 Rf8 (2.101.320) 800
 19/17	 0:05 	-0.11++	1...Qf3 2.Qxf3 Rxf3 3.Be2 Rf8 4.Bg4 Nc8 5.Bf5 Rh8 6.Nh5 Bd4 7.c3 Bxc3 8.Nf6 Nf8 9.Ng4 Bd4 (4.728.279) 798
 19/22	 0:05 	-0.08 	1...Qf3 2.Qxf3 Rxf3 3.Be2 Rf8 4.Bg4 Nc8 5.Bf5 Rh8 6.Nh5 Bd4 7.Nf6 Nf8 8.Rgd2 Ng6 9.Kg3 Be3 10.Rg2 Bxg5 11.Nxh7 Rxh7 12.Bxg6 (4.765.601) 798
 19/03	 0:15 	-0.22++	1...a5 2.Nh5 Qf3 (11.635.562) 763
<a5 becomes main move somewhere here>
 19/18	 0:28 	 0.00 	1...a5 2.a4 Qf3 3.Qxf3 Rxf3 4.Be2 Rf8 5.Bg4 Bd4 6.Nf5 Bc3 7.Rg3 Bb2 8.Rb1 Ba3 9.Ra1 Bb2 10.Rb1 (21.762.525) 769
 19/21	 0:28 	-0.08 	1...Qf3 2.Qxf3 Rxf3 3.Be2 Rf8 4.Bg4 Nc8 5.Bf5 Rh8 6.Nh5 Bd4 7.Nf6 Nf8 8.Rgd2 Ng6 9.Kg3 Be3 10.Rg2 Bxg5 11.Nxh7 Rxh7 (21.762.547) 769
 20/12	 0:31 	 0.00 	1...Qf3 2.Qxf3 Rxf3 3.Be2 Rf8 4.Bg4 Bb4 5.Bf5 Rf7 6.Be6 Rf8 7.Bf5 (24.846.382) 777
 21/09	 0:43 	+0.15--	1...Qf3 2.Qxf3 Rxf3 3.Be2 Rf8 4.Bg4 Bb4 5.Nh5 a5 (34.251.943) 788
 21/09	 0:55 	 0.00 	1...Qg6 2.Nf5 Nc8 3.Bc4 b5 4.Nh4 Qe8 5.Nf5 Qg6 (43.639.315) 780

Yes, this was the behavior I was talking about. I only find it odd that Stockfish finds a5 0.00 at depth 19 but when the user forces the move and clears the hash, at depth 18 it seems clearly better (score of -0.27). Why can't Stockfish see that from the root? I guess that's what Richard Vida meant with "you can't have your cake and eat it too".

Anyway, thanks again! Both Accept Fail High and Restart iteration seem like improvements over default behavior, and it's great to have the option to switch.

Other notes: The incident in where clearing the hash didn't have the same effect as reloading the engine was weird, can someone reproduce? (I can't reproduce the analysis that finds a5 at depth 21, it seems it was dependent on hash contents, even though I cleared it.)

[hyatt]

Imagine this:

move 1: exact score =+1.2
move 2: fail high score >= +1.2
move 2: fail low score <= 1.0
move 2: exact score = +0.4
move 3: fail high, score >= +.4
move 3: exact score = +.5

Ugly, eh? You play move 3, which is worse than move 1 or 2.

Expected behavior:

move 1: exact score =+1.2
move 2: fail high score >= +1.2
move 2 switches places with move 1 (move 1 becomes 2 and 2 becomes 1)
move 1: fail low score <= 1.0
move 1: exact score = +0.4
move 2 (used to be move 1): exact score =+1.2 (from hash)
move 3: (doesn't fail high because >+.4 <+1.2)

That's how Naum 4 does it (the part where the fail high is ordered first), and it seems to work fine. Got fail high? Reorder the moves.

That is not quite right, however.

For an example:

move one: score = 0.0

move two: score >= 0.5 (or whatever aspiration beta value is).

move two: score returned after relaxed alpha = 0.1 (when we had proven it >= 0.4 already)

move three: score = 0.2 and this is now the best move. Yet move two was proven to be better. After the fail high, it would be better to research with original beta - 1, +inf. If it fails low, keep score as original beta -1, which is +0.4, so that that weaker 3rd move can't slip into the gap and become best...

[UncombedCoconut]

That is not quite right, however.

For an example:

move one: score = 0.0

move two: score >= 0.5 (or whatever aspiration beta value is).

move two: score returned after relaxed alpha = 0.1 (when we had proven it >= 0.4 already)

move three: score = 0.2 and this is now the best move. Yet move two was proven to be better. After the fail high, it would be better to research with original beta - 1, +inf. If it fails low, keep score as original beta -1, which is +0.4, so that that weaker 3rd move can't slip into the gap and become best...

My "Accept fail high" implementation is similar. Did it test better in Crafty to use +inf instead of, as Stockfish uses, a new aspired beta?
I like your idea to keep the score as original beta - 1. I didn't think to force a preference for a later move that scores equally without a later fail-low.

FWIW, I think your arguments about how to treat the situation make the most sense. My own testing suggests that "Accept fail high" is strongest, but like Marco I was inside error bars before I gave up testing. I wanted to try filtering out games in which the option was unused (and unused in the rematch with sides reversed), but also gave up on that because (1) that was ~50% of the games and (2) if I've thought of an important fussy detail like including rematches, what if I missed some other important fussy detail?

@Jeremy: if you think this feature is worth inclusion in your tree, note that I have included the .git directory in my upload. I locally committed the changeset that add the feature, and made uncommitted changes that helped me cross-compile for Windows. You probably only want the former.

P.S. This is probably as good a place as any to whine about cross-development. Until now I've been satisfied (although I wish SF had a build system that was more complex and more flexible). But once I ran into this Wine bug which affects development versions of Stockfish I was actually pissed off.

[UncombedCoconut]

Now, I tried clearing the hash and trying Restart Iteration, and got that analysis again, so it seems the hash wasn't cleared or something.

Stockfish does clear its main hash in response to this button-type UCI option (although it does not do so in response to the ucinewgame command). I think it resets stuff like history, asp. window, etc. on a new think(). Does anybody have an obvious explanation for this nondeterministic result?

[UncombedCoconut]

I forgot to comment on this (and was too slow to avoid a triple-post).

The point is that a5 was found with a real score of -0.22 at the end of iteration 19 instead of the move being abandoned.

I always cringe when I see the phrase "real score". This time, I have a specific objection:
Here "my" SF calls this value exact, but this is a white lie. In "Accept fail high" mode, if one assumes its correctness, this value is a lower bound which cannot be improved at the current search depth.

(Most of the time my grounds are philosophical: a "real score", even if you believe evaluate(), should be some description of a random variable. That's neither what you want nor easy to calculate.)

[Uly]

I always cringe when I see the phrase "real score". This time, I have a specific objection:
Here "my" SF calls this value exact, but this is a white lie.

I realized that later, actually, Stockfish shouldn't output -0.22 if that is not a "real score", that only confuses the user as he assumes the fail high was resolved to -0.22, while in truth it wasn't. Stockfish should just go silently to a new iteration (IIRC this was old Stockfish behavior, 1.7? Stockfish would sometimes not resolve a fail high but go to the next iteration without resolving it, and without a real score).

Accept fail high becomes then bad for analysis (where the user may stop Stockfish at iteration n, and never let Stockfish get the real score of the move, because the user thinks that the fail high score is the real one).