Total Posts:35|Showing Posts:1-30|Last Page
Jump to topic:

Zermelo's Theorem

dylancatlow
Posts: 12,242
Add as Friend
Challenge to a Debate
Send a Message
7/26/2015 11:22:40 AM
Posted: 1 year ago
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.
Otokage
Posts: 2,347
Add as Friend
Challenge to a Debate
Send a Message
7/26/2015 12:46:51 PM
Posted: 1 year ago
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.
kp98
Posts: 729
Add as Friend
Challenge to a Debate
Send a Message
7/26/2015 1:32:42 PM
Posted: 1 year 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.
kp98
Posts: 729
Add as Friend
Challenge to a Debate
Send a Message
7/26/2015 1:56:04 PM
Posted: 1 year 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.
dylancatlow
Posts: 12,242
Add as Friend
Challenge to a Debate
Send a Message
7/26/2015 2:51:51 PM
Posted: 1 year ago
At 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).
dylancatlow
Posts: 12,242
Add as Friend
Challenge to a Debate
Send a Message
7/26/2015 2:52:58 PM
Posted: 1 year ago
At 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 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.

Are you sure about that: https://en.wikipedia.org...
dylancatlow
Posts: 12,242
Add as Friend
Challenge to a Debate
Send a Message
7/26/2015 2:57:10 PM
Posted: 1 year ago
At 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.
kp98
Posts: 729
Add as Friend
Challenge to a Debate
Send a Message
7/26/2015 3:04:32 PM
Posted: 1 year 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... :)
dylancatlow
Posts: 12,242
Add as Friend
Challenge to a Debate
Send a Message
7/26/2015 3:15:30 PM
Posted: 1 year 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).
RuvDraba
Posts: 6,033
Add as Friend
Challenge to a Debate
Send a Message
7/26/2015 5:01:57 PM
Posted: 1 year ago
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. :D

I hope that may be useful.
dylancatlow
Posts: 12,242
Add as Friend
Challenge to a Debate
Send a Message
7/26/2015 5:26:14 PM
Posted: 1 year ago
At 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. :D

I 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?
RuvDraba
Posts: 6,033
Add as Friend
Challenge to a Debate
Send a Message
7/26/2015 6:12:16 PM
Posted: 1 year ago
At 7/26/2015 5:26:14 PM, dylancatlow wrote:
At 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?

This idea of working backwards from winning positions underpins a technique called 'reverse induction' that's usually used to proved Zermelo's Theorem.


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?

Okay, so... using my earlier definition of a 'winning position' -- i.e. a position from which you can still win, a turn-based 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 perfectly-played 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 high-value pieces, such as queen and rooks, because your opponent can then demolish your remaining winning positions too fast to admit counter-attack.)

For a draw, there must also be a tipping-point, 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 tipping-point 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 chess-player 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 tipping-points, 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.
RuvDraba
Posts: 6,033
Add as Friend
Challenge to a Debate
Send a Message
7/26/2015 6:24:49 PM
Posted: 1 year 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 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.
dylancatlow
Posts: 12,242
Add as Friend
Challenge to a Debate
Send a Message
7/26/2015 6:25:00 PM
Posted: 1 year 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:
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?

This idea of working backwards from winning positions underpins a technique called 'reverse induction' that's usually used to proved Zermelo's Theorem.


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?

Okay, so... using my earlier definition of a 'winning position' -- i.e. a position from which you can still win, a turn-based 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 perfectly-played 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 high-value pieces, such as queen and rooks, because your opponent can then demolish your remaining winning positions too fast to admit counter-attack.)

For a draw, there must also be a tipping-point, 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 tipping-point 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 chess-player 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 tipping-points, 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.

I think I get it now. Thanks!
RuvDraba
Posts: 6,033
Add as Friend
Challenge to a Debate
Send a Message
7/26/2015 6:28:54 PM
Posted: 1 year ago
At 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. :)
ShabShoral
Posts: 3,222
Add as Friend
Challenge to a Debate
Send a Message
7/26/2015 6:39:19 PM
Posted: 1 year 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:
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?

