Zermelo's Theorem
Posts: 13,531
Add as Friend Challenge to a Debate Send a Message 
7/26/2015 11:22:40 AM Posted: 2 years ago One of the principles of game theory states that in any twoplayer, turnbased game in which all moves are completely up to the player and in which all rules are fixed (e.g., Checkers, Connect Four), one of three things is necessarily true: the first person to go could, if they played a certain way; always force a win; the second person to go could, if they played a certain way, always force a win; or both players could, if they played a certain way, always force a draw. In other words, it's necessarily true that it is theoretically possible to build a computer program which is mathematically unable to lose at chess, no matter what the opponent does.
Intuitively this feels true, given that a deterministic setup would seem to preclude intractable uncertainty, but I don't get exactly why it's the case. Bossy's explanation is that "If player one doesn't have an unbeatable strategy, then player two can beat/dodge all his strategies, in which case he can always win/draw". This leaves me unsatisfied, because it seems to beg the question. Just because player one doesn't have an unbeatable strategy doesn't mean that the possibility for player two to beat his strategies implies a strategy in which he can always do so unless we take for granted Zermelo's Theorem. I would really appreciate if someone could explain why Zermelo's Theorem is true in a straightforward, intuitive way. 
Posts: 2,460
Add as Friend Challenge to a Debate Send a Message 
7/26/2015 12:46:51 PM Posted: 2 years ago At 7/26/2015 11:22:40 AM, dylancatlow wrote: Wow, I believe Zermelo is more simple than that. It simply means that if player 1 loses, then it is necesarily true that this is because player 2 has won, and therefore he had an unique winning strategy that can be seen by recalling all his movements to the beginning of the game. It is not possible on "twoplayer, turnbased game in which all moves are completely up to the player and in which all rules are fixed" to make both players "lose" (in which losing means obtaining a lower result than the rival). They will, at the very least, end in a draw. 
Posts: 729
Add as Friend Challenge to a Debate Send a Message 
7/26/2015 1:32:42 PM Posted: 2 years ago Strictly Zermelo does not apply to chess because Zermelo applies to games were draws are not possible, but we can allow a little looseness!
I think OKs exposition can be tidied up: If white doesn't have a strategy that guarantees it a win, then it must be the case that black has a strategy guaranteed to stop white winning. So one and only one of the following must exist: 1) a strategy that guarantees a white win or 2) a strategy that guarantees a black win/draw. Zermelo says nothing about which one is true for chess (or any other game), only that one (and only one) of them must exist. 
Posts: 729
Add as Friend Challenge to a Debate Send a Message 
7/26/2015 1:56:04 PM Posted: 2 years ago On further thought I think the basic idea can be expressed even more succintly as:
'Either white has a strategy that guarantees a win or black has a strategy that guarantees avoiding defeat  but not both. With chess the number of strategies is virtually uncomputable, so discovering a guaranteed winning strategy is beyond possibility as things stand, but Zermelo tells us that  in theory  either white must win or black does not have to lose. As the OP suggests, it's a intuitive result, but mathematicians are never happy leaving things to intuition. There is a proof that for any circle some points are inside the circle and others points are outside it .... something most people would probably take on trust. 
Posts: 13,531
Add as Friend Challenge to a Debate Send a Message 
7/26/2015 2:51:51 PM Posted: 2 years ago At 7/26/2015 12:46:51 PM, Otokage wrote:At 7/26/2015 11:22:40 AM, dylancatlow wrote: That isn't the theorem. For example, when applied to Connect Four the theorem says that the person who goes first can win 100 percent of the time if they know what to do (which requires their opening move to be in the middle). 
Posts: 13,531
Add as Friend Challenge to a Debate Send a Message 
7/26/2015 2:52:58 PM Posted: 2 years ago At 7/26/2015 1:32:42 PM, kp98 wrote: Are you sure about that: https://en.wikipedia.org... 
Posts: 13,531
Add as Friend Challenge to a Debate Send a Message 
7/26/2015 2:57:10 PM Posted: 2 years ago At 7/26/2015 1:56:04 PM, kp98 wrote: The reason I don't like using the word strategy is because it must accommodate for many different styles depending on how the opponent plays, so it has to adjust onthefly to continuously changing conditions. I guess it sort of still applies, but it still feels weird to me. Also, the theorem allows for the possibility that both players can force a draw, so your formulation is actually wrong. With chess the number of strategies is virtually uncomputable, so discovering a guaranteed winning strategy is beyond possibility as things stand, but Zermelo tells us that  in theory  either white must win or black does not have to lose. 
Posts: 13,531
Add as Friend Challenge to a Debate Send a Message 
7/26/2015 3:00:36 PM Posted: 2 years ago Oh wait, I actually read your formulation wrong. Nvm

