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?