Author 
Message 
bass
Joined: 02 Jul 2007 Posts: 6


Tic Tac Blah 

I don't seem to be able to solve the Tic Tac Blah challenge, so please tell me whether I have made a mistake, or if there is a mistake in the challenge itself. Here's my reasoning, which produced the nonaccepted answer:
A win will not turn into a draw by further plays, so any won game can be continued until the board is filled. There are exactly M (no solutions on the forum, you said) distinct patterns which fill the tictactoe board with an O in the middle and four of both Os and Xs elsewhere. Every one of these patterns can be reached in an equal number of ways, since there are equally many Xs and Os, and there are no symmetry considerations to take into account. As the players play randomly, this means that every pattern is equally probable.
Now, counting that out of these M possible patterns exactly N are draws, the probability of a draw should be exactly N/M.
As my final attempt(s) a couple of minutes ago I submitted the result as a fraction, in case you want to check against my making a silly rounding error or some other likely idiocy.
Cheers,
bass


Thu Jun 05, 2008 12:04 am 


adum
Joined: 19 Apr 2007 Posts: 391




i think your reasoning is slightly off: you have to put the _first_ move in the center.
i'm pretty confident the challenge is correct because bok independently solved it without issue.
cheers,
adum


Thu Jun 05, 2008 12:12 am 


adum
Joined: 19 Apr 2007 Posts: 391




PS: please submit as decimal  i just check with a string compare, so a fraction won't get computed


Thu Jun 05, 2008 12:12 am 


bass
Joined: 02 Jul 2007 Posts: 6




[quote="adum"]
i'm pretty confident the challenge is correct because bok independently solved it without issue.
[/quote]
That's what I thought too. So I programmed it another way, to see where I went wrong. No help, still got the same result, (now with an extra factor of 576 in both the numerator and the denominator. And yes, I do submit in decimal. :)
Then I tried the trick of trying to explain my program to an imaginary someone, but even THAT did not help, so my choices are down to a) trying to guess where two people might make the same error and attempt to reproduce it, or b) email you my (now recoded, polished and thoroughly commented) solver, so you can just point at it and say "silly bass, you make a mistake on line 2!". (which I intentionally left empy, so the joke is on you! ha!)
Cheers,
bass


Thu Jun 05, 2008 5:45 pm 


adum
Joined: 19 Apr 2007 Posts: 391




i will quietly note that bass has now solved this challenge =)
adum


Thu Jun 05, 2008 10:21 pm 


bass
Joined: 02 Jul 2007 Posts: 6




[quote="adum"]i will quietly note that bass has now solved this challenge =)
adum[/quote]
Nearly silently I'll add that I'd never have found the required answer without the additional information that two people have independently reached the same result :)


Mon Jun 09, 2008 8:51 pm 


adum
Joined: 19 Apr 2007 Posts: 391




i will also note that bass was right, i was wrong, and i've updated the challenge text
adum


Mon Jun 09, 2008 8:55 pm 


therethinker
Joined: 28 Mar 2008 Posts: 144 Location: #hacker.org on Freenode 



I'm still having trouble with the challenge, and the added text just confused me.
Could you explain more? I can't figure out a difference between the two descriptions.


Mon Jun 09, 2008 11:18 pm 


adum
Joined: 19 Apr 2007 Posts: 391




in short, you want to divide the number of draws by the number of possible games.
the original description technically asked for something else, which is how likely a draw will be with both players playing randomly. the reason this is different is some games end earlier with a win, so they're more likely.
adum


Tue Jun 10, 2008 12:45 am 


Allosentient
Joined: 10 Apr 2008 Posts: 273




I still do not understand this problem or am doing it wrong. I am searching through all possible move combinations (starting with 8 possible moves excluding center). I do not count moves that occur after a win (though I have tried counting all moves including moves made after a win and still not getting anything).
All decimal points I have tried have not worked (I have included a trailing 0 to the left of the decimal, and have rounded to 8 decimal places).
I probably have a flaw somewhere, but if someone could point me in the right direction that would be great.


Fri Jun 13, 2008 7:46 pm 


bok
Site Admin
Joined: 30 Jan 2007 Posts: 24




I've looked at the answers you've submitted, and I can tell you that they are not being rejected because of a rounding error or a syntax issue. The values are pretty far off.
Maybe I can try to give an example to clarify what's being asked:
The first player plays in the center. After that, the second player plays randomly (in one of the 8 free positions), then the first player plays randomly (in one of the 7 remaining locations), etc... until one player wins, or the board is full (draw). Compute how many different ways there are to get to a draw, and divide by how many ways there are to get to any end of game. That's your solution.
So far, 5 people have found the correct solution independently, so it is safe to say that there is a 'common' understanding of what the required answer is.


Sat Jun 14, 2008 8:27 am 


Allosentient
Joined: 10 Apr 2008 Posts: 273




hmm, I have tried doing that. There must be a bug in my program. Thank you everyone who gave advice.
By the way, I am at the very last challenge, and I can't believe it is even possible to do what you are asking (you guys really come up with some brilliant things). I am sure gonna lose a lot of sleep on this one!


Sat Jun 14, 2008 9:02 am 


sky
Joined: 06 Jun 2008 Posts: 17


Two advices 

A pair of errors that made me waste too much time:
1) Be sure you are posting the floating point with a "." not a "," .It will sound like a joke but the first version of the ruby program i wrote to solve the problem gave as output the number in "fraction form", i made the floating point conversion with the gnome calculator and its output was a fp with a "," . The funny thing is that the answer was right but i didn't realize what the problem was
2) Endgames have to be counted with the right multiplicity I mean that there can be two or more (many in fact) different games that end in the same way. Those games should be counted as different
Ps.: yes, after the lame thing of the ","floating point i thought that maybe the order should count but i got negative response even in that case, so i smashed my head against a wall until god blessed me with the solution


Sat Jun 14, 2008 3:40 pm 


YesItsMe
Joined: 06 Nov 2008 Posts: 1


description misleading 

i solved this challenge, but found the description misleading as the note in parenthesis seems to describe exactly the number that solved it.
this is how i would describe what's asked for:
d = Number of possible draws starting with the first move in the center.
g = Possible games (incuding draws) starting with the first move in the center.
solution: d/g


Wed Nov 12, 2008 11:00 pm 


samc
Joined: 20 Aug 2009 Posts: 4


also found description misleading 

Let:
d = number of draws where player 1 starts in center
gc = number of possible games where player 1 starts in center
g = number of all possible games (regardless of where player 1 starts)
I interpreted "What fraction of all possible games are draws? (Note: that means something different from what fraction of random games played from this point would be draws.)" to mean d/g whereas the answer is actually d/gc.


Sun Aug 23, 2009 11:48 pm 


