Back to Sprouts

3. Who wins?

To deal with this question completely, you must deal with the issue of graph isomorphism or topological equivalence so that you can discuss which graphs are really the "same". Two graphs are isomorphic if, loosely, by moving vertices and edges of one graph around, it can be made to look like the second graph without breaking any edges. Since Sprouts requires that the graphs are planar (edges do not cross) there is also the question of "inside" and "outside" which is not dealt with in graph isomorphism. For example, the following two graphs are isomorphic, but not equivalent with regard to Sprouts since in the second, the black vertices are "outside" and another move can be made.

As you consider which moves you make that are basically equivalent, realize that to start a game of Sprouts with any number of vertices, there are basically only two moves: to draw an edge between two vertices or to draw an edge from a vertex to itself. It does not really matter which vertices are used, since it is only the properties of attachment and "inside"/"outside" that are used. You can eventually build up a game tree similar to that given for two-vertex sprouts; although for larger games of Sprouts, this is a very large project. This game tree then can provide data to answer the questions.

  1. In the game of two vertex Sprouts, there are essentially 17 different ending games shown in the game tree. (Note that this count can vary depending on what one defines as "different". I have chosen that "inside"/"outside" choices at the end of the game which do not give different outcomes are essentially the same game.) Of these, 11 are won by the 1st player, so in playing randomly, it might appear that the 1st player has an advantage. Testing this experimentally is a good introduction to probability and the difference between experimental and theoretical probability. It may also lead you to decide that the choices made about "essentially different" games may not be the most accurate, as they may not reflect the way people think about their choices as they play the game. One could also figure out the theoretical probability by regarding all the vertices as labelled and not dealing with isomorphisms and get a very different probability.

  2. Analysis of the game tree for two-vertex Sprouts will show that the 2nd player actually has the winning strategy — that is, that you can make choices that guarantee that you win. One can analyze the game tree by starting from the bottom of the tree and paying attention to who has the choice leading to each result. For example, the first two results in the game tree result in the 1st player winning, so once the first graph in the 4th row is reached, any choice made allows the 1st player to win — even though the 2nd player makes the choice. However, at the next stage up, the series of choices to the right would

    result in the 2nd player winning, but the 1st player makes the choice, so you would choose the option to the left, rather than the option to the right, guaranteeing their win. Therefore, from the first graph in the 3rd row, the 1st player has the winning strategy. Working the way up the tree shows that the second player has a winning strategy. If the first player chooses to draw an edge from a vertex to itself in the first move, the 2nd player should choose to connect the vertices of the loop within the loop, since all results from this will result in the 2nd player winning. If the first player chooses to connect the two vertices with an edge in the first move, the 2nd player can then choose the 2nd or third options and from there make choices that will continue to result in his/her win.

These questions can be answered for larger games of Sprouts in the same way, but the data is somewhat unmanageable.