A convergence technique for the game i ​ -Mark i\textsc{-Mark}

Gabriel Nivasch, Oz Rubinstein · 2025

Read A convergence technique for the game i ​ -Mark i\textsc{-Mark} by Gabriel Nivasch, Oz Rubinstein (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-23196.txt.

Introduction

Gabriel Nivasch and Oz Rubinstein study a number game in a 2025 paper. The game i-Mark lets a player cut a pile by a set amount or divide it by a set factor, if the division is exact. The last player to move wins. Past work solved many cases where only one division factor was allowed.

The authors give a convergence technique for the harder cases with more than one divisor. It yields polynomial-time algorithms for the Sprague-Grundy values of many such games. They prove it works for all games with a step of one and two divisors. Dynamic programming sits at the core of the method.

Catalog record

CREATORGabriel Nivasch, Oz Rubinstein
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE27 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-23196

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A convergence technique for the game i ​ -Mark i\textsc{-Mark} Gabriel Nivasch, Oz Rubinstein Abstract The game of i ​ -Mark i\textsc{-Mark} is an impartial combinatorial game introduced by Sopena (2016). The game is parametrized by two sets of positive integers S S , D D , where min ⁡ D ≥ 2 \min D\geq 2 . From position n ≥ 0 n\geq 0 one can move to any position n − s n-s , s ∈ S s\in S , as long as n − s ≥ 0 n-s\geq 0 , as well as to any position n / d n/d , d ∈ D d\in D , as long as n > 0 n>0 and d d divides n n . The game ends when no more moves are possible, and the last player to move is the winner. Sopena, and subsequently Friman and Nivasch (2021), characterized the Sprague–Grundy sequences of many cases of i ​ -Mark ​ ( S , D ) i\textsc{-Mark}(S,D) with | D | = 1 |D|=1 . Friman and Nivasch also obtained some partial results for the case i ​ -Mark ​ ( { 1 } , { 2 , 3 } ) i\textsc{-Mark}(\{1\},\{2,3\}) . In this paper we present a convergence technique that gives polynomial-time algorithms for the Sprague–Grundy sequence of many instances of i ​ -Mark i\textsc{-Mark} with | D | > 1 |D|>1 . In particular, we prove our technique works for all games i ​ -Mark ​ ( { 1 } , { d 1 , d 2 } ) i\textsc{-Mark}(\{1\},\{d_{1},d_{2}\}) . Keywords: Combinatorial game, impartial game, Sprague–Grundy function, convergence, dynamic programming. 1 Introduction The game i\textsc{-Mark} is an impartial combinatorial game introduced by Sopena [ 6 ] . The game is parametrized by two sets of positive integers S and D , where \min D\geq 2 . A position in the game is given by a single natural number n . There are two players, and in each turn, a player can move from position n to position n-s for for some s\in S (assuming n-s\geq 0 ), or to position n/d for some d\in D , if n/d is a positive integer. The game ends when no more moves are possible. As usual in the theory of impartial games, in normal play the last player to move is the winner (or in other words, the player with no legal moves is the loser). For example, in the game i\textsc{-Mark}(\{1\},\{2,3\}) , starting from position 10 , the first player can move to position 9 or 5 . If she moves to position 9 , then the second player can move to position 8 or 3 , and so on. The player who moves to position 0 will be the winner. 1.1 The Sprague–Grundy theory of impartial games An impartial game is a two-player game in which there is perfect information, there is no chance involved, and, from each position, the legal moves available are the same for both players (see e.g. Conway [ 2 ] , Berlekamp et. al [ 1 ] ). An impartial game can be represented by a directed acyclic graph G=(V,E) , where each position in the game is represented by a vertex, and each legal move from one position to another is represented by an edge. We assume that the game is well-founded , i.e. from no position in the game there exists an infinite sequence of moves. We say that position v is a follower of position u if one can get from position u to position v in one move. In an impartial game, positions are classified into P -positions (in which, with perfect play, the previous player to have moved is the winner), and N -positions (in which, with perfect play, the next player to move is the winner). P - and N -positions are characterized recursively as follows: If all the followers of position v are N -positions, then v is a P -position. Otherwise (if v has at least one follower which is a P -position), then v is an N -position. The base cases of this characterization are the sinks , or positions with no followers, which are P -positions. Let G_{1}=(V_{1},E_{1}) and G_{2}=(V_{2},E_{2}) be two impartial games. Their sum G^{\prime}=G_{1}+G_{2} is the impartial game played as follows: Each position of G^{\prime} consists of a pair of positions v_{1}v_{2} with v_{1}\in V_{1} and v_{2}\in V_{2} . On each turn, a player chooses one of the games G_{1} , G_{2} and plays on it, leaving the other game untouched. The game ends when no moves are possible on G_{1} nor on G_{2} . Formally, G^{\prime}=(V^{\prime},E^{\prime}) where \displaystyle V^{\prime} \displaystyle=V_{1}\times V_{2}, \displaystyle E^{\prime} \displaystyle=\{(v_{1}v_{2},w_{1}v_{2}):(v_{1},w_{1})\in E_{1}\} \displaystyle\qquad\cup\{(v_{1}v_{2},v_{1}w_{2}):(v_{2},w_{2})\in E_{2}\}. In order to know whether a position v^{\prime}=v_{1}v_{2} in the game G^{\prime} is a P - or an N -position, it is not enough to know whether v_{1} and v_{2} are P - or N -positions: It can be shown that by induction that, if both v_{1} and v_{2} are P -positions, then v^{\prime} is a P -position, while if exactly one of v_{1},v_{2} is a P -position, then v^{\prime} is an N -position. However, if both v_{1},v_{2} are N -positions, then v^{\prime} could be either a P - or an N -position. The Sprague–Grundy function (or Grundy function for short) enables us to correctly play sums of impartial games (Sprague [ 7 ] , Grundy [ 4 ] ). Denote {\mathbb{N}}=\{0,1,2,\ldots\} . Let G be an impartial game. To each position v of G let us assign a Grundy value \mathcal{G}(v)\in{\mathbb{N}} recursively as follows: \mathcal{G}(v)=\mex{\{\mathcal{G}(w):\text{$w$ is a follower of $v$}\}} . Here \mex S=\min({\mathbb{N}}\setminus S) denotes the minimum excluded value . Then, the following two properties can be proven by induction: • We have \mathcal{G}(v)=0 if and only if v is a P -position. • If v^{\prime}=v_{1}v_{2} is a position in the game G^{\prime}=G_{1}+G_{2} , then \mathcal{G}(v^{\prime})=\mathcal{G}(v_{1})\oplus\mathcal{G}(v_{2}) , where \oplus is the nim-sum , or bitwise-XOR, operation (so for example 3\oplus 5=011_{2}\oplus 101_{2}=110_{2}=6 ). Hence, by knowing the Grundy function of an impartial game we can correctly play this game, as well as the sum of this game with any other impartial game we also know the Grundy function of. Since the “sum of games” operation is commutative and associative, as is the nim-sum operation, the Sprague–Grundy function enables us to play sums of an arbitrary number of games. 1.2 Previous work on i\textsc{-Mark} Let i\textsc{-Mark}(S,D) be a fixed i\textsc{-Mark} game. Suppose we are given an integer n , and we want to find the value of \mathcal{G}(n) . The naive way of doing this is to compute the entire sequence \mathcal{G}(0),\mathcal{G}(1),\ldots,\mathcal{G}(n) from the bottom up. This approach takes time and space \Theta(n) . However, since the input size is \log_{2}n , this naive algorithm takes time and space that is exponential in the size of the input. To solve a particular instance i\textsc{-Mark}(S,D) means to find a polynomial-time algorithm that, given a position n , returns \mathcal{G}(n) . This can be done by identifying a pattern in the Grundy sequence of the game (for example, all i\textsc{-Mark} games with D=\emptyset are eventually periodic), or by some other method. Sopena [

Read the complete text