0832: "Tic-Tac-Toe"

This forum is for the individual discussion thread that goes with each new comic.

Moderators: Moderators General, Prelates, Magistrates

javajosh
Posts: 4
Joined: Mon Dec 13, 2010 6:57 pm UTC

Re: 0832: "Tic-Tac-Toe"

Postby javajosh » Mon Dec 13, 2010 7:09 pm UTC

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

User avatar
Matt
Posts: 182
Joined: Sat Apr 15, 2006 1:01 am UTC
Location: behind the bottle of Campari

Re: 0832: "Tic-Tac-Toe"

Postby Matt » Tue Dec 14, 2010 2:31 am UTC

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
Hi. I'm from Massachusetts.

weisnix
Posts: 1
Joined: Tue Dec 14, 2010 8:28 pm UTC

Re: 0832: "Tic-Tac-Toe"

Postby weisnix » Tue Dec 14, 2010 8:38 pm UTC

There is a mistake in the map for O. One circle is black, but it has to be red. :P
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
Posts: 1
Joined: Wed Dec 15, 2010 12:44 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby xero_art » Wed Dec 15, 2010 12:53 am UTC

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!

User avatar
wil.langford
Posts: 4
Joined: Thu Oct 21, 2010 5:20 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby wil.langford » Wed Dec 15, 2010 1:34 am UTC

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 291 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
Posts: 3
Joined: Mon Dec 13, 2010 8:29 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby nneonneo » Wed Dec 15, 2010 1:38 am UTC

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

User avatar
RebeccaRGB
Posts: 336
Joined: Sat Mar 06, 2010 7:36 am UTC
Location: Lesbians Love Bluetooth
Contact:

Re: 0832: "Tic-Tac-Toe"

Postby RebeccaRGB » Wed Dec 15, 2010 2:44 am UTC

ColinMcNulty wrote: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.
Stephen Hawking: Great. The entire universe was destroyed.
Fry: Destroyed? Then where are we now?
Al Gore: I don't know. But I can darn well tell you where we're not—the universe!

User avatar
wil.langford
Posts: 4
Joined: Thu Oct 21, 2010 5:20 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby wil.langford » Wed Dec 15, 2010 8:08 am UTC

nneonneo wrote:@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:

Tic-Tac-Toe-Tree preview.jpg
Zoomed all the way out.


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

Tic-Tac-Toe-Tree preview 2.jpg
Zoomed in on a few nodes in the middle.

chuck981996
Posts: 10
Joined: Fri Oct 23, 2009 9:02 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby chuck981996 » Thu Dec 16, 2010 11:36 pm UTC

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

redscourge
Posts: 3
Joined: Wed Jan 12, 2011 7:25 am UTC

Tic Tac Toe, and comic #832

Postby redscourge » Wed Jan 12, 2011 9:37 am UTC

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.

User avatar
uncivlengr
Posts: 1202
Joined: Fri Nov 14, 2008 10:35 pm UTC
Location: N 49°19.01 W 123°04.41

Re: Tic Tac Toe, and comic #832

Postby uncivlengr » Wed Jan 12, 2011 8:15 pm UTC

What is with people thinking this is intended to be a practical tool for playing games of tic-tac-toe?
I don't know what to do for you

redscourge
Posts: 3
Joined: Wed Jan 12, 2011 7:25 am UTC

Re: Tic Tac Toe, and comic #832

Postby redscourge » Thu Jan 13, 2011 3:34 am UTC

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


uncivlengr wrote: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!

User avatar
Tyrannosaur
Posts: 107
Joined: Thu Sep 02, 2010 5:39 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby Tyrannosaur » Thu Jan 13, 2011 4:34 am UTC

xero_art wrote:4) Now make one for chess!


I second that motion.
djessop wrote:The t-shirt should read "There are 11 types of people in the world, those who understand binary, those who don't and those who insist the number above is pronounced as eleven no matter what base you're in".

User avatar
uncivlengr
Posts: 1202
Joined: Fri Nov 14, 2008 10:35 pm UTC
Location: N 49°19.01 W 123°04.41

Re: Tic Tac Toe, and comic #832

Postby uncivlengr » Thu Jan 13, 2011 2:43 pm UTC

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


uncivlengr wrote: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.
I don't know what to do for you

Algrokoz
Posts: 39
Joined: Sun May 02, 2010 1:36 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby Algrokoz » Tue Mar 22, 2011 1:45 am UTC

Patrius wrote:
sardia wrote: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
Posts: 6
Joined: Tue Dec 15, 2009 10:08 pm UTC

Re: 0832: "Tic-Tac-Toe"

Postby Zanmor » Thu May 05, 2011 5:26 am UTC

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

rauni
Posts: 16
Joined: Mon Jan 24, 2011 12:03 pm UTC

Re: Tic Tac Toe, and comic #832

Postby rauni » Wed May 11, 2011 7:40 am UTC

redscourge wrote: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
Posts: 3485
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: Tic Tac Toe, and comic #832

Postby rmsgrey » Fri Nov 30, 2012 3:10 pm UTC

redscourge wrote: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


uncivlengr wrote: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.

User avatar
Davidy
Posts: 221
Joined: Sat Dec 01, 2012 1:18 am UTC

Re: 832 Tic-Tac-Toe

Postby Davidy » Sat Dec 01, 2012 1:54 am UTC

SEE wrote:
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.

User avatar
Klear
Posts: 1965
Joined: Sun Jun 13, 2010 8:43 am UTC
Location: Prague

Re: 832 Tic-Tac-Toe

Postby Klear » Sat Dec 01, 2012 10:33 am UTC

Davidy wrote:
SEE wrote:
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.

User avatar
mathmannix
Posts: 1415
Joined: Fri Jul 06, 2012 2:12 pm UTC
Location: Washington, DC

Re: 832 Tic-Tac-Toe

Postby mathmannix » Mon Dec 03, 2012 2:36 pm UTC

Klear wrote:
Davidy wrote:
SEE wrote:
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?
I hear velociraptor tastes like chicken.


Return to “Individual XKCD Comic Threads”

Who is online

Users browsing this forum: Pfhorrest and 153 guests