0832: "Tic-Tac-Toe"

[javajosh]

I had a hankering (!) on Friday to animate this xkcd cartoon and explore some programming ideas. So I wrote an interactive zooming version in JavaScript and HTML. You can play with it here:

http://dl.dropbox.com/u/4566368/tic-tac-toe/index.html

Instructions: Drag the red squares over the side you want to play, then follow the cartoon's instructions, clicking on the opponents move and adjusting position as necessary. When you're done, zoom out by clicking the numbers on the upper left a few times. You'll get a neat picture.

Let me know what you think!

- Josh

[Matt]

It was nice to see this! Randy destroying me at tic-tac-toe (or pretty much any similar game) when we were very small is one of those memories that endures, and I'm glad he got back around to it

[weisnix]

There is a mistake in the map for O. One circle is black, but it has to be red.
It's in the middle, in the left boddom corner, in the middle of left side, the circle in the middle of the right.
I hope you can understand although my english is not that good(I'm german).
Btw My first post here

[xero_art]

I really only joined to say 4 things.

1) Henceforth Randall Munroe is my God.
2) (because) I actually made one of these(worse format) < a week ago
3) I want this on the sleeve of a hoodie.
4) Now make one for chess!

[wil.langford]

In my undergraduate Game Theory class, I made a PDF of the entire game tree of TTT. It's bigger, harder to read, and less useful than the representation of optimal moves given in the comic.

I wrote a Perl program to produce dot code which in turn got processed into the PDF:

Tic-Tac-Toe-Tree.pdf

(329.16 KiB) Downloaded 201 times

Zoom in to see the actual game states.

And before I get a bunch of replies from graph theorists, I know it's a digraph and not a tree. This is the relevant part of the writeup that accompanied the homework when I turned it in:

Explanation of PDF
The PDF accompanying this writeup is not the game tree for tic-tac-toe. The full game tree for tic-tac-toe is very large and would be difficult to represent as a whole in a meaningful way. Therefore, I’ve taken a cheap shortcut by creating a digraph that represents the game tree for tic-tac-toe.

In the digraph, each vertex represents a symmetrically distinct game state of tic-tac-toe. Game states to the left are parent states of their children on the right. Each edge in the graph represents a symmetrically distinct legal move. Red edges with triangular ends represent corner moves. Green edges with half-box ends represent edge moves. Blue edges with circular ends represent center moves.

A single play of tic-tac-toe can be traced from left to right on the digraph, beginning at the empty board on the far left and ending at a game state with no children (which corresponds to a “leaf” vertex in the full game tree.)

Each game state with more than one parent can be viewed as the root vertex of a symmetric equivalence class of subgames. Therefore, the full game tree could be generated by creating a separate copy of each vertex v for each of v’s parents.

There are 765 symmetrically distinct game states in tic-tac-toe. There are 138 “leaves.” (That is, 138 distinct win, loss or draw states.)

Symmetric equivalence between two game states was decided based on applying all eight symmetries of a square (from group theory) to one of the game boards and comparing the results to the other board to see if they were equal.

In the primary data structure I used, I referred to each game state only according to a symmetrically equivalent “master state” for its class. Effectively, I chose one game state from each equivalence class as the “name” of the entire class and used it throughout to refer to that class. This approach was a deliberate tradeoff: I wanted condensed enough output to be able to view as a whole, but the ability to trivially trace a single play of tic-tac-toe was lost (as discussed above.) It’s still possible to trace a given play, but it’s not trivially easy.

Wil

[nneonneo]

@Wil: That PDF comes up blank for me. Maybe it's too big to view?

[RebeccaRGB]

What gives with this forum? Can't post an image, can't set a signature, can fill in some profile data?!?

I'm guessing you can't do that stuff until you have a certain number of posts. (Wild guess: 5?) None of those restrictions were in place when I joined, but there have been some spambot attacks since then, so they must have recently put those in place.

[wil.langford]

@Wil: That PDF comes up blank for me. Maybe it's too big to view?

Hrm... you're not the first to tell me that. Fortunately the professor was able to read it, and I see it fine with everything I've used to view it. I'll attach a couple of images so you get the idea of the scale of the thing.

Here's a snapshot of the entire PDF zoomed all the way out:

Zoomed all the way out.

And here's one of a few nodes in the middle of the graph:

Zoomed in on a few nodes in the middle.

[chuck981996]

Interesting: The centre square for X is perfectly diagonally symmetrical.

[redscourge]

I wish I could enjoy #832, but I fear that somewhere out there in the world is someone smart enough to understand the diagram, yet not smart enough to realize that they should not solve simple problems in this way, which in this case is the very least efficient way. This fear is mainly rooted in the fact that I believe that inevitably, this person will one day work for a company that will eventually want to sell me something. I realize that comic is in no way an attempt to present an efficient representation of an optimal tic tac toe strategy, but the thought still makes me feel like...well...do a search for "Mr. Bean in the museum" and watch the video...like that!

In tic tac toe, I think the simplest way to express the optimal algorithm is basically like this:

while the game is not over yet do the following in order:
-if you see a move that will allow you to immediately win, take that move
-else if you see a move you must take to prevent the other player from immediately winning, take that move
-else if the center square is available take it
-else if any corner square is available take it
-else take any edge square

Basically, if the first player starts by taking the center square and the second player starts by taking an edge square, the first player can win, otherwise it should always be a tie unless someone screws up.

You could come to this same conclusion by discovering two facts about the game:

1) After a certain point, you really have no choice of what square to take next if you wish to avoid immediately losing, so after that point there's not really any need for "strategy". This point is most likely after the other player has chosen two squares, because the earliest one can win is when they choose their third.

