Winning strategies for aperiodic subtraction games

DOI10.1016/J.TCS.2011.11.025zbMATH Open1233.91055arXiv1108.1239OpenAlexW2963033792MaRDI QIDQ764378FDOQ764378

Authors: Alan Guo 

Publication date: 13 March 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: We provide a winning strategy for sums of games of MARK-t, an impartial game played on the nonnegative integers where each move consists of subtraction by an integer between 1 and t-1 inclusive, or division by t, rounding down when necessary. Our algorithm computes the Sprague-Grundy values for arbitrary n in quadratic time. This solves a problem posed by Aviezri Fraenkel. In addition, we characterize the P-positions and N-positions for the game in mis`ere play.

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

Recommendations

• \(i\)-\textsc{Mark}: a new subtraction division game
• Some \(i\)-\textsc{Mark} games
• Aperiodic subtraction games
• Faster evaluation of subtraction games
• scientific article; zbMATH DE number 7306576

zbMATH Keywords

complexityaperiodicitycombinatorial gamessubtraction games

Mathematics Subject Classification ID

Combinatorial games (91A46)

Cites Work

• Aperiodic subtraction games
• Title not available (Why is that?)
• Partizan octal games: Partizan subtraction games

Cited In (11)

• \(i\)-\textsc{Mark}: a new subtraction division game
• Title not available (Why is that?)
• Aperiodic subtraction games
• Title not available (Why is that?)
• Atomic weight calculus of spindly games
• An exact quantum algorithm for a restricted subtraction game
• The self-referential impartial game Minnie
• Title not available (Why is that?)
• Some \(i\)-\textsc{Mark} games
• Superlinear period lengths in some subtraction games
• Faster evaluation of subtraction games

This page was built for publication: Winning strategies for aperiodic subtraction games

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