# Strategy set in Tic-Tac-Toe [closed]

I read in a book that the cardinality of the strategy set of the first player in a game of Tic-Tac-Toe is approximately equal to $10^{126}$ but I cannot see how to arrive at this result.

Disclaimer: I don' t want to calculate how many sub-games there are!

• Possible duplicate of game combinations of tic-tac-toe
– lulu
Commented Jul 5, 2016 at 0:14
• Note: the number you give is absurdly high. There are $9$ possible moves all in all and no game can last longer than $9$ moves, so $9^9$ is already absurdly high.
– lulu
Commented Jul 5, 2016 at 0:15
• No, this is the number of games you can play, not the number I want. Commented Jul 5, 2016 at 0:15
• Then I don't know what you mean by "strategic set".
– lulu
Commented Jul 5, 2016 at 0:16
• I'll retract the close vote. You want a dictionary of all possible first moves, then all possible responses to second moves and so on. Very path dependent. Number might grow pretty high.
– lulu
Commented Jul 5, 2016 at 0:19

A strategy is a function defined from all possible positions to all possibles moves you can make from that position.

Note that there are $3^9$ positions in this game (at most) and 9 possibles moves at most there are at most $9^{3^9}$ possible such functions.

Of course much less because you can only consider the positions before you have to play that you can reach after previously applying the strategy so it's more like

$$9\times 7^{8}\times 5^{8\times 6}\times 3^{8\times 6\times 4}\times 1\approx 10^{132}$$

A little bit less because some games will end before filling the board.

• I have a question. At the second move of the first player there are $8\times 9$ possible positions so why it isn' t $7^{8\times 9}$? The same question goes to exponents of $5$ and $3$. Commented Jul 9, 2016 at 15:37
• @LivaditisAlex because the strategy choose (always the same one for a given strategy) a possible position at first move, so there are indeed only 8 possible positions at the second move.
– Xoff
Commented Jul 9, 2016 at 15:44
• @LivaditisAlex in fact a strategy doesn't need to define what to do if you did not apply the strategy.
– Xoff
Commented Jul 9, 2016 at 15:47
• OK. Understood. Thanks! Commented Jul 9, 2016 at 16:25
• @LivaditisAlex: You are correct: For subgame perfect Nash equilibrium (Selten won a Nobel Prize for it), a strategy needs to specify what the player does in all subgames including those subgames that would never be reached if the player followed the strategy in the first place. Commented Jul 16, 2016 at 19:55