2) Due to symmetry, the board can be simplified down to a 1/8th section like a piece of pie (i.e. the top left section would consist of the top left, top center, and center squares). Any move that would fall outside this section can be mirror transposed as though it fell within this section, so basically when not faced with an immediate win or loss situation, you only ever really have 2 (or 3 if the center is not yet taken) truly unique choices of where to move.

[uncivlengr]

What is with people thinking this is intended to be a practical tool for playing games of tic-tac-toe?

[redscourge]

...I realize that comic is in no way an attempt to present an efficient representation of an optimal tic tac toe strategy, but...

What is with people thinking this is intended to be a practical tool for playing games of tic-tac-toe?

That's not actually what I thought, but my post was so damn long I don't blame you for missing one of the sentences. Oddly enough there is actually an eye tracking study on Jakob Nielsen's site ( useit.com/eyetracking ) that shows this happens at about the place that sentence was at!

[Tyrannosaur]

4) Now make one for chess!

I second that motion.

[uncivlengr]

...I realize that comic is in no way an attempt to present an efficient representation of an optimal tic tac toe strategy, but...

What is with people thinking this is intended to be a practical tool for playing games of tic-tac-toe?

That's not actually what I thought, but my post was so damn long I don't blame you for missing one of the sentences. Oddly enough there is actually an eye tracking study on Jakob Nielsen's site ( useit.com/eyetracking ) that shows this happens at about the place that sentence was at!

You say this, and yet opt to post your own strategy, as if everyone doesn't know how to optimally play tic tac toe before they leave elementary school.

The algorithm itself isn't particularly interesting, efficiently presented or not, but the comic takes it and produces something visually engaging.

[Algrokoz]

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.

It seems that this graph assumes that X is going to make the first move in the corner, as opposed to the side or middle. Why is this? Are there less available winning scenarios if X's first move isn't in the corner, hence the "Optimal" part of the title?

If O is playing a similarly optimal game there are no winning games anywhere, ever. Opening in the corner is optimal because of the number of chances it gives O to not play optimally, not because of total potential win scenarios.

[Zanmor]

I'd like to see something like this for Connect4.

[rauni]

I wish I could enjoy #832, but I fear that somewhere out there in the world is someone smart enough to understand the diagram, yet not smart enough to realize that they should not solve simple problems in this way, which in this case is the very least efficient way. This fear is mainly rooted in the fact that I believe that inevitably, this person will one day work for a company that will eventually want to sell me something. I realize that comic is in no way an attempt to present an efficient representation of an optimal tic tac toe strategy, but the thought still makes me feel like...well...do a search for "Mr. Bean in the museum" and watch the video...like that!

In tic tac toe, I think the simplest way to express the optimal algorithm is basically like this:

while the game is not over yet do the following in order:
-if you see a move that will allow you to immediately win, take that move
-else if you see a move you must take to prevent the other player from immediately winning, take that move
-else if the center square is available take it
-else if any corner square is available take it
-else take any edge square

Basically, if the first player starts by taking the center square and the second player starts by taking an edge square, the first player can win, otherwise it should always be a tie unless someone screws up.

You could come to this same conclusion by discovering two facts about the game:

1) After a certain point, you really have no choice of what square to take next if you wish to avoid immediately losing, so after that point there's not really any need for "strategy". This point is most likely after the other player has chosen two squares, because the earliest one can win is when they choose their third.

2) Due to symmetry, the board can be simplified down to a 1/8th section like a piece of pie (i.e. the top left section would consist of the top left, top center, and center squares). Any move that would fall outside this section can be mirror transposed as though it fell within this section, so basically when not faced with an immediate win or loss situation, you only ever really have 2 (or 3 if the center is not yet taken) truly unique choices of where to move.

Do a similar algorithm for gomoku (15x15 tic-tac-toe, winner needs to get 5 in row), and then You are on to something!

Rauni

[rmsgrey]

In tic tac toe, I think the simplest way to express the optimal algorithm is basically like this:

while the game is not over yet do the following in order:
-if you see a move that will allow you to immediately win, take that move
-else if you see a move you must take to prevent the other player from immediately winning, take that move
-else if the center square is available take it
-else if any corner square is available take it
-else take any edge square

That strategy draws against itself, but loses as second player against an opponent who knows that you're using that strategy:

First move: X in any corner.
Second move: O in center.
Third move: X in opposite corner.
Fourth move: O in either remaining corner.
Fifth move: X in last corner (blocking).
Sixth move: O in an edge to block one of X's two threats.
Seventh move: X wins

Played out on a keypad, the game goes (taking the lowest number when equivalent moves are available): 1593748

You say this, and yet opt to post your own strategy, as if everyone doesn't know how to optimally play tic tac toe before they leave elementary school.

Apparently not - or at least not everyone can capture their knowledge in an algorithm. That or Redscourge was still in elementary school and had exceptional English skills for their age.

[Davidy]

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.

Shirley, you jest!

I saw "computers" in the 1950's, made of mechanical relays and incandescent lights, that could play perfect games. And, there were chickens in the 1930's that could play and win. I have no doubt that the game was solved pretty much as soon as it was created.

[Klear]

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.

Shirley, you jest!

I saw "computers" in the 1950's, made of mechanical relays and incandescent lights, that could play perfect games. And, there were chickens in the 1930's that could play and win. I have no doubt that the game was solved pretty much as soon as it was created.

He was talking about Draughts. Also that was two years ago.

[mathmannix]

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.

Shirley, you jest!

I saw "computers" in the 1950's, made of mechanical relays and incandescent lights, that could play perfect games. And, there were chickens in the 1930's that could play and win. I have no doubt that the game was solved pretty much as soon as it was created.

He was talking about Draughts. Also that was two years ago.

And don't call him Shirley.

Shirley, you meant Surely?