Nim Game Variants

Introduction

Many games look like Nim but change one rule. Some changes preserve the xor solution after transforming every pile. Others change only a small endgame. The main skill is to identify the independent components and determine the Grundy value of one component.

This lecture studies three common versions: normal Nim, misère Nim, and bounded-removal Nim.

Problem or motivation

We process several game positions:

• Type 1: normal Nim. Remove any positive number from one pile; taking the last stone wins.
• Type 2: misère Nim. Moves are the same, but taking the last stone loses.
• Type 3: bounded Nim. Remove between $1$ and $k$ stones from one pile; taking the last stone wins.

For every position, print whether the first player wins.

Core concept

Normal Nim

The first player wins exactly when the xor of pile sizes is nonzero.

Misère Nim

As long as some pile has size at least two, normal Nim strategy still works. The only special case is when every non-empty pile has size one. Then every move removes exactly one whole pile, so the players only alternate until no piles remain. Because taking the last stone loses, the first player wins exactly when the number of piles is even.

Therefore:

• if all piles have size one, use parity;
• otherwise, use the normal xor rule.

Zero piles may be ignored when checking this endgame.

Bounded-removal Nim

For one pile where a move removes $1$ through $$ stones, positions repeat with period . Its Grundy value is