0832: "Tic-Tac-Toe"

[StClair]

HOW ABOUT A NICE GAME OF CHESS?

[phillipsjk]

This reminded me a little of the tic-tac-toe playing chickens. However, a little bit of research shows that the chickens are not actually playing tic-tac-toe. Their enclosure is:

One of the beautiful things about this promotion is that you can set your own frequency of winners. That means, that depending on your prize, you can set how often it pays; if your prize is $10,000 then you might want it to pay off one in every 15,000 players (15,000 chicken players is a little less than once a month for many properties); if your prize is $250 — or playable credits as some casinos have successfully done — then you might want to pay off one in every 150 tic-tac-toe players (several times a day).

- Q: How often does the chicken lose (how often to I have to pay out the prizes)?

I might be able to believe that chickens can be trained to play the game (poorly). I know for a fact that a chicken can't be trained to 'choose' when to lose.

[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

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.

Just looked up "heuristics," thanks

[Aarchaput]

I once made an HTML based game of Tic-Tac-Toe. The computer always went first. In all but two cases, the user lost. The user tied in those two cases. I'd post a link, but I don't recall the website it's found on, or even if it can still be found on that website.

It's no longer online. Oh well, it looked awful. I still have it on my computer. 84 pages.

[N1C0LE]

Soo... if tic-tac-toe is the simplest and most boring game, and we've all known how it works since we were seven years old, and these maps are simple fractals of X's and O's:

Then isn't this the fractal representation of complete boredom?

[Werewolf]

I realised when I was a small child that in the game...
The only winning move is not to play.

[herbys]

[quote="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?
quote]

So you didn't understand the joke? Haha...hahahahaha! You made my day.

[LesterDragon]

I've got no idea how this works

[funda]

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 remember making one based on html and javascript a long time back. And I knew figured out the strategy on a boring day in school, most probably in 5th grade ( It's ther ein my book of mathematical discoveries,along with the word you can make by turning a calculator upside down. like 710 becomes OIL). So, I really don't think it took until 2007 to solve.

[SuperfluousFluteMusic]

I think anyone arguing over optimal tic-tac-toe strategies has already lost.

I mean, it is cool as an intellectual exercise, but there are more important things. I guess it is fun as a non-serious topic.

[taemyr]

Whyn the corner is a better starting position.

If you start in the center the game goes:

• Opp takes corner->draw
• Opp takes side->you win

If you start in the corner the game goes:

• Opp takes center->you take opposite corner
  
  • Opp takes corner->you win
  • Opp takes side->draw
• Opp takes anything but the center->you win

In short starting with the corner gives your opponent more room to make a mistake. And it's a mistake that a person who have learnt, but not understood, the first strategy might make. All in all I think I have a greater proportion of wins when starting in the corner than in the center. Although it's rather a lot of years since I won a tic tac toe game so I could be misremembering.

Another, and rather better way of looking at it is; both moves lead to a drawn position so they are equivalent.

[thomasahle]

Randal should set up a bugzilla, so we could squatch out the bugs before this goes into the store.
Here is another (graphical) mistake: http://thomas.ahle.dk/screenshot1.png

[omf]

Given the game wasn't solved until 2007

It may have not been officially/mathematically solved until 2007, but I agree with other posters here who say they realized at a young age that you always ended-up at a stalemate if no one made mistakes.

Maybe we hadn't solved every possible move, but we understood the correct move given any particular state of the game.

[DavidRoss]

I once made an HTML based game of Tic-Tac-Toe. The computer always went first. In all but two cases, the user lost. The user tied in those two cases. I'd post a link, but I don't recall the website it's found on, or even if it can still be found on that website.

I don't understand. Who is the "user" in this case? Another computer process? If it is a human user, one that knows the basic strategy of tic-tac-toe, (and the first computer doesn't break the rules), how does the user lose?

[DavidRoss]

Some are complaining that the graphics are not crisp, but are Randall-esque. So? Do you also complain that a Monet is not photo-realistic? The point is that it is supposed to be uneven lines.

Some complain that it is not funny. I thought the point was not so much humor, but data visualization. I know the data - and have since I was 8 - but I had not thought to present it in the fractal way Randall did, so that was interesting enough. [If he copied from another without attribution, that is not cool, but it is conceivable that he thought of this without seeing prior versions of it. I have been on the Internets for many years and I hadn't bumped into this before.]

Some complain that the red-black color scheme doesn't work for those who can't distinguish colors. OK. That's fair. Easy enough to fix and one should be accommodating to one's audience. That said, if you can't distinguish the colors and you absolutely actually need this data as a reference guide while playing tic-tac-toe, just note that red is used to indicate the "current" move in any given situation, but you can infer the current move by looking at the relative sizes and where you came from. For example, when trying to figure out X's second move, look at the ninth of the X diagram that is the middle left. There are two large X's. The first one is the original X, so the second X of the same size must be the current move.

Some complain that some of the moves are in error. OK, if you are using this chart for tic-tac-toe, you'll go wrong, but if you are using this as a pretty visualization, it should work just fine. That said, Randall, couldn't you have checked your work? Sheesh.

For those who think the game is too trivial, try chess. For something somewhere in between, just play tic-tac-toe but don't draw the grid. The rules are the same, but the location of the grid relative to the moves only develops after a few moves. Think about it as if you are playing tic-tac-toe on an infinite grid with the constraint that all of the moves have to be contained within some 3x3 square.

[Headrushed]

okay, now do one for reversi

[onauta]

"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.

Using the same system, for the O grid, the sequences 1,2,7,8 and 1,2,7,9 should indicate wins for O by moving to 6.

[Diadem]

You're wrong. Checkers has been solved, draughts has not.

Draughts and checkers are the same game, just as football and soccer are.

I know people in different parts of the world sometimes refer to the same game by different names, and different games by different names, but generally checkers and draughts are not the same game. With checkers one generally refers to the version played on an 8x8 board where you're not allowed to move back at all except with promoted pieces, and with draughts you mean the version on an 10x10 board where pieces can take backwards and promoted pieces can move any number of squares. I know the former game is sometimes also called draughts, but I've never heard of the latter game being called checkers.

Either way, checkers is solved, draughts is not. Though unlike chess or go, it's not impossible that it'll one day be solved.

[Algrokoz]

Great. Now do one for chess, please!

Well since there are apparently more permutations of of a chess game than atoms in the universe, that might be a little hard.

Also, despite what other posters have said, corner is definitely the way to open.

[Patq911]

Can someone help me understand this? I don't get how to read it...

[ManaUser]

This is perfectly usable without color. The red just highlights your newest mark. It's a convenience, but it doesn't provide extra information.

[SEE]

You're wrong. Checkers has been solved, draughts has not.

Draughts and checkers are the same game, just as football and soccer are.

I know people in different parts of the world sometimes refer to the same game by different names, and different games by different names, but generally checkers and draughts are not the same game.

My analogy was far more specific than just making the point that games change names depending on location; thus italicization of the word "just". The customary name for the game in North America is the second in each case; the customary name in the rest of the English-speaking world is the former in each case. You can check the Oxford English Dictionary if you like, under "draught", definition 22; it specifies that draughts is called "checkers" in America. The English-language equivalent of the Dutch "dammen" is "international draughts"; unmodified, the English word "draughts" by default means "English draughts", the same game as checkers.

Accordingly, it is completely accurate to say, in English, that draughts is a solved game. It is international draughts that is not solved.

[phillipsjk]

For those who think the game is too trivial, try chess. For something somewhere in between, just play tic-tac-toe but don't draw the grid. The rules are the same, but the location of the grid relative to the moves only develops after a few moves. Think about it as if you are playing tic-tac-toe on an infinite grid with the constraint that all of the moves have to be contained within some 3x3 square.

The infinite grid does not complicate things at all. People have pointed out that rotations and flips are equivalent. Playing optimally, the first 'X' always takes a corner. Playing optimally, 'O' must take the center (diagonal from the corner). If 'O' takes an adjacent space, X can still take the opposite corner, defining the space (not optimal). 'O' must take center. 'X' must take side to block 'O'. 'O' must take corner to block 'X'. 'X' must take opposite corner to block 'O'. 'O' must take side to block 'X'. 'X' takes remaining side; draw.

X can still force a win if O doesn't take the center on the first move:
'X' takes corner. 'O' takes adjacent. 'X' takes what they hope is the center. 'O' blocks by taking a corner defining the boundaries. Both configurations are equivalent (only in the one case, the first move was the center). 'X' forks taking corner not blocked by 'O's first move. 'O' Chooses any open space. 'X' wins by completing row.

Edit: something in-between would be "checkers", that game solved in 2007.

[Patrius]

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?

[funda]

I once made an HTML based game of Tic-Tac-Toe. The computer always went first. In all but two cases, the user lost. The user tied in those two cases. I'd post a link, but I don't recall the website it's found on, or even if it can still be found on that website.

I don't understand. Who is the "user" in this case? Another computer process? If it is a human user, one that knows the basic strategy of tic-tac-toe, (and the first computer doesn't break the rules), how does the user lose?

I made one in which the user and the computer alternate for the first play.

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...

Are you referring to the HTML/javascript version i programmed when I was a kid.

Because that was way back in 2003.


Warning !! When i was a kid, i loved the Geocities/MySpace style


Sorry, it's old and full of ads from the "free hosting provider"
I'll upload it somewhere else later ..
http://johndavis.i8.com/tictac.htm

Seriously, what was I thinking ??

[Retsam]

For the love of God please click one of the links in my sig so I can someday move out of my mom's basement

fixt

That's about the fourth of fifth time I've read that rebuff here. Really, are you people that original? Must be reading way too much xkcd, then.

Originality criticism, from the troll who has the exact same thing to say about every xkcd comic? "Gee Willikers, this sux, I could have drawn a better comic, randall, your not funny" (despite the thousands of people who think he is hilarious)

And, as I've said before:
You don't need an excuse to praise someone for their work. However, you -should- have a reason if you're going to be a dick to someone for no reason. Randall puts hard work into these comics. VERY hard work. He spent months researching to make the map of the internet (http://xkcd.com/802/), and that was just one comic among the 3 he releases every week. He deserves more respect than having you constantly bashing him just cause you get a kick out of being a troll. You usually don't even have a good reason why the comics bad, except that you consider yourself the universal arbiter of what's funny. You shouldn't be disrespecting the guy "for teh lulz", haven't you heard of common decency? "Welcome to the internet", indeed.

EDIT: These fora have some interesting filters. I certainly didn't type "Gee Willikers", and it wasn't even anything that most people consider offensive... interesting.

[BytEfLUSh]

http://johndavis.i8.com/tictac.htm

Seriously, what was I thinking ??

The "Eye Teasers" section of your website looks like some interesting pages from "Elements of psychology". The rest of the book is boring, though I always enjoyed those "trickses".

[LesterDragon]

I don't really need the grid anyway. How I always saw it when I used to play:
If my opponent's X is in the middle and my O isn't in one of the corners the first time it's my turn (assuming X goes first) I'm screwed.

[meatyochre]

Not one of the colorblind folks thought to paste the image into paint and invert colors? That should be the first thing you do anytime you have trouble distinguishing colors...

[Cool Username]

I understand this wasn't directed at me, buuuut...

Randall puts hard work into these comics. VERY hard work.

God yes, it must be terribly time-consuming and exhausting to draw a handful of stick-figures three times a week. Gosh, us normal folk with 40-hour workweeks certainly have it easier than he does. Especially because he puts so much effort into the art too, like making sure the heads are even attached consistently to their bodies.

He spent months researching to make the map of the internet (http://xkcd.com/802/),

you mean the one where he openly admits he made a whole bunch of it up?

and that was just one comic among the 3 he releases every week.

Again, because clearly a map of the internet is exactly like 3, 4, or 5 panels populated only by shoddily drawn stick figures.

He deserves more respect than having you constantly bashing him just cause you get a kick out of being a troll. You usually don't even have a good reason why the comics bad, except that you consider yourself the universal arbiter of what's funny. You shouldn't be disrespecting the guy "for teh lulz", haven't you heard of common decency? "Welcome to the internet", indeed.

I can only speak for myself, but I'm not here to troll. I come here to critique Randall's latest comic. If I don't like it, or think it's bad in some way, I'm going to say so. Even better? I'm going to say why. Try to get a handle the idea that not everyone is as in love with xkcd as you are.

[thefoot]

It's actually much simpler than even this. As the board has horizontal and vertical symmetry, there are really only three possible opening moves.

side, corner, and middle. Displaying all the permutations from games starting from these three positions amounts to showing them all.

[iamevn]

Sorry, it's old and full of ads from the "free hosting provider"
I'll upload it somewhere else later ..
http://johndavis.i8.com/tictac.htm

Seriously, what was I thinking ??

>try to right click
"Right click popup menu not enabled!"

[Thesh]

Sorry, it's old and full of ads from the "free hosting provider"
I'll upload it somewhere else later ..
http://johndavis.i8.com/tictac.htm

Seriously, what was I thinking ??

>try to right click
"Right click popup menu not enabled!"

Line 282: Ads end.
Line 341: Ads begin again.

I have a paid webhost. If you want, I can upload it there. Just send me the HTML you want me to use (you know, for proper attribution - I already have the js).

[fredb]

Martin Gardner described a tic-tac-toe computer built with JuJuBes and small slip-open medicine boxes* in one of his SciAm columns in the 1950s. I built one back then and wish I still had it. This one seems at least very reminiscent of it.

* They were much like matchboxes, but plain white -- and not filled with matches. I doubt these are even used by pharmacies anymore. Even if they are, I doubt that any pharmacy today would fulfill a request for the 32 or so of them that the computer required.

[orbik]

For those who think the game is too trivial, try chess. For something somewhere in between, just play tic-tac-toe but don't draw the grid. The rules are the same, but the location of the grid relative to the moves only develops after a few moves. Think about it as if you are playing tic-tac-toe on an infinite grid with the constraint that all of the moves have to be contained within some 3x3 square.

How about the kind of noughts and crosses I learned as a kid: virtually unlimited grid (the paper's edges are seldom reached), and you need a row of 5 to win. It's what's usually referred to as "ristinolla" (cross-zero) or "jätkänshakki" (jack's chess) in Finnish. Would be awesome to see a similar graph of that one too, although it may not really be solved yet. Here's a java implementation http://biphome.spray.se/dread/connect5.html

After googling a little looks like Gomoku, basically the same game but played on a 15x15 board, has been solved in favor of the starting player. There are however special rules that lessen the advantage by disallowing certain patterns.

[Oglokoog]

For some reason, I registered to say this: I've played unlimited board, five-in-a-row (alternatively four) tic-tac-toe (called "piškvorky" (pish-quo-rki) in my language) since I was very little and my first encounter with this stupid and pointless 3x3 thing was when I was like 16. I don't understand how anyone can play more than three games and not know that it is trivial.

[nneonneo]

Someone asked about the "loser's version" of Tic-Tac-Toe, in which players attempt to force the other player to get a 3-in-a-row (also referred to as misère Tic-Tac-Toe).

So, without further ado, here are the graphs:


(full-size: http://upload.wikimedia.org/wikipedia/commons/thumb/f/f0/Losers-tictactoe-X.svg/4000px-Losers-tictactoe-X.svg.png, original: http://commons.wikimedia.org/wiki/File:Losers-tictactoe-X.svg)

(full-size: http://upload.wikimedia.org/wikipedia/commons/thumb/4/42/Losers-tictactoe-O.svg/4000px-Losers-tictactoe-O.svg.png, original: http://commons.wikimedia.org/wiki/File:Losers-tictactoe-O.svg)

I also generated similar graphs for the normal version of Tic-Tac-Toe, but they differ slightly from Randall's version. The most obvious difference is the centre-O move for X's tree: in his graphic, the lower-right move for X is identified as optimal, whereas in mine, the top-centre move is identified as optimal. My X graphic has a much simpler layout; there are only two ties (as opposed to 8), but Randall's version looks "nicer" in that it is symmetric in the centre. These are available at the following URLs:


(full-size: http://upload.wikimedia.org/wikipedia/commons/thumb/d/de/Tictactoe-X.svg/4000px-Tictactoe-X.svg.png, original: http://commons.wikimedia.org/wiki/File:Tictactoe-X.svg)

(full-size: http://upload.wikimedia.org/wikipedia/commons/thumb/2/2f/Tictactoe-O.svg/4000px-Tictactoe-O.svg.png, original: http://commons.wikimedia.org/wiki/File:Tictactoe-O.svg)

We observe that O manages a draw if (and only if) he plays the opening sequence 5,3,4; any deviation from this sequence results in a win for X, assuming X uses this strategy (if X does not, e.g. by playing on 5, 3 or 4 when he should not, then O's strategy similarly changes).

I defined the "optimal move" as the move which results in the fastest win, if possible, or the fewest draw outcomes.

Code is available upon request.

[Diadem]

For some reason, I registered to say this: I've played unlimited board, five-in-a-row (alternatively four) tic-tac-toe (called "piškvorky" (pish-quo-rki) in my language) since I was very little and my first encounter with this stupid and pointless 3x3 thing was when I was like 16. I don't understand how anyone can play more than three games and not know that it is trivial.

five-in-a-row is commonly known as Go-Moku though i've also heard the name Go-Bang. It is a forced win for the starting player, in somewhere around 15 moves (don't recall the exact number, but it was less than 20 and more than 10). Of course noone can memorize all variations for 15 moves, but still amongst experienced players the starting player wins 99.9% of games. The advantage is too big. A website where I play this game has for that reason introduced the following rules change: Black starts. First black move goes in the centre. White can answer wherever. Black's second move then has to be at least 3 squares away from his first stone. So he can not move in the 5x5 square centred around his starting stone. With these rules black still seems to have the advantage, but it's much smaller, and no forced win has so far been found.

Another variation upon this theme is of course Four-in-a-row or Connect Four. Which is played on a vertical board, i.e. the stones fall down to the bottom row. A common commercial version has a 7x6 board (7 wide, 6 high). This is a forced win for the starting player. It's of course significantly more complex than tic-tac-toe but still a rather simple win for experienced players. The nice thing about this game is that different board sizes change the outcome of the game. 7x6 is a win for the first player, but 7x7 is a tie. And 8x6 is a win for the second player. As far as I know all board sizes n * m where n + m <= 15 have been solved. The site I play it on has 8x8, which has not been solved. But amongst top players the second player virtually always wins. Still a very rich and interesting game, and for people without a lot of experience the starting advantage is very small. So I can really recommend 8x8 Four-in-a-row to everyone.

btw: n*m four-in-a-row for n + m <= 15 has been solved, like I said. But it has been solved in 1988! So 22 years ago. The only reason bigger board sizes have not yet been solved is because noone has tried. So there's an opportunity here to get your name in the history books! I once tried solving 8x8 myself, bur I don't know enough of that kind of algoritms. Might try again once I have more time again.

[Kartoffelkopf]

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

Randall = WOPR?

Why not play it for yourself and report your findings?

Of course, the only winning move is- *shot*

http://biphome.spray.se/dread/connect5.html

FUCK.
THIS.
GAME.

I'm glad there's at least the occasional WOPR reference. I can't believe I'm the first person to point out Randall's alt text is incorrect. It should say

A strange game. The only winning move is not to play.

I don't think you understand that references are often funnier if they are not completely identical to what they are referencing.

I like how this thread has devolved into flaming already. But, I guess I expected too much of this forum.

[ColinMcNulty]

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

Anyway, there's a logical error on the board. Not that it's wrong in it's interpretation or rules as others have stipulated, there's physically a O been drawn in the wrong place on the map. I have a screen shot of where the mistake is and what it should be, which I was going to post, but I can't and I can't even post a link to it. So it's here, not that anyone will likely bother to go look:

http://screencast.com/t/Uc5J8LnG