Left-Hand-Path Notation for Sprouts
This document describes how to write down a sprouts game in
left-hand-path (LHP) notation.
Preliminary Notions
- degree
- A spot's degree is the number of lines entering it.
- live spot
- A live spot is a spot of degree 0, 1, or 2.
- dead spot
- A dead spot is a spot of degree 3.
- touch
- A spot touches a region (and vice versa) if they are adjacent. Every spot touches at least one region, and every region touches at least one spot.
Every dead spot touches three regions, while a live spot can touch at most two regions.
- pier spot
- A pier spot is a spot of degree 2 that touches only one region.
- pivot spot
- A pivot spot is a spot of degree 2 that touches two regions. Each spot of degree two is either a pier spot or a pivot spot.
- initial spot
- An initial spot is a spot of degree 0. Each initial spot touches exactly one region.
- connected
- Two spots are connected there is a sequence of lines joining one to the other.
- region
- A region is a maximal contiguous area of whitespace. The game starts with one region that touches every spot.
- boundary
- A boundary of a region is a group of lines that separates the region from another region. More precisely, a boundary of a region consists of a maximal connected group of spots that touch the region. Every region has at least one boundary.
- enclosing move
- An enclosing move is a move that consists of drawing a line between two spots that were already on the same boundary. Figure 4 (below) illustrates an enclosing move; figure 3 does not.
Examples of Preliminary Notions
Consider Figure 1. There are 5 spots (a, b, c, d, and e) and 2 regions (X and Y). Spot e is a spot of degree 0. Spot a is a spot of degree 1. Spots b and d are spots of degree 2, and c is a spot of degree 3. Spots a, b, d, and e are live spots, while c is dead. Spot e is an initial spot.
Spots a, b, c, d, and e all touch region
X. Spots c and d also touch region Y.
Spots a, b, c, d are a connected group. Spot e forms a connected group by itself.
Region X has two boundaries: the boundary consisting of a, b, c, and d, and the boundary that consists of e alone. Region Y has only one boundary: the one that consists of c and d.
Spot b is a pier spot, spot d is a pivot spot, and spots a, e, and c are neither pier spots nor pivot spots.
Game Format
A game transcription for a normal game of n spots is prefixed by "n+", and a
game transcription for a misere game of n spots is prefixed by "n-". This
prefix is followed by the names of the participants in parentheses, with the
player moving first named first, and with an asterisk indicating the server.
Other provenance information optionally can be placed in the parentheses. The
postscript "I" indicates a win by Left, while "II" indicates a win by Right.
Thus "3+ (Steinitz - Morphy *) 1<4>1[2] I" is the complete score of a normal
game starting from three spots, proposed by Morphy, in which Steinitz chose to
move first and which Morphy resigned after seeing Steinitz's first move.
Move Format
A move in sprouts consists of drawing a line and placing a new spot on that
line. A move in LHP notation lists the sequence of spots that a robot would pass while walking along the newly-created line, keeping its left hand on the line.
For example, in Figure 2, the move creating spot g would be written down as e.f<g>h.i. (In these diagrams, a solid line indicates a pre-existing line, and a dashed line indicates the move being played.)
Spot g is always the "next spot number": the least positive integer not already used to number a spot on the graph before the new line was drawn. For example, in a game with 5 initial spots, the first move would have g = 6.
Suppose a line has just been drawn from f to h (possibly f = h), creating
new spot g. Imagine a miniature robot located in some
region of the graph and oriented so that if it were to put its left hand on f and walk forward keeping its left hand along the new line, the next spot it encountered would be g. The move may have divided an existing region into two regions: if so, call the region that the robot is in R, and call the other one L.
To write down the move, follow these 6 steps:
- If the move was an enclosing move or if f was a pier spot before the move, then consider the first spot the robot would reach when walking backward from f along the boundary without crossing any lines; if this spot is not equal to f, g, or h, then call it spot e and write "e.". Otherwise, write nothing for this step.
- Write "f<g".
- If nothing was written for step 1, f and h are both pivot spots that touch the same two regions (say P and Q, and suppose the line was drawn in P), R has only one boundary, and L touches at least one live spot that Q doesn't, then call this spot x, and write "@x". Otherwise, write nothing for this step.
- Write ">h".
- If h was a pier spot before the move, then consider the first spot the robot would reach after walking forward keeping its left hand along the boundary past f, g, and h without crossing any lines; call this spot i and write ".i". Otherwise, write nothing for this step.
- If f and h were on the same boundary before the new line was drawn, then choose a live spot from each other boundary in R, say a, b, c, ..., z and write "[a,b,c,...,z]". (These spots are listed with commas and dashes as needed, using dashes to indicate consecutively numbered spots. Thus [5,7,10-12] represents spots 5, 7, 10, 11, and 12.) If there are no such live spots, write nothing for this step.
Examples of Writing Moves
Figure 3 (above) shows a move for which only steps 2 and 4 result in anything being written.
Figure 4 shows a move in which only steps 2, 4, 5, and 6 result in anything being written.
Figures 5, 6, and 7 illustrate step 3.
Figures 8, 9 and 10 illustrate enclosing moves in which a line is drawn from a spot to itself.
Credits
Author: Josh Purinton
This document borrows liberally from the work of Applegate, Jacobson, and Sleator, Dan Hoey, and Danny Purvis.
Back to World Game of Sprouts Association Home Page
