Answers.Body: <p>It is possible, if the computer program has a bug... A position is assigned a win-in-(k+1) only when one move from that leads to a loss-in-k, and assigned a loss-in-k only when every move from that leads to a win-in-k or when k=0 and it is a checkmate. So every correct chess program will never assign a position to win-in-12 and then later revise it to win-in-15 <em>due to &quot;searching deeper&quot;</em>. No heuristic pruning techniques should ever affect this, as heuristic pruning can only weaken the evaluation away from a win/loss (in a correct program).</p>
  <p>However, it is possible that the program is designed to search deeper if the input position satisfies a certain criterion C, in which case it may find a win-in-12 for a given position X that satisfies C, but then one move later the resulting position Y no longer satisfies C and so the program does not search as deep lines as it did for X, and so fails to find a win-in-11 for Y! It may still be able to prove a win-in-15 for Y if it has some rudimentary endgame evaluation. For example, KQK is always a win-in-10, so we do not have to do any search to return win-in-10 in such a position. Thus the program might do a more shallow search for Y and see a KQK in the search tree and immediately return win-in-10, but a deeper search would have revealed that it was actually win-in-5. This can produce the observed effect, but is <em>due to &quot;searching less deep&quot;</em>!</p>
  <p>Note that clicking on &quot;go deeper&quot; on Lichess analysis may not use the same memoization table that had been used before at the lower depth level. One clear example is <a href="https://lichess.org/WosjJ9SV/black#109" rel="nofollow noreferrer">here</a> where the cached analysis states #−30 but if you click &quot;go deeper&quot; it clearly starts completely from scratch. This is expected; after all it makes no sense to store huge tables along with the cached analysis. I think that if you cannot provide an actual concrete example of the behaviour you are asking about, it is difficult to address your hypothetical question more than I already have.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-24T15:02:52.227Z
