Probability of winning tic tac toe game.

Question

You and your friend like to play tic tac toe, but are not very good at it. On each turn, the player picks a random empty square to place their mark. The game ends when the first person gets three in a row, as usual. If you make the first move, what is the probability that you win the game? If you make the first move, what is the probability that you win the game? If the answer can be expressed as $\frac{a}{b}$, a and b are coprime, find a+b.

My attempt:

No of probable ways of arranging tic tac toe symbols so as to win the game

=3horizontal ways+3 vertical ways+2 criss-cross ways=8

---

The total number of ways in which 3 spaces can be filled out of 9 spaces=9C3.

Therefore, Total number of outcomes=The total number of ways in which 3 spaces can be filled out of 9 spaces (and) One extra space where either of the two tic tac toe symbols can be filled up=9C3*2

---

Probability=8/(2*(9C3))=1/21

Answer 1

This is Problem E1324 from the American Mathematical Monthly, June-July 1958, p. 447. According to the solution the first player wins with probability $$\frac{1}{126}\left(62 + 36\cdot \frac{13}{40}\right)=\frac{737}{1260}.$$ See the details HERE.

Answer 2

This is not right. You just calculated the probability that if you randomly put down three X's, that you get a three in a row ... that is not at all the same as the probability of winning when you start and play a game against an opponent, even if you both randomly put down pieces. For one, there are many more games possible than $9 \choose 3$, and many of them result in a draw. Also, if your opponent wins, that opponent will win by one of the 8 three-in-a-row'.

Finally, just by gross estimation/judgment $\frac{1}{21}$ seems low ... it is true that there are many games that end in a draw, so those count against you winning, but just intuitively one would think the chance of you winning when you start and you both play randomly should be higher than $\frac{1}{21}$

Answer 3

There seems to be an error in either the accepted 1958 answer above, or in my attempt to verify it. Pardon my brute force method and (python) code inefficiencies below, but it's just a 3x3 game, and unless I'm missing something, there are 255168 win/lose/draw leaf nodes in the tree, and corresponding probabilities:

First player: 0.514108
Second player: 0.305305
Draw game: 0.180587

(in contrast to the 1958 solution of: 0.584850, 0.288275, 0.126875)

def winner(board, xwin=(1,1,1), owin=(2,2,2)):
#{
    for r in range(3):
        tup = tuple(board[r])
        if tup == xwin: return 1
        if tup == owin: return 2
for c in range(3):
    tup = (board[0][c], board[1][c], board[2][c])
    if tup == xwin: return 1
    if tup == owin: return 2

for tup in [(board[0][0], board[1][1], board[2][2]),
            (board[2][0], board[1][1], board[0][2])]:
    if tup == xwin: return 1
    if tup == owin: return 2

return 0

#}
def play_all_games(wins, losses, draws, player=1, board=None, mvnum=0):
#{
    if not board: board = [[0] * 3 for _ in range(3)]
x = winner(board)
if x == 1: wins[0] += 1
elif x == 2: losses[0] += 1
elif mvnum == 9: draws[0] += 1
else:
    for r in range(3):
        for c in range(3):
            if board[r][c] == 0:
                board[r][c] = player
                play_all_games(wins, losses, draws, 
                               2 if player == 1 else 1, 
                               board, mvnum+1)
                board[r][c] = 0

#}
wins, losses, draws = [0], [0], [0]
play_all_games(wins, losses, draws)
ngames = wins[0] + losses[0] + draws[0]
print(f"First player: {wins[0] / ngames:.6f}")
print(f"Second player: {losses[0] / ngames:.6f}")
print(f"Draw game: {draws[0] / ngames:.6f}")
print(f"\nWins/losses/draws/total: {wins[0]}/{losses[0]}/{draws[0]}/{ngames}")