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