Take-and-Break Games

Take-and-Break Games 🙊

The Basics 🙆

Take-and-Break Games are impartial, combinatorial games where the rules allow splitting one pile into two or more parts under certain conditions, thus increasing the number of piles. These "mini games", or piles are then disjunctive.

The type of Take-and-Break game that I am going to focus on is called Dawson's Chess! The game is basically chess with just pawns on a 3 x n board. If you don't know how the pawns move on a chess board, here is a visualization.

                                                                                     https://www.flickr.com/photos/kevinbyrom/5023239218

Pawns can only move forward one square at a time. However, when attacking an opponent the pawns can move diagonally to take over the opposing pawn's spot. So, on that 3 x n board, imagine all white pawns on the bottom row and all black pawns on the top row.

Now before I go any further, you might be thinking "Wait just a minute Greg..... chess isn't impartial." You're right! Chess is not impartial because the two players can only touch his or her respective pieces. Try and think how this specific set up (Dawson's Chess) allows for each player to have equal opportunities to make all the same moves.

Have some fun with this online version below ↓ and conjure up a hypothesis

Dawson's Chess online: Math 450 vs. Computer

What did you hypothesize? Let me know in the comments section below!

What is happening here to make Dawson's Chess impartial is this:

On this 3 x 3 game of chess with just pawns we see that since black moved first he was able to make the board come to a stale mate, meaning no more moves can be made. So as you saw on the Dawson's Chess online, this is exactly what's happening! Once you make a move you mark the square with an "X" and therefore the two adjacent squares are marked with "O's" to mark them as unusable. So obviously you would't play Dawson's Chess on a 3x3 board like this because the first person who moves wins! Dawson's Chess can be played on any size 3 x n board and the player who moves last wins! Normal play! :) And there you have it! Dawson's Chess.

The Math Behind Winning 📘

For this game, we will be using a lot of the wording and material from previous presentations such as Nim sums, the Sprauge-Grundy theorem, P-positions, N-Positions, Grundy Tables, mex and so on. So make sure you are brushing up on these topics and have them down pat.

So how do we calculate n and g(n) for a game? I think it's helpful if we think of Dawson's Chess as a game of knocking down bowling pins that are aligned in a long row. (Similar to another take-and-break game called Kayles. Except with Kayles, there are different bounds of play in which the players can operate.)

Rules for Dawson's Chess:

1. For a single move, knocking down one pin means knocking down the two adjacent pins, or one adjacent pin if you knock the pin on the end.
2. Players are skillful and cannot miss or knock down too many pins.
3. The player unable to move because of a lack of pins loses.

Formula To Calculate the Nim-value 💯

g(n)= mex( g(remaining pins after 1st potential legal move),  g(remaining pin after 2nd potential legal move),...... nim-sum of the SG-values of any disjunctive sets).

Small example: Game of 5 squares, or pins, where n is the number of pins

n	0	1	2	3	4	5
g(n)	0	1	1	2	0	3

Wait how did you get g(x)? Good question. Lets do an example.

g(5) =?

Step 1.
Possible moves are: 3 pins left, 2 pins left, 1 + 1 pins left if you hit the middle pin

Step 2.
g(5) =  mex( g(3), g(2), and g(1) ⊕ g(1)). 

        =  mex( 2, 1, 0) = 3
So,

g(5) = 3. 

Don't feel like doing all of the Nim-values by hand?

Well, we can use our Grundy Scale to help us out! Let's do an example of finding g(6). 












g(6) = ?

g(a)     = 0 0 1 1 2 0
g(b)     = 0 2 1 1 0 0
g(a⊕b) = 0 2 0 0 2 0
mex(g(a⊕b)) = 1 

Therefore, g(6) = 1 🔑

How To Win 🔮

Okay so lets talk about the magic behind winning a game of Dawson's Chess. We want to force our opponent into a P-position every time we move. That means, every move we have to progressively make a move that will make our opponent end up in a P-position (Nim-value of zero). When the game is split into a disjunctive sum of several smaller games, that's where the Sprague-Grundy theorem comes in! These disjunctive sums of three smaller games can be called G1, G2, G3...Gk with some associated positions or number of pins x, y and z. Then, if g is the SG-function for the big game, and g1, g2, g3 are the respective SG-functions for those three smaller games, the SG theorem tells us

g(x,y,z) = g1(x) ⊕ g2(y) ⊕ g3(z)

This equation helps us determine whether or not our move within each smaller game will be a zero, or P-position.

Lets play an example game of 11 squares. 

To pick our first move so that our opponent is in a P-position, what do we do? Can you tell me in the comments section?

Step 1.

List all possible moves from a row of 11:

Leaves rows of 9, 8, 7 and 1, 6 and 2, 5 and 3, or 4 and 4.

Any of these moves leave a P-position?

Lets find out:

Step 2. 

Find out if and move n is a P-position by using the above table. 

n= 9 g(n) = 3 P-position? No. So we won't make that move of knocking down two off of the end. 

n= 8 g(n) = 0 P-position? Yes! 0 is always a P-position. 

Step 3. 

After every move you and your opponent makes, you must repeat step 2 and you will eventually win! 

Okay, so lets complete this game. So, I just decided that I wanted n to equal 8, so I'm going to make my move. 

My first move is: 





My opponents arbitrary move is:

And so for my next move, I'll have to run through the steps again.

Step 1.

My potential moves include: 3 pins remaining, 2 pins remaining or 1 and 1 split pins remaining. 
Since from a previous example we know that g(1) ⊕ g(1) = 0. We can move into that position, leaving our opponent in a P-position. 

My next move: 





And from here we know that we are going to win! There are only two moves left and our opponent is in a P-position right now!! So EXCITING! 😄

WE WIN!

How is it like Nim?

Take-and-Break games are similar to Nim. However, instead of viewing a Nim position as of piles of paperclips, the positions can be viewed as rows of paperclips. These rows can then be broken into smaller rows. It would be like if the rules of Nim allowed us to break the piles into even smaller piles. 

Conclusion

One of the neat things that Jack will like is that the Nim-values have a period of 34! There are a few exceptional numbers that ruin the periodicity in a large chart of hundreds of Nim-values. But, other than that, there is a proven periodicity.

I really enjoyed working with these take-and-break games and I hope you guys enjoyed my post! Please feel free to leave a comment and let me know what you guys think. See you Tuesday!



Citations: 

Citations for Math 450 – Taking and Breaking Games

Berlekamp, Elwyn R., John H. Conway, and Richard K. Guy. Winning ways, for your mathematical plays. London: Academic Press, 1982.

Ferguson, Thomas S., F. Thomas Bruss, and Le Cam Lucien M. Game theory, optimal stopping, probability and statistics: papers in honor of Thomas S. Ferguson. Beachwood, OH: Institute of Mathematical Statistics, 2000.

"Dawson's Chess." Dawson's Chess. Accessed February 05, 2017. http://www.math.ucla.edu/~tom/Games/dawson.html.

"Take and Break Games." Take and Break Games. Accessed February 05, 2017. http://lincoln.sjfc.edu/~gwildenberg/games-course/take_and_break2.html.

¡Periodicity!

First things first.  In order to understand what Periodicity is all about, and how it is useful to us as gamers, we will have to touch back on Sprague-Grundy Values for a sec. 

Sprague, Grundy, and Their Numbers

 Lets go through an example.


       [An example]  

 
This is a graph that I am borrowing from Thomas S. Ferguson's Game Theory, Pg. 16.  Each vertex on this graph is a possible position for a player to be in throughout this  theoretical game.   

                                 

                                   

As you can see, each vertex is assigned a value (values 0, 1, and 2 seen here).  These values are in fact Sprague-Grundy Values.   How did Tom assign these SG Values to each vertex?  Well we have already seen how this unfolds thanks to Nevin, but lets do it again for the sake of review.  

1. First we need to know that a terminal position is a position where the game is over.  There are 4 terminal positions on the graph above (3 on the left, 1 on the bottom right). 

               
2. The Sprague - Grundy Value of a terminal position = 0.  Which is why each terminal position above is labeled with a 0.  ¡HOWEVER!  There are a bunch of vertices with a 0 SG Value assigned to them, but they are not terminal positions?  So...what the Farve? 🏈         We'll get to that. 

         
3.  The Mex or Minimum Exclusive of a set = The smallest non-negative integer that is not in the set.  AKA  any number x not in the set, such that x ≥ 0.  

With those three properties, we can now deduce this graph and how each SG-Value is  assigned.  Lets look at vertices a, b, and c.   

     Vertex 'a' :  We have to pay attention to the out-neighbors of each vertex.   Vertex a only                                         has 1 out-neighbor.  And that out-neighbor is a terminal position.  In order to                                         find out what the SG Value of a is, we need to determine the set of each SG                                         Value, of each possible position vertex a could move to.   Since vertex a can                                         only move to a single other vertex, the set of possible positions for a to move                                          to is going to contain only 1 SG Value.  And as said before, that position is a                                          terminal position, implying that the single SG Value contained in the set of                                             possible new positions for a is just {0}.   So to apprehend the SG Value of                                             vertex a with that information.  All we are to do is take the Mex of that set.  In                                          this case the Mex = 1.  Hence, the SG Value for vertex a is 1.      Yew!

     Vertex 'b' :   Now, vertex b has two out-neighbors.  One to its right (another terminal                                                  position with SG Value 0), and one to its left (vertex a with an SG Value of 1).                                        Therefore, the set of SG Values of possible positions for vertex b to move to is                                       {0, 1}.  The Mex of set {0, 1} = 2.  Hence, the SG Value for vertex b is 2!  

     Vertex 'c' : 🏈  Vertex c only has 1 out-neighbor.   So its set of possible SG Values to move                                           to is just {1} from vertex a.  Thus, the Mex of set {1} = 0.  Indicating that                                                 vertex c has an SG Value of 0.  

 So there is my review of Sprague-Grundy Values and how you apprehend them.                                  Hopefully it was clear, please let me know if not...or if I am wrong, that would also be                          good.  But to finish, I want to say that the most important part in finding SG-Values is                          being able to work recursively (work backwards).  Find the terminal positions, and get                        going from there.   Now to let the periodicity ensue.   

Questions Asked/Questions Answered

What is Periodicity?
I am glad you asked.   Google states that it is - The tendency to recur at intervals - and they are           not wrong.    In fact...they're right.

To provide some examples of different types of numeric periods.  We have:

        1231451671 

        1123123123 

        1122334455 

        0123252729 

        0120120120 

        1112233445 

Why does Periodicity matter?

Simply put.  Periodicity is one of the keys to understanding combinatorial games.   You are also able to quickly determine N and P positions if you know what the period of a game looks like.  

What Do Sprague and Grundy have to do with it?

Sprague-Grundy Values are the best way in finding the period of each combinatorial game you play.
You can also use a "Grundy Scale" to quickly determine the period of a subtraction game by hand.  I will explain what a Grundy scale is in class on Thursday.  If you are so inclined, feel free to look it up prior to my presentation.  

      [An Example]

Take Tuesday's class.  Much like a Nim-Sum of 0, we found out in Tuesday's class that a position where the Sprague - Grundy Value is 0, will always be a P - position.

At the end of our discussion Dr. Komarov provided us with:

                  G1 = sub{1, 2}, with a starting number of 10  (one out of the 3 games)

Here is the table of Sprague - Grundy Values we drew out for G1

        

                  G1 = sub {1, 2}    PERIODIC                      x 0 1  2  3  4  5  6 7  8 9 10

                                                                                 g(x) 0 1 2  0 1  2 0 1 2 0 1

   

By starting at the terminal position {0}, we can work recursively in order to attain all of the SG-Values for the rest of the possible moves.  Thus allowing us to analyze the game further, and use the SG-Values of 0 to place ourselves in P - Positions.    

Nim-Sequences

The Periodic order of the SG-Values are also referred to as a Nim-Sequence.  This is because you can use the SG Values to calculate Nim-Sums, and move the game to N and P positions.  


         [An Example]

Take G1 from Tuesday's class above.

                        G1 = sub {1, 2}    PERIODIC                        x 0 1  2  3  4  5  6 7  8 9 10
                                                                                         g(x) 0 1 2  0 1  2 0 1 2 0 1                              
And take G3 from Tuesday's class as well (should be in your notes).

                        G3 = sub {2, 3}   PERIODIC                         x  0  1  2  3  4  5  6  7  8  9  10
                                                                                          g(x) 0  0  1  1  2  0  0  1  1  2  0

If we start with 10 pieces in G1, and 6 pieces in G3 (10, 6), how can we move the game to a P-Position?  Aka when the Nim Sum of both games is 0.
 
