OT: Tic-tac-toe probability puzzle

[QuikSand]

Okay, there just isn't much to tic-tac-toe. Once you figure out basic strategy, you can force a tie every time. (Perhaps some of you will recall my chicken anecdote... there's now a similar trained chicken at the Tropicana in Vegas)

But, what if you don't follow a stategy? What if you simply pick your spots at random... and so does your opponent?

If X goes first, and O goes second... and both simply pick their placements at random... what is each's chance of winning the game?

[Dr. Sak]

Ok i'll be the first to guess....two thirds..

[John Galt]

FYI, I saw the chicken in Vegas last August, but the last time I was there (January), it was gone. Besides, you didn't really play the chicken (they kept the pecking pad hidden and where the chicken hit the pad was seemingly unrelated to the actual play).

As for the math puzzle, I guess X wins 60% of the time (but that answer doesn't have any math behind it).

[Bee]

Since 2/3rd is taken, I'll take 5/9ths.

[Bee]

Guess QS forgot about us. Left us hanging...

[Brillig]

Well, I'm not sure that QS had the answer to this before he posted

It's a pain in the ass to do, short of writing a program and brute-forcing it. I still haven't found an elegant way of doing it...

[JeeberD]

Originally posted by John Galt
FYI, I saw the chicken in Vegas last August, but the last time I was there (January), it was gone. Besides, you didn't really play the chicken (they kept the pecking pad hidden and where the chicken hit the pad was seemingly unrelated to the actual play).

Yeah, the chicken was a scam. Spent nearly an hour combing the damn casino to see it and then you find out that everybody's probably playing a computer program. Such a rip off...

[Bee]

I'll revise my answer.

I'm guessing X has a 1/3rd chance to win.
O has a 2/9ths chance to win.
and there's a 4/9ths chance the game is a draw.

Yes, I pulled those out of the air and have no backup.

[Franklinnoble]

Mmmm... Chicken...

[albionmoonlight]

Some things we know:

There are 9^2 (512) different boards possible.

[X wins] + [Y wins] + [tie] + [impossible] = 512

[impossible] boards are boards that have both X and Y winning or too many X's or Y's.

Not that I am ever any good at these, but this is hard, isn't it?

[John Galt]

Originally posted by JeeberD
Yeah, the chicken was a scam. Spent nearly an hour combing the damn casino to see it and then you find out that everybody's probably playing a computer program. Such a rip off...

I did, however, enjoying watch some of the people playing. One person actually lost after 3 turns by the chicken. She didn't see the diagonal coming.

[QuikSand]

I have yet to see this puzzle definitively "solved" except by way of a computer program. I suppose it's deceivingly difficult...

In theiry, the solution might start with counting the number of "end layouts" of X and O in the 3x3 grid, and seeing if anyone won the game. Then, from there, you'll have three easy-to-count sets: no winner, X wins, and O wins. However, you'll also have some where both X and O made a tic-tac-toe, and solving how to split those up is apparently the rub.

So, Brillig, I plead guilty. I was counting on you to show the way, at least to some degree. ::sigh::

[Brillig]

Oh, don't give up, I'm still noodling on it, just very slowly...

[stupid Hattrick - why did I sign up for that anyway, it's cutting into my puzzle time...]

[TredWel]

The only thing that I thought of is breaking down the set of moves up to isomorphism.

I.e., X has three opening moves: any corner, any side, and any center. Any corner move is the same as any other corner move, etc.

On X center: O has two moves - any corner and any side.

On X corner: O has five moves: adjacent sides, opposite sides, opposite corners, other two corners, and center.

On X side: O has 5 moves: adjacent corner, opposite corner, center, opposite side, other two sides.

This gets ugly quickly, but would still be faster than estimating all 9! possible set of moves.

[Brillig]

Obviously, this problem can be solved with a program, but that’d be too easy.

The problem is to determine what the probabilities are that X or O can win a game of tic-tac-toe where the plays are made randomly, X playing first. The approach I took to solving this was to break down the possible positions and determine the probabilities for each result. At the end, we can add up the individual probabilities and get the overall probabilities for a win for either X or O.

Neither X nor O can win in the first four moves, so the first situation we will look at is where X wins in 5 moves.

There are 8 different ways a player can win in tic-tac-toe – in any given orientation, 3 vertical, 3 horizontal and 2 diagonal. Throughout this analysis, the diagonals will be treated separately, as if a player wins with a diagonal, it is impossible for the opponent to have three in a row, which is not the case for a vertical or horizontal.

Where X wins in 5, we don’t need to be concerned about O having won previously, since O has only 2 moves…

For this first analysis, we will break it down in detail so the process is clear:

X wins in 5

Consider how many possible board patterns exist where X has won in 5 moves – we break this down by looking at the 8 different winning possibilities separately. If X wins by occupying the top horizontal, then there are 6 open spaces left ‘below’. The two O’s can be arranged in these 6 spaces in a total of 15 different patterns. Just for clarity, I’ll show the possibilities for this one:

X X X      X X X      X X X      X X X      X X X      
O O        O   O      O          O          O 
                      O            O            O

X X X      X X X      X X X      X X X      X X X      
  O O        O          O          O            O
           O            O            O      O 

X X X      X X X      X X X      X X X      X X X      
    O          O
  O            O      O O        O   O        O O

A similar set of patterns apply for each of the other horizontal and vertical ways for X to win in five moves. Also, for the diagonals, the problem is similar, putting two O’s into six spaces. Again, there are 15 patterns. (In this case, the difference between a horizontal/vertical win and a diagonal one is irrelevant).

So, multiplying the number of possible wins by the possible patterns for each, there are a total of 8 * 15, or 120 different board patterns that result in a win for X in 5 moves.

Now, how many ways are there to get to those patterns?

For the 3 X’s, you can get to that result in 6 different ways (3 options for the first X * 2 options for the second * 1 for the third). Similarly, for the 2 O’s, there are 2 different ways to get to that pattern.

So the total number of ways to get to the 120 different board patterns is 120 * 6 * 2, or 1,440 different ways.

Now, how many different possible ways are there to get through the first five moves? Well, X has 9 possibilities for the first move, O has 8 for the second, etc… So the total is 9 * 8 * 7 * 6 * 5, or 15,120.

This gives us the probability that X will win in 5 moves as 1,440 : 15,120, or 2 : 21.

Hopefully everyone is still following, because it only gets deeper from here…

Next we’ll look at the possibility that O wins in 6 moves.


O wins in 6

The patterns for O to win are the same as for X, 3 horizontal, 3 vertical and 2 diagonal. The new wrinkle in the analysis is that we need to look at patterns for 3 X’s in the 6 open spaces, as opposed to 2 O’s. Also, we need to make sure that the 3 X’s don’t line up, as that would imply that X already won on move 5.

There are 20 different ways to arrange the 3 X’s into 6 spaces, but 2 of them are disqualified because they result in a row of X’s. The same 18 patterns apply for the vertical as well as the horizontal. However, for the diagonals, there are 20 different patterns for the X’s, as it is impossible for X to get a win in that scenario.

So there are 6 * 18, or 108 different board patterns where O wins with a horizontal or vertical, and 2 * 20, or 40 patterns where O wins on the diagonal.

For the 3 X’s and 3 O’s, there are 6 ways (each) to get to each possible pattern. So the total number of ways to get to a pattern where O wins in 6 is 6 * 6 * (108 + 40) = 5,328.

Dividing by the total number of ways to get through the first six moves (9 * 8 * 7 * 6 * 5 * 4), we arrive at a probability that O wins in 6 of 37 : 420.


X wins in 7

Again, we extend on the last analysis. After discounting the winning row, we face the question of fitting 1 X and 3 O’s into the 6 remaining spaces.

Ignoring other considerations for the moment, there are 15 ways to put 4 ‘objects’ (X’s and O’s) into 6 spaces.

Looking at the horizontal/vertical case first, of those 15, 6 have 3 of those objects in a row of 3, the other 9 have no more than 2 in a row. If there are 3 in a row, then X must be one of those 3 in order to prevent O from winning – if there are 2 in a row, X can be any of the 4. So this means that there are (6 * 3) + (9 * 4), or 54 valid patterns for the 1 X and 3 O’s to go into 6 spaces.

In the case where X is winning on the diagonal, since there is no possibility of O winning there are 15 * 4, or 60 valid patterns for the 1 X and 3 O’s.

This adds up to (6 * 54) + (2 * 60), or 444 total board patterns where X wins in 7.

Looking at how many ways there are to get to those patterns, there are 6 ways to get the 3 O’s on the board. In theory, there are 24 (4 * 3 * 2 * 1) ways to get 4 X’s on the board – however, we need to account for the fact that the last move that X makes must be one that completes three-in-a-row. Of the 24 possible ways to place the 4 X’s, 1 in 4 will have the final X be not in the three-in-a-row. That leaves us with 18 valid ways to get the 4 X’s on the board.

This gives us 444 * 18 * 6, or 47,952 possible ways to get to a board pattern where X wins in 7 moves. Dividing by the possible ways to make 7 moves on the board, we have a probability of 37 : 140 that X wins in 7 moves.


O wins in 8

In the horizontal/vertical win case, there are 6 different ways to arrange 5 ‘objects’ in 6 spots. Since there are always 3 objects in a row in these cases, the extra O must always go in that row to break it up. So there are 6 * 3, or 18 different possible patterns for the 1 O and 4 X’s in this case.

For the diagonal win case, there are no such considerations, so the lone O can go in any of the 5 spots. So there are 6 * 5, or 30 different possible patterns for the 1 O and 4 X’s.

This leads to the calculation that there are (6 * 18) + (2 * 30), or 168 possible board patterns where O wins in 8.

As for how we get to those patterns, there are 24 possible ways to place the 4 X’s, and 18 ways to place the 4 O’s (as per above).

So there are 168 * 24 * 18, or 72,576 ways to get to a board pattern where O wins in 8. Dividing by the possible ways to make the 8 moves leaves us with a probability of 1 : 5 that O wins in 8.


X wins in 9

This one gets complicated. Due to the fact that X has 5 moves at this point, there are board positions where X has two ‘wins’ on the board, and we have to make sure we don’t count such positions twice.

So, going to the horizontal/verticals – there are 9 patterns of 2 X’s and 4 O’s that don’t have 3 O’s in a row. Of those, 5 will result in a double-win for X, 4 will not.

On the diagonal, there are 15 patterns for 2 X’s and 4 O’s – 8 do not result in a double win, 6 result in a combination horizontal/vertical + diagonal win, and 1 is a diagonal-diagonal double win.

Adding up the board position to get the total number of unique board positions, first the non-double wins (6 * 4) + (2 * 8), or 40. The number of double wins is (6 * 5) + (2 * 7), or 44. Since those are each being counted twice, we divide by 2 to get 22 unique double-win board positions.

As far as the placement of X’s and O’s, there are the normal 24 ways to place the 4 O’s on the board. As for the X’s if there is no double win, then the only criteria is that the last X placed must complete the three-in-a-row. That means that 2 out of 5 of the total possible placement orders should be disqualified. Since the total number is 5!, or 120, the number of possible orders for us is 72. If there is a double win on the board, then the last move must be made at the intersection of the double win. That means that the placement order is restricted to 4!, or 24.

So the total number of possible ways to get to an X wins in 9 position is (40 * 72 * 24) + (22 * 24 * 24). Dividing by 9! to get the probability, we find that the probability that X wins in 9 moves is 71 : 315.


Draw

As a check on our math, we will figure out the possibility that the match ends drawn after 9 moves. If we take this probability and add it together with the probability that X wins and the probability that O wins, we should reach 100%.

This, it turns out, is relatively easy to figure.

There are only 3 basic board configurations for a draw

  X O X      X X O      X O X
  O X X      O O X      X O O 
  O X O      X X O      O X X

The first pattern leads to 8 unique board configurations (4 by rotation, times 2 by reflection), while the other 2, being symmetric, lead to 4 unique board configurations each (by rotation). This gives us a total of 16 unique board configurations. We know that the number of placement orders for X is 5!, while the number for O is 4!.

This gives us a total number of possible ways to get a draw as 120 * 24 * 16, and dividing by 9! to get the probability gives us 8 : 63.


Summing up

The probability that X wins in 5 is 2:21.
The probability that O wins in 6 is 37:420.
The probability that X wins in 7 is 37:140.
The probability that O wins in 8 is 1:5.
The probability that X wins in 9 is 71:315.
The probability that there is a draw is 8:63.

The least common denominator is 1260, so converting, we get

The probability that X wins in 5 is 120:1260.
The probability that O wins in 6 is 111:1260.
The probability that X wins in 7 is 333:1260.
The probability that O wins in 8 is 252:1260.
The probability that X wins in 9 is 284:1260.
The probability that there is a draw is 160:1260.

Note that adding all six up comes to 1260:1260, so our math looks good.

The probability that X wins is 737:1260, or 58.5%
The probability that O wins is 363:1260, or 28.8%
The probability that there is a draw is 160:1260, or 12.7%


A final note

I discovered an interesting thing during this analysis. The probability that X wins in 5 (2:21) is exactly the same that X would get 3 in a row in 3 moves without any opposition (i.e., without O playing at all!).

[TredWel]

::applause::

I don't know if it's right or not (just skimmed through it, and it looks believable), but kudos for the effort.

[QuikSand]

Brillig, that's spot on... and very well laid-out, too. I hope this was worthwhile for you.

[Brillig]

Well, since Hattrick was down last night, I had to do *something*

[tucker342]

:applause:

impressive

[Craptacular]

I gave up when TredWel used "isomorphism".

[Shkspr]

Hmmm. Does that analysis take into account the fact that X might disagree with Whoopi's answer?