Evanescent Thoughts

Evanescent Thoughts

Introduction and Analysis of a Simple Combinatorial Take-Away Game

with 5 comments


I have been reading on game theory and thought of posting some introduction so tht more ppl can start on these topics.

Combinatorial games are two-player games with an outcome (ie 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 misre play .In a normal play , the one who moves the game to the terminal position is the winner and in a misre 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 partizan game.An comman example of partizan 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 analyse 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 analyse 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 atleast one possible way so that we emerge the final winner.

If the game starts with P position , the second player to play wins beacause, 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 labelled P-position in one move as an N-position.
Step 3: Find those positions whose only moves are to labelled 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 recognised P positions .By using Step 1, { 1,3,4} are decided to be N positions and analysing 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 postions and analysing 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 genaralising 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 tht 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 tht the second player makes a suitable move and moves to 0 winning the game. If the Second player at any stage makes a un-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 atually 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 andTrofim. This problem helps us understand the above disucssed 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 belog 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 ie Nikofir wins always .

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

Stress on Optimal Play :
Why do we need to analyse 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.

The problem can be made more complex by imposing more constraints and by adding more piles. When the piles are added , it becomes a Simple Nim game which can be found here

Any suggestions or comments kindly leave comments below 🙂

Advertisements

Written by Sathya Narayanan

May 13, 2008 at 10:50 am

Posted in computers, Game Theory

5 Responses

Subscribe to comments with RSS.

  1. How about a proof for NGM based on invariants?
    The invariant would be: A player can always reach a multiple of 10 from any other number not a multiple of 10. which can be proved by induction.
    Though the argument for both the proofs will be the same..

    Akhil Ravidas

    May 13, 2008 at 11:36 am

  2. I’d just like to say that this was a great introduction to this kind of analysis! From knowing nothing about this I now feel that I could solve this kind of problem for any given S (possible moves), and I’ll be sure to look into more complex variations (with more piles or constraints)! Thanks a million 🙂

    Peter Pan

    April 28, 2009 at 2:52 am

  3. Is this the general method to solve all those simple take-away games?
    Is it always result in a sequence that will be periodical if apply a modulo n to it?
    If so, how to find n?
    Given a possible set of take-away moves, are there any algorithm to find the answer faster than this backward induction method?

    Mgccl

    May 8, 2009 at 9:12 am

  4. Hi! I was surfing and found your blog post… nice! I love your blog. 🙂 Cheers! Sandra. R.

    sandrar

    September 11, 2009 at 3:04 am

  5. Your post was really helpful!
    Can you give a hint regarding how to apply the same approach to the spoj problem http://www.spoj.com/problems/HUBULLU/
    Thanks 🙂

    Pawan Dhananjay

    November 1, 2015 at 5:49 am


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: