Search explosion / Search stuck at a given depth #3911
Comments
|
which version of SF ? |
|
Apologies, Version Date: Sat Jan 29 08:58:12 2022 +0100 Timestamp: 1643443092 |
|
Reported depths and seldepths look normal to me. No search explosion, just a position with a high branching factor. for example: |
|
maybe this position is a better example of maybe unintended results after "Simplify limiting extensions" commit kind of "stalls" at random depths and needs very long to find 1.Kd3 reverting "Simplify limiting extensions" solves it fast |
|
I also have a hung search. |
|
The problem with the analysis hanging disappeared on the stockfish_22012018_x64_bmi2. But still, productive games are analyzed more slowly than draws |
|
Analysis is carried out at 26 depth |
|
you'll need to provide FENs that illustrate the problem, otherwise it is not possible to analyze. |
after some research i found deleting in search.cpp cures these stalling effects somehow. The actual "Big search tuning" commit does it too, changing this to Maybe there is an underlying issue in |
|
probably these stalls are hidden double extensions? search.cpp ` |
|
Another example of the same phenomenon. I've cut the output of the first ply 40 to keep this post readable. There is output for the first 9.5 minutes and then nothing more and I stopped the engine at 99 minutes. Version #3937 |
You don't need to do that, just use a codeblock |
stuwph suggestion seems correct. Removing deeper indeed solves the stalling for me. |
|
we can treat deeper the same way as singular extensions with non-regression test. |
Closed
|
This is another example where the search explodes. I found this position here. Only one thread now, just as the post in Talkchess. FEN r3r1k1/2qb1pp1/pp2n1np/2p1P3/2R1N3/1B3N1P/PP1Q1PP1/4R1K1 w - - After ply 17 no more output and I stopped the engine after an hour. I'll test the same position in #3943 and with deeper in LMR removed. |
|
Same conditions as my post above, but with deeper removed. I have no idea how to initiate a regression test because I think removing deeper really deserves a go. Removing deeper solves a lot of problems imho. |
|
Here is something you might try. Could also be done in concert with Viz's patch limiting based on ply. |
|
Testing with jhellis' patch along with Viz's patch (combined): FEN: |
|
I don't understand why we don't just test a version without deeper, especially at STC and LTC. Please excuse my ignorance, but I have no idea how to initiate such a test myself and to me it seems that this piece of code brings more bad than good. search.cpp, remove search.cpp, add |
|
Submitted a test. https://tests.stockfishchess.org/tests/view/6218b2f3da649bba32ef3f56 |
|
probably not passing at LTC https://tests.stockfishchess.org/tests/view/6218d940da649bba32ef43e8 |
|
Could you try this version: jhellis3@a242d5b It should be much more effective. |
Pity, but it was worth the try to get rid of the search explosions. I'll have a look at jhellis3 version of deeper. |
With jhellis3@a242d5b version of deeper the output on this position. Better than the original deeper but not as good as without deeper. Yet no stalling after an hour. |
Here jhellis3@a242d5b version works like a charm. Time to depth is faster than without deeper. I will now test the position in my first post in this topic, but that will probably take hours to come to a conclusion. |
Definitely better than the original deeper in terms of time to depth, but last pv at 51.8 minutes and I stopped the search after 4 hours. |
|
Would there be an objection to testing the above patch as a non-regression at LTC? It was Elo neutral after 144k games here: https://tests.stockfishchess.org/tests/view/6218fbcdda649bba32ef4853 |
|
Not my call I suppose but I consider it an improvement over the current implementation of deeper. Give it a go as far as I am concerned. |
|
Some examples using the latest version, bench: 7729968 |
|
Another example using the latest version, bench: 7729968 |
|
Another example using the latest version, bench: 6174823 |
|
More examples using the latest version, bench: 6174823 |
|
@BetaTester-cpu |
|
Another example (stuck at depth 33) using the latest version, bench: 6174823 |
I think it would be better if you specified the version like this -> 9eb7b60 |
|
r1b2rk1/pp2bppp/2n1p3/qB2P3/3B4/2N3Q1/PPP3PP/2KR1R2 b - - 6 15 |
|
interestingly one can follow along on the stuck moves (currmove) and observe this stuck behavior for a while on all fens along the line, untill there is a critical position, for which seldepth is much larger than depth (like depth 38 and seldepth 70 (d4c5)) position fen r1b2rk1/pp2bppp/2n1p3/qB2P3/3B4/2N3Q1/PPP3PP/2KR1R2 b - - 6 15 moves a5c7 b5c6 b7c6 c3e4 c8a6 f1f4 g8h8 |
|
3 local searches, last output at 1-7s and then no further output for +24h Those 3 local searches with 2 positions on my machine (has busy CPU): Stockfish 15 by the Stockfish developers (see AUTHORS file) Same position, latest version 2022-05-04: Related but different position, latest version 2022-05-04: In all cases no output for +24h, after stopping: info depth 23 seldepth 42 multipv 1 score cp 285 nodes 46189853116 nps 507062 hashfull 1000 tbhits 827 time 91092991 pv e4d6 info depth 20 seldepth 30 multipv 1 score cp -150 upperbound nodes 45730947750 nps 504699 hashfull 1000 tbhits 2561 time 90610174 pv f8d8 g3g5 |
|
Another example (stuck at depth 25) using the latest version, bench: 6481017 |
|
Another example (stuck at depth 34) using the latest version, bench: 6481017 |
|
Another example (stuck at depth 28) using the latest version, bench: 6407734 |
|
Another example (stuck at depth 27) using the latest version, bench: 6410652 |
|
Another example (stuck at depth 26) using the latest version, bench: 5845802 |
vondele
changed the title
|
I'm not a chess engine developer, and even if I aspired to contribute to Stockfish, the search algorithm appears to demand a long period of study. But I have been exercising Stockfish 15 as a tester and have encountered the issue as described in this ticket when running depth-limited searches. The evidence I've collected suggests - to me at least - that the cause of runaway search is a TT hash collision. The collision yields a bad value that sends the current iteration on a non-terminating search. (As to the precise reason why search does not terminate I'm too much of a newbie to the search.cpp to say.) My suspicion builds on a line of reasoning that goes like this: My test example is symmetrical Chess960 position recent brought to attention on TalkChess by Larry Christiansen (the "Chess324" subset). The engine is Stockfish 15 with the packaged NNUE. White uses the Classical evaluation function. White searches each move to a fixed depth of 11. Black searches to a fixed depth of 10. Both side run single-threaded. Both sides use a hash size of 512 MB. No opening book. No tablebases. The problematic search occurs on White's 76th move. In the cutechess-cli log: In contrast, with the hash cleared immediately beforehand the comparable search result is: For amusement I hacked search() to print out the values of alpha, beta, and cutNode immediately after entering the function. By eyeball inspection the aspiration window values did not look abnormal compared to the cleared-TT search that completes, except that it continues forever, absent a ctrl-c. I'm thinking one or more cutoffs get mangled from a bad lookup and that this throws search into a non-terminating quest, but I don't know. Other data structures could be in play as culprits too. Excessive quiescence searches and fail-lows? I'm not expert enough to speculate reasonably. P.S. In case you look, you won't find much information on me on github. I made a new account tonight for the sole purpose of posting this small report in hopes that it helps. |
That is fantastic news! Does that test example reproduce under several different commits, or only one commit in particular? |
|
I can't say if incremental changes before and after the version 15 release also trigger the stuck search, but I'd wager that my test case is replicatable only within a small code-change window, including no change to the neural net. The freeze does not happen if I use Stockfish 14 or 13. And ... [one moment while I check ... okay I'm back] ... pulling and compiling the latest (2002-08-20) code does not replicate the problem either. You'll want to debug based off of the official release. It is worth mentioning that I compiled the version of Stockfish 15 locally, as the version of Ubuntu I'm running is behind GLIBC_2.32. The architecture choice (avx2, bmi2, etc.) does not affect the observed behavior. I'll opt for the lazy route and cut & paste my ad-hoc test harness. Usage is:
I make use of the python library "Stockfish". Change the hard-coded path to the binary file, of course. |
This was referenced Sep 4, 2022
|
Another one that halts at low depth with multipv for sf15, if it helps: 6r1/4R1P1/8/8/1P1Bp3/PK1kP3/2r5/8 b - - 0 1 |
|
Since "my" ticket #4110 was merged with this one, hope it's OK I'm commenting here. I played around with the latest SF dev of 17 Sep 2022 (mainly since the eval now is symmetric again, which helps me a lot for analysis but which is not key here). So I decided to have another experiment with this search issue. I again looked at the Pytel-Czech line of TCEC S22 VVLTC game 6. Up to move 17 for Black everything is normal, but this is maybe not surprising since SF now prefers another reply to 17. Qc3 than the tricky Nxa2 line. So the real test came at move 18 for White (r1bq1rk1/p3bppp/2p5/1p2P3/3BN3/2Q4P/nPPN2P1/3R1RK1 w - - 0 18). SF 17Sep22 (2 threads) output 18. Qe3 after 7:53, eval +4.47 (so in particular, the win in this line is now very clear to it), at d=42/76. Then a long wait and I thought it got stuck again, but after 1:22:46 it gave 18. Qe3, eval +4.71, d=43/82. It went on to d=48/94 at 3:31:19 before I called it a day (always 18. Qe3 with similar evals). So a long search as could probably be expected due to the huge seldepth, but it completed correctly! Encouraged, I tried the stalemate puzzle that started this thread. Output below; still SF17Sep22, with 24 threads this time. It zipped past depth 80 in 2h without a hitch. And the deeper you get, the better it realizes the drawishness of this (I assume intended) line. All is as it should be? Or was I just lucky twice in the above? Would be great if others could check their pet examples; I can't do them all, but just maybe SF 17Sep22 represents substantial progress on this issue (for reasons above my pay grade). I have seen issue #4175 (meanwhile closed by its author), but from my own limited experience the latest SF dev is a beast. Let's see what it can do in TCEC S23 Div P. |
|
I'll close this issue, I believe this is fixed in current master To test I collected the FEN's mentioned in this PR (stuck.epd): And ran d30 search on all: |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
No more output after 44.5 minutes. I stopped the search after nearly 6 hours.
1k6/3p4/1B6/4Pp1p/1p5R/1p4p1/pP3n2/K6n w - -
The text was updated successfully, but these errors were encountered: