About Chess Unwinnability Analyzer 2.0

Chess Unwinnability Analyzer is a free and open-source implementation of a decision procedure for checking whether there exists a sequence of legal moves that allows a certain player to checkmate their opponent in a given chess position.

We will refer to this tool as CHA, which stands for Chess Helpmate Analyzer, an earlier name of this project.

(Although the unwinnability decision algorithm used by CHA is completely original, we use Stockfish as a back end for move generation and chess-related functions.)

What is this useful for?

This tool can be used to rigorously (and automatically) apply Article 6.9 of the FIDE Laws of Chess:

"... if a player does not complete the prescribed number of moves in the allotted time, the game is lost by the player. However, the game is drawn if the position is such that the opponent cannot checkmate the player's king by any possible series of legal moves."

Which in shorter English would read as: "If you run out of time but your opponent can't mate you, it's a draw!"
This is a (relatively unknown) generalization of the folklore rule that says that when you just have the king, you cannot win anymore, not even on the clock.

Easy for humans?

It is usually relatively easy for a human to tell whether a position can be won or not. For example, it is not very hard to realize that no player can deliver checkmate in this position, since the pawn wall is blocked and the bishops are not useful to open it.

Other positions are more involved, for example, in this amazing composition, by Andrew Buchanan (StrateGems 2002) White can checkmate Black (but not vice versa). However, if the pawn on a5 were on a4, neither player would be able to win. Try to understand why!

In over-the-board tournaments, when a player runs out of time, the arbiter can usually check whether the position is unwinnable (for the player who still has time on the clock) and call it a draw if so is the case. But, what happens in online chess? Well, chess servers only perform simple static checks on the position after a timeout and call it a victory if the position is out of the scope of this analysis, unfairly classifying many games.

Hard for machines

The problem of automatically checking that a position cannot be won by a given player is believed to be extremely hard: How can we rule out all sequences of legal moves without actually exploring them?

There exist some attempts that identify "blocked" positions, e.g. this tool Jakob Varmose. However, it does not identify all unwinnable positions. Other attempts are more general, for example, the helpmate solver by Daniel Dugovic can (potentially) identify any unwinnable position, since it performs an exhaustive search on the tree of moves. Nevertheless, such a tool (designed to solve helpmate problems) can hardly be utilized to identify the above positions as unwinnable, since it would be "computationally too expensive", as argued by the author himself.

This tool

CHA can decide unwinnability in all chess positions and is efficient enough to be used by chess servers with a minimal computational overhead.

CHA is designed to be sound, this means that (ignoring possible implementation bugs) CHA will never declare a position as "unwinnable" if the position is indeed winnable.

CHA is also complete (if run without a depth limit), this means that it will always find a helpmate sequence if it exists. CHA performs extremely well in real games, but artificially designed positions can potentially make the analysis reach the default search limit. I challenge you to find a position like this!

Results

We have evaluated CHA 2 over the entire Lichess database of standard rated games, which includes 3,099,534,127 games at the moment. More concretely, we have applied CHA to the final position of all games that ended in a timeout and that were classified as 1-0 or 0-1. This represents a total of 981,467,875 games (about 31% of all games) which have been analyzed in about 88 hours of CPU time (323 μs per position on average).

Our analysis led to identifying a total of 84,100 games that were unfairly classified. Namely, games that were lost by the player who ran out of time, but their opponent could not have checkmated them by any possible sequence of legal moves.

Note that our analysis is definite, i.e., we have identified all the games that were unfairly classified. In all other games, there exists a checkmate sequence for the player who did not run out of time.

We conclude that CHA 2 is ready for practical use. Chess servers could leverage our tool to accurately classify games after a timeout, following the FIDE Laws of Chess.

Full vs Quick version of CHA

In order to minimize the computational impact of running CHA, we propose a less complete, but faster version of our algorithm. Our quick version may terminate without having found a helpmate sequence in complex positions, declaring them as "probably winnable". Consequently, the quick version may fail to find all unwinnable positions. In fact, out of the exact 84,100 games that were unfairly classified (identified with the full version of CHA), the quick version can identify 84,097 of them. Not bad at all!

This means that if we used the quick version of our algorithm to classify games from Lichess after a timeout, there would only be 3 games unfairly classified in the whole database, out of 3 billion+! Actually, these three: FKr42ZRT, bKHPqNEw, f6c1lu7R.
Below, we present a comparison of the performance of the two versions of CHA when analyzing all the timeouts from September 2021. All experiments were performed on a 3.50GHz Intel-Core i9-9900X CPU, running Ubuntu 18.04 LTS.

How does CHA work?

I am planning to add a tutorial on how CHA works to make its core ideas more accessible to everybody. I will not have much free time for this in the near future, so please, bear with me.

There is a lot of room for improvement on optimizing and polishing the code implementation and improving the tool's logic (especially on the criteria for rewarding variations, designed to find helpmates asap when they exist).

If you want to collaborate with me on this project or you have any questions, do not hesitate to contact me: @ambrona