From: Dan Hoey <email@example.com> Subject: Sprouts notation To: firstname.lastname@example.org 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 email@example.com
From: Danny Purvis <firstname.lastname@example.org> Subject: Sprouts: New Proof for Old Result To: email@example.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.