Total Posts:35|Showing Posts:1-30|Last Page

# Zermelo's Theorem

 Posts: 12,171 Add as FriendChallenge to a DebateSend a Message 7/26/2015 11:22:40 AMPosted: 1 year agoOne of the principles of game theory states that in any two-player, turn-based 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.There are those who believe that irresponsible breeding practices, and the stupidity which fosters them, cannot be stemmed without damage to our freedom. But freedom, and much else as well, cannot tolerate the geometric prolificacy of stupidity. - Chris Langan -
 Posts: 2,347 Add as FriendChallenge to a DebateSend a Message 7/26/2015 12:46:51 PMPosted: 1 year agoAt 7/26/2015 11:22:40 AM, dylancatlow wrote:One of the principles of game theory states that in any two-player, turn-based 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.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 "two-player, turn-based 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 FriendChallenge to a DebateSend a Message 7/26/2015 1:32:42 PMPosted: 1 year agoStrictly 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 winor 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 FriendChallenge to a DebateSend a Message 7/26/2015 1:56:04 PMPosted: 1 year agoOn 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: 12,171 Add as FriendChallenge to a DebateSend a Message 7/26/2015 2:51:51 PMPosted: 1 year agoAt 7/26/2015 12:46:51 PM, Otokage wrote:At 7/26/2015 11:22:40 AM, dylancatlow wrote:One of the principles of game theory states that in any two-player, turn-based 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.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 "two-player, turn-based 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.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).There are those who believe that irresponsible breeding practices, and the stupidity which fosters them, cannot be stemmed without damage to our freedom. But freedom, and much else as well, cannot tolerate the geometric prolificacy of stupidity. - Chris Langan -
 Posts: 12,171 Add as FriendChallenge to a DebateSend a Message 7/26/2015 2:52:58 PMPosted: 1 year agoAt 7/26/2015 1:32:42 PM, kp98 wrote: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 winor 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.Are you sure about that: https://en.wikipedia.org...There are those who believe that irresponsible breeding practices, and the stupidity which fosters them, cannot be stemmed without damage to our freedom. But freedom, and much else as well, cannot tolerate the geometric prolificacy of stupidity. - Chris Langan -
 Posts: 12,171 Add as FriendChallenge to a DebateSend a Message 7/26/2015 2:57:10 PMPosted: 1 year agoAt 7/26/2015 1:56:04 PM, kp98 wrote: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.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 on-the-fly 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.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.There are those who believe that irresponsible breeding practices, and the stupidity which fosters them, cannot be stemmed without damage to our freedom. But freedom, and much else as well, cannot tolerate the geometric prolificacy of stupidity. - Chris Langan -
 Posts: 12,171 Add as FriendChallenge to a DebateSend a Message 7/26/2015 3:00:36 PMPosted: 1 year agoOh wait, I actually read your formulation wrong. NvmThere are those who believe that irresponsible breeding practices, and the stupidity which fosters them, cannot be stemmed without damage to our freedom. But freedom, and much else as well, cannot tolerate the geometric prolificacy of stupidity. - Chris Langan -
 Posts: 729 Add as FriendChallenge to a DebateSend a Message 7/26/2015 3:04:32 PMPosted: 1 year agoAre 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: 12,171 Add as FriendChallenge to a DebateSend a Message 7/26/2015 3:15:30 PMPosted: 1 year agoI 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).There are those who believe that irresponsible breeding practices, and the stupidity which fosters them, cannot be stemmed without damage to our freedom. But freedom, and much else as well, cannot tolerate the geometric prolificacy of stupidity. - Chris Langan -
 Posts: 6,033 Add as FriendChallenge to a DebateSend a Message 7/26/2015 5:01:57 PMPosted: 1 year agoAt 7/26/2015 11:22:40 AM, dylancatlow wrote: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.Yes. You can see it more easily in practice with Tic-Tac-Toe (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 Tic-tac-toe 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 second-last 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 second-last move and meanwhile, hope X makes a mistake.That means that for O, the third-last turn needs to leave no more than one winning position for X, which can then be blocked on the second-last move. For X, it's about ensuring there are at least two different winning positions on the third-last 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 tic-tac-toe 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 50-move limit, it turns out that if the search-space (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 tic-tac-toe. :DI hope that may be useful.
 Posts: 12,171 Add as FriendChallenge to a DebateSend a Message 7/26/2015 5:26:14 PMPosted: 1 year agoAt 7/26/2015 5:01:57 PM, RuvDraba wrote:At 7/26/2015 11:22:40 AM, dylancatlow wrote: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.Yes. You can see it more easily in practice with Tic-Tac-Toe (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 Tic-tac-toe 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 second-last 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 second-last move and meanwhile, hope X makes a mistake.That means that for O, the third-last turn needs to leave no more than one winning position for X, which can then be blocked on the second-last move. For X, it's about ensuring there are at least two different winning positions on the third-last 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 tic-tac-toe 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 50-move limit, it turns out that if the search-space (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 tic-tac-toe. :DI hope that may be useful.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?There are those who believe that irresponsible breeding practices, and the stupidity which fosters them, cannot be stemmed without damage to our freedom. But freedom, and much else as well, cannot tolerate the geometric prolificacy of stupidity. - Chris Langan -
 Posts: 6,033 Add as FriendChallenge to a DebateSend a Message 7/26/2015 6:24:49 PMPosted: 1 year agoJust 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 tipping-point 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: 6,033 Add as FriendChallenge to a DebateSend a Message 7/26/2015 6:28:54 PMPosted: 1 year agoAt 7/26/2015 6:25:00 PM, dylancatlow wrote:At 7/26/2015 6:12:16 PM, RuvDraba wrote: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.I think I get it now. Thanks!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: 12,171 Add as FriendChallenge to a DebateSend a Message 7/26/2015 6:58:35 PMPosted: 1 year agoAt 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: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.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.There are those who believe that irresponsible breeding practices, and the stupidity which fosters them, cannot be stemmed without damage to our freedom. But freedom, and much else as well, cannot tolerate the geometric prolificacy of stupidity. - Chris Langan -
 Posts: 3,071 Add as FriendChallenge to a DebateSend a Message 7/26/2015 7:01:15 PMPosted: 1 year agoAt 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: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.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.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)."This site is trash as a debate site. It's club penguin for dysfunctional adults." ~ Skepsikyma <3 "Your idea of good writing is like Spinoza mixed with Heidegger." ~ Dylly Dylly Cat Cat "You seem to aspire to be a cross between a Jewish hipster, an old school WASP aristocrat, and a political iconoclast" ~ Thett the Mighty
 Posts: 6,033 Add as FriendChallenge to a DebateSend a Message 7/26/2015 7:08:13 PMPosted: 1 year agoAt 7/26/2015 6:39:19 PM, ShabShoral wrote: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.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 near-identical 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: 12,171 Add as FriendChallenge to a DebateSend a Message 7/26/2015 7:08:27 PMPosted: 1 year agoAt 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: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.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.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).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?There are those who believe that irresponsible breeding practices, and the stupidity which fosters them, cannot be stemmed without damage to our freedom. But freedom, and much else as well, cannot tolerate the geometric prolificacy of stupidity. - Chris Langan -
 Posts: 3,071 Add as FriendChallenge to a DebateSend a Message 7/26/2015 7:24:43 PMPosted: 1 year agoAt 7/26/2015 7:08:27 PM, dylancatlow wrote: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: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.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.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).I did not say that it won't result in a draw, just that it need not to.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).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 non-loss 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."This site is trash as a debate site. It's club penguin for dysfunctional adults." ~ Skepsikyma <3 "Your idea of good writing is like Spinoza mixed with Heidegger." ~ Dylly Dylly Cat Cat "You seem to aspire to be a cross between a Jewish hipster, an old school WASP aristocrat, and a political iconoclast" ~ Thett the Mighty