How to play

Tired of playing tic-tac-toe to survive through a boring lecture?
Here is an interesting alternative you can try.

‘Sprouts’ is a pencil and paper game with interesting mathematical properties. It was invented by mathematicians John Horton Conway and Michael S. Paterson at Cambridge University in the early 1960s.

Rules of the game:

The game is played by two players, starting with a certain number of dots (called spots) drawn on a sheet of paper. Two players make alternate moves, which consists of connecting two dots (spots) with a curve and marking a new dot anywhere on this curve. The segments of curves connecting two dots are called edges. The game play can be summarized by the following rules:

1. No edge should intersect another edge.  (You cannot connect two dots if this current edge (current move) intersects any previously drawn edge)

2. No spot (dot) can have more than three lines attached to it. (Another way of saying it would be – max degree of any spot = 3)

3. A curve may connect a spot to itself. (i.e. – self loops are allowed but be careful with rule number 2. You cannot connect more than 3 lines to a dot)

The player who draws the last curve wins.

Let’s look at some examples to understand the rules.

Before that, some terms I have used:

Spot     =   dot     =   vertex

Curve    =   edge   =   line

Degree of a spot (/dot/vertex) = number of lines (edges) connected to it.

Current curve (/edge/line) refers to the curve drawn by a player as his move. If curves c1, c2 and c3 are drawn during a game in the 1^st, 2^nd and 3^rd move respectively then current curve just after 1^st move is finished and before the 2^nd move is made refers to c1. Likewise current curve after 2^nd move refers to c2 and current curve after 3^rd move refers to c3.

Let’s look at a sample game where the players (assume X & Y) start with 2 dots.

Play a few games of sprouts with someone to get the feel of it. You can start with a small number of initial dots (2-3) and increase gradually. You can also experiment and alter the rules to your taste.

It’s not necessary that one who makes the last move will win the game. You can make your own variations. You can reverse this rule to- one who will make the last move will lose. You can try other variations like – making a new dot on the current curve as optional (my fav).

I didn't like the idea of making a new dot on the current curve after every move. Here is what I do when I play with my friends – (assume X & Y are two players playing the game) If Y made a curve (say c1) in his current move then X has the power to decide if she wants to create a dot on c1. Likewise Y has the power to decide if he wants to make a dot on the current curve after X’s move.

This may seem to complicate things. In optimal play (optimal play means X, in her turn, will make a move such that it enhances her chances of winning. Likewise, in Y’s turn, he will make a move which enhances his chances of winning) before making a move the player has to decide if he/she should mark a dot on the current curve, how the outcome will change with/without the new dot, possible outcome(s) with/without new dot after his/her move … in short- a lot of computations in one’s head.

Complicated?

What is the fun in keeping things simple ;)

More about this variant and other variants in the next post

It will be good to try a few hands at the game before reading further.

Variants of the game

Modes of gameplay:

There are two modes of gameplay- normal play and misère play. In so called normal play, the player who makes the last move wins. In misère play, the player who makes the last move loses. It seems the 2 modes are exactly opposite of each other but the analysis shows that the game scenarios for the two mode are not related to each other.

There exists a pattern for outcome of the game as the number of spots increases in case of normal play. But no such pattern is discovered yet in the case of misère play.

Analyzing the game scenarios for different number of initial dots is a tedious job. As we saw in the sample game in previous post, X had 3 distinct options for her 1^st move. Then again Y had 6 distinct options for his turn. Thus if we consider all the possibilities (i.e. build a game tree) then we will have a large number of possible game scenarios (number of leaf nodes in the game tree) even for initial game size of 2 (i.e. for initial number of spots=2).

[ Let’s assume X & Y are playing and X makes the first move of the game.

  Let the number of initial spots be n. ]

Scientists have researched and found some interesting fact related to the gameplay.

They have found certain patterns in outcome of the game if both the players play optimally.

[ Here optimally means X, in her turn, will make a move such that it enhances her chances of winning.
  Likewise, in Y’s turn, he will make a move which enhances his chances of winning ]

For Normal Play:

// Spots = number of initial spots

//Normal Outcome = Result for the player who starts the game (X in our case)

Spots (n)	1	2	3	4	5	6	7	8	9	10	11	12	...
Normal Outcome	Loss	Loss	Win	Win	Win	Loss	Loss	Loss	Win	Win	Win	Loss	…

