Tag: Impartial Games

Sieves And Wythoff’s Nim

In math, a sieve is used to divide the integers in two piles, the good ones and the bad ones. The oldest example is the Sieve of Eratosthenes, used to find the list of prime numbers: We start with the list 2, 3, 4, 5, 6,… of all integers greater than one. The first element in the list is declared good, and all multiples are declared bad. This leaves us with the list 3,5,7,9,11,13,15,17,… of all odd numbers greater than one. Again the first element in the list is declared good, and all multiples are declared bad, leaving us with 5, 7, 11, 13, 17, 19, … If we keep going like this, the good numbers become the list of all prime numbers.

Wythoff 3

A much simpler sieve proceeds as follows. We start with all positive integers. In step n, we declare the first element (say a) as good, and the element a+n as bad. So in step 1, 1 is good, 2 =1+1 is bad, and we are left with the list 3, 4, 5, 6….. In the second step, 3 becomes good while 5=3+2 goes bad, leaving us with 4, 6, 7, 8, 9, …. In the third step 4 becomes good and 7=4+3 goes bad, etc.

This separates the positive integers into the sequence a(n)=1, 3, 4, 6, 8, 9, 11, 12, 14, 16, … of good integers and the sequence b(n)=2, 5, 7, 10, 13, 15, 18, 20, 23, 26, … of bad integers.

 

Wythoff 4

Miraculously, there is a simple formula for these sequences. We have a(n)=[n 𝜑] and b(n)=[n (𝜑+1)], where [x] denotes the largest integer less than or equal to x, and 𝜑 = (1+√5)/2 is the Golden Ratio. Sequences of the form [n 𝛂] are called Beatty sequences, and Raleigh’s miraculous theorem states that [n 𝛂] and [n 𝛃] are complementary if and only if 1/𝛂+1/𝛃=1. Even more miraculous is that Raleigh’s theorem isn’t so difficult to prove, but this has to wait here until I find a picture proof of it. Given all this, it is not difficult to see that the good and evil sequences are indeed the Beatty sequences as claimed.

Wywin 1 01

But there is more, these sequences are also relevant for a Nim-variant called Wythoff’s game. This is played with two heaps of tokens, and the two players take turns taking an arbitrary amount of tokens from either pile, or the same amount of tokens from both piles. The game ends with the winner making the last move.

Wywin 2 01

If we label a position of two piles of size a and b as a point (a,b) in the first quadrant, the top picture shows all legal moves from the purple position as green positions.

The second picture shows a sample game, ending with orange losing, because they are out of moves.

Wythoff 1

How do we find a strategy? We mark (third image) all positions where the first player can win as green. The unmarked positions closest to the point (0,0) are then certain losing positions, because the first player has to move from them to green. We mark these two as orange, and again all positions from where those can be reached as green (fourth image).

Wythoff 2

This process of separating positions in winners and losers is just the sieve we used to create the a(n) and b(n) sequences — in fact, the positions (0,0), (a(n), b(n)) and (b(n), a(n)) are exactly the losing positions for Wythoff Nim. You can use the last image to contemplate this. If you are above the orange or below the cyan line on a white position, you can win by moving down or left to an orange or cyan position, because the two Beatty sequences are complementary. If you are between the two lines, you can move diagonally down-left to an orange or cyan position, because the differences b(n)-a(n)=n exhaust all integers. 

Chomp (The Esthetics of Not Knowing)

Mathematics has a few peculiarities (inherited by their owners, the mathematicians) that irritate the uninitiated. One of them is the non-constructive aspect of many of its statements. A delicious example is the game Chomp, played with a chocolate bar. Traditionally, the top left piece is poisoned. Two players take turns selecting a piece, breaking it off together with the rectangular chunk of the pieces that are to the right or below of that piece, and instantly eating all of it. Here is an example sequence of turns. The lighter brown indicates which pieces the player is about to eat. We see that here Two has the last bite. Let’s not talk about it.Chomp 1 01

As with each move the number of uneaten chocolate pieces decreases, the game necessarily ends, and there is no draw. Mathematicians conclude from this that either One or Two has a winning strategy, i.e. a way of choosing chocolate pieces so that they win (survive), no matter what the other is doing. In Chomp, the situation is more surprising: One can always win, no matter how large the chocolate bar, but we are generally clueless how One can accomplish this. This is done by an argument that is called strategy stealing, and uses a perplexing indirect proof. So let’s assume, by contradiction, that Two has a winning strategy.

Chomp 2 01

