The Sprague–Grundy function for some nearly disjunctive sums of NIM and SILVER DOLLAR games

Graham Farr, Nhan Bao Ho

Research output: Contribution to journalArticleResearchpeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)46-59
Number of pages14
JournalTheoretical Computer Science
Volume732
DOIs
Publication statusPublished - 7 Jul 2018

Keywords

  • Combinatorial games
  • Disjunctive sum
  • NIM
  • SILVER DOLLAR
  • Sprague–Grundy function
  • STAR NIM
  • STAR SILVER DOLLAR

Cite this

@article{21d7c7cd0e3f4924a7e958c5b2bc018a,
title = "The Sprague–Grundy function for some nearly disjunctive sums of NIM and SILVER DOLLAR games",
abstract = "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.",
keywords = "Combinatorial games, Disjunctive sum, NIM, SILVER DOLLAR, Sprague–Grundy function, STAR NIM, STAR SILVER DOLLAR",
author = "Graham Farr and Ho, {Nhan Bao}",
year = "2018",
month = "7",
day = "7",
doi = "10.1016/j.tcs.2018.04.027",
language = "English",
volume = "732",
pages = "46--59",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",

}

The Sprague–Grundy function for some nearly disjunctive sums of NIM and SILVER DOLLAR games. / Farr, Graham; Ho, Nhan Bao.

In: Theoretical Computer Science, Vol. 732, 07.07.2018, p. 46-59.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - The Sprague–Grundy function for some nearly disjunctive sums of NIM and SILVER DOLLAR games

AU - Farr, Graham

AU - Ho, Nhan Bao

PY - 2018/7/7

Y1 - 2018/7/7

N2 - 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.

AB - 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.

KW - Combinatorial games

KW - Disjunctive sum

KW - NIM

KW - SILVER DOLLAR

KW - Sprague–Grundy function

KW - STAR NIM

KW - STAR SILVER DOLLAR

UR - http://www.scopus.com/inward/record.url?scp=85046161929&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2018.04.027

DO - 10.1016/j.tcs.2018.04.027

M3 - Article

VL - 732

SP - 46

EP - 59

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -