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:
- Each vertex can have at most three edges coming from it
- 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!)
- 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
- 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
- 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:
- 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?)
- 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