Impartial games problems

Again with a new problem, but this time i will explain a very nice approach to solve a specific set of problems located under the category of game theory.

Impartial games

In combinatorial game theory, an impartial game is a game in which the allowable moves depend only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric. In other words, the only difference between player 1 and player 2 is that player 1 goes first.

Impartial games include Nim, Sprouts, Kayles, Quarto, Cram, Chomp, and poset games. I will explain the nim problem and how to solve it, then i will move to the Stone Piles problem that i solved this week.

 

Nim Problem

Nim is a game in which two players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object, and no more than a set maximum number from the heap.

An example normal play game is shown below:

A B C
3 4 5 I take 2 from A
1 4 5 You take 3 from C
1 4 2 I take 1 from B
1 3 2 You take 1 from B
1 2 2 I take entire A heap leaving two 2’s.
0 2 2 You take 1 from B
0 1 2 I take 1 from C leaving two 1’s.
0 1 1 You take 1 from B
0 0 1 I take entire C heap and win.

What is your winning strategy? 

Luckily, we can find one. Nim has been solved for all starting positions and for any number of heaps. First we’ll look at different types of game positions, then we’ll do some work with “nimbers” (yes, that really is a word) and then apply them to finding a solution to Nim.

Types of impartial game positions

• A game is in a P-position if it secures a win for the Previous player (the one who just moved).
• A game is in a N-position if it secures a win for the Next player.

So in normal play Nim with three heaps, (0,0,1) is an N-position and (1,1,0) is a P-position. We call the position from which no possible moves are left a terminal position. To find whether a Nim position is N or P, we work backwards from the end of the game to the beginning in a process called backwards induction:

1. Label every terminal position as P.
2. Label every position that can reach a P position as N.
3. For positions that only move to N positions, label P.
4. At this point either all positions are labeled or return to step 2 and repeat the process until all positions are labeled.

Applying these rules to Nim, we first set the only terminal position (in other games there could be many) 0,0,0, to P. It is obvious that any position (0,0,n) is an N position, since the next player can just take the last heap in one turn.

Nimber arithmatic

The key operation in the solution to Nim is binary addition without carrying. To add two numbers in this manner, first write out their binary expansions, and then take the exclusive or (XOR) of the two numbers bit by bit.

Theorem 1. A position, (x1, x2, x3), in Nim is a P-position if and only if the nim-sum of its components is zero, x1 ⊕ x2 ⊕ x3 = 0. As an example, take the position (x1, x2, x3) = (13, 12, 8). Is this a P-position? If not, what is a winning move? We compute the nim-sum of 13, 12 and 8:
 

13 = 11012
12 = 11002
8 = 10002
nim-sum = 10012 = 9
 

Since the nim-sum is not zero, this is an N-position according to Theorem 1. Can you find a winning move? You must find a move to a P-position, that is, to a position with an even number of 1’s in each column. One such move is to take away 9 chips from the pile of 13, leaving 4 there. The resulting position has nim-sum zero:

4 = 1002
12 = 11002
8 = 10002
nim-sum = 00002 = 0

Another winning move is to subtract 7 chips from the pile of 12, leaving 5. Check it out.

Now we can solve the Nim game with any number of piles.

Stone Piles problem

This is a much harder problem in which we are going to move to another theorem called Sprague Grundy theorem, in which will help us solving this problem.

You can view this problem at interviewstreet.com using this link. However in this problem the game described as below:

There are N piles of stones where the ith pile has x_i stones in it. Alice and Bob play the following game:

• a. Alice starts, and they alternate turns.

• b. In a turn, a player can choose any one of the piles of stones and divide the stones in it into any number of unequal piles such that no two of the piles you create should have the same number of stones. For example, if there 8 stones in a pile, it can be divided into one of these set of piles: (1,2,5), (1,3,4), (1,7), (2,6) or (3,5). 

• c. The player who cannot make a move (because all the remaining piles are indivisible) loses the game.

Given the starting set of piles, who wins the game assuming both players play optimally?

Sprague Grundy Theorem

Definition: A directed graph G(X,F) Where A directed graph, G, is a pair (X,F) where X is a nonempty set of vertices (positions) and F is a function that gives for each x ∈ X  a subset of X, where each of them is a position reachable from x.

The Sprague-Grundy function of a graph, (X,F), is a function, g, defined on X and taking non-negative integer values, such that g(x) =min{n ≥ 0 : n = g(y) for y ∈ F(x)}.

In words, g(x) the smallest non-negative integer not found among the Sprague-Grundy values of the followers of x. If we define the minimal excludant, or mex, of a set of non-negative integers as the smallest non-negative integer not in the set, then we may write simply g(x) =mex{g(y) : y ∈ F(x)}.

Mex means Minimum Excluded Value. Below are some practice examples:

mex({2,4,5,6}) = 0
mex({0,1,2,6}) = 3

Now how to solve the stone piles game?

1. Mark all terminal nodes sg = 0 (In this case its 1 and 2 as the player will not be able to divide them)

2. For each pile compute the sg value of it

3. Get the nim-sum of all the sg values of the piles, if 0 then BOB wins, else ALICE wins.

How to get the sg value of a number?

1. DFS all the possible divisions of this pile

2. Recursively compue the sg values of all the possible divisions

3. Return the mex out of them

Now i am done explaining the whole topic, i think its really interesting and i suggest you solving more problems as i will do isA.