68
$\begingroup$

Zermelo's Theorem, when applied to chess, states:

"either white can force a win, or black can force a win, or both sides can force at least a draw [1]"

I do not get this. How can it be proven?
And why do people lose in chess then, if they can force a draw at least?

$\endgroup$
30
  • 122
    $\begingroup$ People lose in chess because people don't play perfect games. $\endgroup$
    – Git Gud
    Commented Jul 7, 2014 at 16:36
  • 13
    $\begingroup$ People still lose in chess because the state space is so large. A general winning strategy is very difficult to find even with really good computers. $\endgroup$ Commented Jul 7, 2014 at 16:37
  • 14
    $\begingroup$ @Brika: what you just said is obviously false. Otherwise, if both sides played perfectly, they would both win. $\endgroup$
    – TonyK
    Commented Jul 7, 2014 at 16:45
  • 65
    $\begingroup$ I've even see people lose in Tic Tac Toe unnecesarily ... $\endgroup$ Commented Jul 7, 2014 at 17:02
  • 8
    $\begingroup$ @Brika: That's also obviously false. Every time a game doesn't end in a draw, that means the winner payed perfectly? $\endgroup$
    – TonyK
    Commented Jul 7, 2014 at 17:21

8 Answers 8

102
$\begingroup$

The theorem is about perfect players.

Assume you were able to enumerate and evaluate all the gazillion chess positions. Then the following can happen:

  1. You find out that you can force a win as white, no matter how well black plays
  2. You find out that even with your best play, you cannot force a win as white if black plays well enough
  3. You find out that you can force a win as black, no matter how well white plays
  4. You find out that even with your best play, you cannot force a win as black, if white plays well enough.

In fact, with your complete knowledge, you will find out that exactly one of 1 and 2 holds (but we imperfect beings don't know which): either you can or you can't force a win.

Similarly exactly one of 3 and 4 must hold.

Of course, 1 and 3 cannot hold simultaneously. That leaves us with three exhaustive and mutually exclusive options in total:

  1. A perfect white player can force a win
  2. A perfect black player can force a win
  3. None of the above. That is: if only they play well enough, both white and black can avoid losing. In other words, both can force at least a draw (though they may win against a stupid opponent).

Real life people (and computers) lose because the premise of the above is not fulfilled for them: nobody has perfect knowledge of all chess positions.

We do have perfect knowledge about simplified games, for example chess endgames with very few pieces. The perfect knowledge about these even led to a change in chess rules regarding the 50-move-rule, because endgames were discovered that could be won, but might require more than 50 moves. More precisely (thanks to Voo's comment): The 50 moves rule was changed so that if you could show you'd win in $N$ moves with $N \le 100$ it would still be allowed (and players had to agree on which positions that extension was allowed and god knows what else) and then abolished again later on. In §9.3 of the current FIDE rules the 50 moves rule is once again strictly enforced.

EDIT:(inspired by vaxquis' comment) The above considerations are not specific to chess, they apply to a large class of games, the important properties of these games being that there are no elements of secrecy or probability (e.g. Poker fails on both these criteria because the cards are dealt at random and only you know your own hand):

  • TicTacToe is so simple that one can enumerate all possibiliteis by hand to show that no side can force a win
  • Who can force a win in Nim (a draw is not possible by the rules) depends on the specific variant and the starting position, but the analysis is not too complicated and may be done in introductory courses - or even by puzzlers
  • That Nine men's morris is a draw was found by a lot of brute-forcing (plus smart ideas)
  • In 2007, it ws found that Checkers is a draw, also by the use of massive computer power
  • It is a "two-liner" to show that the game of Hex can be won by the first player ("strategy stealing"). Nevertheless, explicit winning strategies are known only for small boards (again, by throwing CPU power at the problem)

Wikipedia has a nice overview listing more games that are more or less solved.

$\endgroup$
8
  • 2
    $\begingroup$ There was that Russian guy, about the same time as Fischer and Spassky, who specialized in draws. Cannot remember the name. $\endgroup$
    – Will Jagy
    Commented Jul 7, 2014 at 17:57
  • 4
    $\begingroup$ Probably Petrosian, actually Armenian. $\endgroup$
    – Will Jagy
    Commented Jul 7, 2014 at 18:04
  • 5
    $\begingroup$ Good answer, just to nitpick: The 50 moves rule was changed so that if you could show you'd win in N moves with N <= 100 it would still be allowed (and players had to agree on which positions that extension was allowed and god knows what else) and then abolished again later on. In current FIDE rules the 50 moves rule is once again strictly enforced (§9.3). $\endgroup$
    – Voo
    Commented Jul 7, 2014 at 20:46
  • 3
    $\begingroup$ It would be the perfect answer if you'd give an example of e.g. checkers, which has been proven mathematically to be solvable, quote: "A brute force approach that took hundreds of computers working nearly 2 decades was used to solve the game, showing that a game of draughts will always end in a stalemate if neither player makes a mistake." - game proven to be unwinnable with optimal strategy, the same way 3x3 TTT is $\endgroup$
    – user81774
    Commented Jul 8, 2014 at 0:16
  • 9
    $\begingroup$ @vaxquis 3x3 Tic-tac-toe, and Global Thermonuclear War. ;) $\endgroup$
    – Ajedi32
    Commented Jul 8, 2014 at 14:20
19
$\begingroup$

Answering to a comment which seems to be closer to the core of the issue here:

In every game, if people play a perfect game they win and they lose otherwise. What is the utility of the theorem then, please?

The theorem allows you to classify games. Assuming all players play perfectly, there are games where the beginning perfect player will always win, others where the player to make the second move will always win, and still others where any tournament between perfect players will lead to a draw. So it says that you can classify (deterministic finite perfect-information two-player) games into these three categories.

As others have already stated, perfect players for chess are hard to come by, so at the moment (and for the forseeable future) we don't know which of these categories chess falls into. But we do know – thanks to the theorem – that it must fall into one of the categories.

The relevance of this finding for actual chess players is zero. The relevance for game theorists is a bit larger, but obviously the theorem is most useful in those cases where you can actually determine (in reasonable time) which of the three cases holds, like e.g. Tic Tac Toe. Once you have analyzed a gaim sufficiently to know the perfect strategy, and are able to remember that strategy (as Voo pointed out), then the game will likely become boring. That's the reason why there are no world championships for standard Tic Tac Toe: all games would be draws, since it falls into the “both players can force at least a draw” category. For some other games, perfect strategies are known as well, and more might join that club eventually.

Come to think of it, there might be one possible application of Zermelo's theorem for chess players: blaming frustration after a lost game on the game design. “I did play perfectly, but unfortunately so did my opponent, and the game is designed in such a way that I had to loose it.” A claim which is hard to believe but also not easy to refute. The part about the game being designed in such and such way is this classification I've mentioned, which is unknown so far. So you'd have to show that the speaker did make some suboptimal move at some point. (If his opponent did make a suboptimal move, and the speaker lost anyway, that means the speaker must have made such a move as well.)

$\endgroup$
2
  • $\begingroup$ To be fair the perfect strategy for most games even if known would be impossible for humans to follow through. I mean I've read the paper that proved that checkers will always end in a draw, but it's still an interesting game to play.. and I still loose sadly ;-) $\endgroup$
    – Voo
    Commented Jul 7, 2014 at 20:51
  • 7
    $\begingroup$ There's the game "Chomp" where it is known that first to play has a winning strategy (but nobody knows the strategy in non-trivial cases). That's the case because (a) there is no draw, only in and lose and (b) the first player to play and only he can waste one move. Either wasting one move forces a win, or doing the opponent's optimal strategy after the wasted move forces a win. $\endgroup$
    – gnasher729
    Commented Jul 8, 2014 at 14:18
9
$\begingroup$

Here's an intuitive definition for what a "winning strategy" is.

We define recursively what it means to "have a winning strategy" for any given state of the game.

  1. If at a particular game state, it's your turn, and there is a move you can make that'll win you the game (right away), you have a winning strategy for that state.

  2. If it's the opponent's turn, but all of the moves available to them lead to states in which you have a winning strategy, then you have a winning strategy for that state.

  3. If it's your turn, and at least one of the moves available to you leads to a state in which you have a winning strategy, then you have a winning strategy for that state.

This definition does break down a little for games like chess that can theoretically go on forever (since there might not be a place to start the recursion in some cases), but it works for games with a guaranteed end (like Tic Tac Toe) and provides some intuition about what mathematicians mean when they say that a player can "force a win".

I suppose the answer to your question - why do people lose, if there exists a winning strategy - lies in point (3). At least one of the moves available to you leads to a state in which you have a winning strategy. But you need to be smart enough to know which move that is.

I should mention that I've never studied game theory, so I don't know exactly what the definition used in Zermelo's theorem is. I'm assuming that whatever it is, it would be equivalent to mine, but I could be wrong.

$\endgroup$
2
  • 4
    $\begingroup$ Because of the 50-move rule, we can assume the game tree is finite. Include in your notion of "position" a counter of the number of moves that have passed without a pawn being moved or a piece being taken. In any position where that counter is 50 or more, the move "I claim a draw" can be played, which immediately draws the game. That will be the player's best move in situations where the opponent would have a winning strategy if the 50-move rule were ignored. $\endgroup$ Commented Jul 8, 2014 at 8:58
  • $\begingroup$ Hmm your definition reminds me of the Hangman's Paradox; but I guess there's a difference en.wikipedia.org/wiki/Unexpected_hanging_paradox $\endgroup$
    – Ovi
    Commented Sep 26, 2018 at 4:45
4
$\begingroup$

People lose because nobody knows how to force a draw.

It may be possible, but no one knows how (if at all possible) and this is what keeps chess interesting.

On the other hand, you can force a draw in tic tac toe, and since it is really easy to learn a strategy that ensures that, games of tic tac toe are not that interesting.

$\endgroup$
5
  • 10
    $\begingroup$ How do you know that forcing a draw is possible? Perhaps a perfect white player could always force a win? $\endgroup$
    – MvG
    Commented Jul 7, 2014 at 17:18
  • $\begingroup$ @MvG: Yes, and perhaps Goldbach's conjecture is false. $\endgroup$
    – TonyK
    Commented Jul 7, 2014 at 21:21
  • 7
    $\begingroup$ @TonyK I think if I had to choose between the two, I would say 'Chess is a first-player win' is orders of magnitude more likely than Goldbach's conjecture being false. (Contrariwise, I think a case could be made that Goldbach being false is marginally more likely than chess being a win for black!) $\endgroup$ Commented Jul 7, 2014 at 21:26
  • 2
    $\begingroup$ @TonyK: There is strong evidence for Goldbach's conjecture. Although there are strong opinions by experts in support of your claim, I'd hardly see this as scientific evidence. $\endgroup$
    – MvG
    Commented Jul 7, 2014 at 22:20
  • 1
    $\begingroup$ Rather than saying "it's possible" it's more correct so say "it may be possible" because the truth is, we don't know yet. $\endgroup$
    – slebetman
    Commented Jul 8, 2014 at 2:33
3
$\begingroup$

In the statement, there are three disjoint sets:

A) White can win.
B) Black can win. C) Either White or Black (or both) can force a draw. (We won't go into the subsets of this, since the outcome is the same--a draw.)

The union of these three sets $A \cup B \cup C$ is just the whole space of possible outcomes.

$\endgroup$
3
  • 3
    $\begingroup$ Using union in an answer is not a sufficient reason to use a set theory tag. Even less the set-theory one. $\endgroup$
    – Asaf Karagila
    Commented Jul 8, 2014 at 2:27
  • 3
    $\begingroup$ And how does this answer the question? Also, set union is associative so there's no need to bracket $A\cup B\cup C$. $\endgroup$ Commented Jul 8, 2014 at 9:01
  • 1
    $\begingroup$ @DavidRicherby: It might answer the question. It's what an English major would call "parsing." That is, my theory was that the OP misunderstood the statement, and if so, drawing a Venn diagram for him might help. (And I removed the "parens," not "brackets.") $\endgroup$
    – Tom Au
    Commented Jul 8, 2014 at 14:10
1
$\begingroup$

You are looking at it wrong. It may be easier to understand if stated more precisely;

"Either 1) it is true that White can force a win, or else 2) it is true that Black can force a win, or else 3) neither White nor Black can force the other to accept a loss."

That is, the theorem sets out the possiblities. It does not say which of those three possiblities are actually true. It merely states that one of them must be. I suppose you could take a stronger view; it says that one must be, and only one can be.

Most people would guess 1 or 3, but no one knows.

$\endgroup$
1
$\begingroup$

Thinking about games of perfect information for games other than chess in some respects is more instructive. If one sees the game of Nim for the first time - two players alternating taking one or more "stones" from a single heap of different heaps of stones, it may seem interesting and challenging to play. However, it is now known that one can look at an initial position and determine if there a "win" for the next player to move or not. If the next player to move has a winning position he/she may not play optimally but no matter how the other player plays that player will lose if the position is a winning position for the player to move, and that player plays optimally. So in a sense Nim is a mathematically interesting game (non-trivial mathematical analysis) but boring to play for informed players. By comparison the game of Hex can be shown to be a win for the first player. However, on large hex boards it is not known how the first player can take advantage of the fact that he/she is known to have a forced win. It is also known that if the second player can specify the first move for the first player, then the second player will have a forced win, but again without any way of knowing how to play optimally. Hex and Nim can't end in a draw. There is lots of pretty mathematics and interesting new questions related to combinatorial games.

$\endgroup$
0
$\begingroup$

This breaks down to four statements:

  • White can force a win
  • Black can force a wim
  • White can force a draw
  • Black can force a draw

The rules of chess ensure that at least one of these outcomes happens. Also notice that it's one player causing the outcome to happen.

Now, regarding your statement: "And why do people lose in chess then, if they can force a draw at least?"

They can indeed force a draw. That's one of the possible outcomes. But for a particular match, that wasn't the outcome. The other player forced a win.

This statement doesn't imply that players can always force a draw instead of losing. Forcing a draw takes skill. It means that you played well enough that your opponent didn't win. But if your opponent is much better than you are, they can force the win.

$\endgroup$
5
  • 4
    $\begingroup$ You write “they can indeed force a draw”. How do you know that? $\endgroup$
    – MvG
    Commented Jul 7, 2014 at 17:18
  • $\begingroup$ Your first four statements can not all be true. So it may be that white or black can always force a win. $\endgroup$ Commented Jul 7, 2014 at 17:37
  • $\begingroup$ This answer analyses the statements correctly, but doesn't really answer the question. In the last two paragraphs you start talking only about player skill and specific games. The theorem is absolutely true, and does not depend on the skill of the players in any given game. So: there's the core of an excellent answer here, but you need to say more about chess in the abstract, as applied to all chess games. $\endgroup$
    – Tynam
    Commented Jul 7, 2014 at 17:47
  • 3
    $\begingroup$ @John You're misunderstanding the problem. By "forcing a draw" the question is really saying "forcing a draw from the first move". Not from some random board position. The real answer is that chess has so many states that we still don't know which type of game it is "white always wins", "black always wins" or "always end in a draw"? Not even with the help of computers. It took us 20 years to run all possible games of checkers to find out that checkers is a game that always ends in a draw if nobody makes any mistakes. $\endgroup$
    – slebetman
    Commented Jul 8, 2014 at 2:41
  • $\begingroup$ @slebetman @ Tynam Thanks for the explanations. I understand now that I didn't understand. :) $\endgroup$
    – John
    Commented Jul 8, 2014 at 18:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .