CheckmateFinder is a Java application that can find forced checkmates ("mate in n") given an initial board state. A "forced" checkmate means that one side, given optimal play, can force the opponent into a checkmate. This often occurs towards the end of a chess match, and can be surpisingly difficult to find. My original motivation to make CheckmateFinder came from chess puzzles.
By default, CheckmateFinder will try to provide the first move in a forced checkmate sequence, and the maximum moves till checkmate if played correctly. CheckmateFinder can also generate a JSON representation of the move tree which can be supplied to the included chess-grapher.py script in order to generate a graphic representation of the tree.
CheckmateFinder can be controlled from the command line by providing the FEN (Forsyth–Edwards Notation) of the game with the --fen argument. Along with the FEN, a depth must be provided (with --depth) that tells CheckmateFinder how many moves ahead to search. Another parameter, the "check depth," must also be provided (with --check-depth), that tells CheckmateFinder how many turns it should consider non-check moves (higher values drastically increases the search time). The higher the depths, the more likely it is that CheckmateFinder will find a forced mate. With higher depths also comes increased search time. CheckmateFinder is not an optimized program, but an absolute brute-force approach to calculating moves that is only useful when a game is near completion.
A proper chess engine will use advanced heuristics along with hard-coded solutions to certain patterns to ensure that it can make a good move in a reasonable amount of time. CheckmateFinder is not a chess engine, it is not even guaranteed to provide you with a move. CheckmateFinder is primarily a proof of concept, and was made out of my frustration with a puzzle that could be solved much easier by a computer (or somebody reasonably good at chess).
It is easiest to understand how CheckmateFinder works with a visual:
In this tree, blue dots represent game states. The leftmost dot is the initial game state. Assuming it's white's turn, each white line represents a move that white can make. If we are still below the check depth, we consider all possible moves that white can play. If we are above the check depth, only check moves are considered. Black lines are all valid moves that black can play. To have a forced checkmate, the entire tree must have this recursive property:
(Initial state is at depth 0)
- A leaf who is at an odd depth (opponent's turn), is a forced checkmate tree if the opponent is in check. (opponent has no possible moves and is in check: checkmate.)
- A subtree whose root is at an odd depth (opponent's turn), and whose branches exclusively lead to forced checkmate trees, is also a forced checkmate tree. (any of the opponent's moves still result in a forced checkmate)
- A subtree whose root is at an even depth (your turn), and whose branches lead to at least one forced checkmate tree, is also a forced checkmate tree. (there exists a move for you that forces checkmate on your opponent given optimal play)
This example tree does have this recursive property, and so it represents a forced checkmate. In fact, for this example, any of white's initial moves can lead to a forced checkmate.
Let's start with a trivial example:
|
|
|
|
| Initial board state | White: Qe8+ | Black: Rxe8 | White: Rxe8# |
We can use CheckmateFinder to generate a tree that tells us how to checkmate from this initial state. We do this by running checkmate-finder to generate a JSON representation of the move tree, which we then pipe into the python graphing program.
Here is the command that generates the graph below:
java -jar checkmate-finder.jar --fen 'rn1r2k1/1pq2p1p/p2p1bpB/3P4/P3Q3/2PB4/5PPP/2R1R1K1 w - -' \
--depth 4 --check-depth 0 --generate-move-tree | python chess-grapher.py \
--font <path to TTF or OTF Font> --width 1600 --height 900 --max-text-box-height 40 --show-image
In this diagram, the red-outlined paths represent moves that lead to a forced checkmate. The purple paths at the end represent the algorithm giving up because maximum depth was exceeded. The green #s surround states where the opponent is in checkmate. We can see that the entire Qe8+ -> Rxe8 -> Rxe8# sequence that we just played is highlighted red and fits within the maximum depth. But, Qxg6+ will not work as a first move since both fxg6 and hxg6 lead black to escape checkmate (for this search depth).
Here is a more complicated match from thechessworld.com's 3 Hardest Mate-in-4 ever: L. Knotec, “Cekoslovensky Sach”, 1947:
|
|
|
|
| Initial board state | White: Kg4 | Black: Kd4 | White: Rd3+ |
|
|
|
|
| Black: Ke5 | White: Kg5 | Black: e6 | White: Nd7# |
This was an example of how this game might be played, but what if black plays different moves? We can use CheckmateFinder to solve this mate in 4 by running the following command:
java -jar checkmate-finder.jar --fen '8/4p3/1B6/2N5/2k5/1R4K1/8/7B w - -' \
--depth 8 --check-depth 5 --generate-move-tree --skip-wrong-moves | python \
chess-grapher.py --font <path to TTF or OTF Font> --width 1600 --height 1200 \
--max-text-box-height 45 --dont-highlight-force-mate --show-image
Note: this tree is omitting all paths that don't directly lead to a forced mate (--skip-wrong-moves). It would be absolutely massive if all paths were included.
To hunt down bugs in CheckmateFinder regarding compliance with the rules of chess, Perft was used to verify, from an initial game state, that the calculated number of possible moves for a limited depth matched that of a known-good engine. This was tested for 6 initial game states, and led to the discovery of a few bugs that would have likely gone unnoticed.