Take-and-Break Games

Take-and-Break Games

    In my post, I will introduce a specific type of game called take-and-break games. For take-and-break games, there is not too much new stuff we have to learn and the crucial thing is to know the Sprague-Grundy Theorem. So thanks Sam! 

    "Take-and-Break" games are something like Nim. However, instead of viewing a Nim position as consisting of piles of matches, we view the position as consisting of rows of matches which can be broken into smaller rows.  Or we view a pile as capable of being divided into two smaller piles. So the rules of Take-and-Break games are to take and/or split one pile into two or more parts under certain conditions, thus, the number of piles will increase. There are many examples of Take-and-Break games, and I would like to concentrate on Lasker's Nim and The Game of Kayles in this post.

Lasker's Nim

    Emanuel Lasker, the world chess champion from 1894 to 1921, was the first one to generalize Nim into a Take-and-Break game. In this game, each player at his turn is allowed to do one of the followings:

             (1)remove any number of chips from one pile as in Nim, or 

             (2)split one pile containing at least two chips into two non-empty piles(no chips are removed)

and the last player to move wins.

    Recall that the Sprague-Grundy Theorem states that If g_i is the Sprague-Grundy function of G_i, i = 1,...,n, then G = G_1 + ··· + G_n has Sprague-Grundy function g(x_1,...,x_n) = g_1(x_1) ⊕···⊕ g_n(x_n). 

    Now let us find the Sprague-Grundy function for the one-pile game. Clearly that g(0)=0 and g(1)=1. For piles with 2 chips, you can remove either 1 or 2 chips, or to split the pile to (1,1). Thus, the follower of 2 are 0,1, and (1,1). with respective Sprague-Grundy values of 0,1, and 1⊕1=0. So g(2)=2. For piles with 3 chips, you can remove 1, 2, or 3 chips, or to split the pile to (1,2). So the follower of 3 are 0,1,2, and (1,2), with respective Sprague-Grundy values of 0,1,2, and 1⊕2=3. Hence, g(3)=4. If we continue in this manner, we will find that

    Therefore, we can conclude a conjecture that g(4k+1)=4k+1, g(4k+2)=4k+2, g(4k+3)=4k+4, and g(4k+4)=4k+3, for all k ≥ 0.

    We can use induction to easily verify the conjecture as follows:

        (a) The followers of 4k+1 that consist of a single pile have Sprague-Grundy values from 0 to 4k. For those that consist of two piles, (4k, 1), (4k-1, 2), ... , (2k+1, 2k), have even Sprague-Grundy values, so g(4k+1)=4k+1.

        (b) The followers of 4k+2 that consist of a single pile have Sprague-Grundy values from 0 to 4k+1. For those that consist of two piles, (4k+1, 1), (4k, 2), ... , (2k+1, 2k+1), have Sprague-Grundy values alternately divisible by 4 and even numbers, so g(4k+2)=4k+2.

        (c) The followers of 4k+3 that consist of a single pile have Sprague-Grundy values from 0 to 4k+2. For those that consist of two piles, (4k+2, 1), (4k+1, 2), ... , (2k+2, 2k+1), have even Sprague-Grundy values, so g(4k+3)=4k+4.

        (d) The followers of 4k+4 that consist of a single pile have Sprague-Grundy values from 0 to 4k+2, and 4k+4. For those that consist of two piles, (4k+3, 1), (4k+2, 2), ... , (2k+2, 2k+2), have Sprague-Grundy values alternately equal to 1 (mod 4) and even, so g(4k+4)=4k+3.

    Let us look at an example, suppose we are playing Lasker's Nim with three piles of 2, 5, and 7 chips. What is you move? Firstly, we should find the Sprague-Grundy value of the component to be 2, 5, and 8 respectively. The Nim-sum of the three numbers, 2⊕5⊕8=15. Since we want to have a Nim-sum of 0 to win the game, so we can split the pile of 7 chips into two piles say 2 and 5 chips. And at the next move, your opponent will be faced with a four pile game of Lasker's nim with 1, 2, 5 and 6 chips. This has Sprague-Grundy value of 0 and so is a P-position. Also, there is another way to split one pile and get to a P-position, can anyone figure that out?

                     

The Game of Kayles

    The Game of Kayles was introduced by Sam Loyd  and H. E. Dudeney in  about 1900. It basically says that two bowlers face a ling of 13 bowling pins in a row with the second pin already knocked down. In order to make this game easy to understand, let us think of this game as one of our graph games played with piles of chips whose rules can be described as: one may remove one or two chips from any pile, and if desired,  the pile may split into two nonempty piles after the move.
    So remove one chip from a pile without splitting the pile corresponds to knocking down the end pin of a line. Removing one chip with splitting the pile into two nonempty piles corresponds to knocking down a pin in the interior of the line. And it is similar for removing two chips.
   First, let us figure out the Sprague-Grundy function, g(x). Since the only terminal position is a pile with no chips, so g(0)=0. A pile with 1 chip can only be moved to an empty pile, so g(1)=1. A pile of 2 chips can be moved either to a pile of 1 or 0 chips, so g(2)=2. A pile of 3 chips can be moved to a pile of 2 or 1 chips or to split to 2 piles with 1 chip in each(SG-value=1⊕1=0), so g(3)=3. Continuing in this manner, we could find more of the Sprague-Grundy values in the following table.

    From the above table, for x=72 and later, the SG-values are periodic with period 12, so the values in the last line will repeat forever. However, there are 14 exceptions to the sequence of the last line are displayed in bold face type. The last exception is when x=70. Since we know all the SC-values, we can consider the game as solved.

Conclusion

  There are many other interesting take-and-break games that worth exploring and even considering doing a final project. The one that I am really interested in is called the Dawson's Chess. I spent some time understanding and playing around it, and I still find out there are parts that I am not comfortable with explaining them. So I will spend more time on the Dawson's Chess and I hope I can finally share it with you guys on Tuesday's class. 

Amber


Sources: Game Theory, Thomas S. Ferguson
              Winning Ways For Your Mathematical Plays, Volume 1, E.R. Berlekamp, J. H. Conway, R.K. Guy