WWW.ABSTRACT.DISLIB.INFO FREE ELECTRONIC LIBRARY - Abstracts, online materials

<< HOME
CONTACTS

Pages:     | 1 |   ...   | 15 | 16 || 18 | 19 |   ...   | 22 |

# «Contents Ü Foreword Elwyn Berlekamp and Tom Rodgers ½ I Personal Magic ¿ Martin Gardner: A “Documentary” Dana Richards ½¿ Ambrose, Gardner, ...»

-- [ Page 17 ] --

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

reasons:

¯ 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.

Our Results

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

Time 0:

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.

Hickerson’s Synopsis

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.

Pages:     | 1 |   ...   | 15 | 16 || 18 | 19 |   ...   | 22 |

Similar works:

«1 Voynich Diagram 86v: An Interpretation Jules Janick, Thomas Ryba, and Arthur Tucker The Diagram Page 86v of the Voynich Codex (sometimes referred to as The Rosette) could be a key to decipherment and understanding of the manuscript because there are so many figures accompanied by texts. The large diagram is a composite composed of six pages pasted together (Fig. 1A). It includes 8 spheres surrounding and connected to a large sphere in the center plus three small spheres including one that is...»

«The Independent Commission for Human Rights Monthly Report on Violations of Human Rights and Public Freedoms In the Palestinian-controlled Territory September 2010 This monthly report highlights major human rights violations as monitored and documented by the Independent Commission for Human Rights (ICHR) throughout the Palestinian-Controlled Territory during the month of September, 2010. Based on ongoing monitoring and documentation of violations of human rights and public freedoms during the...»

«March 17, 2016 Todd W. Kingma Perrigo Company plc todd.kingma@perrigo.com Re: Perrigo Company plc Incoming letter dated March 17, 2016 Dear Mr. Kingma: This is in response to your letter dated March 17, 2016 concerning the shareholder proposals submitted to Perrigo by Dennis Breuel. On March 16, 2016, we issued our response expressing our informal view that Perrigo could not exclude Proposal Two from its proxy materials for its upcoming annual meeting because we were unable to conclude that...»

«§ 5-21-101. Short title This chapter shall be known and may be cited as the “County Financial Management System of 1981.” COMPARISON TO OTHER TENNESSEE COUNTIES Counties Financial Management System of 1981 Under ‘81 Act 20 Counties Bedford Lincoln Campbell Madison Carter McMinn Cumberland Monroe Fentress Morgan Franklin Rhea Giles Robertson Henderson Scott Hickman Weakley Jefferson White Counties Financial Management System of 1981 Under ‘81 Act NOT Under ‘81 Act 20 Counties 75...»

«The Way of the Pilgrim: The Unfolding Path of Buddhist Chaplaincy Final Learning Project Buddhist Chaplaincy Training Program Upaya Zen Center By: Marlee Ross January 2011 Index Pilgrimage Introduced..3 A Project of Pilgrimage.. 5 Traditional Buddhist Pilgrimage: An Unfolding Geography.9 The Way of the Pilgrim..14 Walking in the Footsteps of the Buddha: India 2010.19 The Practices of Pilgrimage..33 The Return..53 The Unfolding Path of Buddhist Chaplaincy..56 The Gift of Pilgrimage..61 In Beauty...»

«9 Maintenance and Cleaning Daily Maintenance When the NESS L300 Plus System is not in use: 1. If appropriate, reapply the covers to the hydrogel electrodes. Do not let the hydrogel dry out.2. Store the cloth electrodes where they can air dry.3. Allow the FS Cuffs to air dry.4. Check each component for wear or damage.5. Replace any components or electrodes that appear old, worn, or damaged. 6. Fully charge the L300 Plus Control Unit, Thigh RF Stim Unit, and L300 RF Stim Unit batteries. Chapter 9...»

«26th Annual General Meeting November 26, 2015 Shaw Centre Ottawa, ON 26TH ANNUAL GENERAL MEETING | ACFO-ACAF Association of Canadian Financial Officers 400 2725 Queensview Drive Ottawa, ON – K2B 0A1 1-877-728-0695 www.acfo-acaf.com 26TH ANNUAL GENERAL MEETING | ACFO-ACAF Table of contents 26th AGM Agenda Minutes of the 25th AGM (2014) Opening remarks 2014 annual report Labour relations Resource management Communications Looking forward 2013 financial report and 2015 budget Key assumptions...»

«     Speakers as of 9 November 2016 Abdullah Al Abdooli Al Marjan Island Abdullah Al HAbdooli is Managing Director of Al Marjan Island L.L.C (AMI), a master developer and real estate development company located in the Emirate of Ras Al Khaimah (RAK), UAE. A seasoned architect, Abdullah is considered a key real estate development authority within the RAK real estate sector and has spearheaded an aggressive expansion program for the Al Marjan Island development a collection of four man-made...»

«ATTORNEYS FOR APPELLANT ATTORNEYS FOR APPELLEE Susan K. Carpenter Steve Carter Public Defender of Indiana Attorney General of Indiana P. Jeffrey Schlesinger Kelly A. Miklos Deputy Public Defender Deputy Attorney General Crown Point, IN Indianapolis, Indiana In the FILED Indiana Supreme Court Jun 26 2008, 11:55 am _ CLERK No. 45S00-0608-CR-298 of the supreme court, court of appeals and tax court DARRYL JETER, Appellant (Defendant below), v. STATE OF INDIANA, Appellee (Plaintiff below). _ Appeal...»

«AAP Guía para las EPSA, AUTORIDAD DE FISCALIZACIÓN Y CONTROL SOCIAL DE AGUA POTA Y SANEAMIENTO BÁSICO sobre derechos y obligaciones con respecto a los usuarios 4111.11111 Captación Transporte EPSA EL ACCESO AL AGUA ES UN DERECHO Alma n • iento DE TODAS Y TODOS Tratamiento Distribución COOPERACIÓN Bolivia `manta Guía para las EPSA, sobre derechos y obligaciones con respecto a los usuarios CONTENIDO Introducción 1 UF La Autoridad de Fiscalización y Control Social de Agua Potable y...»

«P of TULIP Sermon #75 The New Park Street Pulpit 1 FINAL PERSEVERANCE (PERSEVERANCE OF THE SAINTS) NO. 75 A SERMON DELIVERED ON SABBATH MORNING, APRIL 20,1856, BY THE REV. C. H. SPURGEON, AT NEW PARK STREET CHAPEL, SOUTHWARK. “For it is impossible for those who were once enlightened and have tasted of the heavenly gift, and have become partakers of the Holy Spirit and have tasted the good word of God, and the powers of the age to come, if they shall fall away, to renew them again unto...»

«PART I DESTRUCTIVE LEADERS CHAPTER 1 GOAL SETTING AS AN ANTECEDENT OF DESTRUCTIVE LEADER BEHAVIORS Mary Bardes and Ronald F. Piccolo Au: Authors’ correspondence addresses should be noted A relatively new stream of research has emerged that examines the dark, or in the author bio section at the destructive, side of leadership. This research examines negative leader end of the book. behaviors in several forms including abusive supervision, petty tyranny, destructive leadership, social...»

<<  HOME   |    CONTACTS
2017 www.abstract.dislib.info - Abstracts, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.