Site Info

Authors
  • H.Koenig
  • Adam Goucher
  • Dave Greene

« Completed Universal Computer/Constructor | Main | Update: new territory for Online Soup Search »

2009 August 31

Discovery
Progress of the Online Soup Search

Over the last couple of months, Nathaniel Johnston's Online Soup Search for Conway's Life has been hunting for 20x20 random "methuselah" patterns, using a modest-sized distributed network -- a good fraction of the spare CPU cycles of perhaps a dozen computers. As of the end of August, the conwaylife.com server has tallied the final stabilizations of over 111 million random 20x20 Conway's Life "soups", totaling over three billion Life objects (still-life, oscillator, or spaceship). This is slowly approaching the scale of Achim Flammenkamp's earlier random-ash census project from a decade and a half ago -- which represented an impressive amount of dedicated CPU time for 1994.

Version 1.03 of the soup-search script is now available. It's a Python script that will run on the current version of Golly for Windows, Mac, or Linux. Version 1.03 displays much more detail about the progress of the current search.

Methuselah survival times appear to fit a simple inverse exponential sequence. Lifespans between 1000(N-1) and 1000N are about twice as frequent as lifespans between 1000N and 1000(N+1) -- for a wide range of N. Version 1.03 of the script continuously updates an on-screen table of these frequencies, starting at N=5. It is an open question how far this relationship continues, or whether a larger sample will yield a more precise approximation of the curve.


The longest-lived methuselah found so far by the Online Soup Search is the pattern at right, which lasts over 25,000 ticks before stabilizing. Previous search efforts have done considerably better -- the record-holder is Andrzej Okrasinski's "Lidka", found by his "Life Screensaver" Windows software in 2005, in a run of some 12 billion 20x20 soups -- apparently somewhere near the 3-billion-soups mark. Unfortunately, however, the email address given on the website does not appear to be functional, and some compatibility problems have been reported with the screensaver utility in recent versions of Windows.

With current CPU resources, "Lidka" is not likely to be surpassed very quickly. If the exponential drop in methuselah frequency continues at a similar rate through the next several 1000-tick "bins", then a methuselah lasting 30,000+ ticks might be expected to turn up, very roughly, sometime in the next year or two, after several billion soup patterns have been tallied. This lines up fairly well with the number of soups examined to discover "Lidka", though of course there are no guarantees that the first 30,000+ methuselah will appear at exactly the "right" time (statistically speaking).

Of course, the time needed to find a new record-breaker will go way down if enough computers join the distributed search effort...!