Using the SG-Values, we currently have a Nim Sum of...
                             
                                G1 = 10 = SGV: 1 =   0001
                                G3 =  6  = SGV: 0 =   0000  =  1  *N-Position*
                                                                   0001

To move to a P-Position, we will have to find a place where the SG-Values of both games Nim-Sum up to 0.  By looking at the games, we can see that subtracting 1 from G1 will bring us down to 9.  Thus Providing us with a Nim-Sum of 0, and moving the game to a P-Position.           Yew!

                                G1 =  9  = SGV: 0 =   0000
                                G3 =  6  = SGV: 0 =   0000  =  0  *P-Position*
                                                                   0000

You would then continue the game as such in order to win.  Or loose.  Whatever floats                         your boat.

Every Finite Subtraction Game Is Periodic

Claim:  The Nim-Sequences of finite subtraction games are periodic.  

Proof:  Base Case

            1.  Consider the finite subtraction game sub(a1, a2, . . . , ak) and its Nim-Sequence (of SG -                        Values). 

            2.  From any position there are at most k legal moves. 

            3. So, using G(n) ≤ k for all n. Define a = max{ai}. 

            4. Since G(n) ≤ k for all n there are only finitely many possible blocks of a consecutive values                 that can arise in the Nim-Sequence. 

            5. So we can find positive integers q and r with a ≤ q < r such that the a values in the nim-                       sequence immediately preceding q are the same as those immediately preceding r. 

             

         Then G(q) = G(r) since G(q) = mex{G(q − ai) | 1 ≤ i ≤ k} = mex{G(r − ai) | 1 ≤ i ≤ k} = G(r). 

  

            

             Inductive Step

             1. For such q and r and all t ≥ 0, G(q + t) = G(r + t).

             2. Set l = q and p = r − q and we see that the above says that for all n ≥ l, G(n + p) = G(n)

                         Hence, the Nim-Sequence is periodic.

  

Conclusion

Periodicity is essential to understanding combinatorial games.  It can help you determine N and P positions, and allow you to measure each move made by you or your opponent!  Periodicity is not so much a direct route to winning combinatorial games, but rather a direct route to how they behave.  And with understanding these games, you can then determine the best way to approach them.  Please ask questions about this blog post.  I will try my best to answer them.  If you have any further thoughts or conjectures on Periodicity,  feel free to throw that in there.

See you all in class.      

Citations

Albert, Michael H., Richard J. Nowakowski, and David Wolfe. Lessons in play: an introduction to combinatorial game theory. Wellesley, MA: AK Peters, 2007.

pages 144 - 157

Ferguson, Thomas S., F. Thomas Bruss, and Le Cam Lucien M. Game theory, optimal stopping, probability and statistics: papers in honor of Thomas S. Ferguson. Beachwood, OH: Institute of Mathematical Statistics, 2000.

Pages 14 - 17

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.

Sprague-Grundy values

Hello Math 450,

The purpose of this post is to explore Sprauge-Grundy values. Before dwelling into the topic I would like to remind you of features that pertain to combinatorial games:

Impartial games
An impartial game is a two-player game in which the legal moves are solely based on position and each position has the same payouts between players. The only difference between players in an ideal impartial game is who goes first.

Normal play
Under the normal play rule, the last person to play wins.

P- and N-positions
Positions in the game can be classified accordingly, depending if the current player wins or if the bystanding player wins (granted that both players play optimally). A current player win is an N-position because the next player to play will win. Likewise a P-position is if the bystanding player wins because the previous player to play will win.

Note: All terminal positions are P-positions.
Note: From every N-position there is at least one move to a P-position.

OK.. Enough of that. Onward!

We have a decent understanding of combinatorial games. Now, we want to take that understanding and display it graphically. Impartial games can be represented using directed acyclic graphs. A directed acyclic graph is a finite graph with no directed cycles. These can be displayed on an xy-plane with vertices and edges.

from: http://mathinsight.org/definition/undirected_graph

From graph to game, the vertices correspond to positions and edges represent a legal move from one position to another.

Mathematically speaking: "a directed graph, G, is a pair (X, F) where X is a nonempty set of vertices (positions) and F is a function that gives for each x ∈ X a subset of X, F(x) ⊂ X. For a given x ∈ X, F(x) represents the positions to which a player may move from x (called the followers of x). If F(x) is empty, x is called a terminal position."

