Combinatorial Games (Handout for Math428)

Dr. Z. ^{1}

An impartial combinatorial game is given by a set of positions, V, and a function f : V → 2^{V} where for every v ∈ V, f(v) is the set of positions reachable from v by one legal move.

Any combinatorial game can be described by a digraph whose vertices are V and the arcs are {vw|w ∈ f(v)}, i.e. there is an arc from position v to w iff w can be reached from v in one legal move. Conversely, given a digraph, we can define a game in which a penny is placed on the initial position, and in each turn, the player slides the penny along one of the arcs that come out of the current position. A player who can’t move (i.e. is at a sink) lost the game. If the digraph is acyclic then there can never be any ties, and every position (vertex) can be labelled P or N according to whether the Previous or Next players won respectively.

Labelling algorithm

1. Label all the sinks by P.

Alternate steps 2 and 3 until all the vertices are labelled.

2. Label N all vertices that have (at least one) arc going to a vertex previously labelled P (because this means that the player whose turn it is to move (the Next player) has a good move, i.e. a move that is bad for the Previous player.

3. Label P all vertices that have all their outgoing arc going to vertices labelled N (this means that whatever the Next player can do, will lead to a win to the Previous player).

Sprague-Grundy function

For any set of non-negative integers A let mex(A) be the smallest non-negative integer not in A. For example, mex({0, 1, 2, 4}) = 3 and mex({1, 4}) = 0. In particular mex(∅) = 0.

The Sprague-Grundy function of a Combinatorial game is defined recursively by

f(v) = mex ({f(w)|vw ∈ E}) .

If the graph is acyclic then f(v) can always be defined. For all the sinks s, f(s) = 0. Removing the sinks leaves another acyclic graph whose sinks get the value 1. Removing these vertices, yields yet another graph whose sinks either get the value 2 (if they have arcs that go both to vertices whose values are 0 and 1) or the value 0 (if all the arcs go to vertices labelled 1), etc.

1 Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen

Rd., Piscataway, NJ 08854-8019, USA. zeilberg@math.rutgers.edu http://www.math.rutgers.edu/~zeilberg/ . Nov. 24, 2003.

The Nim Sum ⊕ of a set of numbers is obtained by converting them to binary and adding them up without carry.

For example:

5 ⊕ 7 ⊕ 9 =
(0101)_{2} ⊕ (0111)_{2} ⊕ (1001)_{2} = (1011)_{2} = 2^{3} + 2^{1} + 2^{0} = 11_{10}

If G_{1}, G_{2}, …, G_{r} are games, then their Cartesian product G_{1} × G_{2} × … G_{r} is the game in which you have r boards, the i-th being the digraph G_{i}, and each of them has a penny at the initial position, and at each turn the player can decide which board to play on (just one board!), and on that board slide the penny along one of the arcs.

Theorem: The Grundy function of the position [v_{1}, …, v_{r}] in the compound game G_{1} × … × G_{r} is given by

f([v_{1}, …, v_{r}]) = f(v_{1}) ⊕ … ⊕ f(v_{r}) .

In particular, you can tell whether a position is winning (Grundy function is not 0) or losing (it is 0). In the former case, you should also be able to figure out the winning move, by picking the board with the largest Grundy function and making a move that would made the Nim sum of the Grundy functions 0.

Exercises

1. Prove that a position v is P iff f(v) = 0.

2. Consider the game G_{1} that starts with 10 counters, and a player may take-away 1 or 2 counters.

(a) Draw the digraph of the game. (b) Find the winning/losing positions. (c) Find the Grundy function of all the positions.

3. Do the same as 1, for the game G_{2} that starts with 12 counters and you can take-away 1 or 3 counters.

4. Consider the game G_{1} × G_{1} × G_{2}. If the first pile has 8 counters, the second has 6 counters and the third has 5 counters, is this a P or N position? If it is an N position, what is a winning move?

5. Consider the game G that starts with n counters, and a player can move any number i of counters, 1 ≤ i ≤ n, if the pile is empty then the player whose turn is to move lost. What is the Grundy function f(i)? What is the winning move?

6. The game of r-pile Nim is G × G × … × G (r times). In 4 pile Nim, the current position is (4, 5, 6, 8) (i.e. the first pile has 4 counters, the second 5, the third 6, and the fourth 8). Is that an N or P position? If it is an N position, find the winning move.