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.)
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.
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!
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.
CHA can decide unwinnability in all chess positions and is efficient enough to be used by chess servers with a minimal computational overhead.
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.
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.
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!
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
