Optimal Strategies On Small Nim Games

In Guy and Nowakowski’s Unsolved Problems in Combinatorial Games,the following entry is found:"David Gale would like to see an analysis of Nim played with the option of a single pass by either of the players,which may be made at any time up to the penultimate move.It may not be made at the end of the game.Once a player has passed,the game is as in ordinary Nim.The game ends when all heaps have vanished."This paper mainly studies the above problem based on Small Nim games.There are N piles of counters.The players take turns in sequential unchanging order.Each player at his turn removes any positive integer of counters from the smallest pile.Firstly,we generalize Small Nim Games from 2-player to n-player.Then we get Multi-player Small Nim Games.When the number of players is equal or greater than piles,we determine all game values for all possible positions.We also analyze certain cases of positions when the number of players is smaller than piles.Secondly,we generalize Multi-player Small Nim Games by adding s pass options.Then we get Multi-player Small Nim with Passes.The game values are determined for infinitely many triplets(N,n,s)i.e.the number of piles,players and passes.Thirdly,we generalize Multi-player Small Nim with Passes by generalizing the pass options.We determine the game values of many positions with SAM.In the last,we study Ring-Bounded Small Nim Games.The set of all P-positions is determined under the normal play convention.