The Sprague–Grundy function for some nearly disjunctive sums of Nim and Silver Dollar games

We introduce and analyse an extension of the disjunctive sum operation on some classical impartial games. Whereas the disjunctive sum describes positions formed from independent subpositions, our operation combines positions that are not completely independent but interact only in a very restricted...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2018-07, Vol.732, p.46-59
Main Authors: Farr, Graham, Ho, Nhan Bao
Format: Article
Language:English
Subjects:
Combinatorial games
Disjunctive sum
Nim
Silver Dollar
Sprague–Grundy function
Star Nim
Star Silver Dollar
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We introduce and analyse an extension of the disjunctive sum operation on some classical impartial games. Whereas the disjunctive sum describes positions formed from independent subpositions, our operation combines positions that are not completely independent but interact only in a very restricted way. We extend the games Nim and Silver Dollar, played by moving counters along one-dimensional strips of cells, by joining several strips at their initial cell. We prove that, in certain cases, computing the Sprague–Grundy function can be simplified to that of a simpler game with at most two tokens in each strip. We give an algorithm that, for each Sprague–Grundy value g, computes the positions of two-token Star Nim whose Sprague–Grundy values are g. We establish that the sequence of differences of coordinates of g-positions is ultimately periodic.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2018.04.027