0832: "Tic-Tac-Toe"

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

Moderators: Magistrates, Prelates, Moderators General

0832: "Tic-Tac-Toe"

Postby sardia » Fri Dec 10, 2010 7:53 am UTC

Image
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.
Last edited by sardia on Fri Dec 10, 2010 8:06 am UTC, edited 3 times in total.
User avatar
sardia
 
Posts: 2467
Joined: Sat Apr 03, 2010 3:39 am UTC

Re: 832 Tic-Tac-Toe

Postby Kirby » Fri Dec 10, 2010 7:54 am UTC

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?
User avatar
Kirby
 
Posts: 199
Joined: Tue Mar 30, 2010 11:08 pm UTC

Re: 832 Tic-Tac-Toe

Postby CorruptUser » Fri Dec 10, 2010 7:55 am UTC

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.
User avatar
CorruptUser
 
Posts: 5844
Joined: Fri Nov 06, 2009 10:12 pm UTC

Re: 832 Tic-Tac-Toe

Postby GoosebusterT5 » Fri Dec 10, 2010 8:01 am UTC

Great. Now do one for chess, please!
GoosebusterT5
 
Posts: 1
Joined: Fri Dec 10, 2010 7:56 am UTC

Re: 832 Tic-Tac-Toe

Postby echoechoecho » Fri Dec 10, 2010 8:01 am UTC

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.)
Last edited by echoechoecho on Fri Dec 10, 2010 8:08 am UTC, edited 2 times in total.
echoechoecho
 
Posts: 7
Joined: Wed Aug 11, 2010 4:10 am UTC

Re: 832 Tic-Tac-Toe

Postby glasnt » Fri Dec 10, 2010 8:03 am UTC

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

And

Wow. Just, wow.
User avatar
glasnt
 
Posts: 522
Joined: Fri Jan 25, 2008 5:18 am UTC
Location: SQUEE!

Re: 832 Tic-Tac-Toe

Postby SEE » Fri Dec 10, 2010 8:10 am UTC

CorruptUser wrote: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.
User avatar
SEE
 
Posts: 72
Joined: Mon Jun 30, 2008 1:58 pm UTC

Re: 0832: "Tic-Tac-Toe"

Postby hthall » Fri Dec 10, 2010 8:13 am UTC

Brilliant.
Look at me, still talking when there's Science to do.
hthall
 
Posts: 98
Joined: Wed Oct 10, 2007 3:40 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby Vehemence » Fri Dec 10, 2010 8:14 am UTC

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.
Vehemence
 
Posts: 27
Joined: Mon Apr 19, 2010 6:54 pm UTC

Re: 0832: "Tic-Tac-Toe"

Postby aeson25 » Fri Dec 10, 2010 8:14 am UTC

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

Randall = WOPR?
aeson25
 
Posts: 4
Joined: Wed Mar 18, 2009 3:58 pm UTC

Re: 0832: "Tic-Tac-Toe"

Postby Malikat » Fri Dec 10, 2010 8:14 am UTC

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.
Malikat
 
Posts: 2
Joined: Fri Dec 10, 2010 8:10 am UTC

Re: 832 Tic-Tac-Toe

Postby Mavrisa » Fri Dec 10, 2010 8:18 am UTC

SEE wrote: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...
"I think nature's imagination is so much greater than man's, she's never gonna let us relax."
Mavrisa
 
Posts: 340
Joined: Mon Dec 22, 2008 8:49 pm UTC
Location: Ontario

Re: 0832: "Tic-Tac-Toe"

Postby F-13 » Fri Dec 10, 2010 8:18 am UTC

This is why I love xkcd.

Now if there were just a way to input this jpeg into my brain (http://xkcd.com/644/)????...
F-13
 
Posts: 5
Joined: Tue Jun 29, 2010 9:36 am UTC

Re: 832 Tic-Tac-Toe

Postby pwndnoob » Fri Dec 10, 2010 8:19 am UTC

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.
pwndnoob
 
Posts: 1
Joined: Fri Dec 10, 2010 8:00 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby st0aty » Fri Dec 10, 2010 8:21 am UTC

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. :-)
st0aty
 
Posts: 4
Joined: Fri Dec 10, 2010 8:16 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby big boss » Fri Dec 10, 2010 8:21 am UTC

Doesnt anyone just call the game checkers anymore...
"Starbuck, what do you hear?"
"Nothing but the Rain."
User avatar
big boss
 
Posts: 589
Joined: Tue Mar 23, 2010 7:59 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby Alex Steiner » Fri Dec 10, 2010 8:23 am UTC

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?
Alex Steiner
 
Posts: 2
Joined: Fri Dec 10, 2010 8:13 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby JontomXire » Fri Dec 10, 2010 8:30 am UTC

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?
JontomXire
 
Posts: 1
Joined: Fri Dec 10, 2010 8:24 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby thescientist » Fri Dec 10, 2010 8:33 am UTC

"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 :)
thescientist
 
Posts: 3
Joined: Fri Dec 10, 2010 8:28 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby Kxronos » Fri Dec 10, 2010 8:34 am UTC

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
Kxronos
 
Posts: 1
Joined: Fri Dec 10, 2010 8:18 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby Sojourner » Fri Dec 10, 2010 8:39 am UTC

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.
Sojourner
 
Posts: 1
Joined: Fri Dec 10, 2010 8:35 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby hansolo22 » Fri Dec 10, 2010 8:39 am UTC

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
glasnt wrote:Wow. Just, wow.

Hopefully you meant that the same way I do.
Last edited by hansolo22 on Fri Dec 10, 2010 8:51 am UTC, edited 2 times in total.
hansolo22
 
Posts: 3
Joined: Fri Dec 10, 2010 8:21 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby Isaac20 » Fri Dec 10, 2010 8:39 am UTC

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

JontomXire wrote: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.
Isaac20
 
Posts: 19
Joined: Mon Oct 05, 2009 4:33 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby Yoinkinator » Fri Dec 10, 2010 8:44 am UTC

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 :)
Yoinkinator
 
Posts: 2
Joined: Fri Dec 10, 2010 8:33 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby Xylos » Fri Dec 10, 2010 8:52 am UTC

"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?
Xylos
 
Posts: 4
Joined: Fri Dec 10, 2010 8:44 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby Arancaytar » Fri Dec 10, 2010 8:53 am UTC

This is the most awesome visualization of a decision tree I've ever seen.
"You cannot dual-wield the sharks. One is enough." -Our DM.
Image
User avatar
Arancaytar
 
Posts: 1615
Joined: Thu Mar 15, 2007 12:54 am UTC
Location: 50.099432 degrees north, 8.572756 degrees east.

Re: 832 Tic-Tac-Toe

Postby TravDogg » Fri Dec 10, 2010 9:02 am UTC

SEE wrote:
CorruptUser wrote: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.
TravDogg
 
Posts: 7
Joined: Mon Jun 28, 2010 4:31 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby TheoGB » Fri Dec 10, 2010 9:04 am UTC

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?
TheoGB
 
Posts: 70
Joined: Fri Aug 22, 2008 1:38 pm UTC

Re: 0832: "Tic-Tac-Toe"

Postby Goplat » Fri Dec 10, 2010 9:18 am UTC

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.
Goplat
 
Posts: 490
Joined: Sun Mar 04, 2007 11:41 pm UTC

Re: 0832: "Tic-Tac-Toe"

Postby KeithM » Fri Dec 10, 2010 9:22 am UTC

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.
"It is nothing short of a miracle that modern methods of instruction have not yet entirely strangled the holy curiosity of inquiry." - A.E.
KeithM
 
Posts: 9
Joined: Fri Mar 20, 2009 11:41 am UTC
Location: 1098XG

Re: 0832: "Tic-Tac-Toe"

Postby K^2 » Fri Dec 10, 2010 9:31 am UTC

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.
K^2
 
Posts: 68
Joined: Mon Feb 18, 2008 6:33 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby shashwat986 » Fri Dec 10, 2010 9:45 am UTC

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


Megalike!
Apparently, 1 in 5 people in the world are Chinese. And there are 5 people in my family, so it must be one of them. It's either my mum or my dad. Or my older brother Colin. Or my younger brother Ho-Chan-Chu. But I think it's Colin -- Tim Vine
User avatar
shashwat986
 
Posts: 58
Joined: Wed Mar 24, 2010 10:15 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby Thesh » Fri Dec 10, 2010 9:49 am UTC

st0aty wrote: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).
Big are getting bigger and hearts are getting harder, an imaginary game
eating at every living thing, a voice dripping with sarcasm like a bloody fat slash
grinning over bleached white-fang teeth that glow like green warning signs of sickness.
User avatar
Thesh
Has the Brain Worms, In Case You Forgot.
 
Posts: 3438
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: California, Southern USA

Re: 0832: "Tic-Tac-Toe"

Postby sje46 » Fri Dec 10, 2010 9:56 am UTC

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).
General_Norris: Taking pride in your nation is taking pride in the division of humanity.
Pirate.Bondage: Let's get married. Right now.
sje46
 
Posts: 4720
Joined: Wed May 14, 2008 4:41 am UTC
Location: New Hampshire

Re: 0832: "Tic-Tac-Toe"

Postby knoop » Fri Dec 10, 2010 10:01 am UTC

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
knoop
 
Posts: 1
Joined: Fri Dec 10, 2010 9:58 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby nonstick101 » Fri Dec 10, 2010 10:01 am UTC

Great idea for a comic but I can't clearly see the red (partial Red/Green colorblind) the line is too thin.
nonstick101
 
Posts: 1
Joined: Fri Dec 10, 2010 9:55 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby Burn0ut07 » Fri Dec 10, 2010 10:05 am UTC

Yoinkinator wrote: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.
Burn0ut07
 
Posts: 8
Joined: Sun Feb 17, 2008 11:52 am UTC

Re: 832 Tic-Tac-Toe

Postby vintermann » Fri Dec 10, 2010 10:22 am UTC

CorruptUser wrote: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
vintermann
 
Posts: 7
Joined: Sun Aug 02, 2009 1:46 pm UTC

Re: 0832: "Tic-Tac-Toe"

Postby xkcdfan » Fri Dec 10, 2010 10:49 am UTC

thescientist wrote:"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.
User avatar
xkcdfan
 
Posts: 121
Joined: Wed Jul 30, 2008 5:10 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby LordBritish » Fri Dec 10, 2010 11:01 am UTC

JontomXire wrote: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
In vacuum, you are no longer a sucker.

now to something completely different: http://demesos.blogspot.com
LordBritish
 
Posts: 23
Joined: Tue Jun 30, 2009 9:10 pm UTC

Next

Return to Individual XKCD Comic Threads

Who is online

Users browsing this forum: Google [Bot], jpk, orthogon and 25 guests