MakarovSuites
English
EnglishDeutschРусскийУкраїнськаFrançaisEspañolItalianoPolski
Contact & licences

Math

Nim and the binary sum

Heaps of stones and their binary digits below. A column with an odd number of ones burns red; with no red columns the player to move has already lost. The card checks that rule by solving the whole game tree, not by quoting it.

Nim and the binary sum — Actual application image
Actual application image

What happens

Take any number of stones from one heap; whoever has nothing to take loses. Under the heaps the card draws their binary digits, one column per heap, and a digit column with an odd number of ones burns red. Bouton’s rule says the position is lost for the player to move exactly when no column is red - when the binary sum is zero - and this card does not ask you to believe that: every position of the state space is labelled by solving the game to the end, and the labels are compared with the rule on 729, 2197, 4096 and 7776 positions with zero disagreements. To leave your opponent a zero you must put out the red columns, and only a heap carrying a one in the top red digit can do it. Such heaps are odd in number - otherwise that digit would not be red - so the number of winning moves is one or three and never two, which the count over three heaps confirms: 1092 positions with a single winning move, 148 with three, and none at all with two. Switch to misere, where taking the last stone loses, and the same rule breaks: the solved tree disagrees with it on exactly the positions made of single stones.

Equations used in the module
Equations
heaps of stones, a move takes any number from ONE heap, and the player with nothing to take loses
Bouton's rule: the position is lost for the player to move exactly when the binary sum (xor) of the heap sizes is zero
  the card does not quote this - it labels EVERY position by solving the game to the end and compares: 729, 2197, 4096 and 7776 positions, zero disagreements
winning moves are the heaps with (h xor s) < h, and their number is ALWAYS ODD - one or three, never two:
  over three heaps up to 10 the distribution is 0 moves in 91 positions, 1 move in 1092, 3 moves in 148, and 2 moves in none
  the reason is not a coincidence: a move to zero is made by a heap carrying a one in the top set bit of the sum, and such heaps are odd in number, or that bit would be zero
losing positions are counted exactly: k heaps with sizes 0..2^b−1 hold 2^(b(k−1)) of them - 64 for three heaps of 0..7
MISERE is a different game and this rule is WRONG there: solving the tree disagrees with xor on exactly 2^k positions, all of them made of single stones
  the misere rule: while some heap holds more than one stone, play as usual; when every heap holds one, the position is lost for the mover exactly when their number is ODD
  (1,1,1) is won for the mover in the normal game and lost in misere; (1,1) is the other way round; (2,1,1) is won in both
the default deal 7-5-3 has binary sum 1 and exactly three winning moves: to 6-5-3, to 7-4-3 and to 7-5-2

Related experiments

Back to catalogue
Game tree and alpha-beta — Actual application image

Math

Game tree and alpha-beta

A game tree where every block is as tall as its value: a MAX node stands as high as its tallest child, a MIN node as low as its lowest. Minimax looks at every leaf; alpha-beta skips what cannot change the answer, and how much it skips depends on the order of the moves.

Huffman coding — Actual application image

Math

Huffman coding

A sorted queue of frequencies becomes a prefix-code tree. Select a symbol to trace its bits; step through each merge.

Knapsack: greedy against the table — Actual application image

Math

Knapsack: greedy against the table

Choose numbered cargo under a mass limit. Compare your selection with greed and the exact solution, open a table cell and trace the optimal set backwards.