Answers.Text: So if I understand correctly, you're saying that when an engine reports a mate in N it is because it has analyzed all possible moves that can potentially delay such mate?
Answers.UserDisplayName: Wins94
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-24T16:29:49.043Z
Answers.Text: @Wins94: Indeed, that should be the way chess engines are programmed, since one can hardly gain any speed increase by messing that case up. I have already given the recursive definition for win/loss-in-k, and it should be trivial to see how the values can be propagated up correctly regardless of any heuristics used.
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-24T16:32:19.013Z
Answers.Text: @Wins94: I didn't look at Stockfish's code, but I haven't seen a position where the engine says win-in-k but it was possible for the opponent to delay it for more than k moves. If you have, please show me one.
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-24T17:41:08.780Z
Answers.Text: @user21820, while I don't doubt your claim, I'm unconvinced by "...regardless of any heuristics used." There are plenty of heuristics that disregard certain lines which could potentially disrupt this argument. Could you expand on why you don't think this is the case?
Answers.UserDisplayName: Noah Caplinger
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-24T17:50:12.313Z
Answers.Text: @user21820 What do you mean by "it should be trivial to see how the values can be propagated up correctly". Do you mean k+1, k+2, etc..?
Answers.UserDisplayName: Wins94
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-25T03:16:54.003Z
Answers.Text: @NoahCaplinger: As I said in my other comment to you, heuristics that disregard lines should not return a win/loss-in-k value! Instead, it should return a likely-win/loss value, namely closer to zero than win/loss-in-k but larger in magnitude than any other less certain class of values.
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-25T03:17:34.247Z
Answers.Text: @Wins94: I mean it is a trivial recursion. You need to understand programming and a bit of mathematics if you truly want to grasp how a chess engine is made.
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-25T05:11:12.497Z
Answers.Text: @user21820 Thank you for the insight. In a related question, why does an engine find mate in N moves for position Y after a deep search but when you make it analyze position Y+1 it starts from scratch and doesn't take the analysis done on the previous move. It takes time to calculate the new mate. Shouldn't it return the mate instantly as all possible moves should have been taken into account when it analyzed position Y?
Answers.UserDisplayName: Wins94
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-25T05:27:04.783Z
Answers.Text: @Wins94: Yes that is a good question. If I wrote a chess program, it would indeed do as you said, because it is easy to implement [memoization](https://en.wikipedia.org/wiki/Memoization). I have no idea why some engines do not do that, and appear to "start from scratch". I noticed that on Lichess as well, which made it look a bit silly.
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-25T12:42:39.853Z
Answers.Text: While it is conceivable to me that we chould return a "likely-win/loss value," I've never heard of this, and it seems unlikely to me. In order for an engine to find a mate in 14, say, we would expect to search 30^14 nodes with naive MiniMax, and **with perfect move ordering** (unlikely), alpha/beta could get it down to 30^7 = 21,870,000,000. Engines can only search a few million nodes a second, so whenever you see the computer say M14, it had to throw out lots of lines. Could you perhaps explain how you would circumvent this challenge, or otherwise give a reference to someone that has?
Answers.UserDisplayName: Noah Caplinger
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-25T13:36:43.250Z
Answers.Text: @NoahCaplinger: No it doesn't have to search so many moves. Taking the example in my post, if the chess engine finds that within 4 moves White can reach a KQK position, then it could return correctly win-in-14. Secondly, if from a position X the engine finds a move that results in loss-in-k for the opponent, it doesn't matter if it prunes other possible moves off because evaluating X as win-in-k is correct! Only if it prunes off some moves and of the rest finds that all lead to at most win-in-k, then it would have to return likely-loss-in-k to be correct.
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-25T13:38:37.323Z
Answers.Text: @NoahCaplinger: I am aware that they use memoization for **each** search, but if you had read my comment carefully I was responding to the question about why Lichess appears to evaluate each position **from scratch** even if it is one move after a previous position that it had already evaluated earlier to be win-in-k. Instead of doubting my expertise, you should have asked to clarify...
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-25T14:10:05.043Z
Answers.Text: I'll retract my snarky comment. It was rude and I apologize. It's certainly true that you can return a mate in K if you allow tablebases, but in some sense that's not a "real" mate in K. In a mate in 14 situation where the defending side has many, many possible refutations and none of them are recognized patterns, you are **forced** to traverse a large portion of the tree if you want to give a 100% confident M14. For this reason, I find it unlikely that stockfish doesn't prune away possibly relevant branches when it gives M14. Could you perhaps explain how you would circumvent this challenge?
Answers.UserDisplayName: Noah Caplinger
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-25T14:10:10.707Z
Answers.Text: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/109832/discussion-between-noah-caplinger-and-user21820).
Answers.UserDisplayName: Noah Caplinger
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-25T14:58:14.683Z
Answers.Text: @Wins94: If you're interested in a concrete example of Lichess "looking silly", see [this example I found](https://chat.stackexchange.com/transcript/message/54758903#54758903). =)
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-25T17:25:52.173Z
Answers.Text: Excuse my lack of technical jargon, what was meant by "likely-win/loss value". Doesn't the engine report a Mate in N or a material equivalent +/- score? What is this other "likely-win/lose score"?
Answers.UserDisplayName: Wins94
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-01T16:46:55.993Z
Answers.Text: Did we get a consensus answer to this mystery? I think it is possible to have the engine return mate in 14, for example, to later rectify it to mate in 15 because if I'm not mistaken the engine does not limit mate in N solutions to only lines that have consecutive forced checks.
Answers.UserDisplayName: Wins94
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-01T16:52:34.950Z
Answers.Text: @Wins94: I don't have the time to look into the source code of Lichess. But as I stated, I believe that Lichess "win-in-k" is always correct (i.e. win-in-at-most-k), but it may or may not report a different (but still correct) answer one move later due to different pruning. I have seen this happen quite a few times, and it is never wrong even if it is a bit weird. As I said earlier, you have to show me a position where you actually found Lichess making an erroneous evaluation, before I would change my mind about it.
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-01T16:56:40.877Z
Answers.Text: @user21820 Can you clarify the behavior you're referring to. The behavior I've seen is Lichess reporting mate in 14 and as it moves to a higher level of pruning report mate in 15 only to revert back to mate in 14 or lower after additional pruning. Is that your experience as well?
Answers.UserDisplayName: Wins94
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-01T16:57:59.403Z
Answers.Text: @Wins94: Yes, and there is nothing wrong with that as long as there truly is a mate-in-14 strategy at the point where it claims that. I have never seen an error.
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-01T17:00:00.250Z
Answers.Text: @user21820 That's where my reservation lies. If it reports a mate in 14, it should be after it is 100% confident that there is no other mate that is longer. Wouldn't you agree?
Answers.UserDisplayName: Wins94
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-01T17:01:47.440Z
Answers.Text: @Wins94: That's why I said earlier as well that it wouldn't happen with memoization. But it is obvious that Lichess does *not* use memoization when evaluating the position at different moves. So it isn't surprising if it has other quirks due to the lack of obviously correct optimization techniques. I think you keep confusing between what should be obvious to you and what the (unthinking) Lichess program does. Programs do not have any such thing as "confidence".
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-01T17:57:14.240Z
Answers.Text: @user21820 I got confused when you said it is still reporting a correct answer. By correct it seems you meant it is behaving as it is intended, not necessarily that it is the absolute correct answer. Is that right?
Answers.UserDisplayName: Wins94
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-01T17:59:23.760Z
Answers.Text: My fear is that if the engine is not 100% accurate on the "at-most-k" then a mate can be misreported to the extend where there might not be a forced mate at all.
Answers.UserDisplayName: Wins94
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-02T15:45:32.483Z
Answers.Text: @Wins94: I'm not sure why you keep misreading what I say. I said that the engine **appears to be 100% accurate** because "win-in-k" does **NOT** mean "win in *exactly* k moves against the best opponent strategy"!! If a position is win-in-1 (there is a move to checkmate), it is **also** win-in-2, and an engine would **NOT** be incorrect to claim that.
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-03T17:28:32.633Z
Answers.Text: But why would it report a mate in 2 after reporting a mate 1? Shouldn't the engine have realized it had found a quicker mate at an earlier depth?
Answers.UserDisplayName: Wins94
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-04T13:01:26.843Z
Answers.Text: @Wins94: You are just repeating yourself pointlessly. I have said **many times** now that there is nothing **wrong** about that, and that **you keep confusing between what should be obvious to you and what the (unthinking) Lichess program does**. Until you find an actual Lichess error, do **NOT** ever assume that failing to make an obvious inference implies any error. I moreover already **explained very clearly** in my answer itself HOW such phenomena can arise, but you didn't seem to even attempt to understand that.
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-05T15:18:41.640Z
Answers.Text: @user21820 I don't see how memoization applies in this situation. When you first referenced memoization it was in regards to a different issue (the engine not taking the results of its calculations on position Y into account when analyzing position Y+1). In the issue at hand, the engine does not start from scratch when going from depth X to depth X+1.
Answers.UserDisplayName: Wins94
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-05T15:35:22.890Z
Answers.Text: @Wins94: How do you know it does not start from scratch? In fact, the Lichess behaviour you can observe proves my claim. Let me edit my post to include an indisputable example.
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-05T22:34:13.057Z
Answers.Text: @user21820 Because I've seen the engine evaluate a position from depth Y to Y+1 in 10 seconds and then from Y+1 to Y+2 in another 10 seconds. If it had started from scratch it would be close to cumulative sums and that's clearly not the case.
Answers.UserDisplayName: Wins94
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-06T03:37:32.607Z
Answers.Text: @Wins94: Ok given your last comment, it is clear that you need to find an actual example. I don't feel it is worth the time to discuss it without a concrete example to look at.
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-08T11:46:05.143Z
Answers.Text: An  example of what exactly? The engine reporting mate in N and then N+1 at a later depth?
Answers.UserDisplayName: Wins94
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-09T14:37:31.713Z
Answers.Text: @Wins94: Yes, with the "10 seconds" timing that you claimed in your comment. I don't believe it exists, so I need to actually see it to even be able to guess what is going on.
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-12T10:59:04.150Z
Answers.Text: @Wins94: Just curious to know whether in the past 8 months you ever saw any example of "*The engine reporting mate in N and then N+1 at a later depth*". I still don't believe such a thing exists, because I have still never seen it occur.
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-15T13:41:00.340Z
Answers.Text: @user21820 I thought you said that an engine exhibiting such behavior would still be performing "correctly."
Answers.UserDisplayName: Wins94
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-15T14:30:52.457Z
Answers.Text: @Wins94: Uh? I said "*every correct chess program will never assign a position to win-in-12 and then later revise it to win-in-15 due to "searching deeper"*", and I never changed my mind, because you have never provided a counter-example (so far) despite me asking so many times... =|
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-15T16:09:06.120Z
Answers.Text: @user21820 This is what you said: "If a position is win-in-1 (there is a move to checkmate), it is also win-in-2, and an engine would NOT be incorrect to claim that." That implies for example, that if you run the engine when is the losing side turn to move, the engine will try to optimize the move (delaying mate as much as possible). So in this sense it is conceivable that after searching deeper it finds a better move for the losing side that delays the mate. Would you agree?
Answers.UserDisplayName: Wins94
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-15T16:10:53.920Z
Answers.Text: @Wins94: No. What you just quoted does not contradict what I said, which is about **revising**. No **correct** chess engine will **revise** a win-in-1 to a win-in-2. You are completely wrong in your idea of "optimize the move", and it is obvious if you think carefully; it would be wrong to claim win-in-1 *at first* if it couldn't prove it. I strongly suggest you actually read up and understand negamax and how exactly the engine assigns win-in-k and lose-in-k values.
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-15T16:23:10.370Z
Answers.Text: @Wins94: Anyway, let me sum up again. Like I mentioned in my actual post, it is possible if the engine **throws away** what it knows and recalculates with a different depth parameter, but that is not a revision! Once a subtree is found that proves win-in-1, any correct engine will never within the same run throw away that subtree and end up with a worse bound like win-in-2.
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-15T16:29:33.210Z
Answers.Text: When you say "worse", it is worse for the side that will mate but actually better for the side that will be mated as it will delay it.
Answers.UserDisplayName: Wins94
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-15T16:30:20.037Z
Answers.Text: @Wins94: Look, your last comments show that you don't actually understand negamax and assignment of win/loss-in-k values. If you want to learn, don't keep assuming you know what is happening.
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-15T16:33:00.953Z
Answers.Text: @user21820 That is why I asked the question in the first place, because I did not know the answer. In other words, my question was asking if Mate in N are proven (after the engine exhausted all possible moves leading to the mate). It is not the case in other analyses such as when the engine evaluates the position to a draw to then revise it.
Answers.UserDisplayName: Wins94
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-15T16:51:36.253Z
Answers.Text: @Wins94: In theory, I already explained adequately in my first paragraph, but you don't seem to get it, so you need to read up. A correct engine that sees 1 move to checkmate will evaluate it as win-in-1, *as per my first paragraph*, and **will never revise it to win-in-2** because win-in-1 is strictly better. It is the same for win-in-2; if it has a move to P with value loss-in-1, it means that it checked **every** move from P and found it to lead to win-in-1, so it again **will never revise it** to win-in->2 (within the same run).
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-15T17:28:08.367Z
Answers.Text: @user21820 Thank you for your insight.  I trust your knowledge on the matter so will consider my question answered.
Answers.UserDisplayName: Wins94
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-24T06:06:54.963Z
Answers.LastActivityDate: 2021-03-05T15:46:54.370Z
Answers.LastEditDate: 2021-03-05T15:46:54.370Z
Answers.UserDisplayName: user21820
Body: <p>Is it possible to have the computer analysis report mate in 12 moves to only change that to mate in higher number of moves, like 15 for example, after it searches deeper?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-24T02:35:41.833Z
Comments.Text: The standard answer is that no, this is not possible. I was about to write out an answer to this effect before hitting some complications regarding LMR/other selectivity techniques---it's conceivable that the computer could miss a line due to LMR or null move stuff for instance. It is also possible that the best engines account for this by turning off all reductions if it finds a mate to verify it is indeed a mate. This probabally isn't the level at which @Wins94 asked this question, but I would be curious if anyone could shed some light on this point.
Comments.UserDisplayName: Noah Caplinger
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-24T06:09:45.710Z
Comments.Text: @NoahCaplinger: LMR cannot change the win/loss scores. As for the null move heuristic, if the program gets the wrong mate-length due to that, then I would consider the program to be incorrect, because it is trivial to assign a large value instead of a mate-in-k value.
Comments.UserDisplayName: user21820
Tags: <engines><analysis><stockfish>
Title: Mate In N algorithm-Lichess Computer Analysis
ThreadText: # Mate In N algorithm-Lichess Computer Analysis
  
  (Asked by: username_0 on 2020-06-24)
  
  Is it possible to have the computer analysis report mate in 12 moves to only change that to mate in higher number of moves, like 15 for example, after it searches deeper?
  
  **Tags:** engines, analysis, stockfish
  
  > **Comments:**
  > **username_1**: The standard answer is that no, this is not possible. I was about to write out an answer to this effect before hitting some complications regarding LMR/other selectivity techniques---it's conceivable that the computer could miss a line due to LMR or null move stuff for instance. It is also possible that the best engines account for this by turning off all reductions if it finds a mate to verify it is indeed a mate. This probabally isn't the level at which @username_0 asked this question, but I would be curious if anyone could shed some light on this point.  
  > **username_2**: @NoahCaplinger: LMR cannot change the win/loss scores. As for the null move heuristic, if the program gets the wrong mate-length due to that, then I would consider the program to be incorrect, because it is trivial to assign a large value instead of a mate-in-k value.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2020-06-24. Score: 1
  
  It is possible, if the computer program has a bug... A position is assigned a win-in-(k+1) only when one move from that leads to a loss-in-k, and assigned a loss-in-k only when every move from that leads to a win-in-k or when k=0 and it is a checkmate. So every correct chess program will never assign a position to win-in-12 and then later revise it to win-in-15 *due to "searching deeper"*. No heuristic pruning techniques should ever affect this, as heuristic pruning can only weaken the evaluation away from a win/loss (in a correct program).
  
  However, it is possible that the program is designed to search deeper if the input position satisfies a certain criterion C, in which case it may find a win-in-12 for a given position X that satisfies C, but then one move later the resulting position Y no longer satisfies C and so the program does not search as deep lines as it did for X, and so fails to find a win-in-11 for Y! It may still be able to prove a win-in-15 for Y if it has some rudimentary endgame evaluation. For example, KQK is always a win-in-10, so we do not have to do any search to return win-in-10 in such a position. Thus the program might do a more shallow search for Y and see a KQK in the search tree and immediately return win-in-10, but a deeper search would have revealed that it was actually win-in-5. This can produce the observed effect, but is *due to "searching less deep"*!
  
  Note that clicking on "go deeper" on Lichess analysis may not use the same memoization table that had been used before at the lower depth level. One clear example is [here](https://lichess.org/WosjJ9SV/black#109) where the cached analysis states #−30 but if you click "go deeper" it clearly starts completely from scratch. This is expected; after all it makes no sense to store huge tables along with the cached analysis. I think that if you cannot provide an actual concrete example of the behaviour you are asking about, it is difficult to address your hypothetical question more than I already have.
  
  > **Comments:**
  > **username_0**: So if I understand correctly, you're saying that when an engine reports a mate in N it is because it has analyzed all possible moves that can potentially delay such mate?  
  > **username_2**: @username_0: Indeed, that should be the way chess engines are programmed, since one can hardly gain any speed increase by messing that case up. I have already given the recursive definition for win/loss-in-k, and it should be trivial to see how the values can be propagated up correctly regardless of any heuristics used.  
  > **username_2**: @username_0: I didn't look at Stockfish's code, but I haven't seen a position where the engine says win-in-k but it was possible for the opponent to delay it for more than k moves. If you have, please show me one.  
  > **username_1**: @username_2, while I don't doubt your claim, I'm unconvinced by "...regardless of any heuristics used." There are plenty of heuristics that disregard certain lines which could potentially disrupt this argument. Could you expand on why you don't think this is the case?  
  > **username_0**: @username_2 What do you mean by "it should be trivial to see how the values can be propagated up correctly". Do you mean k+1, k+2, etc..?  
  > **username_2**: @NoahCaplinger: As I said in my other comment to you, heuristics that disregard lines should not return a win/loss-in-k value! Instead, it should return a likely-win/loss value, namely closer to zero than win/loss-in-k but larger in magnitude than any other less certain class of values.  
  > **username_2**: @username_0: I mean it is a trivial recursion. You need to understand programming and a bit of mathematics if you truly want to grasp how a chess engine is made.  
  > **username_0**: @username_2 Thank you for the insight. In a related question, why does an engine find mate in N moves for position Y after a deep search but when you make it analyze position Y+1 it starts from scratch and doesn't take the analysis done on the previous move. It takes time to calculate the new mate. Shouldn't it return the mate instantly as all possible moves should have been taken into account when it analyzed position Y?  
  > **username_2**: @username_0: Yes that is a good question. If I wrote a chess program, it would indeed do as you said, because it is easy to implement [memoization](https://en.wikipedia.org/wiki/Memoization). I have no idea why some engines do not do that, and appear to "start from scratch". I noticed that on Lichess as well, which made it look a bit silly.  
  > **username_1**: While it is conceivable to me that we chould return a "likely-win/loss value," I've never heard of this, and it seems unlikely to me. In order for an engine to find a mate in 14, say, we would expect to search 30^14 nodes with naive MiniMax, and **with perfect move ordering** (unlikely), alpha/beta could get it down to 30^7 = 21,870,000,000. Engines can only search a few million nodes a second, so whenever you see the computer say M14, it had to throw out lots of lines. Could you perhaps explain how you would circumvent this challenge, or otherwise give a reference to someone that has?  
  > **username_2**: @NoahCaplinger: No it doesn't have to search so many moves. Taking the example in my post, if the chess engine finds that within 4 moves White can reach a KQK position, then it could return correctly win-in-14. Secondly, if from a position X the engine finds a move that results in loss-in-k for the opponent, it doesn't matter if it prunes other possible moves off because evaluating X as win-in-k is correct! Only if it prunes off some moves and of the rest finds that all lead to at most win-in-k, then it would have to return likely-loss-in-k to be correct.  
  > **username_2**: @NoahCaplinger: I am aware that they use memoization for **each** search, but if you had read my comment carefully I was responding to the question about why Lichess appears to evaluate each position **from scratch** even if it is one move after a previous position that it had already evaluated earlier to be win-in-k. Instead of doubting my expertise, you should have asked to clarify...  
  > **username_1**: I'll retract my snarky comment. It was rude and I apologize. It's certainly true that you can return a mate in K if you allow tablebases, but in some sense that's not a "real" mate in K. In a mate in 14 situation where the defending side has many, many possible refutations and none of them are recognized patterns, you are **forced** to traverse a large portion of the tree if you want to give a 100% confident M14. For this reason, I find it unlikely that stockfish doesn't prune away possibly relevant branches when it gives M14. Could you perhaps explain how you would circumvent this challenge?  
  > **username_1**: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/109832/discussion-between-noah-caplinger-and-username_2).  
  > **username_2**: @username_0: If you're interested in a concrete example of Lichess "looking silly", see [this example I found](https://chat.stackexchange.com/transcript/message/54758903#54758903). =)  
  > **username_0**: Excuse my lack of technical jargon, what was meant by "likely-win/loss value". Doesn't the engine report a Mate in N or a material equivalent +/- score? What is this other "likely-win/lose score"?  
  > **username_0**: Did we get a consensus answer to this mystery? I think it is possible to have the engine return mate in 14, for example, to later rectify it to mate in 15 because if I'm not mistaken the engine does not limit mate in N solutions to only lines that have consecutive forced checks.  
  > **username_2**: @username_0: I don't have the time to look into the source code of Lichess. But as I stated, I believe that Lichess "win-in-k" is always correct (i.e. win-in-at-most-k), but it may or may not report a different (but still correct) answer one move later due to different pruning. I have seen this happen quite a few times, and it is never wrong even if it is a bit weird. As I said earlier, you have to show me a position where you actually found Lichess making an erroneous evaluation, before I would change my mind about it.  
  > **username_0**: @username_2 Can you clarify the behavior you're referring to. The behavior I've seen is Lichess reporting mate in 14 and as it moves to a higher level of pruning report mate in 15 only to revert back to mate in 14 or lower after additional pruning. Is that your experience as well?  
  > **username_2**: @username_0: Yes, and there is nothing wrong with that as long as there truly is a mate-in-14 strategy at the point where it claims that. I have never seen an error.  
  > **username_0**: @username_2 That's where my reservation lies. If it reports a mate in 14, it should be after it is 100% confident that there is no other mate that is longer. Wouldn't you agree?  
  > **username_2**: @username_0: That's why I said earlier as well that it wouldn't happen with memoization. But it is obvious that Lichess does *not* use memoization when evaluating the position at different moves. So it isn't surprising if it has other quirks due to the lack of obviously correct optimization techniques. I think you keep confusing between what should be obvious to you and what the (unthinking) Lichess program does. Programs do not have any such thing as "confidence".  
  > **username_0**: @username_2 I got confused when you said it is still reporting a correct answer. By correct it seems you meant it is behaving as it is intended, not necessarily that it is the absolute correct answer. Is that right?  
  > **username_0**: My fear is that if the engine is not 100% accurate on the "at-most-k" then a mate can be misreported to the extend where there might not be a forced mate at all.  
  > **username_2**: @username_0: I'm not sure why you keep misreading what I say. I said that the engine **appears to be 100% accurate** because "win-in-k" does **NOT** mean "win in *exactly* k moves against the best opponent strategy"!! If a position is win-in-1 (there is a move to checkmate), it is **also** win-in-2, and an engine would **NOT** be incorrect to claim that.  
  > **username_0**: But why would it report a mate in 2 after reporting a mate 1? Shouldn't the engine have realized it had found a quicker mate at an earlier depth?  
  > **username_2**: @username_0: You are just repeating yourself pointlessly. I have said **many times** now that there is nothing **wrong** about that, and that **you keep confusing between what should be obvious to you and what the (unthinking) Lichess program does**. Until you find an actual Lichess error, do **NOT** ever assume that failing to make an obvious inference implies any error. I moreover already **explained very clearly** in my answer itself HOW such phenomena can arise, but you didn't seem to even attempt to understand that.  
  > **username_0**: @username_2 I don't see how memoization applies in this situation. When you first referenced memoization it was in regards to a different issue (the engine not taking the results of its calculations on position Y into account when analyzing position Y+1). In the issue at hand, the engine does not start from scratch when going from depth X to depth X+1.  
  > **username_2**: @username_0: How do you know it does not start from scratch? In fact, the Lichess behaviour you can observe proves my claim. Let me edit my post to include an indisputable example.  
  > **username_0**: @username_2 Because I've seen the engine evaluate a position from depth Y to Y+1 in 10 seconds and then from Y+1 to Y+2 in another 10 seconds. If it had started from scratch it would be close to cumulative sums and that's clearly not the case.  
  > **username_2**: @username_0: Ok given your last comment, it is clear that you need to find an actual example. I don't feel it is worth the time to discuss it without a concrete example to look at.  
  > **username_0**: An  example of what exactly? The engine reporting mate in N and then N+1 at a later depth?  
  > **username_2**: @username_0: Yes, with the "10 seconds" timing that you claimed in your comment. I don't believe it exists, so I need to actually see it to even be able to guess what is going on.  
  > **username_2**: @username_0: Just curious to know whether in the past 8 months you ever saw any example of "*The engine reporting mate in N and then N+1 at a later depth*". I still don't believe such a thing exists, because I have still never seen it occur.  
  > **username_0**: @username_2 I thought you said that an engine exhibiting such behavior would still be performing "correctly."  
  > **username_2**: @username_0: Uh? I said "*every correct chess program will never assign a position to win-in-12 and then later revise it to win-in-15 due to "searching deeper"*", and I never changed my mind, because you have never provided a counter-example (so far) despite me asking so many times... =|  
  > **username_0**: @username_2 This is what you said: "If a position is win-in-1 (there is a move to checkmate), it is also win-in-2, and an engine would NOT be incorrect to claim that." That implies for example, that if you run the engine when is the losing side turn to move, the engine will try to optimize the move (delaying mate as much as possible). So in this sense it is conceivable that after searching deeper it finds a better move for the losing side that delays the mate. Would you agree?  
  > **username_2**: @username_0: No. What you just quoted does not contradict what I said, which is about **revising**. No **correct** chess engine will **revise** a win-in-1 to a win-in-2. You are completely wrong in your idea of "optimize the move", and it is obvious if you think carefully; it would be wrong to claim win-in-1 *at first* if it couldn't prove it. I strongly suggest you actually read up and understand negamax and how exactly the engine assigns win-in-k and lose-in-k values.  
  > **username_2**: @username_0: Anyway, let me sum up again. Like I mentioned in my actual post, it is possible if the engine **throws away** what it knows and recalculates with a different depth parameter, but that is not a revision! Once a subtree is found that proves win-in-1, any correct engine will never within the same run throw away that subtree and end up with a worse bound like win-in-2.  
  > **username_0**: When you say "worse", it is worse for the side that will mate but actually better for the side that will be mated as it will delay it.  
  > **username_2**: @username_0: Look, your last comments show that you don't actually understand negamax and assignment of win/loss-in-k values. If you want to learn, don't keep assuming you know what is happening.  
  > **username_0**: @username_2 That is why I asked the question in the first place, because I did not know the answer. In other words, my question was asking if Mate in N are proven (after the engine exhausted all possible moves leading to the mate). It is not the case in other analyses such as when the engine evaluates the position to a draw to then revise it.  
  > **username_2**: @username_0: In theory, I already explained adequately in my first paragraph, but you don't seem to get it, so you need to read up. A correct engine that sees 1 move to checkmate will evaluate it as win-in-1, *as per my first paragraph*, and **will never revise it to win-in-2** because win-in-1 is strictly better. It is the same for win-in-2; if it has a move to P with value loss-in-1, it means that it checked **every** move from P and found it to lead to win-in-1, so it again **will never revise it** to win-in->2 (within the same run).  
  > **username_0**: @username_2 Thank you for your insight.  I trust your knowledge on the matter so will consider my question answered.  
  
  ---
  
  