SprOuTs99

Analysis

(We shall limit the discussion and analysis to sprouts99 from now on)

Let us play around with the rules of the game and see what happens.

The rules for Sprouts99 are:

• Max degree of any vertex(/dot/spot) = 3
• No edge should intersect
• A player may add a vertex(/dot/spot) on his/her opponent's last move

The player who makes the last move wins.

Let’s change rule 1 and analyze.

Let the max degree of any vertex be e

Let the number of initial spots be n

Let the number of move made in a game be m

Assume X & Y are playing.

 X makes the first move.

When e = 1

Only one line can connect to a vertex.

This cancels out the option of adding a new spot on opponent’s last move because degree of new spot drawn on a current spot is 2. But max degree allowed is 1.

We cannot create any closed regions (including self loops) because to create closed region we need vertices with degree 2 (or more).

So the total number of moves for a game is fixed.

One move exhausts 2 vertices.

If n is odd, then one vertex is left at the end of the game when no more moves are possible.

The total number of moves possible in a game, m = n/2

If m is odd X will win

If m is even Y will win

The outcome of the game can be given by the equation:

O = (Integer (n/2)) % 2

If O = 1, X wins

If O = 0, Y wins

//this image shows last move for different n

         n = 2                       n = 4                      n = 4                       n = 5                        n = 5

When e = 2

Two lines can connect to a vertex.

This again cancels out the option of adding a new spot on opponent’s last move because degree of new spot drawn on a current spot is already 2. So adding a new spot is useless.

We can create closed regions and self loops but this does not affect the number of moves possible in a game in any way. This is because – It is not possible to have total degree inside a closed region as an odd quantity. The total degree of vertices inside a closed region must be an even number or zero. This follows from the no intersection rule.

Vertices with degree = 2 are useless and can be ignored

All the vertices with degree = 0 inside a closed region can be seen a sub game of smaller size.

All the vertices with degree = 1 are found in pairs. Total moves possible due to these pairs = total number of such pairs.

As e = 2, we can associate 2 lives with each vertex.

So total lives for a given n = 2n

One move takes away 2 lives

So total moves possible in a game, m = 2n/2 = n

The total number of moves for a game is fixed.

(Because adding a new spot is useless & closed regions do not affect the game play)

If m is odd X will win

If m is even Y will win

The outcome of the game can be given by the equation:

O = n % 2

If O is odd, X wins

If O is even, Y wins

//For a given n, the number of moves possible is always same (= n)

//Different last move scenarios for n = 3

When e >= 4

Game continues forever…

This is because a new spot can be added to opponent’s last move and a self loop can be drawn in this spot. Now degree of this spot = 4, which is valid. This can be repeated at each turn.

Hence when e = 1 & e = 2, the outcome is predefined and cannot be changed by the nature of game play. Playing sprouts with e = 1 or 2 will not produce any interesting game play.

With e>=4 the game will never end.

When the max degree of a vertex (e) is restricted to 3, the game is guaranteed to end after finite moves and the outcome cannot be predicted easily.

We analyze this case in the next post.