2026-07-24T05:02:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8811 2024-03-06T10:42:42Z ddc:004 open_access

Faster Evaluation of Subtraction Games Eppstein, David subtraction games Sprague-Grundy theory nim-values 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik David Eppstein 2018 Is Part Of LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2018.20 urn:nbn:de:0030-drops-88119 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.20 eng https://creativecommons.org/licenses/by/3.0/legalcode