Antichess: 1. e3 Wins for White in #79

The solution is here.

Mark Watkins' Solution

Algorithm

Almost 10 years ago, Mark Watkins completed his years-long work on proving that 1.e3 wins for White. For this, he used a program he developed, the source code of which can be downloaded here. The program is based on the Proof-number search algorithm. In a greatly simplified form, the essence of the algorithm is that the program sequentially checks all White moves and all Black responses to a certain depth. If a White move leads to a loss or a draw, that move is discarded. If even one of Black's responses leads to a win for Black or a draw, the previous White move is discarded. From the remaining moves, the branches are explored more deeply where, as the search progresses, more winning moves and fewer losing or yet-to-be-explored moves are encountered.

This algorithm is quite good for finding forced wins that are not too complex. It's also good enough for finding moves that lead to positions where Black is left with a limited set of moves that do not lead to an immediate loss. In most cases, this is precisely the best continuation for White. The algorithm is not very good in positions where White has a clear advantage but no forced win, so they first need to slowly improve their position before moving on to active play. For example, consider a position like this:

Practically every White move leads to a position with a clear White advantage. If Black prefers to stay in the corner near a1, the only winning path for White will be to first promote all their pawns and then attack the King. Black might choose to attack White's slow pawns on g2 and h2, so White must arrange their pieces to ensure the pawns' safe passage to the last rank and their safe promotion. In such positions, the Proof-number search algorithm may require considerable time to generate the solution tree, and the solution might be far from optimal. As seen in the study linked above, this position in Watkins' solution (3rd revision) was solved as a win in 163 moves (326 half-moves) adhering to the 50-move rule. Meanwhile, a win here only requires 29 moves, starting with Re5 and then Re6.

Complexity of the Solution

Watkins' complete solution for 1.e3 can be downloaded here. It's a 1 GB file, or 4.2 GB after decompression. A special program can be used to read the file and navigate the solution tree, a link to which, along with instructions, can be found at the bottom of this page. The computational resources allocated to the search for the solution varied at different stages of the project. Towards the end, it was typically 8 computers, each with 16 cores and 128 GB of RAM. The entire project took over 5 years. Mark Watkins estimated that if a single computer with a single-core processor were used for the computations, it would have taken 200...300 years.

How complex is Watkins' solution? The latest, 4th, revision of Watkins' solution tree consists of 694 million nodes and 54 million transposition pointers. Every White or Black move leads to a specific position/node. If it's a White move, the solution provides only one single move. This doesn't mean other White moves don't win. The solution only provides one path to a guaranteed win. If it's a Black move, all possible Black responses are given. All branches end when White wins or a 4-piece endgame position with a win for White is reached. Many positions can be reached via different paths. Such positions are not duplicated; a single node is used with a common continuation for all transpositions leading to that position.

On one hand, strong players don't need to memorize complete sequences of moves. They only need to memorize the sequences of moves leading to positions with a comfortable White advantage. Their experience and skill will take care of the rest. On the other hand, the solution is so cumbersome that even the strongest players cannot memorize all the necessary moves. The solution has been available for about 10 years, but in that time, I haven't seen a single player who could master this task.

Moreover, a seemingly paradoxical situation is observed where players consciously refuse to use the Watkins solution and choose alternative paths. This is explained by the fact that many branches in Watkins' solution lead to sharp positions where White must play quite accurately to win. Often, White has only one single move that allows them to win, and all other moves lose. Many winning moves seem anti-intuitive. Some branches can lead to very similar positions with small differences, such as piece rearrangements or slightly different pawn structures. However, these positions may require completely different approaches to achieve a win. It's not always easy to keep all these nuances in mind. Therefore, White often prefers alternative paths that may objectively not win but are easy enough to play, maintaining a significant advantage for a long time. This is in contrast to some branches in the Watkins solution where failing to find the correct move in a critical situation will inevitably lead to a loss.

Endgames

In his solution, Mark Watkins used a 4-piece endgame tablebase. Most branches of the solution end with a White win. However, 19.5 million branches end in 4-piece endgames. Some of these endgames are trivial, but some are quite complex. The most complex 4-piece endgames in Antichess lead to victory only after 87 moves (174 half-moves) with optimal play:

4-piece endgames in Antichess are richer and more diverse than in standard chess. Unlike chess, in Antichess, players may not have kings, so Antichess endgames are represented by a greater variety of piece combinations. Some 4-piece endgames are so complicated that players prefer not to enter them if possible. Examples include KNNvK, KBNvK, BNPvP, and so on.

