|
Alyssa and Ben play a game of 2-Tic-Tac-Toe on a 2x2 grid. Alyssa and Ben take turns claiming territory until one player makes 2-in-a-row with their territory. Alyssa goes first, and it is obvious that she always wins.
Extend this to 3-Tic-Tac-Toe for a 3x3x3 cube. It is less readily apparent that Alyssa can still win every time. Assume Alyssa plays optimally, so she doesn't make mistakes or throw the game for Ben (who is very miserable losing over and over again).
To be clear, a 2-TTT game has 6 winning positions across 2 dimensions (4 orthogonal and 2 diagonal). So a 3-TTT game has 27 1-dimensional wins, 18 over 2 dimensions, and 4 over 3 dimensions.
Edit: An n-TTT game is defined to have n^n cells over n dimensions. A 4-TTT game therefore has 256 cells over 4 dimensions, and is a 4-dimensional hypercube. To visualize: draw a 4x4 grid of 16 smaller 4x4 grids. You can win 4-TTT on just one grid, across a row of 4 grids, or diagonally across the grids (marking one cell in each grid). In this image there are 5 winning arrangements.
+ Show Spoiler +web.mit.edu/mikemp/Public/4-TTT.png
Prove/disprove that Alyssa has a winning strategy for any n-TTT game.
Hint:
+ Show Spoiler +This problem hinges on whether or not it is possible for the game to draw. Case 1: A draw is possible for all n. Case 2: A draw is possible for some n. Case 3: A draw is impossible. Credit to Muirhead for intuition regarding the third case: + Show Spoiler +
Assume that Ben (who plays second) has a winning strategy. Alyssa plays first in any location, and subsequently will play out Ben's strategy as though she were second to play. Any time Alyssa's strategy would require a move in a place she already owns, she simply takes another arbitrarily since she already owns the location mandated by her strategy. By deferring the initiative Alyssa steals Ben's strategy, thus forming a contradiction. By this contradiction Ben cannot have a winning strategy if a draw is impossible.
A subtle point: Alyssa's first move does not jeopardize the strategy she stole from Ben, since it does not lend Ben any stronger of a strategy. Alyssa loses no options by making this move, although her opponent is weakened.
Intuition says that case 3 is reality, but a proof is still necessary. Can you think of a clean or elegant way of showing that a completely filled n-TTT board must contain an n-in-a-row?
This is a game that I played with a friend way before getting into SC. We played for n=4,5. Hope that you enjoy the problem!
|
I was told there would be no math involved upon registering. 1 post wonder.
|
1. post math problem.
2. claim you know the solution.
3. ???
4. reap answers!
|
Belgium9947 Posts
Is a Min-Max tree an allowed solution? Or is that computing the problem instead of solving it?
|
I enjoy reading TL for strategy, news, and its math sub-culture. I think other TLers will appreciate the problem.
Sorry for having a first post. Everyone has a first post. If you know a particular thread this would best be directed to, please let me know.
|
On May 29 2009 06:38 mmp wrote:
I enjoy reading TL for strategy, news, and its math sub-culture. I think other TLers will appreciate the problem.
Sorry for having a first post. Everyone has a first post. If you know a particular thread this would best be directed to, please let me know.
Well you shouldn't apologize because now you have 2 posts. See how easy that was?
|
On May 29 2009 06:38 mmp wrote:
I enjoy reading TL for strategy, news, and its math sub-culture. I think other TLers will appreciate the problem.
Sorry for having a first post. Everyone has a first post. If you know a particular thread this would best be directed to, please let me know.
no no do enjoy the math subculture :p
Read my blogs.
I'll work on this problem in the library.
|
RaGe: assume that n can be arbitrarily (and infinitely) large. Computing a winning solution for some constant n is cool, but there will always be a larger n so it doesn't help very much in the proof.
You are proving that Alyssa's winning strategy *exists* for any n-TTT. The method by which she wins is not the intent of this problem.
|
On May 29 2009 06:45 evanthebouncy! wrote:Show nested quote +On May 29 2009 06:38 mmp wrote:
I enjoy reading TL for strategy, news, and its math sub-culture. I think other TLers will appreciate the problem.
Sorry for having a first post. Everyone has a first post. If you know a particular thread this would best be directed to, please let me know. no no do enjoy the math subculture :p Read my blogs. I'll work on this problem in the library.
I read your problems. Fun stuff. 
|
so if I pick n, my playboard will be n^n size?
|
Belgium9947 Posts
On May 29 2009 06:51 evanthebouncy! wrote:
so if I pick n, my playboard will be n^n size?
edit: i read it as n x n sorry lol
|
On May 29 2009 06:51 evanthebouncy! wrote:
so if I pick n, my playboard will be n^n size?
That is correct. a 4-TTT game is 4x4x4x4, or 256 cells that can be claimed over 4 dimensions.
|
we have a math subculture? awesome ill mosey over to your blog now
|
On May 29 2009 06:45 evanthebouncy! wrote:Show nested quote +On May 29 2009 06:38 mmp wrote:
I enjoy reading TL for strategy, news, and its math sub-culture. I think other TLers will appreciate the problem.
Sorry for having a first post. Everyone has a first post. If you know a particular thread this would best be directed to, please let me know. no no do enjoy the math subculture :p Read my blogs. I'll work on this problem in the library.
I'm really lazy. Link?
Interesting problem. I'm trying to do the proof by induction, not working out well, haha.
Edit: Nevermind, found it.=)
|
+ Show Spoiler +This is probably going to be worded fairly poorly, because I'm kinda bad at formal mathematical proofs, but here goes anyway:
Proof by induction:
Assume that there exists a winning strategy for (n-1)-TTT for the first player. This means that the first player can force a string of length n-1 in n-1 dimensions, creating the immediate threat of a length n string in the (n-1)th dimension, which his opponent must immediately block or he will lose the game. The player can then apply this strategy in each of the (n-1)th dimensions making up the nth dimension. Eventually by filling up the nth dimension with the (n-1) winning strategy, he will be able to force a win in the nth dimension, as the opponent will be unable to block him from winning both in the (n-1)th (n-1)th dimension, and in the nth dimension simultaneously.
There is a winning strategy for n=2, as detailed in the original post: Taking any corner on the first move creates 3 possibilities to win on the next move, only 1 of which can be blocked by the opponent.
Since a winning strategy exists for n=2, and we have shown that a winning strategy for n-1 implies a winning strategy for n, there is a winning strategy for all n. QED.
|
On May 29 2009 07:29 Macavenger wrote:+ Show Spoiler +This is probably going to be worded fairly poorly, because I'm kinda bad at formal mathematical proofs, but here goes anyway:
Proof by induction:
Assume that there exists a winning strategy for (n-1)-TTT for the first player. This means that the first player can force a string of length n-1 in n-1 dimensions, creating the immediate threat of a length n string in the (n-1)th dimension, which his opponent must immediately block or he will lose the game. The player can then apply this strategy in each of the (n-1)th dimensions making up the nth dimension. Eventually by filling up the nth dimension with the (n-1) winning strategy, he will be able to force a win in the nth dimension, as the opponent will be unable to block him from winning both in the (n-1)th (n-1)th dimension, and in the nth dimension simultaneously.
There is a winning strategy for n=2, as detailed in the original post: Taking any corner on the first move creates 3 possibilities to win on the next move, only 1 of which can be blocked by the opponent.
Since a winning strategy exists for n=2, and we have shown that a winning strategy for n-1 implies a winning strategy for n, there is a winning strategy for all n. QED.
Your method sounds perfect for this problem but I'm not quite so sure about the proof itself. I just don't get it as it is worded poorly xD
Edit: Got it.
|
On May 29 2009 07:29 Macavenger wrote:+ Show Spoiler +This is probably going to be worded fairly poorly, because I'm kinda bad at formal mathematical proofs, but here goes anyway:
Proof by induction:
Assume that there exists a winning strategy for (n-1)-TTT for the first player. This means that the first player can force a string of length n-1 in n-1 dimensions, creating the immediate threat of a length n string in the (n-1)th dimension, which his opponent must immediately block or he will lose the game. The player can then apply this strategy in each of the (n-1)th dimensions making up the nth dimension. Eventually by filling up the nth dimension with the (n-1) winning strategy, he will be able to force a win in the nth dimension, as the opponent will be unable to block him from winning both in the (n-1)th (n-1)th dimension, and in the nth dimension simultaneously.
There is a winning strategy for n=2, as detailed in the original post: Taking any corner on the first move creates 3 possibilities to win on the next move, only 1 of which can be blocked by the opponent.
Since a winning strategy exists for n=2, and we have shown that a winning strategy for n-1 implies a winning strategy for n, there is a winning strategy for all n. QED.
The second player can block anywhere anytime in the n^n dimension, he's not forced to play within each (n-1)^(n-1) dimension with the first player.
|
On May 29 2009 07:43 hixhix wrote:Show nested quote +On May 29 2009 07:29 Macavenger wrote:+ Show Spoiler +This is probably going to be worded fairly poorly, because I'm kinda bad at formal mathematical proofs, but here goes anyway:
Proof by induction:
Assume that there exists a winning strategy for (n-1)-TTT for the first player. This means that the first player can force a string of length n-1 in n-1 dimensions, creating the immediate threat of a length n string in the (n-1)th dimension, which his opponent must immediately block or he will lose the game. The player can then apply this strategy in each of the (n-1)th dimensions making up the nth dimension. Eventually by filling up the nth dimension with the (n-1) winning strategy, he will be able to force a win in the nth dimension, as the opponent will be unable to block him from winning both in the (n-1)th (n-1)th dimension, and in the nth dimension simultaneously.
There is a winning strategy for n=2, as detailed in the original post: Taking any corner on the first move creates 3 possibilities to win on the next move, only 1 of which can be blocked by the opponent.
Since a winning strategy exists for n=2, and we have shown that a winning strategy for n-1 implies a winning strategy for n, there is a winning strategy for all n. QED. The second player can block anywhere anytime in the n^n dimension, he's not forced to play within each (n-1)^(n-1) dimension with the first player.
Shouldn't matter. The first player can do the n-1 dimensions in any order, skipping around in them according to what the second player is doing, etc. Also, the first player has n directions to radiate out from his initial play into the nth dimension, and only n-1 of them can be blocked before the second player is forced to respond.
Probably should have written something about that in, but like I said, I'm bad at these, even 3 years ago when I was last in practice at writing them :p
|
On May 29 2009 07:43 hixhix wrote:Show nested quote +On May 29 2009 07:29 Macavenger wrote:+ Show Spoiler +This is probably going to be worded fairly poorly, because I'm kinda bad at formal mathematical proofs, but here goes anyway:
Proof by induction:
Assume that there exists a winning strategy for (n-1)-TTT for the first player. This means that the first player can force a string of length n-1 in n-1 dimensions, creating the immediate threat of a length n string in the (n-1)th dimension, which his opponent must immediately block or he will lose the game. The player can then apply this strategy in each of the (n-1)th dimensions making up the nth dimension. Eventually by filling up the nth dimension with the (n-1) winning strategy, he will be able to force a win in the nth dimension, as the opponent will be unable to block him from winning both in the (n-1)th (n-1)th dimension, and in the nth dimension simultaneously.
There is a winning strategy for n=2, as detailed in the original post: Taking any corner on the first move creates 3 possibilities to win on the next move, only 1 of which can be blocked by the opponent.
Since a winning strategy exists for n=2, and we have shown that a winning strategy for n-1 implies a winning strategy for n, there is a winning strategy for all n. QED. The second player can block anywhere anytime in the n^n dimension, he's not forced to play within each (n-1)^(n-1) dimension with the first player.
I think the keyword is simultaneously. If he attack the n dimension then the other dimensions are vulnerable for attack, which the 2nd player will have to block eventually as it becomes a threat thus giving an opening for the n-dimension.
Another way of thinking is since we assume the n-1 dimensions is optimal, if the 2nd player block on the n-dimension then the 1st player will have 1 extra move on the n-1 dimensions which would win him the game on the n-1 dimensions.
|
So let's do an example.
First player picks the corner (1, 1, 1). Consider the 2-dimension grid (1, x, y), now there are 3 possible winning positions for player 1.
Second player picks (1, 1, 2), then what happens next? I know the strategy for first player to win, but I fail to see how it reduces to 2x2 grid game.
|
|
|
|
|
|
EPT
