So, I have this problem for my homework in which I'm asked to show that the amount of strategies for player number 1 in tic-tac-toe is between

$$9*7^8*5^{48} \text{ and } 9*7^8*5^{48}*3^{192}$$ But I can't see why and I don't fully understand the answer provided in the following link: Tic-Tac-Toe Game.

As far as I know (from the Wikipedia definition of strategy), a strategy tells the player what to move for every situation in the game. So, my approach was to consider strategies as functions that map an information set (that represents a particular situation of the game) into an action. Then my problem is to count how many of such functions exist.

I can map the first information set to 9 possible values (in the first move all 9 cells are available). Then player number 2 makes his move. For each of the 9 moves of the first player there are 8 possible moves for player number 2. So, after 2 moves there are 72 possible situations (information sets). For any of those 72 situations player number 1 can take 7 actions, that is $7^{72}$. It's clear that if I continue reasoning this way I won't get the desired result but I don't see why my reasoning is wrong. Can you tell me where is my mistake, or if I'm missunderstanding the definition of strategy? Thanks in advance


Your mistake is that after the first move is made, the $9$ possibilties for that move should not be considered again as far as the strategies go in response to player two's countermove. That is, for each of the $9$ strategies relative to the first move, player $1$ only has to consider the strategies relative to each of the $8$ countermoves, and with $7$ possible strategies for each of the $8$ countermoves, that gives $9 \cdot 7^8$ strategies to cover the first three moves of the game.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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