Many of the endgames in Watkins' solution require more than 50 moves without captures or pawn moves to win. This means that if White follows the Watkins solution on Lichess and uses an endgame tablebase for optimal play in the endgames, such games can still end in a draw.

Solution Minimizing Winning Length

Preconditions

One day, I decided to use the Watkins solution to choose the best continuation for Black. This turned out to be a difficult task. It seemed that you simply choose the move with the largest number of nodes each time, and eventually, you get a complex position where White is unlikely to remember the correct sequence of moves. But nope, upon advancing to a depth of 20...30 moves, I reached a position where it was very hard for Black not to lose instantly. Where were all those complicated endgames? While the number of nodes is in the millions, this metric accurately indicates the complexity of the positions. However, when moving deeper into the solution tree, these numbers become less informative. Some positions with hundreds of thousands of nodes can be solved by the engine in seconds, while some positions with only hundreds of nodes resist the engine for a long time because almost all moves lead to complex endgames. That's when I thought that if, in addition to the number of nodes, I had information about the maximum winning length, it would greatly help in finding complex lines.

On one hand, the presence of an additional metric (maximum winning length) allows for a better assessment of the complexity of the positions. On the other hand, it's simply interesting: does White win in 50, 100, or 200 moves with optimal play on both sides?

Furthermore, it was interesting whether White wins when the 50-move rule is applied, or if a forced draw is the most White can achieve with Black's best play. To answer this question, I wrote a small program that traversed the Watkins solution tree and found all branches where the solution ends in endgames that only win if the 50-move rule is not applied. As it turned out, the 13 simplest Black responses — when their complexity is judged by the number of nodes in the solution tree — do not have such endgames. And the 7 most complex responses (1...Nc6, 1...Nh6, 1...g5, 1...e6, 1...b5, 1...c5, and 1...b6) have such endings. Examples of these endgames can be found in this study.

Upon a quick review of these branches, it was evident that most of these endgames could have been avoided quite simply by going back a few moves and changing something. Unfortunately, there were too many such endgames to attempt to correct them all. It wasn't always obvious how many moves back one needed to go to attempt to find an alternative solution.

In parallel with finding endgames that lead to a draw when the 50-move rule is used, the program also determined the maximum winning length for each of the 20 Black responses to 1.e3, ignoring all drawing endgames. The results can be seen in the study, in the first half of the chapters. Here are some of those results:

As with the drawing endgames, the longest branches in the Watkins solution can be corrected by small changes at earlier stages. However, implementing such corrections would require many times more resources compared to correcting only the endgames.

All this showed that small changes were not enough to correct the Watkins solution, so I decided to develop a separate program for these purposes.

Search Methodology

To find the solution that minimizes the maximum winning length, we used Multi-Variant Stockfish at the initial stage, and then switched to Fairy-Stockfish. The first engine is good enough at finding relatively simple forced wins. It is head and shoulders above Fairy-Stockfish in finding forced wins in the opening stage when there are many pieces on the board. This is likely due to more aggressive pruning. However, Fairy-Stockfish excels over Multi-Variant Stockfish in complex positions requiring careful maneuvering and gradual position improvement. In such positions, Multi-Variant Stockfish can overestimate some lines and eventually lead to a drawn position. This constantly required additional human intervention, so the decision was made to fully switch to using Fairy-Stockfish.

The algorithm is quite simple in its idea. In every position with a White move, Fairy-Stockfish is launched, and the best move is determined. This move is selected, and we gradually build the solution tree until the engine sees a win. We do not stop the engine immediately as soon as it reports a win, but wait some time in case the engine can find a win in fewer moves. If the engine cannot investigate the position to a sufficient depth, we stop it and continue advancing along the branch until we are confident that further improvements are unlikely. At this point, the upper-level solution ends. The lower-level solution involves proceeding to a win in every sub-branch.

Thoroughly analyzing every position with the engine is quite resource-intensive. A compromise between accuracy and speed is necessary. The main difficulty is determining when to stop the engine. On one hand, if the engine analyzes every position for too long, it will delay the solution process. On the other hand, if we don't give it enough time, we might not find the best continuation, and then we will lose time building a more complex solution than necessary. The algorithm uses a heuristic approach to determine the time given to the engine to analyze each position. Depending on the progress reported by the engine when advancing one depth further, we decide whether to give it more time or to stop it and proceed to the sub-branches.

