Question

Suppose that in a variation of the game of nim we allow a player to either remove one or more stones from a pile or merge the stones from two piles into one pile as long as at least one stone remains. Draw the game tree for this variation of nim if the starting position consists of three piles containing two, two, and one stone, respectively. Find the values of each vertex in the game tree and determine the winner if both players follow an optimal strategy.

Short answer

Player \({\bf{1}}\) can win the game if he moves to the position \(\left( {{\bf{2 2}}} \right)\).

Step-by-step solution

Define the values of all vertices in a game tree in a way that enables us to determine the outcome of this game when both players follow optimal strategies

By a strategy mean a set of rules that tells a player how to select moves to win the game. An optimal strategy for the first player is a strategy that maximizes the payoff to this player and for the second player is a strategy that minimizes this payoff. We now recursively define the value of a vertex.

One shall draw the game tree for the nim game.

If the beginning position contains three piles containing two, two, and one stone, respectively. Also have to find values of every vertex within the game tree and determine the winner if both players follow an optimal path.

One is only considering the paths only the player moves in which he has a chance to win. A player will never opt to make a move that produces the following cases:

1) Two piles with one pile have\({\bf{1}}\)stone and another greater than\({\bf{1}}\), because in the next move if the other player removes a greater pile, then the other player wins.

2) One pile with more than\({\bf{1}}\)stone. In this case also if the other player removes all the stones except the last one, he wins.

The paths to these two cases can be considered suicidal and we will not consider these paths in the tree.

Note that a vertex with no children except suicide moves is a win for whoever is not moving at that point.

For example, from the node \(\left( {{\bf{2 2}}} \right)\).

Final conclusion, calculate the values of each internal node using the rule as follows:

The possible moves are \(\left\{ {{\bf{4, (3}}\,{\bf{0,2, }}\left( {{\bf{1 1}}} \right){\bf{, }}\left( {{\bf{1 2}}} \right)} \right\}\) and all are suicidal for player \({\bf{1}}\) (So the node contains only suicidal children for player \({\bf{1}}\)) and assume that he will not choose anyone of these. In this case, we can consider it as a win for player \({\bf{1}}\). That is why we are putting \({\bf{ + 1}}\) as the value of this node.

Now calculate the values of each internal node using the rule as follows:

For an internal node an even level the value is the maximum of the values of its children. For an enclosed node within the odd level, the worth is the minimum of values of its children.

It follows that player \({\bf{1}}\) can win the game if he moves to the position \(\left( {{\bf{2 2}}} \right)\).

A player is allowed to combine stones from two piles also if the player combines stones from piles \({\bf{1}}\) and \({\bf{3}}\), the new arrangement becomes \(\left( {{\bf{3 2}}} \right)\).

Similarly, from\(\left( {{\bf{2 1 1}}} \right)\)we get\(\left( {{\bf{2 2}}} \right)\)if the player combines stones from piles\({\bf{2}}\)and\({\bf{3}}\).

Hence, Player 1 can win the game if he moves to the position\(\left( {{\bf{2 2}}} \right)\).