Discuss Tic-Tac-Toe-Take-Two here.

[mith]

Tic-Tac-Toe-Take-Two

[HyToFry]

I'm too dumb to even calculate the number of possibilities.

[What if...]

I get the probability that X wins in three moves as 11/126. Anyone get this, or, hopefully, more?

[random thoughts]

If there are 9 spots for the opening move, then 8 for the next, etc...there would be 362,880 possibly ways to play. Of course, the board is symmetrical by 4 (can rotate the board 4 ways) so the actual different ways of playing would be 90,720. But, if the game is won, the game is over. Hmmm....

[HyToFry]

Just a guess... but I think X winning in four moves would be a lot higher than 11/126.

I don't think we need to take symetry into account, because we're working on random moves, and not final outcomes... though the percentages would still be the same, so it shouldn't matter.

The number of possible games after five moves *should* be 9*8*7*6*5. 15120.

[What if...]

Three moves, five total. I think almost 1/10 is actually pretty high for randomly picking three moves. Also, I reduced the fraction for 11/126. It was originally 1320/15120. Symmetry doesn't matter, as the probability won't change.




[This message has been edited by What if... (edited 03-19-2003 11:14 PM).]

[What if...]

Sorry, the probability is a bit higher, around 37/378 (1480/15120), because I forgot about some of the moves that can be won more than one way.

[redscitle]

I feel you guys are calulating wrong. You are finding possibly the number of ways for a given number of moves, however, the puzzle doesn't say how many moves are used or needed. I grabed a pen and paper and visually did every possible permutation(not combonation) possible if X starts first, and starts in any of the top three squares. this gave me 24 games(i think at least two were exactly the same, just with different starting points for the O, and because its probabitly each duplicate was still included in the total count). out of 24 games, i got x wins 16, o wins 5, and 3 draws. now this is only for the top row of x's starting point. i need to get to bed, so i can't do the last two rows, but if anyone notices what i did to get this then go ahead and finish(if you feel im on the right track), and see if you get it right. I'll post back in a few days, hopefully.

[redscitle]

Sorry for making you read that.. never mind, my stuff was messed up at the beginning, and my pattern changed after i changed the x to top mid position. maybe, if during class, ill look at this again.
Sorry again guys, for tht bs up there....

[kevinatilusa]

I think this might work:

Play the game through until all 9 moves have been made (regardless of whether there's a tic-tac-toe by move 5 or something). If both players have a tic-tac-toe in the extended game, then the winner is whoever completed their tic-tac-toe first. This is identical to the standard game.

There are 126 possible extended games (ways of choosing 5 out of 9), and 8 possible directions of getting tic-tac-toe. For each of these ways, there are (6 choose 2)=15 ways for x to get the win and (6 choose 1)=6 ways for y to get the win.
Thus it (initially) seems like x has 120 wins and y has 48. However, we've overcounted in two possible ways.

First: X could have tic-tac-toe in two directions simultaneously. There are 3*3 ways for x to get horizontal/vertical simultaneously, and 3*2 ways for x to get horizontal/diagonal simultaneously, and 3*2 ways for x to get vertical/diagonal simultaneously, so we've counted 21 wins twice, and x really only has 99 ways to "win" {edit: Ironically, I forgot about X's possible X, which adds another duplication, dropping the number to 98}

Second: X and Y could both have tic-tac-toe simultaneously. There are 3*2*3 ways for x and y to both get vertical tic-tac-toe (3 choices for x's column, 2 for y's column, 3 ways to fill in the remaining column), and ditto for both getting horizontal, so we've counted 36 wins for both x and y (call these wins "disputed", since either player could have won before we extended the game).

Therefore of our 126 equally likely extensions.

99-36=63 are undisputed wins for X {edit, 62}
48-36=12 are undisputed wins for Y
36 are still disputed, but someone has to have won
126-63-12-36=15 are draws {edit, this is up to 16}

It remains to classify the disputed extensions. X can win in precisely two ways:

Finish his row in the first 3 moves. The chance of this happening is 1 in (5 choose 3)=1/10
Finish his row in exactly 4 moves, and have Y NOT finish his row in 3 moves. The change of X's row being finished in the first four moves is the chance the 5th move is not in the X row, 2/5. However, we already counted the case where the row is finished in 3 moves above, so the chance it takes exactly 4 moves is 2/5-1/10=3/10. The chance y doesn't finish his row in 3 moves is the chance that his fourth move is in fact in the Y row, 3/4.

Therefore X won a disputed extension with probability 1/10+3/10*3/4=13/40.

Combining everything, the chance of a draw is 16/126=5/42=.127
The chance of x winning is 62/126+13/40*36/126=83/140=.585
The chance of y winning is 12/126+27/40*36/126=121/420=.288


Anyone want to check this?

{Edited to correct the one case I forgot about}
C

[This message has been edited by kevinatilusa (edited 03-20-2003 12:45 PM).]

[ZutAlors!]

OK, I did this in a similar way to Kevin's procedure:

1. If you play all the way through to the end, filling up all nine boxes, there are 126 possible end games.

2. This number can be reduced to 23 different games by combining rotations and mirrored games.

3. Of the 126 games, 16 result in ties, 62 result in wins for player 1, 12 result in wins for player 2, and 36 are ambiguous: they have wins for both players.

4. Each ambiguous game has one and only one possible win for each player.

5. To resolve the ambiguous games, I work backwards: If player 1 enters one of his marks in the winning row on the last turn (3/5 chance), then he loses (because player 2 has already won).

6. Likewise, if the above is not true (2/5 chance), then player 2 will lose if he enters one of his marks in the winning row on the last turn (3/4 chance) , then he loses (because player 1 has already won).

7. Repeating a couple more times and adding, the chance of player 1 *winning* in an ambiguous game is 13/40, and the chance of player 2 winning is 27/40.

8. Adding everything up:

Player 1 wins: 62/126 + (36/126)*(13/40) = 0.585
Player 2 wins: 12/126 + (36/126)*(27/20) = 0.288
Draws: 16/126 = 0.127


EDIT: Correction: found an error. Bingo! Another error, and now this matches Crysty's.



[This message has been edited by ZutAlors! (edited 03-20-2003 11:01 AM).]

[CrystyB]

i don't get it. Why doesn't my C program work??

code:

---

#include <stdio.h>





#define win(x) ((a[1][1]==x)&&(a[1][2]==x)&&(a[1][3]==x))||\


               ((a[2][1]==x)&&(a[2][2]==x)&&(a[2][3]==x))||\


               ((a[3][1]==x)&&(a[3][2]==x)&&(a[3][3]==x))||\


               ((a[1][1]==x)&&(a[2][1]==x)&&(a[3][1]==x))||\


               ((a[1][2]==x)&&(a[2][2]==x)&&(a[3][2]==x))||\


               ((a[1][3]==x)&&(a[2][3]==x)&&(a[3][3]==x))||\


               ((a[1][1]==x)&&(a[2][2]==x)&&(a[3][3]==x))||\


               ((a[1][3]==x)&&(a[2][2]==x)&&(a[3][1]==x))


//replace the numbers above by one less. I have C-style indexing... 





void main() {


 long a[3][3],win1=0,win2=0,draw=0,total=0,i,j,p1,p2,p3,p4,p5,p6,p7,p8,p9;


 for (i=0;i<3;i++) for (j=0;j<3;j++) a[i][j]=0;


 for (p1=0;p1<9;p1++) {a[p1/3][p1%3]=1;


 for (p2=0;p2<9;p2++) if (!a[p2/3][p2%3]) {a[p2/3][p2%3]=2;


 for (p3=0;p3<9;p3++) if (!a[p3/3][p3%3]) {a[p3/3][p3%3]=1;


 for (p4=0;p4<9;p4++) if (!a[p4/3][p4%3]) {a[p4/3][p4%3]=2;


 for (p5=0;p5<9;p5++) if (!a[p5/3][p5%3]) {a[p5/3][p5%3]=1;


  if (win(1)) {win1+=24/*9*729*/;total+=24;continue;}


 for (p6=0;p6<9;p6++) if (!a[p6/3][p6%3]) {a[p6/3][p6%3]=2;


  if (win(2)) {win2+=6;total+=6;continue;}


 for (p7=0;p7<9;p7++) if (!a[p7/3][p7%3]) {a[p7/3][p7%3]=1;


  if (win(1)) {win1+=2;total+=2;continue;}


 for (p8=0;p8<9;p8++) if (!a[p8/3][p8%3]) {a[p8/3][p8%3]=2;


  if (win(2)) {win2++;total++;continue;}


 for (p9=0;p9<9;p9++) if (!a[p9/3][p9%3]) {a[p9/3][p9%3]=1;


  if (win(1)) win1++; else draw++;


  total++;a[p9/3][p9%3]=0;}


  a[p8/3][p8%3]=0;}


  a[p7/3][p7%3]=0;}


  a[p6/3][p6%3]=0;}


  a[p5/3][p5%3]=0;}


  a[p4/3][p4%3]=0;}


  a[p3/3][p3%3]=0;}


  a[p2/3][p2%3]=0;}


  a[p1/3][p1%3]=0;}


 printf("wins for 1: %8ld/%8ld = %.5f\n",win1,total,win1/(float)total);


 printf("wins for 2: %8ld/%8ld = %.5f\n",win2,total,win2/(float)total);


 printf("draws:      %8ld/%8ld = %.5f\n",draw,total,draw/(float)total);


}

