«Contents Ü Foreword Elwyn Berlekamp and Tom Rodgers ½ I Personal Magic ¿ Martin Gardner: A “Documentary” Dana Richards ½¿ Ambrose, Gardner, ...»
Drawing de Bruijn Graphs Herbert Taylor The simplest kind of de Bruijn graph, in which the number of nodes is a power of two, has, at each node, two edges directed out and two edges directed in.
When the number of nodes is ¾ Ò we can label them with the integers from ¼ to ¾ Ò ½ and notice that they correspond to all the numbers expressible with Ò bits (Ò binary digits). Out from the node labeled Ü the two directed edges go to the nodes labeled ¾Ü and ¾Ü·½. If ¾Ü or ¾Ü·½ is bigger than ¾Ò ½, just subtract ¾ Ò from it to bring the number back into the range from ¼ to ¾ Ò ½.
There is reason to think that the picture for Ò may ﬁll a gap in the existing literature, because Hal Fredricksen told me he had not seen it in any book. Pictures up to Ò can be found in the classic “Shift Register Sequences” by Solomon W. Golomb, available from Aegean Park Press.
Bigger de Bruijn graphs get really hairy. The picture for Ò suggests 2-pire fashion½ for drawing the de Bruijn graph on the sphere without any lines crossing each other. The scheme would be to put ¼ on the North pole, ¾Ò ½ on the South pole, the numbers from ½ to ¾ Ò ¾ in order going south down the Greenwich Meridian, and down the international date line.
Edges out from ¼ to ¾ Ò ½ ½ on the meridian go east to the dateline, while edges out from ¾ Ò ½ to ¾Ò ½ go west.
½In 2-pire fashion each node of the graph is allowed to appear in two places in the picture. The earliest reference I know of to the m-pire (empire) problem is P. J.
Heawood’s 1891 paper in the Quarterly Journal of Mathematics.
See Scientiﬁc American, February 1980, Vol. 242, No. 2, “Mathematical Games,” by Martin Gardner, pp. 14–22.
Computer Analysis of Sprouts David Applegate, Guy Jacobson, and Daniel Sleator Sprouts is a popular (at least in academic circles) two-person pen-and-paper game. It was invented in Cambridge in 1967 by Michael Patterson, then a graduate student, and John Horton Conway, a professor of mathematics.
Most people (including us) learned about this game from Martin Gardner’s “Mathematical Games” column in the July 1967 issue of Scientiﬁc American.
The initial position of the game consists of a number of points called spots. Players alternate connecting the spots by drawing curves between them, adding a new spot on each curve drawn. Each curve must be drawn on the paper without touching itself or any other curve or spot (except at end points). A single existing spot may serve as both endpoints of a curve.
Furthermore, a spot may have a maximum of three parts of curves connecting to it. A player who cannot make a legal move loses. Shown below is a sample game of two-spot Sprouts, with the ﬁrst player winning. Since draws are not possible, either the ﬁrst player or the second player can always force a win, regardless of the opponent’s strategy. Which of the players has this winning strategy depends on the number of initial spots.
Sprouts is an impartial game: The same set of moves is available to both players, and the last player to make a legal move wins. Impartial games have variants where the condition of victory is inverted: The winner is the Figure 1. A sample game of two-spot Sprouts.
200 D. APPLEGATE, G. JACOBSON, AND D. SLEATOR player who cannot make a legal move. This is called the losing or misère version of the game.
While Sprouts has very simple rules, positions can become fantastically complicated as the number of spots, n, grows. Each additional spot adds between two and three turns to the length of the game, and also increases the number of moves available at each turn signiﬁcantly. Games with small numbers of spots can be (and have been) completely solved by hand, but as the number of spots increases, the complexity of the problem overwhelms human powers of analysis. The ﬁrst proof that the ﬁrst player loses in a six-spot game, performed by Denis Mollison (to win a 10-shilling bet!), ran to 47 pages.
Conway said that the analysis of seven-spot Sprouts would require a sophisticated computer program, and that the analysis of eight-spot Sprouts was far beyond the reach of present-day (1967!) computers. Of course, computers have come a long way since then. We have written a program that determines which player has a winning strategy in games of up to eleven spots, and in misère games of up to nine spots.
Our Sprouts Program As far as we know, our program is the only successful automated Sprouts searcher in existence. After many hours of late-night hacking and experimenting with bad ideas, we managed to achieve sufﬁcient time- and spaceefﬁciency to solve the larger games. Our program is successful for several
¯ We developed a very terse representation for Sprouts positions. Our representation strives to keep only enough information for move generation. Many seemingly different Sprouts positions are really equivalent. The combination of this low-information representation and hashing (whereby the results of previous searches are cached) proved to be extremely powerful.
¯ Many sprouts positions that occur during the search are the sum of two or more non-interacting games. Sometimes it is possible to infer the value of the sum of two games given the values of the subgames.
Our program makes use of these sum identities when evaluating normal Sprouts. These ideas are not nearly as useful in analyzing misère Sprouts. This is the principal reason that we are able to extend the analysis of the normal game further than the misère game.
¯ We used standard techniques to speed adversary search, such as cutting off the search as soon as the value is known, caching the results COMPUTER ANALYSIS OF SPROUTS 201 of previous searches in a hash table, and searching the successors of a position in order from lowest degree to highest.
¯ The size of the hash table turned out to be a major limitation of the program, and we devised and implemented two methods to save space without losing too much time efﬁciency. We discovered that saving only the losing positions reduced the space requirement by a large factor. To reduce the space still further we used a data compression technique.
Here’s what our program found:
A “1” means the ﬁrst player to move has a winning strategy, a “2” means the second player has a winning strategy, and an asterisk indicates a new result obtained by our program.
The n-spot Sprouts positions evaluated so far fall into a remarkably simple pattern, characterized by the following conjecture:
Sprouts conjecture. The ﬁrst player has a winning strategy in n-spot Sprouts if and only if n is 3, 4, or 5 modulo 6.
The data for misère Sprouts ﬁt a similar pattern.
Misère sprouts conjecture. The ﬁrst player has a winning strategy in n-spot misère Sprouts if and only if n is 0 or 1 modulo 5.
We are still left with the nagging problem of resolving a bet between two of the authors. Sleator believes in the Sprouts Conjecture and the Misère Sprouts Conjecture. Applegate doesn’t believe in these conjectures, and he bet Sleator a six-pack of beer of the winner’s choice that one of them would fail on some game up to 10 spots. The only remaining case required to resolve the bet is the 10-spot misère game. This problem seems to lie just beyond our program, our computational resources, and our ingenuity.½
The Gathering for Gardner Atlanta International Museum of Art and Design Atlanta, Georgia Dear Gathering, Martin Gardner, by singlehandedly popularizing Conway’s game of Life during the 1970s, sabotaged the Free World’s computer industry beyond the wildest dreams of the KGB. Back when only the large corporations could afford computers because they cost hundreds of dollars an hour, clandestine Life programs spread like a virus, with human programmers as the vector. The toll in human productivity probably exceeded the loss in computer time.
With the great reduction in computation costs, and the solution of most of the questions initially posed by the game, it would be nice to report that, like smallpox, the Life bug no longer poses a threat. Sadly, this is not the case. While the Life programs distributed with personal computers are harmless toys whose infective power is 100% cancelled by TV, new developments in the game are still spreading through computer networks, infecting some of the world’s best brains and machinery.
The biggest shock has been Dean Hickerson’s transformation of the computer from simulation vehicle to automated seeker and explorer, leading to hundreds of unnatural, alien Life forms, of which the weirdest, as of late 1992, has to be
Note that it extends leftward with velocity ½, with the left end (found by Hartmut Holzwart at the University of Stuttgart) repeating with period
4. But the (stationary) right end, found by Hickerson (at U.C. Davis) has period 5! Stretching between is a beam of darts that seems to move rightward at the speed of light. But if you interrupt it, the beam shortens in both directions at the speed of light, and then both ends explode.
204 B. GOSPER
Times 100–105:STRANGE NEW LIFE FORMS: UPDATE 205
So, if you’re wondering “Whatever happened to Life?,” here is a synopsis of recent developments computer-mailed by Hickerson when the ineffable Creator of the Universe and its Laws himself asked the same question.
There have been developments in various areas by different people:
resembling your initials, JHC!), a few oscillators with periods 5 (including some with useful sparks) and 6, inﬁnitely many period 2, speed c/2 orthogonal spaceships, inﬁnitely many period 3, speed c/3 orthogonal spaceships, one period 4, speed c/4 orthogonal spaceship, one period 4, speed c/4 diagonal spaceship (not the glider), and one period 5, speed 2c/5 orthogonal spaceship. More recently, David Bell wrote a similar program that runs on faster machines. (Mine runs only on an Apple II.) Lately, he and Hartmut Holzwart have been producing oodles of orthogonal spaceships with speeds c/2, c/3, and c/4. Also, Hartmut found another with speed 2c/5.
Some of the c/3s and c/4s have sparks at the back which can do various things to c/2 spaceships that catch up with them. (These are used in some of the large patterns with unusual growth rates mentioned later.) Construction of Oscillators. Due mostly to the work of Buckingham and Wainwright, we now have nontrivial examples (i.e., not just lcms of smaller period oscillators acting almost independently) of oscillators of periods
½ ½ ½ ¾ ¾ ¾ ¿¼ ¿¾ ¿ ¼ ¾ ¼ ¾ ½¼¼ ½¼ ½¾
· ½¾¼Ò ½¿ · ½¾¼Ò · ¾ Ò ¾ · ¾ Ò ¼ · ¾ Ò ¾¿¼ · ¼Ò ¾ ¾ · ¿ Ò·¿ Ò ½¿ · Ò ½ ¼· Ò and all multiples of ¿¼ and ½¼¼. We also have an argument, based on construction universality, which implies that all sufﬁciently large periods are possible. (No doubt you ﬁgured that out for yourself long ago.) The multiples of ¿¼ and ½¼¼ and the · ½¾¼Ò and ½¿ · ½¾¼Ò are based on gliders shuttling back and forth between either oscillators (or periods ½ ¿¼ and ½¼¼) or output streams of glider guns (of periods
· ¾ Ò ¾ · ¾ Ò ¼ · ¼Ò ¾¿¼ ·¿¼ and ¼¼ · ¾¼¼Ò). The ¼Ò ¾ ¾ · ¿ Ò and · ¿ Ò use a device discovered by Wainwright, which reﬂects a symmetric pair of parallel gliders; it consists of a still life (“eater3”) and two spark producing oscillators, of periods 5, 6, or 47. (Any greater nonmultiple of 4 would also work, but 5, 6, and 47 are the only ones we know with the right sparks.) Periods ½¿ · Ò and ½ ¼ · Ò use a mechanism developed by Buckingham, in which a B heptomino is forced to turn a 90 Æ corner. The turn can take either 64, 65, or 73 generations;
by combining them we can build a closed loop whose length is any large multiple of 5 or 8; we put several copies of the B in the track to reduce the period to one of those mentioned. For example, I built a p155 oscillator in which 20 Bs travel around a track of length ¿½¼¼´ ¾¼ ¢ ·¾ ¢ µ generations. For the multiples of 8, the 73 gen turn can emit a glider, so we also get glider guns of those periods.
Another amusing oscillator uses the glider crystallization that Bill mentioned in his centinal letter a few years ago. A period 150 gun ﬁres toward a distant pair of pentadecathlons. The ﬁrst glider to hit them is reﬂected STRANGE NEW LIFE FORMS: UPDATE 207 180Æ and collides with the second to form a honey farm. Subsequent gliders grow a crystal upstream; 11 gliders add a pair of beehives to the crystal.
When the crystal reaches the guns, an eater stops its growth, and it begins to decay; two gliders delete one pair of beehives. When they’re all gone, the process begins again.
Glider Syntheses. Rich has already mentioned this. I’ll just add that some of Buckingham’s syntheses of still lifes and billiard table oscillators are aweinspiring.
New Glider Guns. In addition to the long-familiar period 30 and period 46 guns, there’s now a fairly small period 44 gun that Buckingham built recently. The other guns are all pretty big. The largest by far that’s actually been built is Bill’s period 1100 gun (extensible to ¼¼ · ¾¼¼Ò), based on the period 100 centinal; its bounding box is 13,584 by 12,112. Buckingham mercifully outmoded it with a comparatively tiny, centinal-based ¼¼ · ¾¼¼Ò.
The period ½¿ · Ò guns based on Buckingham’s B heptomino turns are ´ ¢ ¿ · ¢ µ gun also smaller. For example, there’s a period ½ ´ ¼ ¢ ¿ · ½ ¢ µ ¾ gun that’s 309 that’s 119 by 119 and a period ½¿ by 277.
Buckingham has also found extremely weird and elegant guns of periods 144 and 216, of size 149 by 149, based on a period 72 device discovered by Bob Wainwright.