A two-person game may be represented using graph G=(X,F) and by following these rules:

(1) Player 1 moves first, starting at a set opening position.
(2) Players alternate moves
(3) At position x, the player whose turn it is to move chooses a position y ∈ F(x).
(4) The player who is confronted with a terminal position at his turn, and thus cannot move, loses.

An impartial game (what we are working with) requires more regulation.

As of now, from the previous definitions, this game could continue for an infinite amount of moves. To fit the rules of the games that we are working with, such as Nim, we need to impose the property that no matter what starting point x is used, there is a number n, such that every path from x has length less than or equal to n. These graphs are considered progressively bounded, this means that there are no cycles.

This image depicts a directed a cyclic graph for a game where you start with 10 pieces and can take away 1,2, or 3 pieces. Notice how there is no repetition of moves. Notice anything else?


source: http://m.blog.csdn.net/article/details?id=21039309



Using the idea of N- and P- positions we can get graphs that look like this:
                                                    
source:http://www.gabrielnivasch.org/fun/combinatorial-games/sprague-grundy

Is it a good time to talk about Sprague-Grundy values?

Two mathematicians in the 1930's, Roland Sprague and Patrick Grundy, are credited with a function that will assign each position in combinatorial games a natural number.  The Sprague-Grundy function of a graph, G=(X, F), is a function, g, defined on X and taking non-negative integer values, such that

g(x) = mex{g(y) : y ∈ F(x)}. 

g(x) is defined recursively, meaning g(x) is defined in terms of g(y) for all followers y of x.

mex is a short way of saying the minimal excludant. The minimal excludant of a non-negative integer set is the smallest non-negative integer in that set.

Ex. Let M be the set {0, 1,3,4}
mex(M)=2

Ex. Let M be the set {0,2,100}
mex(M)= 1

The end-game Grundy value is equal to 0, thus terminal positions are when g(x)=0. Also, p-positions in a game will have a Grundy value of 0.

Example:
Let there be a game where a position consists of a pile of chips, and a legal move is to remove 1, 2 or 3 chips.

Imagine a table where x is the amount of chips and g is the Grundy function:
                x   0   1   2   3   4   5   6   7   8
             g(x) 0   1   2   3   0   1    2   3   0
g(x) outputs the corresponding Grundy value's for x. Notice how there is a Grundy value of 0 for 4 chips left.

That is, g(2) = mex{0, 1} = 2, g(3) = mex{0, 1, 2} = 3, and g(4) = mex{1, 2, 3} = 0.

In this example g(x)= x mod 4.

Another Example:
A game consists of a pile of chips. A legal move from a position with n chips is to remove any positive number of chips strictly smaller than n/2 + 1.

Here are the corresponding Grundy values for x being the number of chips and g(x) being the grundy values.

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

The Grundy values may be hard to mentally visualize, but it may be easier to comprehend if you write it out. Instead of tables we can apply those graphs we were working on earlier.

source: http://www.gabrielnivasch.org/fun/combinatorial-games/sprague-grundy

So far Grundy values haven't told us much of anything new. We could compute nim-values to find the N- and P-positions.

Fortunately the Sprague-Grundy function lets us analyze Sums of Graph Games. 

Definition: The sum of two combinatorial games G1 and G2 is that game G where, for any move, a player may choose in which of the games G1 and G2 to play. The terminal position in G is (t1,t2), where t is terminal in Gi for i ∈ {1, 2}. We will write G = G1 + G2.

Every progressively bounded combinatorial game, G, in normal play is equivalent to a nim pile.

Need help imagining G1 and G2? Think of those nim piles we love so much.

Suppose we are given G1 and G2. Can we correctly play their sum G1+G2 if we know the N- and P- positions of the seperate games?

Unfortunately the answer is no.

