Impartial Games and How to Solve Them Part 3

Abstract: In this short post we apply the techniques learned in the previous two posts on impartial games and present solutions for a a few variations on the previously discussed subtraction games, mainly the addition of a take and break mechanic. We also present the more complicated impartial game, Kayles and its solution.

In the previous post on impartial games, we introduced two fundamental concepts to impartial game theory. That being the idea of a the Sprague-Grundy function and the Sprague-Grundy theorem, both of which can be reviewed here. As an important note, the term g-values can also be referred to as Nimber, Grundy-numbers or Grundy-values (which is where I derived g-values from), and is often referred to by that term in common literature. Recall, that in our last posts on this subject we discussed various forms of subtraction games, in which players take turns reducing the number of chips in a shared pile by a value in our subtraction set . With the winner of the game being the player who removed the last chip in the set.

We will now introduce a new type of game that is an extension of these subtraction games. This type of game is referred to as Take-and-Break games, which give the players another type of move, that being the take and break. In Take-and-Break games player, when allowed by the rules, can split one pile into two, which increases the number of piles.

One type of Take-and-Break game is Lasker’s Nim. In it players are given two options for move types. The first is to remove any number of chips from a single pile, as in a normal game of Nim. The second option is to split any pile with two or more chips into two non-empty piles. So how do we analyze this game?

The first and only terminal state is when their are no chips remaining. For shorthand we will right the game state in parenthesis like this – (0). Obviously this has a g-value of 0 (. Finding the g-value of (1) is also trivial, as we can only move to zero, thus . However, when dealing with a 2 sized pile we now get the option of splitting. With 2 chips we can go to the following positions, (0), (1), (1,1). We already know the g-values of (0) and (1), but what about (1,1). Well, from the Sprague-Grundy theorem we know that to find the g-values of a disjunctive sum of games we simply use the bitwise xor operator. Since (1,1) is just two individual instances of Lasker’s Nim with 1 chip, we can do the following to find its g-value: . So with the g-values of 2’s neighbor’s known, we can know find the g-value of (2), which is 2. The possible moves from (3) are 0, 1 , 2, (1, 2), with their g-values being 0, 1, 2, and respectively. Hence . If we continue with this we get the following values:

This pattern continues and we get the following equations: and for all . To prove this conjecture we can use the following inductive argument.

(1) All followers of , when dealing with a single pile, have Sprague-Grundy values from 0 to 4k. When splitting into two piles, we get the following possible piles . Looking at said piles, we see that both piles can only be split up such that they can be written as and or and . As per the inductive hypothesis, we can find said Grundy-values using the rules made earlier. With that in mind we find that the g-values for both pairs are either odd & odd, or even & even. When xoring those two, we will always get an even number, so all possible g-values from this operation are even. With that in mind, and knowing that values from are covered, the mex of the set will be , as such .

(2) Looking at all possible followers from , we can seen that all g-values from 0 to are already covered. When looking at possible two pile moves, we can break up the chips in the following ways: . Using the same analysis, we can see that all possible g-values are odd, or divisible by 4, thus the mex of this set is .

(3) For the followers of 4k+3 we see something a bit different. As usual, when reducing the chips we can reach any values from to . However, when looking at two pile moves, , we see that they all have odd g-values. Also importantly, . This means that we must go to the next highest value which is , thus .

(4) Finally, we look at the followers of . Because of the rule for , we see that single pile moves cover g-values from and . When looking at the possible two pile moves, , we see that the g-values are either even or equal to 1 (mod 4). Thus is not in the neighbor set, and .

Thus, we have proven the conjecture, and presented a solution for the game of Lasker’s Nim. In order to find if a winning move exists, we use the same strategy as we did for standard Nim. If the current g-value is equal to 0, it is a P-position, and our goal is to find such a position.

The second example game we will be looking at is the game of Kayles, invented by Henry Dudeney in 1908. The rules of Kayles are quite simple, given a row of pins, players take turns knocking out either one pin, or two adjacent pins. As we are studying games under the normal play convention, the winner is the player who knocks over the last pin. One could also formulate this as a subtraction Take-and-Break game where, and players may also split during the same move, making two nonempty piles.

When it comes to solving said game, it turns out to be rather trivial. The first player will always have a guaranteed win, whenever the row length is greater than 0. This can be achieved by breaking the row into two sections of equal length, and then simply imitating the second players moves in the opposite row.

However, finding the nimber of specific row lengths is a significantly more interesting question. Starting with our only terminal position we find that . A pile with only one chip must make an empty pile, so . A pile of two chips can either go to a pile with 1 or 0, so . When dealing with three chips, we can either get a pile with 1 or 2 chips, or two piles, both with 1 chip , so . We can continue to work through backwards induction, at which pointed we get the following table. Please note, this table is taken from [2] and the formatting of which, will be explained.

               g(x) 0  1  2  3  4  5  6  7  8  9 10 11 
                    ----------------------------------
                0+  0  1  2  3  1  4  3  2  1  4  2  6 
               12+  4  1  2  7  1  4  3  2  1  4  6  7
               24+  4  1  2  8  5  4  7  2  1  8  6  7
               36+  4  1  2  3  1  4  7  2  1  8  2  7
               48+  4  1  2  8  1  4  7  2  1  4  2  7
               60+  4  1  2  8  1  4  7  2  1  8  6  7
               72+  4  1  2  8  1  4  7  2  1  8  2  7

Each value of the table is written out as , where the rows are a, and the columns b. This is done to highlight the somewhat periodic nature of the games g-values. In fact, after , the games values do become periodic repeating ever 12 values. For looking into an algorithmic solution for Kayles, see this paper published by Bodlaender, Kratsch, and Timmer, [3].

Final Thoughts and Conclusions: With both of these examples, we have now shown how to utilize the Sprague-Grundy theorem for more complicated games. With this, we have completed are series on impartial games. With this series, we have shown the basics of impartial combinatorial game theory, given an explanation of the Sprague-Grundy theorem, and definition of nimbers/Grundy-values/g-values, and discussed how to find the best winning move for some of these games. Finally, we have given two more complex examples of impartial games that are used to highlight how the same analysis can be utilized in more complicated impartial games.

Citations:
[1] By User:RCraig09 – File:20200127 Bowling ball and pins for strike – front view.png with measurements erased, CC BY-SA 4.0,
[2] https://en.wikipedia.org/wiki/Kayles
[3] https://www.sciencedirect.com/science/article/pii/S0304397514007324
https://commons.wikimedia.org/w/index.php?curid=86383766 http://math450games.blogspot.com/2017/02/variants-of-nim-laskers-and-misere.html
http://myslu.stlawu.edu/~nkomarov/450/LIP-subgames.pdf
https://www.cs.cmu.edu/afs/cs/academic/class/15859-f01/www/notes/comb.pdf
https://web.mit.edu/sp.268/www/nim.pdf