Document Open Access Logo

Faster Evaluation of Subtraction Games

Author David Eppstein

PDF

File

Thumbnail PDF
PDF
LIPIcs.FUN.2018.20.pdf
  • Filesize: 435 kB
  • 12 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • subtraction games
  • Sprague-Grundy theory
  • nim-values

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get BibTex

David Eppstein. Faster Evaluation of Subtraction Games. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 20:1-20:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.FUN.2018.20

Author Details

David Eppstein
  • Computer Science Department, University of California, Irvine

Funding

  • Eppstein, David: Supported in part by NSF grants CCF-1618301 and CCF-1616248.

References

  1. Richard Beigel and William Gasarch. Square-difference-free sets of size Ω(n^0.7334…). Electronic preprint arxiv:0804.4892, 2008. Google Scholar
  2. Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy. Subtraction games. In Winning Ways for your Mathematical Plays, Vol. I: Games in General, pages 83-86. Addison-Wesley, 1982. Google Scholar
  3. David Bush. The uniqueness of 11,356. sci.math usenet newsgroup, October 12 1992. URL: https://www.ics.uci.edu/~eppstein/cgt/subsquare.html.
  4. J. H. Conway. Chapter 11: Impartial Games and the Game of Nim. In On Numbers and Games, pages 122-135. Academic Press, 1976. Google Scholar
  5. Michael J. Fischer and Michael S. Paterson. String-matching and other products. In Complexity of computation (Proc. SIAM-AMS Appl. Math. Sympos., New York, 1973), volume 7 of SIAM-AMS Proceedings, pages 113-125, Providence, RI, 1974. American Mathematical Society. Google Scholar
  6. Harry Furstenberg. Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions. Journal d'Analyse Mathématique, 31:204-256, 1977. URL: http://dx.doi.org/10.1007/BF02813304.
  7. Solomon W. Golomb. A mathematical investigation of games of "take-away". Journal of Combinatorial Theory, 1:443-458, 1966. URL: http://dx.doi.org/10.1016/S0021-9800(66)80016-9.
  8. P. M. Grundy. Mathematics and games. Eureka, 2:6-8, 1939. Google Scholar
  9. Adam Kalai. Efficient pattern-matching with don't cares. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '02), pages 655-656, Philadelphia, PA, 2002. Society for Industrial and Applied Mathematics. URL: https://dl.acm.org/citation.cfm?id=545381.545468.
  10. Mark Lewko. An improved lower bound related to the Furstenberg-Sárközy theorem. Electronic Journal of Combinatorics, 22(1):P1.32, 2015. URL: https://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p32.
  11. S. Muthukrishnan and Krishna V. Palem. Non-standard stringology: algorithms and complexity. In Frank Thomson Leighton and Michael T. Goodrich, editors, Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montréal, Québec, Canada, pages 770-779. ACM, 1994. URL: http://dx.doi.org/10.1145/195058.195457.
  12. János Pintz, W. L. Steiger, and Endre Szemerédi. On sets of natural numbers whose difference set contains no squares. Journal of the London Mathematical Society (2nd Series), 37(2):219-231, 1988. URL: http://dx.doi.org/10.1112/jlms/s2-37.2.219.
  13. I. Z. Ruzsa. Difference sets without squares. Periodica Mathematica Hungarica, 15(3):205-209, 1984. URL: http://dx.doi.org/10.1007/BF02454169.
  14. A. Sárkőzy. On difference sets of sequences of integers. I. Acta Mathematica Academiae Scientiarum Hungaricae, 31(1-2):125-149, 1978. URL: http://dx.doi.org/10.1007/BF01896079.
  15. A. Sárközy. On difference sets of sequences of integers. II. Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae, 21:45-53, 1978. Google Scholar
  16. Andrew F. Siegel. Robust regression using repeated medians. Biometrika, 69(1):242-244, 1982. URL: http://dx.doi.org/10.1093/biomet/69.1.242.
  17. R. P. Sprague. Über mathematische Kampfspiele. Tohoku Math. J, 41:438-444, 1935. URL: https://www.jstage.jst.go.jp/article/tmj1911/41/0/41_0_438/_article.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact