0832: "Tic-Tac-Toe"

[sardia]

Alt Text: The only winning move is to play, perfectly, waiting for your opponent to make a mistake.
It's kinda hard to read at first, but I'll get the hang of it.

BTW: For those of you wondering where the comic is, Go to xkcd.com.
Press back to go back one comic, and then press forward twice to get to the newest comic. It's strange like that, but it works when Randall hasn't updated the website fully.

[Kirby]

I have to say that this is absolutely beautiful.

Also, was I the only one that thought I was looking at a fractal at first glance?

[CorruptUser]

Basically, if X knows what to do, he will never lose, only tie.

Something everyone discovered when they were 8 and gave up playing tic-tac-toe.

And then played draughts, where oops, person who went first always won if they knew what to do.

[GoosebusterT5]

Great. Now do one for chess, please!

[echoechoecho]

Fractal you say? Maybe because that is what it is called.

http://www.stonybrook.edu/philosophy/fractal/2Tic.html

Though I admit Randall's version is a lot cleaner. I've seen this already before, and in different ways too, so I'm kinda sad, but still must've taken him a long time to do it.

(Here's another way of looking at all possible Tic-Tac-Toe moves: http://gamescrafters.berkeley.edu/software/TTTLegend.pdf . The colors represent the expected outcome of the game if your next move is at that square.)

[glasnt]

Two things...
First, golly, tic tac toe is now ruined forever.

And

Wow. Just, wow.

[SEE]

Basically, if X knows what to do, he will never lose, only tie.

Something everyone discovered when they were 8 and gave up playing tic-tac-toe.

And then played draughts, where oops, person who went first always won if they knew what to do.

Given the game wasn't solved until 2007, and it took twenty years and hundreds of computers to solve, I expect that most eight-year-olds do not play a deep enough game to actually always win if they went first, but merely that the first move was sufficient advantage to beat other eight-year-olds who also lacked a deep game.

[hthall]

Brilliant.

[Vehemence]

Am I the only one who always looked at tic-tac-toe Ender-style? No matter where the X went, I always mentally oriented it to the top-left or top-middle of the board. Looking at it this way, there are only three starting moves - corner, center, and edge. The board can be mirrored mentally, as well as rotated to fit your viewpoint. Because of the simple 3x3 nature of tic-tac-toe, and how much of it is based on perspective, it makes a significant portion of this map redundant.

I like it, it's interesting, but redundant.

[aeson25]

What's next, all the possible moves in GTNW?

Randall = WOPR?

[Malikat]

Brilliant comic. oddly fascinating.
but.. there's an error. D:
x,y.. for X, [1,3:2,1:2,2 & 2,3] are the same.

[Mavrisa]

Given the game wasn't solved until 2007, and it took twenty years and hundreds of computers to solve

Huh... I remember playing tic tac toe against an unbeatable flash game a few years before that...

[F-13]

This is why I love xkcd.

Now if there were just a way to input this jpeg into my brain (http://xkcd.com/644/)????...

[pwndnoob]

This is perhaps the first comment ever that I have found something I really disagree with. While the corner start is the best (with 4 ways to not lose, and all mirrors of each other), it is very much possible to start (as X) with both middle and side and still guarantee yourself at least a tie. And, because everybody and their mother knows how to defend against corner, playing the side is typically the easiest way to win, as your opponent is more likely to make a mistake.

Of course, if you play this way, your opponent will just pull out their xkcd, and defend perfectly. This comic will guarantee you will never lose. But, for something so amazingly detailed and spectacular, I feel a note that it isn't fully complete would have been appropriate.

[st0aty]

Would it be bad form to say that when I saw the title, before the image loaded I was thinking of "War Games"?

Btw, hi everyone, this is my first time posting on the boards.

[big boss]

Doesnt anyone just call the game checkers anymore...

[Alex Steiner]

I think there might be a mistake. One sequence is repeated, an adjacent one missing.

7/9 of the way down, 2/9 of the way across, the centre square of this section shows the sequence of moves above it (when it should have an O in the middle).

Does this make sense?

[JontomXire]

Hasn't anyone noticed that this is wrong? I haven't looked at the best moves for O bit, but the best move for X is always to go in the middle. Also on tracking through a game I got stumped until I realised that a cross that should be red was actually black.

As for it not being solved before 2007 that's gotta be wrong. I had this all figured out when I was around 10 or something - and I'd been writing computer programs for a year or two before that so I could have programmed an unbeatable computer player - not entirely sure I didn't at some point in my life.

Also, at some point in the 1900s I came across an article that found a way to create an AI player using matchboxes. There was a position drawn on each matchbox and you added or removed beads depending on whether you won or lost, and picked a move depending on which matchbox had the most or fewest beads. Basically it was a learning AI algorithm. It was deliberately flawed so as to not become unbeatable, but if you removed that part of the algorithm, after only a few games the matchboxes would have "learnt" how to play unbeatably.

Also isn't Checkers the same as Chequers which is draughts and not tic tac toe?

[thescientist]

"checkers" and "tic-tac-toe"/"noughts and crosses" are not the same thing (at least not in UK/AU/NZ)

signed up to say: this comic is a big F*** YOU to colourblind people.

Apologies for the negativity, but I could barely tell that the big top left X was red. Pretty please remake it with thicker lines/different colours (even a lighter red might do it) so that everyone can appreciate it

[Kxronos]

I was testing out a few of these moves and came across two moves that did not have suggested RED Xs. There may be more, but I've pointed arrows to the two Xs that I think should be red at the link below.
http://flarecorp.com/public/forums/tic_tac_toe.png

[Sojourner]

I love it. I so hope this can be made into a poster and sold in the shop... With any mistakes corrected of course and if too big... perhaps Vehemence's idea of only posting the three absolute possibilities per X or O would work nicely.

[hansolo22]

How is this NOT a thinly-veiled insult of the intelligence of the readers? He's basically saying "Since you could never figure this out yourself, I compiled this genius chart for you." And yet you still fellate Randall, saying how interesting/useful/whatever it is. I've known that tic-tac-toe was unbeatable with the advantage to the person with the first move since ten years old, at the very latest. It never made sense to my why it was so popular given that fact. Either way, isn't the optimal move always ridiculously obvious?

@Vehemence, I did the same thing. But this comic is not interesting.

Glasnt, you strike me as one of the intelligent posters not blinded by fanboyism here, so I'm going to end this with

Wow. Just, wow.

Hopefully you meant that the same way I do.

[Isaac20]

Huh... I remember playing tic tac toe against an unbeatable flash game a few years before that...

As for it not being solved before 2007 that's gotta be wrong.

Er, SEE was referring to Draughts, not Tic-Tac-Toe.

While it is trivial to solve Tic-Tac-Toe, I very much enjoyed this comic due to the fractal nature.

[Yoinkinator]

Well... this is quite strange...

I've spent the last few days programming an AI for Tic Tac Toe. It essentially finds all of the next possible moves, then finds all of the possible moves of all of the previous possible moves, and continues until the recursion ticker reaches 0 (it overloads if I don't) or if someone won and determines the best possible move. I finally got it working today, but sadly, It sucks: I can easily beat it. I did however make the AI play against itself and it ended a tie (War Games nostalgia ftw!). If I implement it, this chart will probably make the whole thing more effective...

I have also started "solving" the game of Tic Tac Toe on paper and am on the fourth turn so far, and I expect this to be a long and interesting project. I expect it to take up 5 pages in my notebook. Yeah, I'm a bored nerd X)

ANYWAYS, quite a cool chart. I like how it's organized

[Xylos]

"Long time fan, first time writing, blah blah blah..."

I'm suprised I don't see more mistakes, with the detail he goes into, but I have actually found one.

1 2 3
4 5 6
7 8 9

Using that coordinate grid (zooming in after each election), 3,4,5 is wrong. Its a copy of 3,4,6. The third "O" should be in space 5, not 6.

And, yes, I know no one would notice if I did not just point it out. But from the elaborate work Mr. Creator has done before, I figured he'd like this to be error-free.

As to a few comments.

I thought of the WOPR as well. Power to B movies!
Props to the "Ender-reorintation stratagy." Always been my line of thinking.
In general: It took some people 8 years to realise the game was pointless?

[Arancaytar]

This is the most awesome visualization of a decision tree I've ever seen.

[TravDogg]

Basically, if X knows what to do, he will never lose, only tie.

Something everyone discovered when they were 8 and gave up playing tic-tac-toe.

And then played draughts, where oops, person who went first always won if they knew what to do.

Given the game wasn't solved until 2007, and it took twenty years and hundreds of computers to solve, I expect that most eight-year-olds do not play a deep enough game to actually always win if they went first, but merely that the first move was sufficient advantage to beat other eight-year-olds who also lacked a deep game.

Also, according to http://en.wikipedia.org/wiki/Draughts#English_draughts, the 2007 solution shows that the game always ends in a stalemate if neither player makes a mistake.

[TheoGB]

That blows my mind a bit. Surely the best opening move in Noughts and Crosses is to start in the centre? The only way to win is if the other player lets you set up two winning positions, much like Connect-4, and that's surely easier from the middle?

[Goplat]

It really depends on who you're playing against. If X starts in a corner, 7 out of 8 possible moves for O are losing, compared to only 4 out of 8 for starting in the center. So if you're X and up against a complete newbie, go in the corner. But if you're up against someone who likes to take the center as quick as possible, then take it yourself, because if you let O take the center you probably won't do any better than a tie.

[KeithM]

Using the same method as Xylos (2010), both 567 and 583 lack a red cross.

and:

@TheoGB The only way to win is not per se to have two winning positions. You can also win if the opponent fails to spot a single winning position.

[K^2]

By what criterion is the corner move optimal to start the game?

By opening with center square, you can create a hidden win condition on your second turn if O takes edge, rather than corner square. Realistically, that's the only way you are beating anyone in Tic-Tac-Toe, ever. I would call that the most advantage you can get if you are opening.

ALL other combinations lead to a tie, so long as the opponent has half a brain.

[shashwat986]

This is the most awesome visualization of a decision tree I've ever seen.

Megalike!

[Thesh]

Would it be bad form to say that when I saw the title, before the image loaded I was thinking of "War Games"?

Btw, hi everyone, this is my first time posting on the boards.

Well, War Games was just on the other day. I watched it. I'm Randall did too.

Anyway, the one thing I know is that if X's first move is in the center, O must go to a diagonal or it will be doomed (if the other player knows what they are doing).

[sje46]

This one confuses me, however I figured out when I was 10 that you are guarenteed a win if you go first and take the center, and your opponent takes a side (not corner).

[knoop]

I (we) found a mistake:
X O X
X O (x)
O >O<(x)

() give the possible red X's and >< give the only proper O for the situation. and people whether you play with X or O it is impossible to win. the best way is to force your opponent in a mistake with the following sequence:

X
O
X

[nonstick101]

Great idea for a comic but I can't clearly see the red (partial Red/Green colorblind) the line is too thin.

[Burn0ut07]

Well... this is quite strange...

I've spent the last few days programming an AI for Tic Tac Toe. It essentially finds all of the next possible moves, then finds all of the possible moves of all of the previous possible moves, and continues until the recursion ticker reaches 0 (it overloads if I don't) or if someone won and determines the best possible move. I finally got it working today, but sadly, It sucks: I can easily beat it. I did however make the AI play against itself and it ended a tie (War Games nostalgia ftw!). If I implement it, this chart will probably make the whole thing more effective...