Posts: 729
Add as Friend Challenge to a Debate Send a Message 
7/26/2015 3:04:32 PM Posted: 2 years ago Are you sure about that: https://en.wikipedia.org......
It's a bit muddied because of the possiblility of a draw in chess, but yes I'm sure about that. Of course, I do make misakes... :) 
Posts: 13,531
Add as Friend Challenge to a Debate Send a Message 
7/26/2015 3:15:30 PM Posted: 2 years ago I think a more precise definition of "unbeatable strategy" is this: a situation in which no matter what moves your opponent makes, he cannot deviate from some sequence of moves in which he loses. That is, no matter what he does, here's merely completing some pattern where he loses (I'm thinking of Connect Four).

Posts: 6,033
Add as Friend Challenge to a Debate Send a Message 
7/26/2015 5:01:57 PM Posted: 2 years ago At 7/26/2015 11:22:40 AM, dylancatlow wrote: Yes. You can see it more easily in practice with TicTacToe (noughts and crosses), a game of alternating moves that's over within five turns. In TTT there are nine squares to fill in, so if X goes first, then X gets up to five moves, while O gets at most four. If you explore these (you can do it by hand in an afternoon), you should discover 138 distinct board positions to end a game of TTT. Of these, 91 positions are won by X; 44 are won by O, and 3 are draws. Just on the possible endings, you can see that Tictactoe is heavily skewed toward X winning, so with experienced players, often X tries to win, while O tries not to lose. :) And for X, that problem means seeking a board position after your secondlast move such that, however O moves, you still have at least one winning move left  let's call that a 'winning position'. For O, the challenge is to to block all winning positions for X by the secondlast move and meanwhile, hope X makes a mistake. That means that for O, the thirdlast turn needs to leave no more than one winning position for X, which can then be blocked on the secondlast move. For X, it's about ensuring there are at least two different winning positions on the thirdlast turn, such that O can at most block one. You can keep working backwards from there until you reach the beginning of the game. This gives us a restatement of the strategic problem: Can X place a first move such that as the game unfolds, X always has more winning positions than O can block in four moves? Meanwhile, can O block winning positions fast enough so that they're all blocked by X's final move? It turns out that if X plays perfectly, X can never lose, while O can never win. In other words, going first (and last) gives X so many winning positions that if X plays perfectly, O can at most only hope to block them all  not gain a winning position for himself. This idea of working backwards from winning positions underpins a technique called 'reverse induction' that's usually used to proved Zermelo's Theorem. Computer programs generally play tictactoe perfectly (you can check this at: http://www.calculatorcat.com...) So if you go first and play well, you'll still only get a draw, while if you go second, you'll be fighting for a draw, and can't afford to make a single mistake. However, it's harder for chess. With vastly more ending positions, even allowing for the 50move limit, it turns out that if the searchspace (i.e. the total number of distinct possible games) is around 10 ^ 120  i.e. 1 with 120 zeroes after it. This compares to around 10 ^ 80 hydrogen atoms in the observable universe. So it's not certain if we'll ever get enough computing power to play a perfect chess game. :) But even if we could , the Japanese strategy game of Go has vastly in excess of 10 ^ 1023 possible games, making chess look like tictactoe. :D I hope that may be useful. 
Posts: 13,531
Add as Friend Challenge to a Debate Send a Message 
7/26/2015 5:26:14 PM Posted: 2 years ago At 7/26/2015 5:01:57 PM, RuvDraba wrote:At 7/26/2015 11:22:40 AM, dylancatlow wrote: This is interesting, but I still don't exactly understand why one of the players can always force a certain outcome no matter what game we're talking about. Why is this principle universal? 
Posts: 6,033
Add as Friend Challenge to a Debate Send a Message 
7/26/2015 6:12:16 PM Posted: 2 years ago At 7/26/2015 5:26:14 PM, dylancatlow wrote:At 7/26/2015 5:01:57 PM, RuvDraba wrote:This is interesting, but I still don't exactly understand why one of the players can always force a certain outcome no matter what game we're talking about. Why is this principle universal?At 7/26/2015 11:22:40 AM, dylancatlow wrote: Okay, so... using my earlier definition of a 'winning position'  i.e. a position from which you can still win, a turnbased strategy game is designed to block the other player's remaining winning positions as rapidly as possible, while preserving one's own. Perfect play means you keep the number of remaining winning positions available to you as big as possible, while minimising the number of winning positions for the other player. Perfectly prescient play (i.e. one where players can look ahead to see all possibilities) should end in a resignation if you have winning positions available to you while your opponent has none, and should end in a draw when neither player has winning positions available. So to end in a win, a perfectlyplayed game must have a 'final tipping point'  a point at which you can definitely consume all your opponent's remaining winning positions faster than your opponent can consume all yours. Again, with perfect play and perfect prescience, if you reach a final tipping point, your opponent should resign. (In chess, this often happens when you lose too many highvalue pieces, such as queen and rooks, because your opponent can then demolish your remaining winning positions too fast to admit counterattack.) For a draw, there must also be a tippingpoint, past which perfect players can never do better than consume each others' winning positions at an identical rate. So the argument is the same. But with perfect play, that tipping point itself must have a prior tipping point, beyond which a final tippingpoint became unavoidable. With perfectly prescient play, if you reach the prior tipping point for a win, then your opponent should also resign, because he also can't prevent you from reaching your final tipping point. (As a youngster, I once had this playing a state champion. We both knew about three moves ahead that she was about to obliterate my queen far too early in the game... so I resigned  and won a compliment from a seasoned chessplayer far more experienced than I, for my understanding of strategy, if not tactics. :D) And that prior tipping point must have a prior tipping point, and so on... You can repeat that argument as many times as you want... going back to the very first move. With perfect information, if a game can be won or drawn, it can only be won or drawn by relative consumption of winning positions, constructed as a series of tippingpoints, each securing the next, stretching all the way back to the very beginning. As intuitively as I can put it, Zermelo's Theorem just says that in an alternating game played perfectly, with perfect information about the remaining possibilities, one of the first two moves must be an initial tipping point  one that guarantees that one player will either win or break even in the race to consume winning positions. Hope that might make it clearer. 
Posts: 6,033
Add as Friend Challenge to a Debate Send a Message 
7/26/2015 6:24:49 PM Posted: 2 years ago Just for clarity, Dylan, though it may be obvious...
A finite alternating game, played perfectly, must nevertheless end in a win or a draw. So because it has, and was played perfectly, you can apply the argument I described above: find the final tipping point making a win or draw inevitable; find the prior tippingpoint making the final tipping point inevitable, and so on... Since the number of moves in the game was finite, that'll take you all the way back to the first two moves. 
Posts: 13,531
Add as Friend Challenge to a Debate Send a Message 
7/26/2015 6:25:00 PM Posted: 2 years ago At 7/26/2015 6:12:16 PM, RuvDraba wrote:At 7/26/2015 5:26:14 PM, dylancatlow wrote:At 7/26/2015 5:01:57 PM, RuvDraba wrote:This is interesting, but I still don't exactly understand why one of the players can always force a certain outcome no matter what game we're talking about. Why is this principle universal?At 7/26/2015 11:22:40 AM, dylancatlow wrote: I think I get it now. Thanks! 
Posts: 6,033
Add as Friend Challenge to a Debate Send a Message 
7/26/2015 6:28:54 PM Posted: 2 years ago At 7/26/2015 6:25:00 PM, dylancatlow wrote:At 7/26/2015 6:12:16 PM, RuvDraba wrote: Oh, great! I can't tell you how pleased I am, Dylan. It's pretty hard to put induction proofs into words. When mathematicians do it, it's usually full of algebra and Greek letters. It makes me very happy to be able to explain an induction proof in English for a change. :) 
Posts: 4,199
Add as Friend Challenge to a Debate Send a Message 
7/26/2015 6:39:19 PM Posted: 2 years ago At 7/26/2015 6:12:16 PM, RuvDraba wrote:At 7/26/2015 5:26:14 PM, dylancatlow wrote:At 7/26/2015 5:01:57 PM, RuvDraba wrote:This is interesting, but I still don't exactly understand why one of the players can always force a certain outcome no matter what game we're talking about. Why is this principle universal?At 7/26/2015 11:22:40 AM, dylancatlow wrote: That's a very good explanation, though I think it's a bit unnecessary. I used the argument as follows: If the first player does not have an unbeatable strategy, then the second person has a strategy that will beat every one of the first player's strategies (leading to him either forcing a draw or a win). As such, if the first player doesn't have a winning strategy (which is necessary if, as Dylan argues, there aren't any universally winning strategies), that means that he *cannot* logically win and therefore must lose, and the strategy employed by player two that leads to his loss must then be unbeatable (else player one would have an unbeatable strategy of his own). Essentially, here's a list of possibilities as to how it could go: 1. Player one has an unbeatable strategy and therefore wins every game. 2. Player one does not have an unbeatable strategy and neither does player two, leading to a forced draw (since neither player can win) 3. Player one does not have an unbeatable strategy while player two does, meaning that player one can never win and player two will always win. Leading to the fact that there are three possibilities: A win is forced for player one, a draw is forced, or a win is forced for player two, which are just the possibilities implied by Zermelo's theorem . There are just no other logically coherent situations, since, for example, if player one has an unbeatable strategy and still loses, his strategy, by definition, was not unbeatable (and the same for player two). : At 10/2/2017 3:00:43 AM, YYW wrote: : Bossy: You are Regina. :Inferno wrote: :You sound rather gay.  And the light shineth in darkness; and the darkness comprehended it not. "I believe that my powers of mind are surely such that I would have become in a certain sense a resolver of all problems. I do not believe that I could have remained in error anywhere for long. I believe that I would have earned the name of Redeemer, because I had the nature of a Redeemer. " 
Posts: 13,531
Add as Friend Challenge to a Debate Send a Message 
7/26/2015 6:58:35 PM Posted: 2 years ago At 7/26/2015 6:39:19 PM, ShabShoral wrote:At 7/26/2015 6:12:16 PM, RuvDraba wrote:Essentially, here's a list of possibilities as to how it could go: I take issue with option two. Just because neither player has an unbeatable strategy does not mean that there is a strategy for both players which guarantees a draw. At least, you have not shown why this is the case. 
Posts: 4,199
Add as Friend Challenge to a Debate Send a Message 
7/26/2015 7:01:15 PM Posted: 2 years ago At 7/26/2015 6:58:35 PM, dylancatlow wrote:At 7/26/2015 6:39:19 PM, ShabShoral wrote:At 7/26/2015 6:12:16 PM, RuvDraba wrote:Essentially, here's a list of possibilities as to how it could go: Because if a strategy does not result in a draw then it results in either a loss or a win (tautologically), and therefore guarantees a win for either player one or two (which just makes the case one of option one or three). : At 10/2/2017 3:00:43 AM, YYW wrote: : Bossy: You are Regina. :Inferno wrote: :You sound rather gay.  And the light shineth in darkness; and the darkness comprehended it not. "I believe that my powers of mind are surely such that I would have become in a certain sense a resolver of all problems. I do not believe that I could have remained in error anywhere for long. I believe that I would have earned the name of Redeemer, because I had the nature of a Redeemer. " 
Posts: 6,033
Add as Friend Challenge to a Debate Send a Message 
7/26/2015 7:08:13 PM Posted: 2 years ago At 7/26/2015 6:39:19 PM, ShabShoral wrote: That's a nice account too, ShabShoral. The middle case might need more explanation for some readers, but it's correct by induction, since by definition if you don't have an unbeatable strategy, then your opponent can always force you into a game where you still don't have an unbeatable strategy, and so on forever, thus forcing a draw. :) All that remains is to explain what an unbeatable strategy is  and if you're forced to explain that (or if readers don't intuit it), you may find yourself working backwards, as I did. :) This fun discussion (and a nearidentical copy of your argument) is picked up in a unit for gifted math students at UHK, which I found here: http://hkumath.hku.hk... Hope it may be of interest. :D 
Posts: 13,531
Add as Friend Challenge to a Debate Send a Message 
7/26/2015 7:08:27 PM Posted: 2 years ago At 7/26/2015 7:01:15 PM, ShabShoral wrote:At 7/26/2015 6:58:35 PM, dylancatlow wrote:At 7/26/2015 6:39:19 PM, ShabShoral wrote:At 7/26/2015 6:12:16 PM, RuvDraba wrote:Essentially, here's a list of possibilities as to how it could go: I did not say that it won't result in a draw, just that it need not to. Also, just because a strategy happens to result in a win does not mean that it was guaranteed to. You're begging the question again. Why should any strategy guarantee anything, given that the other player is free to make their own choices? 
Posts: 4,199
Add as Friend Challenge to a Debate Send a Message 
7/26/2015 7:24:43 PM Posted: 2 years ago At 7/26/2015 7:08:27 PM, dylancatlow wrote:If it *does* result in a draw, given optimal play, then a draw is the best possible outcome for both sides and is therefore guaranteed if both sides make no mistakes (which is assumed by the theorem).At 7/26/2015 7:01:15 PM, ShabShoral wrote:At 7/26/2015 6:58:35 PM, dylancatlow wrote:At 7/26/2015 6:39:19 PM, ShabShoral wrote:At 7/26/2015 6:12:16 PM, RuvDraba wrote:Essentially, here's a list of possibilities as to how it could go: Also, just because a strategy happens to result in a win does not mean that it was guaranteed to.Assuming perfect play, yes, it is guaranteed to. If it wasn't guaranteed to, then perfect play would result in it not being a win, since forcing a nonloss is more optimal than letting a loss occur (and thus, if it isn't necessary to lose, a player who plays perfectly will not lose). You're begging the question again."A is A" "You're begging the question!" "..." Why should any strategy guarantee anything, given that the other player is free to make their own choices? Because if a strategy DOES NOT guarantee a win for player one (assumed by your premise that wins are never guaranteed) then the outcome, assuming the opponent makes no mistakes, MUST not be a win, and therefore the opponent can be said to force a draw or a win for himself, which contradicts the idea that no strategy is determined. : At 10/2/2017 3:00:43 AM, YYW wrote: : Bossy: You are Regina. :Inferno wrote: :You sound rather gay.  And the light shineth in darkness; and the darkness comprehended it not. "I believe that my powers of mind are surely such that I would have become in a certain sense a resolver of all problems. I do not believe that I could have remained in error anywhere for long. I believe that I would have earned the name of Redeemer, because I had the nature of a Redeemer. " 
Posts: 4,199
Add as Friend Challenge to a Debate Send a Message 
7/26/2015 7:29:52 PM Posted: 2 years ago At 7/26/2015 7:08:13 PM, RuvDraba wrote:Exactly my reasoning :)At 7/26/2015 6:39:19 PM, ShabShoral wrote: All that remains is to explain what an unbeatable strategy is  and if you're forced to explain that (or if readers don't intuit it), you may find yourself working backwards, as I did. :)I can see why you did what you did (because Dylan is clearly confused about the definition of a winning strategy). It seems fairly obvious  an unbeatable strategy is, well, a strategy that cannot be beaten (and therefore will always lead to a win). A beatable strategy is a strategy which can be responded to and therefore does not win. I assumed this was selfevident, but apparently not for Dylan! This fun discussion (and a nearidentical copy of your argument) is picked up in a unit for gifted math students at UHK, which I found here: http://hkumath.hku.hk... I actually was planning to read that sometime, though I never got around to it  I'll make sure to do it soon. Thanks! : At 10/2/2017 3:00:43 AM, YYW wrote: : Bossy: You are Regina. :Inferno wrote: :You sound rather gay.  And the light shineth in darkness; and the darkness comprehended it not. "I believe that my powers of mind are surely such that I would have become in a certain sense a resolver of all problems. I do not believe that I could have remained in error anywhere for long. I believe that I would have earned the name of Redeemer, because I had the nature of a Redeemer. " 
Posts: 13,531
Add as Friend Challenge to a Debate Send a Message 
7/26/2015 7:35:58 PM Posted: 2 years ago At 7/26/2015 7:24:43 PM, ShabShoral wrote:At 7/26/2015 7:08:27 PM, dylancatlow wrote:If it *does* result in a draw, given optimal play, then a draw is the best possible outcome for both sides and is therefore guaranteed if both sides make no mistakes (which is assumed by the theorem).At 7/26/2015 7:01:15 PM, ShabShoral wrote:At 7/26/2015 6:58:35 PM, dylancatlow wrote:At 7/26/2015 6:39:19 PM, ShabShoral wrote:At 7/26/2015 6:12:16 PM, RuvDraba wrote:Essentially, here's a list of possibilities as to how it could go: You're smuggling in the idea that there exists a strategy which guarantees a draw when you introduce the concept of "optimal play". Hence, begging the question. I don't actually disagree with your conclusion by the way. Also, just because a strategy happens to result in a win does not mean that it was guaranteed to.Assuming perfect play, yes, it is guaranteed to. If it wasn't guaranteed to, then perfect play would result in it not being a win, since forcing a nonloss is more optimal than letting a loss occur (and thus, if it isn't necessary to lose, a player who plays perfectly will not lose).You're begging the question again."A is A" That takes for granted that strategies can guarantee things. 
Posts: 729
Add as Friend Challenge to a Debate Send a Message 
7/26/2015 7:42:50 PM Posted: 2 years ago 2. Player one does not have an unbeatable strategy and neither does player two, leading to a forced draw (since neither player can win)
I think that can be expressed as 'if neither player can force a win, then the game will end in a draw (assuming no mistakes)'. I am not sure that clears anything up. 
Posts: 4,199
Add as Friend Challenge to a Debate Send a Message 
7/26/2015 7:44:44 PM Posted: 2 years ago At 7/26/2015 7:42:50 PM, kp98 wrote: Yeah, that's probably a better formulation. : At 10/2/2017 3:00:43 AM, YYW wrote: : Bossy: You are Regina. :Inferno wrote: :You sound rather gay.  And the light shineth in darkness; and the darkness comprehended it not. "I believe that my powers of mind are surely such that I would have become in a certain sense a resolver of all problems. I do not believe that I could have remained in error anywhere for long. I believe that I would have earned the name of Redeemer, because I had the nature of a Redeemer. " 
Posts: 6,033
Add as Friend Challenge to a Debate Send a Message 
7/26/2015 7:48:05 PM Posted: 2 years ago At 7/26/2015 7:29:52 PM, ShabShoral wrote:At 7/26/2015 7:08:13 PM, RuvDraba wrote:Exactly my reasoning :)At 7/26/2015 6:39:19 PM, ShabShoral wrote: In fairness to Dylan, he asked for an intuitive explanation. I opted for what is called an intuitionistic or constructive proof, in which you aren't allowed to assume anything, and only define things you can show how to construct. For realworld situations, this has the benefit of playing straight into our experiences of constructing stuff from known situations  like best next moves in chess games. :) While logically equivalent, your explanation uses two nonconstructive elements: 1) An unbeatable strategy (can we construct it? If so, how? As Dylan points out, it can look like questionbegging) and 2) The logically valid assumption that either one player has an unbeatable strategy, or none does. (But which is it, and how do we know?) These elements look fine as algebra, but can rattle our intuitions. We can avoid that by being strictly constructive and not assuming anything. Like you, I used the idea of an 'unbeatable strategy', but constructed it backwards (really the only way to do so), and showed two separate endcases individually  a draw endcase and a win endcase, even each used the same argument. Constructive proofs generally take longer, but there's a whole branch of logic dedicated to doing constructive proofs only, and for my sins, in the folly of my youth, I used to play with it. :) [https://en.wikipedia.org...] Perhaps that, plus many years of teaching, may have steered me to the less efficient, but more effective explanation. :) 
Posts: 5,960
Add as Friend Challenge to a Debate Send a Message 
7/26/2015 7:51:04 PM Posted: 2 years ago The reason this is true is that you could hypothetically map out all possible outcomes of a chess game, like this (http://plato.stanford.edu...) except much more complex. Thanks to this, you start on the bottom and map out which decision on each branch would give you the best shot in a game of chess. If you always went with the best decision as mapped from the bottom, and followed the matrix as you played, you would either win or draw since there's a roughly 50/50 chance of black or white winning,
Stooge the Worst #UnbanTheMadman #StandWithBossy #UnbanTheCuntMan "bossy r u like 85 years old and have lost ur mind" ~mysteriouscrystals "I've honestly never seen seventh post anything that wasn't completely idiotic in a tryingtobefunny way." ~F16 "SeventhProfessor is actually a surprisingly good poster." ~Devilry https://docs.google.com... 
Posts: 13,531
Add as Friend Challenge to a Debate Send a Message 
7/26/2015 7:58:18 PM Posted: 2 years ago I mean, I basically agree with the explanation that "If player A doesn't have an unbeatable strategy, then player B can beat him if he wants to, and thus has an unbeatable strategy available to him" but it's just soooo unsatisfying.

Posts: 6,033
Add as Friend Challenge to a Debate Send a Message 
7/26/2015 8:46:29 PM Posted: 2 years ago At 7/26/2015 7:58:18 PM, dylancatlow wrote: It's a bit trickier than that, Dylan. If A or B has an unbeatable strategy, then they can just play it. We don't know what it is, but they can't both have one because then one wouldn't be unbeatable. But if neither has one, then for each move starting with the first, B can always force A into a game where A doesn't have an unbeatable strategy, and viceversa. Because if they couldn't do that, then A or B would have an unbeatable strategy in the first move  it's a bit of argumentbycontradiction, but there you go. We can apply that argument to the second move, the third move and so on. For each move, each player can force the other into a game where they don't have an unbeatable strategy. So even if there were some great strategy later in the game, they'll never get to play it, because if a perfect player can stop them doing that, they will. That'll continue until the end of the game, which means both A and B can force the other into a draw. That completes the proof, but what's dissatisfying about it is that it glosses over the interesting part: what's an unbeatable strategy, and how do you build it? The explanation we used earlier addresses this : if perfect players with perfect information end up playing to a win, then one player has an unbeatable strategy made up of tippingpoints. We know how to construct tipping points. First we work out how to eliminate the other player's winning positions, then we construct the tipping point allowing us to eliminate the other player's winning conditions faster than they can control, then we construct the tipping point allowing us to put that tippingpoint into place... and so on. If we can do all that, then that's our unbeatable strategy. If we can't, then either the other guy can do it to us, or we can each stop the other from doing it until all our winning positions are eliminated at the same rate, forcing a draw. In the end it's the same proof, but with what some might feel is more smoke and mirrors. :) 