Updated 7/16/2013 – See Original Here
Once at a picnic, I saw mathematicians crowding around the last game I would have expected: Tic-tac-toe.
As you may have discovered yourself, tic-tac-toe is terminally dull. There’s no room for creativity or insight. Good players always tie. Games inevitably go something like this:
But the mathematicians at the picnic played a more sophisticated version. In each square of their tic-tac-toe board, they’d drawn a smaller board:
As I watched, the basic rules emerged quickly.
- Each turn, you mark one of the small squares.
- When you get three in a row on a small board, you’ve won that board.
To win the game, you need to win three small boards in a row.
But it took a while for the most important rule in the game to dawn on me:
You don’t get to pick which of the nine boards to play on. That’s determined by your opponent’s previous move. Whichever square he picks, that’s the board you must play in next. (And whichever square you pick will determine which board he plays on next.) For example, if I go here…
Then your next move must be here…
This lends the game a strategic element. You can’t just focus on the little board. You’ve got to consider where your move will send your opponent, and where his next move will send you, and so on.
The resulting scenarios look bizarre. Players seem to move randomly, missing easy two- and three-in-a-rows. But there’s a method to the madness – they’re thinking ahead to future moves, wary of setting up their opponent on prime real estate. It is, in short, vastly more interesting than regular tic-tac-toe.
A few clarifying rules are necessary:
- What if my opponent sends me to a board that’s already been won? In that case, congratulations – you get to go anywhere you like, on any of the other boards. (This means you should avoid sending your opponent to an already-won board!)
- What if one of the small boards results in a tie? I recommend that the board counts for neither X nor O. But, if you feel like a crazy variant, you could agree before the game to count a tied board for both X and O.
When I see my students playing tic-tac-toe, I resist the urge to roll my eyes, and I teach them this game instead. You could argue that it builds mathematical skills (deductive reasoning, conditional thinking, the geometric concept of similarity), but who cares? It’s a good game in any case.
Anyway, that’s Ultimate Tic-Tac-Toe. Go play! Let me know how it goes!
11/18/13: See the follow-up post!
A Partial List of Online Versions and Apps
(Check Comments Below for Others)
- Super Tic Tac Toe
- Tic Tac Toe Ten
- Ultimate Tic-Tac-Toe
- XO9
- Nikhil Baliga
- Niek Haarman
- Kongregate
- Inception Tic Tac Toe
- Khan Academy (open-source online version)
- Live-coding of an online version (French, with English subtitles)
- C code for a strong artificial intelligence
While you’re here, check out Math Experts Split the Check and the epic rhyming proof-poem A Fight with Euclid.
Have you had the opportunity to put this strategy into action yet? This seems like a terrific game to teach during one of those dreary days in the middle of a long unit.
I’ve used it mostly for reward time, or on days when half the class is gone (e.g., for an AP). It might be fun, though, to design a slightly more structured lesson about it. Most kids have sharp game-playing instincts; getting them to articulate their thinking about a game like this might help improve their ability to articulate their thinking in general.
amazing game , lot of things can be learned from it e.g from math , programming to thinking skill so +1 for your post !!!
Glad you enjoyed it!
This is terrific. Getting into action as I write this. 🙂
Is there a generalization for ultimate^n tic-tac-toe? Something like “you played in the xth cell of the yth grid of the zth grid of the game, which means your opponent has to play in the xth grid of the yth grid of the game”?
I wonder how complex such a thing would be…
Ah, that makes sense! Another poster mentioned generalizing it and I couldn’t quite picture how that would work. But your explanation makes sense.
That game sounds dizzying (and long!) but I’ll have to give it a shot sometime when I’ve got a free afternoon.
How about tournament style– playing the Xth cell of the Yth grid of the Zth grid of the game could mean your opponent has to play in the Xth grid of the Yth grid of the Zth game. I’m still puzzling out how to extract yourself out of the loop without enabling massive first-mover advantage (i.e., if the termination condition is to just stack the constraints on the last game, then the first mover could conceivably determine the entire course of the last game).
theres another alternative to this.
In conventional O’s and X’s you have a 3×3 grid in two dimensions.
You could have a 4x4x4 grid where you must achieve a line of 4 X’s or 4 O’s. This is done in 3 dimensions.
by the way, great original idea
I actually used to play such a game as a kid, although I think it was 5x5x5. You could win by 5 in a row in any direction, including diagonally. That meant 5 vertical, 5 horizontal, 5 diagonally along a side, 5 diagonally in one plane, or 5 diagonally from opposite corners. Kept me busy for quite some time with friends. 🙂
I’ve no idea if anyone still sells tthat game.
What happens if a board ties? Is the game considered a tie?
A lot of people have this question, and it’s a really good one.
I’ve always played that the board stays neither X nor O. It leads to some ties overall, but I guess that’s in the spirit of ordinary tic-tac-toe.
nested tic-tac-toe , nice idea ^^.
i think that it can be generalized to have multiple levels of nesting just to make the game a little more harder x’).
That’s a cool idea – how would the next level of nesting work?
I had the same idea. For an n deep game, you track the last n-1 moves, and use them to dictate your position in the board.
So you are showing a 2 deep game, and you’re tracking the last 1 move.
For a 3 deep game, you track the last 2 moves and use them to index into the board. For example, top-right, then lower-left. The 3 deep game also removes the annoying gambits from the 2 deep game.
To remove the gambit style move from the 2 deep game, we’ve been playing where a player cannot choose the same position for consecutive turns.
That sounds like an awesome game!
But I have to ask, is this “What if my opponent sends me to a board that’s full?” even possible? Just like in your gambit example, once you’ve sent a player to the center sub-board nine times, there shouldn’t be any middle squares left on the sub-board.
Anyway, thanks!
Good question. It actually happens at the end of the gambit, because X starts in the very central square. So it sends O to the center board 9 times, but there are only 8 spots available, meaning that the 9th time, O can go wherever O wants.
Evernoted this post, my son is going to love this!
Cool – let me know how it goes!
My colleague and I just tried to play a game but we decided the Orlin Gambit is just too powerful. It becomes very difficult for O’s to come back from. Also, in your final photo, you have one too many X’s filled. If X fills in all the centre squares then it gives O a free placement which is probably not a good strategy.
You might be right. When I play the gambit, I give O that free placement at the end – the board is so symmetrical at that point I don’t really care where O goes. But a better variant might be to claim all but one of the center squares, and then use your ninth move to confine O somewhere.
As someone demonstrated on HN, you can use that to force the game for X in 15 moves (Orlin gambit for all but the NW corner, then take all the NW corners, then win the SE, EE, and NE boards: http://imgur.com/a/tZPjl
What do you do if O responds to the NW corner by playing in the center and giving you the free play right away?
“What do you do if O responds to the NW corner by playing in the center”
That’s a good point! The force relies on getting the free move at the end. Tricky.
Yeah, it’s interesting to see this. I totally underestimated the power of continuing along similar lines.
This AI seems to handle the response that you and Chris are talking about. https://www.khanacademy.org/cs/in-tic-tac-toe-ception-perfect/1681243068
This game is fun. During the whole game we were saying “I will send you here”.
But you gotta play it with smart people
Hi – what happens when there is a tie in one of the smaller boards? (I assume that’s possible…)
good question! I added an edit – see above
You could also make it so the the play with the most squares on the small board wins it.
Or the play which won the small board FIRST.
I’m really glad you shared ‘THE ORLIN GAMBIT’ at the end there. I think it more clearly exemplifies the “How the next battlefield is decided” Rule in a deviously satisfying and easier to understand way than earlier in the the post.
Thanks – I was hoping it would work like that. When I explain the game in person, it usually takes a little back-and-forth to get the rules across, and I’m glad that explaining the gambit accomplishes it.
Love this game! My daughter and I often play this for dibs on the one laptop we have. With your version, I think that I may have a chance of winning instead of losing out of boredom. Thank you
When I was taught and/or play, if you’re sent to any WON board you have the choice to go anywhere. Honestly the Orlin gambit seems like cheesing to me.
Yeah, it’s a little sneaky, and threatens to make the game kind of lame. Although a good player can still win as O.
It may be that I misremembered the rules after being taught. The rule you describe would certainly make sense. Which one do you feel like makes for a better game?
I learned the same rule as cgmorton (with the game called “Tic Tac Ten”). It makes it a much better game, in part because the simplistic strategy you outlined fails.
Agreed. I didn’t realize it, but the strategy I outlined can be extended to ensure that X literally always wins. The “Tic Tac Ten” variant is definitely better.
There should really be some rule governing what happens if you get a tie in one of the smaller grids. Does it become an O or an X… do you empty it and start over, or what? As otherwise you can easily finish the game with a partially empty larger grid. Also, your strategy falls into the trap that we all used to fall into… that the central square of a grid is the most important since the highest number of lines go through it. However, it is usually more optimal to get to a stage where you control opposing corners of a board… adding a third corner often leaves your opponent unable to counter a victory (if they aren’t looking even a reasonable player can fall into this trap from time to time).
When there’s a tie on a small board, I just call it a “neither.” I wish there were a better alternative, but unfortunately emptying it and starting over wouldn’t work out (since you’d have already used up the smaller squares that would send you to that small board).
In principle, I agree with you that a corner can be as valuable (or more valuable) than the center. But in this variant, it’s possible to win two of the small boards ina row, so you don’t usually win by springing unbeatable traps – you win by controlling and winning as many small boards as you can.
But as others have noted, you could adapt the gambit to sacrifice a corner board and claim the same corner square in every smaller board.
Nice game! thanks op.
I have made up a version of tic tac toe that is 4x4x4 to play with friends at the army about 6 years ago.
To play it, you draw 4 boards of 4×4 (naturally the boards will be drawn in a diagonal line to give them a spread out 3d look).
The goal of course is to be the first to get 4 in a line. The line can be a row or a column in any of the 4 layers, or any vertical line across all layers (same position in all layers), or a diagonal across all layers. There are many possibilities, and strategies.
We also later created a c# program to play it instead of drawing the boards. it also helped spot victories, because they are not always easy to spot yourself =)
The benefits of this game:
1. There is no real center, but a central 2x2x2 cube. This way the starting player down’t have superiority for the rest of the game only because he grabbed the center.
2. You have to always imagine how the cube would look if the 4 boards were layered, and I think it improves your spacial perception.
Try it out. it’s fun.
That sounds like a good game! I’ll have to try it out.
http://xkcd.com/832/
of course…
Ah, what a great diagram. The visualization is cooler than the game itself!
Surely you could apply the Orlin gambit to any of the squares- if you start in the top right of the top right, and keep sending the opponent there, you ‘d get the same effect, but a lower loss? Or have I missed something really obvious?
Awesome update to the game though 😀
You’re quite right – lower loss, though also a lower gain, IMO. But I have a friend who prefers to start out that way, and it’s a solid approach.
what if one of the smaller boards is tied?
Good question – I added an edit above. I usually play that the small board is simply left unwon, neither X nor O.
Another fun tic-tac-toe variation is what I call “tic-tac-grow,” where each time you place an x or an o, you also add a square to the grid. Goal is to get 4 in a row.
Cool! I assume you can place it wherever you want, adjacent to an existing square?
You can.
Can’t you use the strategy on any of the large squares? Seems like it would be better to sacrifice an edge of the large grid rather than the center. The trade-off would be that you have only occupied an edge of each of the other smaller grids, rather than the center.
You’re definitely right. I prefer the center move, but taking an edge would be a more-conservative alternative.
I was following until the gambit strategy, I thought that wherever you move the player has to use the board immediately to the left, the gambit strategy just totally threw me of on how to play this
Ah, good question – it’s not the board immediately to the left, actually.
When you make your move, think of the small board that you use as a sort of map of the large board. If I go in the upper-right CORNER of my small board, for example, then my opponent has to go in the upper-right BOARD.
So in the gambit, when X goes in the center square of a small board, that means O has to go in the center board.
Very interesting. What will happen if the inner tile is a tie? I know this is hard to achieve but there is a possibility that it will happen.
Very interesting. What will happen if an inner tile is a tie? I know it is hard to achieve but possible.
Good question. I’ve been telling people that the board counts for neither X nor O.
But it occurs to me that if you wanted to play a more aggressive version, you could count it for BOTH X AND O. That would make overall ties less likely.
I think considering it both X and O would add more fun to the game, thanks for sharing this.
I would use Tic Tac Toe x 9 to teach matrix algebra.
Salman Kahn has a very interesting beginners spoof on Matrix movie.
http://www.khanacademy.org/math/algebra/algebra-matrices
Building quantum algorithms depends on matrix algebra.
http://nextbigfuture.com/2013/05/dwave-512-qubit-quantum-computer-faster.html
NASA, Google and Lockheed have bought a D-wave computer. Is it real?
http://www.wired.com/wiredenterprise/2013/05/google-dwave/
http://nextbigfuture.com/2013/05/google-buys-dwave-quantum-computer-and.html
http://www.newscientist.com/article/dn23251-controversial-quantum-computer-aces-entanglement-tests.html
http://nextbigfuture.com/2013/03/lockheed-martin-talks-about-humanity.html
http://nextbigfuture.com/2013/05/quantum-machine-learning-singularity.html
Quantum computing – Really advanced tutorial
http://michaelnielsen.org/blog/quantum-computing-for-the-determined/
Good general book on Quantum Computing
http://www.amazon.com/Quest-Quantum-Computer-Julian-Brown/dp/0684870045
A new computer paradigm has arrived? How will it arrive?
http://scratch.mit.edu/projects/20917/
http://en.wikipedia.org/wiki/Technological_singularity
“Absent quantum computing, eventually the laws of physics will prevent any further improvements in computing and Moore’s Law will end”
Will 23andMe/Google end disease and control healthcare costs via D-wave?
http://www.bloomberg.com/news/2012-05-11/google-s-brin-makes-strides-in-hunt-for-parkinson-s-cure-health.html
http://en.wikipedia.org/wiki/23andMe
Creepy future from Google-D-wave?
http://www.wired.com/gadgetlab/2013/05/on-google-island/
This had students connecting Obamacare, Sci. Fi. and NSA to Math.
They all were complaining of “Quantum headaches” trying to understand computing in a multiverse. This really got students excited about math.
http://en.wikipedia.org/wiki/Quantum_tic-tac-toe
Dammit! I just wanted to post this.
Everyone, check that link out. It’s really great.
I think the solution for your ultimate way is to disallow the choosing of the position you hat in the previous turn. By this you cannot always mark a x in the middle and after this the game should be fair.
Another variation to prevent this may be to make it so if you’re forced to play to the same board three times that player may play to any board. Kind of like Go’s and Chess’s rules for repeated moves.
Neat! Someone should make this into a cellphone or web app.
Without some kind of anti-repetition rule, X cannot lose, e.g.:
X takes center square in upper left grid, O takes any square in center grid
X takes center square in center left grid, O takes any square in center grid
X takes center square in lower left grid, O wins center grid
X takes lower right square in upper left grid, O takes any square in lower right grid
X takes lower right square in center left grid, O takes any square in lower right grid
X takes lower right square in lower left grid, O wins lower right grid
X wins upper left grid, O takes any square in upper right grid
X wins center left grid, O takes any square in upper right grid
X wins game
I made a wee playable demo for HTML
It doesn’t have a final win condition
http://xoxo.gl/ultimate
I think the Orlin Gambit can be extended to guarantee a win for the first player. If you can beat this “perfect” AI, let me know; I’m not aware of a way to do it, but I haven’t played it for *too* long.
https://www.khanacademy.org/cs/in-tic-tac-toe-ception-perfect/1681243068
For a different challenge, try James Irwin’s Monte-Carlo bot with a rules variation: if your opponent sends you to an already-won board, you may choose your next board:
https://www.khanacademy.org/cs/in-tic-tac-toe-ception/1676336506
I think the Orlin Gambit can be extended to guarantee a win for the first player. If you can beat this “perfect” AI, let me know; I’m not aware of a way to do it, but I haven’t played it for *too* long.
https://www.khanacademy.org/cs/in-tic-tac-toe-ception-perfect/1681243068
For a different challenge, try James Irwin’s Monte-Carlo bot with a rules variation: if your opponent sends you to an already-won board, you may choose your next board:
https://www.khanacademy.org/cs/in-tic-tac-toe-ception/1676336506
I used to employ Tic-Tac-Toe as an exercise when I taught programming.
Occasionally there were a few who found this exercise ‘below par’.
I will be unleashing Ultimate Tic-Tac-Toe on the next smartass who rolls his eyes at regular Tic-Tac-Toe.
[But first I need to work on my game so that I can have an upperhand in my discussions with future students :)]
does android has an app for this game the same concept?? if not then why dont u try to develop an app with this concept..
My family and I enjoy this game (under the name Tic Tac Ten). We also came up with two extensions to Tic Tac Toe that are more complex than the original, but not as complex as this.
One is Pay-to-Play Tic Tac Toe, which penalizes plays in the center and corner and also eliminates the first-mover advantage (http://ethanbradford.blogspot.com/2012/06/this-is-my-favorite-casual-game-for-two.html).
The other is No-Starting-Grid Tic Tac Toe: the first play is arbitrary; subsequent plays go anywhere that keeps a legal 3×3 grid with existing plays (http://ethanbradford.blogspot.com/2012/02/tic-tac-toe-with-no-starting-grid.html).
I played a variation of this that was printed in GAMES magazine years ago(probably the late 1990s). In that version you don’t play to win multiple boards, but to win on any one board! For obvious reasons the Orlin gambit doesn’t work anymore, instead the gameplay is one of calculating extremely far ahead to see where you can force the other player into a bad situation.
I dont know what you teach, but this would be a great starter program for new programming students. Its a fun project thats easy to design( a simple modification of a tic tac toe game that could be made beforehand) and you could have fun designing the interface, and maybe even an AI for it.
Hello there, this games sounds interesting, but there’s something I don’t understand:
“You don’t get to pick which of the nine boards to play on. That’s determined by your opponent’s previous move. Whichever square he picks, that’s the board you must play in next. (And whichever square you pick will determine which board he plays on next.)”
That’s what I don’t get. So if I start in the middle box, I tell them where they place next? And after their move, they pick a spot for me? What’s stopping us from winning a single box, since some of us might only worry about one box at a time (if that’s possible)?
Where you play in the middle box determines which box I play in. If you play in the middle of the middle box, I play in the middle box. If you play in the top-right square of the middle box, I play in the top-right outer box.
Why do the O’s cluster when the center board is finished? That wasn’t explained very well…
O has won the centered board. When the X takes other centers, why would make a move to the center board that he has already won? I’m confused.
Cool game. One thing: did you notice that in your top drawings (the one board game), X could have won if they had placed an X in one of the other corners…
I (re-re-re?)-invented this “Recursive tictactoe” one year ago in a dorm of the ENS with a friend (Fof0) and we played with several variations of the rules :
– when a (big) square is full, there is exactly one square leading to it. Immediatly and freely grant it to the player that has not begun (and change your record of starting player for the next). Mathematicians will understand the reason for this 🙂
– a (big) square can be awarded to both players if they both satisfy the winning condition (that way all hope is not lost for a square when the opponent wins it) (when we played, we considered that a tie is awarded to none)
– diagonals does NOT count as a winning condition (!) –> this really changes the game. All squares are *exactly* equivalent with that, with no preference over the center or corners.
– Basically, you can play (a x b)^ n \forall a,b,n>1 , playing in the sub-rectangle [ x_1 … x_n ] after someone played in the square [x_0 … x_n]. We never tried a \neq b, but it should be interesting 🙂
– we played (3×3)^2 ; (3×3)^3 ; (2×2)^3 and (2×2)^4.
I do not recommend the 3×3 ^3 because it has 729 cases and it took 4+ hours to finish. the 2×2 ^4 is slightly better, but it took ages to figure out the moves each time 🙂
Reblogged this on The Daily Fillip.