It can be seen through observation that the sum of P-positions is always a P-position.. And the sum of an N-position and a P-position  will be a N-position. But what happens if we add the sums of N-positions? Ambiguity happens :(, not good. The Sprague-Grundy Function takes away this ambiguity.

The Sprague-Grundy function has two important properties:
           -A vertex v is a P-positoin iff g(v)=0
           - if G= G1+G2 and v=v1v2 is a position in G, then g(v) is the bitwise XOR (nimsums) of the binary representations of g(v1) and g(v2): g(v)= g(v₁) ⊕ g(v₂).

These properties imply that v=v1v2 is a P-position iff g(v1)=g(v2), since this is the only way the nim-sum can come out to zero.

The sums of games is a commutative and associative operation, this means we can understand ideal play with any impartial game as long as we know the Grundy function. 


Moving forward we can think about the most efficient path for achieving a win by looking at a graph.

"The most natural application of the Sprague-Grundy theory is for games that naturally decompose into sums of themselves.

Consider the following game: There is a checkerboard of size m × n, and there is an unlimited supply of polyominoes of a certain shape. On each turn, a player places a polyomino on an empty place on the board, and the player who cannot make a move is the loser:

During the course of the game, the board will gradually split into separate regions, for which we can calculate their Grundy values independently:

"

from source 3. 

Any questions or comments would be greatly appreciated.

sources:

1. Ferguson, Thomas S., F. Thomas Bruss, and Le Cam Lucien M. Game theory, optimal stopping, probability and statistics: papers in honor of Thomas S. Ferguson. Beachwood, OH: Institute of Mathematical Statistics, 2000.

2. Peres, Yuvul. "Stat 155 Game theory." http://www.stat.berkeley.edu/~yuvalweb/gath7.pdf.

3. "Sprague-Grundy theory - Gabriel Nivasch." Gabriel Nivasch. Accessed January 30, 2017. http://www.gabrielnivasch.org/fun/combinatorial-games/sprague-grundy.

The Game of Nim

Hello all-

Before I get to the game of Nim, there are a few things you all will need to know in order to understand my presentation.

Review

1. Binary Numbers

For the CS majors, and probably some of the Math majors, this will be review. If so, feel free to skip. For those who don't know (or don't remember) binary numbers, you can represent any base-10 number (Example: 5, 18, 135) using only zeroes and ones. To do so, you'll need to break the base-10 number down into powers of two.  In binary, the rightmost digit is representative of 2⁰, the second rightmost digit is 2¹, the third rightmost is 2², and so on.

Example:

The number 5 can be written as the sum of 4 + 1, or 2² + 2⁰.This means, that 5 in binary is 101, or 1*2² + 0*2¹ + 1*2⁰.

Example:

The number 18 can be written as the sum of 16 + 2, or 2⁴ + 2¹. Then, in binary, we would represent 18 as 10010.

Example:

Finally, the number 135 can be written as the sum of 128 + 4 + 2 + 1, or 2⁷ + 2² + 2¹ + 2⁰. Hence, in binary, 135 is 10000111.

Got it? Good. If not, Google it.

2. Exclusive-Or

The second thing you'll need to remember is the exclusive or operation. A simple way to remember this is to think of it as arithmetic mod 2. For example, 0 ⊕ 0 = 0, because 0+0 = 0 mod 2. Likewise, 1 ⊕ 1 = 0, because 1+1 = 2 = 0 mod 2. Be careful! One thing to be aware of is 1 ⊕ 1 ⊕ 1 = 1, since 1+1+1 = 3 = 1 mod 2. If this is confusing, don't worry too much. I'll spend some time on this in class.

Also feel free to Google this, or leave a question in the comments- I'll try to answer it in class.

3. N and P Positions

Make sure that you're comfortable with the idea of N and P positions, as we'll use them to analyze Nim. If you're iffy on this, review Natasha's blog post below.

On to Nim!

Ok, so the way Nim works is similar to the subtraction game we played with Natasha in class.

Rules:

1. Start with three piles of objects, call them coins.
2. On your turn, you may remove any number of coins from any pile, but only that pile.
• Example move: Take one coin from one pile, leaving the rest in the pile.
• Example move 2: Take an entire pile, so that there are only two piles left.
3. The game is over when all the coins are gone, or your three piles each have zero coins in them.
4. The person who took the last coin (or pile of coins) wins.

You can play Nim with three piles here by clicking on Level 4. We will also probably play a game as a class during my presentation, just to clear everything up.

The Big Question: When in Nim are you in a P-Position, and when are you in an N-Position?

Before I tell you the answer, feel free to write some conjectures in the comments!

Done? Okay.

It turns out you can calculate whether or not a situation in Nim is a P-Position or N-Position, using binary numbers and exclusive or to calculate the Nim Sum.

Then what's the Nim Sum?

The nim sum is the binary representations of the number of objects in your piles, exclusive-ored together.

Huh?

So, let's say you have three piles in your game, with 13, 12, and 8 objects respectively. Then in binary, you have 1101 (13), 1100 (12), and 1000 (8) objects in each pile. To exclusive-or them, we can line them up vertically, and do our mod 2 arithmetic.

So, our answer is 1001, which in base-10, equals 9. This 9 is our nim sum!

How does that relate to P-Positions and N-Positions?

It turns out, that in any given situation, if your nim sum equals zero, you're in a P-Position. Now let's prove it.

Bouton's Theorem

Bouton's Theorem states that a position in Nim, (x₁, x₂, x₃) is a P-Position if and only if the nim sum of its components is zero, x₁ ⊕ x₂ ⊕ x₃ = 0.

In other words, this is the claim that we need to prove.

Proof

Just like in our Subtraction game proof, let's start our proof by building some sets, and then we'll show that they consist of all the situations that satisfy the definition of P and N Positions.

$$\textit{Let} \ P = \{(x_1, x_2, x_3)| x_1 \oplus x_2 \oplus x_3 = 0\}$$

$$\textit{Let} \ N = \{(x_1, x_2, x_3)| x_1 \oplus x_2 \oplus x_3 > 0\}$$

Also note that there is only one terminal position in Nim, (0,0,0), when the last of the coins has been taken.

Step 1: Show all terminal positions are in P

    This is fairly obvious. We have one terminal position, (0,0,0), and 0 ⊕ 0 ⊕ 0 = 0,
so it's in our set P.

Step 2: For any n ∈ N, you can move to a situation in P.

    Let (n₁, n₂, n₃) be a situation ∈ N. Then n₁ ⊕ n₂ ⊕ n₃ > 0.

    Hence our nim sum is greater than zero.

    So, set up your nim sum columns, and compute your nim sum in binary. Go to the leftmost column in your sum that has a 1. We know that there is one, since our nim sum is greater than zero. Pick one of the piles (n₁, n₂, or n₃) that also has a 1 in that column. Make that 1 a 0, and adjust the rest of the columns of that pile so that you have all 0's in your nim sum.

Note: We will do examples of this in class, because I know it's confusing to read about.

    How do we know we made a legal move? Since the leftmost column is being reduced from a 1 to a 0, we know we're taking objects away from that pile, even if we change the rest of the number to 1's. Hence, you can always take away some number of objects from one pile to move into a P-Position if your nim sum is > 0.

Step 3: For any p ∈ P, you have to move to a situation in N.

    Let (p₁, p₂, p₃) be a situation ∈ P. Then p₁ ⊕ p₂ ⊕ p₃ = 0.

    Then when you set up your nim sum columns, the nim sum is comprised entirely of zeros. Remember: another way to think of exclusive or is arithmetic mod 2. This means that there is no way to change only one pile so that you keep zeros in all the columns. Since you can only change the numbers from zeros to ones and vice versa, changing only one pile will always change one of your nim sum columns from a zero to a one, creating a nim sum > 0.

    Hence, from any position in P, you must move to a position in N.


DONE!

Conclusion

What does all this mean? Basically, it means that for any situation in Nim, it is always possible to figure out whether or not you're in a P-Position or an N-Position. Why is this important? We'll discuss in upcoming classes how Nim is representative of all combinatorial impartial games, but that's beyond the scope of my presentation. Throughout this post, we've discussed and analyzed the game of Nim, using nim sums, and we've talked about how they relate to N and P Positions. We've also proved Bouton's Theorem true, using the same model discussed in class. I'll leave you with some ideas for discussion topics, either in the comments or class:

• Misere Nim: a variation where the last person to take coins loses
• Other variations on Nim
• Does Bouton's Theorem apply to Nim with more than 3 piles?
• Anything you have questions on

Citations:

Bouton, Charles L. "Nim, A Game with a Complete Mathematical Theory." The Annals of Mathematics 3.1/4 (1901): 35-39. Web.

Ferguson, Thomas S. "Game Theory." (n.d.): n. pag. Web. <http://myslu.stlawu.edu/~nkomarov/450/comb.pdf>.

"Theory of Impartial Games." The Mathematics of Toys and Games. N.p.: n.p., 2009. N. pag. Print.