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 the game if 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!
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 3 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.
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.
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.
An example is the following (dead) position if we added several more black bishops on dark-squares.
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 3,277,874,614 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 1,038,558,007 games (about 31% of all games) which have been analyzed in about 104 hours of CPU time (361 μs per position on average).
Our analysis led to identifying a total of 88,387 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.
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 88,837 games that were unfairly classified (identified with the full version of CHA), the quick version can identify 88,834 of them!