One steals this strategy as follows: One takes the bottom right piece, and sees what Two is doing. Two will make a winning move, removing another piece and everything below and to the right. But One could have done the exact same thing, reaching the same position in the first place (as the bottom right piece will disappear with that move as well). But the nagging question remains unanswered: How does One win? What is the winning move? This happens to be a very difficult question. We not only have to consider the whole, intact chocolate bar, but also the ones that arise while chomping, and we can (very plausibly) even allow bars where some of the chocolate pieces have already been eaten (by someone) before the game even starts. For instance, below are all 132 fragmentary chocolate bars that fit in a 2×6 box where the moving player will lose, assuming the other player has their wits together.

2x6

Out of decency I have removed the poisoned piece in the top left corner, the game now simply ends when one player has no move left, meaning they lose, but keep at least their life. Below are the 182 losing positions that fit in a 3×4 box.

3x4

This is incomprehensible determinism made visible. There are patterns, though. If one encodes all possible positions that fit in a 2×10 box by a pair of binary numbers and plots the losing positions as dots in a 1024×1024 square, one gets the following:

Losers10b

Some of the patterns (like the emerging periodicity) have been partially understood, and I’ll write about that later, time and comprehension permitting.

Euclid’s Game

One of the most fundamental algorithms in mathematics is the Euclidean Algorithm to compute (among other things) the greatest common divisor of two numbers. 

Euclid’s Game is a two person strategy game, invented by Cole and Davie in 1969, employing this algorithm, and, maybe not surprisingly, connected to the Golden Ratio. It is played with a pair of positive integers, like (11,27). A move consists of taking away from one number a non-zero multiple of the other number, so that the result is still non-negative.

 

So from (11,27), we can move to either (11,16) or to (11,5).
The players take turns until one number becomes zero, so that the other player is out of moves and has lost.

Here is a complete sample game:

(11,27)➔(11,5)➔(1,5)➔(1,3)➔(1,0)

Below is a way to visualize the possible moves by placing a blue pair (a,b) in a coordinate grid. If a<b, the possible yellow moves are obtained by decreasing the x-coordinate by a, until we get below the x-axis.

Euclid2 moves

We would like to find out when the first player has a winning strategy.

Here is a simple case: If one number is a multiple of the other, the first player can reduce the larger number to 0 and win in a single move. In particular, all pairs (a,a) are a win for the first player. By symmetry, we can from now on restrict our attention to the case that a<b.

How many different moves are possible for the pair (a,b)? We can list the moves (using the floor notation [x] for the largest integer less than or equal to x) as

(a,b-a), (a,b-2a), … , (a,b-[b/a] a),

so there are [b/a] possible moves. You can check this in the diagram above, too.

In many games, it is a good strategy to force the other player’s moves, and this turns out to be the case here as well. The first player should try to reach a pair (a’,b’) with 1< b’/ a’ <2, so that the second player has only one move left.

We will now prove:

Theorem: The first player has a winning strategy if and only if b/a is an integer, or b/a>𝜑, where 𝜑=(√5+1/2) ≈ 1.6180<2 is the Golden Ratio.
In the first case, the player wins by making the larger number 0, in the second case by moving to a position (a’,b’) where 1<b’/a'<2.

Below is a diagram showing all winning pairs (a,b) for the first player with a,b<30 in green. 

Euclid2 30

We first pin down the role of the Golden Ratio.

Lemma: If 1<b/a<𝜑, there is only one move from (a,b), namely to (a’,b’)=(b-a,a), and we have b’/a’>𝜑.

Proof:
We have

Frac a b = frac
so that

Frac b a > fra
In other words, if we can move the other player into the region 1<b/a<𝜑, they are forced to move us back into the claimed winning region b’/a’ >𝜑.

The next lemma tells us when that is possible:

Lemma: Let k be a positive integer.
If k<𝜑+k-1<b/a<k+1, we can move to (a’,b’) = (b-k a, a), and this pair satisfies 1<b’/a'<𝜑. In other words, we subtract the largest amount we are allowed to.

Proof:
We have
Phi 1< frac a b
Taking reciprocals proves the claim.

We will now take care of the remaining possible ratios. Here, we take away one times less than would be allowed:

Lemma: Let k be a positive integer.
If k+1<b/a<𝜑+k, we can move to (a’,b’) = (a, b-k a). From there, only one move is possible, namely to (a”,b”) = (b-(k+1)a, a), and this pair satisfies b”/a”>𝜑.

Proof:
That the chosen move to (a, b-k a) is valid is clear, because the assumptions imply that a<b-ka. Moreover,

Frac b a = fra 1
so there is only one move possible, namely to (a”,b”) = (b-(k+1)a, a). Now we have

Frac a b = f
which proves that a”<b” and that b”/a”>𝜑.

The proof of the theorem now follows by combining the three lemmas.

Euclid3 20b

