Technical Information

This page was mostly written by Claude (an AI by Anthropic), with the instructions to be technical and to include the information needed to program this software yourself. It is the technical companion to the User’s Guide, which describes the controls. Where an algorithm is easier to state as a program than in prose it is given as pseudocode. The names in this font are those of the functions and files in the program, so that the source can be read alongside.

Sprouts is a combinatorial drawing game. Two players take turns. At each turn one of them draws a curve from one spot to another (or back to the starting spot) and adds a new spot somewhere on the curve. Curves must not cross or touch. No spot may have more than three curves emanate from it. The first player who is unable to draw a new curve loses. The winner is determined entirely by the topology of the drawing, independently of the shape of the curves and regions. The program is therefore built in two layers: a topological one that determines the moves, and a geometric one that draws them.

Most of the code, and most of this page, is about the second layer: how to draw a move that the rules allow when the picture has become crowded. Section 1 describes the two layers, sections 2 to 4 the drawing, section 5 the computer players, section 6 play between two computers and section 7 how it all runs in a browser. Section 8 contains a bibliography of the papers and books that were used in the design of this software.

The Table of Contents below takes you to any part of this page. Clicking on this symbol  ⇧  anywhere on the page takes you back here.

Table of Contents

• 1. Two Layers and One Invariant
  • 1.1. The rules and their consequences
  • 1.2. The position is the authority
  • 1.3. No limit on the number of spots
• 2. From Picture to Position
  • 2.1. Curves are splines
  • 2.2. Deciding touching and crossing
  • 2.3. The rotation system and the regions
  • 2.4. The position as lists of corners
  • 2.5. The moves
  • 2.6. When are two positions the same?
• 3. Drawing a Move
  • 3.1. Reading the player’s intention
  • 3.2. The planner: a grid and Dijkstra
  • 3.3. Enclosing chosen spots
  • 3.4. The elastic band
  • 3.5. Leaving and reaching a spot
  • 3.6. From polyline to spline, and the check
• 4. Making Room: Six Kinds of Rearranging
  • 4.1. Overview
  • 4.2. The window
  • 4.3. Sliding spots along their curves
  • 4.4. Pushing curves apart
  • 4.5. A and R: one energy for the whole picture
  • 4.6. Z: the picture drawn afresh
  • 4.7. Heroic mode
• 5. The Computer Players
  • 5.1. Thinking without pictures
  • 5.2. Random
  • 5.3. Monte Carlo
  • 5.4. Parity search
  • 5.5. Bounds on the number of moves left
  • 5.6. Exact play by parts: nimbers
  • 5.7. Misère play by parts
  • 5.8. The candidates and the clock
  • 5.9. From intention to drawing
  • 5.10. What is known about Sprouts
• 6. Two Computers
• 7. Running in a Browser
  • 7.1. Workers
  • 7.2. Memory
  • 7.3. The log
  • 7.4. The files
• 8. References

1. Two Layers and One Invariant⇧

1.1. The rules, and their consequences

The game starts with $n$ spots. A move draws a curve from a spot to a spot, possibly the same one. That curve crosses no curve and no spot. Every move puts a new spot somewhere on the new curve. The program puts it near the middle of the curve, but the spot may be moved along the curve at a later stage. No spot may have more than three curves attached to it. The number of curves that can still be attached is the number of lives at that spot. Spots with 3, 2, 1 or 0 lives are called seeds, sprouts, links and stumps, respectively. In normal play the first player who cannot make a move loses. In misère play that player wins. The game was invented by John Conway and Michael Paterson in 1967 and made known by Martin Gardner [1].

Two facts follow at once and are used everywhere. First, every move removes two lives, one at each end, and it creates a new spot with one life left, so the total number of lives on the board decreases by exactly 1 at each move. The game starts with $3n$ lives, and the last move leaves at least one link (the new spot added by the last move). Therefore a game lasts at most $3n-1$ moves. A counting argument (section 5.5) shows that it lasts at least $2n$ moves. Second, a move is possible exactly when some region has at least two lives on its boundary or in its interior. So whether the game is over is a topological question, and the answer is independent of the shape of the curves and regions.

1.2. The position is the authority

The position is the topological content of the game, the only thing the rules care about. It consists of the regions into which the curves cut the plane, and for each region its boundaries: the curves and spots that enclose it from the outside and the curves and spots that lie inside it. Each boundary is read as the cyclic sequence of the spots on it, and every spot carries its lives. (Section 2.3 says precisely what is stored.) The picture is one of infinitely many ways of drawing a position: the same position can be drawn with the curves bent any way one likes, the spots anywhere, and any region as the outside.

The program keeps both. The position is the authority and the picture serves it, under one rule: an operation on the picture may never change the position. Every such operation (drawing a move, sliding a spot, pushing curves apart, rearranging the whole drawing) is followed by a check. The position is read off the changed picture from scratch (engine.analyse, section 2.3) and compared with the position it should be. This is the position before the operation when the operation only rearranges, and the position after the intended move when the operation draws one. The operations are built so that they keep the position (the band of section 3.4 can deform a curve but never pass it through anything, and the descent of section 4.5 caps every step so that nothing can cross). The check catches what the construction does not cover, such as the smooth curve laid through the polyline at the end of A, R and Z. If the check fails, the operation is rejected and the picture is put back. The computer player goes further: it chooses its move in the topological layer alone, and the drawing it gets back is accepted only if it produces the position the computer intended (section 5.9).

Three consequences shape the program:

1. Bugs in the geometry cannot corrupt the game. They can only make a move fail to be drawn, and then the program says so.
2. Any amount of freedom may be taken with the picture (spots moved, curves reshaped, the outside region swapped for another) as long as the check passes.
3. Network play needs to send only topological moves. Each computer draws its own picture (section 6).

1.3. No limit on the number of spots

The program has no upper limit on the number of spots. Practical limits are imposed by the size of your drawing area and your computing resources. A position with many regions needs room for its curves, and at some point a move the rules allow cannot be drawn with the minimum clearance the Settings ask for. When that happens the program says why (the widest way it found and what was needed), and offers the ways of making room described in section 4. The largest games played during development had 100 seeds, computer against computer, in a drawing area of 2560 by 1383 pixels.

2. From Picture to Position⇧

2.1. Curves are splines

Every curve is a piecewise cubic polynomial, twice continuously differentiable (C²), stored in Bézier form. Each cubic piece $i$ is given by its four control points $b_0, b_1, b_2, b_3$, which are points of the plane (vectors with an $x$ and a $y$ coordinate), and it traces the plane curve $$p(t) = \sum_{k=0}^{3} \binom{3}{k} (1-t)^{3-k} t^k\, b_k, \qquad 0 \le t \le 1,$$ a point of the plane for each $t$. With the piece is stored its parameter length $h_i$, roughly its arc length. The knots need not be uniform. C² continuity holds with respect to this parameterization, so pieces may be long where a curve is straight and short where it bends. A curve is refined locally, one piece cut in two by de Casteljau subdivision without changing the shape, never globally.

A move’s curve from spot $x$ to spot $y$ is fitted as one spline and then cut near its middle, where the new spot $z$ goes. The cut is made where half the arc length is reached, except that an existing knot close to that point (within 15% of its piece’s parameter length) is used instead, so that no very short piece is made. The new spot is therefore near the middle of the curve, not exactly at it, and it may be slid along the curve later (section 4.3). The program stores the curve as two curves, $x \to z$ and $z \to y$, but remembers that they were one spline. As long as $z$ has no third curve, the two can be treated as one again, to slide $z$ along them (section 4.3) or to move them together (section 4.4).

