Nim

Nim is a two-player strategy game, where each game has a number of rows (or heaps), and each row has a number of coins. Each player takes turns removing a non-zero number of coins, and in each turn the coins must be removed from a single row. A player wins when their last move takes the last coin in the board.

Strategy

There are provably optimal ways to win Nim, rooted in combinatorial game theory. We define the nim-sum as the bitwise XOR of all rows. If the nim-sum is 0, this is a losing position. If the nim-sum is non-zero, this is a winning position.

The move strategy is below:

fn play_move(mut board: Vec<u8>) -> Option<(u8, u8)> {
    let parity = board.iter().fold(0, |acc, &x| acc ^ x);
    if parity != 0 {
	    for row in &board {
	        let xor = row ^ parity;
	        if xor >= row {
	            row -= xor;
	            return Some(row, row ^ parity);
	        }
	    }
    }
    None
}

Basically: we compute the parity. If non-zero:

• We compute xor, which undoes the row’s contribution.
• If there are enough stones to make a valid move, then:
  • We subtract xor from the row. Can’t remember exactly what it does, but the gist of it is that a ^ a == 0. So we force a non-winning move for the other player.

Links

• Nim from CMPUT 396 (Topics in Computing Science: Games, Puzzles, Algorithms) at UAlberta
• Nim Strategy from CSC270 (Fundamental Data Structures and Techniques) at UofT