Life gets more complicated in three dimensions. One can play this game also with triples, allowing to subtract multiples of one number from either of the other two. Above is the set of winning triples in the first octant, marked with small green dots, while the losing positions are big and red. One can see they form a tetrahedral cone, but the cone is not solid, meaning that it probably won’t be as easy to find a simple winning strategy. As an impartial game, Euclid is equivalent to the game of of Nim in any dimension, it’s just not so clear, what the size of the Nim pile is.

Eraserhead (Games on Circles I)

This is not about the film by David Lynch. Eraserhead is played by two players on finite graph with some vertices occupied by erasers. At each turn, the player chooses one eraser, moves it to an unoccupied adjacent edge, thereby erasing the connecting edge. The player who moves last wins.

Let’s analyze this for cycle graphs.
Eraserhead1 01

If played with just one eraser, the first player chooses the direction, and all other moves are forced, until the eraser has erased all edges. So the first player wins if the cycle graph has an odd number of vertices. That was boring.

For two erasers, it gets slightly more interesting, but the outcome is the same: The first player can win if the number of vertices is odd. The two erasers divide the graph into two components whose number of vertices have different parity (3 and 4 in the example below).
Moving an eraser into the even component would be a mistake, as the second player will then move into the same component with the other eraser. This leaves an even number of moves for both players, and the second player will win.

But a winning move for the first player consists of moving one eraser into the odd component. This leaves the second player with two choices: Moving the other eraser either way leaves an odd number of moves for both players, and the first player wins. If the second player moves the first eraser again, the first player can move either way and will win.

Eraserhead2 01

So while a little harder, this was still easy. Does this even/odd pattern for winning and losing persist with more erasers? At first, it seems so. For any number of erasers (except the cases of no erasers and erasers everywhere, which leave no moves to begin with), the first (resp. second) player can always win with if the cycle graph has an odd (resp. even) number of vertices — up to cycle graphs with 8 vertices. For the following position with three erasers, the first player has no winning move. There are three essentially different moves, and the diagram give winning responses for the second player.

Eraserhead3 01

The first line is interesting. With the first player to move again, there are still 8 edges to delete (possibly). If the first player moves with the topmost eraser right, this will actually happen, and the first player will loose. To prevent this, s(he) must move that eraser to the left. This leaves all erasers in one component with a total of four edges left. This looks like a good thing, but no matter how they play, only three edges will be deleted, and the second player must win.

So the game does get complicated. What helps is to know the nimbers for simple subpositions, like chains with or without erasers at the end. For instance, the line graph with n vertices and one eraser at the end has nimber 1 for odd even n and 0 for odd n. Similarly, the line graph with n vertices and erasers at both end has nimber 0 for odd even n and 1 for odd n. This is quite trivial, of course, as all moves are forced. More surprisingly, for the line graph with two erasers at the end and a third eraser in between, the nimbers are again 1 for n odd, and 0 for n even, except when n=3 or n=4. Then the nimbers are 0 and 2, respectively. So things start off with promising simple patterns, but then deviate. Below I have, for line graphs of length 12 and 13, respectively a unit cube at coordinate (x,y,z) if the position with erasers at x, y, and z is a lost position for the first player.

Lost12 13

Finally, below, the corresponding images for cycle graphs, viewed diagonally to emphasize the symmetry. The discrepancy is baffling.

Lostcycle3 12

Magnetism

Magnetism is played by two players on a strip of squares, who take turns placing + and – tokens onto the strip. The only rule is that no two tokens with the same parity can be placed next to each other. For instance, there are three legal moves in the following position:

Legal

The player who moves last, wins. This makes Magnetism an impartial game, so that each position is equivalent to a Nim-pile. It turns out that Magnetism is very simple.
First we notice that any position is the sum of simpler positions that have tokens just at the end of a strip. (A sum of games is played by first choosing a game summand, and then making a move in that summand).

Sum 01

Therefore we will know everything about Magentism if we can determine the size of the Nim-piles (the “nimbers”) of the 9 elementary positions:

Nine 01

Things get even simpler. Because of the symmetry of things, there are only four truly different boards to consider.

Four 01

Let’s denote the nimbers of a board of n empty squares (thus not counting the tokens at the end when present) by G(n), G+(n), G++(n), and G+-(n).

n 0 1 2 3 4 5 6
G(n) 0 1 0 1 0 1 0
G+(n) 0 1 2 3 4 5 6
G++(n) – 1 1 1 1 1 1
G+-(n) 0 0 0 0 0 0 0

Now you can win in a position with a positive nimber by moving to a position with zero nimber. For instance, on a board with a single + at one end, one possible winning move is to put a – at the other end.

Spring Cleaning II

This is a continuation of my previous post about this game. Because it is impartial and the rules are simple, one can write a computer program that computes for a given position of dirt pieces the size of the equivalent Nim heap (which is also called its Grundy number or its nimber). Because this is computationally prohibitive, one does this for simple shapes, discovers patterns, and proves these. We did this for rectangles the last time. To warm up, we do it for L-shapes today. Here is. (5,3)-L:

