Tic Tac Toe
TheHoad
I don't have the answer to this puzzle, but I am confident that I soon
will if I post it here. It just struck me as an interesting question of
probability:
If one were to play 100 games of tic tac toe randomly, how many games
would be draws?
Regards to the list membership!
Adrian Hoad-Reddick The...@aol.com
Curd Reinert
In article <19970918030...@ladder01.news.aol.com>,
the...@aol.com (TheHoad) writes:
>If one were to play 100 games of tic tac toe randomly, how many games
>would be draws?
I had my computer play 100.000 games of random tic tac toe.
Player 1 (the one who starts) won 35993 games (so about 36 %),
player 2 won 28734 games (29 %), and 35273 games ended in a draw
(35 %).
I believe it could become quite a lot of work to calculate the
accurate probabilities.
Curd
--
@ _ Curd Reinert
.-.O_~=\-. ecreinerKLAMMERAFFEinformatikPUNKTuniBINDESTRICHosnabrueckPUNKTde
(_)= l'(_) Fingerabdruck: 93 11 4E 48 90 1D 51 5D 7E EA C1 81 BE 58 7E FD
Matthew Daly
nos...@informatik.Uni-Osnabrueck.DE (Curd Reinert), if that is your REAL
name, said:
>In article <19970918030...@ladder01.news.aol.com>,
> the...@aol.com (TheHoad) writes:
>>If one were to play 100 games of tic tac toe randomly, how many games
>>would be draws?
>
>I had my computer play 100.000 games of random tic tac toe.
>Player 1 (the one who starts) won 35993 games (so about 36 %),
>player 2 won 28734 games (29 %), and 35273 games ended in a draw
>(35 %).
>I believe it could become quite a lot of work to calculate the
>accurate probabilities.
There are only 9! ~ 360,000 games in all (less, really, since 9! assumes
that you keep playing after a line has been completed). You could
replace your random number generator with a bunch of nested loops and it
might even take less time than your first program to calculate the
precise answer.
-Matthew
--
Matthew Daly I feel that if a person has problems communicating
mwd...@kodak.com the very least he can do is to shut up - Tom Lehrer
My opinions are not necessarily those of my employer, of course.
--- Support the anti-Spam amendment! Join at http://www.cauce.org ---
joseph a reggettz
On Thu, 18 Sep 1997 14:40:04 GMT, mwd...@kodak.com (Matthew Daly)
wrote:
Matthew, there are WAY less than that. I have not done any math in a
while but think of it this way. To fill all the squares takes 5x's and
4 o's. Ok , how many ways can 4 o's fit in 9 squares?
guessing now 9*8*7*6=3024/4=756
divided by 4 because there are 4 rotations of the board. That sounds
like a more logical #. That's also why adults don't play tic tac toe
<g>
My math may be wrong but my logic is not
Matthew Daly
jar...@erols.com (joseph a reggettz), if that is your REAL name, said:
>On Thu, 18 Sep 1997 14:40:04 GMT, mwd...@kodak.com (Matthew Daly)
>wrote:
>
>>There are only 9! ~ 360,000 games in all (less, really, since 9! assumes
>>that you keep playing after a line has been completed). You could
>>replace your random number generator with a bunch of nested loops and it
>>might even take less time than your first program to calculate the
>>precise answer.
>Matthew, there are WAY less than that. I have not done any math in a
>while but think of it this way. To fill all the squares takes 5x's and
>4 o's. Ok , how many ways can 4 o's fit in 9 squares?
>guessing now 9*8*7*6=3024/4=756
>divided by 4 because there are 4 rotations of the board. That sounds
>like a more logical #. That's also why adults don't play tic tac toe
><g>
>My math may be wrong but my logic is not
The number of possible ending boards is less, but it would be hard to
use that number to calculate the probability of winning. For instance,
here is a "over-finished" board:
XOX
XOO
XOX
Who won? Don't know -- it depends on whether X or O completed their
column first. Counting the 9! different ways of filling the board in
order (i.e. 1 6 3 8 4 5 7 2 9 indicates a win for X) solves that
problem.
joseph a reggettz
On Thu, 18 Sep 1997 14:40:04 GMT, mwd...@kodak.com (Matthew Daly)
wrote:
>
>nos...@informatik.Uni-Osnabrueck.DE (Curd Reinert), if that is your REAL
>name, said:
>
>>In article <19970918030...@ladder01.news.aol.com>,
>> the...@aol.com (TheHoad) writes:
>>>If one were to play 100 games of tic tac toe randomly, how many games
>>>would be draws?
>>
>>I had my computer play 100.000 games of random tic tac toe.
>>Player 1 (the one who starts) won 35993 games (so about 36 %),
>>player 2 won 28734 games (29 %), and 35273 games ended in a draw
>>(35 %).
>>I believe it could become quite a lot of work to calculate the
>>accurate probabilities.
>
>There are only 9! ~ 360,000 games in all (less, really, since 9! assumes
>that you keep playing after a line has been completed). You could
>replace your random number generator with a bunch of nested loops and it
>might even take less time than your first program to calculate the
>precise answer.
>
>-Matthew
>--
>Matthew Daly I feel that if a person has problems communicating
>mwd...@kodak.com the very least he can do is to shut up - Tom Lehrer
>
>My opinions are not necessarily those of my employer, of course.
>
>--- Support the anti-Spam amendment! Join at http://www.cauce.org ---
Take back my last answer. DID the math
6!+5!+4!+3!+2!+1!=873 not counting duplicates
shouldn't this number be divisible by 4?
I am sure it is less than 220
You math guys can figure this out
Curd Reinert
In article <34253cbc....@newsserver.rdcs.kodak.com>,
mwd...@kodak.com (Matthew Daly) writes:
>>>If one were to play 100 games of tic tac toe randomly, how many games
>>>would be draws?
>>
>>I had my computer play 100.000 games of random tic tac toe.
>>Player 1 (the one who starts) won 35993 games (so about 36 %),
>>player 2 won 28734 games (29 %), and 35273 games ended in a draw
>>(35 %).
>>I believe it could become quite a lot of work to calculate the
>>accurate probabilities.
>There are only 9! ~ 360,000 games in all (less, really, since 9! assumes
>that you keep playing after a line has been completed). You could
>replace your random number generator with a bunch of nested loops and it
>might even take less time than your first program to calculate the
>precise answer.
I don't agree. There is no reason why each possible game should have the
same probability (1/#possible games), and I don't believe it. Show me why
all games have the same probability, and I will agree.
Bye,
Curd Reinert
> In article <34253cbc....@newsserver.rdcs.kodak.com>,
> mwd...@kodak.com (Matthew Daly) writes:
>>>>If one were to play 100 games of tic tac toe randomly, how many games
>>>>would be draws?
>>>
>>>I had my computer play 100.000 games of random tic tac toe.
>>>Player 1 (the one who starts) won 35993 games (so about 36 %),
>>>player 2 won 28734 games (29 %), and 35273 games ended in a draw
>>>(35 %).
>>>I believe it could become quite a lot of work to calculate the
>>>accurate probabilities.
>>There are only 9! ~ 360,000 games in all (less, really, since 9! assumes
>>that you keep playing after a line has been completed). You could
>>replace your random number generator with a bunch of nested loops and it
>>might even take less time than your first program to calculate the
>>precise answer.
This is what I wrote myself:
I don't agree. There is no reason why each possible game should have the
same probability (1/#possible games), and I don't believe it. Show me why
all games have the same probability, and I will agree.
And here are some numbers:
10 million randomly played games:
Player1 wins Player 2 wins Draw
3595897 2880184 3523919
36.0 % 28.8 % 35.2 %
255168 possible games:
Player1 wins Player2 wins Draw
131184 77904 46080
51.4 % 30.5 & 18.1 %
So I guess that all the possible games have not the same
probabbility. Of course, this is not a proof, but I am VERY
sure that the probability of player1 winning is closer to
36 % than to 51 %.
RM Mentock
Curd Reinert wrote:
> Half true.
> We all know that a game of tic tac toe will be a draw if every-
> body plays perfectly. It's quite interesting that this is still
> true regardless of where the first mark is set. You need not place
> the first mark in the middle, it's just the easiest way.
> But the second mark (the first of the second player) is the one
> that decides the game:
> - If the middle is still free, player 2 must place it there, or he
> will loose if player 1 plays without false
If that is true, how does player 1 force a win if player 1 plays in
a side and player 2 plays in a corner beside it?
--
D.
men...@mindspring.com
http://mentock.home.mindspring.com/index.htm
Mike Williams
In message <19970918030...@ladder01.news.aol.com> TheHoad wrote:
> I don't have the answer to this puzzle, but I am confident that I soon
> will if I post it here. It just struck me as an interesting question of
> probability:
>
> If one were to play 100 games of tic tac toe randomly, how many games
> would be draws?
>
Spoiler...
Answer:
The expected value for the number of draws is about 12.698
Method:
There are 9-factorial (362880) different tic-tac-toe games where X plays
first (treating rotations and reflections as different and always completing
all 9 moves even if one player has already won) since the first move can be
in any of the nine squares, the second can be in any of the remaining eight
squares etc.
I counted the number of these games which end in a draw (well, actually my
computer counted them) and there were 46080.
Playing randomly, there is an equal chance of playing each of these 362880
games, and therefore a 46080/362880 chance of each game being a draw.
The same applies for games where O plays first.
Curd Reinert
In article <342158DE...@doncaster.on.ca>,
Chris LeBlanc <cleb...@doncaster.on.ca> writes:
>I can't remember exactly where I read this, but :
>
>I read somewhere that the outcome of a tic tac toe game is based solely
>on the placement of the first of each mark. ie: X and O
>
>Given these, one can determine if the game will be a draw.
Half true.
We all know that a game of tic tac toe will be a draw if every-
body plays perfectly. It's quite interesting that this is still
true regardless of where the first mark is set. You need not place
the first mark in the middle, it's just the easiest way.
But the second mark (the first of the second player) is the one
that decides the game:
- If the middle is still free, player 2 must place it there, or he
will loose if player 1 plays without false
- If the middle is already occupied, he must put it in a corner
But all this has nothing to do with randomly played tic tac toe
and the probability of winning and loosing there, as it was stated
in the original problem.
Chris LeBlanc
I can't remember exactly where I read this, but :
I read somewhere that the outcome of a tic tac toe game is based solely
on the placement of the first of each mark. ie: X and O
Given these, one can determine if the game will be a draw.
I don't remember if they listed the probability or anything, I'm in the
middle of searching for the article!
Chris
TheHoad wrote:
> If one were to play 100 games of tic tac toe randomly, how many games
> would be draws?
--
Chris LeBlanc ---------- Home : (613)723-3426
28 Inverness Ave ------- Work : (613)829-6597
Nepean, ON
K2E 6N7
E-mail : cleb...@doncaster.on.ca
Home : Http://doncaster.on.ca/~cleblanc/website/main.shtml
Kevin Maguire
Chris LeBlanc wrote:
## I can't remember exactly where I read this, but :
## I read somewhere that the outcome of a tic tac toe game is based solely
## on the placement of the first of each mark. ie: X and O
## Given these, one can determine if the game will be a draw.
I presume you mean if players move randomly? In this case the answer
is NO. My code suggests there are 5184 different games (ignoring
symmetries) which end in a draw for each first move, excepting moving
to the centre square, where the number of games is only 4608. It
seems slightly surprising to me that a corner move has the same number
of drawn games as a middle-of-an-edge move ....
Kev
Curd Reinert
In article <342179...@mindspring.com>,
RM Mentock <men...@mindspring.com> writes:
>> Half true.
>> We all know that a game of tic tac toe will be a draw if every-
>> body plays perfectly. It's quite interesting that this is still
>> true regardless of where the first mark is set. You need not place
>> the first mark in the middle, it's just the easiest way.
>> But the second mark (the first of the second player) is the one
>> that decides the game:
>> - If the middle is still free, player 2 must place it there, or he
>> will loose if player 1 plays without false
>a side and player 2 plays in a corner beside it?
what my computer once told me when I programmed that stuff. Probabily
already the second error I posted on rec.puzzles tonight - but it's
already quite late (10:25 pm), and I'm getting tired, I'm afraid ;-)
Kevin Maguire
Curd Reinert wrote:
## I had my computer play 100.000 games of random tic tac toe. Player
## 1 (the one who starts) won 35993 games (so about 36 %), player 2
## won 28734 games (29 %), and 35273 games ended in a draw (35 %). I
## believe it could become quite a lot of work to calculate the
## accurate probabilities.
I had my computer play all games, maybe I made a mistake but ....
Player 1 won 131184 51.41084 %
Player 2 won 77904 30.53047 %
Draws 46080 18.05869 %
======
255168 (9! = 362880)
Kev
Monwhea Jeng
nos...@nospam.nospam (Curd Reinert) writes:
> Chris LeBlanc <cleb...@doncaster.on.ca> writes:
>>I can't remember exactly where I read this, but :
>>
>>I read somewhere that the outcome of a tic tac toe game is based solely
>>on the placement of the first of each mark. ie: X and O
>>
>>Given these, one can determine if the game will be a draw.
I'm not sure I understand this. Given perfect players, you can look at
the first two moves and determine the outcome of the game. But given two
perfect players, you can determine that the game is a draw before it
even starts.
>Half true.
>We all know that a game of tic tac toe will be a draw if every-
>body plays perfectly. It's quite interesting that this is still
>true regardless of where the first mark is set. You need not place
>the first mark in the middle, it's just the easiest way.
> But the second mark (the first of the second player) is the one
>that decides the game:
>- If the middle is still free, player 2 must place it there, or he
> will loose if player 1 plays without false
>- If the middle is already occupied, he must put it in a corner
I disagree.
123
456
789
Player 1 takes 4
The middle is free, but player 2 is not required to take it
Player 2 can go in 1,6, or 7, no?
Momo
joseph a reggettz
On 18 Sep 1997 20:15:35 GMT, nos...@nospam.nospam (Curd Reinert)
wrote:
>
>In article <19970918....@econym.demon.co.uk>,
> mike....@nospam.demon.co.uk (Mike Williams) writes:
>>> If one were to play 100 games of tic tac toe randomly, how many games
>>> would be draws?
>>Answer:
>>The expected value for the number of draws is about 12.698
>>
>>Method:
>>There are 9-factorial (362880) different tic-tac-toe games where X plays
>>first (treating rotations and reflections as different and always completing
>>all 9 moves even if one player has already won) since the first move can be
>>in any of the nine squares, the second can be in any of the remaining eight
>>squares etc.
>>I counted the number of these games which end in a draw (well, actually my
>>computer counted them) and there were 46080.
>>Playing randomly, there is an equal chance of playing each of these 362880
>>games, and therefore a 46080/362880 chance of each game being a draw.
>Yeah, you're right, I was wrong. I had a silly little mistake in the
>program that did the millions of games for me (if a game was won with
>the last mark, it was counted as a draw). I started it once again:
>From 1000000 randomly played games, 126821 games are a draw (coming close
>enough to the expected 126984). 584833 games are won by the player who
>starts the game, 288346 by the other.
>Higher number of games would even get closer to it.
>
>New puzzle:
>What's the accurat expected number of games won by the first player ?
>
> Bye,
>
> Curd
>
>--
> @ _ Curd Reinert
>.-.O_~=\-. ecreinerKLAMMERAFFEinformatikPUNKTuniBINDESTRICHosnabrueckPUNKTde
>(_)= l'(_) Fingerabdruck: 93 11 4E 48 90 1D 51 5D 7E EA C1 81 BE 58 7E FD
>
ok, there are only 126 games 16 of which are draws!!!!!!!!!!!
Since 'I' only see 16 of 126 games, I will list them. Let me know if I
miss any
oox
xxo
oxx
oxo
oxx
xox
oxo
xox
xox
oxo
xxo
xox
oxx
xoo
oxx
oxx
xoo
xox
oxx
xxo
oox
xoo
oxx
xxo
xox
oox
xxo
xox
oxx
oxo
xox
xoo
oxx
xox
xox
oxo
xox
xxo
oxo
xxo
oox
xox
xxo
oox
xxo
xxo
oxx
xoo
the end!!!!!!!!!!!!!!!!
Now, what are you math and computer guys going to do with that! hehe
Tim Firman
jar...@erols.com (joseph a reggettz) wrote:
>
>On 18 Sep 1997 20:15:35 GMT, nos...@nospam.nospam (Curd Reinert)
>wrote:
>
>>
>>In article <19970918....@econym.demon.co.uk>,
>> mike....@nospam.demon.co.uk (Mike Williams) writes:
>>>> If one were to play 100 games of tic tac toe randomly, how many games
>>>> would be draws?
>>>Answer:
>>>The expected value for the number of draws is about 12.698
>>>I counted the number of these games which end in a draw (well, actually my
>>>computer counted them) and there were 46080.
>>>Playing randomly, there is an equal chance of playing each of these 362880
>ok, there are only 126 games 16 of which are draws!!!!!!!!!!!
There are 5!*4! possible games for each "game" you listed, as there are
5! orders in which the x'es can be placed and 4! orders in which the o's
can be placed. The previous poster used a different definition of what makes
a game different.
Note that 10 * 5!*4! = 46080.
SPOILER for exact probability follows.
As Matthew Daly has noted, this sort of simplification does not always work.
The problematic cases are ones where either player may win, depending on the
order in which they play, e.g.:
xxx Labelled as: 123
xxo 456
ooo 789
However, in all these cases the two winning combinations must be parallel.
The probability that x will win given this layout can be computed, and it
will be general for all two possible winner layouts.
If x chooses 1,2,or 3 last he will always lose. 3/5 loss for x.
If o chooses 7,8,or 9 last he will lose the remaining games.
(2/5)*(3/4)=3/10 loss for o.
Given x chooses 4 or 5 last and o chooses 6 last, (1/10 chance)
If x chooses 1,2 or 3 second to last he will lose the remainder.
(1/10)*(3/4) loss for x, (1/10)*(1/4) loss for o.
Total is x wins 13/40 of the time, o wins 27/40 of the time.
So, of the 126 possible patterns, which are equiprobable:
16 are draws (see above quoted text)
36 are 2 possible winner cases - 130/40 x win, 27/40 o win.
(6 x wins * 2 o wins per x win * 3 placements of the 4th 'o')
12 are o wins outright cases (2 diagonals, 6 placements of the 4th 'o')
62 are x wins outright (the rest)
Giving: 16/126 probability of a draw
[36*(13/40)+62]/126= 737/1260 probability x wins
[36*(27/40)+12]/126= 363/1260 probability o wins
nos...@nospam.nospam (Curd Reinert) wrote:
>10 million randomly played games:
>Player1 wins Player 2 wins Draw
>3595897 2880184 3523919
>36.0 % 28.8 % 35.2 %
(this had an error in counting player 1 wins as draws)
note that 363/1260 would give an average of 2880952 per 10 million,
quite close to the experimental value of 2880184.
Tim
Curd Reinert
In article <19970918....@econym.demon.co.uk>,
mike....@nospam.demon.co.uk (Mike Williams) writes:
>> If one were to play 100 games of tic tac toe randomly, how many games
>> would be draws?
>Answer:
>The expected value for the number of draws is about 12.698
>
>There are 9-factorial (362880) different tic-tac-toe games where X plays
>first (treating rotations and reflections as different and always completing
>all 9 moves even if one player has already won) since the first move can be
>in any of the nine squares, the second can be in any of the remaining eight
>squares etc.
>computer counted them) and there were 46080.
>Playing randomly, there is an equal chance of playing each of these 362880
Monwhea Jeng
jar...@erols.com (joseph a reggettz) writes:
>On Thu, 18 Sep 1997 14:40:04 GMT, mwd...@kodak.com (Matthew Daly)
>wrote:
>>
>>nos...@informatik.Uni-Osnabrueck.DE (Curd Reinert), if that is your REAL
>>name, said:
>>
>>>In article <19970918030...@ladder01.news.aol.com>,
>>> the...@aol.com (TheHoad) writes:
>>>>If one were to play 100 games of tic tac toe randomly, how many games
>>>>would be draws?
>>>
>>>I had my computer play 100.000 games of random tic tac toe.
>>>Player 1 (the one who starts) won 35993 games (so about 36 %),
>>>player 2 won 28734 games (29 %), and 35273 games ended in a draw
>>>(35 %).
>>>I believe it could become quite a lot of work to calculate the
>>>accurate probabilities.
>>
>>There are only 9! ~ 360,000 games in all (less, really, since 9! assumes
>>that you keep playing after a line has been completed). You could
>>replace your random number generator with a bunch of nested loops and it
>>might even take less time than your first program to calculate the
>>precise answer.
>Matthew, there are WAY less than that. I have not done any math in a
>while but think of it this way. To fill all the squares takes 5x's and
>4 o's. Ok , how many ways can 4 o's fit in 9 squares?
>guessing now 9*8*7*6=3024/4=756
>divided by 4 because there are 4 rotations of the board. That sounds
>like a more logical #. That's also why adults don't play tic tac toe
><g>
>My math may be wrong but my logic is not
This isn't quite right. We sometimes need to know the order in which the
squares have been played, as well as the final setup. For example, if
the final position is
XXX
XXO
OOO
then we need to know in what order the squares were played to know
who won. Also, the board has 8 symmetries, not 4.
BTW, what is random play? If the board looks like
X23
4O5
678
is X twice as like to go in the set {3,6} as he is to go in {8}?
Or are 3 and 6 just one option?
Momo
Antony Sims
I have done a similar thing with random games and tried to work out how
many unique games of tic tac toe there are. I guessed at about 1/3 million.
I would like to know how many of these would be draws?
Tony Sims
TheHoad <the...@aol.com> wrote in article
<19970918030...@ladder01.news.aol.com>...
> I don't have the answer to this puzzle, but I am confident that I soon
> will if I post it here. It just struck me as an interesting question of
> probability:
>
> If one were to play 100 games of tic tac toe randomly, how many games
> would be draws?
>
Chris Cole
TheHoad <the...@aol.com> wrote:
> I don't have the answer to this puzzle, but I am confident that I soon
> will if I post it here. It just struck me as an interesting question
> of probability:
>
> If one were to play 100 games of tic tac toe randomly, how many games
> would be draws?
>
> Regards to the list membership!
> Adrian Hoad-Reddick The...@aol.com
This question is in the rec.puzzles archive:
==> competition/games/tictactoe.p <==
In random tic-tac-toe, what is the probability that the first mover
wins?
==> competition/games/tictactoe.s <==
Count cases.
First assume that the game goes on even after a win. (Later figure
out who won if each player gets a row of three.) Then there are
9!/5!4! possible final boards, of which
8*6!/2!4! - 2*6*4!/0!4! - 3*3*4!/0!4! - 1 = 98
have a row of three Xs. The first term is 8 rows times (6 choose 2)
ways to put down the remaining 2 Xs. The second term is the number
of ways X can have a diagonal row plus a horizontal or vertical row.
The third term is the number of ways X can have a vertical and a
horizontal row, and the 4th term is the number of ways X can have two
diagonal rows. All the two-row configurations must be subtracted to
avoid double-counting.
There are 8*6!/1!5! = 48 ways O can get a row. There is no double-
counting problem since only 4 Os are on the final board.
There are 6*2*3!/2!1! = 36 ways that both players can have a
row. (6 possible rows for X, each leaving 2 possible rows for O
and (3 choose 2) ways to arrange the remaining row.) These
cases need further consideration.
There are 98 - 36 = 62 ways X can have a row but not O.
There are 48 - 36 = 12 ways O can have a row but not X.
There are 126 - 36 - 62 - 12 = 16 ways the game can be a tie.
Now consider the 36 configurations in which each player has a row.
Each such can be achieved in 5!4! = 2880 orders. There are 3*4!4!
= 1728 ways that X's last move completes his row. In these cases O
wins. There are 2*3*3!3! = 216 ways that Xs fourth move completes
his row and Os row is already done in three moves. In these cases O
also wins. Altogether, O wins 1728 + 216 = 1944 out of 2880 times
in each of these 36 configurations. X wins the other 936 out of
2880.
Altogether, the probability of X winning is ( 62 + 36*(936/2880) ) /
126.
win: 737 / 1260 ( 0.5849206... )
lose: 121 / 420 ( 0.2880952... )
draw: 8 / 63 ( 0.1269841... )
The computer output below agress with this analysis.
1000000 games: won 584865, lost 288240, tied 126895
Instead, how about just methodically having the program play every
possible game, tallying up who wins?
Wonderful idea, especially since there are only 9! ~ 1/3 million
possible games. Of course some are identical because they end in
fewer than 8 moves. It is clear that these should be counted
multiple times since they are more probable than games that go
longer.
The result:
362880 games: won 212256, lost 104544, tied 46080
#include <stdio.h>
int board[9];
int N, move, won, lost, tied;
int perm[9] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
int rows[8][3] = {
{ 0, 1, 2 }, { 3, 4, 5 }, { 6, 7, 8 }, { 0, 3, 6 },
{ 1, 4, 7 }, { 2, 5, 8 }, { 0, 4, 8 }, { 2, 4, 6 }
};
main()
{
do {
bzero((char *)board, sizeof board);
for ( move=0; move<9; move++ ) {
board[perm[move]] = (move&1) ? 4 : 1;
if ( move >= 4 && over() )
break;
}
if ( move == 9 )
tied++;
#ifdef DEBUG
printf("%1d%1d%1d\n%1d%1d%1d w %d, l %d, t %d\n%1d%1d%1d\n\n",
board[0], board[1], board[2],
board[3], board[4], board[5], won, lost, tied,
board[6], board[7], board[8]);
#endif
N++;
} while ( nextperm(perm, 9) );
printf("%d games: won %d, lost %d, tied %d\n", N, won, lost, tied);
exit(0);
}
int s;
int *row;
over()
{
for ( row=rows[0]; row<rows[8]; row+=3 ) {
s = board[row[0]] + board[row[1]] + board[row[2]];
if ( s == 3 )
return ++won;
if ( s == 12 )
return ++lost;
}
return 0;
}
nextperm(c, n)
int c[], n;
{
int i = n-2, j=n-1, t;
while ( i >= 0 && c[i] >= c[i+1] )
i--;
if ( i < 0 )
return 0;
while ( c[j] <= c[i] )
j--;
t = c[i]; c[i] = c[j]; c[j] = t;
i++; j = n-1;
while ( i < j ) {
t = c[i]; c[i] = c[j]; c[j] = t;
i++; j--;
}
return 1;
}
********************************************
Instructions for Accessing the rec.puzzles Archive
INTRODUCTION
The rec.puzzles Archive is a list of puzzles, categorized by subject
area. Each puzzle includes a solution, compiled from various sources,
which is supposed to be definitive.
To request a puzzle, send a message to archive...@questrel.com
like:
return_address your_name@your_site.your_domain
send requested_puzzle_name
For example, if your net address is "mic...@disneyland.com", to request
"geometry/duck.and.fox.p", send the message:
return_address mic...@disneyland.com
send duck.and.fox
To request the index, use:
send index
To request multiple puzzles, use several "send" lines in a message.
Please refrain from requesting the entire archive via email. Use FTP.
FTP
The entire archive is also accessible via anonymous FTP, from any site
which maintains archives of the newsgroups news.answers or
rec.answers. The file part01 contains the index. The remaining files
contain alternating problem text and solution text for all the
puzzles.
Some FTP sites are:
North America:
ftp://rtfm.mit.edu/pub/usenet/news.answers/puzzles/archive
ftp://ftp.uu.net/usenet/news.answers/puzzles/archive
ftp://mirrors.aol.com/pub/rtfm/usenet/news.answers/puzzles/archive
ftp://ftp.cis.ksu.edu/pub/mirrors/news.answers/puzzles/archive
Europe:
ftp://ftp.cs.ruu.nl/pub/NEWS.ANSWERS/puzzles/archive
ftp://src.doc.ic.ac.uk/usenet/news-faqs/news.answers/puzzles/archive
ftp://ftp.uni-paderborn.de/doc/FAQ/rec/puzzles
Asia:
ftp://ftp.hk.super.net/mirror/faqs/puzzles/archive
GOPHER
From the global home page, the menu choices to access the archives
at "cs.ttu.edu" are:
North America/USA/Texas/Texas Tech University, Computer Sciences
/Entertainment/Games/Puzzles
To access "uni-hohenheim.de" your menu choices are:
Europe/Germany/University of Hohenheim/Lots of Interesting Stuff
/FAQ Frequently Asked Questions/rec/puzzles/archive
WAIS
wais://xraysgi.ims.uconn.edu:8000/rpa
WEB
http://xraysgi.ims.uconn.edu/searchform.html
By keyword as well as subject.
http://einstein.et.tudelft.nl/~arlet/puzzles/index.html
Partially HTMLized.
http://www.nova.edu/Inter-Links/puzzles.html
http://xraysgi.ims.uconn.edu/others.html
A list of other sites (maintained by David Moews)
THE rec.puzzles ORACLE
This is a group of rec.puzzles regulars, who are familiar with the
rec.puzzles archive, and who will find your answer there if it exists,
or maybe compose an original answer if they are interested enough!
At any rate, they promise to respond to your question within two days,
and perhaps save you the embarrassment of posting a well-worn
question. They will respond within two days even if they do not know
the answer to your question.
To query the rec.puzzles oracle, send email containing your question
to the following address:
Don Del Grande
"Antony Sims" <Anton...@btinternet.com> wrote:
>TheHoad <the...@aol.com> wrote:
>> If one were to play 100 games of tic tac toe randomly, how many games
>> would be draws?
>many unique games of tic tac toe there are. I guessed at about 1/3 million.
>I would like to know how many of these would be draws?
Well, taking symmetry and rotation into account, there are really only 12
ways to make each player's first move (number the spaces on the board 1-3
along the top, 4-6 in the middle, and 7-9 at the bottom): 1-2 (same as
1-4), 1-3 (same as 1-7), 1-5, 1-6 (same as 1-8), 1-9, 2-3 (same as 2-1),
2-5, 2-6 (same as 2-4), 2-8, 2-9 (same as 2-7), 5-1 (same as 5-any corner),
and 5-2 (same as 5-the middle of any side). This reduces the number of
games to a maximum of 12 x 7! = 60,480.
--------------------------------------------
Don Del Grande, del_...@ix.netcom.com
"In my day, working out 60,480 games of tic-tac-toe on a computer would
have taken the better part of an hour..."
elizabeth.waller
What is the tic-tac-toe skill level of the players being studied?
From: Leigh, experimental psychology