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.