Three of the same card on the flop...
- Thread starter Cloud Nine
- Start date
Hmmm. Well, it was good enough BS to fool the professional mathematics community; Zermelo's theorem and its proof are taught in serious math courses given by the country's most highly rated math departments...not to mention being considered good enough to be named in his honor (not a formal determination...sort of a concensus informal indication of respect by by other mathematicians).
Those are only "arguments from authority", however, and thus not particularly convincing perhaps. But I don't understand your technical objection and so can't address it. The proof (which I am assuming you have read) not only proves that such an optimum strategy must exist but also (which is a non-trivial addition) gives an algorithm by which that strategy could be explicitly constructed/discovered in principle. The one "fly in the ointment", and the only reason that we do not know which of the options enumerated in the Corollary you quoted is the right one, is that it is not computationally practical to execute that algorithm (given the physical limitations on computation imposed by the nature of the universe). But I don't see how the practical difficulty in finding the optimum strategy is relevant to its existence and assume that is not what you mean.
-Ww
Those are only "arguments from authority", however, and thus not particularly convincing perhaps. But I don't understand your technical objection and so can't address it. The proof (which I am assuming you have read) not only proves that such an optimum strategy must exist but also (which is a non-trivial addition) gives an algorithm by which that strategy could be explicitly constructed/discovered in principle. The one "fly in the ointment", and the only reason that we do not know which of the options enumerated in the Corollary you quoted is the right one, is that it is not computationally practical to execute that algorithm (given the physical limitations on computation imposed by the nature of the universe). But I don't see how the practical difficulty in finding the optimum strategy is relevant to its existence and assume that is not what you mean.
-Ww
Actually, I do have one problem with the proof as it applies to chess. Up before the prrof the author states:
The tree that represents such a game has finitely many nodes
Which given his definition of the tree simply does not hold true for chess games as far as I can tell.
And he does rely on this finiteness condition in hiis proof of the theorm (which is essentially identical to the proof I was thinking of when I wanted my 'cieling'... we both cheat in the same way, but at least I own up to my cheating...)
OTOH, if it's the same Zermelo* that I know of, there's probably a transfinite induction proof that elininates the finiteness requirement and replaces it with some kind of restraint on the infiniteness of the tree.
* - That is the early 20th century set theorist who worked with foundations including the Choice Axiom.
The tree that represents such a game has finitely many nodes
Which given his definition of the tree simply does not hold true for chess games as far as I can tell.
And he does rely on this finiteness condition in hiis proof of the theorm (which is essentially identical to the proof I was thinking of when I wanted my 'cieling'... we both cheat in the same way, but at least I own up to my cheating...)
OTOH, if it's the same Zermelo* that I know of, there's probably a transfinite induction proof that elininates the finiteness requirement and replaces it with some kind of restraint on the infiniteness of the tree.
* - That is the early 20th century set theorist who worked with foundations including the Choice Axiom.
Zermelo's theorem and trivial games
One's confidence in (and understanding of) the validity of the proof can be considerably improved by applying it to some trivial finite game, like tic-tac-toe or that game where you take turns picking up a variable number of stones. In those cases it is actually possible (and not too hard) to implement the algorithm used in the proof to find the optimum strategy, and in fact computers have been programmed to play those games using the Zermelo algorithm. Less trivial problems/games have also been "solved" numerically in this way.
If you have a look at such codes it is fairly easy to convince oneself that they could be applied equally well to the "tree" containing all possible chess games in principle, the practical problem being only that it is far too big to "fit" into any conceivable computer.
-Ww
One's confidence in (and understanding of) the validity of the proof can be considerably improved by applying it to some trivial finite game, like tic-tac-toe or that game where you take turns picking up a variable number of stones. In those cases it is actually possible (and not too hard) to implement the algorithm used in the proof to find the optimum strategy, and in fact computers have been programmed to play those games using the Zermelo algorithm. Less trivial problems/games have also been "solved" numerically in this way.
If you have a look at such codes it is fairly easy to convince oneself that they could be applied equally well to the "tree" containing all possible chess games in principle, the practical problem being only that it is far too big to "fit" into any conceivable computer.
-Ww
http://abel.math.harvard.edu/~elkies/FS23j.03/zermelo.pdf
seems to think that Zermelo proved far less than what is claimed on the UCLA website. In particular the proof of Zermelo that Konig has problems with is different in substance to the UCLA proof (which as far as I can tell is valid, but limited given my criticism above).
seems to think that Zermelo proved far less than what is claimed on the UCLA website. In particular the proof of Zermelo that Konig has problems with is different in substance to the UCLA proof (which as far as I can tell is valid, but limited given my criticism above).
Tic-Tac_toe is deterministically finite. Chess is not.
I agree that the number of positions is finite, however they (UCLA) defines a node to be a triplet of positions, next player to move, and total number of moves made to the point.
Therefore there are not a finite number of nodes as a given position can have an inifinte number of partial games (with corresponding number of moves) that lead to that position and so each position leads to an infinite number of nodes as defined by the site.
I agree that the number of positions is finite, however they (UCLA) defines a node to be a triplet of positions, next player to move, and total number of moves made to the point.
Therefore there are not a finite number of nodes as a given position can have an inifinte number of partial games (with corresponding number of moves) that lead to that position and so each position leads to an infinite number of nodes as defined by the site.
Just to make sure I am understanding you correctly, your worry is based on the fact that there might be an indefinitely large number of moves in a legal chess game unless one introduces a special rule (or rules) to eliminate that possibility, right? If so, I am happy to modify my claim to say that we know that an optimum strategy exists for any version of chess in which games are limited to some finite length (i.e., all real games of chess). I realize that this "move" on my part is not very mathematician-like, but it at least has the virtue of allowing us to terminate the discussion on a note of agreement.
I am not sure but would be that you are right that it is the same guy, and you could also easily be right about there being a somewhat more sophisticated transfinite induction version, but I don't know that for sure either.
-Ww
I am not sure but would be that you are right that it is the same guy, and you could also easily be right about there being a somewhat more sophisticated transfinite induction version, but I don't know that for sure either.
-Ww
Last edited:
The set theoretical lemma that's stated (without proof) on page 4 of my link is a way around the finiteness requirement and essentially leads to the same kind of proof offered in the UCLA paper extending that result to games with a countable (possibly infinite) number of outcomes.
Of course, that lemma looks a lot like a result that requires transfinite induction or the Chocie Axiom (which I think might be equivelent under the Zermelo Axioms of set theory).
Of course, that lemma looks a lot like a result that requires transfinite induction or the Chocie Axiom (which I think might be equivelent under the Zermelo Axioms of set theory).
1. Yeah, that's what I'm saying. It's what I meant way above with the cieling requirement. But if you look at my link, it appears that Kalmar does prove the result for a larger class of games. (I'm currently on page 8 and I think that In the last part of his paper, Kalmar shows that if a player is in a winning position, there exists a { possibly trans nite { ordinal number of moves in which this player can win independently of the behaviour of his opponent. strongly implies to me that a transfinite inductive approach was used.
I only today realized that there was a misunderstanding here. My post was intended as a reply to Slinky's claim that the proof (given in the UCLA link I posted) is a "bullshit tautology" or something to that effect. My point was that it (the proof) has sufficient content to be the basis for a computer code that actually finds optimum solutions to sufficiently simple games and can be used in practise for userful purposes...which, I would claim, shows that it is more than tautological.
It was not meant to address your worry about endless chess games.
-Ww
It was not meant to address your worry about endless chess games.
-Ww
This paper (Schwalbe and Walker) is really a very nice, well written and clear account of the matter from which I learned several new things about the topic. Thanks much for finding and posting it. I strongly recommend it to anyone who is interested in the subject (assuming that there is anyone other than us reading the thread).
For those who don't want to bother reading it but who have at least a passing interest in the matter, I would summarize the bottom line in this way:
Zermelo's proof is generally regarded as the first theorem ever proved in game theory, but what he actually claimed to prove is considerably more modest than is often thought, and moreover, there are some weaknesses in the proof he published. However, by 1930 further work by Konig (1927) and Kalmar (1928/29) had greatly improved and generalized Zermelo's work and essentially settled the matter to the satifaction of the mathematical community (at least up until 1999 when the Schwalbe and Walker paper appeared). Zermelo's proof and its corollary, as stated in the UCLA link I posted and quoted higher up in this thread, are considered to have been proven, although the proof given in that link is only rigorously valid if one "artificially" limits all possible chess games to some finite number of moves (however large...a googleplex factorial is just fine), but such a "ceiling" assumption/rule is not required for the more general analyses/proofs given in the literature.
In short, we do indeed know that there is an optimum strategy for playing chess but do not know to what outcome it leads.
-Ww
For those who don't want to bother reading it but who have at least a passing interest in the matter, I would summarize the bottom line in this way:
Zermelo's proof is generally regarded as the first theorem ever proved in game theory, but what he actually claimed to prove is considerably more modest than is often thought, and moreover, there are some weaknesses in the proof he published. However, by 1930 further work by Konig (1927) and Kalmar (1928/29) had greatly improved and generalized Zermelo's work and essentially settled the matter to the satifaction of the mathematical community (at least up until 1999 when the Schwalbe and Walker paper appeared). Zermelo's proof and its corollary, as stated in the UCLA link I posted and quoted higher up in this thread, are considered to have been proven, although the proof given in that link is only rigorously valid if one "artificially" limits all possible chess games to some finite number of moves (however large...a googleplex factorial is just fine), but such a "ceiling" assumption/rule is not required for the more general analyses/proofs given in the literature.
In short, we do indeed know that there is an optimum strategy for playing chess but do not know to what outcome it leads.
-Ww