0
$\begingroup$

Why is that for a game like Turning Turtles, the Sprague-Grundy value of a whole configuration $g$ is the disjunctive sum of its components with only one head? For example, $g(TTHTH) = g(TTH) + g(TTTTH)$.

Another example: in a Tartan coin-flipping game like Rugs, why does the nim-sum of all of the S-G values of each heads position $h_k$ give the S-G value of the whole board?

$\endgroup$
0
$\begingroup$

Suppose the heads are at positions $h_1,\ldots,h_k$. Then this Turning Turtles game is related to a game of Nim with $k$ piles of size $h_1,\ldots,h_k$.

Intuitively, the positions of the heads mark the heights of the Nim piles. There's a detail to be kept into account, namely that in a game of Nim, piles of the same size cancel out in the computation of the value of the position. In Turning Turtles such pairs of piles just "vanish."

If you flip the coin in position $h_i$ from heads to tails, without flipping another coin to its left, you remove the pile of size $h_i$ from the matching Nim game.

If you flip the coin in position $h_j$ from heads to tail as well as the coin in position $i$, with $i < h_j$, it is as if you removed $t_j-i$ coins from the pile of size $h_j$. If the coin at position $i$ shows tails before the move, then there was no pile of size $i$ before the move and there is one after.

If on the other hand, there was a pile of size $i$ before the move, which is to say that the coin at position $i$ showed heads, then subtraction of $h_j-i$ coins from the pile of size $h_j$ creates a second pile of size $i$, which vanishes with the existing one.


About two-dimensional coin-flipping games: In general, one can use the definition of minimum excludent to compute the Sprague-Grundy value of arbitrary finite impartial games. However, if possible, it is convenient to express a game to be analyzed as a combination of simpler games. For example, the game of Nim itself is the disjunctive sum of single-pile Nim games, each of which is trivial to analyze.

Besides the sum of games, one can also define their product. This notion is particularly useful in the analysis of Tartan games. Specifically, the Tartan theorem says that the Grundy function of the product of two games is the nim product of their Grundy functions. This is covered in the third volume of Winning Ways for Your Mathematical Plays and also discussed here. In particular the Tartan theorem applies to the game of Rugs.

$\endgroup$
  • $\begingroup$ I see. How would this apply to 2-dimensional games? For example, in a Tartan coin-flipping game like Rugs, why does the nim-sum of the S-G value of each heads position $h_k$ give the S-G value of the whole board? (Added to original question) $\endgroup$ – Rakeeb Hossain Sep 24 '18 at 2:47
  • $\begingroup$ Thanks for clarifying. I've expanded my answer. As far as I know, Rugs is decomposed into the nim product of simpler games, not their sum. $\endgroup$ – Fabio Somenzi Sep 24 '18 at 4:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.