Higher-Dimensional Tic-Tac-Toe | Infinite Series
Вставка
- Опубліковано 20 вер 2017
- Viewers like you help make PBS (Thank you 😃) . Support your local PBS Member Station here: to.pbs.org/donateinfi
Regular tic-tac-toe can get a bit boring -- if both players are playing optimally, it always ends in a draw. But what happens if you increase the width of the board? Or increase the dimension of the board? Or increase both?
Tweet at us! @pbsinfinite
Facebook: pbsinfinite series
Email us! pbsinfiniteseries [at] gmail [dot] com
Previous Episode
How the Axiom of Choice Gives Sizeless Sets | Infinite Series
• How the Axiom of Choic...
The standard game of tic-tac-toe is too easy. How can we, as mathematicians, play with the combinatorics of tic-tac-toe? There are (at least) three easy ways to modify the game of tic-tac-toe: increase the width of the board - like this 5x5 board - increase the dimension of the board - like this 3x3x3 board - or increase both, like this 4x4x4 board.
Challenge Winner of the How the Axiom of Choice Gives Sizeless Sets:
For Your Math
Written and Hosted by Kelsey Houston-Edwards
Produced by Rusty Ward
Graphics by Ray Lux
Assistant Editing and Sound Design by Mike Petrow
Made by Kornhaber Brown (www.kornhaberbrown.com)
Resources:
Hales/Jewett paper: www.ams.org/journals/tran/1963...
Golomb/Hales paper: library.msri.org/books/Book42/...
• Math Mornings on Sunda...
www.austms.org.au/Gazette/2005...
Special Thanks: Benjamin Houston-Edwards and Nathan Kaplan
Mathologer Video:
• Death by infinity puzz...
Special thanks to Matthew O'Connor and Yana Chernobilsky who are supporting us on Patreon at the Identity level!
And thanks to Mauricio Pacheco and Nicholas Rose who are supporting us on Patreon at the Lemma level!
A really interesting variant I remember learning as a kid from Games Magazine is a variant called Order and Chaos. It's played typically on a 6x6 board with both players able to play either X or O however they like. One player, Order, is trying to form a line of either five Xs or five Os (Order wins in either case). The Chaos player wins if Order doesn't manage to make any lines of five in a row before the board is filled.
This variant is significantly trickier than standard tic tac toe games because, unlike a traditional tic tac toe game where every mark you place is beneficial, in Order and Chaos extra Xs or Os may or may not assist you depending on how they're arranged and whether or not you are Order or Chaos.
And unlike normal tic tac toe the standard method of proof that the first player can always win or force a draw doesn't work with this game. This is in part because of the game's asymmetry - the first player's win condition isn't the same as the second player's win condition, so if the first player simply "copies the second player's strategy" (eg First player is Order and is using a winning strategy for Chaos) it won't work.
A really fascinating tic tac toe variant!
I can think of some other variations that might also be interesting:
1. Increase the number of players.
2. Allow the length of a winning line to vary separately from the grid size, eg. you could have a 4x4 board where you only need 3 in a row to win.
3. Increase the dimension of the winning 'line', for example a 3d grid where you need to completely fill a 3x3 plane to win.
I used to play 5x5 with a friend in grade school, with length 4 as a win. We got pretty good at it where I believe we could force a draw still. My memory has faded quite a bit, but I think it was mostly about controlling the 3x3 grid in the middle as in the regular game.
I think a version that requires a 2D plane to win would be really interesting. I'd imagine that it's fairly easy to force a draw for small numbers of dimensions, and that it would take quite a large dimensionality before it even comes close to there being a chance of winning.
ua-cam.com/video/wnMHX1eQtIk/v-deo.html
@@vananderson2895 You are basically describing connect four, kind of...
gomoku (or u ci qi) is a classic game of getting 5 in a row on an infinite 2d board (usually played on a finite go board). It's fun and challenging (for humans) (but I think it has been solved by computers)
"If you´d never played 4by4by4by4 tic tac toe, pause here and give it a try"
Play a few games? What? You think I have friends?
ImaginaryMdA you can play against yourself
I wonder if there's a way to start an "Infinite Series Fans Tic-Tac-Toe Tournament" online...
Oooh, I'd like to play some w=5,d=4 games against other people!
That Problem is already solved by AI . No need to Play against a human.
ImaginaryMdA just write a simple AI to play it with you.
The best game rule is having an infinite board (a notebook page irl) and aiming for five in a row.
112BALAGE112 probably a forced draw, too?
That's what I am used to playing too, and I have been wondering if a winning strategy exists for the first player.
Aiming for six in a row seems to be more entertaining in my opinion because it looks more balanced for player 2.
#5inarow
112BALAGE112. en.wikipedia.org/wiki/Gomoku#Optional_.28.22house.22.29_rules
It is a forced win for first player. There is a japanese game called Gomoku in which the first player is banned from certain arrangements (e.g. 4 in a row with both ends open).
The other obvious change that would keep it an abstract strategy game would be to increase the number of players.
What about if you lose instead of win when you make a line?
@TaiFerret I'd guess it would always be a draw except for low d and w values.
I have done that with 2 of my friends, a 3 player, with 5x5 grid n 2d game, but it was a draw more often than not.
My friends and I used to play higher dimensional tic tac toe in highschool math by passing around graph paper notes (Yes, we were that nerdy!). We would usually play on 3^n boards with the number of players about n. After some time it seemed that first player could win if the number of players was less than n or that a tie could be forced if it was n or greater. Something like a 5 player 3^6 game is definitely fun though!
TaiFerret invented, also only X tic-tac-toe game
My favorite variant of Tic-Tac-Toe is Ultimate Tic-Tac-Toe, where you have a large Tic-Tac-Toe board with nine smaller boards, one in each big square. The rule is that the second player has to play in the same big square as the corresponding small square of the previous player (so if P1 plays in the upper-right square of any small board, P2 must play in the upper-right board for their next turn). Whoever takes a small board wins that area, and "sending" an opponent to that board afterward allows them to play wherever they want. Whoever gets three small boards in a row wins!
I know there's a winning strategy, but it's so complicated that I don't know what it is and most people I meet don't either, so it's a really fun game every time I play!
Putting boards inside each other is another way to "expand" the Tic-Tac-Toe board, on top of increasing the side length and the number of dimensions.
Haven't watched the video yet, but I must say this: My desk-neighbour and I used to play mental 4D-tic-tac-toe in 12th and 13th class during boring classes. The dimensions were:
left, middle, right
top, middle, bottom
back, middle front
yesterday, today, tomorrow
That's usually how I imagine 4D items
yeah, all you need is fourth coordinate and it's 4D.
What is a winning “line” in 4d?
Moritz Ernst Jacob how does the time work lol
Moritz Ernst Jacob
Give us an example of you playing. How do you think about those dimensions?
*1966* "I bet in the future we'll have 3D chess!"
*2017* "We made 3D tic-tac-toe!"
a guy has made 4D chess so yeee (its on youtube just sertch it)
2D space (standard chess) + 1D time +1D timeline (same time but different reality)
this is 4D chess
but there are many 4D chess
this is a 4D chess
4D dimensions (4 towers of 4 4x4 boards)
this is very very 4D
5D chess and 7D chess: allow us to introduce ourselves.
7:30
An exhaustive proof (even one done by a computer) is a rigorous proof. It is just as valid as any deduction.
SO the conclusion is, the computer did not create a rigorous proof. Just because the game resulted in a draw or a win for the first player every time the computer played against itself, does not prove that that will ALWAYS do so. Even 999 million draws or wins proves nothing. If the computer were to rigorously examine the entire search tree, that would be a proof, but we do not know, from the information provided, that the computer actually did that.
In high school we would play 4 x 4 x 4 x 4 often, but the win was given to the person with the *most* 4s in a row, not the first.
There should be a forced winner in that game. There are 4 dimensions of attack and 3 blocking O's cannot stop the 4th attack. X's should have a forced win as long as the player knows how to play, since X has first move and advantage of setup.
A 1x1 board will also guarantee that the first player always wins.
Coin flip it is... 🙃😁🙃😜🙃🤔🙃🥺
yes, it literally showed that in the video in the table
*Tadashi Tokieda*
VS *Matt Parker*
_epic-tac-toe_
PlayTheMind
Oh, please make this happen!
In 4D please
They would play not in grid but in Parker square
And with feet
#parkercircle
That brings me back to my childhood. I and a friend in the boy scouts would sketch out four dimensional tic tac toe games in the dirt and play. (You use 9 regular tic tac toe boards.) Other friends thought we were weird.
I'm sure those same friends were also probably eating dirt while you were expanding your minds lol
The common rules that we played by in highschool (when sitting in boring physics lessons):
- 5 in line wins
- "board" is unlimited
aka gomoku
My wife and I built a 4x4x4 tic tac toe board. We quickly learned that "x" always won. So, to make the game more interesting we built random chance into the start of the game.
We did this by making 64 tiles, each with the coordinates of one unique space on the board. At the beginning of game play, each player would draw three tiles at random. So for instance, "x" might draw tiles with coordinates (3,1,4), (4,2,2), and (3,1,3) and "o" might draw tiles with coordinates (1,1,2), (4,3,1), and (2,2,2). Each player would then place one of their markers in each of the spaces specified on the tiles.
After this random start, game play would return to normal with each player taking turns placing a game piece in the location of their choosing.
For the slight chance, that someone will actually read this:
This topic is very close to my hearth. I’ve spend some quality time to getting know 4D space more intimately. And one of products of this, was my version of 4D 3T (Tic-Tac-Toe for short). The rules were different though. I don’t know, how elsewhere, but in my county 3T are played on 2D board, usually 19×19, and winning pattern is line of length 5. Now, the number of surrounding fields of one particular field is 3^n - 1, where n is the dimension. So usually it’s 8, which leaves us with 4 directions. In higher number of dimensions this “combination” number rises exponentially, obviously. This lead to 4D game with the rule of winning 6-long line. It’s usually played in tesseract of edge-length 9 or better, 11. How that look like? Field of fields. You have 11×11 grid of 11×11 grids. It’s surprisingly easy to work with, because you don’t need to visualize something, what our brain cannot visualize: 4D space. You work with what you know, you only need to think about the relations between 11×11 fields. Of course, length 11 is kind-of arbitrary, it might be different. Why odd number? So you have the central point.
In similar fashion, you can put together 5D or even 6D field, but it gets insanely large really fast.
I say it all the time. Higher dimensions are fun. I don’t like our 3D space, I want more dimensions. 4, that would be awesome. Because if you have tesseract of edge-length 1, the full-space diagonal line is 2 units long.
Interesting stuff!
Gonna try to implement it on hardware
you can also create a variant where you have a big 3x3 board, and inside each square of that is another 3x3 board. And a player can go in any square of any of the smaller boards when it's their turn. Once a small board has been won by either X or O, that large square is turned into an X or O respectively and of course the object is to win the big board.
A variation I really like of this is:
You can only play in the small board corresponding to the square in which your opponent played last.
Ej: If your last move was in the TOP-RIGHT corner of the CENTER board I must play in the TOP-RIGHT board.
Then I play in the MIDDLE square of the TOP-RIGHT board. You must play your next turn in the MIDDLE board.
It's really cool.
This series continues to be extraordinary, an the Phd is very good at presenting the information
How about non-euclidean tic-tac-toe?
I think "non-euclidean" doesn't really make sense for discrete grids. (Try to define parallel lines & distance, then try to find a way parallel lines meet or diverge).
You *could* close the topology by connecting the edges of the board, e.g. making a torus or sphere in the 2D-variant.
I think it really depends on how far you are willing to generalize out tic-tac-toe. We could replace squares by some other shape and tile the plane accordingly. This would give some kind of tic-tac-toe board. In that case, regular heptagons would be an example where we need the hyperbolic plane.
If you want to go really wild, you could take the "dual" of a tic-tac-toe board by turning the squares into vertices and touching squares into corresponding edges. This makes a tic-tac-toe board a graph. We could then conceivably play some kind of "tic-tac-toe" on any finite graph.
If graphs are too wild and we want to stick with more traditional boards, we can convert from an arbitrary graph to a "tic-tac-toe board". To do this we just need edges to not cross, so the graph's genus would tell us what kind of topological manifold we need (i.e. toroidal, sperical, Klein-bottle-like, etc.). Interestingly, we only need 2D surfaces to do this.
However, embedding into suitable 2D surfaces might still squish our "boxes" in unpleasant ways, so to fix that we could force them to be regular polytopes. This would then allow us to consider "regular" boards only possible in spaces with exotic curvature, dimension and topology.
I just watched the video on the Cops and Robbers Game, and she mentions your comment about non-euclidean tic-tac-toe. I'm not sure why she says that she's not sure how that would go, because a little later she mentions some of her favorite variants of tic-tac-toe, and one of those is "playing on a cylinder", and more generally, she says "playing on other surfaces". That would be non-euclidean two-dimensional tic-tact-toe.
Some spherical topology would be interesting. How about hypersphere tic tac toe?
TacoDude314
Klein Bottle Tic-Tac-Toe
We used to play 4D tic-tac-toe with four players in our heads in school. If everybody plays optimally, it's as boring as regular tic-tac-toe but the fact that you have to memorize everything and the fact that it's easier to overlook threats in four dimensions made it a fun pastime.
Speaking of which, is there a similar table to the one at 7:28 but with _p_ as the number of players added as an additional dimension? Being restricted to two players seems a bit weird when your playing on a board of arbitrary dimensions and with an arbitrary number of dimensions.
"First off, the idea that the sum of the natural numbers is -1/12 is a highly nonstandard way of adding numbers." That's one way of putting it 😂😂😂
Yeap; another way of putting it would be simply saying "...is bullshit".
Anyway, I believe Mathologer covered this very nicely some time ago :)
Saying that the divergent sum of all natural numbers is -1/12 is not bullshit, it has some applications within mathematics, but assigning a value to something which diverges is usually not done.
You say that some parts of the chart haven't been "rigorously proven" but have been proven by a computer simulation. But if a computer exhaustively calculated every possible game, does that not count as a rigorous proof, since it can't be refuted? (assuming the program itself was proven to be correct)
The "smallest" unproven board is d=3, w=5. That's 125 cells, which would mean roughly (125 choose 63), or about 3 * 10^36 possible board configurations. (Reasoning: Xs can go in 63 spots and Os in the other 62.) This is probably an order of magnitude too high since not all games play out all the way, but that's still too many possible paths to exhaustively test in a relatively short amount of time. In any case, this strategy won't help you at all for boards of higher dimension and/or width.
So, I'll bet they came up with guesses for those board dimensions by taking semi-random walks down the game tree and seeing who wins.
How do you know the computer didnt make a mistake?
That's why I said "assuming the program itself was proven to be correct" - as there exist tools to formally verify programs (see Coq for example)
Yeah, that counts as a proof. But, as El'endia points out, it's a combinatorial explosion. There's a lot of possible tic-tac-toe games once you start increasing the width and dimension.
PBS Infinite Series Higher and higher dimensions would mean more and more symmetrical games. it seems like only checking unique games would drastically decrease the amount of games one would have to check, making this much more plausible. Is this intuition correct?
Love this video! When I was a kid (about 11?) I wrote out all possible games for the standard 3x3 (ignoring symmetries), to verify that the strategy worked. I encoded the squares as digits from 1 to 9. It's possible I still have that little red notebook somewhere, with pages and pages of digit sequences... I hope so.
I love this comment.
it actually helped me to "visualise" a fourth spatial dimension thxxx
She's great precise and intuitive ;Love your Show , More.
I've already made that with some friends, in a 3x3x3 the first player always wins and the game gets intersting in 4x4x4 but gets very slow at 3x3x3x3, in fact so slow that we started to play with 3 players, but in a 3x3x3x3 the 3rd player usually have a gigantic disvantage, so we have never tried 4x4x4x4
yeah i shuld watch the video before comenting
3^4 is easy win though, do you even understand the way it works?
Bootyrockineverywhere You can adapt the strategies of a 3x3 to any 3^n so we've restrained some moves
but after we used 3 players the strategies dont work anymore
edit: doesnt --> dont
I played 4 x 4 x 4 x 4 quite a bit in high school
Multi-dimensional tic-tac-toe ... such a brilliant idea, why did I never think of this one? It could actually be fun to play :)
I liked this episode!
Way back in the early 1960s, I was a DS, Data Systems Technician, in the US NAVY, working on NTDS, the Naval Tactical Data System. As a joke, our school class programed a 4x4x4x4 game, and found out, the hard way, that the computer always wins if it has the first move. Now I see from your chart that all W=D boards are wins for the first player. Phoo.
I absolutely loved how you transformed TicTacToe into an interesting mathematical problem :D Yaaay
Intuitively, if dimension d and width w is a win, I don't really see how it can be a draw in dimension D>d and width w. Can't player 1 just play all their moves on one d-dimensional "slice"/"hyperplane" of the grid? If player 2 plays elsewhere, that's a waste of a move, if player 2 always plays in the same slice, it's effectively a dimension d game on that slice, which player 1 wins. In other words, I don't see how the "magic cutoff" d(w) isn't just the first win in that column, contrary to what is said at 9:14.
If someone could point out where I'm wrong in my reasoning, I'd love to hear it.
I guess you can't prove that it'd be a waste of a move, since player 2 doesn't know which hyperplane player 1 decided to choose
But even if player 2 never wastes their move, it's like we're playing a d-w game. The *best* that player 2 can do is comply and play in the hyperplane, which is still a win for player 1.
That's what I thought too. I think the problem is that one has to prove that O is truly wasting their move and can not move in the new dimension in a way that their second move both blocks X and develops their own line, thereby forcing X into defense.
"If player 2 plays elsewhere, that's a waste of a move." That seems intuitively true, but you have to consider that player 2 can also win by placing w-1 O's in a column perpendicular to the initial grid. This means that if in dimension d there exists a strategy for player 2 such that [player 2 gets the board in a state from which it will take player 1 at least w further turns to win], then player 2 can win in dimension D by doing that strategy and then making a line outside of the d-dimension plane.
I'm guessing the idea doesn't (necessarily) work because player 2 could obviously build a line in a different hyperplane as quickly as possible. You want to say that, because player 2 plays second, player one will always win before him - but is that true? (e.g. player 1's strategy may involve building some complex trap, which requires too many moves before player 2 wins).
For your idea to work, you'd need player 1 to be able to win in d dimensions using at most x+w moves (x is the number of moves player 2 has made on the same board/hyperplane), which might be true, I don't know. But bear in mind this is a now a new game, since player 2 is also (essentially) allowed to 'skip a move'.
It's sad that you find an incredible amazing channel and come to know on the same day that it doesn't upload any more.
In high school, my friends would play 3x3x3 TTT, but you would have to get 2 rows of 3, one going on the "x,y plane" (a normal TTT game) and one across the Z axis. It works quite well
You say that the strategy can never result in a forced loss because X can just steal O's strategy. However, I think we're going over something nontrivial here. In chess there is the idea of zugzwang, which is when it would be to a player's benefit to make no move. That said, it is easy see the fact that no move in tic tac toe can create a disadvantage since at worst you are blocking lines for your opponent, and not removing any protection. Good episode in general!
So good!!
can't wait for a video on negative dimensions
I wouldn't have thought 'great mystery'. I'm going to take this into account.
8:24 About the second statement:
If X has a winning strategy that works in a board with dimensions d, then on a board with dimensions d+1, X simply needs to translate all of their moves to the higher dimension by ignoring that dimension. As in, they simply need to add a constant to all their coordinates for any new dimension. For example if x has a winning strategy on a d=3 board then for each move where X would places their symbol at (x,y,z), then on a d=4 board X would place their symbol at (x,y,z,1).
If X does that, O has three theoretical options:
1.) If O ignores the new dimension like X does, then the optimal strategy for d+1 will be the same as for d just with the last dimensions coordinate set to a constant. As that strategy already resulted in a loss at d, it will also result in a loss for d+1.
2.) O could try to utilize the extra dimension. However, to force a draw, O needs to block more lines in d+1 than they did in d as X was already winning in d, however if we assume X's lines are constrained to points that can be described as (x,y,z,1) then any symbol O places with the format (x,y,z,w) where w is not 1 will effectively block 0 lines as that point will not land on any of the lines X can form under those constraints.
3.) Those two considered together, O cannot force a draw. O's last option is to form a line through the new dimension before X wins with their strategy. Strategy stealing might be an argument here, but that would void argument 1 and 2 as X would change strategy. However, another argument is for any width w > 2, O will have to 'Skip' w-2 turns by placing symbols that will block none of X's potential lines as described by point 2. For example, for w=3 and d+1=4, if x is constrained to (x,y,z,1) due to their strategy, to win by utilizing the new dimension O would have to place symbols at (x,y,z,2) and (x,y,z,3). One of which can be the winning move, but the other move is spent not blocking X. Any move O "skips" this way brings X one move closer to a complete line. X already has a turn advantage (Symbols X can place without interference from O) from going first. Gaining w-2 more turn advantages by O not interfering with X's lines puts X at w-1 turn advantages. That means the next move X makes would be a win, and that is before O can make their winning move. Put simply, O cannot make a line faster than X by going outside of X's "area".
I also like the variant (I think Numberphile made a video about it?) where you *lose* when you get 3 in a row.
Also, I wonder what an infinite dimensional infinite-size tic tac toe would look like
Connect Four - loved that game as a kid
In a 3x3x3 grid, the first player can always force a fork, which means they create two lines that only require one more mark to win in a single move.
I ganeralized tic-tac-toe the following way, which I called poker-tic-tac: take a 4-times-4 board and play normal tic-tac-toe on it. With 4 in a row it would be drawn, but here we add the following rules: When the board is full (of course without a 4-in-the row) count the 3's and the player who has more 3's won. If the number of threes is equal for both players: count the number of pairs, which are not already part of a 3-row. If this numbers are equal too, the game is drawn. poker-tic-tac has also no winnig-strategy and is therefore drawn, but it is very sophisticated to play!
we play a more complicated version on graphing paper called SOS. Player 1 is "S", Player 2 is "0". You have to spell out SOS. The difference here compared to Tic-TAc-Toe is that the width can be increased, but the winning line only needs to be 3squares long.
"Increase size"
"Increase dimention"
"Increase both"
me: What about increase player count?
then it’ll be
X, O, ◽️, and 🔺
@@spamtongspamton9900 itlll be xyz
@@spamtongspamton9900 don’t forget A, B, and Y lol
Tic tac toe but whenever the first person wins, the board size increases to make it more difficult. Whenever there is a draw, the board dimension increases to make it easier to win.
What about multiple players?
Or a finite dimensional game, but infinite in board length?
What happens if you add in a rule that games can not begin in the middle square? or perhaps that neither player can play the middle square on their first turns? or how about an alternate rule that the middle square is a wild card that simply playing a line that runs through it would be considered a win by either player... or the opposite, blocking any move on the middle square???
For the center-as-wildcard case, X will always win on a 3x3 board: if X starts in a corner, O is forced to play the opposite corner to prevent X from winning on the next turn, then X plays one of the middle edge squares adjacent to their first square, leaving two possible wins (one through the center, and one along that edge), and O can only block one; if X starts in the middle of an edge, O is again forced to play on the opposite middle edge, and X again plays one of the corners adjacent to their first square, which again provides them with two possible wins. I haven't thought through any higher-dimensional 3-wide games, but if this variant works similarly to standard Tic-Tac-Toe, then there should be a winning strategy for X (assuming the relevant conjecture holds). The case for games on a board wider than 3 cells might be complicated by the question of what you count as the center square(s) (for example, on a 4x4 board, the middle 2x2 block would be the center squares, presumably, but on a 5x5 board, is it only the single centermost square, or the entire 3x3 interior block?)
for higher dimensional 3^n tic-tac-toe, making the center just completely unavailable makes the game fun. Also, one player per dimension works well too.
Thanks for the interesting video!
What real world applications are there for this?
That's awesome! How about multi dimensional dots and boxes?
A way to generalize tic-tac-toe even further is to have the number of pieces that need to be in a row not necessarily equal the width and/or height of the board. One of the infinite variants you can achieve this way is called "luffarschack" in Sweden. The name literally means "hobo chess". It's played on an infinite board (or whatever amount of graph paper you have available) and requires five or more in a row to win. Since there are no borders and no center square there is only one possible first move. I tried to look up an English name for this, but didn't find one. Wikipedia translates it to the Japanese game "gomoku", and its free-style variant seems very similar.
There was a piece on 'generalized' tic-tac-toe in (March?) 1957 in the Mathematical Games column in Scientific American. The proof that 3x3x3 was always a win for X was in there; and a way of playing 4x4x4x4 was shown. What you do, is to draw a 4x4 array of 4x4 squares. It takes some preparation before your first game, to figure out all the possible winning lines.
As the author of the column, Martin Gardner, put it:
".. a win of four in a row is achieved if four marks are in a straight line on any cube that can be formed by assembling four squares in serial order along any orthogonal or either of the two main diagonals."
Which he accompanied with a diagram showing 6 examples.
He also stated that, "The first player is believed to have a sure win, but the game may be a draw if played on a 5x5x5x5 hypercube." So these games hadn't yet been determined for certain; the former, then suspected to be a win for X, is now known to be; the latter was, and still is, believed to be a draw.
And he gave the following expression for the number of possible winning lines on a (d,w) board:
½[(w+2) ͩ - w ͩ]
which he credited to Leo Moser in the American Mathematical Monthly, Feb. 1948, p. 99.
My nerdy high-school friends and I had some fun playing the 4⁴ game...
There are other methods of improving tic-tac-toe, such as by nesting it. This is called Ultimate tic-tac-toe and it is played on 9 normal boards arranged like a larger tic-tac-toe board. Each of these boards can be scored on using lines which in turn are used to make a larger line of three scored boards on the large board.
The rules are:
1. Whichever square one player plays in determines what board the next player must play in.
Example: If player X plays in the upper left square of the central board. Then player O must play in some cell of the upper left board. If O then played in the upper left of the upper left board, then X must also play in the upper left board.
2.To win, a player must "score" three boards to make a row, column or diagonal on the larger board. (Multiple players are allowed to score in the same small board).
3. If all the squares in a board are full and there is still one square leading to that board left, that square is greyed out unused (this only happens to the board where the first move took place).
It is more mindbending then it seems like it has any right to be.
The next obvious step would be to nest it again and have a massive board containing 9 games of ultimate. Whenever one player scores on one of the ultimate boards with a line of 3 on one of the smaller boards, the other player would have to play in the ultimate board corresponding to that smaller board and play would continue on that ultimate board until another line of 3 is scored. The metaultimate game being won when 3 ultimate boards are won in a line.
I wonder what the winnability grid would look like if it were made three-dimensional by adding a dimension for the number of times it has been nested (called n) and if nested tic-tac-toe games are more or less winnable then "standard" multidimentional ones with w by w rows and columns.
I think I have a proof for the special challenge.
First we will use the model described in the video. We can treat a drawn game as splitting all the possible points into two sets, one for the points player X chose and the other for the points player O chose. Since the game is a draw all 27 points have been chosen, implying there are a total of 27 moves. Since X goes first, they have played 14 moves. Therefore |X|=14 and |O|=13. In addition, neither X nor O contain a line since it is a draw.
We will now prove that X must contain a line.
Let us take a point in X, (a1, b1, c1). For all, other points with a1 we cannot have points containing b2 and b3 or c2 and c3 otherwise a line will be formed. Assume that the other points have b2 or c2. This results in a total of 2*2=4 points in X. Similarly, there are an additional 4 points for points leading with a2. This results in the following at points being a part of X:
(a1,b1,c1) (a1,b1,c2) (a1,b2,c1) (a1,b2,c2) (a2,b1,c1) (a2,b1,c2) (a2,b2,c1) (a2,b2,c2)
Note that any point with a3 will create a line in X. Therefore, the remaining points must have either a1 or a2. However, the only points that can be added that contain a1 or a2 contain either b3 or c3. Therefore, any additional point will create a line in X.
Thus, we cannot create X such that it does not contain a line and consequently a draw cannot exist.
I rly like ur video
A little problem .
For w=1
d=1 . One box with coordinate : 1
Winning line: 1
X plays first and wins.
d=2. Two boxes stacked up with coordinate (1,1) & (1,2)
Winning line: (1,2),(1,1)
X plays first , O plays second. It's a Draw
d=3 three boxes stacked up on each other with coordinates (1,1),(1,2),(1,3)
Winning line : (1,1),(1,2),(1,3)
X plays first, O plays next, X plays last. It's a Draw.
The chart in the video shows it's a win always for w=1 in all dimensions.
One cool variant I’ve played is a version where each space on the board contains another smaller tic tac toe board. The rule is that the position played in the smaller board dictates where in the large board the next players move must be.
During my uni time we had a fun variant where you played a standard 3x3 grid but in each was its own 3x3. Players can put a symbol in any of the 81 spaces. When a mini game is won the player gets the mini board as their shape. This brings in the concepts of sacrificing mini games to gain advantage over others. Give it a try!!!!!
I remember working out 4D tic-tac-toe in High School and playing it with some class mates... and theorizing higher dimentionality, but realizing even at the 4D method it was hard to visualize it (2d grid of 2d planes is how we drew it) ...
I like the version of tic-tac-toe that my kids taught me. You have a larger 3x3 board, and each cell in it is another regular 3x3 board. You capture a larger cell by winning its smaller board. You alternate as normal, and choose between which small cell you want to take. I don't know which type of game this provides, but it's simple enough to play with my kids and complicated enough that there isn't an obvious strategy for me, so I enjoy it.
great content
How to always win in 3x3 tic tac toe
(referring to player 1/X or O)
place the mark on C1
when player 2 places a mark on A1,A2, or B1 place your mark on C3
When player 2 places a mark anywhere except B2 you can place a mark on B2 and have 2 options to win either way
alternative: if player 2 places a mark on B2 you can always place a mark on A3 and win either way (50/50% chance of happening or it ends in a draw no matter what)
Player 2 goes first:
Wherever it places always sabotage player 2 (50% chance of wining 25% chance of losing 25% chance of being a tie):
As a mathematician, "d" used both as a function and a parameter killed me x(
A friend and me played 4³-ttt for dozens if not hundrets of hours in high school*. figured out how the rules apply and that 3³ makes the first player win every time. we got about an 1-2% draw-rate and found that it's to much work to draw 4-dimensional fields (on paper layed out as a 2d-projection).
We also had a little tower with marbles that we build just for fun to play real 3D, even if we were fine with the 2D projection.
It was a bummer to realize that this wasn't the first time someone had brought ttt to higher dimensions tough :D
'almost always while ignoring math lessons
4³ might be not fair with a perfect strategy, but neither of us found it after hundrets of games. it was really playable.
On the Win-Draw chart at 7:30, it appears the cut-off points (last possible win value for width) for odd d is ((d+1)/2)^2 and for even d, it is something like ((d+2^(1/2))/2)^2..The odd one seems quite plausible; but, the even one is seems iffy. They do, however, fit for what is given in the chart.
Towards the beginning you say that if there’s a winning strategy, it will belong to X because they could steal the strategy from O, but that doesn’t work in Tic Tac Toe since there’d be another mark in the board
For those who want to know more, here are three links. The first link is intended for a general audience, but the second two links require comfort with mathematical reasoning (e.g. mathematical notation, proof by induction).
A fantastic 40-min public talk about `Ramsey Theory': ua-cam.com/video/AZnvP86N20I/v-deo.html
Notes on Ramsey Theory. The end of Chapter 1 has a proof of Hales Jewett: tartarus.org/gareth/maths/notes/iii/Ramsey_Theory.pdf
Notes on Games. tartarus.org/gareth/maths/notes/iii/Hypergraph_Games.pdf
"Pause here and give it a go". Yeah let me just whip out my 3x3x3 tic tac toe board from under my ass where I always keep it for occasions just like these.
Awesome
I might play 3x3x3, looks interesting
[01:07] left out the fourth, easy way to modify the game-we played 5-in-a-row-tic-tac-toe on 'infinite' chalkboards in highschool (we used the multi-chalk-holders to draw the grid).
Somebody has probably already noted this, but the comment at the end that the only way for an infinite series to yield a finite number is for the numbers in the series to get smaller and smaller might be misinterpreted to mean that *all* such series yield a finite number. A well-known counterexample is 1/1 + 1/2 + 1/3 + … + 1/n + … .
Their is also a 4th way to make tic-tac-toe more interesting , by playing it with a misère rule set where the first to lose win.
That D vs W chart. You should add a 3rd dimension to that: Players. D vs W vs P: I wonder how that'll work out. P would have to start with 2, right? The result for 1 player is obvious. Honestly, I think it gets fun from 3 players. There's a constantly shifting alliance between 2 of the 3 players to stop the 3rd player from winning.
.... dimension of board,
length four,
optimal play,
pairing strategy,
3x3x3x3 game,
Hales-Jewett Theorem,
winning row,
stretch of the immagination,
continuation of the line segment,
diagonal colomn,
optimal play,
magic cut-off's,
strictly decreasing,
width five,
dubble-u boxes,
the second coordinates ....
0:11 THAT'S A GLIDER
I have a friend who was making 4D Tetris by making 4 3D Tetris wells in a grid- that was in the 90's and he's super successful now so- he better get on it already so I can play it finally, my patience is running out! :D
I played 3d 3x3 Tic Tac Toe with friends when I was in school and we quickly worked out it was always a win for X, so we 'invented' a variant where you kept playing until the board was filled, and whoever had the most completed rows/columns/diagonals at the end would be the winner (rather than just stopping after just one row/col/diag had been filled)... has anyone else 'invented' this variant before? Has it been studied at all? Optimal play is harder there so it's less clear whether it's always a win for X.
Hello, excellent video! Could you help me with something?
I am doing the tic-tac-toe judge and I have to calculate the probability of winning, any idea how I can calculate it?
taking into account a dimension and that the board is 3x3.
Great, now time to make an engine to play all of this!
What when you have to complete a row with a length less than the width of the board (3-line on a 4-board, etc)?
I played 3X3X3X3X3 or five dimensional tic Tac toe once in the sand at the beach with a second grader. The second grader won. The hard part was drawing the board. Playing was easy. I have also played 4d and 3D tic Tac toe many times. I have also tried ultimate tic Tac toe which I personally think is the best variation of tic Tac toe. Oh and I’ve tried 4X4X4 and 4X4X4X4. I have never understood quantum tic Tac toe. I have programmed normal 3X3 tic Tac toe on my calculator when I was younger. If anyone is looking for an interesting twist on tic Tac toe which I haven’t yet mentioned try the app hypertac
A curious easy to play game is the 3 dimensional tic-tac-toe where one has gravity, so one can only place a an x or o in a box if the boxes below it are filled (this has the advantage of also having easy to make physical versions of the game). In this sense, this is essentially a very tiny board of "Connect 4" but with connect 3 and a 3 by 3 by 3 grid. It turns out that in this game x has a winning strategy. Note that you cannot prove this simply from a strategy stealing argument since making a move allows a different move to now take place since one can then place on top of that square.
Joshua Zelinsky you could sell that to a board game maker
Physical versions of this one already exist. I've seen both ones that have a series of grid polls and one places little cubes between the polls as well as a version that had 9 long pegs sticking out with dark and light colored little balls that had a hole in them and one placed the balls on the pegs.
Actually, Hales-Jewett says that not only is a draw impossible, eventually even if you don't allow one coordinate to decrease while another increases, draws become impossible (for w=3, this happens at d=8.)
True! And since O can never win, it must be X that wins if a draw is impossible.
How about three player Tic-Tac-Toe?
how about n player Tic-Tac-Toe
Or 97864858 player tic tac toe and 100000^10000000^1000000000000
Board
Then you have to deal with the issue of cooperation, which is a totally different problem.
n-dimensional n-player Tic-Tac-Toe works nicely
what is interesting is a 5*5 board, but you only need 4 in a row to win. This includes diagonals other than the main diagonals.
but what if you play tic-tac-toe with periodic boundary conditions, i.e., on a torus. For a 3 by 3 grid I assume there is a winning strategy. Is there any references for higher grid sizes/ dimensions on this?
+onlynamelefthere I don't know if there is, however winning lines in this setup are the same as the sets of the game SET! (which is a fun game on its own).
Thanks for your reply. Didn't knew this game. I will look into this
But playing on a 3*3*3*3 board, requiring a 2d plane instead of a line to win works great! We have agreed though that the very middle point, (2, 2, 2, 2), is an "xo": both players can have that as a part of their winning plane.
I'm quite sure that it is a draw case, but it's complex enough for it to be fun. Basically played with a sudoku-looking grid. Figuring out the planes is really fun, they require two operations (-1, 0, 1) for different coordinates that are then mixed to get the 9 points. Some are trivial (for example, a line of 9 in the grid is always a plane in 4d) but some are quite complex.
Please tell me how you get those curls, I want to do them for myself. Thank you so much.
This just made me want to play Pentago.
We played a game where each square of a larger tic tac toe board contained another tic tac toe game. To claim one of the larger board's squares you had to win the game in that square
One of the challenges was deciding what action in that case would make the game most balanced. We eventually settled on draws go to whoever has the least number of their own symbol in that square. That way actively pursuing a square your opponent was ignoring would be an easier way to claim it, but also riskier if they attempted to block you.
Like normal tic-tac-toe, it was a pretty dumb game. But it was fun since everyone knew the optimal strategy for normal tic-tac-toe and the new one had a learning curve to it
What abt graphing a piecewise constant function with (infinitely/finitely) many pieces aka staircase function
There's an easy way to win if you're O. Let X go first, and put your first O well away from X's move. When X puts a mark that would threaten a win next move, then put an X to complete the line of three. Draw a line through it, claim a win, and feign ignorance (or stupidity).
X threatens a win if it takes a cube adjacent to O's first move, hence O must block. Notice how O's first and second moves are not aligned, so wherever X moves next, it cannot yet win. If X moves chooses a cube adjacent to its 2nd move but not aligned with the 1st O, then X threatens to win in two ways: by completing the line connecting its second and third moves, or the one connecting its first and third moves. The first option is not blocked because both vertices lie on a face with only one O and they are not aligned with it. Neither is the second option since that line goes through the center and into the opposite face, where the only O is already aligned with the center and X's second move. Hence, no matter where O moves now, X can always win.
The card game "Set" seems to be related to this... you make triplets of cards that are all the same or all different on various attributes.
Tic-Tac-Toe?
Tic-Tac-Toc-Toe?
Tic-Tac-Toc-Tuc-Toe?
*TIC-TAC-TOC-TUC-TEC-TOE*
Computer scientists have proven infinite Connect 4 (Connect 4 on an infinite board) to be a draw. However, it would be interesting to add extra dimensions.
Challenge answer:
In this proof, player order and play order do not matter, but for the ease of notation, suppose the center square is X. In any 3-by-3 plane, if all four corners are the same mark, then a player will win no matter how the remaining squares are filled. Let us call this the corner lemma. Another observation is that if three corners of a 3-by-3 plane is marked with the same mark, say
X_X
___
X__
then there is only one way for no one to win on that plane, namely
XOX
OOX
XXO
We will call this lemma 3C.
By the corner lemma, at least one corner of the top plane must be X. Without loss of generality, suppose the top-left-back corner is X. Apply the corner lemma to the right plane. X forms a line if it occupies the lower-right-front corner. The top-right-front corner being X and the lower-right-back corner being X are the same case by symmetry, so we will consider two cases: the top-right-back corner being X and the top-right-front corner being X.
Case 1: (the top-right-back corner being X)
Apply the corner lemma to the front plane. Any of the two lower corners being X will win X the game, so X must occupy one more upper corner, say the upper-right-front corner. The bottom does not have any corner marked X yet, using the corner lemma, we have to fill the bottom-right-back corner with X, since the other corners would form a line with the top corner and the center. Applying lemma 3C to the top plane and the right plane, we have
XOX
XOO
OXX
__O
_XO
__X
__X
__X
__O
X wins with top-left-middle, center, lower-right-middle.
Case 2: (the top-right-front corner being X)
In the top plane, the top-center square must be O. This means, one more corner in the top plane must be X lest O form a line. Without loss of generality, the top-right-back corner is X. We are back to case 1.
Therefore, a 3-by-3-by-3 tic-tac-toe game cannot tie.
Gobblet Gobblers is also a good version of tic-tac-toe
I find the ultimate tic-tac-toe (en.m.wikipedia.org/wiki/Ultimate_tic-tac-toe) a very interesting variant.
In this game, there are nine 3x3 regular tic-tac-toe subgrids in a 3x3 grid. Starting move can be in any of the subgrids, but here's the catch: the next player must play on the grid that is at the same position as the last move in the subgrid. For example, if you play cross to the bottom left subgrid, top right square, your opponent must make her next move to the top right subgrid.
When someone wins a regular tic-tac-toe subgrid, it is replaced with giant x or o, depending who made the winning move.
If subgrid ends in a tie, it either gets ignored or owned by both the players. If a player is sent to move to a subgrid that has ended, she can select any subgrid to make her next move.
Game ends when one player gets a row of three giant marks in the grid (she wins) or when every subgrid has ended.
What algorithm in color prediction game. Does it work on mid square or in linear congruential method