# 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.

-
You've overcounted X's strategies. They don't need to have a second move prepared for situations their first move makes impossible. – Chris Eagle Sep 7 '11 at 15:44
@Chris, the way I've constructed the game tree of this game, that shouldn't be a problem. However I do feel that $2^{14}$ is way too high... Where do you think the problem lies? – Stijn Sep 7 '11 at 17:34

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.
Thanks for your answer. But why is the generalized statement I wrote in my question? That statement came out of another exercise which I tried to prove. Am I misinterpretting it wrong? Also, am I still correct in saying that player Y has 3 possible moves in round 2 and 1 possible moves in round 4, and therefore has $3^4\cdot 1^{24}$ possible pure strategies? – Stijn Sep 11 '11 at 11:03
@Stijn: I’m not comfortable commenting on the general statement, because I’m not sure how the author is defining information set. Y does have $3^4$ pure strategies: each one specifies what move he would make in response to each of X’s $4$ possible first moves, and of course he needn’t specify anything for his 2nd move, since it’s forced. – Brian M. Scott Sep 11 '11 at 21:49