2012/07/03 by Urban Larsson, Larsson, Urban, Johan Wästlund +1
Computer Science · Mathematics · #91A46 #Artificial Intelligence in Games #Combinatorics (math.CO) #FOS: Mathematics #Logic, programming, and type systems #math.CO #msc:91A46 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1207.0765
29 pages, 12 figures
arxiv created 2012/07/03 · openalex publication_date 2012/07/03 · arxiv updated 2012/07/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
New combinatorial games are introduced, of which the most pertinent is Maharaja Nim. The rules extend those of the well-known impartial game of Wythoff Nim in which two players take turn in moving a single Queen of Chess on a large board, attempting to be the first to put her in the lower left corner. Here, in addition to the classical rules a player may also move the Queen as the Knight of Chess moves. We prove that the second player's winning positions of Maharaja Nim are close to the ones of Wythoff Nim, namely they are within a bounded distance to the lines with slope (√(5)+1)/(2) and (√(5)-1)/(2) respectively. For a close relative to Maharaja Nim, where the Knight's jumps are of the form (2,3) and (3,2) (rather than (1,2) and (2,1)), we also demonstrate polynomial time complexity to the decision problem of the outcome of a given position.