When moving on to more difficult branches, such as 1.e3 e6 and 1.e3 b5, the ability to employ the Watkins solution file (or one of Steenhuis' solutions in case of building the solution as a win for Black for openings where White does not start with 1.e3) was added to the program (solver). The Watkins solution was used as follows. After analyzing each position with the engine, the move it suggested was compared with the move from the Watkins solution. If the moves differed and the evaluation of the move suggested by the engine turned out to be substantially better, we chose that move. If it wasn't clear which move was better, the program additionally investigated each of these moves to a depth of 3 White moves. If even after advancing three moves deeper, it wasn't clear which of the moves was better, we chose the move from the Watkins solution.

Solver Improvements

Initially, the solver was written in Python. Minimal human intervention was assumed. Unfortunately, this did not work properly. Very often, the engine incorrectly evaluated positions, chose bad moves, and got stuck solving them. As a result, I decided to rewrite the solver in C++ and use a suitable GUI that allows for relatively simple intervention in the solution process. The solver and its source code are available here.

In the initial stages of the project, I experimented with using endgame tablebases. Multi-Variant Stockfish is able to employ Syzygy tablebases. These tablebases allow for taking the 50-move rule into account and finding moves that lead to a win. However, Syzygy tablebases do not provide information about the winning length. In most cases, connecting Syzygy to Multi-Variant Stockfish only slowed down the search process and often led to piece sacrifices with a transition to very complex endgames. Therefore, I abandoned the use of Syzygy tablebases.

When solving more complex branches, such as 1.e3 e6 and 1.e3 b5, it became clear that endgames were taking up more and more time in the computations. To simplify my life, I decided to generate a 4-piece endgame tablebase with information about the winning length. This tablebase is now used by Lichess, and you can see it on the analysis page — the Depth To Win (DTW) metric. I initially used this tablebase in the solver, but not in the engine. When 4 pieces remained on the board, the solver no longer used the engine, but only the tablebase. The greatest progress was achieved when I built my tablebase directly into Fairy-Stockfish. I didn't initially plan to do this due to the negative experience with using Syzygy tablebases in the engine. However, as it turned out, this gave a significant performance boost. I can only regret not having done this sooner. The tablebase was only used when constructing solutions for the last two branches — 1.e3 c5 and 1.e3 b6. Otherwise, we would have spent much less time compiling the solution.

In the later stages of the project, an algorithm based on Proof-number search, developed by Mark Watkins and used by him to generate his solution, was built into the solver. @ChessDemon989 provided invaluable assistance in this, as he not only transformed all the necessary code but also made additional changes to exclude FICS rules from the algorithm and leave only international rules. The fact is that when compiling his solution, Mark Watkins supported both sets of rules, so potential solutions that worked for one set of rules but not for the other were discarded. Our solver was originally conceived as supporting only international rules, as implemented on Lichess (the main difference between the rules is who wins in stalemates), using the 50-move rule. It is worth noting that the Proof-number search algorithm was not applied to generate our solution, but was only occasionally used in manual mode as an additional analysis tool for experts performing human intervention.

Human Intervention

Although the program is capable of generating the solution in automatic mode, human intervention helped not only to speed up this process but also to improve its quality. In some situations, it seems reasonable to allocate more time for engine evaluation of the position to find a more optimal continuation than the one suggested by the engine with standard analysis time. In some positions, a deeper investigation of alternative paths seems advisable. It is difficult to disagree with Mark Watkins' words, referring to his algorithm but also true for our program, “This works fairly well for some of the easier proofs. However, we are of the opinion that there is still a considerable art (or lack of science) involved in the harder ones.”

We used the solver not only to find the solution for 1.e3 as a win for White but also to find solutions for some other White moves as a win for Black. In almost all these solutions, we managed to reduce the maximum winning length by refining the initially generated solutions through the application of expert corrections.

In the initial stages of the project, I was the only one compiling the solution with information about the winning length, using only my old laptop. I gradually expanded the solution, moving from the simplest Black responses to the more complex ones. At the stage when I reached 1.e3 g5 and 1.e3 e6, @Pinni7 joined the project. He solved most of the lines in 1.e3 b5 and also improved the solutions for 1.f4, 1.Nc3, and 1.e3 f6. Unfortunately, the solver was still in its initial stage with the Python implementation back then, which did not allow us to fully utilize @Pinni7's experience.

@Pedro_Re provided invaluable assistance in compiling the solution. The results of his work can be seen in the branches 1.e3 c5 and 1.e3 b5. He completely solved 1.a3, and also made significant efforts to substantially improve the solutions for 1.h3, 1.c3, 1.b4, 1.Nc3, 1.h4, 1.f4, and 1.Nf3. In addition, he also worked on solving complex branches after 1.c4.

In the later stages, @Yabbadabbadoooooooo joined the project. He decided not to use the line employed in the Watkins solution for 1.e3 g5. His hopes were justified, and this allowed for a substantial reduction in the maximum winning length. Yabba also worked on solving 1.e3 c5, as well as improving existing solutions, such as 1.e3 Nc6, 1.e3 b5, and 1.h3.

The most cumbersome branch of the solution is 1.e3 b6. @Awkwardmammal provided priceless assistance in solving it. He not only managed to solve positions that were represented by hundreds of millions of nodes in the Watkins solution but also managed to do it in such a way that the maximum winning length is now at such a low level.

Some specific lines in the solution are based on recommendations and ideas from some strong players: @PepsiNGaming, @Arimakat, @ChessDemon989, etc.

Results

The current results are presented in the following table.

Now we can say that with optimal play, White plays 1.e3 and wins in less than 80 moves, even when the 50-move rule is applied. In other words, regardless of how Black responds, the game will never reach move 80, because with best play, White will win earlier.

All branches except the five most complex ones have been solved down to the very last move, and the number of positions for them in the last column shows the number of moves White needs to memorize to win against any Black response. These numbers cannot be directly compared with the number of nodes in the Watkins solution, since in our solution, we consider all positions, even those belonging to endgames with 4 or fewer pieces. In the Watkins solution, such positions are not counted. A quick analysis shows that some complex endgames can require hundreds of thousands or even millions of nodes to store their full solution, starting from the position where the transition to the endgame with specific pieces in specific starting positions occurs.

On one hand, it makes no sense to use the same format for saving endgame solutions, but on the other hand, the number of positions (nodes) in the solution for endings allows for estimating their complexity. It is one thing if you have a win in 7 moves in the KBNvK endgame, and quite another if in the same endgame, you theoretically cannot win in less than 50 moves, and at the same time, you must not draw the game due to the 50-move rule. In the former case, most strong players will have no problem winning, but it seems virtually unsolvable in the latter case. Here is one example of such an endgame:

Of course, not all endgames are equally complex. For instance, most strong players will have no problem converting a KKKvK to a win, but BNPvK can be a very challenging task. Therefore, we decided not to exclude the number of unique positions in endgames and use this metric as an indicator of complexity.

The five most complex branches were solved only at the upper level, or in other words, up to the point where the engine sees a forced win and the algorithm considers that a further reduction in the winning length is unlikely. For these branches, we only provide the number of positions at the upper level. Cumbersome branches with millions of positions, although fully solved, including at the lower level, are not provided on the website down to the very last move due to saving server space. Most of the discarded positions can be solved by the engine in a matter of seconds, so it makes no practical sense to include them fully.

It should also be noted that the final positions in the upper-level solutions should not be considered equal in complexity. First, the engine's evaluation may not coincide with the evaluation of experienced players. Second, the engine's evaluation may be distorted due to the presence or absence of relevant positions in the engine's cache at the moment the corresponding position was solved. The latter is determined by the order in which the solver considers the moves or the moments of its restart.

Improving the Results

Can the results be improved? We have made a concerted effort to reduce the maximum winning length in each branch. However, this does not mean that shorter wins do not exist. In most cases, it is likely necessary to deviate from the solution somewhere at an earlier stage to try to improve that solution in terms of reducing the maximum winning length. It is entirely possible that this may require generating much more cumbersome solutions. And then the question arises whether the game is worth the candle. As an example, consider two solutions for 1.e3 c6. The move 2.Bb5 leads to a win in 59 moves, and the complete solution contains about 2 million positions. The alternative move 2.e4 leads to a win in 36 moves, but its complete solution contains about 8 million positions.

Although we cannot compare the number of nodes in the Watkins solution with the number of positions in our solution, we assume that our solution tree would require more nodes if the 4-piece endgames were not counted. If endgames are counted, it seems to me that after making small adjustments to the Watkins algorithm to exclude cumbersome endgames, his solution would still require saving fewer positions because this is the price we are forced to pay in our solution to minimize the winning length.

The main efforts were directed toward improving the lines that led to the longest wins. This means that substantially less attention was paid to the remaining lines, which means that almost certainly, most of them can be improved. Nevertheless, these potential improvements are beyond the scope of the current project and the limits of motivation.

Conclusion

I hope the solution will be useful for fans of opening theory. The solution is quite complex, and I don't think anyone is capable of memorizing it completely to win in 100% of cases — at least until Antichess is a professional sport — even considering that in many cases, it is enough to memorize only the main ideas characteristic of specific opening lines. On Lichess, only a small number of people play Antichess using time controls longer than blitz. Using some lines from the solution for fast Antichess can be counterproductive due to the complexity of these lines and the high cost of error, especially compared to alternative lines.