3
$\begingroup$

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!

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

1 Answer 1

Reset to default
4
$\begingroup$

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.

$\endgroup$
5
  • $\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
    Commented Jul 9, 2016 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
    Commented Jul 9, 2016 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
    Commented Jul 9, 2016 at 15:47
  • $\begingroup$ OK. Understood. Thanks! $\endgroup$
    – richarddedekind
    Commented Jul 9, 2016 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
    Commented Jul 16, 2016 at 19:55

Not the answer you're looking for? Browse other questions tagged .