The result pattern for X is – L L W W W L and this repeats after every 6^th game.

In other words, X will win if number of initial spots (n) divided by 6 leaves remainder 3, 4 or 5, when X plays optimally. (i.e. when n % 6 = 3, 4 or 5)

For Misère Play:

// Spots = number of initial spots

//Misère Outcome = Result for the player who starts the game (X in our case)

Spots (n)	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	...
Misère Outcome	Win	Loss	Loss	Loss	Win	Win	Loss	Loss	Loss	Win	Win	Win	Loss	Loss	Loss	...

This mode of gameplay is more interesting because no definite pattern has been discovered yet.

Apart from the modes of gameplay there are other variants of the game:

•  Brussels Sprouts

This variant starts with a number of crosses, i.e. spots with four free ends. Each move involves joining two free ends with a curve (again not crossing any existing line) and then putting a short stroke across the line to create two new free ends. So each move removes two free ends and introduces two more. Despite this, the game is finite, and indeed the total number of moves is predetermined by the initial number of crosses: the players cannot affect the result by their play. With n initial crosses, the total number of moves possible = 5n−2.

So if n is odd, the player who starts the game wins and vice versa.

The outcome is fixed and not affected by playing style of the players.

Refer to this link for prove of number of moves in a game (= 5n-2).

Again this variant can be played in misère mode which will produce exactly opposite outcome as in normal play, i.e. – for odd n, the player who starts the game loses.

This variant can be made interesting we make the stroke on current curve optional. The number of moves will become variable in that case.

• Black and White Sprouts

This variant is similar to the one that is stated in my previous post. More analysis on that variant will be done later.

In this variant the player has an option to mark a new spot on current curve drawn by him/her.

In the variant stated in the previous post the player has the option to mark a new spot on the current curve drawn by his/her opponent, i.e. he/she has to mark a new spot on current curve before making his/her move. 

So although these two variant seem similar, this slight difference changes the game playing strategies completely.

Refer to this link for more info on black & white sprouts.

_________________________________________________________________________________

Now let’s have a look at another variant. Let’s call this version - ‘Sprouts 99’.

I didn't like the idea of making a new dot on the current curve after every move. Here is what I do when I play with my friends – (assume X & Y are two players playing the game) If Y made a curve (say c1) in his current move then X has the power to decide if she wants to create a dot on c1. Likewise Y has the power to decide if he wants to make a dot on the current curve after X’s move. Thus adding a new spot is possible but not mandatory. Also a player cannot add a new spot to his current spot. She/he can add a new spot only on the last move (curve) made by her/his opponent.

This may seem to complicate things.
In optimal play (optimal play means X, in her turn, will make a move such that it enhances her chances of winning. Likewise, in Y’s turn, he will make a move which enhances his chances of winning) before making a move the player has to decide if he/she should mark a dot on the current curve, how the outcome will change with/without the new dot, possible outcome(s) with/without new dot after his/her move … in short- a lot of computations in one’s head.

This actually makes things more complicated but that will lead to more interesting gameplay.

In sample game on the previous post we saw that there are a large number of unique game scenarios possible even for n=2.  This number increases exponentially as we increase the number of initial spots.

This was for normal sprout.

In sprouts99 after each move the player has the option to add/not add a new spot.  So for every move that was possible in normal sprouts we now have another move possible in sprouts99 (when we remove the new spot on current curve). So if p moves are possible after a turn in normal sprouts, 2p moves will be possible in sprouts99. Thus after every turn we have twice more options with us in sprouts99.

Hence the number of unique ways to play a particular game is exponentially more than what we had for the original sprouts game.

The next post consists of a general analysis and some facts about sprouts99.

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.  

Sprouts99: Analysis(continued)

Let the number of initial spots be n
Let the total number of move made in a game be m

Assume X & Y are playing.

 X makes the first move.

If m = 1.

X makes the first (and only) move and wins.

If m = 2.

X makes the first move. Then Y makes the last move and wins.

We see that if m is odd then X wins & vice versa.

But the number of moves possible for a given n is not fixed. It depends on the game playing strategies of the players. (Whether to mark a new spot or not, spots inside closed regions, etc)

Hence the strategy of each player should be to make the number of moves remaining after his/her move an even quantity.

If there are 2 moves left after X’ turn then X will win.
2 moves after X's turn: 1->Y, 2->X(last move). Winner = X

If there are 3 moves left after X’ turn then X will lose.
3 moves after X's turn: 1->Y, 2->X, 3->Y(last move). Winner = Y
_________________________________________________________________________________

It is not possible to compute the total moves remaining after one’s turn from the beginning of a game (even for small n) because after every move the other player has some options for his/her move.  For example if X makes a move and Y has the option to chose from, say, 8 possible moves… then each of these 8 possible moves will lead to other possibilities and so on. For each case the number of moves left after the turn may vary. Even if X is a super human and computes everything in his/her mind in reasonable time, it is not very useful. In general it is not possible for a normal person to do so much calculation. However it’s handy to start doing the math towards the end of the game when game tree has few possibilities left.

Some more analysis:

Let’s consider a game starting with n vertices. Let’s forget about the optional vertex for a while.

At the end of the game we have 3 edges/lines connected to each vertex. (ignoring closed regions) 

So total number of edges out of each vertex at the end of the game = 3n (max)

1 move consists of joining 2 vertices with an edge. (2 vertices share an edge)

So maximum moves possible = 3n/2
{
 at the end of the game we have a total of 3n edges out of all the spots. One move consists of adding one  edge to two spots. So that makes a cumulative total of 2 edges, added to the whole game per move.
 max edges for a game = 3n
 and we add 2 edges per move
 so max possible moves = 3n/2
}

This value gives us the max moves possible for a given n.
But the actual number of moves made in a game may be less than this value. This is because of loops and no intersection rule. Consider the example:

Here n = 4

3n/2 = 6

But game ends in 5 moves.

The total number of moves is less than 3n/2

We lose 1 move for every 4 vertices if we exhaust vertices within closed regions as shown above.

Thus the minimum moves possible = integer (3n/2) – integer (n/4)

We ignored the optional vertex for this calculation.

The players may not use the optional vertex at all. (and this is when we get the min value m)

Hence minimum number of moves(m) for a given n is integer (3n/2) – integer (n/4)

* Now let’s calculate the maximum moves possible for a given n:

For calculating the maximum moves possible we have to consider the optional vertices drawn after every move...we assume its drawn after every move because we will get more moves only when we add more spots.

We can treat each spot as having 3 lives (3 edges allowed to join to it)

So total lives in a game with n spots = 3n

At each move we take away 2 lives from the game. (one live each from the pair of spots used in the last move)

If the optional vertex is added after each move, this new vertex will have one life remaining. (because the new vertex already has 2 edges connected to it)

The optional vertex must be added after each move when considering the maximum possible moves.

So after each move we add 1 life(due to new spot) and take away 2 lives from the game.(from the pair of spots used in the last move)

Thus overall we take away 1 life from the game after each move. [ (+1) + (-2) = (-1) ]

After the last move total lives left in the game = 1. (due to new spot on the last curve)

We cannot make any moves now because we need at least 2 lives to make a move.

So maximum possible moves for a game with n initial spots = 3n-1
{
    total lives = 3n
    lives taken away in one move = 1
    `but no moves is possible when we have 1 life left after last move
    thus max possible moves = 3n-1
}

Examples will make it clearer:

//n = 1

// max number of moves = 3n – 1 = 3 – 1 = 2

//n = 3

// max number of moves = 3n – 1 = 9 – 1 = 8

_________________________________________________________________________________

Some interesting game scenarios:

·         

If the player chooses option 1, he/she will win.

If the player chooses option 2, he/she will lose.

·          

All the vertices with degree 3 can be ignored while considering a next move. These vertices are said to be dead.

If there is a vertex, V, with degree 2 is inside a closed region such that no other vertices are present inside the closed region or all the other vertices present inside this closed region reachable from V are dead then no moves can be made using V. It can be ignored for further computation.

The image shows equivalent scenarios [they will generate the exactly same outcome]

Connecting a given pair of vertices does not necessarily give rise to a unique scenario. Depending on the way the edge is drawn it may give different scenarios:

Contents of next post: Optimal solution for n=1, n=2 & n=3 

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:

Seems like player Y has an edge over player X… Is it?

May be making a game tree for n=4 will make things clearer.

But game tree for n=4 by hand… seriously?

Software Implementation

If n=1, 2, 3 Y will win, if plays optimally.

I believe the player who starts the game will always lose if both the players play optimally.

My reasoning behind it is as follows:

Minimum number of moves for a given n = integer (3n/2) – integer (n/4)

Maximum possible moves for a game with n initial spots = 3n-1

For n=4,

Minimum moves = 6 – 1 = 5

Maximum move = 12 – 1 = 11

For n=5,

Minimum moves = 7 – 1 = 6

Maximum move = 15 – 1 = 14

For n=7,

Minimum moves = 10 – 1 = 9

Maximum move = 21 – 1 = 20

For all n>=4, there is a reasonable margin between the minimum moves and maximum moves that can be made in a game.

Both X & Y will try to make the number of moves left(after their respective turn) an even quantity.

They will do so by creating closed regions and using (or not using) the new spot on opponent’s last move.

At any stage of the game both the players have equal liberty(on whether to add the optional vertex on opponent's last move) except at the first move.

When X makes the first move he/she cannot add a new spot because there is no curve drawn yet.

After X draws the first curve Y can decide whether to put a new spot on this curve.

X doesn’t have this option at the beginning of the game.

May be this one slight advantage can turn the game in Y’s favor, if he/she plays optimally.

We can find out only by computing the game tree.

I was trying to write a code that will compute the game tree and find out who wins if both players play optimally. But I could not figure out how to represent the stages of the game.

Initially I thought the spots & edges can be represented in form of graph but later on I discovered it was not possible to represent the stages of the game in form of graphs. The non equivalent scenarios shown in the previous post cannot be distinguished using graphs.

_________________________________________________________________________________

I find this game very interesting and am trying to build a game application where human will play against computer, and according to the difficulty level, the computer will analyze the game at each stage and make an appropriate move.

Developing the application will require graphics programming, nice algorithms to analyze the game after each stage, proper way to represent the data.

Here is what I have planned so far:

Each vertex can be represented as a node.

Whenever an edge is incident on it, its degree can be increased.

All the vertices with degree 3 can be ignored to limit computation.

False move (intersection of edges & degree exceeding 3) can be checked instantly, as soon as current curve crosses any previously drawn curve or is incident on an invalid vertex(already having degree=3)

After a move is made, we need to analyze and find out how many more moves are possible.

Computer’s strategy should be to make the number of moves left after its turn an even or odd quantity, depending on the difficulty level.

Taking a brute force approach and simulating all the possible moves that the computer can make to find which move is best will take too much time …and probably fail to execute in reasonable time even for small n.

The total moves can be approximated using the degree of vertices.

We compute the total possible moves after a move is made, without considering a new spot on this move.

Then we compute the total moves possible, taking into consideration the new spot.

We compare the results and decide whether to mark a new spot on the current spot.

An algorithm to compute the number of moves possible, given a game scenario:

Divide different regions, as shown here:

Different regions are shown in different

colors.

Let X = {set of all regions}

Algo:

1.       Unmark all the nodes having degree less than 3.

2.       Total_max_moves =0;

3.       Total_min_moves = 0;

4.       For each regions R in X

{

5.       Int y = (total unmarked nodes within R, including those on boundary) x 3 – (total degree of all these nodes)   

// y is total lives that can be used to make a move.

6.       Calculate max & min moves possible.

7.       If min moves is not a whole number then ignore the spots on the boundary of the region and recalculate y. Repeat this step till all spots on the boundary of the region are exhausted.

8.       Mark all the nodes used in computing y.

9.       Total_max_moves = Total_max_moves + max moves.

10.   Total_min_moves = Total_min_moves + min moves.

}

Using this we can compute the max & min moves left in the game.

But this value is of little use when n is large because difference between max & min moves will be too large and adding/not adding a new spot will not make much difference.

Yet, I will like to code this and see how it works.

I think making random moves initially to reduce the game size and using this algorithm towards the end of the game to calculate number of moves left should work fine. I will know only after I code it.

Here is another approach I have thought of:

I already have the optimal moves for small n(for n=1,2,3). I will store these configurations in the code.

First the computer will try to bring the game to a configuration that is already stored in the code.

Then it will use the optimal moves to win the game.

For this I will need algorithms to detect equivalent scenarios.

I am still working on it.