Skip to content

Conversation

eduherminio
Copy link
Member

@eduherminio eduherminio commented Sep 24, 2024

Problem to tackle: infinite aspirations windows search reaching a state as ridiculous as the followig;

Lynx.Cli.Writer|[Lynx]	info depth 1 seldepth 1 multipv 1 score cp -1319 nodes 5 nps 5 time 0 pv g2h3 
Lynx.Engine|Depth 2: mate in -5 detected (50 moves until draw by repetition) 
Lynx.Engine|Stopping search: mate is short enough 
Lynx.Cli.Writer|[Lynx]	info depth 2 seldepth 3 multipv 1 score mate -5 nodes 48 nps 48 time 0 hashfull 104 pv g2h3 e3e2 
Lynx.Cli.Writer|[Lynx]	info depth 2 seldepth 3 multipv 1 score mate -5 nodes 48 nps 48 time 0 hashfull 104 pv g2h3 e3e2 
Lynx.Cli.Writer|[Lynx]	bestmove g2h3 ponder e3e2 
Lynx.Cli.Program|[GUI]	position fen rnbqk1nr/pp3p2/3pp1p1/1N2b2p/4PB2/3B4/PPP2PPP/RN1Q1RK1 w kq - 0 1 moves f4e5 d6e5 a2a4 a7a6 b5a3 b8c6 a3c4 e8f8 d1d2 h5h4 h2h3 f8g7 d2c3 f7f6 a4a5 c6d4 b1d2 a8b8 d2b3 g6g5 f1d1 g8e7 c4b6 d4b3 c3b3 d8c7 d3c4 e7c6 c2c3 h8e8 d1d3 e8d8 d3d8 c6d8 a1d1 d8c6 b3a3 g7f7 c4e2 f7g7 e2h5 g5g4 h3g4 f6f5 e4f5 c7e7 a3e7 c6e7 d1d8 e6f5 g4f5 e5e4 d8e8 e7f5 b6c8 e4e3 f2e3 f5e3 c8d6 b8e8 d6e8 g7h6 h5e2 h6g5 e8d6 h4h3 g2h3 g5h4 g1f2 e3d5 d6b7 h4h3 b7c5 h3h2 e2a6 d5f4 a6b7 f4h3 f2e3 h2g1 c5e4 g1g2 a5a6 h3g5 e4g5 g2g3 g5e4 g3h3 a6a7 h3g2 a7a8q g2h3 a8g8 
Lynx.Cli.Program|Position parsing took 0ms 
Lynx.Cli.Program|[GUI]	isready 
Lynx.Cli.Writer|[Lynx]	readyok 
Lynx.Cli.Program|[GUI]	go wtime 2421 btime 1439 winc 80 binc 80 
Lynx.Engine|Soft time bound: 0.10200000000000001s 
Lynx.Engine|Hard time bound: 0.722s 
Lynx.Cli.Writer|[Lynx]	info depth 1 seldepth 1 multipv 1 score cp -1296 nodes 2 nps 2 time 0 pv h3h2 
Lynx.Cli.Writer|[Lynx]	info depth 2 seldepth 3 multipv 1 score cp -1346 nodes 49 nps 49 time 0 pv h3h2 g8g4 
Lynx.Cli.Writer|[Lynx]	info depth 3 seldepth 5 multipv 1 score cp -1377 nodes 147 nps 147 time 0 pv h3h2 g8g4 h2h1 
Lynx.Cli.Writer|[Lynx]	info depth 4 seldepth 5 multipv 1 score cp -30001 nodes 11 nps 11 time 0 pv  
Lynx.Cli.Writer|[Lynx]	info depth 5 seldepth 7 multipv 1 score cp -30001 nodes 50 nps 50 time 0 pv  
Lynx.Cli.Writer|[Lynx]	info depth 6 seldepth 8 multipv 1 score cp -30001 nodes 87 nps 87 time 0 pv  
Lynx.Cli.Writer|[Lynx]	info depth 7 seldepth 8 multipv 1 score cp -30001 nodes 91 nps 91 time 0 pv  
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]
....

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/ )

@eduherminio eduherminio marked this pull request as ready for review September 24, 2024 23:58
@eduherminio eduherminio merged commit d051082 into main Sep 24, 2024
27 checks passed
@eduherminio eduherminio deleted the bugfix/no-asp-when-mate-detected branch September 24, 2024 23:58
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
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

1 participant