Simple Take Away Game

Combinatorial games are two-player games with an outcome (i.e. it cannot end in a draw) and the players move alternatively from one position to other position depending on their move and finally reach a terminal position. When a player reaches the terminal position, the winner is decided based on the type of game play.

There are two types of game plays – normal play and the misère play .In a normal play , the one who moves the game to the terminal position is the winner and in a misère play , the one who moves the game to the terminal position is a loser.And if the rules of the game are same for both the players , then its a impartial game and when the rules are different for the two players , then its a partisan game.An common example of partisan game is a game of chess.

Take Away Game :

A take away game is a impartial combinatorial game where there is a single pile with n chips and players remove a certain number of chips from the pile depending on the rules of the game.Let us for the ease of analysis consider a normal play where the one who takes the game to the terminal position wins the game.

Consider a pile of n chips and say the rules of the game are given

• N={0,1,2,3,..,n} be the positions that the game can be and a 0 signifies a terminal position and a n signifies a starting position


• S={1,3,4} be the possible set of moves


• A player can take away ‘x’ chips from the current pile where x € {S}.

Say we need to analyze the game given n and S .By analysis what we mean is given n and S and assuming optimal play, who wins the game.To analyze the game we define two positions namely N position where the Next player to play wins and P position where the Previous player to have played wins.So a game ideally starts with either a P or a N position but always ends in a P position.

So we arrive at the following rules which can be recursively used to define the P and N positions.

1. All terminal positions are P positions in a normal play.


2. From an P position, any move takes us to a position.


3. From a N position, we can reach a P position in at least one possible way so that we emerge the final winner.

If the game starts with P position , the second player to play wins because, from P position the game can move to only to N position and the Second player wins by taking the game again to a P position according to the Rule 3 stated above(this is called playing optimally).
If the game starts with a N position , the current player wins the game by taking the game always to a P position.

So Let S be {1,3,4} for our analysis.
We use the following Algorithm to classify the P and N positions of {0,1,2,… n}.

• Step 1: Label every terminal position as a P-position.


• Step 2: Label every position that can reach a labeled P-position in one move as an N-position.


• Step 3: Find those positions whose only moves are to labeled N-positions; label such positions as P-positions.


• Step 4: If no new P-positions were found in step 3, stop; otherwise return to step 2

So we begin by adding ‘0′ to P position and let set P={0} denote the currently recognized P positions .By using Step 1, { 1,3,4} are decided to be N positions and analyzing the next number in the close proximity , we take ‘2′.

‘2′ has only one transition and its to a N position so 2 gets added to P and 1,3,4 gets added to N in this iteration. Now moving to the next iteration, 5(2+3) and 6(2+4) are N positions and analyzing for 7, we have the possible transitions as 6,4,3 which are all N positions and hence 7 gets added to P
hence at the end of second iteration, P={0,2,7} and N={1,3,4,5,6} . On continuing further, we get the following

P={0,2,7,9,14,16,21,23….} and N={1,3,4,5,6,8,10,11,12,13,15,17,18,19,20….}

So generalizing all positions which leave a remainder of 0 or 2 on dividing by 7 are P positions and others are N positions.

So say we have 21 chips then we are asked to comment on the winner assuming the optimal game play, we can conclude from the above derivations that 21 is a P position so the second player can win if he plays optimally . Say i start with 21 , the possible moves are 20,18,17 which are all N positions . Say we move to one of these

17 can move to 16,14,13 (14,16 are both P position)
18 can move to 17,15,14 (14 is a P position)
20 can move to 19,17,16 ( 16 is a P position)

For all the above cases , we observe that there is a possible transition that the second player can make such that the game proceeds to a P position and the cycle continues and finally the second player comes to a N position which could be either 1,3,4 so that the second player makes a suitable move and moves to 0 winning the game. If the Second player at any stage makes a non-optimal move , the game goes temporarily out of his control and he may or may-not win the game.

Another Example from SPOJ :

Let us analyze this Problem from SPOJ NGM which can actually be found here.

The problem states that a number n is taken and the player take turns and subtract the number by any one of its non zero digits.And the one who makes this number ‘0′ wins the game .The two players are Nikofir and Trofim. This problem helps us understand the above discussed concepts.

Analysis :

We start by adding 0 to P and 1,2,3,4,5,6,7,8,9 all lead to 0 directly hence are added to N . Now we analyze 10 which goes to 9 alone which is a N position and gets added to P . So at end of one iteration,

P={0,10) N=(1,2,3,4,5,6,7,8,9} .

Next the following numbers {11,12,13,14,15,16,17,18,19 }all have one possible move to {0,10} so they belong to N and the next P number is 20 proceeding we fins tht P is a set of multiples of 10

P={ x| x is a multiple of 10}

N={x | x is not a multiple of 10}

So given number which is not a multiple of 10 it is in N position and the player who plays first always wins i.e. Nikofir wins always .

If the given number is a multiple of 10 , then its in P position and Trofim wins.

Stress on Optimal Play :

Why do we need to analyze an optimal play? The need for all this analysis is to make the computer make the best move at the current position so that it poses a challenge to the player who plays and if the player gets lucky, he can take advantage of these analysis to make a winning move.