World
Game
Of
Sprouts
Association
We asked the question, why is it not always true that a person who fields an even number of inverters, and no other biospheres, must lose in normal sprouts? The answer is that it is not necessarily true that each of these inverters will be played “as a game”, i.e. with players alternating moves. Either player can force a given inverter to yield an odd number of moves, if the two players alternate in making moves to the inverter – by definition of “inverter”. But if the two players do not alternate in making moves, if, for instance, one player is able to move twice in succession to the inverter, there are no guarantees. Thus, the fielded position is not necessarily hopeless.
Suppose I field two inverters, inverter A and inverter B, and no other biospheres. Suppose also that my opponent has the plan of playing each inverter as a separate game. Providing that inverter A contains at least three moves, I can thwart my opponent’s plan. I first move to A. My opponent now must play to A or I can play to A on my second move and my opponent’s plan has been thwarted. (His plan, remember, is simply to play each inverter as a separate game (such that the opponents alternate moves on each inverter). The fact that I thwart this “plan” does not imply that I win.) I now move to B until B is exhausted. My opponent will have to respond to each of these moves by moving also to B, by the same logic as above. Since B is an inverter, and since it is being played as a separate game (i.e. with alternating moves), I can force B to yield an odd number of moves, which I do. I make the last move to B. My opponent is forced to move to A, and his plan has been thwarted.
Whether or not thwarting my opponent in this way does me any good in regards to the total outcome depends upon the nature of the individual inverters. The four types of biospheres that I have identified – inverters, null, traps, and switches – form a closed set under the operation of moving. A given biosphere at a given moment will be one of these four types, and after any move the biosphere will still be one of these types. There are logical restrictions, however, on how moves affect biospheres. A trap, for instance, is defined as a biosphere which, played as a separate game, is won by the “second player” in both normal and misere play. It follows from this definition that a trap must always be changed to a nontrap by any possible move to the trap. If the first player could keep the trap a trap, then he would enjoy the benefits which the second player, by definition, is supposed to enjoy. On the other hand, there is no logical prohibition against a switch remaining a switch. A switch is defined as a biosphere which, played as a separate game, can be won by the first player in both normal and misere play. The key word is “can”. The first player has the power to win, but winning is not necessarily mandatory. In some cases the first player voluntarily can give up his power, can make a “waiting move” which leaves the biosphere still a switch.
Positions with multiple switches are often quite difficult to play, precisely because of these “waiting moves”. If I leave my opponent with a position consisting of two switches, I might naively believe that I have a sure win. I might reason that any action my opponent takes in regards to one switch can be effectively countered by play to the other. But the waiting move wild card makes it hard. If the first person to turn a switch to a nonswitch must lose, as is often the case, the game comes down to who can make the last waiting move. Often a bewildering tree of possible waiting moves must be taken into account.
Waiting moves also can affect inverters. It follows from definition that an inverter can be changed in one move to a null, but not to a trap or to another inverter. Deduction from definition also does not rule out – but does not require – the possibility that a move can change a given inverter to a switch. Subtleties in connection with this possibility can lead to surprising results.
The biosphere jungle can be partially cleared and civilized by the use of Sprague-Grundy numbers. A biosphere which, if played as a separate game, loses for the “first player” in normal sprouts has the Sprague-Grundy number zero. Sprague-Grundy number zero means that the biosphere loses for the first player in normal play. Nulls and traps always have Sprague-Grundy numbers of zero.
A biosphere which, played as a separate game, wins for the first player in normal sprouts is assigned a Sprague-Grundy number which is a positive integer. The assignment procedure is recursive. The Sprague-Grundy number of a given biosphere B depends upon the Sprague-Grundy numbers of the various biospheres which B could become in a single move. If a single move could transform biosphere B to a biosphere with Sprague-Grundy number N, let us say that biosphere B “branches” to N. Using this terminology, we can say that a biosphere B has the Sprague-Grundy number which is the least positive integer to which B does not branch. For instance, if B can become a biosphere with Sprague-Grundy number zero or a biosphere with Sprague-Grundy number one or a biosphere with Sprague-Grundy number three but no other biospheres, then B has the Sprague-Grundy number of two.
The point of Sprague-Grundy numbers is the famous algorithm which assures one of the players that he can eventually leave his opponent a losing position of all traps and nulls. (He can be assured that he can play each trap and null as a separate game and can force an even number of moves from each.) Convert each Sprague-Grundy number to binary and stack these numbers so that columns align. If there are an even number of “1”s in each column then the player to move has a lost position. Any move he makes will flip one or more columns in a single Sprague-Grundy number. There will now be an odd number of “1”s in at least one column. If the move played involved branching to a larger number than the original number, the opponent can simply play a move which converts the larger number back to the original number. (Remember, a biosphere of a given number can branch to all smaller integers, down to zero.) If, on the other hand, the original move involved branching to a smaller number – the only other possibility – then there will be another biosphere which can be altered to restore an even number of ones in each column. The leftmost “1” in the number altered must be matched by a “1” in some other number, and when this matching “1” is flipped, all of the “1”s in the columns to the right of it can be flipped as needed. Since the opponent always can leave a position with even numbers of “1”s in each column, he is assured that he eventually will leave all “0”s in every column of every number. (Moves must run out, and zero is an even number.)
The application of this clever algorithm has two limitations. In sprouts it can be difficult to determine the Sprague-Grundy number of a switch or inverter. This determination often can only be made by tracing through all of the branches of the tree, usually an impossibly laborious task. The second limitation is that the algorithm only works for normal sprouts.