# Tic-Tac-Toe Game [duplicate]

What is the total number of strategies (pure strategies in game theory) in a Tic Tac Toe game for each player? Assume that it is a 3x3 game and 2 players.

Rule: The players put marks such as X and O sequentially. Both players observe all choices. The first player to have 3 of his/her marks in a row (horizontally, vertically or diagonally) wins.

I was looking at this post (A non-losing strategy for tic-tac-toe $\times$ tic-tac-toe) but it is a specific case that only considers winning strategies.

My solution strategy:

I know that there are 9! ways to play this game for one player, which is 362880. BUT this is the case if the game does not end in 5th, 6th or other moves. I am not really sure how to add in these factors.

## marked as duplicate by JMoravitz, user147263, Johanna, graydad, Adam HughesMar 12 '15 at 1:54

• What is a "strategy" exactly? – MJD Mar 11 '15 at 20:56
• – DreamLighter Mar 11 '15 at 20:57
• So what you mean by a strategy is a table that tells the player, for each possible legal tic-tac-toe position, what move to make from that position, and you want to the number of possible tables? – MJD Mar 11 '15 at 20:59
• @MJD Yes, I am looking for the number of strategies. I do not need the table. One strategy can be Player 1 (assume he/she is X) playing X to the center and Player 2 plays O to the left corner and so on till ends. There are 9! possible strategies if the game does not end earlier. – DreamLighter Mar 11 '15 at 21:02
• I don't understand how that is one strategy. It seems to me you should be looking for two numbers: the number of first-player strategies and the number of second-player strategies. – MJD Mar 11 '15 at 21:03

Let's assume you mean pure strategies, ignore for the moment the fact that the game can end early, and not impose consistency on "transpositions"... i.e., let a player respond to a state differently depending on how it was arrived at. The first player has nine possible first moves, so he has $N_1=9$ pure strategies for his first move. The second player can respond in eight different ways, and the first player has seven possible responses to each of the eight situations he could find himself in on his second move. He can choose these responses independently, so he has $N_2=9\cdot 7^8$ pure strategies for his first two moves. He could find himself in any of $8\cdot 6=48$ situations on his third move, and can respond to each in five different ways, so he has $N_3=9\cdot 7^8 \cdot 5^{8\cdot 6}$ strategies for his first three moves. Continuing, we find $$N = 9\cdot 7^8 \cdot 5^{8\cdot 6}\cdot 3^{8\cdot 6\cdot 4}\approx 7.46\times 10^{132}$$ strategies for the first player for the entire game. The second player, on the other hand, has $$N'=8^9 \cdot 6^{9\cdot 7}\cdot 4^{9\cdot 7 \cdot 5}\cdot 2^{9\cdot 7 \cdot 5 \cdot 3}\approx 1.88\times 10^{531}$$ strategies. Both these numbers are exponentially larger than either the number of positions or the number of games (and would remain so even if consistency were enforced and early endings were handled) but this is as it should be. A strategy, after all, is a map from positions that you might see to moves that you would make in those positions. As such, the number of strategies should be something like a typical branching factor to the power of the number of reachable positions.
• I had the computer do the following calculation: Enumerate every possible position; at each position with X to move, take the number $N$ of legal moves for $X$ and add $\log_{10} N$ to an accumulator; I expected that the accumulator would total up to the log of the number of possible strategies for X. The accumulator totaled 25741.459607636, so I concluded there are $10^{25741.459607636}$ possible strategies for X, but this is very different from your estimate. Which of us has made a mistake? – MJD Mar 11 '15 at 21:18
• Oh, right! Very good, thanks. I will write up my work as a separate post, and link to the source code, later tonight. The corresponding number of strategies I found for O was $10^{38806.9270068241}$; if a strategy must include “a complete contingent plan, which includes every possible distinguishable circumstance” then it is the product of these, or $10^{64548.3866144601}$. – MJD Mar 11 '15 at 21:23