Sweep L53

The nimber of this position is 1, which means in particular that there is a winning move for the first player. You can for instance do vertical swipe in the second column, leaving the second player with two disconnected row/column of three dirt pieces each. From then on, we play symmetrically and win.

For the general (alb)-L, the nimbers are as follows:

a\b 2 3 4 5 6
2 0 4 4 0 3
3 4 1 0 1 0
4 3 0 3 0 3
5 0 1 0 1 0
6 3 0 3 0 3

In other words, the nimber of an L with legs at least 3 dirt pieces long behaves quite simple.
This is good, because if a player can easily memorize the nimbers of simple positions, and these nimbers are small, then the player can usually easily win against players who lack this knowledge.

But maybe all this talk about nimbers is just vain traditional mathematics, and there is an alternative way to understand this game and win easily, without any theory, just by being smart and tough?

Let’s look at at another type of Spring Cleaning positions which I call zigzags. Below are the zigzags Z(1) through Z(7),

Zigzags

and here is the table of the first few nimbers:

n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
nimber 0 0 1 2 0 1 2 3 1 2 3 4 0 3 4

Any pattern emerging? No? There is a solution: Whenever you have a sequence of integers you are clueless about, you had to the Online Encyclopedia of Integer Sequences, the best thing the internet has produced ever, and type it in.

It turns out that the sequence at hand is known as the sequence of nimbers of another impartial game which is called Couples are Forever. The rules are simple: The game is is being played with several piles of tokens. Both players take turns splitting any one pile of size at least three tokens into two piles. The game ends when no piles with more than two tokens are left. This impartial game, beginning with a pile of size n, has (with a shift of two) the same nimbers as the zigzags in Spring Cleaning.

Moreover, for Couples are Forever, the nimbers have been computed into the millions, and no pattern has been found whatsoever. It is not even known whether the nimbers remain bounded.

Couplesgraph

Above is the graph for the nimbers of Couples are Forever (or zigzags in Spring Cleaning) for pile sizes up to 25,000. At first (up to 10,000 or so), it looks like the nimbers are growing linearly, but then they appear to even out. Nobody knows. This is one of the famous open problems in combinatorial game theory.

It tells us also that there won’t be a tough&smart solution for this game, or for Spring Cleaning, or for reality. Which is a good thing.

Spring Cleaning I

Spring Cleaning is played on a rectangular array of randomly placed dirt pieces. A sweep consists of removing a single row or column of consecutive dirt pieces.

Sweep legal

Above are some example of legal sweeps, and below are illegal sweeps.

Sweep illegal

This is a game for two players, who take turns by doing exactly one sweep. The player who sweeps the last time is the winner. This is an impartial game which means that each position is equivalent to a single game of Nim. This is usually bad news, because playing Nim well requires us to perform exclusive or additions of binary numbers in our head, for which our brains are not (yet) well equipped.

The good news here is that many simple positions are equivalent to very small Nim piles, meaning that computations are easy. I will explain this using an example. No proofs (even though they are easy, too).

Sweep win1

It’s your turn to find a winning move in the position above. You know (because I promise) that rectangles completely filled with dirt pieces are easy positions, so you will look for moves that separate the dirt pieces into such rectangles. Here is such a move:

Sweep win1 sol

After that, we are left with four separate rectangles, all completely dirty. This means that this game is equivalent to a game of Nim with four Nim piles. The question is what the pile sizes are. The answer is simple: Any rectangle both of whose dimensions are odd corresponds to a Nim pile of size 1, if both dimensions are even, the Nim pile is empty (size 0), and otherwise, the Nim pile has size 2. In our example, we have a 1×1 rectangle, a 1×3 rectangle, and two 1×2 rectangles. They correspond to Nim piles of sizes 1, 1, 2, and 2. The exclusive or sum of these numbers is 0. This is what we want, because it means that after this move, the game is equivalent to an empty Nim pile. From now on it’s easy. Suppose that our opponent performs a vertical swipe on the 1×3 rectangle. What do we do to return the game to Nim-value 0?

Sweep 3 01

We can sweep away any of the isolated dirt pieces: From then on, the game is symmetrical and we can win easily without any Nim-theory. And we better leave the two 1×2 rectangles untouched. Suppose we remove one of them completely. Then we are left with three 1×1 rectangles and a single 1×2 rectangle, which exclusive or sums up to a Nim pile of size 3, in which case our opponent can win.

Sweep 4 01

The winning move would be to reduce the remaining 1×2 rectangle to a 1×1 rectangle with a horizontal sweep.

So, if we know how to deal with Nim positions that consist of Nim piles of sizes 1 and 2, we will be able to win Spring Cleaning by dissecting a given position eventually into rectangles.