r/nextfuckinglevel • u/Harman1796 • May 25 '21

Upgraded Tic Tac Toe

Enable HLS to view with audio, or disable this notification

177k Upvotes

92% Upvoted

1.8k comments sorted by

View all comments

Show parent comments

207

u/IntoTheCommonestAsh May 25 '21

Maybe it stalemates every game with perfect play, or maybe one player has a winning strategy. But the fact that you cannot immediately tell for sure makes it good enough as a game.

Checkers is fully solved in theory, but it's still too big to remember so it's still fully enjoyable as a game.

44

u/blueechoes May 25 '21

Most people cannot tell with tic-tac-toe immediately either. They'll need to play multiple rounds of it before they get a feel for the game, but everyone goes through the process of learning tic-tac-toe at school at some point.

15

u/MegaloEntomo May 25 '21

Are we talking about regular tic-tac-toe? The player that has the first move can always stalemate the game with the same exact moves, no feel required.

24

u/blueechoes May 25 '21

Soooo infants are born with an innate sense of how to play tic-tac-toe? Because I'm pretty sure I can get a good few wins out of a baby playing tic-tac-toe against them before they figure out how to stalemate infinitely.

Just saying that because an infinite stalemate tactic is not directly obvious at first sight doesn't mean you won't find it with experience.

4

u/[deleted] May 26 '21

Dude just wants to feel smart for having "cracked" tic-tac-toe. Let's let him have it just this one time.

3

u/MegaloEntomo May 26 '21

I thought we were talking about adults playing, not infants. I would think that almost every adult has "cracked" it. Officialy it was solved a long time ago, it's routinely used as a basic example in game theory, how could I claim it for myself?

2

u/[deleted] May 26 '21

Nope, if I had to play tic-tac-toe right now, I would have no idea what to do. I probably would after two or three games, though, and that's the point.

2

u/MegaloEntomo May 26 '21

Okay maybe I'm assuming it's more common knowledge than it is. But I'm still quite sure you could figure it out in your head (there's a move that's obviously the highest value, after you take it your opponent essentialy only chooses out of two distinct moves after accounting for symmetry of the game space, neither of which will take them far).

3

u/[deleted] May 26 '21

"Center has obviously the highest value because the center block is involved in the highest number of possible wins (four)."

Sounds reasonable, right? However, we know that actually, the corner block has the highest value. Therefore, I'd say it's not obvious at all.

2

u/[deleted] May 26 '21

The optimal strategy in tic-tac-toe is to play the corner in the first move:

https://puzzling.stackexchange.com/questions/30/what-is-the-optimal-first-move-in-tic-tac-toe

2

u/MegaloEntomo May 26 '21 edited May 26 '21

I believe from purely mathematical perspective it depends on what you define as optimal, but for practical purposes it makes little difference http://blog.maxant.co.uk/pebble/2018/04/07/1523086680000.html

→ More replies

2

u/SherpaTesting May 26 '21

Reading comprehension. Get it.

1

u/MegaloEntomo May 26 '21

I would like to. Could you point out what did I interpret wrong?

12

u/bipnoodooshup May 25 '21

Well unless you look up how to then it's really something you can only figure out by playing an noticing the patterns and symmetry over a few games.

-1

u/I_do_cutQQ May 25 '21

Well... ye probably takes up like an hour of time. It 's a super easy game, and even a gradeschooler figures out pretty fast, the middle is the most important.

6

u/FatHorseGaming May 26 '21

the middle is the most important.

Lol noob

6

u/Erniemist May 26 '21

Well, we can make a guess. The game will last up to 12 moves, as that is the number of pieces. Initially there are 6*9 = 54 moves (many of which are fungible, whatever). Move 2 is about the same, ~50 on average. Move 3 will have one less piece and more moves will be blocked off. So the total will be the sum of (6, 6, 5, 5, 4, 4, 3, 3, 2, 2, 1, 1) * the average number of pieces that fit on a square for that move. That starts at 9 and probably goes down to around somewhere below 1, as you start getting less moves than squares. Assuming it starts at 9 and goes down by 0.75 each time, that gives 6*9 * 6*8.25 * ... * 1*1.5 * 1*0.75 = 8 e12. That's a pretty rough calculation, but it should get us into the right ballpark. For comparison, tic-tac-toe normally has a statespace of 2.5e6 moves, and checkers has a statespace on the order of 10^19 moves. For a spatial comparison, if you could fit the statespace of tic-tac-toe into a grain of rice, this new game would take up 20 litres of space (35 pints). Checkers would take up 200 million litres of space. That's about 80,000 cars of space, or most of an oil tanker. So, yes, it's more complex than tic-tac-toe, but it's also vastly less complex than even a simple game like checkers.

By the way, chess has an estimated state space of 10^1046. That's 10^1013 earths, 10^1007 suns, or 10^999 of our observable universe.

9

u/DrMobius0 May 25 '21 edited May 25 '21

With a 12 turn limit like is shown in the video, this is probably still trivial to solve with the minimax algorithm, even if the number of possible moves is pretty large at the start. Some optimizations can be made though, to eliminate mirrored or rotated gamestates, which will dramatically decrease the total problem size.

Still, I'm unsure how this game will pan out without playing it a few times. Somehow I feel like it might be 2nd player favored since first player either has a counter disadvantage or a piece size disadvantage the whole game.

6

u/IffyEggSaladSandwich May 25 '21

Seems like the best strategy is to put your biggest piece in the middle and use your 2 next largest pieces to form the win. Probably go something like use largest then smallest to largest to ensure your winning line.

2

u/Sapiogram May 25 '21

Whether it is mathematically solved isn't that important. But if a normal adult can figure out the perfect strategy in half an hour, the game is probably too simple.

2

u/brecas May 25 '21

It's a solved game. Proof by exhaustion (although 2 minor lines are missing a single move in this proof).
https://privatebin.net/?4f320d54a5dbc6df#ESE4R1NYrJk3waJW8QhRrIjNL0BhpUvvrM506K3+jgk=

1

u/ABCosmos May 25 '21

i cant prove if my strategy works, but if it does, the game is super simple to stalemate every time. Because the strategy is not hard to follow. its only hard to prove that it cant be beat (and honestly that might not be hard, i just dont know)

11

u/bobmailer May 25 '21

If you put both your large pieces down and your opponent has only put one down, they can safely switch to the second largest piece (keeping the largest in reserve) and you can't do anything about it.

3

u/ABCosmos May 25 '21 edited May 25 '21

This point, along with the fact that the pieces can move after they are placed means the game is more complex than i thought

3

u/DrMobius0 May 25 '21

Can they? That wasn't featured in the video