Game Theory: Generalize the Take-Away Game


Posted by 5 years ago
426.1k points

Suppose in a game with a pile containing a large number of chips, you can remove any number from 1 to 6 chips at each turn. What is the winning strategy? What are the P-positions? If there are initially 31 chips in the pile, what is your winning move, if any?[1]

In the Take-Away game the winner is the last one to draw chips from the pile. We draw chips in such a way as to put the other player in a P-position, which is a winning position. All other positions are known as N-positions. Proceeding in this manner and using the principle of backward induction it is easy to see that

$$P={0,7,14,21,\ldots}$$

and the N-positions are the complement of this set i.e.,

$$N={1,2,3,4,5,6,8,9,10,11,12,13,\ldots}$$

The winning strategy is then to make a move in such a way as to arrive in a P-position. Therefore the P-positions are,

$$x \equiv 0 \text{ (mod 7)}$$

If there are 31 chips in the pile then 0, 7, 14, 21, 28 are all P-positions. The winning first move will be taking 3 chips from the pile. This will make it impossible for your opponent to win since you will always be able to arrive in a P-position subsequently.

[1]: Game Theory. 2014. (2nd Ed). Thomas S. Ferguson. UCLA Mathematics Department