CHA 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 can be used to automatically deciding whether a game should be lost or drawn after a player runs out of time. According to 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."
In a nutshell:
"If you run out of time but your opponent can't mate you, it's a draw!"
It can also be used to correctly applying Article 5.2.2 of the FIDE Laws, which establishes that a game is finished as soon as the position becomes dead, i.e. unwinnable for both players, and no more moves should be played.
Our tool combines a search of variations (enhanced with a transposition table and heuristics for selecting what moves to explore first) with a static analysis that can identify unwinnable positions without exploring game variations.
For a more detailed explanation of how this tool works, checkout our white paper, which has been published in the peer-reviewed 11th International Conference on Fun with Algorithms!
Our implementation uses the source code of the Stockfish chess engine as a back end for move generation and chess-related functions.
You can try CHA interactively without installation from our analyzer section, where you can edit and analyze any position of your choice.
Have a look at our list of examples and try to determine whether or not players can checkmate their opponent in each of them!
You can also run our tool locally by downloading our source code.
The problem of determining whether or not a given chess position is unwinnable for a certain player has been considered intractable by the community and, consequently, chess servers do not apply the above rule rigorously, thus unfairly classifying many games.
Indeed, chess unwinnability for an appropriate generalization of chess over an n × n board was proven to be PSPACE-complete. This evidences the hardness of the problem that we are facing, but it does not mean we cannot solve it over a fixed-size board of 8 × 8.
See our white paper for a discussion on how chess servers adjudicate timeouts and other related works.
After analyzing with CHA all the games from the Lichess Open Database (containing more than 5 billion games), we successfully identified all the unfairly classified games from the database, which we list here.
Chess servers (and chess software) can leverage CHA (and are invited to do so) to accurately classify games after a timeout, following Article 6.9 of the FIDE Laws of Chess.
The Lichess Team is aware of this project and there is a relevant issue on the GitHub Lichess repository.
These things take time, CHA's source code would need to be audited and the Lichess developers would need to find the best way to integrate it.
Hopefully, our recent white paper will help the cause. There, we describe our algorithm in detail and formally prove that it is sound.
This is a new feature! Here you can consult if your username appears in any of the unfairly classified games on the Lichess Database.
This is intended for curiosity purposes only. Understand that you will not be refunded rating points for any of those games.
It means that there exists no sequence of legal moves that ends in a checkmate by Black. In other words, that the tree of variations does not contain a single leaf where Black wins the game.
Note that CHA may arrive to that conclusion without exhaustively examining the whole tree thanks to our static analysis.
CHA is sound, it will never declare a position as "unwinnable" if the position is indeed winnable.
Not yet! Although it has solved all positions corresponding to actual games from the Lichess Open Database, there exist very artificial positions that would potentially require a large amount of time to be solved by CHA.
Of course! If you want to collaborate, do not hesitate to contact me: @ambrona.
There is a lot of room for improvement on efficiency and simplicity of our implementation. And I have fresh ideas to make the tool efficiently complete. Capturing any position, even the most artificial ones, would be great!
CHA stands for Chess Helpmate Analyzer.
We have evaluated CHA over the entire Lichess Open Database of standard rated games, which includes more than 5 billion games to date (January 2024). 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.
Our analysis led to identifying a total of 136,416 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.