World

Game

Of

Sprouts

Association

A “sphere” is an aggregate of “regions”. A region is an undivided area. A starting position is a single region which is gradually divided into more and more regions. Regions can contain spots. Suppose there is a tiny robot capable of traveling freely across the page except that she is unable to cross rivulets of dried ink. This robot will be confined to any particular region in which she is placed. She will be able to bump against any spot contained by the region but will not be able to touch a spot not contained by the region. She may also not be able to touch the entire exposed surface of a spot. Part of a spot might belong to a different region unreachable by her. Such a spot is called a “pivot”.

Spheres are designated by naming live spots contained by one or two of the regions in the sphere. (Naming spots contained by two regions (pivots) is the more efficient way, if it is available.) The notation begins with “S” and then names the relevant spots in parentheses. (Originally I used angle brackets, but as a concession to the wide world of browsers, I am switching over to parentheses.) The sphere S(a,b) specifies the one or two regions containing live spot a and the one or two regions containing live spot b.

With respect to a given sphere, an “outer” pivot is a pivot that lies at the periphery of the sphere such that the pivot is contained not only by the given sphere but also by some region not part of the given sphere. A sphere containing only outer pivots is called a hollow sphere. The hollow sphere H(s) is the region containing pivot s and no spots that are not outer pivots.

A biosphere is a sphere p, such that sphere p contains one or more live spots, and such that for any sphere q, sphere p contains every spot contained by sphere q or else sphere p contains no spots contained by sphere q. In other words, sphere p is completely cut off from any sphere beyond its borders. We can speak of “simple” and “composite” biospheres, with a simple biosphere being a biosphere not comprised of other biospheres and a composite biosphere being a biosphere that is not simple. The following remarks will be made with simple biospheres in mind, although with suitable qualifications they apply to composite biospheres also.

If two spheres share one or more pivots, then a move made to one of the spheres might affect the other sphere. Questions about survivors will need to take into account the interrelationship of the spheres. Survivor problems concerning only biospheres are much cleaner since a move to a biosphere can affect only that biosphere. A move to a given biosphere can be responded to immediately (unless the biosphere is exhausted) without compromising any other biosphere, and it is therefore natural to think of each biosphere of a collection of biospheres as a separate game. Thinking along these lines, we distinguish four types of biospheres. A “null” is a biosphere which, if played as a separate game, is lost by the “first player” (the player to move first to the biosphere in the separate game) in normal sprouts and is won by the first player in misere sprouts. An “inverter” is a biosphere which, if played as a separate game, is won by the first player in normal sprouts and lost by the first player in misere sprouts. A “trap” is a biosphere that, played as a separate game, is lost by the first player both in normal and misere sprouts. A “switch” is a biosphere that, played as a separate game, is won by the first player both in normal and misere sprouts.

We can restate these definitions in terms of survivor production. A cannibal is a spot with zero or two lines attached. A null is a biosphere containing C cannibals which, if played as a separate game, can be forced by either player to produce S survivors such that C and S are of the same parity. An inverter is a biosphere containing C cannibals which, if played as a separate game, can be forced by either player to produce S survivors such that C and S are of different parity. A trap is a biosphere which, if played as a separate game, will produce the second player’s choice of an even or an odd number of survivors. A switch is a biosphere which, if played as a separate game, will produce the first player’s choice of an even or an odd number of survivors.

A position comprised of multiple biospheres can be tricky. Let’s say a player “fields” a position if it is his turn to play in that position. In normal play, the player who fields a position consisting entirely of nulls is lost. If he makes a move to a particular null, his opponent will always be able to reply to that same biosphere. Every null can be thought of as a separate game, and the opponent will be able to win each of these games. Another way to describe the situation is to say that each null can be forced by either player to expire in an even number of moves, and the sum of all the nulls will therefore be an even number of moves. We can also argue successfully that a player who fields a position consisting of nulls wins in misere sprouts. And there is a sound argument which shows that a player fielding a position consisting of nulls and traps loses both in normal and misere play.

So far, so good, but there are also counterintuitive results. Since an inverter can be forced by either player to expire in an odd number of moves, it seems plausible that the player who fields a position consisting of two inverters will always lose in normal play. Surprisingly, that is not the case. This fact might be a good stopping puzzle. An odd number plus an odd number is an even number, right? So a position consisting of two inverters should always yield an even number of moves, correct? Why can the second player not always force such a position to yield an even number of moves? In Part 2, I will explain this mystery and name anyone who chooses to send in a valid solution. Please answer the question in the terms in which it is asked, without reference to Sprague-Grundy numbers. Sprague-Grundy numbers will be a topic, by the way, of Part 2.