Back to Graph Theory

How to play Sprouts (January 8, 2004)

Rules

Start with a few dots (vertices). For the first few games, start with 2-4 vertices. Players take turns connecting two vertices with a curve (edge) and placing a new vertex along this edge. This is done following two rules:

  1. Each vertex can have at most three edges coming from it
  2. Edges must be drawn so that they do not cross or touch any other vertices than the two they are connecting

If a player is not able to draw an edge according to the rules, the other player wins. NOTE: you can draw an edge connecting a vertex to itself, such as:

A game might start like:

Play a few games and then check out the questions below!


Questions

(not all questions have final answers!)

  1. What can the ending look like? The degree of a vertex is how many edges go to the vertex. Can you play a game so that each vertex ends up with degree 3? Can you play a game that ends with two degree 2 vertices? Three degree 2 vertices? A degree 1 vertex? Can you describe all the possible sets of degrees a game can end with?

    Answer

  2. Does it end? Can you play a game that never ends -- that is, that both players can draw edges indefinitely? Why or why not? If you start with x vertices, is there a minimum number of vertices the game must have at the end? A maximum number?

    Hint

    Answer

  3. Who wins? For a certain number of starting vertices, does it matter which player goes first? Do certain games always go to one player or the other? Note that there are two ways to think about this question:
    1. Do players have an equal probability of winning if they are just making random moves? You can experimentally test this by playing lost of games starting with the same number of vertices and seeing who wins. Is there a way you can decide theoretically? (How many different ends to a game of 2-vertex Sprouts are there?)
    2. Can one player always choose moves that result in him/her winning? If one player can, we say that player has a winning strategy. You might try to find a winning strategy for Sprouts starting with two vertices.

    Answer

Challenge: Brussel Sprouts is a version of Sprouts where the only change is that the second rule reads "Each vertex can have at most four edges coming from it." Can you answer the above questions for Brussel Sprouts?

Answer

Two-vertex Sprouts Game Tree

Other Links*

* These links are for informational purposes only and are from sources outside MEC and Cornell University