apgsearch: a high-performance soup searcher

For general discussion about Conway's Game of Life.
wildmyron
Posts: 1274
Joined: August 9th, 2013, 12:45 am

Re: apgsearch: a high-performance soup searcher

Post by wildmyron » September 15th, 2014, 10:58 pm

@calcyman
Thank you for writing this program, it is fascinating to see the results coming out of it and I am amazed at the performance you've managed to achieve.

Have you considered scoring other soup results rather than just patterns produced, e.g.: interesting objects with no, or minimal, ash score higher, or soups which die out completely. Actually, do you have any idea of the frequency with which that occurs?
The latest version of the 5S Project contains over 221,000 spaceships. Tabulated pages up to period 160 are available on the LifeWiki.

User avatar
velcrorex
Posts: 339
Joined: November 1st, 2009, 1:33 pm

Re: apgsearch: a high-performance soup searcher

Post by velcrorex » September 15th, 2014, 11:14 pm

Thanks for making this awesome project. I've been playing around with as many non-explosive rules as I can find. I have been getting an error (here) which only seems to happen when using the rule B3468/S0378. It seems to run fine for a little bit, but within a minute, often sooner, the error will pop up. Any ideas?
-Josh Ball.

User avatar
dvgrn
Moderator
Posts: 5894
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: apgsearch: a high-performance soup searcher

Post by dvgrn » September 16th, 2014, 11:21 am

I've been having way too much fun with the latest version. Here's a small note that might be useful to other soup-explorers:

Around line 2166 of the current script is the following code:

Code: Select all

# initpos = int(g.getstring("Initial position: ", "0"))
initpos=0
If you re-enable this commented-out line and get rid of the hard-coded zero, you can run a search for a given seed, starting from any soup number N that you want. Mind you, this will write over any remaining HTML report file for that seed on your system, and the statistics will be different this time around because they'll be missing the census data for the first N-1 soups. But if you just want to quickly retrieve a high-scoring soup, it should work fine.

For example, my highest score for a soup so far is 35, for a combined MWSS+LWSS+spark coil found in a 40-million-soup run over the weekend. It wasn't really particularly interesting -- before apgsearch it would have been jaw-droppingly amazing, but not so much this week! -- so I didn't make a copy at the time. The top-scoring soup RLEs are written to a temporary directory, so it's a little harder to get hold of them again after you close Golly.

With the above code change, I typed in seed = 40M, number of soups = 100, rule = B3/S23, and initial position = 35752487, and got a fresh link to the soup in question right away, without having to re-search the 35 million soups before it:

Code: Select all

#C 40M35752487
x = 16, y = 16, rule = B3/S23
b4obo3bob2obo$bob4o6b2o$obo2b3obo2bob2o$2o2bobob5ob2o$o2b3ob2ob4o$2o2b
11o$o2bobo2b5ob2o$o2b2obobobo2bo$o7b2obobo$bobo5bo4bo$o4b2o2bobob3o$2b
3obo5b2o$obobob2o5bo$2ob5o3bobobo$2bob2obobo2b2obo$o2b3obob2obob2o!

User avatar
calcyman
Posts: 2097
Joined: June 1st, 2009, 4:32 pm

Re: apgsearch: a high-performance soup searcher

Post by calcyman » September 16th, 2014, 8:25 pm

Josh Ball wrote:I have been getting an error (here) which only seems to happen when using the rule B3468/S0378. It seems to run fine for a little bit, but within a minute, often sooner, the error will pop up. Any ideas?
Thanks. It's unsurprising that this bug has gone unnoticed for so long -- it only affects the second instance of a particular phase and orientation of a spaceship with period >= 10 which fits within a 7-by-7 box!

Again, this can be fixed by adding a few lines.
What do you do with ill crystallographers? Take them to the mono-clinic!

wildmyron
Posts: 1274
Joined: August 9th, 2013, 12:45 am

Re: apgsearch: a high-performance soup searcher

Post by wildmyron » September 17th, 2014, 6:05 am

dvgrn wrote:For example, my highest score for a soup so far is 35, for a combined MWSS+LWSS+spark coil found in a 40-million-soup run over the weekend. It wasn't really particularly interesting -- before apgsearch it would have been jaw-droppingly amazing, but not so much this week! -- so I didn't make a copy at the time. The top-scoring soup RLEs are written to a temporary directory, so it's a little harder to get hold of them again after you close Golly.
If you just want the soup from the soup string, I put hashsoup() in a separate script because I wanted to be able to do the same thing. Beware the trailing space if you copy from golly's html viewer.

Code: Select all

