License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2018.20
URN: urn:nbn:de:0030-drops-88119
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8811/
Go to the corresponding LIPIcs Volume Portal

Eppstein, David

Faster Evaluation of Subtraction Games

pdf-format:
LIPIcs-FUN-2018-20.pdf (0.4 MB)

Abstract

Subtraction games are played with one or more heaps of tokens, with players taking turns removing from a single heap a number of tokens belonging to a specified subtraction set; the last player to move wins. We describe how to compute the set of winning heap sizes in single-heap subtraction games (for an input consisting of the subtraction set and maximum heap size n), in time O~(n), where the O~ elides logarithmic factors. For multi-heap games, the optimal game play is determined by the nim-value of each heap; we describe how to compute the nim-values of all heaps of size up to n in time O~(mn), where m is the maximum nim-value occurring among these heap sizes. These time bounds improve naive dynamic programming algorithms with time O(n|S|), because m <=|S| for all such games. We apply these results to the game of subtract-a-square, whose set of winning positions is a maximal square-difference-free set of a type studied in number theory in connection with the Furstenberg-Sárközy theorem. We provide experimental evidence that, for this game, the set of winning positions has a density comparable to that of the densest known square-difference-free sets, and has a modular structure related to the known constructions for these dense sets. Additionally, this game's nim-values are (experimentally) significantly smaller than the size of its subtraction set, implying that our algorithm achieves a polynomial speedup over dynamic programming.

BibTeX - Entry

@InProceedings{eppstein:LIPIcs:2018:8811,
  author =	{David Eppstein},
  title =	{{Faster Evaluation of Subtraction Games}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{20:1--20:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Hiro Ito and Stefano Leonardi and Linda Pagli and Giuseppe Prencipe},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8811},
  URN =		{urn:nbn:de:0030-drops-88119},
  doi =		{10.4230/LIPIcs.FUN.2018.20},
  annote =	{Keywords: subtraction games, Sprague-Grundy theory, nim-values}
}

Keywords: subtraction games, Sprague-Grundy theory, nim-values
Collection: 9th International Conference on Fun with Algorithms (FUN 2018)
Issue Date: 2018
Date of publication: 04.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI