# Do restricted Nim-like games have winning strategies?

Considering a Nim-like game to be:

1. There are three piles $$A,B,C$$, and the amount of their elements are $$|A|=2, |B|=5, |C|=6$$;
2. There are 2 players. Each time a player can either take $$x (1\leq x \leq 3)$$ elements from a single pile, or, take the same amount of elements (more than 0) from each pile;
3. The player who takes the last element wins.

Is there any winning strategy for such a game?

Are there any computational methods to decide if a status is a must-win status?

• Some background: there is a general theory of impartial games (impartial means that the move set depends only on the position, not on who is to play) that gives every game a nim-value; this can be computed using the mex-rule (minimum excluded value). A position is a next-player win (N-position) if and only if its nil-value is non-zero. Your game is a restricted version of Whytoff's game in which at most $3$ stones can be taken when a player moves in a single pile, so it might be possible to analyse the nim-values using similar methods. Dec 30, 2021 at 11:06

• "any winning set that you can describe in words is Borel measurable" is a bit strong - I think it's easy to describe $\Pi^1_1$ winning conditions, for example, and those need not be determined. Dec 30, 2021 at 22:55
This is a restricted version of a game that Tanya Khovanova and Joshua Xiong call odd CM-Nim in Cookie Monster Plays Games, The College Mathematics Journal, 48:4 (2015) 283-293. In their version, you can take any positive number of elements from any one pile or the same positive number from all three piles (or generally any collection of an odd number of piles). Interestingly, the $$\mathscr{P}$$ positions (see Mark Wildon's comment) for this odd CM-Nim with $$k$$ piles are the same as the $$\mathscr{P}$$ positions for standard Nim with $$k$$ piles (their Theorem 6).
For your version restricting the number of elements that can be taken in a turn, the analysis is different. With 126 states, it's feasible to work out the $$\mathscr{P}$$ positions by hand. To get started, the $$\mathscr{N}$$ positions where the next player can win (i.e., move to $$(0,0,0)$$) in one move are $$(1,0,0), (2,0,0), (0,1,0), (0,2,0), (0,3,0), (0,0,1), (0,0,2), (0,0,3), (1,1,1), (2,2,2).$$ One description of $$\mathscr{P}$$ positions is that every possible move from a $$\mathscr{P}$$ position goes to an $$\mathscr{N}$$ position. You can see that every possible move from each of $$(1,1,0), (1,0,1), (0,1,1), (0,4,0), (0,0,4)$$ goes to a state in the previous list of $$\mathscr{N}$$ positions, so these five positions join $$(0,0,0)$$ as $$\mathscr{P}$$ positions. To start the next round of $$\mathscr{N}$$ positions, $$(2,1,0), (1,2,0), (1,3,0), (1,4,0), (1,1,2), (1,1,3), (2,2,1)$$ can go to the $$\mathscr{P}$$ position $$(1,1,0)$$ in one move. Etc. (Typically, there are fewer $$\mathscr{P}$$ positions than $$\mathscr{N}$$ positions.)
Eventually this "backwards induction" will put the initial state $$(2,5,6)$$ in one of the lists, telling you whether the initial position is a first or second player win. The $$\mathscr{P}$$ positions also describe optimal play: when it's your turn, move to a $$\mathscr{P}$$ position if possible.