Question

Draw the game tree for nim if the starting position consists of two piles with one and four stones, respectively. Who wins the game if both players follow an optimal strategy?

Short answer

First player wins

Step-by-step solution

Assigning the values

Nim game with \(1\) pile of \(1\) stone and \(1\) pile of \(4\) stones.

Each player can remove one or more stones from one pile on each turn.

The first player is represented by squares in the tree diagram, while the second player is represented by circles in the tree diagram.

We assign a+1 if the first player wins the game and a-1 when the first player loses the game.

Minimum and maximum of optimal strategy

To determine who wins the game when using optimal strategy, we determine the minimum or maximum at each internal vertex of which one already know all assigned values of its children. At vertices at level \(0\), we determine the maximum. At vertices at level \(1\), we determine the minimum. At vertices at level \(2\), we determine the maximum and so on.

One then notes that the root of the tree contains \({\bf{ + 1}}\), which means that the first player will win if both players use an optimal strategy.