-
Notifications
You must be signed in to change notification settings - Fork 5
🐛 Avoid aspiration windows after a checkmate has been detected in the search #1057
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Merged
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
eduherminio
added a commit
that referenced
this pull request
Sep 27, 2024
…Constants.MinEval` Distance `MinEval` from `-CheckMateBaseEvaluation` enough so that there's no possible interference between them at TT level. Now I reaaaally want to change `EvaluationConstants.CheckmateDepthFactor` to 1, but now it's not the time. Logs seen when saving an item to a TT. ``` RecordHash: for position "6k1/4b1p1/8/4P3/8/q7/6r1/2K5 w - - 0 1", with raw score -29865, saving -30085 from TT RecordHash: for position "6k1/4b1p1/8/4P3/6r1/1q6/8/1K6 w - - 0 1", with raw score -29865, saving -30085 from TT ``` Logs seen when retrieving that item from TT, ending up with a score < `EvaluationConstants.MinEval` (-30001). ``` ProbeHash: for position "6k1/4b1p1/8/4P3/8/q7/6r1/2K5 w - - 0 1", with raw score -30085, returning -30005 from TT. Alpha -29921^, Beta -29920, Type "Alpha", Recalculated score -30005 Returning -30005 from TT at depth 0, ply 8 Full search in first visited move returned -30005 ``` This which eventually causes some NegaMax calls to use that value and return it, which ends up in the situation where other shallower NegaMax instances have a bestScore that never bets beaten in the fail-soft version of alphabeta, eventually causing an empty PV and a crash due to `a8a8` move Logs produced using b8f23b9, from [bugfix/no-pruning-negative-checkmate-score-debugging](https://github.com/lynx-chess/Lynx/tree/bugfix/no-pruning-negative-checkmate-score-debugging) (#1062) ----- Code-flow explanation, dumbed for future me: - The negative checkmate scores issue was already there since.. forever If `bestScore` is `EvaluationContants.MinEval`, the double invocations to `TranspositionTableExtensions.RecalculateMateScores` on saving an entry and on retrieving it lead the resulting score to be lower than `EvaluationContants.MinEval`. - While adopting fail soft, I directly jumped into the nested implementation: ```csharp if (score > bestScore) { bestScore = score; if (score >= beta) { /* ... */} } if (score > alpha) { /* ... */} } } ``` vs the option of checking `alpha` and `beta` outside of the `if (score > bestScore` conditional. This implies that if the returned `score` is ever lower than `bestScore`, which gets initialized to `EvaluationContants.MinEval`, there's never a fail low node that beats alpha, that is there's no move beating the 'no move', so there's no PV populated. - This leads to the issue in Aspiration windows implementation of the IDDFS:` ```csharp while (true) { bestScore = NegaMax(depth: depth, ply: 0, alpha, beta); window += window >> 1; // window / 2 if (alpha >= bestScore) // Fail low { alpha = Math.Max(bestScore - window, EvaluationConstants.MinEval); beta = (alpha + beta) >> 1; // (alpha + beta) / 2 } else if (beta <= bestScore) // Fail high beta = Math.Min(bestScore + window, EvaluationConstants.MaxEval); else break; } ``` In our case, `bestScore` is lower than `EvaluationConstants.MinEval` but `alpha` is restricted to [minEval, ...), so alpha always beats `bestScore`. Given that, we end up in the situation described in #1057 (but not fixed): an infinite Aspiration windows loop where stuff overflows due to the window variable growing indefinitely, variables start to overflow and a cancellation with still no PV ends up happening ```log Lynx.Engine|Eval (-30001) (depth 8, nodes 84) outside of aspiration window, new window [-30001, -29995] Lynx.Engine|Eval (-30001) (depth 8, nodes 168) outside of aspiration window, new window [-30001, -29998] Lynx.Engine|Eval (-30001) (depth 8, nodes 252) outside of aspiration window, new window [-30001, -30000] Lynx.Engine|Eval (-29980) (depth 8, nodes 309) outside of aspiration window, new window [-30001, -29917] Lynx.Engine|Eval (-30001) (depth 8, nodes 399) outside of aspiration window, new window [-30001, -29959] Lynx.Engine|Eval (-30001) (depth 8, nodes 483) outside of aspiration window, new window [-30001, -29980] Lynx.Engine|Eval (-30001) (depth 8, nodes 567) outside of aspiration window, new window [-30001, -29991] Lynx.Engine|Eval (-30001) (depth 8, nodes 651) outside of aspiration window, new window [-30001, -29996] Lynx.Engine|Eval (-30001) (depth 8, nodes 735) outside of aspiration window, new window [-30001, -29999] Lynx.Engine|Eval (-30001) (depth 8, nodes 819) outside of aspiration window, new window [-30001, -30000] Lynx.Engine|Eval (-29980) (depth 8, nodes 854) outside of aspiration window, new window [-30001, -28914] Lynx.Engine|Eval (-30001) (depth 8, nodes 940) outside of aspiration window, new window [-30001, -29458] Lynx.Engine|Eval (-30001) (depth 8, nodes 1026) outside of aspiration window, new window [-30001, -29730] Lynx.Engine|Eval (-30001) (depth 8, nodes 1112) outside of aspiration window, new window [-30001, -29866] Lynx.Engine|Eval (-30001) (depth 8, nodes 1198) outside of aspiration window, new window [-30001, -29934] Lynx.Engine|Eval (-30001) (depth 8, nodes 1282) outside of aspiration window, new window [-30001, -29968] Lynx.Engine|Eval (-30001) (depth 8, nodes 1366) outside of aspiration window, new window [-30001, -29985] Lynx.Engine|Eval (-30001) (depth 8, nodes 1450) outside of aspiration window, new window [-30001, -29993] Lynx.Engine|Eval (-30001) (depth 8, nodes 1534) outside of aspiration window, new window [-30001, -29997] Lynx.Engine|Eval (-30001) (depth 8, nodes 1618) outside of aspiration window, new window [-30001, -29999] .... Lynx.Engine|Eval (-29980) (depth 8, nodes 3052) outside of aspiration window, new window [-30001, 30001] Lynx.Engine|Eval (-30001) (depth 8, nodes 3138) outside of aspiration window, new window [-30001, 0] Lynx.Engine|Eval (-30001) (depth 8, nodes 3224) outside of aspiration window, new window [-30001, -15001] Lynx.Engine|Eval (-30001) (depth 8, nodes 3310) outside of aspiration window, new window [-30001, -22501] Lynx.Engine|Eval (-30001) (depth 8, nodes 3396) outside of aspiration window, new window [-30001, -26251] Lynx.Engine|Eval (-30001) (depth 8, nodes 3482) outside of aspiration window, new window [-30001, -28126] Lynx.Engine|Eval (-30001) (depth 8, nodes 3568) outside of aspiration window, new window [-30001, -29064] Lynx.Engine|Eval (-30001) (depth 8, nodes 3654) outside of aspiration window, new window [-30001, -29533] Lynx.Engine|Eval (-30001) (depth 8, nodes 3740) outside of aspiration window, new window [-30001, -29767] Lynx.Engine|Eval (-30001) (depth 8, nodes 3826) outside of aspiration window, new window [1967549553, 983759893] Lynx.Engine|Eval (-29960) (depth 8, nodes 3828) outside of aspiration window, new window [-30001, 491864946] Lynx.Engine|Eval (-30001) (depth 8, nodes 3914) outside of aspiration window, new window [-30001, 245917472] Lynx.Engine|Eval (-30001) (depth 8, nodes 4000) outside of aspiration window, new window [1271841875, 758879673] Lynx.Engine|Eval (-29960) (depth 8, nodes 4002) outside of aspiration window, new window [1907777854, -814154885] Lynx.Engine|Eval (-29920) (depth 8, nodes 4010) outside of aspiration window, new window [-30001, -407092443] Lynx.Engine|Eval (-29960) (depth 8, nodes 4018) outside of aspiration window, new window [-30001, -2145113894] Lynx.Engine|Eval (-29960) (depth 8, nodes 4026) outside of aspiration window, new window [-30001, 30001] Lynx.Engine|Eval (-30001) (depth 8, nodes 4112) outside of aspiration window, new window [-30001, 0] Lynx.Engine|Eval (-30001) (depth 8, nodes 4198) outside of aspiration window, new window [1870919157, 935459578] Lynx.Engine|Eval (-29960) (depth 8, nodes 4200) outside of aspiration window, new window [-30001, 467714788] ... Search cancellation requested after 625ms (depth 8, nodes 963346), best move will be returned [Lynx] info depth 7 seldepth 13 multipv 1 score cp -30001 nodes 963346 nps 592828 time 625 hashfull 78 pv [Lynx] bestmove a8a8 ```
eduherminio
added a commit
that referenced
this pull request
Sep 28, 2024
This effectively reverts #1057 It turns out that without resetting alpha and beta, we also get empty PVs, but this time on winning positions when getting close to 50mr after not having been able to convert
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Problem to tackle: infinite aspirations windows search reaching a state as ridiculous as the followig;
Having search results with cp -30001 may or may not be consequence of this, will see later
(spoiler, it of course didn't, see crash in https://openbench.lynx-chess.com/test/771/ )