0832: "Tic-Tac-Toe"

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

Moderators: Moderators General, Prelates, Magistrates

User avatar
StClair
Posts: 408
Joined: Fri Feb 29, 2008 8:07 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby StClair » Sat Dec 11, 2010 4:39 am UTC

HOW ABOUT A NICE GAME OF CHESS?

User avatar
phillipsjk
Posts: 1213
Joined: Wed Nov 05, 2008 4:09 pm UTC
Location: Edmonton AB Canada
Contact:

Re: 0832: "Tic-Tac-Toe"

Postby phillipsjk » Sat Dec 11, 2010 5:27 am UTC

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:
CasinoChciken.com wrote: 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.
Did you get the number on that truck?

Yoinkinator
Posts: 2
Joined: Fri Dec 10, 2010 8:33 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby Yoinkinator » Sat Dec 11, 2010 6:24 am UTC

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

Just looked up "heuristics," thanks :)

Aarchaput
Posts: 2
Joined: Fri Dec 10, 2010 12:51 pm UTC

Re: 0832: "Tic-Tac-Toe"

Postby Aarchaput » Sat Dec 11, 2010 6:51 am UTC

Aarchaput wrote: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
Posts: 1
Joined: Sat Dec 11, 2010 6:55 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby N1C0LE » Sat Dec 11, 2010 7:02 am UTC

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? :roll:

User avatar
Werewolf
Posts: 61
Joined: Tue Aug 04, 2009 8:35 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby Werewolf » Sat Dec 11, 2010 7:49 am UTC

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

herbys
Posts: 55
Joined: Thu Oct 22, 2009 7:46 pm UTC

Re: 0832: "Tic-Tac-Toe"

Postby herbys » Sat Dec 11, 2010 9:59 am UTC

[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. :D

LesterDragon
Posts: 2
Joined: Sat Dec 11, 2010 10:33 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby LesterDragon » Sat Dec 11, 2010 10:52 am UTC

I've got no idea how this works

funda
Posts: 35
Joined: Wed Jan 28, 2009 10:04 am UTC

Re: 832 Tic-Tac-Toe

Postby funda » Sat Dec 11, 2010 11:29 am UTC

Mavrisa wrote:
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 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.
Last edited by funda on Sun Dec 12, 2010 2:04 am UTC, edited 3 times in total.
Poorly updated Blog http://johndasfundas.blogspot.com
Yes, I will clean it up.... later
And badly maintained website :http://www.fundazone.com

SuperfluousFluteMusic
Posts: 32
Joined: Mon Jul 12, 2010 8:52 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby SuperfluousFluteMusic » Sat Dec 11, 2010 11:30 am UTC

uncivlengr wrote: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
Posts: 111
Joined: Fri Jan 26, 2007 12:14 pm UTC

Re: 0832: "Tic-Tac-Toe"

Postby taemyr » Sat Dec 11, 2010 12:20 pm UTC

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
Posts: 4
Joined: Sat Dec 11, 2010 1:10 pm UTC

Re: 0832: "Tic-Tac-Toe"

Postby thomasahle » Sat Dec 11, 2010 1:42 pm UTC

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
Posts: 1
Joined: Sat Dec 11, 2010 6:23 pm UTC

Re: 832 Tic-Tac-Toe

Postby omf » Sat Dec 11, 2010 6:26 pm UTC

SEE wrote: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
Posts: 96
Joined: Fri Mar 05, 2010 8:04 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby DavidRoss » Sat Dec 11, 2010 6:50 pm UTC

Aarchaput wrote: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
Posts: 96
Joined: Fri Mar 05, 2010 8:04 am UTC

Some of these complaints make no sense

Postby DavidRoss » Sat Dec 11, 2010 7:09 pm UTC

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
Posts: 10
Joined: Sun Oct 03, 2010 11:48 pm UTC

Re: 0832: "Tic-Tac-Toe"

Postby Headrushed » Sat Dec 11, 2010 7:31 pm UTC

okay, now do one for reversi :D

onauta
Posts: 1
Joined: Sat Dec 11, 2010 7:44 pm UTC

Re: 0832: "Tic-Tac-Toe"

Postby onauta » Sat Dec 11, 2010 7:48 pm UTC

Xylos wrote:"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.

User avatar
Diadem
Posts: 5654
Joined: Wed Jun 11, 2008 11:03 am UTC
Location: The Netherlands

Re: 832 Tic-Tac-Toe

Postby Diadem » Sat Dec 11, 2010 8:06 pm UTC

SEE wrote:
Diadem wrote: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.
It's one of those irregular verbs, isn't it? I have an independent mind, you are an eccentric, he is round the twist
- Bernard Woolley in Yes, Prime Minister

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

Re: 832 Tic-Tac-Toe

Postby Algrokoz » Sat Dec 11, 2010 8:32 pm UTC

GoosebusterT5 wrote: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
Posts: 1
Joined: Sat Dec 11, 2010 8:33 pm UTC

Re: 0832: "Tic-Tac-Toe"

Postby Patq911 » Sat Dec 11, 2010 8:37 pm UTC

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

User avatar
ManaUser
Posts: 284
Joined: Mon Jun 09, 2008 9:28 pm UTC

Re: 0832: "Tic-Tac-Toe"

Postby ManaUser » Sat Dec 11, 2010 8:56 pm UTC

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

User avatar
SEE
Posts: 73
Joined: Mon Jun 30, 2008 1:58 pm UTC

Re: 832 Tic-Tac-Toe

Postby SEE » Sat Dec 11, 2010 10:32 pm UTC

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

User avatar
phillipsjk
Posts: 1213
Joined: Wed Nov 05, 2008 4:09 pm UTC
Location: Edmonton AB Canada
Contact:

Re: Some of these complaints make no sense

Postby phillipsjk » Sat Dec 11, 2010 10:45 pm UTC

DavidRoss wrote: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.
Did you get the number on that truck?

Patrius
Posts: 1
Joined: Sun Dec 12, 2010 12:39 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby Patrius » Sun Dec 12, 2010 12:42 am UTC

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?

funda
Posts: 35
Joined: Wed Jan 28, 2009 10:04 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby funda » Sun Dec 12, 2010 1:57 am UTC

DavidRoss wrote:
Aarchaput wrote: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.

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



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 :oops:


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 ?? :shock:
Poorly updated Blog http://johndasfundas.blogspot.com
Yes, I will clean it up.... later
And badly maintained website :http://www.fundazone.com

Retsam
Posts: 57
Joined: Tue Aug 18, 2009 5:29 am UTC

Re: 832 Tic-Tac-Toe

Postby Retsam » Sun Dec 12, 2010 2:16 am UTC

SirMustapha wrote:
chrth wrote:
SirMustapha wrote: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? "Oh me yarm, 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.

User avatar
BytEfLUSh
Posts: 308
Joined: Sat Jan 02, 2010 1:15 am UTC
Location: Sombor, Serbia, Pizza
Contact:

Re: 0832: "Tic-Tac-Toe"

Postby BytEfLUSh » Sun Dec 12, 2010 2:32 am UTC

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

Seriously, what was I thinking ?? :shock:


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 "tricks". :)
Image

