Number of pure strategies for each player in a simple game I've just started following a game theory course. I'm still getting used to the concepts so I hope I can get some comment on my thoughts. This is a homework exercise.

Consider a four square board. There are two players, players X and O. The game consists of four rounds. In round 1 and 3 player X writes a 'X' in one of the squares. In rounds 2 and 4 player Y writes a 'Y' in one of the squares. It is not allowed to write something in a square in which something has been written.
Determine the total number of possible pure strategies for each player.

I think I can calculate the answer by using a more general statement.

Suppose player $i$ has $N$ information sets. Denote by $M_n$ the number of possible actions player $i$ can take at information set $n$, $n = 1,\ldots,N$. Then the total number of possible pure strategies of player $i$ is $\prod_{n=1}^{N} M_n$.
My attempt at a proof: creating a pure strategy boils down to picking from each information set a possible action. Therefore the number of possible pure strategies is equal to the number of ways you can pick an action from information set 1 times the number of ways you can pick an action from information set 2, etcetera, up to information set N. In otherwords, it is equal to $\prod_{n=1}^{N} M_n$.

If this is correct, then the number of possible pure strategies for player X are $4\cdot 2^{12}$. For player Y, this would then be $3^4\cdot 1^{24}$.
Is this right? If not, where do I go wrong? Thanks in advance.
 A: Consider what a pure strategy for X will actually look like. It must have two components: it must specify X’s Round 1 move, and it must specify what X is to do in Round 3 for every possible response by Y in Round 2. The Round 1 component can obviously be chosen in $4$ ways. Suppose that it’s been chosen. Then Y’s $3$ possible responses are known, and a countermove must be specified for each of them. There are $2$ choices for each countermove, so the entire set of countermoves can be chosen in $2^3 = 8$ ways. In other words, for each choice of Round 1 move, X has $8$ possible strategies for Round 3, each covering every possible response by Y in Round 2. Since there are $4$ possible round 1 moves, X has altogether $4 \cdot 8 = 32$ pure strategies.
Here’s another way to see it. Number the cells of the board $1$ through $4$. A strategy for X can be specified as follows. First give the number of the cell in which X plays in Round 1. Then list remaining cells in numerical order. Finally, replace each of the three numbers in that list by $0$ or $1$; replacing number $c$ by $0$ means that if Y plays $c$ in Round 2, X will play in the lower-number of the remaining cells in Round 3, while replacing it by $1$ means that X will instead play in the higher-numbered of the two remaining cells. The strategy $3010$, for instance, means that X will play in cell $3$ in Round 1. If Y then plays in cell $1$, leaving cells $2$ and $4$ open, X will play in cell $2$, the lower-numbered one. If Y plays in cell $2$ in Round 2, leaving $1$ and $4$ open, X will play in $4$. And if Y plays in cell $4$ in Round 2, X will answer with cell $1$. Clearly every strategy for X can be uniquely specified in this way, and clearly there are $4 \cdot 2^3$ such specifications.
A: I'm a beginner myself, but I think the difference boils down to the fact that the generalized statement mentioned (and information sets concept) apply to imperfect information games, while the example given is one with perfect information because the players know the complete history of the game.
This means that the number of information sets at each move is a singleton. And thus, the number of pure strategies is the product of the number of moves at various points of the game, which for X is $4 \times 8 = 32$ (which is actually $4(1) \times 8(1) = 32$)(OP, the fault in your argument is  that the $12$ in the exponent of $2^{12}$ comes from $4\times3$ in round 1 and 2, but here you're recounting the $4$).
For Y, the number of singleton information sets is 4(each corresponding to round 1 of X) and for each set, has 3 moves of his own and thus the total number of strategies he can choose from is $3^4$(Think of each strategy as 4 consequent digits, the $i^{th}$ digit representing the move Y makes should X mark the cell $i$. Now see that there are 3 choices for each digit).
This link will describe the information sets better: http://lcm.csa.iisc.ernet.in/gametheory/ln/web-ncp2-efg.pdf
A: OP is correct.  
First, we define an information set: an informations set is a node or possibly collection of nodes at which a player makes a decision, and for which the player cannot distinguish between multiple nodes in the informations set.  Hence the player has the same available actions at each node in an information set.  An information set establishes all possible moves that could have taken place in the game until the point of the player's decision, given what the player has observed.  In the game of tic tac toe, every player knows exactly what moves have been played at every step in the game (perfect information) so every information set is a singleton.
Now we define a strategy: a strategy for a player is a map from all of the player's information sets to actions.  This includes information sets that the player would never even encounter by virtue of following their own strategy in the course of the game!  Player 1 had 4 actions to choose from at the first information set and after player 2 moves, there are 12 possible information sets player 1 could possibly be at before making a decision, and at each of these information sets, player 1 has 2 possible actions.  Hence, the total number of strategies for player 1 is given by 4*2^12.
The key point is strategies include off-path actions.  That is, even though once player 1 makes a move, he/she is effectively avoiding all subsequent information sets that would be encountered by playing any of the other three actions, a strategy must include a contingent plan for every information set the player has in the game.  More casually, you can think about it as a plan for everything in case somebody (including the player making the strategy) screws up somewhere along the way.