# hashsoup.py  Convert soup string to 16x16 soup
# Extracted from apgsearch.py v0.4, By Adam P. Goucher
# 
# Modified by Arie Paap
# Sept. 2014

import golly as g
import hashlib
# from apgsearch import hashsoup 

# Takes approximately 350 microseconds to construct a 16-by-16 soup based
# on a SHA-256 cryptographic hash in the obvious way.
def hashsoup(instring):

    s = hashlib.sha256(instring).digest()
    
    thesoup = []

    for j in xrange(32):

        t = ord(s[j])

        for k in xrange(8):

            if (t & (1 << (7 - k))):

                thesoup.append(k + 8*(j % 2))
                thesoup.append(int(j / 2))

    g.putcells(thesoup, -8, -8)


# Input the soup string:
g.new("")
soupstring = g.getstring("Enter the soup string?")
g.setname(soupstring)
hashsoup(soupstring)
I also wanted to decode the canonical representation of objects. This script decodes the representation (ignoring anything before the final '_') and places the pattern at 0,0. Now, I'm not a programmer, so this is far from efficient or pretty, but I think it works correctly. The liner growth patterns have a different representation, I haven't delved into linearlyse() yet to work out what it does.

Code: Select all

# decodeCanon.py  Create pattern from canonical representation
# An alphanumeric representation used in apgsearch by Adam P. Goucher
#
# By Arie Paap 
# Sept. 2014
# 
# ord2() from apgsearch, by Adam P. Goucher

import golly as g

def decodeCanon(canonPatt):
    chars = "0123456789abcdefghijklmnopqrstuvwxyz"
    
    ox = 0
    x = 0
    y = 0
    clist = []
    
    ii = 0
    
    while ii < len(canonPatt):
        c = canonPatt[ii]
        if (c == 'y'):
            ii += 1
            x += 4 + ord2(canonPatt[ii])
            
        elif (c == 'x'):
            x += 3
        
        elif (c == 'w'):
            x += 2
        
        elif (c == '0'):
            x += 1
        
        elif (c == 'z'):
            x = ox
            y += 5
            
        else:
            u = ord2(c)
            v = 1
            for jj in xrange(0,5):
                if (u & v):
                    clist += [x, y+jj]
                v = v << 1
            x += 1
            
        ii += 1
    
    return clist

# Converts a base-36 case-insensitive alphanumeric character into a
# numerical value.
def ord2(char):

    x = ord(char)

    if ((x >= 48) & (x < 58)):
        return x - 48

    if ((x >= 65) & (x < 91)):
        return x - 55

    if ((x >= 97) & (x < 123)):
        return x - 87

    return -1

canonPatt = g.getstring('Enter canonical representation')
canonPatt = canonPatt.strip().lower()
canonPatt = canonPatt.split('_')[-1]

if not canonPatt:
    g.exit('Pattern is empty')

patt = decodeCanon(canonPatt)
g.putcells(patt)
Edit: Updated decodeCanon.py to correct a bug with processing of >= 4 empty columns (i.e substrings of form 'yN') and switched to using ord2() from apgsearch in place of a dict.
Last edited by wildmyron on October 9th, 2014, 12:11 am, edited 2 times in total.
The latest version of the 5S Project contains over 221,000 spaceships. Tabulated pages up to period 160 are available on the LifeWiki.

User avatar
calcyman
Posts: 2097
Joined: June 1st, 2009, 4:32 pm

Re: apgsearch: a high-performance soup searcher

Post by calcyman » September 17th, 2014, 7:05 am

If you just want the soup from the soup string, I put hashsoup() in a separate script because I wanted to be able to do the same thing.
Excellent idea.
I also wanted to decode the canonical representation of objects. This script decodes the representation [...]
Great! I have the standalone script which performs the inverse operation!
The linear growth patterns have a different representation, I haven't delved into linearlyse() yet to work out what it does.
The representations of linear-growth patterns are sadly non-invertible (I can't think of a meaningful way to canonise wickstretchers, for example), although you can consult the 'first occurrence' column of the table to find a soup that produces a particular linear-growth pattern.
[...] or soups which die out completely. Actually, do you have any idea of the frequency with which that occurs?
I don't, but it shouldn't be too difficult to implement (quick hack: create a quasi-object called DIEHARD, and then call incobject whenever a soup has zero population).
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
A for awesome
Posts: 1903
Joined: September 13th, 2014, 5:36 pm
Location: 0x-1
Contact:

Re: apgsearch: a high-performance soup searcher

Post by A for awesome » September 17th, 2014, 7:00 pm

What are these "Twit" and "Prodigal sign" objects that keep appearing in the census? I have never heard these terms used before, and I haven't had the time to check what they are?
x₁=ηx
V ⃰_η=c²√(Λη)
K=(Λu²)/2
Pₐ=1−1/(∫^∞_t₀(p(t)ˡ⁽ᵗ⁾)dt)

$$x_1=\eta x$$
$$V^*_\eta=c^2\sqrt{\Lambda\eta}$$
$$K=\frac{\Lambda u^2}2$$
$$P_a=1-\frac1{\int^\infty_{t_0}p(t)^{l(t)}dt}$$

http://conwaylife.com/wiki/A_for_all

Aidan F. Pierce

wildmyron
Posts: 1274
Joined: August 9th, 2013, 12:45 am

Re: apgsearch: a high-performance soup searcher

Post by wildmyron » September 18th, 2014, 12:55 am

I updated decodeCanon.py to fix a stupid typo, remove a debugging statement and to use ord2() from apgsearch instead of using a dict, which was probably a bit silly.
calcyman wrote:
[...] or soups which die out completely. Actually, do you have any idea of the frequency with which that occurs?
I don't, but it shouldn't be too difficult to implement (quick hack: create a quasi-object called DIEHARD, and then call incobject whenever a soup has zero population).
I implemented your quick hack. The result for B3/S23 is that 1 in ~500 16x16 soups die out - less often than the lwss appears and about the same frequency at which the long barge appears.

In another thread you mentioned the p4 and p7 spaceships in B36/S245. I had also run a search there and several non-interacting pairs of p7 spaceships showed up. Is there any chance for pseudo_bangbang() to be able to separate them, or would something specific like countxwsses() be needed?

Code: Select all

x = 26, y = 28, rule = B36/S245
21bo$22bo$19bobo$20bo2$23b3o$23b2o$23bo$12bo$12bo$13bo$9b2ob2o$11b2o3$
13b3o$13b2o$13bo$3bo$3bo$4bo$2ob2o$2b2o3$3b3o$3b2o$3bo!
Also, could you add the rule used and the soup string from firstsoup to the progress file? I think this would make it possible to recreate the html census report at a later time - but additional information may also be required. If you're working on a central database to collect results, this would become redundant though.

Edited to add:
In B367/S245 two non-interacting p168 oscillators are detected as a single object. They maintain a separation distance of two cells at all times (or I'm mistaken), so I hope that they have a better chance of being correctly separated than the pairs of p7 spaceship above.

Code: Select all

x = 29, y = 7, rule = B367/S245
25b4o$3o21bo3bo$2b2o20bo3bo$3bo21b4o$3bo$2b2o$3o!
In B36/S0245 using seed "2014-09-18T15:53:57.851000_wm", in soup number "144768" a pathological object is detected, but the ash is in fact quite mundane. The sanity check at the end of linearlyse is included in my apgsearch but it is this a related issue? Soup rle:

Code: Select all

x = 16, y = 16, rule = B36/S0245
bo5b3ob3obo$2o6bo4b3o$b2o2bobobo4b2o$b2o8bo3bo$o3bobo3b2o$2bob2o3b3obo
bo$o2b2o3bobobobo$b4o2bob3ob3o$3bo7b2ob2o$2bo2b2o2bob2ob2o$bo7b2ob3o$
2bo4b4o3bo$2bob2o5b2o2bo$3b4o7bo$bobobobob2o2b3o$obo3bobob6o!
The latest version of the 5S Project contains over 221,000 spaceships. Tabulated pages up to period 160 are available on the LifeWiki.

User avatar
calcyman
Posts: 2097
Joined: June 1st, 2009, 4:32 pm

Re: apgsearch: a high-performance soup searcher

Post by calcyman » September 18th, 2014, 3:05 pm

In another thread you mentioned the p4 and p7 spaceships in B36/S245. I had also run a search there and several non-interacting pairs of p7 spaceships showed up. Is there any chance for pseudo_bangbang() to be able to separate them, or would something specific like countxwsses() be needed?
countxwsses() would probably be needed, although you could conceivably employ the strategy I'm about to mention for separating non-interacting overlapping oscillators.
In B367/S245 two non-interacting p168 oscillators are detected as a single object. They maintain a separation distance of two cells at all times (or I'm mistaken), so I hope that they have a better chance of being correctly separated than the pairs of p7 spaceship above.
Yes, I'm counting oscillators whose rotors overlap to constitute the same object. One reason for this is that otherwise, it would be possible for (say) a pseudo-object consisting of two reflectorless rotating oscillators to have an overall period of 40, but for each of its components to have period 80. And I'm not sure what this should be counted as.

In theory, using a three-dimensional array (x, y, t) we could distinguish between objects that do not causally affect each other, despite occupying the same space at different times. But Golly doesn't support 3D rules (yet?) so I would have to resort to implementing this manually (which would be awkwardly slow).
In B36/S0245 using seed "2014-09-18T15:53:57.851000_wm", in soup number "144768" a pathological object is detected, but the ash is in fact quite mundane. The sanity check at the end of linearlyse is included in my apgsearch but it is this a related issue? Soup rle:
Urgh. I have no idea why this is happening; is that oscillator somehow responsible? In particular, does that oscillator appear elsewhere in the census? (It *might* be an ExpungeObjects problem, which tries to expunge monominos.)
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
Lewis
Posts: 320
Joined: March 17th, 2009, 5:26 pm
Location: UK
Contact:

Re: apgsearch: a high-performance soup searcher

Post by Lewis » September 18th, 2014, 4:21 pm

calcyman wrote:
In B36/S0245 using seed "2014-09-18T15:53:57.851000_wm", in soup number "144768" a pathological object is detected, but the ash is in fact quite mundane. The sanity check at the end of linearlyse is included in my apgsearch but it is this a related issue? Soup rle:
Urgh. I have no idea why this is happening; is that oscillator somehow responsible? In particular, does that oscillator appear elsewhere in the census? (It *might* be an ExpungeObjects problem, which tries to expunge monominos.)
In 2x2 there's a similar thing goes on where it marks a certain oscillator as 'pathological'. For either of the objects below, it sometimes splits off the 6-cell bit (the 3 dominoes) as a pathological, but sometimes the whole oscillator gets counted correctly.

Code: Select all

x = 23, y = 4, rule = B36/S125
obo12bobob4o$obo12bobob4o$2bob4o9bo$b2ob4o8b2o!
Also, I kept having the script crash after running Day&Night for long enough, bringing up an error similar to the one screenshotted further up the thread. Is this just since the natural 2c/14 ship has period over 10 and fits in a 7x7 box too?

A for awesome wrote:What are these "Twit" and "Prodigal sign" objects that keep appearing in the census? I have never heard these terms used before, and I haven't had the time to check what they are?
I think "twit" is short for tub with tail, but I'm not sure about the other one...

wildmyron
Posts: 1274
Joined: August 9th, 2013, 12:45 am

Re: apgsearch: a high-performance soup searcher

Post by wildmyron » September 19th, 2014, 2:10 am

@calcyman
Thanks for the explanation about nearby objects. I can see the difficulties and in some cases the ambiguity of object description and identification.
calcyman wrote:
In B36/S0245 using seed "2014-09-18T15:53:57.851000_wm", in soup number "144768" a pathological object is detected, but the ash is in fact quite mundane. The sanity check at the end of linearlyse is included in my apgsearch but it is this a related issue? Soup rle:
Urgh. I have no idea why this is happening; is that oscillator somehow responsible? In particular, does that oscillator appear elsewhere in the census? (It *might* be an ExpungeObjects problem, which tries to expunge monominos.)
It does appear elsewhere, but not as often. I think Lewis' issue in 2x2 is the same.

There seem two be two problems:
* this soup - 2014-09-18T15:53:57.851000_wm144757 - decays to an oscillator, a few dots, and a p7 spaceship. stabilise(3) returns 12 when run on this soup. When census() is run for the 100 soups including this one and 2014-09-18T15:53:57.851000_wm144768 HandlePlumes is run for one step and ClassifyObjects is rerun

* The result of running CoalesceObjects and ClassifyObjects on the problem oscillator is

Code: Select all

x = 5, y = 5, rule = APG_ClassifyObjects_B36S0245
4.I$.2IJ$.J2I$.2JI$I!
Running APG_HandlePlumes on this object results in

Code: Select all

x = 5, y = 5, rule = APG_HandlePlumes
4.A$.2AB$.B2A$2.BA$A!
One of the always off cells detected by CoalesceObjects is now lost, and the neighbouring dot is subsequently expunged.

* From here on the object detection tries to deal with a non-periodic object and fails - determining it to be PATHOLOGICAL
The latest version of the 5S Project contains over 221,000 spaceships. Tabulated pages up to period 160 are available on the LifeWiki.

User avatar
Extrementhusiast
Posts: 1797
Joined: June 16th, 2009, 11:24 pm
Location: USA

Re: apgsearch: a high-performance soup searcher

Post by Extrementhusiast » September 24th, 2014, 8:54 pm

How well would the apgsearch method work on a rule like sansdomino_s13?
I Like My Heisenburps! (and others)

wildmyron
Posts: 1274
Joined: August 9th, 2013, 12:45 am

Re: apgsearch: a high-performance soup searcher

Post by wildmyron » September 25th, 2014, 12:08 am

Extrementhusiast wrote:How well would the apgsearch method work on a rule like sansdomino_s13?
My impression is that it would work really well after some adaptation. There are several places where semi-totalistic rules and rule notation are assumed. In particular, the auxillary rules and various tests that check which rule is being used. Some work would be required to generate the auxillary rules and also account for assumptions about the rule string (such as the test for glider existence). You could either create custom rules for APG_CoalesceObjects, APG_ClassifyObjects, and APG_ContagiousLife; or modify the rule generator to be able to handle rules which are not semi-totalistic. My impression is that APG_ClassifyObjects would require the most work to adapt, but I haven't thought through the details. I have been thinking about similar adaptations for multi-state rules, but I suspect that's even more complicated.

One thing to remember is that apgsearch is highly optimised for the ash left behind by B3/S23 - small still lifes, low period oscillators, and gliders. It also has some special case logic for dealing with multiple xWSSs and a few other assumptions built in. If the rule you're interested in searching is significantly different then you don't need these optimisations. SansDomino_S13 however, has sufficiently similar behaviour that you would want to keep the benefit of those optimisations. Searches there might also benefit from an adapted IdentifyGliders rule which would need to be similarly special cased as in the current version.
The latest version of the 5S Project contains over 221,000 spaceships. Tabulated pages up to period 160 are available on the LifeWiki.

User avatar
codeholic
Moderator
Posts: 1142
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: apgsearch: a high-performance soup searcher

Post by codeholic » September 26th, 2014, 2:46 pm

Do you see an easy way to adapt the script so that it would read patterns from a file, rather than generating random soups? I tried it, but it appeared not that trivial to me.

Another question that bothers me, how to get all the patterns that evolve a particular object?
Ivan Fomichev

wildmyron
Posts: 1274
Joined: August 9th, 2013, 12:45 am

Re: apgsearch: a high-performance soup searcher

Post by wildmyron » September 28th, 2014, 4:18 am

codeholic wrote:Do you see an easy way to adapt the script so that it would read patterns from a file, rather than generating random soups? I tried it, but it appeared not that trivial to me.
Quick hack: replace hashsoup(instring) with something like:

Code: Select all

def hashsoup(instring):
    
    d = os.path.dirname(g.getdir("patterns"))
    f = os.path.join(d, instring + ".rle")
    g.open(f)
and set

Code: Select all

sqrtspp = 1
Then run the script giving N as number of files to read and the filename as seed, where your pattern files are: filename0.rle, ... filenameN.rle

A better solution would be to factor the stabilisation, censusing and object recognition code into a library and write separate utilities which utilise the library to do a range of tasks.
codeholic wrote:Another question that bothers me, how to get all the patterns that evolve a particular object?
I've thought about doing that too. I guess you could adapt the awardpoints functions (if you only want uncommon objects) to add each (object, soup) pair to a list, and then write them out to the progress file in save_progress()
The latest version of the 5S Project contains over 221,000 spaceships. Tabulated pages up to period 160 are available on the LifeWiki.

User avatar
A for awesome
Posts: 1903
Joined: September 13th, 2014, 5:36 pm
Location: 0x-1
Contact:

Re: apgsearch: a high-performance soup searcher

Post by A for awesome » September 28th, 2014, 2:43 pm

I just noticed that clocks do not appear to get scored. Is there any way to correct this?
x₁=ηx
V ⃰_η=c²√(Λη)
K=(Λu²)/2
Pₐ=1−1/(∫^∞_t₀(p(t)ˡ⁽ᵗ⁾)dt)

$$x_1=\eta x$$
$$V^*_\eta=c^2\sqrt{\Lambda\eta}$$
$$K=\frac{\Lambda u^2}2$$
$$P_a=1-\frac1{\int^\infty_{t_0}p(t)^{l(t)}dt}$$

http://conwaylife.com/wiki/A_for_all

Aidan F. Pierce

User avatar
dvgrn
Moderator
Posts: 5894
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: apgsearch: a high-performance soup searcher

Post by dvgrn » September 28th, 2014, 6:58 pm

A for awesome wrote:I just noticed that clocks do not appear to get scored. Is there any way to correct this?
I guess the idea was that clocks are just a little too common to need a nonzero score:

Code: Select all

                   "xp2_2a54": ("clock", 0),
Change the above 0 to some unreasonably higher number in your copy of the script, and you'll pretty quickly be able to strain lots of clocks out of your soup. Looks like there should be one showing up every 30,000 soups or so, meaning one in every 750,000 ash objects is a clock.
codeholic wrote:Another question that bothers me, how to get all the patterns that evolve a particular object?
You can increase the score for any particular object in the same table -- or name uncommon objects you're especially interested in (I've added "xq7_3nw17862z6952": ("loafer",51) !). If your edited score is high enough, your top fifty will include all the soups with your pattern of interest... or at least fifty of them.

It looks as if you can extend the top-50 list to top-100 or more by changing one line:

Code: Select all

        for soupnum, score in ilist[:50]:

User avatar
dvgrn
Moderator
Posts: 5894
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: apgsearch: a high-performance soup searcher

Post by dvgrn » September 29th, 2014, 9:05 am

wildmyron wrote:
codeholic wrote:Another question that bothers me, how to get all the patterns that evolve a particular object?
I've thought about doing that too. I guess you could adapt the awardpoints functions (if you only want uncommon objects) to add each (object, soup) pair to a list, and then write them out to the progress file in save_progress()
Here's a hacked version of the apgsearch script that implements something along these lines. The firstoccur dictionary is changed to 'alloccur', which keeps a list of soupids for each object not on the common objects list. I didn't change anything in the progress file, though, just made more links to more patterns in the temp directory.

For really long runs this might make the dictionary a little bloated, and even just really long seed strings will make the HTML table a little ugly, but it seems to work okay otherwise. It should not be mistaken for a competent solution to the problem. If you really want first-occurrence-only links for common objects as well, there's some commented-out code that will probably work.

User avatar
A for awesome
Posts: 1903
Joined: September 13th, 2014, 5:36 pm
Location: 0x-1
Contact:

Re: apgsearch: a high-performance soup searcher

Post by A for awesome » September 29th, 2014, 2:12 pm

dvgrn wrote:
A for awesome wrote:I just noticed that clocks do not appear to get scored. Is there any way to correct this?
I guess the idea was that clocks are just a little too common to need a nonzero score.
Why is this? Pentadecathlons get a score of 15, and they're more common! Even pulsars and LWSS's have nonzero scores, and the clock is many times rarer than them.
x₁=ηx
V ⃰_η=c²√(Λη)
K=(Λu²)/2
Pₐ=1−1/(∫^∞_t₀(p(t)ˡ⁽ᵗ⁾)dt)

$$x_1=\eta x$$
$$V^*_\eta=c^2\sqrt{\Lambda\eta}$$
$$K=\frac{\Lambda u^2}2$$
$$P_a=1-\frac1{\int^\infty_{t_0}p(t)^{l(t)}dt}$$

http://conwaylife.com/wiki/A_for_all

Aidan F. Pierce

User avatar
Tropylium
Posts: 406
Joined: May 31st, 2011, 7:12 pm
Location: Finland

Re: apgsearch: a high-performance soup searcher

Post by Tropylium » September 29th, 2014, 4:46 pm

calcyman wrote:
Lewis wrote:...which made me think, how long until we start seeing soups which produce the c/7 loafer etc. in Life?
I would guess somewhere between 10^11 and 10^13 soups.
Also, anyone got any guesses as to what the next 'natural' spaceship (after glider, *WSS and combinations of 2 interaction *WSSs) will be?
Unless there's a small reasonably-high-period spaceship out there (analogous to the loafer, but hitherto-undiscovered), it's likely to be one of the following five things:
  • Loafer;
  • Sidecar on HWSS;
  • p16 Coe engine on LWSS;
  • p12 Schick engine on two LWSSes;
  • That small unnamed c/3 spaceship with no known synthesis.
Out of this list I'll be betting on the Sidecar or Coe ship. The Loafer is certainly small and "natural-mechanism" enough that it probably can be born naturally with a good frequency — but it's also sufficiently slow that its odds of surviving until census aren't that good. A stray R-pentomino can catch up with one from up to 24 cells away, and dodging gliders is also a risk.

At the other extreme, the Schick engine has excellent getaway odds, but any natural example would probably have to be formed pristine from chaos rather than being "organically synthesized" to any extent.

Something like a 2c/5 ship with a house engine or a small c/4 ship with a tetromino engine, with a small longer-period tail, also seem like fairly likely candidates for Surprizing Things That Might Turn Up, though. After all, we still have no proof on what might be the 5th smallest spaceship, either.

User avatar
Kazyan
Posts: 869
Joined: February 6th, 2014, 11:02 pm

Re: apgsearch: a high-performance soup searcher

Post by Kazyan » September 30th, 2014, 5:13 am

After getting Python to work on my laptop, apgsearch turns out to be thoroughly impressive. Usually this 4-year-old laptop overheats from even a flash game, but it survived 10,000,000 apgsearch-powered soups of B34/S26 over just a few hours, running at 1100+ soups per second. That's huge. B34/S26's ash is sparse (about one object per three soups) and 75.5% of it is blinkers, so it's a bit of an ideal case, but that just makes the search cleaner.

The breakdown of 3,373,589 objects is below.

Code: Select all

x = 37, y = 426, rule = B34/S26
o9b3ob3obobob3ob3ob3ob3o$o11bobo3bobo3bo3bo3bo3bo$o9b3ob3ob3o3bob3ob3o
b3o$10bo5bo3bo3bo3bo3bobo$10b3ob3o3bo3bob3ob3ob3o6$bo9b3ob3ob3ob3obobo
$2o11bobobo3bobo3bobo$2o9b3obobo3bob3obobo$bo9bo3bobo3bo3bobobo$11b3ob
3o3bob3obobo6$b2o8bob3ob3obobobobobo$o10bo3bo3bobobobobobo$b2o8bob3o3b
ob3obob3o$2bo8bobo5bo3bobo3bo$11bob3o3bo3bobo3bo6$bo8bob3ob3obobobob3o
$obo7bo3bo3bobobobobobo$obo7bob3o3bobob3obobo$2bo7bobo5bobo3bobobo$10b
ob3o3bobo3bob3o6$bo8bob3ob3ob3ob3obo$obo7bo3bobo5bobobobo$obo7bob3ob3o
b3ob3obo$bo8bobo3bobo3bo3bobo$10bob3ob3ob3ob3obo6$bo8bobob3obobobob3o$
2o8bobobobobobobo3bo$b2o7bobob3obob3o3bo$bo8bobo3bobo3bo3bo$10bobob3ob
o3bo3bo6$o9b3obob3ob3ob3o$2o8bobobobo5bo3bo$2o8b3obob3o3bob3o$bo10bobo
bobo3bobo$10b3obob3o3bob3o6$bobo6b3ob3ob3obobo$2o8bobo3bobo3bobo$b3o6b
3ob3ob3ob3o$2bo9bo3bo3bo3bo$10b3ob3ob3o3bo6$b3o6b3ob3ob3ob3o$o9bo3bobo
bo3bo$b3o6b3obobob3ob3o$bobo8bobobobobo3bo$10b3ob3ob3ob3o6$bo8bobob3ob
3obo$obo7bobo3bo3bobo$2bo7b3ob3ob3obo$bobo8bo3bo3bobo$b3o8bob3ob3obo6$
o10b3ob3ob3obo$3o10bobobobobobo$obo8b3ob3obobobo$3o8bo3bobobobobo$o10b
3ob3ob3obo6$2o8bobobob3o$o9bobobobobo$bo8bobobob3o$2o8bobobo3bo$bo8bob
obob3o6$bo8b3ob3ob3o$bobo8bo3bobobo$obo9bo3bobobo$2bo9bo3bobobo$12bo3b
ob3o6$2o8b3obob3o$o11bobo3bo$bo10bobob3o$2o10bobobo$bo10bobob3o6$2o8b
3obobob3o$o9bo3bobo3bo$bo8b3ob3ob3o$2o10bo3bobo$10b3o3bob3o6$o2bo6bobo
b3obobo$o2bo6bobobobobobo$o2bo6b3ob3ob3o$o2bo8bobobo3bo$12bob3o3bo6$3o
7bobob3ob3o$ob2o6bobo3bobo$4o6b3ob3ob3o$2b2o8bo3bo3bo$2bo9bob3ob3o6$6o
4b3ob3ob3o$o4bo6bobobo3bo$ob2obo4b3ob3o3bo$12bobobo3bo$2b2o6b3ob3o3bo
6$b2o8b3ob3ob3o$4o9bobo3bobo$b2obo6b3ob3ob3o$2b2o9bobobobobo$3b2o6b3ob
3ob3o6$bo8b3ob3ob3o$3obo7bobobobobo$2bo2bo4b3obobob3o$3bobo4bo3bobobob
o$10b3ob3ob3o6$4bo5bob3ob3o$3o2bo4bobobobobo$b2o2bo4bob3ob3o$3bo6bo3bo
bobo$10bob3ob3o6$4o6b3ob3o$o2bo6bo3bobo$4o6b3ob3o$4o8bo3bo$b2o7b3ob3o
6$3bo6b3obobo$b2o2bo4bo3bobo$3obo5b3ob3o$b2o2bo6bo3bo$3bo6b3o3bo6$bobo
bo4b3obobo$3o2bo6bobobo$4bo5b3ob3o$10bo5bo$10b3o3bo6$ob2o6bob3o$3b2o5b
obobo$o3bo5bob3o$2o2bo5bo3bo$b3o6bob3o6$b4o5bobobo$bo2bo5bobobo$5o5bob
3o$b4o5bo3bo$2b2o6bo3bo6$4o6bobo$2obo6bobo$ob2o6bobo$4o6bobo$10bobobo
6$bo8bobo$2o3bo4bobo$6o4b3o$o3b2o6bo$4bo7bo6$bobo6bobo$3o2bo4bobo$2b2o
2bo3b3o$4bobo5bo$12bo6$o2b4o5b3o$ob2o2bo7bo$2obo2bo5b3o$4b2o8bo$12b3o
6$3o7b3o$b2obo7bo$3bo2bo3b3o$3bo2bo3bo$5bo4b3o6$3o7b3o$o3bo7bo$2b2o6b
3o$bo3bo4bo$3b3o4b3o6$b4o5b3o$3obo7bo$bob2o5b3o$b4o5bo$3bo6b3o6$4bo7bo
$3o2b2o5bo$b2o2b3o4bo$3bo8bo$12bo6$bo3bo6bo$b2o3bo5bo$o2b2obo5bo$b2o3b
o5bo$bo3bo6bo6$2bobo2bo4bo$bo2bob3o3bo$obobo7bo$b2o9bo$o2bo8bo6$obo9bo
$o2bobo6bo$bob3o6bo$4b2o6bo$4bo7bo6$5b3o4bo$bo3bobo4bo$2b2o8bo$2o10bo$
2bo9bo6$b4o7bo$3obo7bo$bob3o6bo$b4o7bo$12bo6$obo9bo$o2bo8bo$bo10bo$3b
3o6bo$5b3o4bo$6bo5$4bo7bo$3obo7bo$4bo7bo$bo10bo$bob3o6bo$bo5$4o8bo$2ob
o8bo$ob2o8bo$4o8bo$2bo9bo6$2bo9bo$2bobo7bo$2obo8bo$2bob2o6bo$bobo8bo$
3bo!
EDIT: Lost a digit somewhere, but that's fixed (and the font). I'm doing a 100,000,000 soup run now and will report those results tomorrow. It's going to take about 22 hours. Yes, searching 100,000,000 soups is now something that a mediocre laptop can do in a day, thanks to calcyman.
Tanner Jacobi

User avatar
codeholic
Moderator
Posts: 1142
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: apgsearch: a high-performance soup searcher

Post by codeholic » September 30th, 2014, 1:25 pm

Tropylium wrote:After all, we still have no proof on what might be the 5th smallest spaceship, either.
Has it been actually ever proven, that the glider and three *WSS are the four smallest spaceships?
Ivan Fomichev

User avatar
Kazyan
Posts: 869
Joined: February 6th, 2014, 11:02 pm

Re: apgsearch: a high-performance soup searcher

Post by Kazyan » October 1st, 2014, 12:43 am

Halfway through the run, and I found a tiny bubble in the code. (42 million soups and only now does one show up. Incredible performance.) Two closely-spaced c/8 ships in a certain configuration register as one object in apgsearch v0.4. I think it's because of this phase:

Code: Select all

x = 12, y = 10, rule = B34/S26
8b2o$6bo$9bobo$5bo5bo$9bobo$2b2o2bo$b4o3b2o$3ob2o$b4o$2b2o!
One of the sparks from the right ship is two cells away from the left ship, so it "should" interfere with the left ship's evolution. But none of the cells that could be affected actually are, due to the birth numbers of the rulestring. The relevant cell that is born next generation simply appears due to the "4" instead of the "3", for example.

The two ships in question appear from this seed and soup number:
Kazyan's100M_2014-09-30T12:09:21.346000_31187720
Tanner Jacobi

wildmyron
Posts: 1274
Joined: August 9th, 2013, 12:45 am

Re: apgsearch: a high-performance soup searcher

Post by wildmyron » October 1st, 2014, 3:35 am

Kazyan wrote:Halfway through the run, and I found a tiny bubble in the code. (42 million soups and only now does one show up. Incredible performance.) Two closely-spaced c/8 ships in a certain configuration register as one object in apgsearch v0.4. ...
The same issue in a different rule was discussed earlier in this thread. It's unlikely to get a general solution, but if you care about a particular rule then a specific solution is probably not too much work (not that I'm volunteering :) ).
The latest version of the 5S Project contains over 221,000 spaceships. Tabulated pages up to period 160 are available on the LifeWiki.

User avatar
lukebradford
Posts: 100
Joined: October 11th, 2013, 8:07 pm
Location: Cambridge, MA
Contact:

Re: apgsearch: a high-performance soup searcher

Post by lukebradford » October 1st, 2014, 9:40 am

This is extremely cool, thanks for making it!

Post Reply