SprOuTs: Optimal Solution

Optimal Solution for n = 1, 2, 3.

(Assume: X & Y are the players. X makes the first move)

In all the three cases Y wins, if both play optimally.

Let’s analyze the game tree (tree structure showing all the possible moves at any stage of the game) for small values of initial spots and deduce who wins if both the players play optimally.

N = 1

The game tree is small and we see that Y will win if both the players (X & Y) play optimally.

N = 2

Building the game tree for one initial spot was a cake walk.

Just add one more spot and try to generate the game tree.

Adding even one spot opens up a large number of options at each stage of the game. The size of game tree for n = 2 is unbelievably large when compared to that for n = 1.

Here is the game tree for n = 2 (redundant nodes at some levels are not shown to limit its size)

An approximate analysis of the game tree for n = 2

Number of unique ways to play the game = 968 (roughly)

If both the players make random moves,

Probability of Y winning = 464/968 = 0.48 (approx)

Probability of X winning = 504/968 = 0.52 (approx)

On analyzing the game tree we find that there is a lot of redundancy. Also there are many equivalent configurations in the whole tree.

The redundant calculation can be done only once, when calculating the optimal solution.

Equivalent configurations can be identified and result of one such configuration can be used to solve others.

We know the optimal solution for n = 1. Whenever the game is at a stage such that it can be reduced to an equivalent configuration of n = 1, we can stop further computation. Likewise even within the game tree for n = 2 there are many equivalent configurations. If one configuration is solved we can use its result, every time an equivalent configuration is encountered.

Generating the game tree for n = 3 is a tedious task.

I used the results of n = 2 and successfully computed the optimal solution for n = 3.

The set of optimal moves for Y, for n= 1, 2, 3, are shown in the following images: