The algorithm
How CHA-Solver works
CHA-Solver is a free, open-source chess helpmate solver and unwinnability detector. Given a position and an intended winner, it either finds a helpmate (a sequence of legal moves ending in a checkmate delivered by that player) or proves, with mathematical certainty, that no such sequence exists.
It was built to address a fairness problem in competitive chess: under FIDE Article 6.9, a timeout should result in a draw, not a loss, when the opponent has no legal path to checkmate. CHA-Solver also handles Article 5.2.2 , a game is over as soon as a dead position arises (a position where neither player can checkmate by any sequence of legal moves). Determining these reliably requires an algorithm, not a chess engine evaluation.
The algorithm is described in a peer-reviewed paper presented at the 11th International Conference on Fun with Algorithms 2022.
The approach
Static analysis
CHA-Solver first applies lightweight rules to detect provably unwinnable positions without any tree search. These cover locked pawn structures, and piece confinement patterns. Most real-world unwinnable positions are resolved here, instantly.
Targeted helpmate search
For positions that need deeper analysis, CHA-Solver searches the game tree for a helpmate. Move selection is guided by heuristics that prioritize forcing lines, and a transposition table avoids re-examining the same positions. The search is cooperative: it looks for any line in which the intended winner can deliver checkmate, even with the opponent's help.
Proved verdict
The result is a binary, proved decision: unwinnable or winnable. There are no scores, no confidence intervals. CHA-Solver is sound: it never incorrectly calls a winnable position unwinnable. It relies on jordanbray/chess for move generation but reasons at a higher level. A formal proof of soundness is given in the FUN22 paper.
Full search vs Fast mode
CHA-Solver runs in two modes. Both return provably correct answers; they trade completeness for raw speed.
Full
CompleteFast
High throughputBenchmarked single-threaded on an Intel Xeon w3-2435, over the timeout position of 10 million real Lichess games that had been adjudicated as a loss for the player who ran out of time.
* Complete on every known legal position, real or constructed; not proven complete in theory. You could be the first to find one it can't resolve!
The fast mode, despite being incomplete on some ad hoc positions, correctly identified all 197,223 unfairly classified games in the Lichess Open Database of standard rated games.
A note on complexity
Chess unwinnability, for an appropriate generalization of chess over an N×N board, has been studied by Brunner, Demaine, Hendrickson, and Wellman in Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess is Hard (2020) . The authors prove that chess unwinnability is PSPACE-complete.
Their generalization places no restriction on the length of games. A natural alternative, motivated by the 75-move rule, would impose a polynomial bound on the round complexity of the game. Under that generalization, the results of Brunner et al. would instead make chess unwinnability coNP-complete.
These intractability results are discouraging, but they do not apply to the (constant) case N = 8. That is why CHA-Solver can exist.
For developers
CHA-Solver is published as a Rust crate. Add it to your Cargo.toml:
chasolver = "3.0"
The full API, including the entry point for each mode, is documented on docs.rs.