I have also started "solving" the game of Tic Tac Toe on paper and am on the fourth turn so far, and I expect this to be a long and interesting project. I expect it to take up 5 pages in my notebook. Yeah, I'm a bored nerd X)

ANYWAYS, quite a cool chart. I like how it's organized

Sounds like you are essentially doing a brute force search through all possibilities, and still not even picking the best which is weird. If you actually want to make it efficient you just need to follow some simple heuristics that will always lead to win or tie. Wikipedia pretty much lists out exactly how you would want to go about it. Building up a decision tree for this game is super inefficient as I am sure you noticed from you stack overflows.

Visualization was still fun to look at even if it's something most people know. People need to relax more its a comic after all guys not a research paper. It's not like he thinks we don't know these things.

[vintermann]

Basically, if X knows what to do, he will never lose, only tie.
Something everyone discovered when they were 8 and gave up playing tic-tac-toe.
And then played draughts, where oops, person who went first always won if they knew what to do.

Either you and your friends were super-geniuses, or you forgot the basic rule that makes draughts into a game: Captures are mandatory.

I wrote a post on boardgamegeek lamenting it: http://boardgamegeek.com/thread/584214/why-checkers-gets-no-love

[xkcdfan]

"checkers" and "tic-tac-toe"/"noughts and crosses" are not the same thing (at least not in UK/AU/NZ)

signed up to say: this comic is a big F*** YOU to colourblind people.

Apologies for the negativity, but I could barely tell that the big top left X was red. Pretty please remake it with thicker lines/different colours (even a lighter red might do it) so that everyone can appreciate it

Wow, and considering Randall even did a big ol' study that involved colorblindness a while back you think he'd know that.

[LordBritish]

Also, at some point in the 1900s I came across an article that found a way to create an AI player using matchboxes. There was a position drawn on each matchbox and you added or removed beads depending on whether you won or lost, and picked a move depending on which matchbox had the most or fewest beads. Basically it was a learning AI algorithm. It was deliberately flawed so as to not become unbeatable, but if you removed that part of the algorithm, after only a few games the matchboxes would have "learnt" how to play unbeatably.

Here is the article:
Mechanical computer uses matchboxes and beans to learn Tic-Tac-Toe
http://boingboing.net/2009/11/02/mechanical-computer.html