1
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Mark Wildon
    Commented Dec 30, 2021 at 11:06

2 Answers 2

Reset to default
3
$\begingroup$

You ask "Is there any winning strategy for such a game?" The answer is positive: every game where (a) players move alternately, (b) the game ends after a finite number of rounds, and (c) the outcomes are either a win for player 1 or a win for player 2, is determined: one of the players has a winning strategy. This is a consequence of Zermelo's Theorem. Even if the game is possibly infinite, as soon as the winning set of player 1 is Borel measurable (and any winning set that you can describe in words is Borel measurable) is determined. This is a consequence of a result of Martin (1975).

Improve this answer
$\endgroup$
1
  • $\begingroup$ "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. $\endgroup$
    – Noah Schweber
    Commented Dec 30, 2021 at 22:55
0
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .