Why a reachable position can have at most 218 playable moves

Ever since Nenad Petrović, grandmaster of chess composition, published his record composition in 1964, people have tried to come up with a better one. Being a computer scientist, I decided the join the pursuit in May 2024 and settle this question once and for all. You can give it a try yourself. Try to find a position with more moves than the one below.

Spoiler: You won't.

Even better: We can prove it ^^

Reachable chess position with 218 moves for White, published by Petrović in 1964.

...but how can we know for sure?

By checking all ~4.8x10^44 reachable chess positions?
Yeah that's not gonna happen...

That's half a billion billion billion billion billion and it's enough to scare even the mightiest of supercomputers. Cracking a 23 character password (numbers, big AND small letters) would be easier.

Fortunately, Chess is not passwords, and we can use the power of Math!

Wait, so this is actually happening?

Follow me along and perhaps you can compute yourself a world record afterwards :)

Using the power of Math

Red is the official color of Math according to my elementary school teachers.

We're gonna tackle this problem from the white side, i.e., it is White to move. Except for rare exceptions regarding the reachability of positions, this is equivalent.

Since proving that a position is reachable from the starting position is pretty complicated, we're gonna ignore that for now and filter non-reachable positions afterwards. This does not diminish the claim we're trying to prove here in any way.

We can imagine the problem like a password of length 64 with 13 possible letters. One for empty squares and 12 for the various pieces. Basically, each position in the password is a choice and its letter is it's chosen value. Unlike real passwords, we know that some combinations are not valid. For example, there can't be more than one white king. So while brute-forcing our way through, we can, very often, stop early, knowing that the position will be illegal. Let this be our first angle of attack.

Unfortunately, this is not good enough! Remember the ~4.8x10^44 reachable legal chess positions? And this also includes non-reachable ones, ugggh!

So we're gonna need a second angle here: We realize that the vast majority of positions SUCK at having lots of moves. They don't even come close. Surely, while trying letters, we can stop early sometimes? But we can't guess, we need to be 100% certain, otherwise we can't claim to have proven the conjecture. This angle basically is like a magic wizard telling us, some time between having typed our 5th to 9th letter, that we're on the wrong track. If we can hire an even slightly better wizard that notifies us one character earlier, we save 72 times the work (assuming letters and digits).

In order to have any hope of solving this, we need to squeeze out the absolute max of both angles of attack, then pray that there exists enough electricity to check the rest.

Let us begin by making a couple of useful observations.

Step 3: Pray that there exists enough electricity.

Useless pieces

A black piece does not improve the number of White's moves unless one of the following is true:

• It can be taken by a white pawn, giving said pawn more moves
• It protects the black king from check, making an otherwise illegal position with lots of moves legal
• It frees a white piece from being pinned to the white king, thus giving it more moves

Otherwise, we can just type the empty letter instead (to stick with our password analogy) and know that the resulting password will be at least as good!

I inserted this picture for the sole purpose of making this article look less text-heavy.

Too powerful pieces

Next, we observe that, if piece counts permit, we can always replace a black piece, with the exception of the black king, with a strictly less powerful one. That is, a piece that has a subset of the moves of the original piece. For example, a queen with a pawn/bishop/rook or a bishop with a pawn. Except if a pawn is on the seventh rank, since in that case, each of its moves to the promotion square counts as 4 separate moves. The only way for Black's moves to affect White's number of moves is by pinning White's pieces or preventing the white king from stepping on a certain square. Both of these things can't get worse if the black piece has less moves than before.

Too weak pieces?

The other way around, it is not so easy, however. You'd think that you can just replace white rooks and white bishops with white queens if counts permit, but the problem is this: How do you ensure that you cannot capture the black king, making the position illegal? Maybe the optimal solution has a rook instead of a queen to avoid just that?

Well, you might say "Let's just place a black piece in between then".

Stop and think a minute.

And you would be wrong unless you can tell me why you haven't just blocked some other white piece and thus reduced the number of moves in total. Or what your plan is, if there is no space to put something in between. You just made the position illegal, duh!

No checks, thank you

Finally, we can get rid of checks. If the black king is in check, it means that the position is illegal, since it is White's turn to move and they could just capture the black king. Not okay! So that can't be it. On the other hand, if the white king is in check, then the number of White's moves is severely restricted and we can easily prove that we cannot reach 218 moves. There are three ways to get out of check:

• Move the king
• Capture the attacker
• Block the attack

Moving the king gives 8 moves at best. Since any square can be reached by at most 16 pieces at the same time (8 knights and 8 other pieces straight or diagonally), capturing gives 16 moves at best. We can have at most 6 squares to block an attack, so that's an additional 6 x 16 = 96 moves. So at best 8+16+96 = 120 moves, far less than 218, and thus we do not need to consider positions in which either king is in check.

So is this it Tobi? Can we now call NASA and ask for their supercomputer?

Nope, it's still absolutely hopeless, there are waaaaay too many positions left.
We have to skip even more positions.

Introducing Fractional Pieces and Moves

Reminder: Replace rook pictures by something more interesting.

Let's turn our attention to the second angle of attack. Stop typing the password when it's obvious that it's not gonna be good.
In particular, while searching through all possible piece configurations, we would like to have some provably correct way of telling whether we can still reach 218 moves, so we can stop trying and save ourselves an astronomically large amount of work. The better the method is, the more work we save. But it also needs to be fast, since we need to run it millions and billions of times.

A common technique in optimization is to allow fractional decisions. Instead of a piece being either on e4 or not, it can be 27.3% there and 72.7% not there. This enables the computer to just "swim" through the solution space towards the optimal solution instead of trying all combinations. The drawback is that we usually end up with a way too good solution with most decisions being fractional. But if even this madness doesn't get us beyond 218 moves, we can stop trying as the best legal solution is part of the swimming pool too.

Obviously, these kinds of algorithms are already implemented in state-of-the-art solvers like Gurobi, so all we need to do is model our problem to its likings (as a so-called integer programming problem), tell it to maximize the number of moves and pray. Finally, after ~55 000 seconds, it crashed.
Not enough memory, but also hopelessly far away from completing the proof. Extrapolating the runtime led to an estimated runtime of ~6 years. Yeah, let's not go there. Going back to making even more observations.

Checking more positions to make things less slow

To reduce the size of the model, I bent some chess rules, simplifying the search space:

• I allowed castling if king and rook were on the right squares, not requiring anything else
• I stopped caring about pieces moving despite being pinned
• I stopped caring whether the white king is in check or walks into check
• I allowed white pawns to always capture when standing on the fifth rank so I'd not have to check en passant.

All of these things are unlikely to happen in 218+ move positions and after a solution has been found, I can still check and discard it if it has less moves than it claims to have, so this does not hurt the validity of our proof either.

I launched Gurobi again and this time, memory wasn't a problem, but the progress was awfully slow with ~29 days remaining. The world could not wait this long and neither could I. I pressed cancel.

Preventing white magic

The optimal fractional solution for the empty board (e.g. the empty password). Most pieces are spread out over multiple squares and have fractional numbers of moves available that sum to ~305. This does prove that the real solution can't have more than 305 moves. Still quite a bit from proving 218 to be the optimum.

Our current way of cheating is too different from reality, causing the solver to have to search through way too many board configurations. In our case, the optimal solution to the easy problem flooded the center with half queens and half knights sharing the same squares, having half pieces move through other half pieces with half moves. A surreal mess. Gurobi thinks that the above position has 305 moves in total, which is far away from 218 and a bad upper bound.

In order to cut off this crazy solution, I added a "redundant" constraint, saying that at most one piece in total can move from one direction onto a particular square. Which got us a new kind of fractional solution...

The second try. This one has 271 2/3 moves which proves that there is no solution with more than 271 moves.

Now we have 271 2/3 moves, which is much better. It's a bit like having to try all passwords with 53 characters vs. all passwords with 87 characters, the latter being many magnitudes harder.

Wait a minute, White can't have 4 kings.

White does not have four kings. White has 3 times 24.6% kings and one 26.2% king. Also, the queen on g3 barely exists, it's 0.8% but apparently it somehow contributes to the total sum of moves :)

With this improved "wizard", I tried again and after ~23 000 seconds, Gurobi solved it to optimality!

Results

Sadly, instead of finding me a fancy position with 219 moves and making my name immortal, Gurobi gave me the following 12 representative positions (of ~40,000 in total) with 218 moves each:

Link to the positions

All 12 positions seem trivially reachable. I only constructed a proof game for some of the positions, since it's not necessary for our proof (a 218 move composition was published ~60 years ago as stated at the beginning of this article). If you don't believe that these positions are reachable from the starting position, then keep in mind that White's last or second last move might have been a capture. Or have a look at the study :)

Sadly not a world record, but at least we now know for certain that 218 is the limit. Assuming no bugs in mind nor machine, that is.

And you smart chess move 3.7 bit compression people and chess engine developers, you can finally stop worrying. 256 moves will be enough. You're welcome :-)

Except if you allow non-reachable positions, in which case you might want to read on :P

Other stuff solved along the way

I also confirmed the optimality of the 144 move record without promotions using the same techniques. Since Gurobi did not find any position with more than 144 moves, that means that there also is no reachable position with more than 144 moves. Hence, 144 moves is the best we can do and "Jenő Bán", a chess composer from Hungary, found one in 1960 already:

144 moves for White, no promotions. Created by Hungarian chess composer "Jenő Bán". Here is a proof game, demonstrating that the position is reachable.

Also, I confirmed the optimality of the following illegal position, which has 288 moves for White.

Illegal position with 288 moves for White. Corner queens can be replaced with bishops.

Now have a guess at what the best non-reachable legal position looks like ;)
Yep, you're right, cramming the kings into the corners for 271 moves.

Legal but non-reachable position with 271 moves for White. Corner queens can be replaced with bishops.

Future plans

My code snippet is freely available at Github. If you manage to do something cool based on it, please let the world know :)

Fun problems enthusiasts could try to tackle next using similar techniques:

• Most captures
• Most stalemates
• Most checks
• Most checkmates
• Most mates in two
• ...
• Most ... under <condition>

Some of these might be hard, extremely hard or practically impossible to solve with current technology. I don't think that integer linear programming is a suitable approach for all of them, one likely has to develop a custom algorithm for computing good upper bounds, based on creative mathematical insights.

Good luck to those who dare to try solving one of these ^^

FAQ (based on questions on Lichess and HackerNews)

A chess game can be longer than 218 moves, duh
Yes, a chess game can have thousands of moves if people cooperate, but this article is about the number of options for the side to move.

Position ... is not reachable from the starting position!
Have you considered that White's last move might have been a capture? Have a look at the proofgame chapters in the study.

I don't get what you are doing, this is magic to me, can you explain it simply?
Let me give an anology: We are trying to write the best possible short story with exactly 1000 letters using a keyboard. Out of ALL ways to arrange 1000 letters.
After choosing the next letter, we consult a magic oracle that tells us whether what we wrote so far is so terrible that it can't possibly become a good story (or rather one better than the currently best known story). Thanks to this magic oracle, we can actually work through the otherwise prohibitively large number of combinations!

Each letter represents a decision, such as, whether there is a queen on h5 or not, whether the piece on h5 can move to g3 or not, ...
The complete story represents a complete chess position. The goodness of a story is the number of legal moves to choose from.

The magic oracle thing is a bit heavier to explain, for that I'd recommend reading the article slowly and asking ChatGPT etc. interactively :)

Can I look at your code?
Yes, of course!

If Gurobi, your code and your thinking do not have a bug, is this mathematical proof?
Yes, this proves that among the set of all chess positions reachable from the starting position by a sequence of legal moves, there are positions with 218 legal moves to choose from for the side whose turn it is and there is no position with 219 or more legal moves. 218 is the maximum. Upper AND lower bound proven. The lower bound was known for ~60 years, of course. This work only supplied the (to the best of my knowledge) missing upper bound.

Has your result been reproduced by other people?
Yes! A wonderful person by the name of @Toberon found their way across the article's forum and notified humanity of their independent arrival at 218 moves. Their code was faster as well :O

Feedback Hall of Fame

@tromp1234: For pointing to a better estimate for the number of legal chess positions and pointing out that my source is off by an order of magnitude.

@IDontWantUsernames: For the native English speaker level title suggestion ;-)

@Toberon: For reproducing the 218 move result! ^___^