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 non-accepted 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 tic-tac-toe 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
Tic Tac Blah
[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
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
-
therethinker
- Posts: 144
- Joined: Fri Mar 28, 2008 11:29 pm
- Location: #hacker.org on Freenode
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
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
-
Allosentient
- Posts: 273
- Joined: Thu Apr 10, 2008 9:47 pm
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.
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.
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.
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.
-
Allosentient
- Posts: 273
- Joined: Thu Apr 10, 2008 9:47 pm
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!
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!
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
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
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
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
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.
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.