A PSPACE-complete graph nim
Kyle W. Burke, Olivia George · 2019
We build off G. Stockman's game NIMG to create a version named NEIGHBORING NIM. By reducing from GEOGRAPHY, we show that this game is PSPACE-hard. The games created by the reduction share strong similarities with UNDIRECTED (VERTEX) GEOGRAPHY and regular NIM, though these are both solvable in polynomial-time. This application of graphs can be used as a form of game sum with any rulesets, not only NIM. 1. Background 1.1. Algorithmic combinatorial game theory. Most of the results here revolve around the computational complexity of determining which player has a winning strategy from a given game position. There exist faster algorithms to solve this problem for some rulesets than for others. For each ruleset, we consider the computational problem that could be solved by such an algorithm. We will refer to both the ruleset and problem by the same name. We strongly encourage readers unfamiliar with these topics to refer to [1]. 1.2. Terminology. A small amount of nonstandard terminology is used: • We use the word sticks to refer to the objects in nim heaps. Thus, a nim heap of size six contains six sticks. • An optimal sequence set is a set of sequences of plays for both players such that any move deviating from all of the sequences results in an _-position (meaning, the _ext player has a winning move). No move in that sequence should be nonoptimal for either player. Thus, if a player does not know whether they have a winning strategy, adhering to an optimal sequence is at least as good as any other move. 1.3. NIM. NIM is an impartial game played on a collection of heaps, each with a nonnegative number of sticks. On a player's turn, they choose a nonempty pile and remove as many sticks as desired (at least one) from that pile. A player loses when they cannot remove sticks (all piles are empty). NIM is a classic impartial game, being the basis of Nimbers and Sprague– Grundy theory [8; 5]. NIM has lots of nice properties, from easy evaluation of games to obvious composition of two NIM games (the sum is just a new NIM game).