Sprouts is a paper-and-pencil game where two players take turns
connecting sprouts and adding a new sprout along the connection. The player
who makes the last move wins. The game of Sprouts is an impartial
combinatorial game and thus by Sprague-Grundy theorem equivalent to a game of
Nim.
Planar graphs are the basis for a computer representation of
Sprouts. Combinatorically, a game is a planar graph with sprouts as its
vertices and moves as its edges. In addition, player's moves also have
geometric components. Each move is a sequence of Bézier
splines.
Our contribution is the cobweb. A cobweb is comprised of the virtual edges which
connect the initial sprouts into a spanning tree. The cobweb guarantees
uniqueness of moves by maintaining a connected structure.
As part of this work, a multi-platform application for playing Sprouts
has been developed.
|
