Nim Game System

Application of Sprague–Grundy theorem(SG theorem)

Introduction

The project is the second assignment of Programming and Software Development(COMP90041) Semester 1, 2018. The main challenge of the project is how to implement a AI with victory guaranteed strategy in advanced Nim Game. Here I will briefly introduce how I apply SG theorm on this problem.

Advanced Nim Game

There are multiple variants of Nim Game. In this project, the advanced Nim Game is defined as following(cited from the instruction document):

The rules of the advanced Nim game are as follows. The major rule in this advanced Nim game is that a player is only allowed to remove 1 stone or 2 adjacent stones in each move. Here, adjacent stones are stones who are neighbors to each other. Hence, the upper bound of stones to be removed is always 2. However, the requirement on the adjacent stones makes the position of the stones matters, i.e., removing the same number of stones at different positions may produce different game states, while in the original Nim game stones are conceptually the same, i.e., removing the same number of stones always produces the same game states. For example, given 5 stones represented as < ∗∗∗∗∗ >,

• in the original Nim game removing 2 stones will always produce the state < ∗∗∗ >
• in the advanced Nim game, depending on which stones are removed, removing 2 stones produces multiple states. In the following example, note that state 2 differs from state 3 because in state 2 the first two remained stones cannot be removed in a single move since they are not adjacent while in state 3 the first two remained stones can be removed in a single move.

1. removing the first and the second, results to < ××∗∗∗ >
2. removing the second the third, results to < ∗××∗∗ >
3. removing the third and the fourth, results to < ∗∗××∗ >
4. removing the fourth and the fifth, results to < ∗∗∗×× >

Similar to the original Nim game, each player takes turns to remove either one stone or two adjacent stones. A player wins if he / she removed the last stone.

Game Strutuce

The advanced Nim Game has only one paremeter: the number of stones. we call an advanced game with n stones AdvanceNim(n). So our goal is to find the win strategy of AdvanceNim(n).

We can easily find that if a move is make on AdvanceNim(n), the game will become the sum game of AdvanceNim(x) and AdvanceNim(y) which satisfy

x+y = n-1(if the move removed 1 stone)

or

x+y = n-2(if the move removed 2 stones)

According to the property of SG function, namely a state s with two sub games AdvanceNim(a) and AdvanceNim(b),

SG(s) = SG(AdvanceNim(a)) xor SG(AdvanceNim(b))

we can derive

SG(AdvanceNim(n)) = mex(SG(AdvanceNim(x)) xor SG(AdvanNim(y))|for all non-negative pairs(x,y) that x+y=n-1 or x+y=n-2)

(You can find the definition of xor here and mex here.)

According to the equation above, we can calculate the SG function of the current state recursively and judge if a win-guaranteed strategy exists in this state. Of course, to improve the efficency, we can first calculate a table of SG(n) and then just use the value accordingly.

For example, if now there are three sub-games AdvanceNim(4), AdvanceNim(6) and AdvanceNim(3), the SG function of the state is

SG(*) = SG(AdvanceNim(4)) xor SG(AdvanceNim(6)) xor SG(AdvanceNim(3))

If the SG function is zero then there is no win-guaranteed strategy while if SG function is non-zero there should exist a win-guaranteed strategy. The next move can be found by traversing all successors and those moves make the SG function of successor zero can be picked.

The JAVA implementation of above algorithm can be found here.