Is This the Most Complex Forced Mate Chess Problem Ever?
I have been working in the area of artificial intelligence (AI), in the domain of chess, specifically, for over 15 years. Yesterday (October 28, 2021, at 3:27 am, GMT+8, to be precise), my ‘computationally creative’ program, Chesthetica (v12.43), produced something very unusual. In fact, I had never seen anything like it before. I noticed an ‘out of memory’ error in one of the instances of the program I had running. Upon looking a little deeper into the logs, I discovered that Chesthetica had apparently stopped in the process of composing a problem because, well, it ran out of memory.
It happened to be a forced ‘mate in 5’ composition (also known as a ‘direct mate’) which means that the stipulation would be, in this case, White is to play and checkmate in 5 moves (at most) against any defense by Black. The initial position of the composition that seemed to have caused the error is shown in Figure 1. Its FEN (Forsyth-Edwards Notation) or board position notation which can be used to easily export positions between chess programs is: 1Q5R/p1p2P2/3N4/p2k4/2p5/K7/2bP4/R7 w — — 0 1.
At first glance, it does not look like much; the composing process was, after all, halted prematurely. White is significantly ahead in material and forcing checkmate is hardly a challenge for even a novice player or patzer. In fact, there are so many ways to force checkmate (in at most 5 moves) that just about anyone should be able to find a solution. Yet, that’s just it; the full analysis actually turned out to be too large for the available memory and code to handle. This, surprisingly, has never happened before in over a decade of Chesthetica composing original chess problems. Figure 2 shows a screen capture of the latest Stockfish chess engine analysis of the position via the ChessBase 13 software interface.
What usually takes only a few seconds for a typical forced mate problem took about 18 minutes in this case on my computer running Windows 10 Home with an Intel® Core™ i5–1035G1 CPU @ 1.00 GHz and 20 GB of RAM. More importantly, you can see that there are 21 forced ‘mate in 5’ lines or solutions, i.e., with a different key or initial move. This is a lot more than would be expected in a forced mate. Bear in mind also there are only seven white pieces on the board. According to chess composition convention or ‘codex’, this problem is thoroughly ‘cooked’ (having more than one key move in the solution), which is a bad thing, but that is not the point.
I have never encountered a chess problem with this many different solutions that satisfy the stipulation, i.e., forcing mate in a particular number of moves. There are also at least two forced ‘mate in 6’ lines that follow but I did not choose to go any further down that rabbit hole. You might think that 18 minutes of analysis should not cause an ‘out of memory’ error, especially on the computers we have today. However, Chesthetica typically deals with more detailed analyses than shown in Figure 2. A ‘mate in 5’ problem, with its complete solution tree, might look like the example shown in Figure 3.
For this problem (FEN: 2k5/3p4/5Q2/4P3/8/4K3/8/8 w — — 0 1), the solution tree has only five lines, including a possible ‘mate in 4’ shown in the third line (assuming Black did not put up the best defense). The tree has a low branching factor, even for a forced mate. If you had to, it would not take very long to explain it thoroughly given the low ‘complexity’ or few intricacies created by the moves. In general, the solution tree for a typical forced ‘mate in 5’ problem can be quite a bit larger and more complex, or difficult to explain in full. In my experience, around 2,000 lines or a 50 KB ASCII (text) file would not be unusual. The composition in Figure 1, in contrast, had 17,799,428 lines in its solution tree and produced a 325 MB ASCII file. That is many thousands of times larger than expected; an outlier, to say the least.
Therefore, it’s not just the fact that there are 21 valid solutions with different key moves given only seven white pieces on the board. It’s also the tremendous complexity of the solution tree (nearly 18 million lines) which goes far beyond other ‘mate in 5’ compositions that I have ever encountered. Is it any wonder why there was an ‘out of memory’ error produced by Chesthetica while processing a position like this? We may never know what the final composition, probably with only one key move (to avoid being ‘cooked’), might have looked like had the program not stalled but then this position would never have been discovered.
It is highly unlikely there will ever be a chess problem or puzzle like the one shown in Figure 1 encountered ever again. The size of the solution tree alone puts it in a class of its own. The composition is so unusual there is really nothing I can see in terms of improving Chesthetica’s code so this error does not happen again, because it probably won’t. Let it even be an open challenge to human composers and players everywhere and for all time to produce something like it, with or without the assistance of a computer. Perhaps the AI community is moving its attention away from chess prematurely. There certainly seems to be hidden depths to the game and more to discover.
Addendum
Upon further analysis, it turns out that if the position in Figure 1 is modified a little, i.e., by removing the black pawn on the a5 square, the complexity increases even further with 23 ‘mate in 5’ solutions, a 353 MB ASCII file and 19,299,598 lines in its solution tree. Chesthetica might have arrived at this too during its optimization process if not for the ‘out of memory’ error. However, not all modifications to the original position have this result.
For instance, shifting the white rook from a1 to a2 turns it into a forced ‘mate in 4’ with only one solution and just 957 lines in its solution tree. Another example is adding a white pawn to e2. That turns the position into a forced ‘mate in 4’ with one solution as well, and only 91 lines in its solution tree. The open challenge therefore refers to a sufficiently different position, and not a modification of the original.
