Skip to the quick start

Impartial 4x4 Nimber Explorer

This demo computes and explores Grundy values for all 65,536 positions of a finite impartial game on a 4x4 board.

← Research demos  |  Home

See how legal moves determine a position’s value

Start with Counterplay →
First visit · three things to try
  1. Inspect the starting L shape. Its three filled squares have nimber 3. The table lists every legal move and the value it leaves.
  2. Play a move from the table. Remove one square, or two filled squares sharing an edge. Try a move whose next nimber is 0.
  3. Build another position. Clicking the board edits it freely; these edits are not game moves. “Restore starting example” returns to the L shape.
How to read the results

mex means the smallest nonnegative integer missing from the next-position values: mex{0,1,2} = 3. A nimber is not a score or a count of winning moves. Zero is losing for the next player under perfect play. Coordinates start at row 0, column 0.

Rules, impartiality, and nimbers

Rules (normal play)

  • A position is a 4x4 board of filled/empty squares.
  • On each move, remove one filled square, or two filled orthogonal neighbours.
  • The player who makes the last move wins.

Why this is impartial

Both players have exactly the same legal moves from every position. There is no hidden information and no chance moves. So this is an impartial combinatorial game under normal play.

Grundy (nimber) value

The nimber of a position is the mex of the nimbers of all legal options. Nimber 0 means a losing position for the player to move; non-zero means winning with correct play.

Historical context: this is a 2D finite variant of the classic Kayles move pattern (remove one or two adjacent tokens). The Sprague-Grundy framework (Sprague and Grundy, 1930s) gives a complete value-theoretic classification for finite impartial normal-play games, though computing nimbers can still be difficult in practice.

Edit a position, then follow a legal move

Computing Grundy table for all 2^16 positions...

Nimber: 0

Bit string order is row-major from top-left to bottom-right.

Move Result state Result bits Nimber(result)

Positions with maximal nimber

Click any listed position to load it into the main board.