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.
This tool uses Stockfish as a back end for move generation and chess-related functions.
Due to an early name of this repository, we will refer to this tool as CHA, which stands for Chess Helpmate Analyzer.
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.
In over-the-board tournaments, when a player runs out of time, the arbiter can 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.
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 2.0 can decide unwinnability in all chess positions and is efficient enough to be used by chess servers with a minimal computational overhead.
CHA 2.0 is designed to be sound, this means that (ignoring possible implementation bugs) CHA 2.0 will never declare a position as "unwinnable" if the position is indeed winnable.
CHA 2.0 is also complete (if run without a depth limit), this means that it will always find a helpmate sequence if it exists. However, it may require a prohibitive amount of time to perform the analysis on some positions. The good news is that I do not know (yet) of any position (reachable from the starting position) that cannot be solved by CHA 2.0 running with its default depth limit (which enforces termination after a few seconds on a modern processor).
Running CHA 2.0 on the final position of a test set of 5 million games from the Lichess game database (that were won on time by one of the players) led to identifying 321 of them which were unfairly classified (they should have ended in a draw). The tool required an average of 296 μs per position (and never more than 4 ms) running on a personal laptop, with processor Intel Core i7 of 10th generation.
Observe that over 99.92% of the positions were analyzed in less than 1.5 ms. These numbers make it completely feasible for an online chess server to run this test on every game that ends in a timeout. Or even after every single move during the game, to end the game immediately if a dead draw is detected (rigorously applying Article 6.9 of the FIDE Laws of Chess).
I am planning to add a tutorial on how CHA 2.0 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
