Everything is Nim

(Wee Kean here.) I recently learned some interesting game theory which may or may not (read: will not) be useful in your life. For starters, we begin with the classic game of Nim. If you have seen this game before you should skip to the third section.

Exploring Nim

The Nim game is played as follows: at the start of the game, there are piles of objects. Two players take turn to choose a pile and remove at least one object from the pile. The player which removes the last object wins (or in some versions of the game loses.) As with all games, the goal is to decide which player wins. If you've not seen this problem, you're encouraged to try it since the solution will be in the next paragraph. Perhaps with small cases, one pile of objects, two pile of objects...

Solution: The Nim game is a win for the first player if and only if the XOR of all pile sizes is nonzero usually refered to as the nim sum. For example, if there are three piles of objects with size 1,2,3 respectively, the game is a win for player 2 since the nim sum is $ 1 \oplus 2 \oplus 3 = 0$. A detailed proof of why this works can be found here.

An extension to the lemma in link above is that for any game with a nim sum of $x$, we can go to a game state with nim sum $0 \leq x' < x$. A similar idea pops up later as we generalise this to impartial games.

Somewhat long side tangent:

If this is your first encounter to such a problem, the solution presented is probably extremely unsatisfying since it follows the classic "unmotivatable" observation > explanation solution outline. I remember the first time someone explained the solution to me as well and having the feeling that I would never have guessed the solution and that the use of $ \oplus $ was extremely random. Honestly, at this point in time, I don't think I have a satisfactory way to movtivate all of it but here's an attempt anyway.

When there are only two piles of coin in the game, it is not hard to see that if the piles are of equal size, then the second player can mirror the first player for a win. This applies to more piles in general, if there is some collection of $n$ piles which are identical to some other $n$ piles, you can always apply this mirror strategy. More generally, if there is some nim game $G$, the nim game $G + G$ is a win for player 2 where $X + Y$ denotes the nim game formed by taking the union of the two collection of piles in $X$ and $Y$. (We'll revisit this notion of adding games later.) Then, in some sense, $G + G$ is identical to the $0$ game (you can verify that if player 2 has a winning strategy for $X + G + G$ if and only if he has a winning strategy for $X$ by considering what happens if player 1 plays in $X$ or $G + G$). Then, the equivalence classes of these games $G$ form a vector space modulo 2. Then, if we take a basis, we're just taking XOR whenever we add two games.

From Nim to Impartial Games

Turns out, we can generalise Nim to all impartial games. Here, impartial games refer to games where

• there are two players
• the set of possible moves for any given position is identical for both players
• for any position, there are finitely many possible moves
• for all games, there exists some $n$ such that the game ends in at most $n$ moves

For example, Chess is not an impartial game since for a given board position, the set of legal moves depends on which player is playing. Nim, on the other hand, is an impartial game.

Now the big claim is that for any impartial game $G$, we can assign it a value $f(G)$ akin to the nim sum i.e. the value $f(G)$ should have the following properties:

1. The game $G$ is a win for the first player if and only if $f(G)$ is nonzero.

2. The game $G + H$ has value $f(G+H) = f(G) \oplus f(H)$. Here the game $G + H$ denotes the game where the two players take turns moving in either game $G$ or $H$ with the game ending when both $G$ and $H$ ends.

If $G'$ is a possible game after one move for some game $G$, then denote $G'$ as a follower of $G$. This value $f(G)$ can be defined recursively as the MEX of set of values $f(G')$ where $G'$ is a follower of $G$. The MEX of a set refers to the smallest non-negative integer which is not in that set. For example, $MEX({1,2,3}) = 0$ and $MEX({0,1,3}) = 2$.

To be precise, for the base case, we give the game where no possible moves are left a value of 0. Then recursively, label each game $G$ whose followers have all been labelled. This value is given by the Minimum Excluded Value (MEX) of the set of values $f(G')$ where $G'$ is a follower of $G$. You can try to show that this eventually labels all games $G$.

Why does this satisfy the properties we hope it does? The first property is not hard to prove - the base case is a lose for the first player and has value 0. Then, we can induct to show that a game G has value 0 if and only if no follower has value 0 and is hence a losing position. For the second property, it suffices to show that

1. For every non-negative integer $x < f(G) \oplus f(H)$, there is a follower of $G + H$ which has value $x$

2. No follower of $G + H$ has value $f(G) \oplus f(H)$.

Then, $G+H$ will have value $f(G) \oplus f(H)$. We prove this inductively. For (1), we can follow the proof for nim. Let $d$ be the most significant nonzero bit of $y = x \oplus f(G) \oplus f(H)$. Then, WLOG, the $d$-th bit of $f(G)$ is nonzero. Then, $y \oplus f(G) < f(G)$ and by definition, there exists some game $G'$ which is a follower of $G$ and hence $\space \space G'+H$ is a follower which has value $$y \oplus f(G) \oplus f(H) = (x \oplus f(G) \oplus f(H)) \oplus f(G) \oplus f(H) = x$$ For (2), assume for the sake of contradiction that there is a follower with value $f(G) \oplus f(H)$. WLOG, the move is performed on game $G$, so the follower is of the form $G' + H$, then $$f(G) \oplus f(H) = f(G') \oplus f(H)$$ $$f(G) = f(G')$$ which is a contradiction since $G'$ is a follower of $G$.

Extra madness

One interesting definition of games I came across: for a $n$ player game, we define a game to be a $n$-tuple where each element is a set of games as well. This is a rather confusing recursive definition. The intuition is that the $i$-th element represents the set of game positions which player $i$ can move to. The end of the game is then represented as the $n$-tuple where all elements are the empty set and is the base case for our recursive definition. For example, all checkmate positions in chess can be represented by $(\empty, \empty)$. An impartial 2-player game is then a 2-tuple where the first and second element are identical. Intuitively, this makes sense, the only information you need to define a game is encapsulated in all possible positions after a move.

Can we do similar arithmetic to games here? For 2 player games, the common notation is to write it like this ${G_1| G_2}$ where $G_1$ is the set of all positions player 1 can move to and similarly for $G_2$. Turns out, we can assign some of these game values as well! For some games, we can assign a value $g$ such that

• $g = 0$ if the second player to move always wins
• $g < 0$ if player 1 always wins
• $g > 0$ if player 2 always wins

You can read more about these numbers here.