3
$\begingroup$

This question already has an answer here:

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.

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ What is a "strategy" exactly? $\endgroup$ – MJD Mar 11 '15 at 20:56
  • $\begingroup$ @MJD en.wikipedia.org/wiki/Strategy_(game_theory) $\endgroup$ – DreamLighter Mar 11 '15 at 20:57
  • $\begingroup$ 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? $\endgroup$ – MJD Mar 11 '15 at 20:59
  • $\begingroup$ @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. $\endgroup$ – DreamLighter Mar 11 '15 at 21:02
  • $\begingroup$ 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. $\endgroup$ – MJD Mar 11 '15 at 21:03
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Great answer, though I would pull out and strongly emphasize the definition of strategy in the last paragraph: a strategy is (in programming terms) a function that takes a position and returns a move, or (in mathematical terms) a function from the set of [legal] positions (for a player) to the set of legal moves from that position. $\endgroup$ – Steven Stadnicki Mar 11 '15 at 21:13
  • $\begingroup$ 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? $\endgroup$ – MJD Mar 11 '15 at 21:18
  • $\begingroup$ @StevenStadnicki: Absolutely, although I'm quibbling a little on the domain of that function... it doesn't need to contain all legal positions, just those that can be reached when applying the strategy. That's a much smaller number of positions. $\endgroup$ – mjqxxxx Mar 11 '15 at 21:20
  • $\begingroup$ @MJD: Same comment applies to you :). I'm treating two strategies as equivalent if they differ only on positions that can never be reached when applying either strategy. $\endgroup$ – mjqxxxx Mar 11 '15 at 21:23
  • $\begingroup$ 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}$. $\endgroup$ – MJD Mar 11 '15 at 21:23

Not the answer you're looking for? Browse other questions tagged or ask your own question.