Generalizing the Survivor Concept

April 21, 2006

We can give the survivor concept a bit more generality by conceiving of the exhausted position as a species of switch, a "no-switch," a theoretical but unplayable switch. Let such a "switch" be called a Y0. In this context we will call survivors "switchmen," and we define switchmen as the cannibals remaining when all waiting moves in a switch have been used up, when a move must be made to resolve the switch if any move is to be made at all. Let any position consisting of trap plus switchmen also be called a Y0.

Of Y0's, we can distinguish two subtypes: positions that hold an even number of switchmen, and positions that hold an odd number of switchmen. Our shorthand for these two types of positions will be Y0-0 and Y0-1, respectively.

We now offer a recursive definition for an infinite hierarchy of positions. For position Yp there are two subtypes: Yp-0 and Yp-1. We say that Yp-0 holds an even number of switchmen and yp-1 holds an odd number of switchmen. Further, for integer p > 0, we say, without loss of generality, that the switch Yp branches in one move to each subtype of positions Y0, Y1, ..., Y(p - 1), but not to both subtypes of Yp. Thus, we say that a Y1 branches in one move to a Y0-0 and to a Y0-1, but not to both a Y1-0 and a Y1-1. We say that a Y2 branches in one move to a Y0-0, to a Y0-1, to a Y1-0, and to an Y1-1, but not to both a Y2-0 and a Y2-1. And so forth.

The Grundy number of a given Yp-q that contains an even number of cannibals is equal to 2p + q. The Grundy number of a given Yp-q that contains an odd number of cannibals is equal to 2p + 1 - q. This ability to translate from switch terminology to Grundy terminology reveals that "switch theory" is a disguised form of Grundy theory and will have value, if at all, only as a shortcut.

Positions containing an even number of Y1's and no Y2's or higher are probably the most conducive to effective counting of switchmen: Y1's are often simple to spot and the quantity of their associated switchmen to project, and the parity of the sum of the switchmen in the total position will determine which side has the advantage without direct resort to Grundy numbers.

Back to World Game of Sprouts Association Home Page