In the game of Tic Tac Toe (knots and crosses for our English brothers out there), it doesn’t take long to learn the strategies to employ so that you can guarantee that you can AT LEAST get a tie in every game, and possibly win depending on mistakes from your opponent. This is what we call a “solved game” - you can gurantee a minimum result, we know how to gurantee it, there’s no way around that strategy and it’s fully understood.
Zermelo’s Theorem is a theorem that there is a much broader category of game that you can apply that same sort of thinking about. This broader category includes games like Chess and Go, games that aren’t solved, games that are so complex and massive in the space of possibilities that they seem impossible to solve. Zermelo’s Theorem states, effectively, that Chess and Go are just like Tic Tac Toe in that way - that there is a flow-chart of perfect strategy, and if the perfect flow chart were available to both players, one of the following statements would necessarily be true:
White can gurantee a win
Black can gurantee a win
Both players can gurantee a draw-or-better (a draw, when they’re both perfect)
Zermelo’s Theorem may seem intuitive to some of you. It seems intuitive to me (I thought of the idea indepdently, though certainly not the proof). Yet intuitive as it is, it still feels… shaky, somehow. Like if I were to be challenged on it, I certainly wouldn’t be able to prove it. I’m not sure I’d even be able to make a great argument for it. Not in the context of something like Chess.
How can you, in plain language, convince another rational person that Chess is as in-principle-solvable as Tic Tac Toe is? I’ve not read the proof of Zermelo’s Theorem myself, but I doubt it’s as plain-language as I’m looking for.
Mathematically, the game of chess can be modeled as a directed graph, where each node is a game state and each edge is a legal move. To say that white can guarantee a win is just to say that there is a sub-graph such that:
At every white-to-move node, the sub-graph contains exactly one outgoing edge
At every black-to-move node, the sub-graph contains all legal outgoing edges
Every terminal node of the sub-graph is “checkmate for white”
The existence of such a sub-graph for white rules out the existence of such a sub-graph for black. This is because the sub-graph covers all of the black’s possible responses. So either this type of sub-graph exists for one color, or it exists for neither color.
So, how to express this in “plain” language? Maybe something like:
If both colors had a winning strategy that always worked, then they would both be able to follow it in the same game, which is a contradiction. So either one color has a winning strategy, or neither do.
It does seem pretty exhaustive for a turn-based full-information game. It basically boils down to asking whether either player has a winning move from the outset, and if not, well then it’s a draw with best play.
I guess one wrinkle is the “full-information” part. Very obviously with chess, Go etc of course, although the information is there, the calculation tree is far too broad to be practically calculated – hence why we can still play and enjoy these games. There may be other ways that “full information” does not map trivially to knowledge of what move to play, like trees of “I know that you know that he knows that I know that…”
Also, as a minor semantic thing, there can be outcomes that are forced without either player being the one that forced it. For instance, a chess game where the only legal move is to resign. Black always wins, but black won’t even get to play a move
I think the problem is that, for people who don’t intuit that Zermelo’s Theorem is true, they don’t think either color has a strategy that ALWAYS works, they think each color may have a strategy that sometimes works.
I like the graph idea, though I can’t say I fully understand it. Don’t know enough about graph theory.
Yeah, I agree that this can be a stumbling block for some people. I think the bottom line is that it will be difficult for someone to grasp how Zermelo’s Theorem applies to Chess unless they can grasp the idea that, in Chess, there is no difference between saying that a strategy “sometimes works” and saying that the strategy only works when the opponent makes a mistake. That is, there has to be some understanding of what “best play” means at a purely theoretical level.
Sure, so maybe that’s the place to concentrate on building some intuition. The basic idea is that there is a winning strategy for white when, for any move black could possibly make, there is always at least one move that white could make in response that eventually leads to white checkmating black. How does that land?
Perfect, easily applicable to end-game positions like mate-in-2 or 3 or 4 or etc positions, but not easy to see how it extends all the way back to move 1.
Yes, and the way you’ve formulated this is actually quite incisive. To say that there is a winning strategy for white is basically equivalent to saying that white has a forced checkmate in X moves (or less) starting from the first move. Since Chess isn’t solved, we don’t actually know whether this is true or not (most researchers think Chess is a forced draw), or how many moves “X” would be if it were true. But that’s the basic idea.
There’s no shame in that. When used responsibly, AI can be a great tool for achieving understanding.
The thing to remember is that just because Zermelo’s Theorem is true, and if there is a path in the game tree that guarantees a win for white, that does not mean that we can practically ever find this path. The reason is that the game tree may branch in a prohibitively wide fashion, such that we cannot effectively compute a path from the first move and a guaranteed mate.
