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?
-
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.– Noah CaplingerJun 24, 2020 at 2:35
-
@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.– user21820Jun 24, 2020 at 6:09
Add a comment
|
1 Answer
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 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.
-
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?– Wins94Jun 24, 2020 at 15:02
-
@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. Jun 24, 2020 at 16:29
-
@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. Jun 24, 2020 at 16:32
-
@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? Jun 24, 2020 at 17:41
-
@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..?– Wins94Jun 24, 2020 at 17:50