2012/01/16 by Urban Larsson, Larsson, Urban
Computer Science · Social Sciences · #Artificial Intelligence in Games #Digital Games and Media #Computability, Logic, AI Algorithms
paper · pdf · doi:10.48550/arxiv.1201.3350
We study variations of classical combinatorial games on two finite heaps of tokens, a.k.a. subtraction games. Given non-negative integers p1,q1, p2,q2, where p1q2 > q1p2, p1>0 and q2>0, two players alternate in removing (m1,m2)≠ (0,0) tokens from the respective heaps, where the allowed ordered pairs of non-negative integers are given by a certain move set (m1,m2)∈\M. There is a restriction imposed on the allowed heap sizes (X, Y), they must satisfy Xq1≤ Yp1 and Yp2≤ Xq2. A player who cannot move loses and the other player wins. For a certain restriction of these games, namely where each allowed move option (m1,m2) is of the form (sp1+tp2,sq1+tq2), for some ordered pair of non-negative integers (s,t)≠ (0,0), we show that all games have equivalent outcomes via a certain surjective map to a canonical subtraction game. Other interests in our games are various interactions with classical combinatorial games such as Nim and Wythoff Nim.