A Computational Approach to the Structure of Subtraction Games

• Activity Number: 256 - Contributed Poster Presentations: Section on Statistical Learning and Data Science
• Type: Contributed
• Date/Time: Monday, July 29, 2019 : 2:00 PM to 3:50 PM
• Sponsor: Section on Statistical Learning and Data Science
• Author(s): Kali Lacy* and Bret Benesh and Jamylle Carter and Deidra Coleman and Douglas Crabill and Jack Good and Michael Smith and Jennifer Travis and Mark Ward
• Companies: Purdue University and College of Saint Benedict/Saint John's University and Diablo Valley College and Wofford College and Purdue University and Purdue University and Purdue University and Lone Star College and Purdue University
• Keywords: Game Theory; Subtraction games; Computer Science; Sequences

Abstract

We present a computational methodology for the structure of subtraction games. One of the oldest problems in combinatorial game theory is to characterize the structure of subtraction games. Although the structure can be analyzed recursively, at present, a methodology for explicitly characterizing the structure of a subtraction game is not (yet) known. In the last two years, our team characterized the (eventual) period lengths of the Sprague-Grundy values of subtraction games with 3 parameters. Recently, however, we greatly generalized these results, to fully characterize the complete sequences of SG-values, including both the periodic and the pre-periodic portions of the sequences. We have analyzed 72 PB of data about this problem, to verify this computational approach to the analysis of these games.