AzizbekSabirov's blog

By AzizbekSabirov, history, 3 weeks ago, In English

In almost every Codeforces game theory problem, we see the classic line: "Alice and Bob play optimally. Who wins?"

In simple games, we just write a Minimax DP or find the Grundy values (mex) to get an AC. Bugs aside, have you ever wondered: does optimal play actually exist in Chess? If two players with infinite rating play against each other, what is the guaranteed outcome?

1. The Math: Yes, It Exists (Zermelo's Theorem)

In 1913, Ernst Zermelo proved that in any finite, two-player, zero-sum game of perfect information (no dice, no hidden cards), an optimal strategy must exist.

In CP terms, chess is just a massive DAG (thanks to the 50-move and threefold repetition rules preventing infinite loops). Every terminal state has a fixed value: +1 (White wins), 0 (Draw), or -1 (Black wins). Using simple Minimax DP:

dp[u] = max / min (dp[v])

Since the state graph is finite, the starting board position S_0 has a strictly determined value. One of these three is an absolute mathematical fact:

  • White has a forced win from move 1.
  • Black has a forced win from move 1.
  • Optimal play from both sides always leads to a draw.

2. Why Haven't We Solved It? (Ultimate TLE & MLE)

Why don't we just run a DFS with memoization from S_0?

  • Number of legal positions (States): ~ 10^44
  • Game tree complexity (Variations): ~ 10^120

For comparison, there are only about 10^80 atoms in the observable universe. Even with #pragma GCC optimize("O3"), storing a dp table of size 10^44 gives an instant MLE and TLE in our universe.

3. What Have We Solved So Far? (Bottom-Up DP)

Since top-down DFS from the start is impossible, computer scientists used bottom-up DP (retrograde analysis) starting from checkmates.

Today, chess is 100% solved for any position with 7 or fewer pieces (Syzygy Endgame Tablebases). This precomputed DP array takes about 140 Terabytes of storage. The moment only 7 pieces remain on the board, engines don't calculate anymore—they just do an O(1) lookup and play mathematically perfect chess.

(Note: Engines like Stockfish and AlphaZero do NOT play optimal chess from move 1. They use Alpha-Beta pruning + neural network heuristics to guess the dp value of states at depth 40–50).

Conclusion: Who Wins?

While dp[S_0] is still unproven, the overwhelming consensus among Grandmasters and AI researchers is that dp[S_0] = 0. White's first-move advantage is too small to force a win against perfect defense.

If Alice and Bob play chess optimally, the output is almost certainly Draw.

What do you think? Will quantum computers ever help us solve 8-piece or 9-piece tablebases, or is chess forever safe from being fully solved?

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by AzizbekSabirov (previous revision, new revision, compare).

»
3 weeks ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Yeah from my experience i also think that there must be a optimal way to win the chess game but idk jamikdev

»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Elon Musk argued this with the Chess.com account on X the other day

»
3 weeks ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

Has it yet been rigorously proven that black cannot force a win? Intuitionally it seems obvious the answer is no but I can't seem to think of any reasonably fast way to prove it.

»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

what a blogg u actually thought

»
3 weeks ago, hide # |
← Rev. 2  
Vote: I like it +8 Vote: I do not like it

Engines like Stockfish and AlphaZero do NOT play optimal chess from move 1

I don't know how sure we can be of this. If optimal play results in a draw, it's plausible that you actually have to go several moves in before a suboptimal move is made. It's also plausible to me that many of the matches between powerful engines consist entirely of optimal moves; most of them end up in draws, after all, and IIRC, tournaments like TCEC need to starting games far into unusual openings in order to avoid always drawing.

  • »
    »
    3 weeks ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    theoretically, if we were to place two absolutely identical chess engines against the board, even if their chess rating would be 100, i am pretty sure that 90% of games would result in a draw

»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I never recommend t play with strategy in 1+0 chess game.

»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Being a 1400 rated chess player in past, Playing chess optimally will just consume lot of time depending on your opponent and if the opponent is also playing optimally then the game will js end in draw and the time complexity will be the worst case which is O(b raised to d) where b is branching factor and d is depth of the game in plies, overall chess is not so forever safe from being fully solved but as of now it is pretty safe

»
3 weeks ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

Once I found a forum thread with guys that collected 7-piece tablebase. They discussed that its not really difficult to create 8 and 9 piece tablebase. Some slight code optimizations could be done. The reason nobody created 8, 9 is just because it requires collective effort, a lot of hardware, a lot of storage. But not like million terabytes, no, quite reasonable amount like 10 people, few terabytes each, a dozen cores, and a few months of computation.

So, basically, its not hard to create 8 and 9, there is no value in it, nobody will pay you for this significant effort. Sad story. I'm thinking maybe it should be some distributed system made in such a way that million people can contribute 5 minutes of their laptop cpu time and its done. There are examples of such projects, massively distributed. Maybe blockchain could be a base for such a solution. "Syzygy-coin".

Also want to add one thought here. Game tree complexity is like 10^100. Yes it might be true. But people study theory of debuts for centuries and it seems that there are some narrow paths in this tree that are reasonable and 99.999% are bad moves. So maybe there is a way to drastically reduce complexity and it will not be a TLE anymore.

»
3 weeks ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

AI generated?

»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I thought bro was gonna share some gambits and ideas with moves