Sprague–Grundy numbers

531 Views Asked by At

I would appreciate if someone can help me understand the columns of the table in this blog: http://lbv-pc.blogspot.co.uk/2012/07/treblecross.html .

The author writes he leaves this as an exercise to the reader and I could not find the answers myself.

Thank you.

1

There are 1 best solutions below

7
On

The first column, labeled "Game", contains what they call the "clean board" game considered in that row; e.g. "$(5)$" denotes a game on a clean board of size $5$.

The second column, labeled "Reachable"; contains the positions reachable from that clean board; e.g. on a clean board of size $5$, you can place an X in the first slot (from either end), leaving games of size $0$ and $2$, or in the second slot (from either end), leaving games of size $0$ and $1$, or in the middle slot, leaving games of size $0$ on both sides.

The last column, labeled "Nimber", contains the nimber associated with the clean board position in the first column, calculated according to standard nimber arithmetic; e.g. for the clean board of size $5$, first form the XOR of the values of all three pairs of games reachable (as described above). Since those games are always smaller than the game under consideration, you can proceed recursively by filling in the table from top to bottom. So if you've filled it up to the row for game $(5)$, you know that $(0)$, $(1)$ and $(2)$ have nimbers $0$, $1$ and $1$, respectively, so the three XORs for the three possible moves described above are $0\oplus1=1$, $0\oplus1=1$ and $0\oplus0=0$. Then applying the rule of the minimum excluded (MEX) value, given that $0$ and $1$ are excluded, yields the nimber $2$ for that row.