Sums of Combinatorial Games

Sums of Combinatorial Games

Now that we know a little bit more about combinatorial games such as subtraction games, we can start looking into some more applications and games using nim-sum and the Sprague-Grundy Theorem. For example, we can start to form new games by combining multiple games. You can have many nim-pile subtraction games going on at once between two players. Players will play the subtraction games as usual, but will continue playing until all subtraction games have reached a terminal position, when there are no more moves to be made in any of the games. This is called the disjunctive sum of combinatorial games. These games will still be played in normal play, so the player to make the last move out of all the games combined will be the winner. The different games combined will not interact as each player must choose only one component to play in per turn.

                Here is an example of sums of subtraction games:

                Say we have three piles.

                One pile would have 10 chips with subtraction set S={1,2}

                The second pile would have 12 chips with subtraction set S = {1, 2, 3}

                The last pile has 13 chips with subtraction set S = {1, 2, 3, 4}

There are still only two players, but the first player might takes chips from the first pile while the second player could take chips from the second pile. The players would continue playing like this until each separate game within the disjunctive sum game were all at terminal positions. In this case, there are three terminal positions at 0 chips for each separate game. In order to analyze the sums of games further we need to learn a bit more about the Sprague-Grundy values of disjunctive sums and how we go about finding them.

The Sprague-Grundy Theorem

The Sprague-Grundy Theorem is also used to find the Sprague-Grundy function for a disjunctive sum of graph games as long as the Sprague-Grundy functions are known for the component games. The proof of this theorem is explained by Ferguson on page 22 of the reading. First, the disjunctive sum of games is denoted as the sum of all the graphs G1….Gn by G = G1 + G2 + …. + Gn for n amount of games or graphs that are being combined.

The theorem that is used is Theorem 2 of Sprague-Grundy which is pretty similar to Theorem 1 which Sam spoke briefly about the other day when he was presenting on Sprague-Grundy values. Here is a summary of how theorem 2 goes:

Theorem: If g_i is the Sprague-Grundy function of G_i, i=1,....n then G = G_1 + .... + G_2  has a Sprague-Grundy function g(x_1, ... x_n)=g_1(x_1) ⊕ ... ⊕ g_n(x_n).

Proof:

Basically, the proof shows two things for the function g(x_1,...x_n) when we let x=(x_1,...x_n) be an arbitrary point of X and we let b=g_1(x_1) ⊕ ... ⊕ g_n(x_n).

1)      For every non-negative integer a<b, there is a follower of any of the points in X that has a g-value of a.

2)      No follower of (x_1, .... x_n) has a g-value of b

I’ll explain the proof more in class when I present, but it’s important to know that the proof proves the above things. Ferguson ends the explanation of the proof by saying that the theorem implies that every progressively bounded impartial game is equivalent to some nim-pile. This means that it could be replaced by a nim-pile of similar size without changing the outcome of the game.

Applications of Sums

Ferguson listed three applications for sums of combinatorial games, and there are a lot of other ones too. I will only be going into depth of one of them- the sums of subtraction games. This is something that we have focused most on and are most familiar with, so I thought I would give an example of sums of subtraction games.

                Ferguson gave the example that G(m) is the one pile subtraction game with subtraction set S_m = {1,2,…,m} in which from 1 to m chips may be removed. Suppose we summed together three subtraction games. The three games are:

 m=3 and the pile has 9 chips

 m=5 and the pile has 10 chips

m=7 and the pile has 14 chips

The game we are playing is G(3) + G(5) + G(7) and the initial position is (9, 10, 14). In order to find the Sprague-Grundy value of the sum of games, we must first find the Sprague Grundy values of each individual game. For each game, the SG value is xmod(m+1). So for G(3) and initial position at 9, the value is 1. When the initial position is 10 for G(5), the SG value is 4. Then when the initial position is 14 for G(7), the SG value is 6. Then, by theorem 2, we know that the SG value for the sum of the subtraction games is the nim sum of each individual Sprague Grundy Value. In this case, the Sprague Grundy Value = 1 ⊕ 4 ⊕ 6 = 3. A couple of classes ago we proved that when the nim-sum is equal to 0, the person is in a p-position. So, we want to try to make a move that gives a nim-sum of 0 in order to put our opponent in a p-position. Ferguson gives us one optimal move which he says is removing one chip from the pile of 14 and which gives a Sprague-Grundy value of 5. He then says there is another optimal move. After playing around with the nim-sum of these values, I found that another optimal move would be to make the Sprague-Grundy value of 2 to the G(3) pile. We can make this happen by leaving 6 chips in the pile that initially had 9, so we do this by taking away 3 chips. Using theorem 2, can any of you find the optimal moves to put your opponent in a p-position in the first example that I gave at the beginning of the blog? I think that there are also two of them.

                There are many other applications that use the second Sprague-Grundy theorem and involve the disjunctive sums of combinatorial games. I think that many of these applications would be interesting to look further into for a potential final project if anyone was interested!