Actually, Maybe There's Only 1 Game of Tic-Tac-Toe
Vložit
- čas přidán 12. 01. 2024
- Turns out there are both more and fewer Tic-Tac-Toe games than I originally imagined. And how better to explore the possibilities than with some exciting new diagrams...
As promised, here's a link to my code: github.com/MarcTheSpark/TicTa...
...and if you want to attend a live chat in which I walk through the code, you can sign up for my Patreon! / marcevanstein
Oh and check out my teaching website for info on lessons and workshops: teaching.marcevanstein.com/
This video makes use of several public-domain and creative-commons licensed visuals:
- commons.wikimedia.org/wiki/Fi...
- commons.wikimedia.org/wiki/Fi...
- commons.wikimedia.org/wiki/Fi... - Věda a technologie
In case you want some very silly merch: shop.marcevanstein.com/ I also made an announcement video featuring some epic Tic-Tac-Toe background music. czcams.com/video/O1gZxmvs8Oc/video.html
O goes first btw
I wonder what are those 4 times O can win (on 8:50)
POV: You've never seen the movie "War Games"
Also, I found the optimal play when I was 12 or so: Top left corner if you go first. Unless someone has brushed up on their tic-tac-toe theory, they'll probably mostly pick their first move at random, which is a guaranteed win for 7 of the 8 remaining squares, the center being the safe one. If they pick the center, you can either pick the square that is a "knight's move" away from the corner or the opposite corner. [Just based on nimbers] The former leaves you with a roughly 94% win rate and the latter a roughly 91% win rate.
Are you in the spectrum?
A strange game… the only perfect move is not to play
How about a nice game of chess?
czcams.com/video/s93KC4AGKnY/video.html
Turns out that Tic-Tac-Toe is indeed a stupid game. Only a fool would engage in a such an activity, knowing that the result of your actions, no matter how well thought or well planned they be, will certainly lead to a draw.
@@sutirkno, that is only assuming your opponent knows how to play well too. If they're not as good as you, you may still win instead of tying. However, it still isn't fun.
How about a game of global thermonuclear war, instead?
@@zotaninoron3548 Personally, Joshua, I think I'll stick to that game of chess you offered.
This was on my mind the entire time while watching your other video. "But wait, isn't tic-tac-toe solved and always a draw?". But your way of framing the problem as two non-perfect humans playing using a reasonable heuristic seemed sensible too. In the end, with perfect play, there is indeed only one game of tic-tac-toe which ends before it even begins.
Tis why I refuse to play with my daughter
This game is rigged
Yeah obviously it just depends on what you assume about the players..... In the other video, he made looser assumptions. In this, he assumed stricter assumptions.
I like the idea of two perfect logicians sitting down in front of a piece of paper and two pens, looking at each other and saying "aha, well played sir, a respectable draw" , getting up and leaving
It doesn't _always_ end in a tie, there is a win condition that's possible to achieve, in fact, only about 18% of all possible move sequences result in a tie. It only "always" ends in a tie _IF_ both players are 1. trying to win, and 2. playing optimally toward that goal.
Tic-tac-toe is a zero-sum territory control game about the futility of competition. In the movie 'War Games', it was used as an object lesson about mutually assured destruction for a machine-learning AI.
That's an interesting way to look at it
What a reference. Yes the calculation in the end stated the only way to win is not to play
I'm so watching this movie in future thank you for the ChatGPT version in 1983
czcams.com/video/1vmnp7ghGPk/video.html
I absolutly love the little sounds the tic tac games do when they are moving. Makes them so lively
E
makes them creepy imo, with the music and the noise. Maybe because it makes me think of Petscope. And also maybe the fact im watching this at midnight
I wish there was just a video of all the permutations of the similar games in audio only.
It helps understanding how different 2 games are, without have to pause to analyze. Genius.
And then the weird and ominous background tone continues to play
Even the background music is tic-tac-toe. This man is INSANE when it comes to content that's multi skilled.
a very shrewd and nitwitted detail indeed, but it still falls into a music skill category i'm afraid
Great profile pic
@@v0id_d3m0n thank you. i will think about it and when i reach my conclusion i will contact you about the resolution of this situation.
@@v0id_d3m0n i did get a profile picture. do i deserve your respect and acceptance now? will i ever?
@@v0id_d3m0n wait, you wrote great? not get? oh well, i regret nothing.
Your kid is gonna find this in, like, a decade and have a huge revelation as to why he wasn't winning 😂
his dad was a certified tic tac toe researcher
E
Or why he was
In my memory, the classic way to win at tic-tac-toe is to start in the middle, and hope the opponent plays on an edge, not a corner. If you then respond with a corner on the opposite side, victory is assured. This strategy became too obvious however, which is why the meta shifted to the corner first play.
I use to think that was the best strategy but my usual tactic is to use the corner centre corner strategy as most people think the corner is op and so will fall for taking it on their turn then you just take the third corner and you have a guaranteed win
I think corner as the first move is objectively better than middle. When you play middle, the opponent has 4 positions they can respond where they don't lose: The four corners. Technically, all the corners are the same game, just rotated versions, but normal people don't think about it that way. However, if you play corner as the first move, the opponent has only 1 position they can respond: Middle. So corner is better
@@Linck192 Even if you take symmetry into account, corner is better: With middle, the opponent has only one losing move: edge. However with corner, the opponent has four losing moves: Adjacent edge, adjacent corner, far edge, opposite corner. With only one non-losing move in both cases, this means 80% losing moves in the corner case, versus 50% losing moves in the middle case.
@@__christopher__ you're absolutely right
@@Linck192 What is this, people on the Internet reaching an agreement? Preposterous, inane, UNACCEPTABLE, every interaction must devolve to something that resembles the intellectual quality of a tic-tac-toe championship!
(I just saw a typical Internet argument, or at least one comment out of it, in one of the other threads. The irony was palpable)
I am losing it at the squeaky sounds for each tic-tac-toe game, it's brilliant!
E
NGL, i was gonna close the vid, but stayed just for those sound effects. lol.
the sequel we didn't know we needed
Also, in history class, a friend of mine and I came across the corner middle opposite corner strategy and we were absolutely stumped to find out that we, in fact, didn't solve the game since there is really obvious counterplay to it
nice pfp :3
As a historian it makes me simultaneously pleased and baffled that kids these days are suddenly interested in the study of Charlemagne, but only one of his paladins and not the other eleven.
@@xyngedIt’s very funny, I wonder how he would react if he came back to life and discover that this is his most popular representation in media.
@@RosieDump :3
@@xyngedOh don’t worry, that same franchise puts a lot of focus on Roland, Bradamante, and even Charlie himself.
*Tic-Tac-Toe Poem*
I played a game of Tic-Tac-Toe
Against AI - a mighty foe
Every one of my attacks
Was undermined with minimax
Every game we played - a draw
Has this program not one flaw!?
Offended by its swift ascendance
I resolved to have my vengeance
"Grids of 3x3 are easy,
They're for babies, don't you know?"
I draw a board, 19x19
"Come computer, let's play Go"
ai generated?
I like this poem, especially the reference to alpha Go at the end. It's pretty interesting the stochastic optimal policy algorithms that get developed to solve systems where the action space is just too cumbersome to explicitly optimize over.
nice dude
This needs to be pinned.
The former world Go champion is gonna have a word with you
The XOX diagonal play is not the strategy that gives your opponent the most opportunity to make a mistake. But many people quickly learn the heuristic, "Middle > Corner > Edge" for cases where there's no obvious play (i.e. if you can't win or block a win). And the corner opening I think is the unique strategy that exploits this and wins, where otherwise that heuristic always achieves at least a draw -- this makes starting in the corner uniquely exploitative and gives it merit.
I've long known that if x starts in the corner and o plays anywhere but the center then x can force them to lose. That's what makes the corner the best place to start. The addition of the corner center corner is a potent weapon on Italian restaurant table cloths the cousins will not see coming....
If you ignore the possibility that the opponent will make a losing move with their first move (non-center in response to your corner opening or edge in response to your center opening), the opening that gives the opponent the most losing moves on their _second_ move is the OXX diagonal play, which gives the opponent a 4/6 chance of losing if they move randomly.
Mad respect for censoring your children’s face before putting it online, some people just do not respect their own children’s privacy and it’s crazy to me
9:13 I would argue that since the game never started to begin with and no move was made, the conclusion should be that there are 0 games of Tic-Tac-Toe.
"The only winning move is not to play"
He wouldn't be a true programmer if he didn't make the occasional off-by-one error.
I think it should be 1, for the same reason that, say, there is only one way of permutating 0 items. The game has length of 0 (it lasts 0 turns) but it is one game.
Sheesh, sorry, the send message button on mobile didn't work and when i spammed it it suddenly sent the message a ton of times
"The only way not to lose"
Can't wait for the times when there's only 1 game of chess.
There already is, we just haven't found out which one it is yet.
@@nixel1324 Imagine that we find out that the one true game of chess is not a draw, but a win for black or white. Thus making tic-tac-toe the more balanced game~
@@nixel1324 The existence of safe and aggressive openings in chess actually sheds light on that. Chess is a game that can be shaped in many different ways. Every chess master has a safe opening that he plays on the day which he doesn't want to take any risk it.
@@eclipserepeater2466 There are certain openings with forced paths which when both sides play the optimum moves the game always ends with a draw.
@@eclipserepeater2466 at least we know that if chess is sound, the one true game of chess should not be a win for black. Although we have enough computer power to solve chess itself right now, we may not have the will to devote the necessary computers to the solution. After all, we used humble desktop computers to solve English draughts between 1990 and 2007.
Next video: Tic-Tac-Toe don't exist
9:48 Another strategy is to always go center as first move. If 2nd player goes on an edge, first player can win the game 100% of the time. If 2nd player goes in the corner, 2nd player can cause a draw 100% of the time. BTW, I did not specify X or O because whenever I have played, either shape was allowed to go first.
I remember me and a fellow neurodivergent classmate spending the lunch on figuring out the optimal strategy of corner center opposite corner. We didn't do any particularly systematic symbolic maths, we just reduced the number of games by noticing the symmetries and testing every option and backtracking each time we had an obvious win or draw.
Neurodivergent 😭😭😭😭😭😭
@@cristianyahirmejiacruz5495 Is this a problem somehow?
@@cristianyahirmejiacruz5495 grow up
@@Red-yt2dk It's annoyingly euphemistic. It just means "crazy".
@@VestinVestin Rude.
You have got to be my favorite tic tac tuber on the entire platform right now
E
There are more than 1?
I came into this video knowing that the one true game was drawn at move 0. Ive played easily over a thousand tictactoe games with my friend, and we came to the conclusion that anything past move one leads to a draw so we started implementing more unique ways to play the game, i would love to see the same video but on 3d tic-tac-toe, a game that is for now not solved. At least in me and my friends' heads. Great video, I hope you can make it big.
Yeah 3d tic tac toe is the way to go once you get to the always draw place. Playing with three boards at once is alot of fun
I love playing Ultimate Tic Tac Toe, but rarely find someone to play it with. 😅
This video is actually exactly why I didn't watch the previous video you did. I saw the one about 14 games in my suggested videos, but I already knew Tic-Tac-Toe was solved and always ends in a draw for anyone that knows the game. This was a good correction to go back and make.
even if it is drawn, there are different ways to draw.
Yeah the original video, had the assumption that no player plays towards a draw. Glad the author looked at the math again.
we could actually use this to generate those mentioned strategies. Instead of always allowing "bad" moves, we allow one heuristic move and from then on play minimax. On the pruned tree, we can then see where you can set up a trap by splitting into a winning node and a draw node
My thoughts exactly. A position that allows for a trap is better than a position that is a guaranteed draw
This can be made objective to generate the perfect game by the following heuristic: Always play the non-losing move for which a greater proportion of the opponent's replies (accounting for symmetry, and assuming the opponent will always win or block an immediate win if they can) lose. If you can't, then play the non-losing move that minimizes the opponent's ability to do that.
That will certainly result in the corner-center-corner strategy. For the first move, there are two replies to center (1/2 draws), five to corner (1/5 draws) and five to edge (3/5 draw). So edge is optimal. Then center is the only non-losing reply. Now the first player has four moves. Two of these force a single non-losing reply. Let's look at the other two, opposite edge and opposite corner. For opposite edge, there are 6 replies (4/6 draws). For opposite corner, there are only two replies (1/2 draws). So again it is the best move. Now assuming that the non-losing move (any edge) is played, all moves are thereby forced - due to the need to block immediate wins - until the game is drawn.
Thanks for including the corner way. I used to play with 2 of my friends in 8th grade often and after a ton of games we'd settled on the corner move, but after we figured out how to block the corner move we stopped playing, because noone could win.
Playing O edge then center consecutively or vice versa after the 2 corner X's (whether horizontally or diagonally) would always end in a draw
if O ever plays edge on their first move then they lose regardless of what X's first move was, assuming X knows what they're doing. because no matter what X's first move was, if O plays an edge then X can control O's second play, while also setting themselves up for a fork on their 3rd play.
center is mathematically the best first play period. because the center affects half of the possible wins.
edit: slight correction. if X's first move is an edge, and O's first move is specifically the opposite edge, then its a draw with perfect play
I LOVE videos that go into the details of a game as simple as Tic-Tac-Toe, solved games and subjects adjacent to it are just so interesting to hear about that I could watch another hour of this.
This is a wonderful follow up. It feels like you read my comment personally and addressed everything in it and more. I am glad you are making videos. (And again, I recommend Connect Four 😊)
there is truly only a single game of tic tac toe, where a player wins, and simultaneously a player loses.
E
@@EEEEEEEE i really disagree with your opinion. how can you be such a shameless creature.
dude the little tic-tac-toe sounds gave my brain so much happy chemicals omg, they just sound so silly 🥺
Even though I was a fan of the corner corner opening in my youth, I believed your previous video and didn't notice you'd omitted it. I like your statement that the game occupies a sweet spot in complexity, which is probably why nearly everybody learns it, even though it's so famously easy to master.
In response to 9:53 I traditionally start with the corner because if they don’t respond with the center there is a guaranteed way to trap them and even if they do there is still one more possible trap they can fall into. The only other starting move I use sometimes is the center because if they choose an edge you can guarantee a trap win, and if they choose a corner, you can choose the opposite corner which sets up a possible trap if they happen to choose an edge. (For example using the grid at 0:23 the game 51947 uses this trap)
I would recommend a healthy rotation of openings to keep you on your toes, every tic tac toe master can win with the X's when it counts. It's holding the draws with the O's where the real players cut their teeth. I find building up your opponents courage to be very important to a slip up later in the match.
I think you meant 51947 with a 3/8 fork? 51943 is a win for "O" at 7
@@gacrux-ni7hwyou are totally right. That was my intention but it appears I envisioned the board wrong and wrote the wrong numbers. Thank you.
Seems to me that in checkers it's also always a draw, if no one ever makes mistakes.
I prefer calling it something like _"perfect plays"_ rather than _"perfect players"_ (or _"zero mistake plays")._ Because a player's skills are never perfect, but an imperfect player can still possibly make no mistakes, and thus have a "perfect play".
That is true only in games of merit, where merit is the decisive factor for winning. As opposed to games of luck, where luck is the decisive factor for winning (like minesweeper or poker).
In a game of merit, the player that wins is always the one that made the least mistakes (or the least severe mistakes). But it's always about mistakes.
Yes, checkers was announced solved by a paper published in September 2007.
I wouldn't say minesweeper is mostly a game of luck, although a bad opening or seed might force you into clicking a random square (a play of pure luck), once you become aware that there is a method to the madness, it becomes 99.9999% skill
@@tiagobelo4965 While no guessing minesweeper is cool, many purely random games of minesweeper end up with a 50/50 guess at the end and aren't that difficult in other places.
@@tiagobelo4965 No. That distinction isn't based on how most of the game is played, but on which factor is decisive to whether you get to win or loose. Your very first move in Minesweeper is 100% down to luck. And you'll be in that situation two or three times per game, depending on board size.
In other words, it doesn't matter how good you are at it, you only ever get to beat minesweeper when you are lucky those two or three times. That's luck being the decisive factor.
That is unlike Monopoly or D&D, where luck isn't the decisive factor. Each dice roll has no effect on the overall outcome of the game, it's how you decide to play with them that does.
I really like this update and particularly the pruned tree at 8:34. I think what you've done is defined the "plausible tic-tac-toe mistakes", and that's a really cool thing to see. If you spent some time trying to make the gametree graph as planar as possible (minimizing crossing edges) I think it'd make for a really beautiful poster.
Thanks! I'm considering doing this 🙂
Yeah I love the implication at 8:34 that if x moves the same move means y wins
I'm also trying to figure out what that Circe Winning game at 3rd move is, I suppose it's a "Corner->Center->Side adjacent to Corner" game
@@kookaburrakai8026 I don't think it can be corner center side, because 8:52 we get that "move 1 corner" is the topmost node, not the middle node. Looking at it, I think it's likely to be (labeling the squares 1-9 in reading order): X4, O2, X6. O5 is forced, X8 is forced, O plays any corner and has a fork, winning. I'm gonna try some ascii art:
__| O |__
X |__| X
. | |
Here's an interesting variation of Tic-Tac-Toe with some fun dynamics:
Play is on a 4x4 board. 4 in a row, column or diagonal win. A square of four connecteds also wins. There is one particular opening position (first player plays on a center square, second player plays on the diagonally opposite center square, first player plays on an edge square orthogonally adjacent to their first move) where the second player has a ton of natural looking possibilities but only one of them is good enough for a draw. I find it pretty fun, though once you get the hang of it it's a draw.
The only game simple enough for me to play as a kid now has the most intricate/complicated lore of anything I've ever seen.
I maintain two things:
1) My favorite opening is corner-center-opposite edge. It maintains a 2/6 possibility (with a random opponent) of setting up a fork and is lesser-known than corner-center-corner.
2) This is the best opener. Let us assume that our opponent plays random moves, but blocks every two-in-a-row when possible. Let us also assume we play the best moves (i.e. fork when possible, block opposing threats). Let us also treat, as you do, symmetrical moves (with rotated and reflected boards) as identical. If we calculate the probability of our opponent making a mistake at some point in the game, the corner is better.
This is because the corner is "trickier". The opponent, on the first move, has 5 possible plays: opposite corner, adjacent corner, adjacent edge, opposite edge, and center. Only the center survives. And on the second move, after I go on the opposite edge, they still have two losing moves. However, if I go in the middle, the opponent has only two possible plays: corner and edge.
If I remember correctly from being bored in AP World History, with the random parameters I set up, the corner->center->opposite edge comes out to 1/96 superior to the second best move (corner -> center -> opposite corner) and vastly superior to the first-move-middle play.
im glad the last vid got picked up by the algorithm, this was a great sequel and im looking forward to whatever you make next!
this is the worst video to listen to in the background while doing homework, it's so engaging and the sounds the board makes just tickle my brain
this is a compliment btw
I love that the perfect player ties you showed, all end in a disappointed sounding progression. I love the way you represented the game sounds!
All other games at least have 1 “blunder”
Edit:the blunder is playing a move
Edit:the blunder is playing a move
Edit:the blunder is playing a move
Edit:the blunder is playing a move
Edit:the blunder is playing a move
i love the songification of the tic-tac-toe games so much its so cute, curious if you would want to make an analysis like this in the future with variations of tic-tac-toe which are a bit less unfair, like having Only x's or having 3 separate boards or 3 in a row actually making you lose or all 3 of those combined (3 boards X's only Misere variation)
also how good is your kid in playing the game
It's not clickbait, watch the whole video - loved it, well done.
1. Play X in the center. If he plays O in the edge you win if you play X in the opposite corner.
2. If he plays in a corner, you play in the opposite corner. His only move is to play O in one of the other 2 corners.
Thats the strategy I use if corner doesn't work. A good second strategy.
9:40 I think the best alternative to corner centre corner is center edge corner. As X can then set up a fork, either along the diagonal or the edge of the board, by placing a corner.
Center edge corner isn't an "opening". It's just O making a blunder with their first move.
I adore the sonifications. Since music is very primary to me I've actually afford something similar to help me learn chess openings and board visualization. I'd love to see the code you use to synthesize these quirky sounds
Ok, but the music/sound in the background of this video is fantastic. Most of my CZcams follows are for mathematics content, and few math creators have this good of sound!! I honestly am just realizing this for the first time.
My fav oppening:
X- Centre
O- Corner (Non corner is losing)
X- Opposite corner (Gives O one last time to make a mistake)
O- One of the 2 corners (Non corner is once again losing)
And from this point agree to draw, since every next move will be 3-in-a-row threat by X and block by O
We are so back
Ive played a decent amount of tic tac toe and there are a few good moves Ive found
First obviously the corner middle corner
The second however is if you do corner and they pic anything OTHER THAN MIDDLE then you can pic any corner that isnt the opposite corner and win (unless they block/took it then take the other corner)
Lastly there is one where you take middle and some other stuff but its been so long Ive forgotten it! but it also leads to a fork
The 7 possible corner games are as follows, and only one of them leads to a draw, six lead to a win for X.
Corner
Opposite corner
Adjacent corner
Edge to block 3 in a row
Remaining corner - creates a fork
Corner
Adjacent corner
Opposite corner
Centre to block 3 in a row
Remaining corner - creates a fork
Corner
Adjacent corner
Remaining adjacent corner
Edge to block
Remaining corner creates a fork
Corner
Adjacent edge
The other adjacent corner
Edge to block
Opposite corner creates a fork
Corner
Opposite edge
Adjacent corner
Blocking edge
Adjacent corner crates a fork
Corner
Centre
Opposite corner
If O takes corner, the blocking move creates a fork
If O takes edge, the blocking move leads to a draw
Finally, the vid we’ve been waiting for
I love this video because it really quantifys my skill as a tic-tac-toe player, when the part about imperfect players came up I got up and said "EXACTLY!".
Now when i play a game of tic-tac-toe vs someone, I usually will want to 3 games with X(the ones I play with O are draws), one game for each starting X move, I do this because I have tricks that work on imperfect players with each starting position. Now I would like to explain a few tricks that can trip up some people, note that since I can't give visuals that it may be a bit messy.
I would like to build on the trick that was said in the video, X goes corner, but instead of middle O goes opposite corner, the trick comes after X goes middle. This creates a similar trick to the one explained in the video, but if O goes on one of the sides he loses instead of the corner because X would go in the corner and fork O. This is actually the same trick I use as when X starts middle, as because O cant go side(forced loss) he has to go corner creating the same situation.
Now the trick for X starting side is the most interesting imo(also the weakest), X starts middle left for visualization sake, O has 5 responses, in 2 of them its a forced win for X, but in the other 3 I would go Top right or bottom right(doesnt matter because both of these moves would always be available because if O went in one it would result in a forced loss in a different series of unrelated moves to this trick), going in one of these positions forces O to make a correct move or else he gets forked, albiet if you're bad its easy to accidentally avoid, going on the side is funnily enough better at tripping up good players then bad players, as they underestimate me resulting in them not thinking and ending up being forked.
Those are the only tricks I know of, maybe there are more but I have yet to find them and I doubt they exist. If you read this far into the comment then give me a like :)
I remember solving this game when I was like, 15. That was fun. Any bored teen with a slightly mathematical mind can do it, as soon as you start eliminating boards by symmetry, and stop playing out decided games.
Corner start is best move IMO, because you force your opponents move into the middle (or you have a guaranteed win), and even if they do that, there's the corner trap for them.
Starting in the center has the edge trap, but most people rightly don't play edges anyway, because they're just not as good.
even if they play in a corner you can preserve the edge trap by playing the opposite corner from them. corner first has no real mathematical advantage over center first. Its strength lies in the relative obscurity of corner first play.
Mathematically any first move you make leads to a draw. The only way to win is to trick your opponent so he does a mistake. Argunmenting mathematically is bogus in this case.
@@sillyking1991 The mathematical advantage of corner first lies in its ability to defeat players who haven't yet figured out that the center is good.
that isn't a mathematical advantage...its a strategic one. that doesn't make it less significant, just making sure we're using the terms correctly@@Tzizenorec
@@sillyking1991 There is no correct use of the term. "Mathematical advantage" is not precisely correct for any part of this topic. But... I can say that the corner first play has a 11/12 chance of beating a clueless player, while the center first play has a 5/6 chance of beating a clueless player. The first number is bigger, so there is a "mathematical advantage" here... arguably.
What a sequel!
Using the chart you have shown at 8:58 I did some calculations and found that on even before any move is done, X has a higher possibility on winning. If we were to give +1 at x winning, 0 at draw, and -1 at o winning, the empty state of the board yield a +0,1515 possibility at the end. I have calculated a nodes point by summing up all the nodes exiting from it and then dividing the summation to the number of exiting nodes to get an average. The best opening move would be the corner move. X will either win or fall to draw in the corner move and never lose. The best move for X in the 3 move which increases the possibility of win for X to +0.5 is the XOX corner to corner state.
On the other hand, the worst opener for X is the center move. The node for the center move gets a point of +0,075 which is the lowest possiblity out of the three. The side move is a better move compared to the center and gets a point of +0,1676. The thing is, the side move loses quite a lot of points because it allows the O to win in a bunch of conditions.
This is an incredible video! Can you do something on chess? Not necessarily solving it, but maybe talking a little bit about how many legal board positions there are? It is a very interesting and similar topic!
en.wikipedia.org/wiki/Shannon_number
I don’t think it’s similar dude after 2 chess moves there’s already 400 potential moves and distinct positions
After 6 moves there’s over 9 million potential positions for the board to be in
I don’t think it’s similar dude after 2 chess moves there’s already 400 potential moves and distinct positions
After 6 moves there’s over 9 million potential positions for the board to be in
I don’t think it’s similar dude after 2 chess moves there’s already 400 potential moves and distinct positions
After 6 moves there’s over 9 million potential positions for the board to be in
Oh interesting! From my experience, Tic-Tac-Toe is only losable by making a mistake, which corresponds with your data.
Play EDGE first move!
Most Tic-Tac-Toe players understand the "corner-start" fork trap.
They'll think you're a fool for starting on the EDGE and will underestimate you!
X: LEFT-EDGE, O: MIDDLE
X: TOP-RIGHT, and if O chooses the sensible-looking option of BOTTOM-RIGHT to set up a win,
X: TOP-LEFT wins by fork!
(The other option for O was BOTTOM-EDGE, which ends in a draw.)
I like playing blind tic tac toe where we both play in our heads, and for that the corner start is great. The reason it wins so often is that the second player is screwed if they play _anything_ except the center, but it's not so obvious this early on that their _first_ move is a forced move. So they'll often make a mistake. Even if they play their only safe move, the center, they'll often mess up later like you said.
Other openings don't have this effect. Center opening is always a draw, and for side opening I can't set up a fork, because their blocks give them 2 in a row forcing me to respond. So corner start wins most often.
So what is the win percentage of X and O in game states that reach the point of inevitability? Is the game more balanced than you thought or less?
Also have you considered making a game that uses these models in it's decision making?
Now do one of these, but with Ultimate Tic Tac Toe!
I really enjoy your videos. The rules in Tic Tac Toe are fixed. What would happen if the rules weren’t fixed? What if two squares in a row was a win? What if instead of your placement being the only factor for winning the game considered sequence as well for determining the winner? What would happen if the players didn’t know the rules? How many games would it take for them to figure out what the rules are? The ultimate challenge would be what would happen if the rules changed randomly each game. What would the winning strategy be then?
I love the sound effects their goofy
Brilliant vid when you reach clarity after spending my full day moving lol
wurp wurp wur barp bwurp bop bwooooow
werb wurp bwomp bwerp werp bur wuaoow
What you could look at to find the most optimal play is to have the player get score after every turn based on how many potential plays lead to wins if the opponent makes a bad move, deriving the best moves chancing a mistake from your opponent.
The strategy I always play is center, if your opponent plays edge, you win. If your opponent plays corner, you play the opposite corner (so you don't threaten a 3 in a row) and the edges are still free for them to play in and lose.
Rock Paper Scissors > Tic-Tac-Toe
There is only 1 game of rock paper scissors, there is the highest chance someone plays scissors. Do just play rock. Works 1/3 of the time
Connect Four > Rock Paper Scissors
Tic-Tac-Toe > Connect Four
Honestly, Tic-Tac-Toe is also very useful as a game, because is not too difficult to analyse, so it allows videos like this to exist.
You Couldn't do this kind of analysis with chess, for example, because there's just too many possibilities.
Absolutely. (I mention this at the end of the video)
I wonder what the smallest solvable subset of chess is
@@U20E0 , they usually call this "mate in X", AIs who are incredibly good at chess usually end up in a draw with optimal play iirc because knowing so far ahead they usually opt to draw by repetition in a position that can't advance to a win but can't be forced out of repetition without a sack that also can't advance to win. If the board is in a state where a win is inevitable it's called "mate in X" and i think there are some states where the board was determined to be "mate in 26" or something crazy
@@RoundShades I am talking about a subset as in a subset of the board, what's the biggest solvable board size
@@RoundShadesFor heaven’s sake don’t start a “sack” eggcorn. Lol.
There are some openings that use the same idea as the corner - center -opposing corner strategy.
One that I like to play is this one:
(for the sake of clarity, I numbered the grids row wise but it shouldn't matter).
x- center (5)
0 - corner (e.g. 3)
x - opposing corner (7)
then from there, the only move that stops x from a fork is the remaining corner (1 or 9), but I often see players just picking one of the side (2 or 6) because that looks like as if they are the one forcing me into a defending.
If we're considering suboptimal play, we might be able to tiebreak between two winning moves by choosing the move that has the least amount of drawing responses. If both moves have the same amount of drawing responses, then you can look one layer deeper and see which of those drawing responses has the least amount of drawing continuations.
I'd be curious what would happen if you had a perfect player going first who knows they're playing a heuristic player (who randomly chooses one of the heuristic moves). What would be the moves that create the highest probability of winning? This would be what I consider to be the optimal moves.
well, if x is a perfect player and 0 is choosing moves randomly, then right off the bat we can eliminate nearly half of possible games. since if O plays an edge on their first move its a guaranteed win for X. its nearly half rather than exactly half because this includes if X's first move is an edge, but in that scenario O only has a 3/8 chance of playing an edge instead of 4/8.
Since the list of heuristics includes "start with center", the perfect player should take the center first to rule out that heuristic. Then, the heuristic player will either play an edge (instant loss) or a corner (perfect player replies with the opposite corner for a 50% chance of winning).
So that's a 3/4 chance of winning for a perfect player who _knows_ they're up against a heuristic player who prefers the center but doesn't prefer the corners.
But that's a quirk of the heuristic. Most humans who haven't solved the game are running a Center>Corner>Edge heuristic, which reliably draws against the center opening but always loses to the XOX diagonal opening. Or you could take away the center preference heuristic entirely, in which case X starting in the corner gives O a 7/8 chance of making a losing first move.
My understanding that you should always take the middle first. Since it splits the game into 50/50 and restricts the available moves of your opponent. Whatever move next, you can either force a win or a draw easily. If they pick a corner, you just pick the opposite corner. If they pick the other option, it's basically a forced draw as long as you surround the enemy options. The other options of starting points require way more effort and investment of looking through the different variations.@@Tzizenorec
@@MultiMVirus Then you're probably one of the people that my corner opening is designed to trick. You're _not_ going to lose to someone who plays the same way you do, but if you play against someone who uses the corner opening and actually knows the variations? You just might.
It would be cool if you did the same analysis of either 4x4 tic-tac-toe or 3D 3x3x3 tic-tac-toe and compared the complexity.
3d tictactoe is a win for the first player after they play in the center
I was in high school or maybe a college freshman when I discovered that center-corner-opposite corner was a pretty good trap.
In order to prevent a loss, O has to make the super-counter-intuitive move of playing on one of the remaining corners. 4 of 6 squares are losing for O, compared to 2 of 6 for corner-center-opposite corner.
You know the added backstory of a Dad teching his son the game oonly to go on and make this analysis makes this saga so much better.
Ur next video is gonna be: theres only 1 game of chess
People are confusing “games” with “outcomes” and “final positions”. These are distinct things. To say the games are the same as the outcomes is to say the journey is the destination. We all arrived at Times Square, therefore there is only one route to Times Square. Outcomes are win, lose, and draw. There are 3 possible outcomes. Final positions are the final diagram or locations of the pieces. The various paths or ways you can arrive at the final positions and outcomes are the possible games. Having one or three outcomes does not mean there are that many games. I’m speaking about both chess and TTT. Each game has exactly one outcome and one final position. But each final position has one outcome and multiple games. Each outcome has multiple final positions and many games.
I never even saw your first video but got recommended this one. I like it a lot 😊
A strange game.
The only winning move is not to play.
How about global thermonuclear war?
There is exactly one game of tic tac toe. It's called tic tac toe. You learn it in like 2nd grade. There is no one on Earth that plays it differently. There is a single game of tic tac toe in existance.
That divided by 8 code is truly well written
2:33 THAT'S my strategy, that's how I play. I saw your video and commented this I think, don't know if you read it but I'm glad it's being pointed out!
I love the sounds in this video they make me rlly happy!! ur rlly talented have a great day
Hi Marc, a few more notes on tic-tac-toe. Although many commenters have mentioned the corner-center-opposite corner as the optimal play pattern for X, if we consider players of different skill levels, it might actually *not* be the best strategy for a skilled X player facing off against an unskilled O player. Let me explain. I refer to the numbering of the tiles at 0:23
I'm going to assume the X player starts, and always plays optimally. However, the O player is a novice. They will always move to block an immediate three Xs in a row, but will not necessarily block an opportunity for X to make a fork, which would guarantee X the win on a subsequent move.
With these assumptions, with the sequence (X1)-(O5)-(X9), then O has six possible squares for their second move. If O plays in 3 or 7, then X is guaranteed a win with perfect play. If O plays in 2,4,6, or 8, then the game is guaranteed to end in a draw. At each point, X will move to block, and O will be presented with a two-in-a-row from X that they must block. Even a novice O player will get to a draw every time. Assuming O's second move is completely random, X will win about 1/3 of the time.
Consider instead the sequence (X1)-(O5)-(X8). Now the board isn't symmetric, and O has some more complicated choices. If they play in 2 or 3, then X is guaranteed a win with perfect play. If O plays in 6, 7, or 9, then they are guaranteed to achieve a draw with their skill level. However, if O plays in 4, then X responds with 6, then O is once again faced with a situation that they can allow X to create a fork if they haphazardly play in 2. As a result, X will win slightly more than 1/3 of the time assuming O's second move is completely random.
In summary: X's optimal first move is corner. O must respond with middle or they lose. X's optimal second move is actually not opposite corner, but rather opposite side. No matter O's next move, X can always get to a draw. However, this play pattern maximizes the chance for a novice opponent to make a mistake.
Yeah, this is the only strategy I ever saw someone older than 7 or so lose to. I beat a very smart friend with it in high school once.
I remember some kid ages ago figured it out and made the game out of tinkertoys.
As you selected a tile as X, it would select O in a manner where either O wins or draws.
I remember seeing it as a kid at the Boston Computer Museum back in the '70s
There are actually 8 unique games of tic tac toe. I figured that out a long time ago in middle school because winning at tic tac toe was more fun than history class lol.
1. Is a tie which as stated with 2 perfect players will always happen. What I figured out was every mistake that o can make and guarantee x a win. I count this as 1 and don't consider all the unique ways to tie.
2. When x goes center and o fails to take a corner there is 1 way to win. next x forces o's next move by o's fist move. X goes to block and creates a double win. This also only creates 1 unique board as it will rotate to look the same.
3. X fist move is on the side and o does not make a move that fall in line with x's first move. This leaves 4 open spots that guarantee's an x win by forcing o's next move and creates 2 unique boards.
4. Finally when x's first move is corner and o fails to go either middle or opposing corner creates 6 ways to win and 5 unique boards. I am not going to list all the plays but I will say like all of the previous games I listed X's next move forces O to block and guarantee's a win. I will also say it is impossible for O to win without several mistakes from X, what I did was figure out all the guaranteed ways to win as X by the placement of the fist 2 moves anything other than scenario 2, 3, or 4 by players that know how to win will always be a tie.
After watching both videos, I want to see the board state diagrams for the stage of the triangle after pruning symmetries, take winning moves, and block winning moves (2936 games), both pruned and unpruned. Since we've only looked at two strategies so far (your strategy and absolutely optimal play), I think it might uncover some funky strategies that people don't usually think of. Something like AlphaGo figuring out some ideas that professional Go players hadn't seen before, but considerably more bruteforce 😁Great videos! Looking forward to watching the others shortly
The thing I like about corner centre corner is that it is actually the second trap. If the second player plays anywhere other than the centre, you can set up a fork over the next two turns.
Those Tic-Tac-Toe sound effects you use hit my brain the same way a hit of gigantic cabbage spliff might. Well done on picking that out! Also nice game analysis btw
As a cs major music minor I am so glad to have found your channel
Starting in the center is just as good as starting in the corner,
Since you can use the center to force opponents' moves.
Also if they don't respond with a corner when you open center you can just play any corner to guarantee a win.
The optimal strategy is to let the opponent go first,
Force a draw if they open with center or corner
And then use the opener they didn't use.
the reason the corner is considered the optimal move, is because there is only one answer to it, because of symmetry you win in all posible situations EXCEPT if they play in the middle, and even if they play the only possible answer to your starting move, then you can use the corner trick so there is still a possibility of you winning
corner start pretty much has only 3 possible ways it can go:
you win turn 1 (opponent doesn't play center)
you win turn 2 (opponent plays corner after center)
or you tie (opponent doesn't play corner)
as you said, a perfect player vs a perfect player will always tie, but a perfect player vs an unperfect player, the optimal route is the one that has you winning in every combination but 1
center creates 2 possible moves to your opponent because of symetry, and one of them is a insta win, but corner creates 5 possible answers and 4 of them are insta win
you give your opponent more options, but don't increase their chances of winning, so instead you increase their chances of making an error, and at the end of the day that is the only way to win in tic tac toe, for your opponent to make an error
so thats why is the better move, more possibilities for your opponent to make an error, thank you for comming to my ted talk
The title of that XKCD comic, XKCD #832, is actually "The only winning move is to play, perfectly, waiting for your opponent to make a mistake." So I'd bet they hold a pretty similar opinion of how people go about playing tic-tac-toe to you, even if their chart is pretty standard.
In a tie game, the player that has center square has made the shape of a Y: by either 2 adjacent corners and the opposite side, or 2 adjacent sides and the opposite corner. If the player with the center was X, then there is an additional square adjacent to the Y prong that is taken.
The largest solved game so far is Pokémon. Someone has mapped out the exact combination of button presses you need to win, regardless of the RNG.
corner center far edge also has a 2/6 chance to win, i use that as well once they figure out to play an edge in response to corner center far corner.
and yes corner is the best opening, if u play anything but the center in response you lose. and even then u still have a 2/6 chance to lose when x plays far corner or far edge. if ur against someone who knows what theyre doing its a draw anyway, and u can assume u know what ur doing, so from that perspective its the best opening.
I would like to point out that picking the corner as the first move wins you the game unless the opponents first move is in the centre. For example if the first move is the top left corner and if the opponent picks any of the sides the optimal move is alway to pick the adjacent corner to your first move without an 0 in the middle of them, this forces the opponent to place an 0 between your 2 Xs and for your move you put an X in the centre creating a fork and winning the game. If the opponent picks any of the 2 adjacent corners the optimal move is to place your X on the side that is next to your first X but on the opposite side to that of the 0, this forces the opponent to place an 0 in the other adjacent corner, which in turn forces you to place a X in the centre which coincidentally causes a fork and wins the game. If the opponent puts the 0 in the opposite corner, the optimal is to place your X in an adjacent corner to your first X, forcing the opponent to block on on a side, the next move is to place an X in the last remaining corner creating a fork and winning the game.
I feel like this video is overrated. There is really one optimum move both player can play, first player corner, second player play center and so on to the draw. That's it. Python code is unnecessary. Because most optimum move 1st player can play is the corner and 2nd player goes center and the game is basically done.
In my youth we used to play "tic-tac-toe extended"
The rules were - unlimited board, first to reach 5 in a row wins.
We spent a lot of time playing during the lectures in the university but eventually...
The game kind of died for us. It was too difficult to actually win the game, however the "X" player got all the rare opportunities to play for the win.
We got bored and dropped it.
However I still remember the game as a big part of my youth.
The amount of effort put into those videos only for The Algorithm to say "nah bro, I'm good", vs. just putting your best foot forward and getting enough attention that someone else helpfully points out your "mistakes" for you.
This has some surprising applications to the perfectionism I've been struggling with lately. Didn't expect that from the follow-up video to something I just clicked on randomly earlier this month... Thanks for this rather serendipitous bit of insight!
Yeah, it's funny with CZcams in particular, because it seems like making mistakes actually causes engagement. So like, it might even be a good plan to have mistakes on purpose. I'm not going to do that, but I definitely think that there are times that I can allow things not to be perfect
I don't know if you saw my comment on the last video, but I thought the same thing with the number of games being the total number of games where each side plays perfectly. I simulated it as well and got 336 games.
Also, sometimes I like going on the edge first as it can throw the other person for a loop as almost no one does it. Then if they go in the center I go on an opposite edge and possibly setup a fork.
that was really 2 cool videos about tic tac toe! Thank you for it!
I remember playing Tic-Tac-Toe in school and we were evolving the rules, until we have played on a full A5 5mm grid page where the goal was to connect at least five in a row, to score a point, and extra move. with potential to connect up to 9 in one move, where each additional symbol in a row would be worth extra point (point only).
Once you scored a point on any symbol, you could not score another point using the same symbol in the same direction.
If you managed to fill 2 five in a row with one symbol at once (one horizontally, and the other diagonally/vertically), or any variation on it, it would count according to previous rules for each row completed (so 2 points, and 2 extra moves in this case)
Generally the game played with altering short bursts of power over the other player scoring 3-5 points in a short span of time, with highly defensive play to not allow runaway effect for the winning player, the game would end either if loosing player concedes, or we run out of space.
We also tried this rule set with more players, where at 3 players the game was less defensive, and it was hard to get more than 1 point at a time. 4 players were too many to score any points.
Starting with center is interesting because it's 100% win or draw, no lose conditions. If they respond with an edge position, you can force a block by choosing an adjacent edge, then fork using those last two moves to set up either an edge win or diagonal win for mate in three. If they respond corner, you simply close one of their lines of play with an adjacent corner, forcing them to block the diagonal. Then you block the edge win they set up, which forces them to block your line through the center. This leaves only the orthogonal center line open as a win condition, but with only three spaces left, this is also obvious, which means it will invariably be a draw. But the center move, if played correctly, cannot lose.
When I was in high school, I spent way too much time analyzing tic-tac-toe and learned that if you go first and play in the corner as long as your opponent doesn't go in the center you can always force a win. If they go in the center then it becomes the corner-center-corner setup described and you can only open that they go in the corner on their next move. So for the majority of games where you go first, you can know the outcome after your opponent's very first move.
If you go second, you can always force a draw, and can only get a win if your opponent makes some pretty glaring mistakes.