Tutorial for A Coin Game

In this tutorial, we will look at the solution of the problem A Coin Game from the September 2009 Challenge. Unless you are aware of the right kind of theory for this problem, it will probably seem to very hard due to the high constraints. So first let's have a short look at the theory needed to solve the problem.

Impartial Games

An impartial game is a two-player game where the players alternate making moves. The moves available to a player at any given time must be independent of whose turn it is. Players will alternate taking moves until they reach a terminal position, where one of the players is declared the winner.

Sprague-Grundy theorem

Impartial games can be analyzed using the Sprague-Grundy theorem. They key idea here is to define the Grundy number of a position p in the game. The Grundy number of a position p is defined recursively as follows. It is the smallest non-negative integer, r, such that no successor position has a Grundy number equal to r. By this definition if the position is terminal, then the Grundy number is 0. The successor positions of a position is the set of all positions that can be reached by making a single move from the current position. As an example, if we are currently in a position where we can make only one move, and the position we can move to is terminal, then the Grundy number of the current position is 1 (it is not 0, because we have a successor position whose Grundy number is 0). Here is pseudocode for computing the Grundy number of a position.

[code] grundy(p):
let s be a set of integers (initially empty)
for each successor position w of p: insert grundy(w) into s
ans = 0
while s contains ans: ans = ans+1
return ans [/code]

The Sprague-Grundy theorem allows us to solve so-called composite games. For impartial games, where it is the case that a player loses if he has no move available, the theorem tells us that a player loses iff the xor of the Grundy numbers of the position in each subgame is equal to 0.

To explain the concept of composite games and subgames, let's have a short look at the classic impartial game of Nim. Nim is played with a number of piles each containing some number of (not necessarily equal) stones. A turn of the game consists of removing any number of stones greater than 0 from any single pile. A subgame should in this case be considered to be a single pile since you can consider Nim with k piles to be a composite game consisting of k Nim games with one pile each. Notice that the subgames are independent in the sense that making a move in one of them does not change the position in any of the others.

The Sprague-Grundy theorem says that a player loses iff the xor of the Grundy number of the position in each subgame is 0. Now, in Nim with one pile the Grundy number of a position is very easy to calculate. It is simply the number of stones in the pile. You can prove this very easily by induction.

Since this introduction was necessarily brief, it would be a good idea to read the tutorial on Algorithm Games from TopCoder.

A Coin Game - The Silver Dollar Game - Bogus Nim

The key to solve this problem is to figure out how the game explained in the problem is actually a composite game. So we need to figure out what the subgames really are.

A first idea would be consider the number of squares between two neighboring coins to be a subgame. However, we will first insert a coin at position 0. By the rules in the game this coin cannot be moved. This will make it easier for us to deal with the first coin that is not at position 0. For instance, if we have coins at positions 0, 2, 5, and 8, then we would have a pile of size 2-0 = 2, one of size 5-2 = 3, and finally one of size 8-5 = 3.

These piles seem to somehow corresponds to piles in Nim. It is clear that whenever a player moves a coin (for instance by moving the coin at 5 to 3), he decreases a pile by the number of squares that he moves the coin. However, there is a slight problem with this decomposition into subgames. By moving a coin, we will also increase the size of another pile. For instance, if we move the coin at 5 to 3, then we decrease one pile by 2, but also increase a pile by 2. This decomposition does not really work, because subgames must by definition be independent. We should now be asking ourselves whether there is a way to make this idea work.

With the above ideas in mind, it would be a good idea to play around with the The Silver Dollar game before proceeding.

There was a problem with adjacent piles in the above decomposition into subgames. We can try to skip every other pile and define our subgames by this. So for example if we have coins at positions 0, 4, 10, 20 and 35, then we would have piles of size 4, 6, 10, 15, but now we will ignore every second one. So we have only the piles of size 4 and 10. Now, a move will either decrease the size of a pile, or it will increase the size of one pile. This is good because subgames are independent as we require them to be. For instance, if we move the coin at 4 to 2, we decrease the first pile by 2, and if move the coin at 10 to 7, we increase the second pile by 3. There is still a problem however because moving the coin at position 35 has no effect on any of the piles. This is not good because in some sense it allows a player to choose not to make a move, and this is not allowed by the rules of impartial games. We can fairly easily fix this problem by selecting the piles from the other end instead. So if we have piles of size 4, 6, 10 and 15 as before, we simply select our piles to be first pile from the end, and then skipping every other pile. In this case, we get the piles 15 and 6. This decomposition into independent subgames is now correct, and every move in the real game corresponds to a move in our subgame, and vice versa.

Now, we have been able to decompose the game into independent subgames, so we just need to figure out what the Grundy number of each position is, xor them and check if it equal to 0. If it is, we lose and otherwise we win.

So in our decomposition into subgames, a subgame is essentially just Nim, but we may also increase the size of a pile. We now argue that this type of move can be disregarded. If a player increases the size of a pile, we may make a move to immediately decrease the size of the pile again leaving the player in the exact same position as before he increased the pile. Hence the move is not useful. You may wonder whether the game terminates, but it is quite obvious from the rules of the problem statement that it does.

To recap the algorithm to solve the problem is to compute the difference between each coin starting from the last one, ignore every second, xor the numbers and output that the player to begin loses iff the xor is 0, and otherwise we output that the starting player wins. The complexity of determining the winner is O(N), where N is the number of coins in the input.

It may be fun to play the Silver Dollar Game while contemplating how the opponent actually chooses to counter all moves that increase pile size and otherwise makes a winning move if he is in a winning position. Using a solution to the problem it is also possible to beat the AI (assuming that you start in a winning position and make perfect moves).

Finding a winning move

As if it was not enough to figure out who won, we also had to determine a winning move for the starting player (given that this player is in fact in a winning position). Also, the problem statement puts some constraints on this winning move. We prefer a winning move moving the leftmost coin possible, and also we want the move that moves this coin as many squares to the left as possible.

Let's assume that we have piles of size s₁, s₂, s₃, ..., s_k, and also assume that we are in a winning position. This means that the xor of all these numbers is not 0. We wish to decrease or increase the size of a pile such that the xor becomes 0, because this will mean that successor position is losing. Assume we remove k (could be negative) stones from pile i, then then we can recompute the xor of all the position as follows. Assume the the xor of all the positions was r before, then it must be r XOR s_i XOR (s_i - k), and we require this to be 0. By simple properties of XOR, we can solve for k. We get that s_i - k = r XOR s_i, i.e. k = s_i - (r XOR s_i).

So for every possible pile, we now know that there is only one possible move that will allow us to put our opponent in a losing position. Furthermore for a given pile we can compute this move in constant time. Therefore we will simply go through every coin, compute the only possible winning move with this coin, test if the move is in fact valid in our game (for instance the move might require us to jump over other coins, which is not allowed), and report the move of the leftmost coin that has a valid move. Remember that moving some coins actually corresponds to increasing the size of a pile and others correspond to decreasing the size of a pile.

Conclusion

The main message to take away from this tutorial is the theory of impartial games, the Sprague-Grundy theorem, the idea of composite games and independent subgames. This is a fairly advanced topic, but it is one that most programming contest contestants should be familiar with, since it is not uncommon to find problems about this. For instance in the September 2009 Challenge, there were two problems involving impartial games, of which one was this and the other was A Bowling Game.