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!


closed as unclear what you're asking by ml0105, Claude Leibovici, Zain Patel, user1551, JMP Jul 12 '16 at 9:29

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Possible duplicate of game combinations of tic-tac-toe $\endgroup$ – lulu Jul 5 '16 at 0:14
  • 2
    $\begingroup$ 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. $\endgroup$ – lulu Jul 5 '16 at 0:15
  • $\begingroup$ No, this is the number of games you can play, not the number I want. $\endgroup$ – richarddedekind Jul 5 '16 at 0:15
  • $\begingroup$ Then I don't know what you mean by "strategic set". $\endgroup$ – lulu Jul 5 '16 at 0:16
  • 1
    $\begingroup$ 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. $\endgroup$ – lulu Jul 5 '16 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.

  • $\begingroup$ 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$. $\endgroup$ – richarddedekind Jul 9 '16 at 15:37
  • 1
    $\begingroup$ @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. $\endgroup$ – Xoff Jul 9 '16 at 15:44
  • 1
    $\begingroup$ @LivaditisAlex in fact a strategy doesn't need to define what to do if you did not apply the strategy. $\endgroup$ – Xoff Jul 9 '16 at 15:47
  • $\begingroup$ OK. Understood. Thanks! $\endgroup$ – richarddedekind Jul 9 '16 at 16:25
  • 1
    $\begingroup$ @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. $\endgroup$ – Sergio Parreiras Jul 16 '16 at 19:55

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