2.2. Deciding touching and crossing

Whether two curves cross, or come closer than some distance, is never decided by sampling points on them. It is decided by their control polygons, which can be computed exactly. A Bézier piece lies in the convex hull of its control points, and more precisely within a known distance of its control polygon. For a cubic, Nairn, Peters and Lutterkort [2] give the sharp bound $$\max_{0\le t\le 1} \bigl| p(t) - \ell(t) \bigr| \;\le\; \tfrac13 \max\bigl(|b_0 - 2b_1 + b_2|,\; |b_1 - 2b_2 + b_3|\bigr),$$ where $\ell$ is the control polygon suitably parameterized. The program (geom.refinedPolygon) subdivides each piece until this bound $\varepsilon$ is small enough and no polygon leg is too long, and then works with the refined polygon. If two refined polygons stay a distance $d$ apart, the curves stay at least $d - 2\varepsilon$ apart. A test on polygons is therefore a certificate about the curves, not an estimate. The stored spline itself is never changed by this. Refinement is done on copies for testing.

2.3. The rotation system and the regions

The drawing is a planar map: spots are vertices and curves are edges, with loops and parallel edges allowed. Its topology is determined by three lists, and nothing else:

1. the spots, each with the number of curves at it (its degree, hence its lives);
2. the curves, each given by its two end spots $a$ and $b$;
3. at every spot, the cyclic order in which the curves leave it (the rotation system). This is what the picture adds to the plain graph: a planar map with the same spots and curves but another cyclic order at some spot is a different position.

From these three lists everything else follows: the faces, which faces lie inside which, and so the regions with their boundaries and lives. The program does not store the regions as data to be updated with each move. It recomputes them from the curves after every operation on the picture (engine.analyse), which is both the way the position is read and the check of section 1.2. The computation runs in four steps.

1. Half-edges. Each curve $e$ from $a$ to $b$ gives two half-edges: $2e$ from $a$ to $b$ and $2e+1$ from $b$ to $a$ (its twin). The spot a half-edge leaves is its tail, the spot it reaches its head.
2. Rotation system. At each spot the half-edges leaving it are sorted by the direction of their first refined-polygon leg (section 2.2). Since the refined polygons of different curves do not touch, two half-edges never have the same direction.
3. Faces. A face is traced by walking: along a half-edge $h$ to its head, then on along the half-edge that comes just before the twin of $h$ in the rotation at the head. This turn keeps the face on one fixed side, and repeating it brings the walk back to $h$. The closed walk is a cycle of half-edges, and every half-edge lies on exactly one cycle. A connected component of the map with $k$ cycles has $k - 1$ inner faces, each bounded by one cycle, and one further cycle, its outer cycle, which goes round the whole component. The outer cycle is the one with negative signed area (the screen’s $y$ axis points down, which flips the usual sign). A component that is a tree has one cycle, its outer cycle, and no inner face.
4. Regions. A region is an inner face of some component, or the unbounded outside. A region can hold further things: whole components, and spots with no curves. They are not nested regions but boundaries of the region they lie in. For each component, a point just outside its outer cycle is tested against the polygons of all inner faces, and the smallest inner face (by area) that contains the point is the region the component lies in. If none does, it lies in the outside. The same test places each spot with no curves. A region’s lives are the lives of the distinct spots on its boundaries.

function analyse(spots, curves):
    for each curve e from a to b: half-edges 2e (a → b) and 2e+1 (b → a), each with its refined polygon
    for each spot: sort the half-edges leaving it by the direction of their first polygon leg   // the rotation
    next(h) = the half-edge just before twin(h) in the rotation at head(h)
    for each half-edge h not yet on a cycle:
        walk h, next(h), next(next(h)), … until h comes back; this is a cycle, with its polygon and signed area
    for each connected component: its cycle of least signed area is its outer cycle, the others bound inner faces
    regions = { outside } ∪ { one region per inner face, with that face's cycle as its first boundary }
    for each component: add its outer cycle as a boundary of the smallest inner face containing a point just outside it, else of the outside
    for each spot with no curves: add it as a boundary of the smallest inner face containing it, else of the outside
    for each region: lives = sum of the lives of the distinct spots on its boundaries
    return regions                                          // a move exists iff some region has 2 lives or more

So the answer to “which regions does a region contain?” is never stored, because it is never needed. What a move needs is the list of boundaries of its region: the cycle round it (for an inner face), the outer cycles of the components inside it, and the spots with no curves inside it. A region is nested in another exactly when the outer cycle of its component is a boundary of the other, and when that matters (for Z, section 4.6) it is read off the boundaries. The result of analyse is the list of regions, each with its boundaries (cycles of half-edges, or single spots) and its lives. It also gives regionAt(p), the region containing a point, which the input code uses to know on which side of a spot the pointer is.

2.4. The position as lists of corners

For the computer players the position is reduced to what Applegate, Jacobson and Sleator [3] call the set representation (ai.js): a list of regions, each a list of boundaries, each boundary the cyclic list of spot corners met when walking once round it with the region on the same side. A spot with $d \ge 1$ curves has $d$ corners in all. A spot in the middle of a bare path appears twice on the same boundary, and a spot on a cycle appears once on each side. A spot with no curves is a boundary of its own. Which region is the outside is not recorded. The game is the same on the sphere, and the drawing may make any region the outside (section 4.6).

2.5. The moves

A move goes from corner $i$ of boundary $j$ to corner $i_2$ of boundary $j_2$ in one region $r$. The new spot is $z$. There are two kinds.

• Two boundaries ($j \neq j_2$): the curve joins them into one, $[x, \dots \text{round } B_j \dots, x, z, y, \dots \text{round } B_{j_2} \dots, y, z]$. Nothing else changes, and the route taken does not matter. Any curve between those two corners inside the region gives the same position.
• One boundary ($j = j_2$): the curve splits the region in two. Reading $B_j$ from $x$’s corner, with $y$ at offset $p$, the two new boundaries are $B_a = [x, \dots, y, z]$ and $B_b = [y, \dots, x, z]$ ($p = 0$ is a loop at one corner and needs two lives at $x$). The region’s other boundaries must go to one side or the other, and every choice is a different move. With $k$ other boundaries that still have lives there are $2^k$ moves for the same pair of corners. Here the route matters very much. Drawing such a move means drawing a curve that goes round exactly the chosen boundaries (section 3.3).

Because $2^k$ can be enormous (twenty seeds in one region give $2^{19}$ loops from each of them), moves are listed as families, one per pair of corners, each standing for its $2^k$ choices (ai.families). Boundaries with no life left may go to either side without changing the game and are always put with $B_b$.

2.6. When are two positions the same?

Many different-looking positions are the same game. The program uses three names for a position, from the most to the least particular:

The canonical form follows the paper [3]. Regions with fewer than two lives are dropped, and so are stumps. A spot is written as its number of lives (1, 2 or 3). A one-life spot can occur twice (on a bare path, or on a cycle between two regions), so it is given a letter that marks its two occurrences as one spot. Each boundary is read from the rotation that makes its string least, the boundaries of a region are sorted, the regions are sorted, letters are given in order of first appearance, the mirror image (every boundary reversed) is done too, and the lesser string wins. Ties (two boundaries with the same string) are where a naive version lets the spot indices decide, and then equal positions get different strings. The program settles ties by branch and bound over the orderings and rotations that matter (those that involve a spot shared with another boundary), so the form is a true canonical form. If the branch and bound exceeds a work budget, the form is finished greedily. The result is still a correct name of this position, only possibly not the same name as an equal position’s, which costs a missed table hit and never a wrong answer. A position made of independent parts (section 5.6) is written as the sorted forms of its parts joined by “+”, each part named on its own.

3. Drawing a Move⇧

Whether a move comes from a person’s mouse or from the computer, it reaches the geometry as the same request: from spot $a$, leaving on this side, to spot $b$, arriving on that side, going round these spots. The geometry answers it in four stages: a rough route on a grid (section 3.2), the route made to go round the right things (3.3), the route tightened into a smooth curve with as much room on both sides as there is (3.4–3.5), and the curve turned into a spline and certified (3.6). The two numbers that govern it all are in the Settings menu: the minimum clearance $d_0$ (default 6 pixels), the least distance a new curve must keep from everything else, and the comfort distance $D$ (default 40 pixels), the distance at which a curve stops feeling its neighbors much.

3.1. Reading the player’s intention

The input code is deliberately forgiving and avoids fixed thresholds: decisions are made by comparison.

• A press goes to the nearest spot that still has a life, at any distance. The spots that can be reached from it light up at once, because the planner (section 3.2) computes the distance to every free cell in one pass.
• A spot with two curves has two sides, and only one of them may lead somewhere. The region under the pointer decides which side the curve leaves from, and the lit destinations follow it as the pointer moves. If the side pressed leads nowhere and the other side does lead somewhere, the other is taken.
• Click or stroke is decided by where the pointer is released. Nearer the start than to any lit destination, it was a click (choose the destination with a second click). Otherwise the nearest lit destination is the end of the move. A release just outside a destination’s disc also says from which side the curve should reach it.
• A stroke that is usable (it reaches the destination without touching anything) is itself the start of the curve. Otherwise the planner’s shortest route is used. Either way the elastic band then smooths it, and the stroke’s way round things is kept: the band can deform a curve but never pass it through an obstacle.
• Right-click, or Shift+click, on spots between the two clicks marks them. The curve must then enclose those spots (more exactly, the boundaries they lie on) and not the others.

3.2. The planner: a grid and Dijkstra

The free space is sampled on a square grid whose cells are $\max(2, \min(8, 0.7\,d_0))$ pixels wide (route.js). A cell is free when its center has clearance at least $d_0$ from every curve, spot and the window’s edge. Since a curve blocks a band $2d_0$ wide and a cell is at most $0.7\,d_0$ wide, the search cannot leak through a curve between two cells. Near a spot, clearance from that spot’s own curves is measured as an angle rather than a distance (section 3.4), so the narrow corner between two curves at a destination stays open, as it will be for the band.

Dijkstra’s algorithm [4] on the 8-connected grid, from the start, gives the distance to every free cell at once. That answers both questions the input needs: which spots can be reached from here (to light them up), and what the shortest way to $b$ is. The grid path is within a few percent of the true shortest path and, more importantly, in the right homotopy class. The band then tightens it into the true geodesic with clearance. An optional side test makes the path arrive at $b$ through a chosen corner.

When no path exists, a bottleneck search (the path whose narrowest point is widest, route.widest) finds how much room the best way actually has, and the refusal says so: “the widest way is too narrow here”. The details go to the log, which gives the clearance of that way and the clearance needed (the status line names the spots and curves involved and leaves out pixel numbers). The same widest way is the starting point for pushing curves apart (section 4.4).

3.3. Enclosing chosen spots

A one-boundary move must put each of the region’s other boundaries on a prescribed side. The shortest path knows nothing of sides, so marked moves are routed differently (moves.markedRoute).

The first method is the barrier route. The boundaries that must end up on the marked side are joined to each other by a tree of grid cells. The boundaries that must not are joined by a second tree that does not touch the first. Each tree also holds what goes with its side: the arc of $a$’s own boundary between the curve’s two ends that belongs on that side, and, in the outside region, the window’s edge (which goes with the unmarked side). A path from $a$ to $b$ that uses no cell of either tree cannot separate two things a tree joins, so it separates the two groups correctly. One Dijkstra run per tree and one for the path suffice. There is no $2^k$ blow-up. (A loop, $a = b$, needs one extra bit of information, which side of the loop is its inside. That bit is found as in the second method.)

The same bit is needed when $a$ and $b$ are so close that the neighborhoods kept free of the trees around them overlap, for instance when $b$ is the next spot along $a$’s own curve (v178). The path could then slip straight from $a$ to $b$ between the trees and go round nothing. A ray from a marked boundary must then be crossed an odd number of times by the curve and the marked arc together (the curve’s share is wanted odd or even as the arc’s own crossings make it). The strip beside the segment from $a$ to $b$ is closed to the path, so that it leaves $a$ away from $b$ and reaches $b$ from beyond it, instead of running out and back along the same narrow gap. Before this, such a move could only be drawn by drawing the whole picture afresh (Z). When the marked side holds the region’s own outer boundary, that side is the outside of the closed curve in the plane. The ray is then taken from the other side instead (an unmarked boundary, or else the point of the other arc farthest from $a$ and $b$), and it is that side the curve and the marked arc must go round (v182: a curve from a spot round the short stub hanging from its neighbor, in the middle of an empty region).

When the trees cannot be built (a long, snaking region can wall off the corner the curve must arrive at), the second method is a parity search. A ray is cut from each boundary that has to change sides, the grid states carry one bit per ray (whether the path has crossed it an odd number of times), and Dijkstra over (cell, bits) looks for a path that reaches $b$ with the wanted bits. Rays are added only for the boundaries that the last candidate left on the wrong side. This costs $2^{\text{rays}}$ states per cell and is limited to seven rays. The search is an A* search (states are taken in order of their distance so far plus the straight distance to $b$, which no way on can beat). It stops as soon as no state left can lead to a shorter path, and it keeps states only for the cells it actually reaches.

Either way the answer is judged, not trusted. engine.afterMove performs the move virtually along the polyline and lists the spots that end up on each side. A route that would enclose the wrong spots is not drawn. If no method finds one, a hand move stays armed and says so (Enter then draws the shortest way, without the marks). The computer simply tries its next candidate.

3.4. The elastic band

The route (a stroke or a grid path, resampled at equal spacing) is tightened by minimizing a clearance energy over the polyline’s vertices (relax.js): $$E = \int \Bigl(1 + \lambda \sum_{o} \varphi\bigl(r_o(s)\bigr)\Bigr)\, ds, \qquad \varphi(r) = \Bigl(\frac{D - d_h}{r - d_h}\Bigr)^2,$$ where $s$ is arc length and $r_o$ the distance to obstacle $o$. The sum runs over distinct obstacles: each other curve, each spot, each side of the window, and the band’s own far-away parts. The term $\varphi$ is 1 at the comfort distance $D$, decays like $1/r^2$ beyond it and never quite vanishes, so a curve keeps drifting towards the middle of whatever room there is. It becomes infinite at the barrier $d_h$, so the band can never pass through an obstacle and stays in the homotopy class it started in. $\lambda$ weighs room against length (Settings → Room vs length; the slider is $\log_{10}\lambda$, default $\lambda = 1$). Obstacles are found through a spatial grid of 64-pixel cells and are felt up to 256 pixels away.

Near a spot, distance is the wrong measure for that spot’s own curves, because every curve leaving a spot is at distance zero from the others there. Within a radius $\rho = \sqrt2\,D$ of a spot, the distance to the spot’s own curves is replaced by their angular separation, scaled as $\theta\,\rho$. Curves can then share a spot while still being pushed apart in angle.

The minimization is a preconditioned Newton iteration whose steps are projected across the band (moving a vertex along the band changes nothing but the spacing). The barrier starts low and is raised towards $d_0$ as the iteration proceeds (a continuation), so that a stroke drawn too close to something can still be eased away from it. The iteration stops when both the change of shape and the gain in energy have become small. On screen the band is drawn as it relaxes, a few steps per animation frame, which is the animation a move shows.

3.5. Leaving and reaching a spot

The band works in two phases. In the first, its ends are free near the end spots. The curves already at those spots are ignored close by, so the band finds its way without being blocked at the very place it must reach. Then the ports are fixed: the directions in which the new curve leaves $a$ and arrives at $b$. At a spot, the existing curves divide the full turn into sectors, and the new curve must use the sector facing the region of the move. If that sector is at least 60° wide, the band’s own direction is kept, but at least 30° from the curves that bound the sector. Otherwise the curve leaves along the sector’s bisector. In the second phase the band relaxes between short fixed stubs in the port directions.

3.6. From polyline to spline, and the check

The relaxed polyline becomes a spline by a least-squares fit (geom.fitClamped) with chord-length parameter and the port directions imposed as the end derivatives (a clamped spline). The fit starts with a single piece and inserts one knot at a time in the worst-fitting piece until every point is within 1.5 pixels. It is local by construction: a knot goes only where it is needed.

The spline is then certified (relax.certify): its refined control polygon (section 2.2) must keep $0.6\,d_0$ from everything. The new spot is placed near half the arc length (section 2.1), the spline is cut there into the move’s two curves, the position is recomputed (section 2.3), and the move is recorded: in the undo history, in the log (in words, such as “3 → 5 enclosing 7, 8-9”, with the regions it split or joined) and, in network play, sent to the other computer.

4. Making Room: Six Kinds of Rearranging⇧

4.1. Overview

As a game goes on, regions get crowded and a legal move may find no way through with the minimum clearance. The program then changes the picture, never the position, in one of six ways. They range from the very local and cheap to the global and expensive, and each later one is tried only when the earlier ones are not enough.

The ladder. The commands M (sliding spots, then pushing curves), A, R and Z are the rungs of a ladder of increasing cost, and above Z there is one more step, • (key .): drawing afresh with the spots in tight places drawn smaller (section 4.6). Each, pressed while a move is waiting for room, changes the picture and then tries the waiting move again. The Room menu has a box per step for a human’s moves and a box per step for the computer’s, saying which steps are taken automatically (by default M and R for a human, M, R, Z and • for the computer). Each step is taken at most once for a move, in the order M, A, R, Z, •. For a human’s move the ladder is climbed as far as the boxes are checked in a row. At the first box not checked it stops (an unchecked A is simply skipped), and the status row offers that step and the ones above it by hand. A step pressed by hand tries the move again, and the ladder then goes on from there by the same rule. For the computer’s move the checked steps are taken in order and the unchecked ones skipped. When the steps are used up, the program stops and says so. A human’s move stays waiting, and the keys still work by hand. A new click on a destination starts the ladder anew, and Space during a step stops the climb. Heroic mode (section 4.7) switches the human’s boxes off. Each change of the picture is its own undo step, and the move that follows a change made for it shares that step. Every one of these operations ends with the check of section 1.2.

4.2. The window

A game lives in world coordinates: the size of the drawing area, in pixels, when the game started (shown as “Drawing area is W x H” on the status line and in the log; Q shows it again). When the window changes size, the view is scaled uniformly by $s = \min(w/W_0,\ h/H_0)$ and centered, and the canvas is sized for the screen’s pixel density so that curves stay sharp. Nothing in the game changes: a larger window magnifies the picture but does not give the game more room, because the clearances in the Settings are measured in world pixels. To have more room, start the game in the larger window (or full screen). Saved games keep their world size and are shown scaled in any window.

4.3. Sliding spots along their curves

A spot made by a move sits on that move’s spline (section 2.1). While it has no third curve it can slide along the spline. The spline is simply cut at another parameter value (one de Casteljau split, or an existing knot if one is within a pixel). The shape of the curve does not change at all, so nothing can cross and no region changes, only where the spot is. Often a move is blocked only by a spot sitting in a narrow passage, and sliding it a little opens the way.

The candidates are positions a minimum clearance apart, on the side of the curve facing the move’s region, taken in order of how far the spot would slide, in both directions at once. A position whose estimated room (the widest way there, an upper bound) is too small gets no trial. The others are each tried with the real planner and band, and when the band keeps the minimum clearance, with the fitted spline too. Its certificate (section 3.6) asks for 0.6 of the minimum clearance, so a shortfall counts as its clearance divided by 0.6 (v183: a loop whose band kept 11 px but whose spline came within 1.5 px was taken to fit already, and nothing was done). Among the positions where the move fits, the one whose curve has the lowest band energy wins, the same measure of length against crowding by which every curve is judged. The search stops at the first valley: when, in some direction, the move has fitted and the energy then rises again.

A seed (a spot with no curves) has no curve to slide along, but it can be moved anywhere in its region. A seed in the way of the move is pushed straight away from the move’s path by what its disc lacks of the minimum clearance, or by half that, or a quarter, the first push that crosses nothing and keeps the seed’s own clearance (v188). When the move has no path at all, because two seeds are so close that nothing can pass between them, the seeds of the region that are closer together than two minimum clearances are spread apart first.

4.4. Pushing curves apart

When sliding is not enough, the curves in the move’s way are moved (room.moveCurvesFor):

1. The ghost: the way the move would take if there were room. It is the planner’s path at the clearance that the widest way actually has, so it goes through the narrowest place the move cannot avoid, and is as short as that allows. Then it is relaxed by the band so that it lies in the middle of what room there is.
2. The curves closer to the ghost than $d_0$ are the ones to move. Each moves as one spline (a move’s two curves while their spot has only those; the spot rides along at its knot). Its de Boor points (the B-spline control points) relax under the band’s energy with the ghost as an extra obstacle. Its ends and end directions stay where they are. Where the ghost is near, pieces are first halved for more freedom.
3. The move itself is tried again. Rounds repeat (a new ghost through the widened place, the curves now too close to it) as long as the room on the widest way keeps growing.

A spot with curves, or the window’s edge, in the way cannot be pushed, and the refusal names it. Neighbors are never squeezed below their own clearance to make room for the move.

Sliding and pushing can take seconds in a crowded picture, so they run in a separate thread (a Web Worker, section 7.1). The page stays responsive and Space stops them.

4.5. A and R: one energy for the whole picture

A (adjust) and R (rearrange) lay out all the curves at once, by minimizing one energy over the whole drawing (redraw.js). The idea is that every curve should be drawn as the band would draw it if it were drawn last, all at the same time. Every curve becomes a polyline through its end spots and points about $D$ apart along it (a move’s two curves form one unit, so bending is charged through the move’s spot). The spots and the points then move together to a minimum of $$E = \sum \text{length} \;+\; \lambda \sum_{\text{points}} w \sum_{\text{near}} \varphi(r) \;+\; D^2 \sum \frac{\theta^2}{\ell} \;+\; D \sum (\theta - 2\pi/k)^2 \;+\; D\sum (t\cdot n)^2 \;-\; \pi D^2 \sum_{\text{live regions}} \text{lives} \cdot \log(\text{area}).$$

The descent is L-BFGS [5] (eight correction pairs) with the exact gradient (checked against finite differences) and a line search on $E$ itself. What makes it safe is a cap on every step taken from Bertault’s PrEd algorithm [6]: each vertex moves at most a third of its distance to anything it could hit (every segment not its own, and the window). No vertex can then reach a segment during a step, so nothing ever crosses, and the position cannot change. When a curve’s length no longer suits its number of points it is re-spaced. The new spacing is kept only if the new polylines do not cross, because two curves crossing twice would leave the rotation system, and hence the position text, unchanged and could not be detected by the check. When no step lowers the energy any more, the points are jiggled at random within a sixth of their caps, a few times, to get out of shallow traps.

The descent stops when the drawing no longer changes visibly: the last 24 steps moved no point by a pixel, or gained less than a pixel’s worth of energy each. (Earlier versions ran to the rounding error of the arithmetic, thousands of steps that nobody could see.) The picture is shown as it goes, in 30 ms slices per animation frame, and Space stops it where it is.

A keeps the original spots, and those added by hand, where they are, and moves the points of each curve only across the curve, spreading them evenly along it again after each step. (Crowding is charged per point, so otherwise the points drain out of crowded stretches and the smooth curve through the few that are left swings into a neighbor.) R moves everything.

Finally each curve is the clamped C² spline through its points (geom.interpolate), a move’s two curves as one, cut at the move’s spot. Where a third curve leaves that spot the spline is made C¹ through it. If the smooth curves fail the certificate there are fallbacks: splines through the middles of the legs, points spread evenly on the polylines, and as a last resort a corner at the failing spot (logged). The result is refused if the position changed or the clearance is not positive. A curve whose pieces already suit its length keeps its knots as its points, so pressing A or R a second time starts where the first ended and changes next to nothing. A spot that was drawn smaller than its size by an earlier Z (section 4.6) grows back to its size in A and R as soon as there is room for it.

Tried and dropped: starting R from Tutte’s barycentric embedding [7] of the position’s map, made into a triangulation. It is exact in theory and gives a genuinely fresh start, but nested positions crowd it exponentially: least gaps of $10^{-7}$ to $10^{-10}$ pixels in 13–20-spot games, beyond what double-precision arithmetic can hold. Z (next section) replaces it with a drawing whose area is polynomial.

4.6. Z: the picture drawn afresh

A and R start from the present picture and can only improve it locally. When a move cannot be drawn even after R, Z draws the position from its combinatorial map alone (layout.js), with no regard to how it looks now. For the computer, the position after its intended move is drawn, so the move needs no router at all.

1. The map. The rotation system and the faces are read off the present drawing through the engine (mapOf). For the computer’s move the move is then performed on the rotation system (withMove), the same surgery as section 2.5 but on half-edges.
2. A simple triangulation. Every edge gets a midpoint (which removes parallel edges, such as a loop’s two halves). The walks of each face are joined by bridges, and every vertex with fewer than two edges gets a bridge to another corner of its face, so the graph is connected and every face is one closed walk. Each face then gets a face vertex $f$ and a spoke $f - d - u$ to every corner $u$ of its walk, and the hexagons between consecutive spokes are cut into triangles by chords. Every added edge names something that exists once (a midpoint, a corner, a face), so no edge is doubled: the result is simple and every face a triangle, which Euler’s formula confirms.
3. A straight-line grid drawing. Kant’s canonical ordering [8] and the shift method of de Fraysseix, Pach and Pollack [9] draw any simple triangulation with straight edges on a $(2N-4) \times (N-2)$ grid, without crossings by theorem and with polynomial, not exponential, area. The chosen region’s face vertex is the apex of the outer triangle, so that region becomes the outside: any region can be made the outer one. The drawing is scaled into the window, all helper vertices and edges are removed, and each curve comes out as a two-leg polyline $u - m - v$ through its midpoint.
4. Polish. R’s descent (section 4.5) then turns the straight, crowded grid drawing into a picture, in a variant for this start. The spots begin small, each at half its own least gap to a curve or another spot (v189; before, every spot started at half the least gap in the whole drawing), and are grown in stages, each by its own room. Long legs are subdivided so that points cannot drain out of crowded stretches. Below one pixel the crowding term is reshaped so that it stays finite inside a spot’s disc while still growing without bound as the true distance goes to zero. The jiggles of section 4.5 are kept only while they give the spots more room.

Which region should be outside is not known in advance, and the results differ a lot (on one 9-spot position the least clearance ranged from 0.5 to 22.6 pixels over its 17 regions). So Z runs one layout per region in parallel, on the drawing workers (section 7.1), with the present outside first. The one the screen shows is the one with the widest gap at the moment, and it changes as they progress. The program stops at the first layout drawn with at least the least clearance the picture had before, provided that clearance was at least the minimum clearance of the Settings. The purpose is to draw the move, not to find the most beautiful picture. A picture whose least clearance, measured at its single tightest place, is already below the minimum is broken, and then the first layout that can be drawn at all is taken (v194: holding out for 3.0 px against a layout with 2.6 px once cost 38 minutes in a 100-seed game). A layout drawn with some spots smaller (below) counts when the • box allows it. When a layout has been drawn but did not meet that bar, Z ends with the best so far as soon as one round is complete (as many layouts as there are workers), rather than running every region to the end. Stragglers are given up by comparison, not by a fixed time. Once half the layouts are done, one still running after twice the time of the median finished one (drawn or failed) is stopped. If a whole round fails (none of its layouts drawn), or every layout fails, Z gives up and says the picture has run out of room (v183: in a 60-seed game of about 160 spots every layout failed, each after minutes, because the smooth curves would cross where the drawing was too tight). More room then comes from smaller spots or a smaller minimum clearance. A larger drawing area helps only a new game, since during a game the picture is only scaled. The log names the reason each layout failed. Space stops Z and takes the best result so far.

Spots drawn smaller where there is no room (the • box of the Room menu, key ., v189). A layout whose spots cannot all grow to the size the Settings ask for is a failure at full size. When Z runs for a move and the mover’s • box is checked (or when . is pressed), such a layout is kept aside instead: at the end each spot is tried at full size, then at the largest size its gap allows, and the layout keeps those spots smaller, never below the smallest size of the Settings’ slider. A layout kept aside that meets the bar above ends Z like one at full size. Otherwise, if no layout drew at full size, the one kept aside with the least shrinking (its smallest spot the largest, then the fewest spots shrunk) is taken. The size of a spot is part of the game object and is saved, loaded and undone with it. The router, the certificate and the room-making all see the spot at its smaller size, and the log names the spots drawn smaller. They grow back as soon as a later A, R or Z finds room for them.

4.7. Heroic mode

Room → Heroic is for players who want to draw every curve exactly as they please. A curve drawn by hand is kept exactly as drawn (as straight pieces between the sampled points, not smoothed). It must merely not touch or cross anything. Curves and spots are not moved locally (no sliding, no pushing, no Ctrl+drag, and no M for the computer either), and nothing is done automatically for a human’s moves (the human row of the Room menu is grayed out). A, R and Z still work by hand.

5. The Computer Players⇧

5.1. Thinking without pictures

The computer players (ai.js) never look at the picture. They work on the set representation of section 2.4, choose a move as (region, corner, corner, enclosed boundaries), and only then hand it to the geometry to be drawn. Their choice never depends on whether a move can be drawn: if the intended move cannot be drawn, the picture is rearranged until it can (section 5.9), rather than a worse move being played. There are three players, chosen in the Player menus: Random, Monte Carlo and Parity search.

5.2. Random

Random picks a family (a pair of corners) uniformly among all families, then how many of the region’s other live boundaries go inside, uniformly from $0$ to $k$, then which ones. Choosing the number first makes small and large enclosures equally likely. Choosing a subset uniformly would almost always enclose about half.

5.3. Monte Carlo

For each candidate move, Monte Carlo plays a set number of random games (by default 100) to the end from the position after it, with Random’s choices, and counts how often the mover wins. In normal play the mover made the last move, and so wins, exactly when the number of moves after its own is even (in misère, odd). The candidate with the highest share wins. Instead of a number of games, a number of seconds per move may be set. The candidates then get rounds of one game each until the time is up. With several workers, every worker plays games for all candidates and the counts are added.

5.4. Parity search

Since every move removes exactly one life, a game is decided by the parity of the number of moves left: in normal play the player to move wins if the number of moves left (including this one) is odd and the opponent cannot change that. Parity search is alpha–beta search in negamax form [10] over the topological positions, with a heuristic value at its leaves based on bounds on the number of moves left (next section). A leaf with no move is lost in normal play and won in misère (value $\mp 2$). Otherwise, with $M$ an upper and $m$ a lower bound on the moves left, $$v = \frac{\pm 1}{1 + M - m},$$ positive when $M$ has the parity the player to move wants (odd in normal play, even in misère). The closer $m$ is to $M$, the surer the verdict, and when $m = M$ the value is $\pm1$. Values of $\pm 2$ are exact: they come from the end of the game or from solved parts (section 5.6), hold at any depth, and are stored as such.

The Player menus offer the search in two forms (v173). Fast parity search takes for $M$ the upper bound of the next section, which costs next to nothing. Sharp parity search takes the longest game that can really be played from the leaf (also next section) wherever it can be worked out in the move’s time, and the bound where it cannot. Its judgments are truer, but each leaf costs more, so in the same time it may look fewer plies ahead.

How much the difference matters depends on the bound. With the bound of v173, Sharp spent minutes at depth 1 on a position of Peter’s (9 seeds, after 6 moves, 32 different moves, 32 workers): a few leaves had a bound that could not be reached, and proving it took the time while the other workers sat idle. With the pairs of v175 the bound is the longest game itself on 98% of the positions from 5 seeds, and on that position:

At depth 10 both see the whole game (a winning position for the player to move). The two choose the same move with the same value at every depth but 4. Time does not grow steadily with depth: deeper leaves are smaller positions, often split into parts, whose longest games are quick to find, and alpha–beta prunes differently at odd and even depths. The measurements were made with a timing harness that ran both searches depth by depth on a saved game, with fresh workers for every calculation.

function negamax(pos, depth, alpha, beta, beside):   // beside: the solved parts (a nim heap, or misère trees)
    if past the deadline: abort
    if no move in pos: return value of 'beside' alone (exact, ±2)
    (pos, beside, exact) = solveParts(pos, depth, beside)   // section 5.6
    if exact: return its value
    if depth == 0: return evaluate(pos)                // ±1/(1 + M − m)
    key = canonical(pos) + beside
    if table[key] was searched at least this deep: use it (exact, or tighten alpha/beta)
    best = −∞
    for each child of pos:                            // every move; a family with very many
        v = −negamax(child, depth − 1, −beta, −alpha, beside)   // enclosures contributes a sample
        best = max(best, v); alpha = max(alpha, v)
        if alpha ≥ beta: break
    for each move in 'beside' (a smaller heap, or a tree's option):
        v = −negamax(pos, depth − 1, −beta, −alpha, that)   // and the same cut-off
    table[key] = (depth, best, exact / lower bound / upper bound)
    return best

The transposition table is keyed by the canonical form (section 2.6), so the many orders in which the same position can be reached, and its mirror images, are searched once. Interchangeable boundaries (equal ones in the same region) are enumerated by how many of each kind go inside rather than by subsets. Inside the tree, a family with more than 64 ways of choosing the enclosed boundaries contributes 64 random distinct ones. At the root every move is considered (section 5.8).

The search depth is set in the Player menu (default 6 plies), or a time per move (default 5 seconds for Player 2): then the search is iterative deepening, one ply deeper at a time as long as the time lasts, and the move of the deepest completed search is played.

5.5. Bounds on the number of moves left

Let $L$ be the number of lives on the board. Since each move removes one life, the number of moves left is $L - s$, where $s$ is the number of lives that survive to the end. The whole game is about $s$.

Upper bound. A life is a sure survivor when no region its spot lies on has two lives: no move can ever use it, since regions only split and lose lives. At least one life survives (the last move leaves its new spot with one). A region with two lives that holds a private life (at a spot all of whose corners lie in that region, such as a seed inside it or a sprout on it) also keeps a survivor inside it. Either that life is never used, or a move inside the region uses it and leaves a new spot with a life inside, which again only a move inside can use, and so on. These survivors are distinct from the sure ones and from each other. The same holds for a pair of regions joined by a link (a spot with one life whose two corners lie in the two regions) when neither region has a private life: the link’s life can only be used by a move in one of the two, which leaves a new spot whose life again only a move in the pair can use. Pairs that share no region keep separate survivors, so the program counts a matching of such pairs (found greedily: any matching is a valid count). And a region in play keeps at least one life to the end. Hence $$M = \min\Bigl(L - \max(\text{sure survivors} + \text{regions with a private life} + \text{pairs},\, 1),\; \sum_{\text{regions}} (\text{lives} - 1)^+\Bigr).$$ (A spot shared by two regions is counted in both, which makes the sum an over-count but still an upper bound.) On the 34,831 positions reachable from 1 to 5 seeds (up to renumbering and mirror images) it is never below the longest game, and from 5 seeds it equals it on 31,407 of 32,140 positions. With private regions but without pairs it did on 13,840, with neither on 5,751.

The longest game itself. The bound is only a bound: in a ring of links, for instance, every move looks equally good to it. The program also works out the longest game exactly. The longest game of a position is the sum of those of its parts (section 5.6), which share no live spot, so their moves do not interfere. For one part it asks whether a line of $M$ moves exists, $M$ the part’s bound. If not, it asks whether one of $M - 1$ does, and so on. The first yes is the answer.

function reach(p, need):
    if need ≤ 0: return yes
    if known[p] says so either way: return that      // lengths shown reachable / out of reach
    if bound(p) < need: return no
    for each move, small loops beside a boundary first:  // fewest enclosed, shortest stretch cut off
        q = the position after it, in parts
        if the parts’ bounds add up to less than need − 1: skip it
        the smaller parts exactly; the largest: reach(it, need − 1 − their sum)
        if yes: record need as reachable for p; return yes
    record need − 1 as the most for p; return no

A yes usually comes at once, down a single line. A no needs every move, which is affordable because a part is small, or splits into parts as moves are made. What has been shown is kept per part (by canonical form), so a game’s later positions are mostly answered from what was learned for the earlier ones. Only proved facts are kept. When time runs out the answer is “not known” and the bound stands in. The page works it out in a worker of its own for the title and the status line, without a time limit. Until the answer is in they show “M ≤ bound”. It agrees with brute force on all 34,831 positions above. Most positions of the saved games are answered in milliseconds. A few, with one large part and a bound that cannot be reached, take minutes or longer, and for those the ≤ stays. (Before the pairs, v175, there were many more: on Peter’s game of 10/18 the longest games after the 32 moves took over 100 seconds, with them 43 milliseconds.)

Lower bound. At the end of a game every spot is either a stump or a survivor with one life, and a survivor’s two curves lead to stumps (otherwise a move would remain). Counting spots and lives at the end gives $$m = \Bigl\lceil \frac{3L - V + p}{4} \Bigr\rceil,$$ with $V$ the number of spots now and $p$ the number of stumps all of whose neighbors are stumps. At the start ($L = 3n$, $V = n$, $p = 0$) this is $2n$, the classical lower bound on the length of a game. The derivation ignores survivors whose two curves go to the same spot, so instead of trusting it, the program’s test suite checked it exhaustively: on all 305,142 positions reachable from 1 to 5 spots it is never above the true minimum, and on average 0.9 moves below it.

5.6. Exact play by parts: nimbers

A position often falls apart into independent games. Its regions form parts when they share no spot with a life (a spot with lives on two regions joins them). A move in one part changes nothing in the others, and the player to move chooses the part to play in. In normal play the Sprague–Grundy theory applies [11]: every part has a nimber, the least non-negative integer that is not the nimber of any position reachable in one move (the mex rule, and a part with no move has nimber 0), the nimber of a sum is the XOR of the nimbers of its parts, and the player to move loses exactly when it is 0.

The search uses this whenever a position is a sum of two or more parts: each part whose upper bound $M$ is within the remaining depth (the search would look to its end anyway) is solved for its nimber, memoized by its canonical form, and taken out of the position, replaced by a single nim heap of the XOR of the solved nimbers. A part with nimber 0 simply vanishes. The cost is the sum of the parts’ game trees instead of their product (every interleaving of moves in different parts), and once every part is solved the position is solved exactly. This is the technique with which Lemoine and Viennot computed normal-play Sprouts far beyond the earlier results [12]. A position that is one part is searched as a whole: the mex rule must look at every move and prunes nothing, while alpha–beta prunes.

When the search proves a result, the status line says so: “Blue has a winning position”, or “… is lost against best play”. In the 30-spot computer-against-computer games played so far this happened between moves 47 and 65, in games of about 75 moves.

5.7. Misère play by parts

In misère play nimbers do not work: whether a part is won or lost on its own does not tell how it behaves next to another. What does is its misère canonical tree (Conway [13], chapter 12, and Lemoine and Viennot’s “reduced canonical trees” [14]): the game tree with equal options merged and reversible options removed. Two games have the same tree exactly when they are interchangeable in every sum. The program keeps a store of trees (each an id), computes a solved part’s tree, and replaces the part by it. A position all of whose parts are solved is decided by the outcome of the sum of the trees. The rules used:

• Equality: $G = H$ if and only if both have the same misère outcome, every option of $G$ equals an option of $H$ or has an option equal to $H$, and the same with $G$ and $H$ exchanged.
• Simplification: an option $x$ of $G = \{S\}$ may be removed when $x$ has an option equal to $\{S \setminus x\}$, unless $S \setminus x$ is empty and $G$ is a misère loss for the player to move.
• Nim heaps are canonical, and $*m + *n = *(m \oplus n)$ when $m$ or $n$ is 0 or 1. A sum of heaps alone is decided by the misère nim rule: the mover wins if and only if the XOR is not 0, except when every heap is 0 or 1, and then if and only if it is 0.

These rules were checked by brute force against all 22 games born by day 4 and their sums.

5.8. The candidates and the clock

At the root, the computer considers every legal move, not a sample. Many of them lead to the same position, so their canonical forms are computed (on the workers) and duplicates dropped. What is left is the list of truly different moves, from 16 at the first move of a 30-spot game to several hundred in the middle game. The parity search splits this list among the workers, and each keeps its own transposition table and stores of solved parts.

The clock is read at every position the search visits, leaves included, so that a search with a time budget stops on time even in very large positions. A search of depth 1 is always completed (a move must be chosen), whatever the budget.

One move, from the position alone. Several moves may tie for the best value (often all the winning moves, once the search is exact). The tie is broken without looking at the picture: random games are played from the tied moves alone (Monte Carlo, with the player’s Monte Carlo settings), and the move that won most often is taken. A tie that remains is broken at random, which keeps games between two computers from repeating. The computer then commits to that one move: it is never exchanged for another that happens to be easier to draw.

5.9. From intention to drawing

The computer’s move is always drawn as intended. It climbs the ladder of section 4.1 with the computer’s boxes of the Room menu:

1. The move is given to the router (section 3) with its enclosed boundaries marked, and room is made for it in place (M) if the computer’s M is on. Which of several interchangeable boundaries it encloses (loose seeds, say: the search decides only how many) is the drawing’s choice (v178): starting from the move’s spots, the boundaries it must enclose and the straight way from its first spot to each of them, the nearest boundary of a kind still wanted is added, then the next nearest to everything chosen so far, and so on: a cluster round the move instead of seeds scattered over the window. If its marks cannot be applied, it is drawn the shortest way, and kept only if that is the same move.
2. If it cannot be drawn: the next of A and R switched on, after which the same move is found again in the new picture (by its spots, which keep their indices: the boundaries made of the enclosed spots, on one side or the other, whichever gives the intended position) and tried again, its interchangeable boundaries chosen afresh for the new picture.
3. Still not: Z, if it is on, with the move laid out as part of the fresh picture (section 4.6).
4. Still not: the game stops, with a message. A, R or Z by hand lets the computer try the same move once more; or the player can be set to Human.

After every computer move the drawn position is compared with the intended one (its gameKey, or that of its mirror image, or the same canonical form). A drawing that encloses something else is taken back, and the next rung is climbed.

5.10. What is known about Sprouts

Applegate, Jacobson and Sleator [3] computed the winner with best play for the first games by computer in 1991:

(W: the first player wins. L: the first player loses.) They conjectured that in normal play the first player wins exactly when the number of spots is 3, 4 or 5 modulo 6. Lemoine and Viennot, using nimbers, extended the normal-play results to 32 spots and further individual cases [12], all consistent with the conjecture, and the misère results to 17 spots with reduced canonical trees [14].

This program’s parity search is not a solver of that strength: it solves positions exactly only once they have fallen apart into small enough parts, or near the end. Its value lies in combining reasonable play throughout with exact play late in the game, at the speed of a browser.

6. Two Computers⇧

Two people can play on two computers (menu Net, net.js). One hosts and gets a random three-digit room code, and the other types it in and joins as the guest. The host is Player 1 and alone starts games. Only humans play over the network.

What travels. Only topological moves, never pictures. Each computer draws its own picture with its own settings and colors, and either player may use A, R and Z without affecting the other’s picture. Spot indices agree on both sides (both start from the same count and every move adds one), so a move is sent as its two end spots, the spots enclosed on one side for a one-boundary move, and the gameKey of the position it produces (and of its mirror image, since the other side may draw it either way round). The receiver finds the move among its own legal moves that produce that position and draws it with the same machinery the computer player uses, climbing the ladder with the computer’s boxes of the Room menu (section 5.9). If it cannot draw it even so, the move is refused and taken back on both sides.

The protocol. Every message carries $k$, the number of moves made so far. The messages are hello (with the program version), game, move, undo, ack, refuse, resend, heartbeat and bye. After an action the actor waits, its page grayed, until the other side acknowledges having drawn it. Either player may undo the last move, whoever made it. If both act at once, the host’s action wins and the guest reverts its own. A message with a $k$ ahead of the receiver’s means something was missed, and a resend is asked for. Heartbeats every 3 seconds carry the position’s key, so a divergence between the two computers would be detected (and reported as a bug). If nothing has arrived for 10 seconds while the channel claims to be open, the channel is rebuilt.

The transport is a Firebase Realtime Database used as a relay, the same as in the Backgammon program on this site, whose hard-won safeguards it reuses. Messages are written to a durable queue, so a message sent while the channel is momentarily closed still arrives. This is the one part of the program that is not self-contained.

7. Running in a Browser⇧

The program is plain HTML, CSS and JavaScript: no build step, and no third-party libraries apart from Firebase for network play (and MathJax on this page). Every algorithm on this page, from the spline fitting to the grid drawing, is implemented in the program itself.

7.1. Workers

A browser page has one thread, and anything that computes for long freezes it. The heavy work therefore runs in Web Workers, separate threads that share nothing with the page and talk to it by messages:

• the thinking workers (sprouts-worker.js), as many as the Workers menu says (by default, the number of logical processors), for Monte Carlo and Parity search and for computing the candidates’ canonical forms;
• the drawing workers (sprouts-draw-worker.js), one layout each for Z, the same number;
• one worker for the router and for making room (sprouts-room-worker.js): sliding spots, pushing curves apart, and the marked route.

The modules they use (geom.js, engine.js, ai.js, and so on) are written without reference to the page, so the same files load in the page, in workers, and in Node for the test suite. Workers do not share memory here: shared memory needs special server headers (cross-origin isolation) that GitHub Pages does not send, so each thinking worker keeps its own tables. Workers do not run from a page opened as a file; the program then works on the page’s own thread and says so.

7.2. Memory

Chrome gives a page and all its workers together one JavaScript heap of at most 4 GB, however much memory the computer has. A Z layout of a crowded 30- or 40-spot position takes 50 to 110 MB, so with 32 drawing workers and 32 thinking workers the total can approach that limit. While Z runs, the idle thinking workers are therefore ended (they are started again for the computer’s next move), and the drawing workers are ended when Z is done.

When a move does not fit, the program looks for a narrower way, at half the minimum clearance, then a quarter, and so on, to explain the refusal and to know where to make room. Its grid cells shrink with the clearance, so in a large window such a search can be many times larger than the one the move was refused by: in a 100-spot game in a 3840×2103 window, a parity search with seven rays on 2-pixel cells would have had 258 million states. A search for a narrower way is therefore given up when it would have more states than the larger of two searches the program makes anyway: the same search at the Settings’ clearance, and a plain search on the finer grid. While the router’s worker is busy, a line in the log every 5 seconds names the job and the size of its searches, so that the log of a crash says what was running.

7.3. The log

The program keeps a log of the session: the start of each game, every move in words, undos, the computer’s reasoning (candidates, depth reached, verdicts), every refusal with its numbers, the drawing area’s size, and periodic “watch” lines with the memory in use and what the page is busy with. File → Save log writes it as a text file. It is also kept in the browser’s local storage as it grows, so that after a crash or a freeze the log of the session that died can still be saved (File → Save the log of the last session). Since the log names every move by its spots and the regions it creates, the positions of a game that crashed can be rebuilt from it, which is how several problems were found.

7.4. The files

The test suite runs in Node, one file per module, and checks among other things that A and R never change a position and leave every curve certified and inside the window, that Z reproduces the position of every saved test game, that every move of every saved game is legal, and the bounds of section 5.5.

8. References⇧

1. M. Gardner, Mathematical Games: Of sprouts and Brussels sprouts, games with a topological flavor. Scientific American 217(1), July 1967. scientificamerican.com
2. D. Nairn, J. Peters, D. Lutterkort, Sharp, quantitative bounds on the distance between a polynomial piece and its Bézier control polygon. Computer Aided Geometric Design 16(7), 1999, pp. 613–631. doi:10.1016/S0167-8396(99)00026-6
3. D. Applegate, G. Jacobson, D. Sleator, Computer Analysis of Sprouts. Technical report CMU-CS-91-144, Carnegie Mellon University, 1991. cs.cmu.edu (PDF)
4. E. W. Dijkstra, A note on two problems in connexion with graphs. Numerische Mathematik 1, 1959, pp. 269–271. doi:10.1007/BF01386390
5. D. C. Liu, J. Nocedal, On the limited memory BFGS method for large scale optimization. Mathematical Programming 45, 1989, pp. 503–528. doi:10.1007/BF01589116
6. F. Bertault, A force-directed algorithm that preserves edge-crossing properties. Information Processing Letters 74(1–2), 2000, pp. 7–13. doi:10.1016/S0020-0190(00)00042-9
7. W. T. Tutte, How to draw a graph. Proceedings of the London Mathematical Society s3-13(1), 1963, pp. 743–767. doi:10.1112/plms/s3-13.1.743
8. G. Kant, Drawing planar graphs using the canonical ordering. Algorithmica 16, 1996, pp. 4–32. doi:10.1007/BF02086606
9. H. de Fraysseix, J. Pach, R. Pollack, How to draw a planar graph on a grid. Combinatorica 10(1), 1990, pp. 41–51. doi:10.1007/BF02122694
10. D. E. Knuth, R. W. Moore, An analysis of alpha-beta pruning. Artificial Intelligence 6(4), 1975, pp. 293–326. doi:10.1016/0004-3702(75)90019-3
11. E. R. Berlekamp, J. H. Conway, R. K. Guy, Winning Ways for your Mathematical Plays. Academic Press, 1982; 2nd edition A K Peters, 2001–2004. (Sprouts, nimbers and the Sprague–Grundy theory.)
12. J. Lemoine, S. Viennot, Computer analysis of Sprouts with nimbers. In Games of No Chance 4, MSRI Publications 63, Cambridge University Press, 2015. arXiv:1008.2320 (PDF)
13. J. H. Conway, On Numbers and Games. Academic Press, 1976; 2nd edition A K Peters, 2001. (Chapter 12: misère games.)
14. J. Lemoine, S. Viennot, Analysis of misère Sprouts game with reduced canonical trees, 2009. arXiv:0908.4407