Archive for the ‘Game Theory’ Category.

Winning Nim Against a Player who Plays Randomly

I recently wrote about my way of playing Nim against a player who doesn’t know how to play. If my move starts in an N-position, then I obviously win. If my move starts in a P-position, I would remove one token hoping that more tokens for my opponent means more opportunity for them to make a mistake. But which token to remove? Does it make a difference from which pile I choose?

Consider the position (2,4,6). If I take one token, my opponent has 11 different moves. If I choose one token from the first or the last pile, my opponent needs to get to (1,4,5) not to lose. If I choose one token from the middle pile, my opponent needs to get to (1,3,2) not to lose. But the first possibility is better, because there are more tokens left, which gives me a better chance to have a longer game in case my opponent guesses correctly.

That is the strategy I actually use: I take one token so that the only way for the opponent to win is to take one token too.

This is a good heuristic idea, but to make such a strategy precise we need to know the probability distribution of the moves of my opponent. So let us assume that s/he picks a move uniformly at random. If there are n tokens in a N-position, then there are n − 1 possible moves. At least one of them goes to a P-position. That means my best chance to get on the winning track after the first move is not more than n/(n−1).

If there are 2 or 3 heaps, then the best strategy is to go for the longest game. With this strategy my opponent always has exactly one move to get to a P-position, I win after the first turn with probability n/(n−1). I lose the game with probability 1/(n−1)!!.

Something interesting happens if there are more than three heaps. In this case it is possible to have more than one winning move from a N-position. It is not obvious that I should play the longest game. Consider position (1,3,5,7). If I remove one token, then my opponent has three winning moves to a position with 14 tokens. On the other hand, if I remove 2 tokens from the second or the fourth pile, then my opponent has one good move, though to a position with only 12 tokens. What should I do?

I leave it to my readers to calculate the optimal strategy against a random player starting from position (1,3,5,7).

3-Pile Nim as an Automaton

In my paper with Joshua Xiong, Nim Fractals, we produced a bijection between P-positions in the three-pile Nim and a three-branch Ulam-Warburton automaton. We also defined a parent-child relationship on games that is induced by this bijection. Namely, two consecutive P-positions in a longest optimal game of Nim are the ones that correspond to a parent-child pair in the automaton. A cell in the Ulam-Warburton automaton has exactly one parent. That means, if (a,b,c) is a Nim P-position, then exactly one of (a − 1,b − 1,c), (a − 1,b,c − 1), and (a,b − 1,c − 1) must be a P-position and a parent of (a,b,c). (See our paper for more details.)

Now I want to explicitly write out the rules of an automaton which will generate the Nim P-positions in 3D.

