From: Dan Hoey <haoyuep@aol.com>
Subject: Sprouts notation
To: geometry-research@mathforum.com
Date: 27 Dec 00 21:27:37 -0500 (EST)
Here are the elements of Sprouts notation I have developed in
response to the discussion earlier this month under the "Game of
Sprouts" topic in geometry-research.
Element 0: Terminology
The number of lines entering a spot is called the spot's "degree".
Degree zero, one, and two spots are called "live" spots; the degree
three spots are "dead".
The lines entering a spot divide the spot into "sites". A spot of
degree zero or one forms a single site. Degree two spots have two
sites and degree three spots have three sites. A degree two spot is
called an "eye spot" if its sites are in separate regions. If both
its sites are in the same region, it is called a "pier spot".
The sites in a region that are connected to each other form a
"boundary." We list the sites of a boundary in "left-hand order,"
the order in which a miniature robot within the region would
encounter them walking forward along the boundary with its left hand
on the boundary. If the boundary surrounds the region, this is
clockwise order. If the region surrounds the boundary, left-hand
order is counterclockwise.
Element 1: Basic position notation
In an N-spot Sprouts game, the initial N spots are numbered 1,2,...,N
and the spots added in the course of the game are numbered starting
at N+1. Each boundary is written as a list of the spot numbers of
its sites in left-hand order, starting at an arbitrary site and
separated by commas. Each region is represented as a list of its
boundaries separated by semicolons. Finally, the region
representations are listed separated by slashes.
1--6---5 Example: This position can be written
| 9 1,6,8,7,4,7,3,9,3,7,8,6,5,6;2/3,9.
8 / \ 2
| \ / Element 2 describes how to abbreviate
4--7------3 this as 1,8,4,9t,8,5;2.
Element 2: Abbreviating position notation
The position notation may be abbreviated by omitting dead spots. If
a degree one spot has all other spots on its boundary deleted it must
be marked with an "o" to distinguish it from a degree zero spot. Any
region with fewer than two live spots may be omitted, but eye spots
listed in only one region must be marked with a "t" to distinguish
them from degree one spots. If the two sites of a pier spot become
adjacent, the pier spot may be listed once, marked with a "t". An
example of the abbreviation appears in the previous example.
It is possible to specify a move in Sprouts by providing the full
position after the move--in fact, the full position notation provides
a complete history of a game. You can see this by using the position
notation to draw the game in pencil, then inking it in one move at a
time. However, it is helpful to be able to specify a move more
concisely, and I describe how to do so below.
Element 3: Basic move notation
A move that connects spot A to spot B, creating spot C in the middle,
is written A-C-B, perhaps with additional notations. By convention,
the lower-numbered endpoint is listed first. The direction of the
move, from A to B, determines one site of C as a "left" and the other
as "right". When listing sites in left-hand order, A is listed after
the left site of C and B is listed after the right site of C. When A
and B are the same spot, this determination is ambiguous, the left
site is taken to be the one accessible to other sites on A's
boundary, if any.
______ Example: The position 1,3,2,4,2,3/2,4 is
(l) / \ created by the moves 1-3-2; 2-4-2. The
1--3--2 (r) 4 (l) first 3 refers to the right site of spot 3,
(r) \______/ and the second 3 refers to the left site.
Element 4: Specifying sites for pier spots
When an endpoint of a move is a pier spot, it is necessary to specify
which site is being connected. This is done by suffixing ".N", where
N is the number of the first live spot appearing after the site in
left-hand order. Just as A is written on the left and B on the right
in the move move A-C-B, the left site is C.A and the right site is
C.B, unless A or B becomes dead after the move. (We avoid using
dead spots to specify sites because they would not appear in the
abbreviated position).
(5.1) Example: After 1-5-2; 3-6-4, there are four ways of
1---5---2 connecting spots 5 and 6, leading to the following
(5.2) four abbreviated positions:
Move 5.1-7-6.3 yields position 1,2,7,3,4,7.
(6.3) Move 5.1-7-6.4 yields position 1,2,7,4,3,7.
3---6---4 Move 5.2-7-6.3 yields position 1,7,3,4,7,2.
(6.4) Move 5.2-7-6.4 yields position 1,7,4,3,7,2.
Element 5: Specifying boundary separations
When a move connects two sites on the same boundary, the region
containing the boundary is split. All other boundaries in the
original region will appear either in the region accessible from the
left site of the new spot or the region accessible from the right
site. This separation is specified by listing the lowest numbered
live spot from each of the boundaries to go into one of the regions.
A list of boundaries accessible to the left site is preceded with
"<", while a list accessible to the right site is preceded with ">".
If there are no other boundaries to separate, the separation is
written "=".
8 7 Example: After 1-6-2; 3-7-4; 1-8-2>; 3-9-4>1
/ \ / \ the position is
1 2 3 5 4
\ / \ / 1-6-2-8;3-9-4-7/1-8-2-6/3-7-4-9;5.
6 9
Element 6: Specifying the region for double-eye-spot moves.
When two eye spots share the same two regions, a move connecting them
must specify in which region the connection is made. Since such eye
spots appear on the same boundary in each region, they separate the
region as in element 5. The separation is also used to determine
which region is used, in one of the following ways:
6a. If the separation normally lists at least one boundary, the
listed boundary is sufficient to specify the region.
6b. If the separation is between at least one boundary on one
side and zero boundaries on the other side, the separation
must specify the side with at least one boundary.
6c. If there are no live boundaries being separated, but there is
at least one other live spot on the boundary being connected,
then the lowest numbered live spot is listed as being
separated, as if it were on a separate boundary, along with
which side the separation is on.
6d. If there are no live spots in the region being separated,
then the separation is written "=".
_ Examples: After 1-3-1> the position is 1,3;2/1,3.
/ \ 2 A move between eye spots 1 and 3 must be written
1---3 1-4-3>2 or 1-4-3= as in elements 6b and 6d,
respectively.
3 In the game 1-4-2; 2-5-3; 1-6-5.2 the position is
| 1,4,2,3,6/1,6,2,4. A move between eye spots 4 and 6
6---5 is written 4-7-6>1 for connection in the region
/ | containing 3, or 4-7-6<1 for the smaller region, as
1--4--2 in element 6c.
Element 7: Equivalent representations for a position
A position representation can be changed in three ways with no
effect on the position represented:
7a: Changing which site is used as the start of a boundary
or boundaries,
7b: Changing the order in which boundaries are listed in a
region or regions, and
7c: Changing the order in which the regions are listed.
There are two other changes that can be made, provided that we do
not need to interpret the notation of moves made in the position:
7d: Permuting the numbers used to denote the spots, and
7e: Reversing the order of all boundaries in a region or
regions.
If a position is changed in these ways, any further moves must be
translated by performing a corresponding permutation to the spot
numbers and exchanging ">" with "<" in the reversed regions (except
where a move connects a point to itself, as in element 3.
I believe these elements are a complete description of a notation
system for Sprouts, but it is quite possible I have overlooked
something. I welcome comments and questions.
Dan Hoey
haoyuep@aol.com
From: Danny Purvis <danny_purvis@hotmail.com>
Subject: Sprouts: New Proof for Old Result
To: geometry-research@mathforum.com
Date: 31 Dec 00 10:04:51 -0500 (EST)
Definitions:
(1) An "exhausted" position is a position with no legal moves.
(2) A player "fields" a position if it is his move in that position.
Thus the player who fields an exhausted position loses.
(3) A "cannibal" is a spot with 0 or 2 lines attached. "Cannibal" is
a whimsical corruption of "countable".
(4) A "ghost" is a spot with 1 line attached. Ghosts are invisible
(but are in the background) of the following argument.
(5) A "survivor" is a live spot in an exhausted position.
Argument:
(1) A single move always changes the total number of cannibals by an
odd number. For instance, a move from a cannibal to a cannibal
changes the total number of cannibals by -1.
(2) Thus a player who fields a position with an odd number of
cannibals cannot field a position with an even number of cannibals.
(3) Since survivors are cannibals, a player who fields a position with
an odd number of cannibals cannot field an exhausted position if there
are an even number of survivors.
(4) Likewise, a player who fields a position with an even number of
cannibals will win if there are an odd number of survivors.