Faster evaluation of subtraction games

DOI10.4230/LIPICS.FUN.2018.20zbMATH Open1491.91040arXiv1804.06515MaRDI QIDQ3301007FDOQ3301007

David Eppstein

Publication date: 11 August 2020

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 $ildeO(n)$, where the $ildeO$ 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 $ildeO(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 $mle|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'ark"ozy 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.

Full work available at URL: https://arxiv.org/abs/1804.06515

Recommendations

• scientific article
• Partizan subtraction games
• Superlinear period lengths in some subtraction games
• Winning strategies for aperiodic subtraction games
• Partizan octal games: Partizan subtraction games

zbMATH Keywords

subtraction gamesSprague-Grundy theorynim-values

Mathematics Subject Classification ID

Combinatorial games (91A46)

Cites Work

• Robust regression using repeated medians
• Ergodic behavior of diagonal measures and a theorem of Szemeredi on arithmetic progressions
• Non-standard stringology: algorithms and complexity
• Title not available (Why is that?)
• On difference sets of sequences of integers. I
• Title not available (Why is that?)
• On Sets of Natural Numbers Whose Difference Set Contains No Squares
• Difference sets without squares
• Title not available (Why is that?)
• A mathematical investigation of games of “take-away”
• Title not available (Why is that?)
• An improved lower bound related to the Furstenberg-Sárközy theorem

This page was built for publication: Faster evaluation of subtraction games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3301007)