¡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