In commenting on the game of chess, “Will Baude”:http://www.crescatsententia.org/archives/2004_09_05.html#004389 notes the following.
bq. Professor Leitzel of Vice Squad writes in to remind me of the 1913 Zermelo’s Theorem, which establishes just that: given the game’s finiteness (established above), there exists some strategy s.t. either white always wins, black always wins, or nobody does.]
Not so, as it happens, although it’s been the conventional wisdom among game theorists until recently – the inestimable James Morrow (whose “Game Theory for Political Scientists” I’m using as a coursebook this semester) states it a little more formally when he says that
bq. Zermelo showed that chess has a winning strategy: White can force a victory, Black can force a victory, or either can force a draw.
But, as discussed on my old blog last year, this “very interesting paper”:http://www.math.harvard.edu/~elkies/FS23j.03/zermelo.pdf by Ulrich Schwalbe and Paul Walker, shows that Zermelo said no such thing. Zermelo proved a much narrower result, and indeed explicitly states that he _hasn’t_ proved that chess has a winning strategy.
bq. The question as to whether the starting position … is a winning position is open. Would it be answered exactly, chess would of course lose the character of a game at all.
It would be very interesting to trace back how this error (and a variety of others) crept into the literature. Zermelo was never translated into English before Schwalbe and Walker’s paper, so I imagine that nobody much bothered to try to read him (especially since his article was published in 1913 and was quite likely printed in Fraktur). One person’s error was presumably picked up by others, and then disseminated until it became accepted dogma in the wider literature. Academic research sometimes resembles a game of Chinese whispers – because we all rely on the research of others, serious blunders can be perpetuated for generations before someone bothers to go back and recheck the work of their elders.
Update: Peter Northup has convinced me in comments and email that I’ve misunderstood Zermelo a little myself, and that the formulation that Morrow uses isn’t as offbase as I thought it was. What’s clear is that game theorists are incorrect in saying that Zermelo used backward induction as such, and that he doesn’t show that there is a winning strategy _as such_. I stand corrected.
{ 38 comments }
dsquared 09.08.04 at 8:47 pm
Ahhh. This looks like ambiguity in the definition “chess”. Zermelo treated chess as a potentially infinite game, which it is …. unless.
Unless you play by the FIDE rule which basically makes the game finite by declaring certain sequences of moves (basically, if some large number of moves has been made, no piece has been taken and no pawn has been moved) to be draws by stalemate. If it’s possible to force a draw by “running out the clock” then chess is finite and Zermelo’s theorem is true for chess. But if you don’t accept this somewhat arbitrary restriction, chess is not finite and Zermelo’s theorem is not proven for chess.
(I think)
Doug 09.08.04 at 8:50 pm
Oh yeah, to say nothing of scholarship left in obscure backwaters. F’rexample, if you read Gleick’s Chaos, you learn that Julia sets and the rest of the fractal iconography were pretty much sitting around after discovery in the late 19th century until Mandelbrot came along. Between the things that are wrong and the things that are forgotten, it’s a wonder we know anything at all.
amusedfrog 09.08.04 at 8:50 pm
Of course, I cannot prove it, but I am sure that the vast majority of professional chessplayers would agree: two opponents playing perfectly would always draw.
One empirical evidence for that: the higher the level of the players in a tournament, the larger the proportion of games ending in a draw.
amusedfrog 09.08.04 at 8:57 pm
Dsquared wrote
“Unless you play by the FIDE rule which basically makes the game finite by declaring certain sequences of moves (…) to be draws by stalemate. If it’s possible to force a draw by “running out the clock” then chess is finite and Zermelo’s theorem is true for chess. But if you don’t accept this somewhat arbitrary restriction, chess is not finite and Zermelo’s theorem is not proven for chess.”
I am not sure about your point: after all, there is a finite number of positions possible on a chessboard. Even if the FIDE rules allowed to repeat the same position ad eternam, it would not change a drawn position into an winning or losing one.
Matt Weiner 09.08.04 at 9:03 pm
by declaring certain sequences of moves (basically, if some large number of moves has been made, no piece has been taken and no pawn has been moved) to be draws by stalemate
Utter nitpickery–I think this should be called a “draw by the 50-move rule”; “stalemate” IIRC is a technical term for a situation in which a player has no legal move but is not in check. Will Baude explicitly cites the 50-move rule, so he’s got the finite game in mind. (IIRC again there are some situations in which the limit on the 50-move rule goes up–king, rook, and bishop versus king and rook, and maybe king, bishop and knight versus king. [UPDATE: not any more–the 50-move rule is now exceptionless.)
Adam Stephanides 09.08.04 at 9:44 pm
But it looks to me like the penultimate paragraph of Zermelo’s paper says that he at least thought he had proved that “White can force a victory, Black can force a victory, or either can force a draw.” (Whether the gap in Zermelo’s paper that Koenig pointed out renders this part of Zermelo’s argument invalid is something I’m not sure of, and I’m not going to spend time figuring it out. In any case, Zermelo later filled in the gap.) Nor do Schwalbe and Walker claim that Zermelo did not think he had proved this; instead they argue that this was not Zermelo’s major interest in the paper. (I’m not sure they’re correct.) The final paragraph of Zermelo’s paper, which you quote in part, only says that it’s not known which one of the three possibilities is true for the initial position, not that none of the possibilities might apply.
“If it’s possible to force a draw by “running out the clock†then chess is finite and Zermelo’s theorem is true for chess. But if you don’t accept this somewhat arbitrary restriction, chess is not finite and Zermelo’s theorem is not proven for chess.”
No, Zermelo treated chess as not finite, and infinite games as being drawn. With this provision, “Zermelo’s theorem” is true.
Something Polish 09.08.04 at 9:47 pm
Casey Stengel:
“Now, there’s three things you can do in a baseball game. You can win, or you can lose, or it can rain.”
Does that help?
bob mcmanus 09.08.04 at 10:21 pm
ftp://ftp.cis.uab.edu/pub/hyatt/TB/
Went out to check the endgame tablebases. Seem to be somewhere around halfway through the six-piece series(includes kings) which will probably take a couple terabytes of storage.
Zermelo will be vindicated empirically, any day now.
Henry 09.08.04 at 10:33 pm
Adam, as I understand Zermelo, what he’s saying is that Black can force it, White can force it, or one can force it from a draw _if the player is already starting from a winning position_. In other words, it’s a quite limited proof, which doesn’t at all set out to prove whether there is a winning strategy as such for the game of chess, which is how it’s been interpreted.
Herb 09.08.04 at 10:34 pm
Regarding grandmaster draws, those are prevalent, not due to the position being a draw, but more often neither player wants to risk anything, especially in a final round. Split the point, split the money, rather than risk no point and no money.
Walt Pohl 09.08.04 at 10:37 pm
Attributions of mathematical theorems are almost always wrong.
But isn’t Zermelo’s theorem actually true? Or is there a counterexample (for some infinite zero-sum game)?
John Quiggin 09.08.04 at 10:51 pm
I’m obviously missing something here. Given the 50-move and repetition rules, the game must end in a bounded number of moves, and so one of Zermelo’s three options must apply. I’m pretty sure I could run up a proof of this in short order.
If we didn’t have these rules, then the outcome of known no-win positions (for example, two kings, no other pieces) would be determined by Sitzfleisch. The more determined player could simply refuse all offers of draws and wait for the other to resign. By backward induction, the less determined player should resign immediately.
kmoney 09.08.04 at 10:59 pm
I think perhaps some of you are missing a subtle point in the article: mathematical errors are propogated through society as a whole, in what could be regarded as a “top-down” model.
Of course the phenomenologists out there will know exactly where I’m coming from.
:)
frankiejr 09.08.04 at 11:03 pm
i have a hamster named chess.
Jim Harrison 09.08.04 at 11:19 pm
About draws: years ago i disabled a chess playing program so that it played random moves for both sides. Oddly, the result was usually a win, not a draw, at least in the somewhat limited sample of games I was able to run. It may be that the “natural” outcome of a chess game is decisive and that it takes intelligence to find the relatively smaller set of indecisive outcomes.
I’d love to know if anybody with better programming skills and a more powerful computer has ever done a comparable experiment—i certainly wouldn’t want to make a very strong claim based on my very amateurish efforts.
Peter 09.08.04 at 11:21 pm
“Zermelo showed that chess has a winning strategy: White can force a victory, Black can force a victory, or either can force a draw.”
That’s an incorrect statement. If either can force a draw then neither has a winning strategy. That each player has an optimal strategy is basic game theory. The “disagreement” comes down to Zermelo using technical terms accurately and Morrow doesn’t.
Bruce Cleaver 09.08.04 at 11:42 pm
David Levy has calculated the game ends in at most 3150 moves due to the 50-move rule.
A chess position can be described in 160 bits at most, and probably a little less, implying 2^160 unique positions (about 10^48). The tablebases are indeed at 6-man right now, but there are ways to grow them without needing every position. I once calculated a database of about 10^15 Terabytes would suffice for unbeatable (but not absolutely optimal) chess. Interested parties may email me for the argumaents and calculations…
Bruce Cleaver 09.08.04 at 11:47 pm
Arghh! In previous post it should read “2 to the 160th power” and “10 to the 48th power”, but the HTTP gremlins ate my carets.
Stephen Samuel 09.08.04 at 11:52 pm
There is another draw rule that I know —
“If exactly the same position occurs three times in a game then a player may claim a draw.”
If we presume that a three-peat WILL result in a draw, then, with theoretical number of possible board positions being N, the maximum number of moves in a game can be trivially proven to be less than 4N (I’m presuming that each position with black to move next and with white to move next is considered unique) It’s less than 4N, since some positions are not repeatable. (stalemates, checkmates and check with the only escape being the capture of the threatening piece.)
This, of course, ignores the problem of storing a list of all possible moves, and only considers the question of theoretical finiteness
Jason 09.09.04 at 1:04 am
From the link someone posted, the 50-move rule is voluntary, and thus does not force a game end. Likewise with the repeating positions rule (it’s funny, I always thought it was 3 repeated moves, but I guess I was wrong).
Tom 7 09.09.04 at 1:47 am
What’s the supposed error? I don’t get it. Chess is finite, so there exists a (winning or drawing) strategy for white or black. This is obvious.
c 09.09.04 at 2:35 am
In 1913 German was almost as important as English is now. So claiming that nobody much bothered to try to read him may be incorrect.
Peter Northup 09.09.04 at 2:47 am
I have to defend my Will Baude, my fellow Crescateer, here–
First, as Adam (above) already said (but it bears repeating, because Henry’s comment reproduces the confusion): Zermelo DID prove that either white has a winning position, black has a winning position, or neither does, that is, both players can stave off defeat indefinitely (because he was ignoring the 50 move rule). It’s in the penultimate paragraph of the proof. It’s just that, as Schwalbe and Walker emphasize, this wasn’t his main concern; he was more interested in putting a bound on the number of moves it takes to win GIVEN that someone has a winning position.
One might quibble with the way Baude and Morrow phrase it–in particular, for Morrow to use the phrase “winning strategy” is a bit misleading, but since in the *very same sentence* he clarifies by saying that he means either W wins, B wins, or both can force draw, I don’t think it’s a big gaffe. One might similarly say “tic-tac-toe has a winning strategy” meaning “a sequence of optimal play for each player” (with perhaps a connotation of “that avoids losing” tacked on); it’s hardly an abuse of language.
Peter Northup 09.09.04 at 2:48 am
I have to defend my Will Baude, my fellow Crescateer, here–
First, as Adam (above) already said (but it bears repeating, because Henry’s comment reproduces the confusion): Zermelo DID prove that either white has a winning position, black has a winning position, or neither does, that is, both players can stave off defeat indefinitely (because he was ignoring the 50 move rule). It’s in the penultimate paragraph of the proof. It’s just that, as Schwalbe and Walker emphasize, this wasn’t his main concern; he was more interested in putting a bound on the number of moves it takes to win GIVEN that someone has a winning position.
One might quibble with the way Baude and Morrow phrase it–in particular, for Morrow to use the phrase “winning strategy” is a bit misleading, but since in the *very same sentence* he clarifies by saying that he means either W wins, B wins, or both can force draw, I don’t think it’s a big gaffe. One might similarly say “tic-tac-toe has a winning strategy” meaning “a sequence of optimal play for each player” (with perhaps a connotation of “that avoids losing” tacked on); it’s hardly an abuse of language.
SickMind Fraud 09.09.04 at 3:52 am
This reminds me very much of a story about Aturo Toscanini in rehersal of (I believe) a Tchaikovsky symphony with some famous orchestra or another.
Essentially, he caught them playing a particular passage wrong, which apparently they had been doing for over 50 years. They had learned it wrong in the first place, and had passed the error down through the generations, until Toscanini forced them to play it correctly. Again, a matter of not checking the original materials.
Pedro 09.09.04 at 6:12 am
Chess is an infinite game. But the conclusion of Zermelo’s Theorem holds for it.
David Cantrell 09.09.04 at 9:44 am
I’ve always believed that the repetition rule was the same as in Go – returning the board to a state it has been in before is illegal.
Marco Vervoort 09.09.04 at 11:17 am
Actually, Martin proved that infinite perfect-information zero-sum games are determined as long as the payoff function is Borel [Annals of Mathematics 102, 1975]. Which indeed means that Chess without drawing rules, or any other potentially infinite game that can be defined without recourse to something like the Axiom of Choice, has a winning strategy for one of the players or drawing strategies for both.
yabonn 09.09.04 at 12:14 pm
… visions of the Two Last Chessmachines, computing endlessly the One Last Game, doomed to repetition or to lose/draw a winning position…
Mike 09.09.04 at 1:37 pm
Cogley: How many games of chess did you win from the computer, Mr. Spock?
Spock: Five in all.
Cogley: May that be considered unusual?
Spock: Affirmative.
Cogley: Why?
Spock: I personally programmed the computer for chess months ago. I gave the machine an understanding of the game equal to my own. The computer cannot make an error. Assuming that I do not either, the best that could normally be hoped for would be stalemate after stalemate, and yet I beat the machine five times.
– Star Trek, “Court-Martial”
Adam Stephanides 09.09.04 at 2:21 pm
“I’ve always believed that the repetition rule was the same as in Go – returning the board to a state it has been in before is illegal.”
No, it’s perfectly legal, but if the same state occurs three times then the game is drawn (providing a player calls it).
That’s not the rule in go, either, at least not in the Japanese rules, which I believe are the most widely used rules in the U.S. It’s only illegal to play a move which returns the board to the state before your opponent’s last move. Other repetitions of positions are legal–for example, triple ko, where there are three kos on the board and the players take them in rotation–and if neither player will yield the game is declared “no result.”
“Actually, Martin proved that infinite perfect-information zero-sum games are determined as long as the payoff function is Borel [Annals of Mathematics 102, 1975]. Which indeed means that Chess without drawing rules, or any other potentially infinite game that can be defined without recourse to something like the Axiom of Choice, has a winning strategy for one of the players or drawing strategies for both.”
Just to clarify, Martin’s result refers to the case where a game that lasts infinitely long can be either a win or a loss (i. e. some infinite sequences of moves are defined as wins for A, and some as wins for B). Zermelo was assuming that an infinitely long game is a draw, and in that case the result that one or both players has an optimal strategy is elementary.
Getting back to Martin’s case: if there are no restrictions on the payoff function, then it’s actually a consequence of the Axiom of Choice that there are some infinite games in which neither player has an optimal strategy. A good deal of work has been done on set theory without the Axiom of Choice, but with the Axiom of Determinacy, which states that a certain set of such games always has a winning strategy.
Adam Stephanides 09.09.04 at 2:43 pm
“Zermelo was assuming that an infinitely long game is a draw, and in that case the result that one or both players has an optimal strategy is elementary.”
I spoke too soon here. I’m pretty sure it’s true if payoffs are restricted to +1, 0, or -1, as in chess; but if payoffs can be any real number, the situation is more complicated.
C.J.Colucci 09.09.04 at 9:35 pm
In certain positions, it is knmown that a draw is the only possible outcome, even regardless of player error. If there are only 2 kings on the board, no one can win and I can only assume that a draw would bed eclared. (This never happens because players of tournament caliber would see the inevitability of a two-king piosition well in advance of its occurring and agree to a draw.) Likewise, there are well-known positions where, short of outright grotesque player error, a draw is the only outcome. Players usually agree to draws in these circumstances.
Oddly, there has recently been a comoputer proof of a forced win in a position that human players always believed to be a draw in the absence of egregious player error. It takes about 75 moves without either the advance of a pawn or the capture of a piece, and, worse, nobody yet understands the logic of the play, though it can be memorized.
If the position arises in a tournament, or if the player aware of the win is about to embark on move 51, what should haoppen if the other player calles the 50-move rule. Should the other player be allowed to demonstrate the existence of the forced win? (realistically, I doubt anyone could remember a 75-move combination in game conditions if the combination does not conform to the logic used by human chess players, but assume the player is exceptionally relaxed and can demonstrate that he knows the sequence)
Bernard Yomtov 09.09.04 at 10:12 pm
Marco,
What is a Borel payoff function?
Jim Harrison,
Did your random games actually go to checkmate, or did you just decide that some positions were so strong that they were wins?
I would expect a set of random moves to produce a mate almost never, even if one side has overwhelming strength.
dsquared 09.09.04 at 10:54 pm
Bernard, basically all payoff functions that anyone might choose are “Borel functions”; it’s a description of a very wide class of functions indeed. In Marco’s post “proved for all Borel functions” just means to exclude very weird mathematical constructions which take advantage of some of the more outlandish properties of the continuum, and keep the discussion to payoffs that you could measure in dollars and cents.
Bernard Yomtov 09.10.04 at 12:17 am
dsquared,
Thanks. You’re forgiven for that business about Denmark.
Pedro 09.10.04 at 1:35 am
I pass on a paraphrased excerpt of Christian Ewerhart’s 2002 paper “Backward Induction and the Game-Theoretic Analysis of Chess”, appearing on Games and Economic Behavior 39, 206-212. The proof of the result is rather elementary. No need for advanced set theory of any sort.
By a “potentially infinite chess-like game”, we mean a strictly competitive perfect information game with at most three outcomes in which each node has a finite height and a finite number of immediate successors, and in which any infinite path yields a draw. When infinite chess games are taken to be draws–which is a very reasonable assumption, is it not?–the official version of chess is a “potentially infinite chess-like game”.
Mathematician L. Kalmar seems to have proved a theorem in 1929, the proof of which has as a corollary the following:
Corollary: Consider any potentially infinite chess-like game G. Then, if player i cannot enforce a win, then player j can ensure at least a draw.
(Say a node x is a nonwinning position for player i if there does not exist a winning strategy for i in the subgame starting at x)
Proof [reworking of Kalmar’s result]: Note first that, when j is called upon to play at a position x, that is nonwinning for i, then there must exist an immediate successor node of x that is nonwinning for i. To see why, assume to the contrary, in any subgame starting at some immediate successor node of x, player i can choose a winning strategy. Then, in the subgame starting at x, a grand strategy composed of these strategies in the respective subgames will be a winning strategy for i. This, however, contradicts our assumption that x is nonwinning for i. Thus, whenever player j moves at a node x that is nonwinning for i, there is an immediate successor node that is also nonwinning for i.
We can therefore define player j’s action at any such x in the searched for strategy by the requirement that it leads to an immediate successor
node that is nonwinning for i. At all other nodes in G, choose any of the feasible actions for j. This defines a strategy s for player j. Now we claim that any path p generated by s and some strategy of i yields at least a draw for j. This is clear for any infinite path. Assume therefore that p is finite. We will show that the terminal node of p must be nonwinning for i, and therefore yield at least a draw for j. Note first that, by assumption, the initial node of G is nonwinning for i. Hence, it suffices to show that if x is nonwinning for i, the immediate successor node of x on p has the same property. This is clear for any x, at which j is called upon to play, because j’s strategy was precisely defined that way. But this is also true for any node x at which it is i’s turn, because, if i had available a winning strategy in a subgame starting at some immediate successor node w of x, this strategy could be complemented, in a way that i moves from x to w, to a strategy of i in the subgame starting at x. As w was arbitrary, this shows that any successor node of x is nonwinning for i. This proves the theorem.
Adam Stephanides 09.11.04 at 6:29 pm
“Oddly, there has recently been a comoputer proof of a forced win in a position that human players always believed to be a draw in the absence of egregious player error. It takes about 75 moves without either the advance of a pawn or the capture of a piece, and, worse, nobody yet understands the logic of the play, though it can be memorized.
If the position arises in a tournament, or if the player aware of the win is about to embark on move 51, what should haoppen if the other player calles the 50-move rule.”
Iirc, when such positions were first discovered, FIDE adjusted the rules of chess to take account of them, so that in those endgames it took 75 moves (or however many it was) without a capture or pawn move before a draw could be called. Later FIDE reversed itself, and currently the 50-move rule has no exceptions. I don’t know why FIDE changed its mind, but my guess would be that the inconvenience of having players fumble around endlessly (iirc, a position is now known in which it takes over 200 moves w.o. a pawn move or capture to force a win) was felt to outweigh the theoretical possibility of a player being able to execute one of the wins requiring more than 50 moves.
Comments on this entry are closed.