This idea of working backwards from winning positions underpins a technique called 'reverse induction' that's usually used to proved Zermelo's Theorem.


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?

Okay, so... using my earlier definition of a 'winning position' -- i.e. a position from which you can still win, a turn-based 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 perfectly-played 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 high-value pieces, such as queen and rooks, because your opponent can then demolish your remaining winning positions too fast to admit counter-attack.)

For a draw, there must also be a tipping-point, 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 tipping-point 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 chess-player 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 tipping-points, 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.

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).
"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
dylancatlow
Posts: 12,242
Add as Friend
Challenge to a Debate
Send a Message
7/26/2015 6:58:35 PM
Posted: 1 year 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:

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.
ShabShoral
Posts: 3,222
Add as Friend
Challenge to a Debate
Send a Message
7/26/2015 7:01:15 PM
Posted: 1 year 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:

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
RuvDraba
Posts: 6,033
Add as Friend
Challenge to a Debate
Send a Message
7/26/2015 7:08:13 PM
Posted: 1 year ago
At 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
dylancatlow
Posts: 12,242
Add as Friend
Challenge to a Debate
Send a Message
7/26/2015 7:08:27 PM
Posted: 1 year 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:

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?
ShabShoral
Posts: 3,222
Add as Friend
Challenge to a Debate
Send a Message
7/26/2015 7:24:43 PM
Posted: 1 year ago
At 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
ShabShoral
Posts: 3,222
Add as Friend
Challenge to a Debate
Send a Message
7/26/2015 7:29:52 PM
Posted: 1 year ago
At 7/26/2015 7:08:13 PM, RuvDraba wrote:
At 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. :)
Exactly my reasoning :)
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 self-evident, but apparently not for Dylan!
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

I actually was planning to read that sometime, though I never got around to it - I'll make sure to do it soon. Thanks!
"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
dylancatlow
Posts: 12,242
Add as Friend
Challenge to a Debate
Send a Message
7/26/2015 7:35:58 PM
Posted: 1 year ago
At 7/26/2015 7:24:43 PM, ShabShoral wrote:
At 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).

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 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.

That takes for granted that strategies can guarantee things.
kp98
Posts: 729
Add as Friend
Challenge to a Debate
Send a Message
7/26/2015 7:42:50 PM
Posted: 1 year 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.
ShabShoral
Posts: 3,222
Add as Friend
Challenge to a Debate
Send a Message
7/26/2015 7:44:44 PM
Posted: 1 year ago
At 7/26/2015 7:42:50 PM, kp98 wrote:
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.

Yeah, that's probably a better formulation.
"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
RuvDraba
Posts: 6,033
Add as Friend
Challenge to a Debate
Send a Message
7/26/2015 7:48:05 PM
Posted: 1 year ago
At 7/26/2015 7:29:52 PM, ShabShoral wrote:
At 7/26/2015 7:08:13 PM, RuvDraba wrote:
At 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. :)
Exactly my reasoning :)
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.

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 real-world 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 question-begging) 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 end-case and a win end-case, 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. :)
SeventhProfessor
Posts: 5,079
Add as Friend
Challenge to a Debate
Send a Message
7/26/2015 7:51:04 PM
Posted: 1 year 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,
#UnbanTheMadman

#StandWithBossy

#BetOnThett

"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 trying-to-be-funny way."
~F-16

https://docs.google.com...
dylancatlow
Posts: 12,242
Add as Friend
Challenge to a Debate
Send a Message
7/26/2015 7:58:18 PM
Posted: 1 year 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.
RuvDraba
Posts: 6,033
Add as Friend
Challenge to a Debate
Send a Message
7/26/2015 8:46:29 PM
Posted: 1 year ago
At 7/26/2015 7:58:18 PM, dylancatlow wrote:
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.

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 vice-versa. 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 argument-by-contradiction, 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 tipping-points. 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 tipping-point 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. :)