Coin Turning Games

Many impartial combinatorial games can be put into the category of coin turning games. Many coin turning games have rather complex descriptions and intuition. Obviously, we can't touch on every single coin turning game. So, for the sake of time, we will touch on some of the simpler games.

Before we get to specific games, here are some general rules to all coin turning games.

What is a Coin Turning Game?

• We are given a finite number of 'N' coins in a row

• Each coin shows either heads or tails

• A move consists of a player turning over coins from heads to tails or from tails to heads 

• The number of coins a player can turn over varies based on the particular game being played (we will primarily stick to games where 1 to 3 coins are being flipped)

• The set of coins that can be turned over depends solely on the position of the rightmost coin turned over

• The rightmost coin turned over must go from heads to tails (this guarantees that the game will end in a finite number of moves)

• The player to flip the last coin from heads to tails wins (when all coins are flipped to tails)


Okay...now that we have the rules down for these games, let's start by looking at a classic example of a coin turning game that will help us understand other games easier.

Turning Turtles

Note: we could turn turtles for this game but for the sake of the turtles' health it might be better to stick to turning over coins instead.

Rules:

• A player must turn over one of the coins from heads to tails

• That player also has the option to turn over a coin to the left of it (from heads to tails or from tails to heads)

For example, consider the following sequence of coins with N=10:

1 2 3 4 5 6 7 8 9 10
T H T T H H T T T H

Possible moves from this position:

• Turn one coin from heads to tails (for example, turn the coin in position 6 from heads to tails)

• Turn one coin from heads to tails and another coin from heads to tails to the left of it (for example, turn the coin in position 6 from heads to tails and then turn the coin in position 2 from heads to tails)

• Turn one coin from heads to tails and another coin from tails to heads to the left of it (for example, turn the coin in position 6 from heads to tails and then turn the coin in position 3 from tails to heads)

Using Nim

We have talked a little about how many of the games we will play this semester are just Nim in disguise. We will see that this game is just Nim in disguise if an H in position x is taken to represent a nim pile of x.

Now, we can use our three possible moves from Turning Turtles and think about how they are equivalent to moves in Nim. Any ideas? Write any guesses or thoughts on this in the comments section. I will also go over this in my presentation.

How does this relate to Nim-sums? Well, if we number the coins 1, 2, 3, ... from the left like in the example above, then the nim-value of a coin in position x is x if it is heads, and 0 if it is tails. The Nim-value of a specific coin setup is the Nim-sum of the Nim-values (so only the Nim-values of the heads because the Nim-values are 0 if it is tails).

Remember, this Nim-sum is just the binary representations of the number of coins in our piles, exclusive-ored together.

So how do we find a winning move from any given position? Just like in Nim, the only thing we want to do is reduce to a position where the Nim-sum is 0. In the above example, try to figure out the original Nim-sum. From there, figure out how you can get to a position with a Nim-sum of 0 so that you can always win assuming optimal play. Here is the table again:

1 2 3 4 5 6 7 8 9 10
T H T T H H T T T H

Feel free to post any answers or questions you might have about this in the comments.

Can't figure it out? Don't worry, I'll go over an example in class to help.

Okay, so let's incorporate Sprague-Grundy into here...

Connecting this to Sprague-Grundy

Using the rules of coin turning games, the same decomposition that we used in Turning Turtles also works for many other coin turning games. But how? Let's say we are in a position with k number of heads in positions x1, x2, ... xk. This position is the disjunctive sum of k games with exactly one head, where for j = 1, 2, ... k, the head in game j is at xj. Let's take the game THHTTH for example. This is simply the sum of the three games TH, TTH, and TTTTTH. So what does this say about Sprague-Grundy values? Well, in order to find the Sprague-Grundy value of a position, we only need to know the Sprague-Grundy values of positions with exactly one head. Therefore g(THHTTH) = g(TH) ⊕ g(TTH) ⊕ g(TTTTTH).

Let's look at a simple subtraction game so that we can apply these Sprague-Grundy values to coin turning games and get a better understanding of how they work.

Example Subtraction Game

• Sub{1,2,3}

• As a coin turning game, we number the coins 1, 2, 3, ... from the left like we have done above

• A coin in position x must be turned over from heads to tails

• A second coin must be turned over in one of the positions x-1, x-2, or x-3, except when x < 4, in which case a second coin doesn't need to be turned over.

Remember, even though we are in a position with k number of heads, we can think of this game as a disjunctive sum of k games with exactly one head in each game. We can now find the Sprague-Grundy values of each position much easier.

If we have a head in the 0 position, then that head can be turned over and can end the game...so the Sprague-Grundy value is 0 since our only option is to end the game. 

If we have a head in the 1 position, then that head can be turned to a head in the 0 position...so the Sprague-Grundy value is 1 since mex{0}=1.

If we have a head in the 2 position, then that heads can be turned to a head in the 1 position or to a head in the 0 position...so the Sprague-Grundy value is 2 since mex{0,1}=2.

If we have a head in the 3 position, then that heads can be turned to a head in the 2 position, a head in the 1 position, or to a head in the 0 position...so the Sprague-Grundy value is 3 since mex{0,1,2}=3.

Continuing this analysis, we can see that the Sprague-Grundy values look something like this:

x:      0    1     2     3     4     5     6     7     8     9     10

g(x):  0    1    2     3     0     1     2     3     0     1      2

As we have said before, if we can get to a position with a Sprague-Grundy value of 0 then we know we can win the game assuming optimal play.

Now, let's bring this analysis back to Turning Turtles.

Twins

We can apply this method to the game Turning Turtles which gives us the game Twins, which is also equivalent to Nim. In Turning Turtles we saw that we must turn over one coin from heads to tails and then have the option to turn over another coin to the left of it. In Twins, we must turn over one coin from heads to tails and then must turn over another coin to the left of it.

Can you guess what the Sprague-Grundy values are for this game?

Okay...so that's it for now. But what does all of this mean?

Conclusion

So it turns out that a lot of coin turning games are very similar to Nim, if not equivalent.

We can use methods from Nim as well as Sprague-Grundy values in order to find moves that will put us in a winning position.

There are way too many coin turning games that exist which makes it impossible to discuss all of them. I will leave it at this for now, but we can dig deeper into this broad subject.

We can also look at these games from a two-dimensional perspective which can get pretty complicated. However, this can lead to some pretty interesting findings on the extension of one-dimensional coin turning games, like the use of nim-multiplication. I probably will not be going into much detail on two-dimensional games for my presentation due to their complicated nature. However, this might be something to explore further for a final project as there are so many different variations of coin turning games.

Sources Used:

Ferguson, Thomas S. "Game Theory." Ferguson, T. S. (n.d.). Game Theory. Retrieved from http://myslu.stlawu.edu/~nkomarov/450/comb.pdf.


Guy, Richard K. "Impartial Games." http://library.msri.org/books/Book29/files/imp.pdf.


"Nim Game Example." Suhendry's Blog. April 14, 2012. Accessed January 31, 2017. http://www.suhendry.net/blog/?p=1612.


"Theory of Impartial Games." http://web.mit.edu/sp.268/www/nim.pdf.