|
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.
|
I've worked it out, though if you don't understand recursive-embedded matrix terminology it will be hard to understand:
Answer:+ Show Spoiler +
|
On May 29 2009 08:17 hixhix wrote:
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.
I may be misinterpreting a winning strategy, but I think any time when you have n adjacent units together in an n TTT game you win.
The way I'm envisioning the problem:
Start in dimension 1 (in this case your z)
Since in every dimension you can always adjoin two squares together no matter your starting strategy (i.e. you "win" in that dimension). The optimal choice could be a number of things for the sake of argument, suppose you chose (1,2,2)
Once you "win" that dimension, by definition you can also win in the next dimension (lets say the x dimension). Suppose the opposing player chooses (1,3,3). You can win the x dimension, by choosing any adjacent square in the x-dimension adjacent to (1,1,1) suppose you chose (2,1,1)
You then have a string of (2,1,1), (1,1,1), and (1,2,2).
I think this is problem is isomorphic to just playing the (2x2) game over and over again, and asking whether you can win every time.
However, I might be misinterpreting a winning strategy.
|
but if you think of it as winning in the N=2 game over and over again you miss the that let's say in N=4 you win in the corner, then the next move is your oppononets, thus it's not a string of 2x2 games where you start and can apply the same strategy.
edit: i think you're on the right track though, proof by induction seems to be the correct way to do it.
|
On May 29 2009 09:32 jeppew wrote:
but if you think of it as winning in the N=2 game over and over again you miss the that let's say in N=4 you win in the corner, then the next move is your oppononets, thus it's not a string of 2x2 games where you start and can apply the same strategy.
edit: i think you're on the right track though, proof by induction seems to be the correct way to do it.
I think I may have been a little vague about the last statement. If one views the battle to win each dimension as a repetition of the 2x2 game, then it is isomorphic. Which essentially is the induction proof.
|
On May 29 2009 09:13 outqast wrote:
....
Since in every dimension you can always adjoin two squares together no matter your starting strategy (i.e. you "win" in that dimension)....
....
This is so wrong. As I said before, the second player can choose to play any where, he's not forced to play within the reduced space as assumed in many posts here.
For example, assuming the 4^4 space, the first player chooses (1, 1, 1, 1), then second player chooses (3, 2, 4, 4), those belong to disjoint spaces (there exists no space that contain a valid row (length 4) and contain both points) and from the point of view of the second player, he becomes the "first player" to play in his space.
I'm not saying that there is no winning strategy for the first player, I'm saying that the argument has been dicussed so far saying that n-dimension space can be reduced to (n-1)-dimension space is incorrect.
|
On May 29 2009 10:08 hixhix wrote:Show nested quote +On May 29 2009 09:13 outqast wrote:
....
Since in every dimension you can always adjoin two squares together no matter your starting strategy (i.e. you "win" in that dimension)....
....
This is so wrong. As I said before, the second player can choose to play any where, he's not forced to play within the reduced space as assumed in many posts here. For example, assuming the 4^4 space, the first player chooses (1, 1, 1, 1), then second player chooses (3, 2, 4, 4), those belongs two completely different spaces and from the point of view of the second player, he becomes the "first player" to play in his space. I'm not saying that there is no winning strategy for the first player, I'm saying that the argument has been dicussed so far saying that n-dimension space can be reduced to (n-1)-dimension space is incorrect.
It is the ability to "win" in that dimension, i.e. adjoin two units together, not the ability to play in the dimension. By the nature of the game, once you have started playing you have "played in all of the dimensions."
Note: There are a vast amount of winning strategies from any point in the game. They have just identified one that works.
|
I guess there is a big misunderstanding. Let's formalize the problem and all definitions and so it's easier to discuss.
Problem:
Given an n-dimension space, a valid point X in this space is represented by n coordinates X(a1, ..., an) where 1 <= ai <= n for all i from 1 to n.
A valid row is a set of n points X1, ... Xn where each Xi is a valid point and Xi = X1 + (i-1) * V, V is an n-dimension vector V(v1, v2, ..., vn), vj = 0 or 1 for all j, and there is at least one non-zero vj.
Assuming there is an algorithm A that allows the first player to choose points forming a valid row in a (n-1)-dimension space, prove that first player can use A to choose points forming a valid row in an n-dimension space.
...
Let's play with a small space (3-dimension), you're the first player and you have the algorithm A, I'm the second player. Can you step by step show me how the first player *use* A to choose a valid row of 3 points. (algorithm A guarantees that you can choose a valid row of size 2 in a 2-dimension space).
First player picks the corner (1, 1, 1).
Second player (me), picks (1, 1, 2).
Now, what's your next move (based on algorithm A & your reduction protocol) ?
|
On May 29 2009 10:40 hixhix wrote:
I guess there is a big misunderstanding. Let's formalize the problem and all definitions and so it's easier to discuss.
Problem:
Given an n-dimension space, a valid point X in this space is represented by n coordinates X(a1, ..., an) where 1 <= ai <= n for all i from 1 to n.
A valid row is a set of n points X1, ... Xn where each Xi is a valid point and Xi = X1 + (i-1) * V, V is an n-dimension vector V(v1, v2, ..., vn), vj = 0 or 1 for all j, and there is at least one non-zero vj.
Assuming there is an algorithm A that allows the first player to choose points forming a valid row in a (n-1)-dimension space, prove that first player can use A to choose points forming a valid row in an n-dimension space.
...
Let's play with a small space (3-dimension), you're the first player and you have the algorithm A, I'm the second player. Can you step by step show me how the first player *use* A to win. (algorithm A guarantees that you can choose a valid row in a 2-dimension space).
First player picks the corner (1, 1, 1).
Second player (me), picks (1, 1, 2).
Now, what's your next move (based on algorithm A & your reduction protocol) ?
Calling each dimension x,y, and z
So you picked (1,1,2) which is the z dimension,
Thus I will use my A algorithm on dimension x and y at point (1,2,1) Thus I have 2.
You are force to go (1,3,1) or else I will win.
Now I will use my A algorithm on dimension y and z so I go (1,2,2)
You are force to go (1,3,3) to stop me from forming a diagonal on the y and z dimension.
Now I go (1,2,3) and I win.
I have (1,2,1) ( 1,2,2) and (1,2,3)
By using my A algorithm I control where you move next because You are force to go there to stop me. Thus I basically control your every move after your first move.
|
On May 29 2009 10:57 toopham wrote:Show nested quote +On May 29 2009 10:40 hixhix wrote:
I guess there is a big misunderstanding. Let's formalize the problem and all definitions and so it's easier to discuss.
Problem:
Given an n-dimension space, a valid point X in this space is represented by n coordinates X(a1, ..., an) where 1 <= ai <= n for all i from 1 to n.
A valid row is a set of n points X1, ... Xn where each Xi is a valid point and Xi = X1 + (i-1) * V, V is an n-dimension vector V(v1, v2, ..., vn), vj = 0 or 1 for all j, and there is at least one non-zero vj.
Assuming there is an algorithm A that allows the first player to choose points forming a valid row in a (n-1)-dimension space, prove that first player can use A to choose points forming a valid row in an n-dimension space.
...
Let's play with a small space (3-dimension), you're the first player and you have the algorithm A, I'm the second player. Can you step by step show me how the first player *use* A to win. (algorithm A guarantees that you can choose a valid row in a 2-dimension space).
First player picks the corner (1, 1, 1).
Second player (me), picks (1, 1, 2).
Now, what's your next move (based on algorithm A & your reduction protocol) ? Calling each dimension x,y, and z So you picked (1,1,2) which is the z dimension, Thus I will use my A algorithm on dimension x and y at point (1,2,1) Thus I have 2. You are force to go (1,3,1) or else I will win. Now I will use my A algorithm on dimension y and z so I go (1,2,2) You are force to go (1,3,3) to stop me from forming a diagonal on the y and z dimension. Now I go (1,2,3) and I win. I have (1,2,1) ( 1,2,2) and (1,2,3) By using my A algorithm I control where you move next because You are force to go there to stop me. Thus I basically control your every move after your first move.
First, in the reduced space, it's only 2x2, if you just said xy- at (1, 2, 1), it's 2-dimension space of size 3x3. Please specify what the reduced space is.
Anyway, you can ignore that because the example was the intention, the second player chooses the point in the same space with the first player.
How about this:
First player: (1, 1, 1)
Second player: (1, 2, 2)
And when you reduce to the trivial case, please specify 2-dimension space of size 2x2 .
|
On May 29 2009 11:11 hixhix wrote:Show nested quote +On May 29 2009 10:57 toopham wrote:On May 29 2009 10:40 hixhix wrote:
I guess there is a big misunderstanding. Let's formalize the problem and all definitions and so it's easier to discuss.
Problem:
Given an n-dimension space, a valid point X in this space is represented by n coordinates X(a1, ..., an) where 1 <= ai <= n for all i from 1 to n.
A valid row is a set of n points X1, ... Xn where each Xi is a valid point and Xi = X1 + (i-1) * V, V is an n-dimension vector V(v1, v2, ..., vn), vj = 0 or 1 for all j, and there is at least one non-zero vj.
Assuming there is an algorithm A that allows the first player to choose points forming a valid row in a (n-1)-dimension space, prove that first player can use A to choose points forming a valid row in an n-dimension space.
...
Let's play with a small space (3-dimension), you're the first player and you have the algorithm A, I'm the second player. Can you step by step show me how the first player *use* A to win. (algorithm A guarantees that you can choose a valid row in a 2-dimension space).
First player picks the corner (1, 1, 1).
Second player (me), picks (1, 1, 2).
Now, what's your next move (based on algorithm A & your reduction protocol) ? Calling each dimension x,y, and z So you picked (1,1,2) which is the z dimension, Thus I will use my A algorithm on dimension x and y at point (1,2,1) Thus I have 2. You are force to go (1,3,1) or else I will win. Now I will use my A algorithm on dimension y and z so I go (1,2,2) You are force to go (1,3,3) to stop me from forming a diagonal on the y and z dimension. Now I go (1,2,3) and I win. I have (1,2,1) ( 1,2,2) and (1,2,3) By using my A algorithm I control where you move next because You are force to go there to stop me. Thus I basically control your every move after your first move. First, in the reduced space, it's only 2x2, if you just said xy- at (1, 2, 1), it's 2-dimension space of size 3x3. Please specify what the reduced space is. Anyway, you can ignore that because the example was the intention, the second player chooses the point in the same space with the first player. How about this: First player: (1, 1, 1) Second player: (1, 2, 2) And when you reduce to the trivial case, please specify 2-dimension space of size 2x2 .
For the first example my winning diagonal was in the 3x3 of the y and z plane with x=1.
your move (1,2,2) stopped me from winning in the y and z 3x3.
So now I will just do the same strategy but I will use it on the x and y plane with z=1.
IF I go (2,1,1) i create a row of 2. The reduced space is the 2x2 of the x and z or x and y.
Either one works, you pick.
But I will go (2,2,1) So that it's obvious the reduced space is x and y.
You are forced to go (3,3,1) to stop me
So I go (1,2,1)
Now you go (1,3,1) to stop me from winning.
Now I go (3,2,1) to win
I have (2,2,1) (1,2,1) and (3,2,1)
|
Hmm, I'm still not convinced. It's not like you use algorithm A at all and winning strat for 3-dimension space is simple. In this small space, you can control the next move of the second player since each row is size of 3, forcing him to block right away. However, in case of larger spaces, say 100-dimension space, you can't force him to play in the next move. He can always wait until a valid row is formed 90+ % and just chooses 1 point to block it.
Also, there is no guarantee that a valid row in a (n-1)-dimension space can lead to a valid row in n-dimension space.
For example, assuming the following is a 2-dimension cut from a 4-dimension space
o o x o
o x o o
x o o o
o o o o
"x x x" is a valid row in the 2-dimension space of size 3 but it can't lead to a valid row in 2-dimension of size 4.
Anyway, I guess we cant agree, let's relax.
|
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? (I am trying to prove this myself at the moment).
|
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.
I disagree with this, maybe this is the right approach, but as I see how it is worded, I don't think this is a conclusive proof.
Let's say we have a winning strategy in the n-1 dimension, that means we have a string of n-1 length in an n dimensioned TTT game. However, it is now the second players turn to make a move, and can immediately "corner" off the n-1 length string (since all the strings are only 1 dimensional), thus negating the n-1 length string which would have won in an n-1 TTT game, but is now blocked in an n dimensioned game.
edit:
Let's say you're in the very first n-1th x n-1th dimension, trying to force an n-1 string. Since you have assumed in the induction step that you can indeed do this, you force a string of n-1. However, he goes second and blocks it, while you start the next iteration in the next n-1th x n-1th dimension. You go first, but you went first in the first iteration as well, and makes no difference. In order to succeed, you need to force two threatening strings simultaneously. That is in order to succeed in the n-1 dimension TTT game, you are forcing two n-2 dimensional strings. To win in an n-dimensioned game you need to force two n-1 strings simultaneously, which I don't think you can do with this approach.
This is also why I don't think all cases are simply analogous to the base case(s). In a 1 dimensional game, your first move forces a win, but before you've won, you have threatened with 1 possible win condition. In a 2 dimensional game, your first move threatens 3 possible win conditions. In a 3 dimensional game, it takes a few moves (do it in your head), but your final win condition comes out to threatening only 2 win conditions. I imagine following this step, the rest of them threaten only 2 simultaneous conditions.
On May 29 2009 10:24 outqast wrote:Show nested quote +On May 29 2009 10:08 hixhix wrote:On May 29 2009 09:13 outqast wrote:
....
Since in every dimension you can always adjoin two squares together no matter your starting strategy (i.e. you "win" in that dimension)....
....
This is so wrong. As I said before, the second player can choose to play any where, he's not forced to play within the reduced space as assumed in many posts here. For example, assuming the 4^4 space, the first player chooses (1, 1, 1, 1), then second player chooses (3, 2, 4, 4), those belongs two completely different spaces and from the point of view of the second player, he becomes the "first player" to play in his space. I'm not saying that there is no winning strategy for the first player, I'm saying that the argument has been dicussed so far saying that n-dimension space can be reduced to (n-1)-dimension space is incorrect. It is the ability to "win" in that dimension, i.e. adjoin two units together, not the ability to play in the dimension. By the nature of the game, once you have started playing you have "played in all of the dimensions." Note: There are a vast amount of winning strategies from any point in the game. They have just identified one that works.
You are missing their point. Winning in a smaller dimension successfully does not ensure that win condition will remain viable following your opponent's turn. If you successfully connect 2 in a 2x2 dimension, your opponent can immediately block it in a 3x3 dimensioned game, leaving your entire win condition from the 2x2 game useless.
|
|
|
This reminds me of school. Which is never good, but I will admit it is an interesting problem 
Macavenger seems to have it down. I'm not sure that can be considered an actual proof though. It's been a while since I did any kind of discrete mathematics.
|
Some google searching shows that this problem has been studied and is very hard. I'm no longer at all certain that draws are impossible for large n.
http://en.wikipedia.org/wiki/Hales-Jewett_theorem is an interesting theorem regarding this problem, though a combinatorial line is a little less common than an ordinary tic-tac-toe line. The Hales-Jewett number seems to grow rapidly, which is a very bad sign. It is likely that the problem is complicated enough that a proof is impossible.
|
Intuitively, it seems to me that the higher the dimension, the more difficult it is to win. It takes more consecutive moves and ever increasing lengths of strings in order to force a win condition, which only means that the opponent has all the more time to continue to corner off each and every win attempt before it even gets close.
And since the win condition is always a 1-dimensional string, pursuing a win condition does not necessarily open up n dimensional (possibly much less) more possible strategies.
|
haha 7 posts all about this math questions? isnt this a Starcraft forum?
From what I'm seeing there's no math needed to answer this question. im sure theres a formula but if you play Tic-Tac-Toe well you automatically know that first gets to win.
The larger the grid the more options for the person to connect to their previous spots.
but the more = harder to connect the n amount
Also the game will end in ties often since the second person will put pieces in places where connecting the n amount is impossible.
hence the answer: there is no set strategy to win. the game will end in tie like normal tic-tac-toe if the second person is smart. (wow that was hardddddd)
edit: proper punctuation
|
On May 29 2009 10:08 hixhix wrote:Show nested quote +On May 29 2009 09:13 outqast wrote:
....
Since in every dimension you can always adjoin two squares together no matter your starting strategy (i.e. you "win" in that dimension)....
....
This is so wrong. As I said before, the second player can choose to play any where, he's not forced to play within the reduced space as assumed in many posts here. For example, assuming the 4^4 space, the first player chooses (1, 1, 1, 1), then second player chooses (3, 2, 4, 4), those belong to disjoint spaces (there exists no space that contain a valid row (length 4) and contain both points) and from the point of view of the second player, he becomes the "first player" to play in his space. I'm not saying that there is no winning strategy for the first player, I'm saying that the argument has been dicussed so far saying that n-dimension space can be reduced to (n-1)-dimension space is incorrect.
I think hixhix is right. Because to "block" a winning tuple, all you need is to interrupt one of it's elements, so player 2 could've filled up your other dementions to a point where you no longer have a sure win on those n-1 dimention space anymore.
|
On June 04 2009 07:30 opsayo 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. I disagree with this, maybe this is the right approach, but as I see how it is worded, I don't think this is a conclusive proof. Let's say we have a winning strategy in the n-1 dimension, that means we have a string of n-1 length in an n dimensioned TTT game. However, it is now the second players turn to make a move, and can immediately "corner" off the n-1 length string (since all the strings are only 1 dimensional), thus negating the n-1 length string which would have won in an n-1 TTT game, but is now blocked in an n dimensioned game. edit: Let's say you're in the very first n-1th x n-1th dimension, trying to force an n-1 string. Since you have assumed in the induction step that you can indeed do this, you force a string of n-1. However, he goes second and blocks it, while you start the next iteration in the next n-1th x n-1th dimension. You go first, but you went first in the first iteration as well, and makes no difference. In order to succeed, you need to force two threatening strings simultaneously. That is in order to succeed in the n-1 dimension TTT game, you are forcing two n-2 dimensional strings. To win in an n-dimensioned game you need to force two n-1 strings simultaneously, which I don't think you can do with this approach. This is also why I don't think all cases are simply analogous to the base case(s). In a 1 dimensional game, your first move forces a win, but before you've won, you have threatened with 1 possible win condition. In a 2 dimensional game, your first move threatens 3 possible win conditions. In a 3 dimensional game, it takes a few moves (do it in your head), but your final win condition comes out to threatening only 2 win conditions. I imagine following this step, the rest of them threaten only 2 simultaneous conditions. Show nested quote +On May 29 2009 10:24 outqast wrote:On May 29 2009 10:08 hixhix wrote:On May 29 2009 09:13 outqast wrote:
....
Since in every dimension you can always adjoin two squares together no matter your starting strategy (i.e. you "win" in that dimension)....
....
This is so wrong. As I said before, the second player can choose to play any where, he's not forced to play within the reduced space as assumed in many posts here. For example, assuming the 4^4 space, the first player chooses (1, 1, 1, 1), then second player chooses (3, 2, 4, 4), those belongs two completely different spaces and from the point of view of the second player, he becomes the "first player" to play in his space. I'm not saying that there is no winning strategy for the first player, I'm saying that the argument has been dicussed so far saying that n-dimension space can be reduced to (n-1)-dimension space is incorrect. It is the ability to "win" in that dimension, i.e. adjoin two units together, not the ability to play in the dimension. By the nature of the game, once you have started playing you have "played in all of the dimensions." Note: There are a vast amount of winning strategies from any point in the game. They have just identified one that works. You are missing their point. Winning in a smaller dimension successfully does not ensure that win condition will remain viable following your opponent's turn. If you successfully connect 2 in a 2x2 dimension, your opponent can immediately block it in a 3x3 dimensioned game, leaving your entire win condition from the 2x2 game useless.
I think I am confused about a winning strategy.
Is a winning strategy an nx1 string in a single dimension because I just interpreted it as you just have to have n boxes that are touching in some way.
If it is by my definition, then my logic holds. Otherwise, I have no idea what is going on.
I don't think the problem is not well articulated...
|
Some ideas:
Let's ssuppose our algorithm A starts at the corner, i.e. (1,1,1,...1)
How many paths to win we can create with a corner opening?
For dimention 2x2, we have 3 ways
(1,1)-(1,2) two straight edges
(1,1)-(2,1)
(1,1)-(2,2) one diagonal
For dimeion 3, we have
(1,1,1) (2,1,1) (3,1,1) 3 straight edges
(1,1,1) (1,2,1) (1,3,1)
(1,1,1) (1,1,2) (1,1,3)
(1,1,1) (1,2,2) (1,3,3) 3 semi diagonals on planes
(1,1,1) (2,1,2) (3,1,3)
(1,1,1) (2,2,1) (3,3,1)
(1,1,1) (2,2,2) (3,3,3) 1 full diagonals
For dimention 4, we have
(1,1,1,1) (2 111) (3 ...) (4 ...) 4 straight edges
(1,1,1,1) (1 2 1 1) (.3..) (.4..)
(1,1,1,1) (1 1 2 1) blah
(1,1,1,1) (1 1 1 2) blah
And?
And?
And?
|
The question I want to answer is, given a "string" of length n, say
(pt1, pt2, pt3, ... ptn)
What kind of string is a "winning string"?
Remark:
Note that each pt_i looks like (a1, a2, ... an), that's to say each point is a n-tuple, and a string is a n collection of these n-tuple points.
For instance, a winning string in 3D might look like
((1,1,1), (2,2,2), (3,3,3))
Once we collectively answer that question, we will see that out of ALL the winning strings, which one can player_1 claim in such way that player 2 cannot block.
Again, we'll formalize our terms, build on top of hixhix, I add this one more definition:
a winning string is a collection of points in which, once all points are claimed by one player, he wins.
|
Some intuition:
2D has total of 4 points, Since any 2 points in 2D forms a winning string, total number of winning string will be (4 choose 2) or 6.
3D has total of 27 points, how many winning strings are there?!
4D, 5D?
HAhAH this is already fun!
Cmon play with me here
|
On June 04 2009 08:12 Muirhead wrote:Some google searching shows that this problem has been studied and is very hard. I'm no longer at all certain that draws are impossible for large n. http://en.wikipedia.org/wiki/Hales-Jewett_theorem is an interesting theorem regarding this problem, though a combinatorial line is a little less common than an ordinary tic-tac-toe line. The Hales-Jewett number seems to grow rapidly, which is a very bad sign. It is likely that the problem is complicated enough that a proof is impossible.
For other people working on this, I'll like to emphasize Muirhead's post. Note that OP does not claim to know that answer, only that he played around with the cases n=4 and 5.
@evanthebouncy!
Well, a winning string in one such that for each coordinate the pt_i_n (i is varying, n is fixed) are counting up from 1 to n, counting down from n to 1, or is constant. This is because if you project a winning string to a single axis, it must appear as one of three cases above. Conversely, a string whose projection to every coordinate is as above must be a winning string.
edit: note that we cannot have every coordinate constant. As long as one coordinate is varying it is fine.
edit2: The number of strings in n dimension TTT is 1/2 times (n+2)^n - n^n. This checks with the 3 dimensional case in the OP.
|
On June 04 2009 11:20 datscilly wrote:Show nested quote +On June 04 2009 08:12 Muirhead wrote:Some google searching shows that this problem has been studied and is very hard. I'm no longer at all certain that draws are impossible for large n. http://en.wikipedia.org/wiki/Hales-Jewett_theorem is an interesting theorem regarding this problem, though a combinatorial line is a little less common than an ordinary tic-tac-toe line. The Hales-Jewett number seems to grow rapidly, which is a very bad sign. It is likely that the problem is complicated enough that a proof is impossible. For other people working on this, I'll like to emphasize Muirhead's post. Note that OP does not claim to know that answer, only that he played around with the cases n=4 and 5. @evanthebouncy! Well, a winning string in one such that for each coordinate the pt_i_n (i is varying, n is fixed) are counting up from 1 to n, counting down from n to 1, or is constant. This is because if you project a winning string to a single axis, it must appear as one of three cases above. Conversely, a string whose projection to every coordinate is as above must be a winning string. edit: note that we cannot have every coordinate constant. As long as one coordinate is varying it is fine. edit2: The number of strings in n dimension TTT is 1/2 times (n+2)^n - n^n. This checks with the 3 dimensional case in the OP.
That is correct, I do not know of a solution. I talked with another math-bent friend who believes it is unprovable, but isn't certain.
|
|
|
|
|
|
EPT
