Officers is a two-player “take-and-break” game played with heaps of coins (or if you prefer, piles of beans, or officers and their subordinates, or groups of people who form indivisible couplesIn the equivalent game Couples-are-Forever, a move is to choose a heap and split it into two, with the proviso that you may not split a heap of size 2. An Officers heap of size n is equivalent to a Couples-are-Forever heap of size n+1.

, or …). The two players alternate turns, and every turn consists of removing a coin from a heap and leaving the remainder in either one or two heaps. In particular, taking away a lone coin is not a valid move. The winner is the last player who can make a move.

For example, a game starting with a single pile of 10 coins might proceed

[10] \xrightarrow{\mathcal{L}} [3, 6] \xrightarrow{\mathcal{R}} [3, 1, 4] \xrightarrow{\mathcal{L}} [1, 1, 1, 4] \xrightarrow{\mathcal{R}} [1, 1, 1, 1, 2] \xrightarrow{\mathcal{L}} [1, 1, 1, 1, 1]

at which point player \mathcal{R} is stuck, so player \mathcal{L} has won.In fact, he was following the winning strategy.

Although the total number of coins decreases by 1 each turn, the outcome of the game is not determined simply by the parity of the starting number of coins: the moment that the game ends also depends on how many piles are created by the players making splitting moves. As we will soon see, the winning move from any given position is extremely unpredictable.

We can solve a game of this kind by calculating the Grundy value for each position, and in this post I’m going to discuss my attempt at calculating these values for Officers as fast as possible.