Image

-- Professor Dan, The Man from Earth (paraphrased)

LesterDragon
Posts: 2
Joined: Sat Dec 11, 2010 10:33 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby LesterDragon » Sun Dec 12, 2010 7:41 am UTC

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.

User avatar
meatyochre
Posts: 1524
Joined: Mon Apr 05, 2010 7:09 am UTC
Location: flying with the Conchords

Re: 0832: "Tic-Tac-Toe"

Postby meatyochre » Sun Dec 12, 2010 8:26 am UTC

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

Image
Dark567 wrote:"Hey, I created a perpetual motion device"

"yeah, but your poster sucks. F-"

Image

User avatar
Cool Username
Posts: 23
Joined: Mon Nov 22, 2010 7:36 pm UTC

Re: 832 Tic-Tac-Toe

Postby Cool Username » Sun Dec 12, 2010 4:49 pm UTC

I understand this wasn't directed at me, buuuut...
Retsam wrote: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
Posts: 1
Joined: Sun Dec 12, 2010 6:30 pm UTC

Re: 0832: "Tic-Tac-Toe"

Postby thefoot » Sun Dec 12, 2010 6:43 pm UTC

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
Posts: 98
Joined: Thu Oct 30, 2008 3:59 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby iamevn » Sun Dec 12, 2010 6:43 pm UTC

funda wrote: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 ?? :shock:


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

User avatar
Thesh
Made to Fuck Dinosaurs
Posts: 6568
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: Colorado

Re: 0832: "Tic-Tac-Toe"

Postby Thesh » Sun Dec 12, 2010 6:53 pm UTC

iamevn wrote:
funda wrote: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 ?? :shock:


>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).
Summum ius, summa iniuria.

fredb
Posts: 1
Joined: Sun Dec 12, 2010 7:11 pm UTC

Re: 0832: "Tic-Tac-Toe"

Postby fredb » Sun Dec 12, 2010 7:32 pm UTC

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.
Last edited by fredb on Mon Dec 13, 2010 5:02 am UTC, edited 1 time in total.

orbik
Posts: 17
Joined: Sun Nov 21, 2010 7:06 pm UTC

Re: 0832: "Tic-Tac-Toe"

Postby orbik » Sun Dec 12, 2010 9:00 pm UTC

DavidRoss wrote: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
Posts: 1
Joined: Sun Dec 12, 2010 10:31 pm UTC

Re: 0832: "Tic-Tac-Toe"

Postby Oglokoog » Sun Dec 12, 2010 10:41 pm UTC

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

Re: 0832: "Tic-Tac-Toe"

Postby nneonneo » Mon Dec 13, 2010 8:49 am UTC

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:

Image
(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)
Image
(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:

Image
(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)
Image
(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.
Last edited by nneonneo on Wed Dec 15, 2010 2:21 am UTC, edited 6 times in total.

User avatar
Diadem
Posts: 5654
Joined: Wed Jun 11, 2008 11:03 am UTC
Location: The Netherlands

Re: 0832: "Tic-Tac-Toe"

Postby Diadem » Mon Dec 13, 2010 9:19 am UTC

Oglokoog wrote: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.
It's one of those irregular verbs, isn't it? I have an independent mind, you are an eccentric, he is round the twist
- Bernard Woolley in Yes, Prime Minister

User avatar
Kartoffelkopf
Posts: 134
Joined: Sat Jan 26, 2008 9:44 am UTC

Re: 0832: "Tic-Tac-Toe"

Postby Kartoffelkopf » Mon Dec 13, 2010 10:49 am UTC

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

Randall = WOPR?

Why not play it for yourself and report your findings? :lol:

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

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

FUCK.
THIS.
GAME.

jbaber wrote: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
Posts: 1
Joined: Mon Dec 13, 2010 5:26 pm UTC

Re: 0832: "Tic-Tac-Toe"

Postby ColinMcNulty » Mon Dec 13, 2010 5:39 pm UTC

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


Return to “Individual XKCD Comic Threads”

Who is online

Users browsing this forum: Eoink and 52 guests