Let me restrict the evolution of the automaton to the non-negative octant. That is, we consider points (a,b,c) in 3D, where each coordinate is a non-negative integer. We define the neighbors of the point (a,b,c) to be the points that differ from (a,b,c) in two coordinates exactly by 1. So each point strictly inside the octant has 12 neighbors. (There are three ways to choose two coordinates, and after that four ways to choose plus or minus 1 in each of them.

There is a geometric interpretation to this notion of neighborhood. Let us correspond a unit cube to a point with integer coordinates. The center of the cube is located at the given point and the sides are parallel to the axes. Then two points are neighbors if and only if the corresponding cubes share one edge. Now it becomes more visual that a cube has 12 neighbors, as it has 12 edges.

Here is the rule of the automaton. Points never die. We start with the patriarch, (0,0,0), one point being alive. The non-alive point is born inside the non-negative octant if it has exactly 1 alive neighbor that is closer to the patriarch. In other words the point (a,b,c) is born if and only if exactly one out of three points (a − 1,b − 1,c), (a − 1,b,c − 1), and (a,b − 1,c − 1) is alive. It follows that the points that are born at the n-th step has a coordinate sum 2n.

Consider for example the starting growth. At the first step the points (0,1,1), (1,0,1) and (1,1,0) are born. At the next step the points (0,2,2) and (2,0,2) and (2,2,0) are born. while the (1,1,2) will never be born as starting from the second step it has at least two live neighbors: (0,1,1) and (1,0,1) that are closer to the patriarch.

Theorem. In the resulting automaton, the points that are born at step n are exactly the P-positions of Nim with the total of 2n tokens.

Proof. Only the points with an even total can be born. Now we proceed by induction on the total number of tokens. The base case is obvious. Suppose we proved that at step n exactly P-positions with 2n tokens are born. Consider a P-position of Nim: (a,b,c) such that a + b + c = 2n + 2. Remember, that bitwise XOR of a, b, and c is zero. Consider the 2-adic values of a, b, and c (aka the smallest powers of 2 dividing a, b, and c). There should be exactly two out of these three integers that have the smallest 2-adic value. Suppose these are a and b. Then (a − 1,b − 1,c) is a P-position, while (a − 1,b,c − 1) and (a,b − 1,a − 1) are not. That means by the inductive hypothesis (a,b,c) has exactly one alive neighbor. So the position (a,b,c) is born at time n + 1.

Now we need to proof that nothing else is born. For the sake of contradiction suppose that (a,b,c) is the earliest N-position to be born. That means it has a live neighbor that is a P-position closer to the patriarch. WLOG we can assume that this neighbor is (a − 1,b − 1,c).

If a − 1 and b − 1 are both even, then (a,b,c) is a P-position, which is a contradiction. Suppose a − 1 and b − 1 are both odd. Then their binary representations can’t have the same number of ones at the end. Otherwise, (a,b,c) is a P-position. That is a and b have different 2-adic values. Suppose a has a smaller 2-adic value, Then, for (a − 1,b − 1,c) to be a P-position a and c has to have the same 2-adic value. That means (a,b − 1,c − 1) is a P-position too. Now suppose a − 1 and b − 1 are of different parities. Without loss of generality suppose a − 1 is odd and b − 1 is even, then c is odd. Then (a − 1,b,c − 1) is a P-position too. Thus we can always find a second neighbor with the same number of tokens. That is, both neighbors are alive at the same time; and the N-position (a,b,c) is never born. □

One might wonder what happens if we relax the automaton rule by removing the constraint on the distance to the patriarch. Suppose a new point is born if it has exactly one neighbor alive. This will be a different automaton. Let us look at the starting growth, up to a permutation of coordinates. At step one, positions (0,1,1) are born. At the next step positions (0,2,2) are born. At the next step positions (0,1,3), (1,2,3) and (0,3,3) are born. We see that (0,1,3) is not a P-positions. What will happen later? Will this N-position mess up the future positions that are born? Actually, this automaton will still contain all the P-positions of Nim.

Theorem. In the new automaton, the points that are born at step n and have total of 2n tokens are exactly the P-positions of Nim with the total of 2n tokens.

Proof. Only the points with an even total can be born. Now we proceed by induction on the total number of tokens. The base case is obvious. The birth of the points that have total of 2n tokens and are born at step n depend only on the points with the total of 2n − 2 tokens that are born at step n − 1. By the inductive hypothesis, those are the P-positions with 2n − 2 tokens. So the points have total of 2n tokens and are born at step n match exactly the first automaton described above. To reiterate, N-positions with 2n tokens are born after P-positions with 2n tokens, so they do not influence the birth of P-positions with 2n + 2 tokens. □

The Longest Optimal Game of Nim

In the game of Nim you have several piles with tokens. Players take turns taking several tokens from one pile. The person who takes the last token wins.

The strategy of this game is well-known. You win if after your move the bitwise XOR of all the tokens in all the piles is 0. Such positions that you want to finish your move with are called P-positions.

I play this game with my students where the initial position has four piles with 1, 3, 5, and 7 tokens each. I invite my students to start the game, and I always win as this is a P-position. Very soon my students start complaining that I go second and want to switch with me. What should I do? My idea is to make the game last long (to have many turns before ending) to increase the chances of my students making a mistake. So what is the longest game of Nim given that it starts in a P-position?

Clearly you can’t play slower then taking one token at a time. The beauty of Nim is that such an optimal game starting from a P-position is always possible. I made this claim in several papers of mine, but I can’t find where this is proven. One of my papers (with Joshua Xiong) contains an indirect proof by building a bijection to the Ulam-Warburton automaton. But this claim is simple enough, so I want to present a direct proof here. Actually, I will prove a stronger statement.

Theorem. In an optimal game of Nim that starts at a P-position the first player can take one token at each turn so that the second player is forced to take one token too.

Proof. Consider a P-position in a game of Nim. Then find a pile with the lowest 2-adic value. That is the pile such that the power of two in its factorization is the smallest. Suppose this power is k. Notice that there should be at least two piles with this 2-adic value.

The first player should take a token from one of those piles. Then the bitwise heap-sum after the move is 2k+1−1. Then the Nim strategy requires the second player to take tokens from a pile such that its value decreases after bitwise XORing with 2k+1−1. All piles with the 2-adic value more than k will increase after xoring with 2k+1−1. That means the second player has to take tokens from another pile with 2-adic value k. Moreover, the second player is forced to take exactly one token to match the heap-sum. □

In the position (1,3,5,7) all numbers are odd, so I can take one token from any pile for my first move, then the correct move is to take one token from any other pile. My students do not know that; and I usually win even as the first player. Plus, there are four different ways I can start as the first player. This way my students do not get to try several different options with the same move I make. After I win several times as the first player, I convince my students that I win anyway and persuade them to go back to me being the second player. After that I relax and never lose. I am evil.

The Ford Circles Game

What are the Ford circles? A picture is worth a thousand words, so here is a picture.

Ford Circles

We draw a circle for any rational number p/q between 0 and 1 inclusive. We assume that p/q is the representation of the number in the lowest terms. Then the center of the circle is located at (p/q,1/q) and the radius is 1/q. The number inside a circle is q.

Here’s the game. We start with any circle on the picture, except for the two largest circles corresponding to integers 0 and 1. In one move we can switch to a larger circle that touches our circle. The person who ends up at the two largest circles corresponding to integers 0 or 1 loses. Equivalently, the person who ends in the central circle marked “2” wins.

There are other ways to describe moves in this game in terms of rational numbers corresponding to circles, that is, the x-coordinates of their centers. Two circles corresponding to numbers p/q and r/s touch each other iff one of the following equivalent statements is true:

  • The cross-determinant of two numbers p/q and r/s that is defined as |ps-qr| equals to 1;
  • p/q and r/s are neighbors in some Farey sequence;
  • One of the numbers is the parent of the other in the Stern-Brocot tree.

Let me explain the last bullet. Given two rational numbers in their lowest terms a/b and c/d, we generate their mediant as: (a+c)/(b+d). We call the two numbers a/b and c/d the parents of the mediant (a+c)/(b+d). The Stern-Brocot tree starts with two parents 0/1 and 1/1. Then their mediant is inserted between them to create a row: 0/1, 1/2, and 1/1. Then all possible mediants of two consecutive numbers are inserted in a given row to get a new row. The process repeats ad infinitum. The famous theorem states that any rational number between 0 and 1 will appear in the process.

What I like about this game is a simple and beautiful description of P-positions (These are the positions you want to end your move at in order to win.) P-positions are numbers with even denominators in their lowest terms.

Ford Circles

In the picture above P-positions are blue, while other positions are red. All circles touched by blue are red. And if we look at the larger neighbors of every red circle, one of them is blue and one is red.

Let’s prove that the numbers with even denominators satisfy the conditions for P-positions. First, two circles corresponding to numbers with even denominators can’t touch each other. Indeed, the cross-determinant of two such fractions is divisible by 2. Second, each red circle has to touch one blue and one red circle with larger radii. Indeed, the circles with larger radii touching a given circle are exactly the parents of the circle. If the mediant has an odd denominator, then one of the parents must have an even denominator and the other an odd denominator.

Ringiana

Starting position

My brother, Mikhail Khovanov, has invented a new game: Ringiana. It is now available for iPhone, and soon should be available for Android.

In the starting position you see four multi-colored quadrants of a ring. For example, the first picture shows the starting position of level 33.

You can either swipe or touch between the quadrants. A swipe expands one quadrant into two quadrants and compresses two other quadrants into one. You can swipe clockwise or counterclockwise. The second figure shows the result of the clockwise swipe of the North opening. The NW quadrant that was half-red and half-yellow has expanded into two quadrants. The red piece now occupies the entire NW quadrant and the yellow piece—the entire NE quadrant. Two East quadrants got contracted into one SE quadrant. The former blue NE quadrant became the top blue half of the SE quadrant. The former SE half-blue half-green quadrant became the bottom half of the SE quadrant. In general the quadrant where the swiping movement starts expands in the direction of the swipe and the quadrant where the swiping movements ends together with the next quadrant compresses.

 

After Swipe
After Touch
End Game

You can also touch an opening between quadrants. In this case the neighboring quadrants exchange places. The third figure shows the result of touching the East opening.

 

The goal of the game is to reach the final position: have each quadrant in one color. The next image shows the end of this particular level. As you can see the game was finished in 7 moves. In this particular case this is the smallest number of moves possible. To tell you a secret, it wasn’t me who finished the game in the smallest number of moves: it was my brother.

There is also a tutorial for this game on youtube.

The Wythoff’s Game Evolution Graph

In my paper Nim Fractals written with Joshua Xiong we discovered an interesting graph structure on P-positions of impartial combinatorial games. P-positions are vertices of the graph and two vertices are connected if they are consecutive P-positions in an optimal longest game.

A longest game of Nim is played when exactly one token is removed in each turn. So in Nim two P-positions are connected if it is possible to get from one of them to the other by removing two tokens.

In the paper we discussed the evolution graph of Nim with three piles. The graph has the same structure as three branches of the Ulam-Warburton automaton.

The evolution graph of the 2-pile Nim

For completeness, I would like to describe the evolution graph of the 2-pile Nim. The P-positions in a 2-pile Nim are pairs (n,n), for any integer n. Two positions (n,n) and (m,m) are connected if and only if m and n differ by 1. The first picture represents this graph.

The Wythoff’s game is more interesting. There are two piles of tokens. In one move a player can take any number of tokens from one pile or the same number of tokens from both piles.

The P-positions (n,m) such that nm start as: (0,0), (1,2), (3,5), (4,7), (6,10) and so on. They can be enumerated using φ: the golden ratio. Namely, nk = ⌊kφ⌋ and mk = ⌊kφ2⌋ = nk + k, where k ≥ 0.

The evolution graph of the Wythoff's game

In a longest Wythoff’s game the difference between the coordinates decreases by 1. That is, it takes a maximum of 2k steps to end an optimal game starting from position (nk,mk). The picture shows the evolution graph.

The interesting part of the picture is the crossover between two “lines”. From positions with large coordinates like (6,10) with a difference of 4 you can get to only one position with a difference of 3: (4,7) and not (7,4). But from position (3,5) with a difference of 2 you can get to both positions with a difference of 1: (1,2) and (2,1).

From Graphs to Games

In my paper with Joshua Xiong on Nim Fractals we explained how to build an evolution graph corresponding to an impartial combinatorial game. The vertices of the graph are P-positions. And two vertices are connected if the two corresponding positions are consecutive P-positions in a longest possible optimal game.

What types of graphs do we get? An evolution graph should have at least one sink: these are our terminal P-positions. Also there are no directed loops: the game is finite. In addition, the distance from a vertex to sinks is uniquely defined: the number of directed edges that is needed to move from this vertex to a sink. This number is equal to half of the number of moves in the longest game, starting from the corresponding P-position.

A natural question arises: Can we build a game from a graph? The graph needs to satisfy the properties above. But other than that, can we? We can consider the graph itself as a game. Players can start at a vertex or an edge. From an edge, they can only move to a vertex where this edge ends. From a vertex they can move to any out-edge. The corresponding evolution graph is the graph itself. Vertices correspond to P-positions and edges to N-positions.

There is an equivalent game with a more uniform description. We put a vertex in the middle of every edge in the evolution graph. The new graph becomes bipartite. Players can start at any vertex. A move is allowed from a vertex following an out-edge to the vertex, where this edge ends. Vertices that are in the same part as terminal positions are P-positions. Other vertices are N-positions.

Nim Automaton

I mentor three PRIMES projects. One of them, with Joshua Xiong from Acton-Boxborough Regional High School, is devoted to impartial combinatorial games. We recently found a connection between these games and cellular automata. But first I need to remind you of the rules of Nim.

In the game of Nim there are several piles with counters. Two players take turns choosing a pile and removing several counters from it. A player loses when he or she who doesn’t have a turn. Nim is the most famous impartial combinatorial game and its strategy is well known. To win, you need to finish your move in a so called P-position. Nim P-positions are easy to calculate: Bitwise XOR the number of counters in all the piles, and if the result is zero then it’s a P-position.

The total number of counters in a P-position is even. So we calculated the sequence a(n): the number of P-positions in the game of Nim with three piles with the total number of counters equal to 2n. As soon as we got the sequence we plugged it into the OEIS, and voilà it was there: The sequence A130665 described the growth of the three branches of the Ulam-Warburton cellular automaton.

U-W automaton

The first picture shows the automaton after 6 generations. The automaton consists of cells that never die and it grows like this: start with a square on a square grid. In the next generation the squares that share exactly one side with the living squares are born. At the end remove the Southern branch.

Everything fell into place. We immediately realized that the language of the automata gives us the right words to describe what we know about the game of Nim.

Now we want to describe the automaton related to any impartial combinatorial game. Again, the cells never die and the initial cells correspond to terminal P-positions. People who write programs for calculating P-positions will find a notion of the next generation very natural. Indeed, the program usually starts with the terminal P-positions: they are generation 0. Then we can proceed by induction. Suppose we have found P-positions up to generation i. Denote the positions that are one move away from generation i and earlier as Ni. Then the P-positions that do not belong to generation i and earlier and from which all moves belong to Ni are the P-positions from generation i + 1.

This description explains the generations, but it doesn’t explain who is the parent of a particular P-position. The parent-child relations are depicted as edges on the cellular automaton graph. The parent of position P1 from generation i + 1 is a P-position P2 in generation i that can be reached from P1 in the game.

The parent-child relationship in the game of Nim is especially easy to explain. A P-position P1 is a parent of a P-position P2 if P1 differs from P2 in exactly two piles and it has one fewer counter in each of these piles. For example, a P-position (1,3,5,7) has six parents, one of them is (1,3,4,6). In the game with thee piles a P-position always has exactly one parent.

A position in the game of Nim with three piles is naturally depicted as a triple of numbers, that is as a point in 3D. The picture below shows the Nim automaton in 3D at generation 6.

Nim Automaton

Our paper, Nim Fractals, about sequences enumerating P-positions and describing the automaton connection in more detail is posted at the arXiv:1405.5942. We give a different, but equivalent definition of a parent-child relationship there. A P-position P1 is a parent of P2 if there exists an optimal game such that P1 is achieved from P2 in exactly two moves in a game which takes the longest number of possible moves.

Rubik’s Cube Game

My son Sergei invented the following game a couple of years ago. Two people, Alice and Bob, agree on a number, say, four. Alice takes a clean Rubik’s cube and secretly makes four moves. Bob gets the resulting cube and has to rotate it to the initial state in not more than four moves. Bob doesn’t need to retrace Alice’s moves. He just needs to find a short path back, preferably the shortest one. If he is successful, he gets a point and then it is Alice’s turn.

If they are experienced at solving Rubik’s cube, they can increase the difficulty and play this game with five or six moves.

By the way, how many moves do you need to solve any position on a Rubik’s cube if you know the optimal way? The cube is so complicated that people can’t always know the optimal way. They think that God can, so they called the diameter of the set of all possible Rubik’s cube positions, God’s Number. It was recently proven that God’s Number is 20. If Alice and Bob can increase the difficulty level to 20, that would mean that they can find the shortest path back to the initial state from any position of the cube, or, in short, that they would master God’s algorithm.

Rock, Paper, Scissor

rpsSergei Bernstein and Nathan Benjamin brought back a variation of the “Rock, Paper, Scissors” game from the Mathcamp. They call it “Rock, Paper, Scissor.” In this variation one of the players is not allowed to play Scissors. The game ends as soon as someone wins a turn.

Can you suggest the best strategy for each player?

They also invented their own variation of the standard “Rock, Paper, Scissors.” In their version, players are not allowed to play the same thing twice in a row.

If there is a draw, then it will remain a draw forever. So the game ends when there is a draw. The winner is the person who has more points.

They didn’t invent a nice name for their game yet, so I am open to suggestions.