---

Got it! It didn't erase the numbers before 'continuing'...

Answer:

code:

---

wins for 1:   212256/  362880 = 0.58492 (58.492%)


wins for 2:   104544/  362880 = 0.28810 (28.810%)


draws:         46080/  362880 = 0.12698 (12.698%)

---

[This message has been edited by CrystyB (edited 03-20-2003 09:23 AM).]

[mith]

I spotted at least one error in kevin's solution. CB has the answer, though.

[Silversunset]

*sigh*
i know how to answer this, alas i don't have my tables with me they're at school.
so fine, you do it. i don't CARE!
*grumbles something about men and having to be right all the time*

------------------
"If you take the Christian Bible and put it out in the wind and the rain, soon the paper on which the words are printed will disintegrate and the words will be gone. Our bible IS the wind and the rain."
42

[CrystyB]

Hey, i just posted the brute force answer. I left all the chances of having the solution text from a GLer's solution to anybody else who wants that, in this case it could be you, Silverella!

And if i'm not mistaking, the error in the '126 final outcomes' approach is due to the fact that those final positions are not equi-probable... Right?

[What if...]

All outcomes are equuiprobable, since you're just sticking 9 marks randomly in 9 squares. By using the probability that someone would win each way at the end minus doubles and some of the ambiguous cases, I got CB's fractions. Everything is based on the final board configuration, since the double and ambiguous type scenarios already mentioned above are the only times order matters. This is my reasoning (almost) in its entirety.

probability X has 3 in a row each way - probability of doubles - probability that O gets an ambigous case = probability that X wins
and vice versa for O.
probability X has 3 in a row each way= number of ways X can get 3 in a row x the probability of each
=8 x (5/9 x 4/8 x 3/7) the series of fractions being the chance of X being in three places
doubles = 22 ways x (5/9 x 4/8 x 3/7 x 2/6 x 1/5) these fractions being the chance X is in five specific places
probability of an ambiguous case = chance of a horizontal/vertical win for X x probability that the other two X's are in the same row/column leaving a row/column for O
=6 x (5/9 x 4/8 x 3/7) x 2/5
The probability that X wins an ambiguous case is 13/40 (kevin's figure is right).
So probability X wins ends up being (20/21)-(11/63)-[(27/40) x (2/7)]= 737/1260= 58.49206%
Similarly, since the probability for the Os being in certain places is 4/9 x 3/8 x 2/7 x 1/6, there is no chance of doubles, and (if you think for a second) all vertical and horizontal wins for O are ambiguous cases, as the Xs fill one of the remaining rows/columns:
chance of winning diagonally + chance of winning an ambiguous horizontal/vertical case = chance O wins.
There are 2 diagonal terms and 6 horizontal and vertical terms, so
probability O wins = [2 x (4/9 x 3/8 x 2/7)] + (27/40)[6 x (4/9 x 3/8 x 2/7)]= 121/420= 28.80952%
You can also just use the earlier 2/7 in this equation instead of the 6 x fractions term.
Probability of a draw = 100% - the probability of O winning or X winning = 8/63 = 12.69842%


Edited for clarity, though that might not be enough to clarify my scattered thoughts...



[This message has been edited by What if... (edited 03-24-2003 05:53 PM).]

[HappyFunBall]

I think people are close, but I came up with some different answers:


First, note that there are 3 different kinds of draws:

code:

---

xxo   xxo   xxo


oox   oox   oxx


xxo   xox   xoo

---

The first kind is really 4 after rotation/reflection, the second kind is really 4, and the third is really 8. So, there are 16 different classes of draws, and each one can be played 5! * 4! ways, for a total of 46080 total ways a draw can be played. Now, the chance of playing any one of those draws specifically, is 1/9!, so the total chance of playing a draw is 46080/9! = 8/63. I think I'm in agreement with other people here, but not for the next part.

Now we figure the chance that O wins (easier I think, than figuring X). O can win in 6 moves 2 different basic ways:

code:

---

ooo   oxx


xx-   xo-


x--   --o

---

In the first case, there are 6*[C(6,3) - 2] = 148 different ways to arrange it (the Os can be in any row or column, and the Xs can be arranged in any of the 6 remaining spots, except when they form a win also).

In the second case, there are 2*C(6,3) = 40 different ways to arrange it (2 diagonals and there are no ways for the Xs to have a win).

So there are a total of 188 ways for O to win in 6 moves with 3!*3! different ways to play each one, and the chance of playing any one of these games is 1/P(9,6).

Similar reasoning gives 6*[C(6,4) - 2*3]*2 + 2*C(6,4)*2 = 168 ways for O to win in 8 moves with 4!*4! ways to play each one, and the chance of playing any one of these games is 1/P(9,8).

So, 188*3!*3!/P(9,6) + 168*4!*4!/P(9,8) = 149/420, which is the total chance that O wins.

Now, the chance of X winning is just 1 - (chance of O winning + chance of draw).
Numerically:
chance that X wins ~= 51.825 %
chance that O wins ~= 35.476 %
chance of draw ~= 12.698 %

Note that computing X directly gets kind of tricky because you have to consider situations like:

code:

---

xoo


xxo


xox

---

separately. And counting the number of ways to play that board isn't quite as straightfoward because the X in the upper left must be placed last (otherwise you'd already have a win.)

[HappyFunBall]

Ugh, I'm stupid. I made the same mistake I was careful to note in my previous post. In the case of 8-move O wins, there are actually 4!*(4! - 3!) ways to play each one, not 4!*4!. This is because the O that's not part of the win cannot be played last, otherwise it would have really been a 6-move win, not 8..

Taking this into account, and refiguring the numbers, I get the same answers as CrystyB's program.

[The GL Rebels]

gah, it's never as simple as it first looks. and i thought i was going to get it right when i figured out the 9! thing...

[What if...]

Well, now we now for sure what to bet on, though I don't really know why you would want to bet on a random game of Tic-Tac-Toe. And if you do bet on X, and lose a lot, you can console your self knowing you had almost a 60% chance of winning, so it wasn't quite as stupid as it looked...

[mathgrant]

There are 9!/3!*3!=10,080 different boards, since the order of a player's first three moves doesn't matter.

[ZutAlors!]

How so, mathgrant? Each position has either an X or an O; randomly filling a nine-position board with Xs and Os would result in 512 (2^9) different boards. Taking the subset of this where there are exactly five Xs and four Os results in 126 possible boards.

[mathgrant]

The order of the first three moves doesn't matter, BUT which move is fourth and which is fifth DOES matter. Remember, whoever gets tic-tac-toe first wins. If they BOTH get tic-tac-toe, then the order of moves will determine who got theirs FIRST, and hence who WINS.

[This message has been edited by mathgrant (edited 03-26-2003 02:18 PM).]

[Blacksilk]

Hey, labyrinthians. It's been a while...

I think we can solve this problem from the 126 end-states, all of course with equal probability. Obviously, no end-state will have two completed lines of Os, since that requires five of them. Almost as obviously, no end-state will have both two lines of Xs and a line of Os. So, the only end-states we have are A) cat's games, B) always wins for X, C) always wins for O, and D) one line of Xs and one of Os. This last possibility accounts for 36 of the 126 end-states. (The O line can be any of six rows and columns, and the extra O any of six remaining squares.) Given such an end-state, we can calculate the probability of the X line being completed first. X will fill his critical three squares in three turns (5 choose 3 = 1/10) of the time, in four turns (5 choose 4 - 5 choose 3 = 3/10) of the time, and in five turns 6/10 of the time. O will fill his critical three squares in three turns (4 choose 3 = 1/4) of the time, and in four turns 3/4 of the time. Since X is first, he will win iff the number of turns he takes is less than or equal to O's, which means (1/10*1/4 + 1/10*3/4 + 3/10*3/4 = 13/40). For 36/126 end-states, X wins 13/40.

How about the other end-states? There are 12 that are always wins for O (either of 2 diagonals and the stray being 1/6). There are many more that are always wins for X. First, there are the cases where X has two lines: both diagonals(1), diagonal-row(6), diagonal-column(6), row-column(9), equals 22. Then there are the end-states where X has only one line, but blocks all others: either diagonal, with two non-opposite sides (2*4=8) or another corner with a non-adjacent side (2*4=8); or one of six rows and columns, with the other two Xs blocking the remaining rows/columns without forming a second line [6*(3*3-5)=24]. 22+8+8+24=62 end-states where X always wins.

X wins 62/126 + (36/126)(13/40) = 737/1260.
O wins 12/126 + (36/126)(27/40) = 363/1260.

Hopefully I didn't make any sloppy errors...

--Silk--

[What if...]

Its right, if CB and others are, the fractions are equivalent. Hopefully, by this point, the answer is good (especially since so many get the same) but are there other methods (faster or more interesting?) we could use? I am hopelessly in love with exceptionally fast or un-dull ways of doing things...

I just realized I probably kill too much time here, looking at the list of last posts (wonderer was who I was before I registered).
[Edited to kill yet more time]



[This message has been edited by What if... (edited 03-28-2003 01:25 AM).]

[Jack Crazyquilt]

I must be crazy to dispute the answer agreed upon by so many people here, but I'm not entirely satisfied with the solution given.

In the Real World a game of tic-tac-toe ends as soon as one of the two sides completes a row. In the 'official' solution this idea is tossed out in favor of playing till the board is filled, regardless of whether there was a win earlier. We're assured this won't affect the probabilities. But is this really the case? There's 1440 ways for X to win on the fifth move, but by completing the grid this number swells to 34560. 6 and 7 move wins would also be increased of course. But the number of tied games is fixed at 46080 since we have to play the full 9 moves to reach one of them. Wouldn't this artificially inflate the percentage of wins compared to ties?

To test this, lets do things the hard way and enumerate all the possible games. (For brevity's sake I've left out the math for some of this, if there's a disagreement about some of my figures I'll address them as they're brought up.)

There's 9x8x7x6x5=15120 ways to play the first five moves. Of this number, 1440 games will be a win for X, leaving

15120-1440=13680 games not won by move 5. In each of these there's 4 ways to play the 6th move:

13680x4=54720 6-move games. O wins in 5328 of these, leaving

49392 'non-wins'. Multiplied by 3 (ways to play the seventh move):

49392x3=148176 7-move games, of which X wins 47952, leaving

100224 non-wins, multiplied by 2=

200448 8-move games. O wins 72576 leaving

127872 No need to multiply this time since there's only one square left to fill:

127872 9-move games, X wins 81792 of these, leaving

46080 tied games. so, there's

1440+47952+81792=
131184 wins for X

5328+72576=
77904 wins for O

46080 tied games.

This gives a total of 255168 possible games, considerably less than 9!, and would make the percentages:


X--51.41084% O--30.53047% Tie--18.05869%

-------------------

I expect my reasoning will be torn to shreds now, but this has been bugging me since the answer was posted, so I thought I'd raise the issue. At worst, I may at least get a better idea of exactly why I'm mistaken.

[CrystyB]

1. My program ends as soon as there's a victor!

2. You are affecting the probabilities! Not all the outcomes are equiprobable, so don't just divide the number of wins to the number of endings... Look at what i did in there (a win by the fifth move is worth 24 wins by the last move...).

[This message has been edited by CrystyB (edited 04-14-2003 06:49 AM).]