ConwayLife.com - A community for Conway's Game of Life and related cellular automata
Home  •  LifeWiki  •  Forums  •  Download Golly

Rulesrc: Finding rules for a spaceship

For scripts to aid with computation or simulation in cellular automata.

Re: Rulesrc: Finding rules for a spaceship

Postby Saka » September 5th, 2017, 8:56 am

I have an idea of a script very similar to this but looks for a rule where a pattern becomes another.
If your input pattern is this (Blue=selected)
x = 10, y = 4, rule = LifeHistory
A2B$3B$B2A5.2A$B2A5.2A!

It will ask you "What is the space between the boxes?", and you enter 5, it will count 5 cells from the right edge of the box and "copy" the selection there:
x = 11, y = 16, rule = LifeHistory
A2B5.3B$3B5.3B$B2A5D2AB$B2A5.2AB$5.D$4.3D$3.D.D.D$5.D$5.D$5.D2$4.3D$
4.D$4.3D$6.D$4.3D!

Now I know you can't have 2 selections at once, but you can save each selection as a cell list or something.
The script will then take the first selection and run it in a bunch of different rules and try to find it. It would also use the g.note function to note how many generations it takes from pattern a to b.

This could be useful for finding reactions such as
x = 17, y = 7, rule = LifeHistory
BA5B3.7B$2BA4B3.7B$3A4B3.7B$7B3.7B$7B3.7B$5B2A3.3B2A2B$5B2A3.3B2A2B!
Everyone, please stop posting B/S about CA
x = 17, y = 10, rule = B3/S23
b2ob2obo5b2o$11b4obo$2bob3o2bo2b3o$bo3b2o4b2o$o2bo2bob2o3b4o$bob2obo5b
o2b2o$2b2o4bobo2b3o$bo3b5ob2obobo$2bo5bob2o$4bob2o2bobobo!

(Check gen 2)
User avatar
Saka
 
Posts: 2267
Joined: June 19th, 2015, 8:50 pm
Location: In the kingdom of Sultan Hamengkubuwono X

Re: Rulesrc: Finding rules for a spaceship

Postby muzik » September 5th, 2017, 2:46 pm

Suggestion: The script could output its results to Catagolue by submitting them under a "rulesrc" pseudosymmetry under the rule the ship was found in.
2c/n spaceships project

Current priorities: see here
muzik
 
Posts: 2612
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Rulesrc: Finding rules for a spaceship

Postby Naszvadi » September 5th, 2017, 3:07 pm

Greetings!

Neat Rulesrc, grats+thnx!

My attempt to kill the party is a process proposal for a complex glider/osc finder application:
  1. generate list of bounded patterns that are sorted (e.g. (greater dim:smaller dim:bitmap-in-integer)
    1. iterating on list:recurse on a pattern evolving it and branching on used hensel notatitions between each recursion steps. Stopping criteria is:
    2. reaching maximal recursion depth (pattern with current rulemask remain uncategorized - usually in exploding rules)
    3. evolving into a _smaller_ pattern - e.g. using a function defined at pattern list generation
    4. reaching a loop

This will certainly be faster than inspecting 2**102 rules (excluding some trivial cases, but there would be still exponentially many rules)

Well, I published a pattern generator in the forum, but is still buggy. Its C version is hopefully not :oops:

Further improvements may cover automated wikibot feeding, haul comparison input generators etc.
Naszvadi
 
Posts: 193
Joined: May 7th, 2016, 8:53 am

Re: Rulesrc: Finding rules for a spaceship

Postby Rhombic » September 15th, 2017, 11:27 am

Towards a Progressive Rulesrc
A self-correcting Rulesrc would be interesting enough to attempt to find cell configurations, but one of the initial steps is to allow variation in the number of identical generations. Note that this yields similar and not necessarily identical ships, but for many purposes it's good enough. The idealised script should be able to identify good leads, allowing much quicker finds of interesting spaceships from decent inputs.

The following example already gives surprisingly good results for such a terribly hand-waving algorithm!! But I really hope you don't think I'm wasting your time, since it shows how that little addition, still far away from the optimum, already gives promising results.

# progRulesrc.py
#
# Expanded from Rulesrc by Rhombic, Sep 2017.
# Arie Paap, Aug 2017
# Nathaniel Johnston (nathaniel@nathanieljohnston.com), June 2009.
# Updated by: Peter, NASZVADI (), June 2017.
# Grafted by Rhombic, Aug 2017.

import golly as g
import itertools
import random
from glife import validint
from string import replace

def Rulesrc(familytree,maxiteration):
    g.select(g.getrect())
    if not g.empty():
        g.clear(0)
    g.putcells(cell_list)
    # Search parameters

    # Stop if pattern is a ship with this minimum period
    minShipP = 1
    # Stop if pattern is an oscillator with this minimum period
    minP = 3
    # Maximum period to test the pattern for
    maxGen = 1000
    # Maximum population in any phase
    maxPop = 300
    # Allow search for oscillators
    bOsc = False

    Hensel = [
        ['0'],
        ['1c', '1e'],
        ['2a', '2c', '2e', '2i', '2k', '2n'],
        ['3a', '3c', '3e', '3i', '3j', '3k', '3n', '3q', '3r', '3y'],
        ['4a', '4c', '4e', '4i', '4j', '4k', '4n', '4q', '4r', '4t', '4w', '4y', '4z'],
        ['5a', '5c', '5e', '5i', '5j', '5k', '5n', '5q', '5r', '5y'],
        ['6a', '6c', '6e', '6i', '6k', '6n'],
        ['7c', '7e'],
        ['8']
    ]

    # Python versions < 2.4 don't have "sorted" built-in
    try:
        sorted
    except NameError:
        def sorted(inlist):
            outlist = list(inlist)
            outlist.sort()
            return outlist

    # --------------------------------------------------------------------

    def chunks(l, n):
        for i in range(0, len(l), n):
            yield l[i:i+n]

    # --------------------------------------------------------------------

    def rulestringopt(a):
        result = ''
        context = ''
        lastnum = ''
        lastcontext = ''
        for i in a:
            if i in 'BS':
                context = i
                result += i
            elif i in '012345678':
                if (i == lastnum) and (lastcontext == context):
                    pass
                else:
                    lastcontext = context
                    lastnum = i
                    result += i
            else:
                result += i
        result = replace(result, '4aceijknqrtwyz', '4')
        result = replace(result, '3aceijknqry', '3')
        result = replace(result, '5aceijknqry', '5')
        result = replace(result, '2aceikn', '2')
        result = replace(result, '6aceikn', '6')
        result = replace(result, '1ce', '1')
        result = replace(result, '7ce', '7')
        return result

    clist = []
    rule = g.getrule().split(':')[0]

    fuzzer = rule + '9'
    oldrule = rule
    rule = ''
    context = ''
    deletefrom = []
    for i in fuzzer:
        if i == '-':
            deletefrom = [x[1] for x in Hensel[int(context)]]
        elif i in '0123456789/S':
            if deletefrom:
                rule += ''.join(deletefrom)
                deletefrom = []
            context = i
        if len(deletefrom) == 0:
            rule += i
        elif i in deletefrom:
            deletefrom.remove(i)
    rule = rule.strip('9')

    if not (rule[0] == 'B' and '/S' in rule):
        g.exit('Please set Golly to a Life-like rule.')

    if g.empty():
        g.exit('The pattern is empty.')

    s = str(familytree)
    if not validint(s):
        g.exit('Bad number: %s' % s)

    numsteps = int(s)
    if numsteps < 1:
        g.exit('Period must be at least 1.')

    g.select(g.getrect())
    g.copy()
    s = int(s)

    for i in range(0,s):
        g.run(1)
        clist.append(list(chunks(g.getcells(g.getrect()), 2)))
        mcc = min(clist[i])
        clist[i] = [[x[0] - mcc[0], x[1] - mcc[1]] for x in clist[i]]

    g.show('Processing...')

    ruleArr = rule.split('/')
    ruleArr[0] = ruleArr[0].lstrip('B')
    ruleArr[1] = ruleArr[1].lstrip('S')

    b_need = []
    b_OK = []
    s_need = []
    s_OK = []

    context = ''
    fuzzed = ruleArr[0] + '9'
    for i in fuzzed:
        if i in '0123456789':
            if len(context) == 1:
                b_need += Hensel[int(context)]
                b_OK += Hensel[int(context)]
            context = i
        elif context != '':
            b_need.append(context[0] + i)
            b_OK.append(context[0] + i)
            context += context[0]
    context = ''
    fuzzed = ruleArr[1] + '9'
    for i in fuzzed:
        if i in '0123456789':
            if len(context) == 1:
                s_need += Hensel[int(context)]
                s_OK += Hensel[int(context)]
            context = i
        elif context != '':
            s_need.append(context[0] + i)
            s_OK.append(context[0] + i)
            context += context[0]

    for i in [iter2 for iter1 in Hensel for iter2 in iter1]:
        if not i in b_OK:
            b_OK.append(i)
            execfor = 1
            # B0 and nontotalistic rulestrings are mutually exclusive
            try:
                g.setrule(rulestringopt('B' + ''.join(b_OK) + '/S' + ruleArr[1]))
            except:
                b_OK.remove(i)
                execfor = 0
            for j in range(0, s * execfor):
                g.run(1)
                try:
                    dlist = list(chunks(g.getcells(g.getrect()), 2))
                    mcc = min(dlist)
                    dlist = [[x[0] - mcc[0], x[1] - mcc[1]] for x in dlist]
                    if not(clist[j] == dlist):
                        b_OK.remove(i)
                        break
                except:
                    b_OK.remove(i)
                    break
            g.new('')
            g.paste(0, 0, 'or')
            g.select(g.getrect())
            b_OK.sort()

        if not i in s_OK:
            s_OK.append(i)
            execfor = 1
            # B0 and nontotalistic rulestrings are mutually exclusive
            try:
                g.setrule(rulestringopt('B' + ruleArr[0] + '/S' + ''.join(s_OK)))
            except:
                s_OK.remove(i)
                execfor = 0
            for j in range(0, s * execfor):
                g.run(1)
                try:
                    dlist = list(chunks(g.getcells(g.getrect()), 2))
                    mcc = min(dlist)
                    dlist = [[x[0] - mcc[0], x[1] - mcc[1]] for x in dlist]
                    if not(clist[j] == dlist):
                        s_OK.remove(i)
                        break
                except:
                    s_OK.remove(i)
                    break
            g.new('')
            g.paste(0, 0, 'or')
            g.select(g.getrect())
            s_OK.sort()

        if i in b_need:
            b_need.remove(i)
            g.setrule(rulestringopt('B' + ''.join(b_need) + '/S' + ruleArr[1]))
            for j in range(0, s):
                g.run(1)
                try:
                    dlist = list(chunks(g.getcells(g.getrect()), 2))
                    mcc = min(dlist)
                    dlist = [[x[0] - mcc[0], x[1] - mcc[1]] for x in dlist]
                    if not(clist[j] == dlist):
                        b_need.append(i)
                        break
                except:
                    b_need.append(i)
                    break
            g.new('')
            g.paste(0, 0, 'or')
            g.select(g.getrect())
            b_need.sort()

        if i in s_need:
            s_need.remove(i)
            g.setrule(rulestringopt('B' + ruleArr[0] + '/S' + ''.join(s_need)))
            for j in range(0, s):
                g.run(1)
                try:
                    dlist = list(chunks(g.getcells(g.getrect()), 2))
                    mcc = min(dlist)
                    dlist = [[x[0] - mcc[0], x[1] - mcc[1]] for x in dlist]
                    if not(clist[j] == dlist):
                        s_need.append(i)
                        break
                except:
                    s_need.append(i)
                    break
            g.new('')
            g.paste(0, 0, 'or')
            g.select(g.getrect())
            s_need.sort()

    g.setrule(oldrule)
    ruleres = 'B' + ''.join(sorted(b_need)) + '/S' + ''.join(sorted(s_need)) + \
        ' - B' + ''.join(sorted(b_OK)) + '/S' + ''.join(sorted(s_OK))
    g.show(rulestringopt(ruleres))

    ruleB="B"+''.join(sorted(b_need))
    ruleS="S"+''.join(sorted(s_need))
    isotropiclistB = sorted(b_OK)
    isotropiclistS = sorted(s_OK)

    # Remove B0 and B1 conditions
    for wrongvalues in ["0","1c","1e"]:
        if wrongvalues in isotropiclistB:
            isotropiclistB.remove(wrongvalues)

    # Generate a random isotropic rule which is likely to allow spaceships to exist
    def randIsoRule():
        # Birth conditions
        prob = random.random()*0.55+0.05 # Random number between 0.05 and 0.6
        rulestr = ruleB
        for elem in isotropiclistB:
            if random.random()<prob: rulestr+=elem
        # Ensure rule has a chance of supporting ships
        if len(rulestr) == 1:
            # Add a random rule element
            rulestr+=random.choice(isotropiclistB)
        if not rulestr[1] in '23':
            # Add two random 2x or 3x rule elements
            rulestr+=random.choice(isotropiclistB[:16])
            rulestr+=random.choice(isotropiclistB[:16])
       
        # Survival conditions (force S0 for dot survival)
        prob = random.random()*0.55+0.05 # Random number between 0.05 and 0.6
        rulestr+='/'+ruleS
        for elem in isotropiclistS:
            if random.random()<prob: rulestr+=elem
        return(rulestr)
       
    # ----------------------------------------------------------

    # Return the minimum and maximum of the absolute value of a list of numbers
    def minmaxofabs(v):
        v = map(abs, v)
        return min(v), max(v)

    # Test a pattern in the given rule to determine if it reappears
    def testRule(rulestr):
        r = g.getrect()
        if r:
            g.select(r)
            g.clear(0)
        g.putcells(testPatt)
        g.setrule(rulestr)
        for ii in xrange(maxGen):
            g.run(1)
            pop = int(g.getpop())
            if (pop < minPop or pop > maxPop):
                break
            elif (pop == testPop):
                # Test for periodicity
                r = g.getrect()
                if testPatt == g.transform(g.getcells(r),-r[0],-r[1]):
                    period = ii+1
                    if (r[0] == 0 and r[1] == 0 ):
                        # Oscillator (reject if low period or bOsc is False)
                        if bOsc and period >= minP:
                            return (period, )
                    elif ( period >= minShipP ):
                        # Spaceship (reject if low period)
                        return (r[0], r[1], period)
                    break # Pattern is a low period oscillator or spaceship
        return ()
       
    # Set up the search with the current pattern
    testRect = g.getrect()
    testPop = int(g.getpop())
    testPatt = g.transform(g.getcells(testRect),-testRect[0],-testRect[1])

    if bOsc: minPop = 2 # Patterns with 0, or 1 cells can not be oscillators
    else: minPop = 3 # Patterns with 0, 1, or 2 cells can not be ships

    g.new('spRulesrc')

    for ii in itertools.count(0,1):
        if bOsc==False:
            while 1:
                j=randIsoRule()
                if "2a" in j: break
                if "2c" in j: break
                if "3i" in j: break
        else:
            j=randIsoRule()
        result = testRule(j)
        if result:
            # Interesting pattern found
            break
        if (ii % 1000 == 0):
            g.select([])
            g.show('%d candidate rules tested for interesting patterns' % (ii))
            g.update()
            g.new("")
        if ii > maxiteration:
            return
           
    g.new('Search result')
    if result:
        g.putcells(testPatt)
        if (len(result) == 1):
            # Pattern is an oscillator
            description = 'Found oscillator with period = %d' % result
        elif (len(result) == 3):
            dx, dy, period = result
            dy, dx = minmaxofabs( (dx, dy) )
            if dy == 0:
                description = 'Found orthogonal spaceship with speed = %dc/%d' % (dx, period)
            elif dy == dx:
                description = 'Found diagonal spaceship with speed = %dc/%d' % (dx, period)
            else:
                description = 'Found knightship with speed = (%d, %d)c/%d' % (dx, dy, period)
        else:
            g.exit('Unrecognised pattern')
        g.exit(description)
    else:
        g.show('No results found')

M=g.getstring('How many generations to use as base:', '', 'Rules calculator')
D=g.getstring('Set depth:','100000')
D=int(D)
cell_list=g.getcells(g.getrect())
while 1:
    Rulesrc(M,D)
    Rulesrc(str(max(1,int(M)-1)),2*D)
    Rulesrc(M,D)
    Rulesrc(str(max(1,int(M)-2)),4*D)
    Rulesrc(M,D)
    M=str(int(M)-1)


After a given depth at a number of generations, it attempts widening the search, then narrowing it*(please read the asterisk later) in case there's a good lead, and otherwise widening it further. This is as bad an implementation of the original idea as I can imagine being possible. I know. It's just to have a preliminary proof of how effective it is nonetheless!

* The way it narrows it back would have been nice if and only if the new attempted nth generation was interesting. This script just does it with whichever rule it got to at generation D, so it has a 1/D chance of having chosen the best one, which really is awful. Optimising this will make results faster by about 2 orders of magnitude, I should imagine.

Proof of Concept and Further Goals
The easiest proof that my idea has any validity whatsoever would be by trying to find copperhead in the discovered phase, with 10 generations in rule B34k/S23. Even a depth 100 immediately gives an answer very quickly (the recommended depth should be higher, in general).
With the original Rulesrc, trying with 8 generations would have yielded nothing and trying with 4 generations would have taken somewhat longer. Bear in mind this was a single-point defect in the rule, so the change won't be as noticeable.
In any case, trying 1D spaceships with a very optimistic number of generations (11-13) and depth of 10000 gave very quick results with minor changes in the evolution.

The main objectives now are the following:
1) to change the number of generations kept in a more justified way than the current absurdity
2) to narrow down in a more justified way, ideally with a scoring system for the failed spaceships
3) to try specific neighbourhood changes based on a heuristic estimate (i.e. to avoid leaving [o.o] dots behind in a B.../S0... search, try a B2i transition)

Please, feel free to play around with the script and to comment on how you find it. It's still terribly suboptimal, but we'll work on it.
User avatar
Rhombic
 
Posts: 790
Joined: June 1st, 2013, 5:41 pm

Re: Rulesrc: Finding rules for a spaceship

Postby drc » September 15th, 2017, 7:09 pm

Rhombic wrote:Towards a Progressive Rulesrc
A self-correcting Rulesrc would be interesting enough to attempt to find cell configurations, but one of the initial steps is to allow variation in the number of identical generations. Note that this yields similar and not necessarily identical ships, but for many purposes it's good enough. The idealised script should be able to identify good leads, allowing much quicker finds of interesting spaceships from decent inputs.

I like this! I found this cool 9c/849 orthogonal with it (in a non-explosive rule), so it's certainly not useless:
x = 12, y = 3, rule = B2ik3-qy4eknrt5aek6in/S2-a3ijqy4aqt5aen7e8
3o7bo$obo6b3o$3o7bo!
This post was brought to you by the letter D, for dishes that Andrew J. Wade won't do. (Also Daniel, which happens to be me.)
Current rule interest: B2ce3-ir4a5y/S2-c3-y
User avatar
drc
 
Posts: 1665
Joined: December 3rd, 2015, 4:11 pm
Location: creating useless things in OCA

Re: Rulesrc: Finding rules for a spaceship

Postby Saka » September 16th, 2017, 1:12 am

I'm not exactly understanding the progressive rulesrc. What does it mean by progressive? What is "base generation"? I don't get it, sorry.
Everyone, please stop posting B/S about CA
x = 17, y = 10, rule = B3/S23
b2ob2obo5b2o$11b4obo$2bob3o2bo2b3o$bo3b2o4b2o$o2bo2bob2o3b4o$bob2obo5b
o2b2o$2b2o4bobo2b3o$bo3b5ob2obobo$2bo5bob2o$4bob2o2bobobo!

(Check gen 2)
User avatar
Saka
 
Posts: 2267
Joined: June 19th, 2015, 8:50 pm
Location: In the kingdom of Sultan Hamengkubuwono X

Re: Rulesrc: Finding rules for a spaceship

Postby Rhombic » September 16th, 2017, 8:02 am

Saka wrote:I'm not exactly understanding the progressive rulesrc. What does it mean by progressive? What is "base generation"? I don't get it, sorry.

Base generation is the maximum initial generations you want to keep identical, for a start.

Since the last generations might have been wrong due to a slight mistake when defining them (think messing up a copperhead in B34k/S23, which would be a shame), the only answer so far was widening the search by starting with fewer generation constraints. However, in the event that there was in fact a ship with the very tight constraints, it would be a shame to make the search last for so long.

Do realise that Rulesrc is much more likely to find spaceships tht works in many many rules instead of endemic ones, because it's down to the luck of choosing the only rule the spaceship works in. Narrowing down the search is crucial. Ideally, this could be done in a more intelligent way (using a scoring function), but so far it just does this:
while 1:
    Rulesrc(M,D)
    Rulesrc(str(max(1,int(M)-1)),2*D)
    Rulesrc(M,D)
    Rulesrc(str(max(1,int(M)-2)),4*D)
    Rulesrc(M,D)
    M=str(int(M)-1)

Where Rulesrc(A,B) is performing a Rulesrc with A generations for B rules.

Scoring Functions
For now, line 4 of that excerpt has a major problem. The idea is to narrow it down after having widened it. However, one can clearly see that this extra generation will be a random pick from all the D ones explored. In some cases, this will imply wrongly narrowing down the search to a rule that might be explosive, which is a crazy waste of time and effort.
The quality of a "partial rule find" spaceship should be assessed, and there is a great benefit from doing so: when the search is narrowed, it is narrowed exclusively to high-potential rules. This is what we want, because Rulesrc is otherwise a brute-force search if you allow it to make a broad search regardless.
Heuristic neighbourhood correlation could be very useful!! If the last forced generation has an interacting dot spark, if allowed, maybe S0 is a good approach. If the spaceship is at risk of becoming D4 symmetric if a section becomes a spark, then we should limit the search space to rules where that part is NOT a spark.

Other Additions to Include
If the number of rules <= search depth, then, instead of generating random rules, cycle through each of the possible rules and return after going through all of them.
That way, if a pattern works in B36a/S23-k - B36an8/S234ce8, it's much shorter to go through 64 rules instead of repeating random rules 2000 times.
User avatar
Rhombic
 
Posts: 790
Joined: June 1st, 2013, 5:41 pm

Re: Rulesrc: Finding rules for a spaceship

Postby muzik » September 24th, 2017, 1:25 pm

Could this script be extended to non-totalistic Generations?
2c/n spaceships project

Current priorities: see here
muzik
 
Posts: 2612
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Rulesrc: Finding rules for a spaceship

Postby Saka » September 27th, 2017, 8:52 am

what about a faster version of the original searchRules but with rule-that-supports-spaceships logic and progrulesrc logic?
Everyone, please stop posting B/S about CA
x = 17, y = 10, rule = B3/S23
b2ob2obo5b2o$11b4obo$2bob3o2bo2b3o$bo3b2o4b2o$o2bo2bob2o3b4o$bob2obo5b
o2b2o$2b2o4bobo2b3o$bo3b5ob2obobo$2bo5bob2o$4bob2o2bobobo!

(Check gen 2)
User avatar
Saka
 
Posts: 2267
Joined: June 19th, 2015, 8:50 pm
Location: In the kingdom of Sultan Hamengkubuwono X

Re: Rulesrc: Finding rules for a spaceship

Postby muzik » September 27th, 2017, 4:08 pm

Is "amount of generations to remain unchanged" just a confusingly verbose version of "minimum period"?
2c/n spaceships project

Current priorities: see here
muzik
 
Posts: 2612
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Rulesrc: Finding rules for a spaceship

Postby Rhombic » September 28th, 2017, 10:04 am

muzik wrote:Is "amount of generations to remain unchanged" just a confusingly verbose version of "minimum period"?

Yes and no... I mean, that's a clear implication of the fact that, otherwise, there would have been an impossible subperiod repeat for a higher period spaceship. However, I wanted to state the fact that it's trying to find a spaceship that preserves those generations, more than the fact that it will obviously need a higher period. I hope that makes sense. Any new wordings appreciated.

Does someone know how to make a decent scoring function? i.e. one that could detect non-explosive rules (so the pattern doesn't grow wildly) and that could potentially involve a translation of a potential predecessor (so that the pattern has reached a possible parent/have a few common cells).
User avatar
Rhombic
 
Posts: 790
Joined: June 1st, 2013, 5:41 pm

Re: Rulesrc: Finding rules for a spaceship

Postby Rhombic » October 5th, 2017, 11:34 am

Crude script to find patterns that evolve to a high population in a rule, very poor logic.
It addresses a couple of issues though:
- If the population tends to be very high and very similar regardless of the original starting pattern, you are facing an explosive rule.
- If the improvements on the best result tail off very quickly and at a low population, the rule is probably too static.
import golly as g

class maxpop:
    def __init__(self):
        self.pop=0
        self.patt=[]
    def compare(self,other):
        g.select(g.getrect())
        g.clear(0)
        g.putcells(other)
        g.run(3000)
        comp=int(g.getpop())
        g.select(g.getrect())
        g.clear(0)
        g.putcells(self.patt)
        g.run(3000)
        newpop=int(g.getpop())
        if comp>newpop:
            return 1
        else: return 0

best=maxpop()
candidate=maxpop()
while 1:
    g.select([0,0,7,7])
    g.randfill(50)
    candidate.patt=g.getcells(g.getrect())
    g.run(2000)
    if int(g.getpop())>best.pop:
        candidate.pop=int(g.getpop())
        if best.compare(candidate.patt)==1:
            best.pop=candidate.pop
            best.patt=candidate.patt
    g.show("New highest population is %d. Press any key to show current best." %best.pop)
    g.select(g.getrect())
    try:
        g.clear(0)
    except: pass
    event = g.getevent()
    if event.startswith("key"):
        g.new('Result')
        g.putcells(best.patt)
        g.exit()

This could be used, once improved upon, to classify whether a rule where a spaceship has been found is good enough or not. If not, a search of rules where the spaceship works could attempt to find a less explosive one, starting from the fewest B/S conditions. Let me know what you think, its potential uses apart from progRulesrc merging, etc.

EDIT: g.setclipstr() removed
Last edited by Rhombic on October 5th, 2017, 4:48 pm, edited 1 time in total.
User avatar
Rhombic
 
Posts: 790
Joined: June 1st, 2013, 5:41 pm

Re: Rulesrc: Finding rules for a spaceship

Postby drc » October 5th, 2017, 3:37 pm

Rhombic wrote:Crude script to find patterns that evolve to a high population in a rule, very poor logic.

It copies weird stuff to my clipboard:
[0, 0, 1, 0, 2, 0, 1, 1, 2, 1, 3, 1, 4, 1, 6, 1, 0, 2, 1, 2, 4, 2, 0, 3, 2, 3, 3, 3, 4, 3, 6, 3, 1, 4, 3, 4, 1, 5, 4, 5, 6, 5, 0, 6, 1, 6, 3, 6, 5, 6]
This post was brought to you by the letter D, for dishes that Andrew J. Wade won't do. (Also Daniel, which happens to be me.)
Current rule interest: B2ce3-ir4a5y/S2-c3-y
User avatar
drc
 
Posts: 1665
Joined: December 3rd, 2015, 4:11 pm
Location: creating useless things in OCA

Re: Rulesrc: Finding rules for a spaceship

Postby Rhombic » October 8th, 2017, 6:28 pm

Allowing oscillator searches for Rulesrc gives more impressive results than I had expected initially... higher order symmetries tend to be prolific.
Proof by searching with 9 generations kept, a novel p35:
x = 8, y = 8, rule = B3-cky4eiq5kny6aci/S2-n3-eij4inr5-cijk6c78
4o2b2o$4o2b2o$6b2o$6b2o$2o$2o$2o2b4o$2o2b4o!

EDIT: an unbelievable xp110
x = 17, y = 5, rule = B34ijqrz5ckry6c7c8/S23-cky4y5c6n
9bo$2o7b2o4b2o$2o8b2o3b2o$9b2o$9bo!
Last edited by Rhombic on October 8th, 2017, 6:43 pm, edited 1 time in total.
User avatar
Rhombic
 
Posts: 790
Joined: June 1st, 2013, 5:41 pm

Re: Rulesrc: Finding rules for a spaceship

Postby muzik » October 8th, 2017, 6:35 pm

Have you considered adapting this to allow non-isotropic rules? There's some freaky slopes out there just waiting to be tapped into
2c/n spaceships project

Current priorities: see here
muzik
 
Posts: 2612
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Rulesrc: Finding rules for a spaceship

Postby toroidalet » October 8th, 2017, 6:41 pm

I don't want to sound annoying by suggesting a lot of things, but (and this is probably extremely trivial) could Rulesrc be modified to just look for repetitions of the starting pattern (for finding guns, puffers and replicators)?
I have the best signature ever.
User avatar
toroidalet
 
Posts: 772
Joined: August 7th, 2016, 1:48 pm
Location: Somewhere on a planet called "Earth"

Re: Rulesrc: Finding rules for a spaceship

Postby drc » October 8th, 2017, 6:54 pm

toroidalet wrote:I don't want to sound annoying by suggesting a lot of things, but (and this is probably extremely trivial) could Rulesrc be modified to just look for repetitions of the starting pattern (for finding guns, puffers and replicators)?

+1

Added bonus if you get to choose which one(s)
This post was brought to you by the letter D, for dishes that Andrew J. Wade won't do. (Also Daniel, which happens to be me.)
Current rule interest: B2ce3-ir4a5y/S2-c3-y
User avatar
drc
 
Posts: 1665
Joined: December 3rd, 2015, 4:11 pm
Location: creating useless things in OCA

Re: Rulesrc: Finding rules for a spaceship

Postby Rhombic » October 13th, 2017, 9:12 am

New script that lists results for particularly productive pattern/condition pairs.
Lists the results in a text file with rule, displacement, period (for a given initial pattern that is also written to the text file).
This script does NOT exit once a result is found, and restarts itself to keep searching, so many 3 cell ships can be found like this without the need to copy each one individually.
The spaceships listed are always in minimal rule form - see the defined function setminrule(arguments)

iterRulesrc
# iterRulesrc.py
#
# This version of Rulesrc (available: ConwayLife.com) aims to improve search efficiency for productive patterns+conditions.
# The results get listed to iterRulesrc_results.txt and the search is cancelled by pressing any key.

# Arie Paap, Aug 2017
# Nathaniel Johnston (nathaniel@nathanieljohnston.com), June 2009.
# Updated by: Peter, NASZVADI (), June 2017.
# Grafted by Rhombic, Aug 2017.

import golly as g
import itertools
from glife import validint
from string import replace
import random

GENERATION_STRING=g.getstring('To stop this script, press any key at any point.\nHow many generations to remain unchanged:', '', 'Rules calculator')

def setminrule(RULE, DX, DY, PERIOD):
    # Rule computation script for use with Golly.
    # Author: Nathaniel Johnston (nathaniel@nathanieljohnston.com), June 2009.
    # Updated by: Peter, NASZVADI (), June 2017.

    # Gives the maximal family of rules that a still life, oscillator, or spaceship
    # works under. Must be called while the rule is set of one such family
    # For example, to find out what rules a glider works in, first set the rule
    # to Life or HighLife, not Seeds.
    # Handles nontotalistic rules, too, so it needs Golly 2.8 or newer.

    import golly as g

    g.setrule(RULE)

    Hensel = [
        ['0'],
        ['1c', '1e'],
        ['2a', '2c', '2e', '2i', '2k', '2n'],
        ['3a', '3c', '3e', '3i', '3j', '3k', '3n', '3q', '3r', '3y'],
        ['4a', '4c', '4e', '4i', '4j', '4k', '4n', '4q', '4r', '4t', '4w', '4y', '4z'],
        ['5a', '5c', '5e', '5i', '5j', '5k', '5n', '5q', '5r', '5y'],
        ['6a', '6c', '6e', '6i', '6k', '6n'],
        ['7c', '7e'],
        ['8']
    ]

    # Python versions < 2.4 don't have "sorted" built-in
    try:
        sorted
    except NameError:
        def sorted(inlist):
            outlist = list(inlist)
            outlist.sort()
            return outlist

    # --------------------------------------------------------------------

    def chunks(l, n):
        for i in range(0, len(l), n):
            yield l[i:i+n]

    # --------------------------------------------------------------------

    def rulestringopt(a):
        result = ''
        context = ''
        lastnum = ''
        lastcontext = ''
        for i in a:
            if i in 'BS':
                context = i
                result += i
            elif i in '012345678':
                if (i == lastnum) and (lastcontext == context):
                    pass
                else:
                    lastcontext = context
                    lastnum = i
                    result += i
            else:
                result += i
        result = replace(result, '4aceijknqrtwyz', '4')
        result = replace(result, '3aceijknqry', '3')
        result = replace(result, '5aceijknqry', '5')
        result = replace(result, '2aceikn', '2')
        result = replace(result, '6aceikn', '6')
        result = replace(result, '1ce', '1')
        result = replace(result, '7ce', '7')
        return result

    clist = []
    rule = g.getrule().split(':')[0]

    fuzzer = rule + '9'
    oldrule = rule
    rule = ''
    context = ''
    deletefrom = []
    for i in fuzzer:
        if i == '-':
            deletefrom = [x[1] for x in Hensel[int(context)]]
        elif i in '0123456789/S':
            if deletefrom:
                rule += ''.join(deletefrom)
                deletefrom = []
            context = i
        if len(deletefrom) == 0:
            rule += i
        elif i in deletefrom:
            deletefrom.remove(i)
    rule = rule.strip('9')

    if not (rule[0] == 'B' and '/S' in rule):
        g.exit('Please set Golly to a Life-like rule.')

    if g.empty():
        g.exit('The pattern is empty.')

    s = PERIOD
    numsteps = PERIOD
    if numsteps < 1:
        g.exit('Period must be at least 1.')

    g.select(g.getrect())
    g.copy()
    s = int(s)

    for i in range(0,s):
        g.run(1)
        clist.append(list(chunks(g.getcells(g.getrect()), 2)))
        mcc = min(clist[i])
        clist[i] = [[x[0] - mcc[0], x[1] - mcc[1]] for x in clist[i]]

    g.show('Processing...')

    ruleArr = rule.split('/')
    ruleArr[0] = ruleArr[0].lstrip('B')
    ruleArr[1] = ruleArr[1].lstrip('S')

    b_need = []
    b_OK = []
    s_need = []
    s_OK = []

    context = ''
    fuzzed = ruleArr[0] + '9'
    for i in fuzzed:
        if i in '0123456789':
            if len(context) == 1:
                b_need += Hensel[int(context)]
                b_OK += Hensel[int(context)]
            context = i
        elif context != '':
            b_need.append(context[0] + i)
            b_OK.append(context[0] + i)
            context += context[0]
    context = ''
    fuzzed = ruleArr[1] + '9'
    for i in fuzzed:
        if i in '0123456789':
            if len(context) == 1:
                s_need += Hensel[int(context)]
                s_OK += Hensel[int(context)]
            context = i
        elif context != '':
            s_need.append(context[0] + i)
            s_OK.append(context[0] + i)
            context += context[0]

    for i in [iter2 for iter1 in Hensel for iter2 in iter1]:
        if not i in b_OK:
            b_OK.append(i)
            execfor = 1
            # B0 and nontotalistic rulestrings are mutually exclusive
            try:
                g.setrule(rulestringopt('B' + ''.join(b_OK) + '/S' + ruleArr[1]))
            except:
                b_OK.remove(i)
                execfor = 0
            for j in range(0, s * execfor):
                g.run(1)
                try:
                    dlist = list(chunks(g.getcells(g.getrect()), 2))
                    mcc = min(dlist)
                    dlist = [[x[0] - mcc[0], x[1] - mcc[1]] for x in dlist]
                    if not(clist[j] == dlist):
                        b_OK.remove(i)
                        break
                except:
                    b_OK.remove(i)
                    break
            g.new('')
            g.paste(0, 0, 'or')
            g.select(g.getrect())
            b_OK.sort()

        if not i in s_OK:
            s_OK.append(i)
            execfor = 1
            # B0 and nontotalistic rulestrings are mutually exclusive
            try:
                g.setrule(rulestringopt('B' + ruleArr[0] + '/S' + ''.join(s_OK)))
            except:
                s_OK.remove(i)
                execfor = 0
            for j in range(0, s * execfor):
                g.run(1)
                try:
                    dlist = list(chunks(g.getcells(g.getrect()), 2))
                    mcc = min(dlist)
                    dlist = [[x[0] - mcc[0], x[1] - mcc[1]] for x in dlist]
                    if not(clist[j] == dlist):
                        s_OK.remove(i)
                        break
                except:
                    s_OK.remove(i)
                    break
            g.new('')
            g.paste(0, 0, 'or')
            g.select(g.getrect())
            s_OK.sort()

        if i in b_need:
            b_need.remove(i)
            g.setrule(rulestringopt('B' + ''.join(b_need) + '/S' + ruleArr[1]))
            for j in range(0, s):
                g.run(1)
                try:
                    dlist = list(chunks(g.getcells(g.getrect()), 2))
                    mcc = min(dlist)
                    dlist = [[x[0] - mcc[0], x[1] - mcc[1]] for x in dlist]
                    if not(clist[j] == dlist):
                        b_need.append(i)
                        break
                except:
                    b_need.append(i)
                    break
            g.new('')
            g.paste(0, 0, 'or')
            g.select(g.getrect())
            b_need.sort()

        if i in s_need:
            s_need.remove(i)
            g.setrule(rulestringopt('B' + ruleArr[0] + '/S' + ''.join(s_need)))
            for j in range(0, s):
                g.run(1)
                try:
                    dlist = list(chunks(g.getcells(g.getrect()), 2))
                    mcc = min(dlist)
                    dlist = [[x[0] - mcc[0], x[1] - mcc[1]] for x in dlist]
                    if not(clist[j] == dlist):
                        s_need.append(i)
                        break
                except:
                    s_need.append(i)
                    break
            g.new('')
            g.paste(0, 0, 'or')
            g.select(g.getrect())
            s_need.sort()

    g.setrule(oldrule)
    ruleres = 'B' + ''.join(sorted(b_need)) + '/S' + ''.join(sorted(s_need))
    ruleres = rulestringopt(ruleres)
    g.setrule(ruleres)
    RESULT = [ruleres, DX, DY, PERIOD]
    return RESULT


def Rulesrc():
    # Search parameters

    # Stop if pattern is a ship with this minimum period
    minShipP = 1
    # Stop if pattern is an oscillator with this minimum period
    minP = 3
    # Maximum period to test the pattern for
    maxGen = 1000
    # Maximum population in any phase
    maxPop = 300
    # Allow search for oscillators
    bOsc = False


    import golly as g
    from glife import validint
    from string import replace

    Hensel = [
        ['0'],
        ['1c', '1e'],
        ['2a', '2c', '2e', '2i', '2k', '2n'],
        ['3a', '3c', '3e', '3i', '3j', '3k', '3n', '3q', '3r', '3y'],
        ['4a', '4c', '4e', '4i', '4j', '4k', '4n', '4q', '4r', '4t', '4w', '4y', '4z'],
        ['5a', '5c', '5e', '5i', '5j', '5k', '5n', '5q', '5r', '5y'],
        ['6a', '6c', '6e', '6i', '6k', '6n'],
        ['7c', '7e'],
        ['8']
    ]

    # Python versions < 2.4 don't have "sorted" built-in
    try:
        sorted
    except NameError:
        def sorted(inlist):
            outlist = list(inlist)
            outlist.sort()
            return outlist

    # --------------------------------------------------------------------

    def chunks(l, n):
        for i in range(0, len(l), n):
            yield l[i:i+n]

    # --------------------------------------------------------------------

    def rulestringopt(a):
        result = ''
        context = ''
        lastnum = ''
        lastcontext = ''
        for i in a:
            if i in 'BS':
                context = i
                result += i
            elif i in '012345678':
                if (i == lastnum) and (lastcontext == context):
                    pass
                else:
                    lastcontext = context
                    lastnum = i
                    result += i
            else:
                result += i
        result = replace(result, '4aceijknqrtwyz', '4')
        result = replace(result, '3aceijknqry', '3')
        result = replace(result, '5aceijknqry', '5')
        result = replace(result, '2aceikn', '2')
        result = replace(result, '6aceikn', '6')
        result = replace(result, '1ce', '1')
        result = replace(result, '7ce', '7')
        return result

    clist = []
    rule = g.getrule().split(':')[0]

    fuzzer = rule + '9'
    oldrule = rule
    rule = ''
    context = ''
    deletefrom = []
    for i in fuzzer:
        if i == '-':
            deletefrom = [x[1] for x in Hensel[int(context)]]
        elif i in '0123456789/S':
            if deletefrom:
                rule += ''.join(deletefrom)
                deletefrom = []
            context = i
        if len(deletefrom) == 0:
            rule += i
        elif i in deletefrom:
            deletefrom.remove(i)
    rule = rule.strip('9')

    if not (rule[0] == 'B' and '/S' in rule):
        g.exit('Please set Golly to a Life-like rule.')

    if g.empty():
        g.exit('The pattern is empty.')

    s = GENERATION_STRING
    if not validint(s):
        g.exit('Bad number: %s' % s)

    numsteps = int(s)
    if numsteps < 1:
        g.exit('Period must be at least 1.')

    g.select(g.getrect())
    g.copy()
    s = int(s)

    for i in range(0,s):
        g.run(1)
        clist.append(list(chunks(g.getcells(g.getrect()), 2)))
        mcc = min(clist[i])
        clist[i] = [[x[0] - mcc[0], x[1] - mcc[1]] for x in clist[i]]

    g.show('Processing...')

    ruleArr = rule.split('/')
    ruleArr[0] = ruleArr[0].lstrip('B')
    ruleArr[1] = ruleArr[1].lstrip('S')

    b_need = []
    b_OK = []
    s_need = []
    s_OK = []

    context = ''
    fuzzed = ruleArr[0] + '9'
    for i in fuzzed:
        if i in '0123456789':
            if len(context) == 1:
                b_need += Hensel[int(context)]
                b_OK += Hensel[int(context)]
            context = i
        elif context != '':
            b_need.append(context[0] + i)
            b_OK.append(context[0] + i)
            context += context[0]
    context = ''
    fuzzed = ruleArr[1] + '9'
    for i in fuzzed:
        if i in '0123456789':
            if len(context) == 1:
                s_need += Hensel[int(context)]
                s_OK += Hensel[int(context)]
            context = i
        elif context != '':
            s_need.append(context[0] + i)
            s_OK.append(context[0] + i)
            context += context[0]

    for i in [iter2 for iter1 in Hensel for iter2 in iter1]:
        if not i in b_OK:
            b_OK.append(i)
            execfor = 1
            # B0 and nontotalistic rulestrings are mutually exclusive
            try:
                g.setrule(rulestringopt('B' + ''.join(b_OK) + '/S' + ruleArr[1]))
            except:
                b_OK.remove(i)
                execfor = 0
            for j in range(0, s * execfor):
                g.run(1)
                try:
                    dlist = list(chunks(g.getcells(g.getrect()), 2))
                    mcc = min(dlist)
                    dlist = [[x[0] - mcc[0], x[1] - mcc[1]] for x in dlist]
                    if not(clist[j] == dlist):
                        b_OK.remove(i)
                        break
                except:
                    b_OK.remove(i)
                    break
            g.new('')
            g.paste(0, 0, 'or')
            g.select(g.getrect())
            b_OK.sort()

        if not i in s_OK:
            s_OK.append(i)
            execfor = 1
            # B0 and nontotalistic rulestrings are mutually exclusive
            try:
                g.setrule(rulestringopt('B' + ruleArr[0] + '/S' + ''.join(s_OK)))
            except:
                s_OK.remove(i)
                execfor = 0
            for j in range(0, s * execfor):
                g.run(1)
                try:
                    dlist = list(chunks(g.getcells(g.getrect()), 2))
                    mcc = min(dlist)
                    dlist = [[x[0] - mcc[0], x[1] - mcc[1]] for x in dlist]
                    if not(clist[j] == dlist):
                        s_OK.remove(i)
                        break
                except:
                    s_OK.remove(i)
                    break
            g.new('')
            g.paste(0, 0, 'or')
            g.select(g.getrect())
            s_OK.sort()

        if i in b_need:
            b_need.remove(i)
            g.setrule(rulestringopt('B' + ''.join(b_need) + '/S' + ruleArr[1]))
            for j in range(0, s):
                g.run(1)
                try:
                    dlist = list(chunks(g.getcells(g.getrect()), 2))
                    mcc = min(dlist)
                    dlist = [[x[0] - mcc[0], x[1] - mcc[1]] for x in dlist]
                    if not(clist[j] == dlist):
                        b_need.append(i)
                        break
                except:
                    b_need.append(i)
                    break
            g.new('')
            g.paste(0, 0, 'or')
            g.select(g.getrect())
            b_need.sort()

        if i in s_need:
            s_need.remove(i)
            g.setrule(rulestringopt('B' + ruleArr[0] + '/S' + ''.join(s_need)))
            for j in range(0, s):
                g.run(1)
                try:
                    dlist = list(chunks(g.getcells(g.getrect()), 2))
                    mcc = min(dlist)
                    dlist = [[x[0] - mcc[0], x[1] - mcc[1]] for x in dlist]
                    if not(clist[j] == dlist):
                        s_need.append(i)
                        break
                except:
                    s_need.append(i)
                    break
            g.new('')
            g.paste(0, 0, 'or')
            g.select(g.getrect())
            s_need.sort()

    g.setrule(oldrule)
    ruleres = 'B' + ''.join(sorted(b_need)) + '/S' + ''.join(sorted(s_need)) + \
        ' - B' + ''.join(sorted(b_OK)) + '/S' + ''.join(sorted(s_OK))
    g.show(rulestringopt(ruleres))

    ruleB="B"+''.join(sorted(b_need))
    ruleS="S"+''.join(sorted(s_need))
    isotropiclistB = sorted(b_OK)
    isotropiclistS = sorted(s_OK)

    # Remove B0 and B1 conditions
    for wrongvalues in ["0","1c","1e"]:
        if wrongvalues in isotropiclistB:
            isotropiclistB.remove(wrongvalues)

    # Generate a random isotropic rule which is likely to allow spaceships to exist
    def randIsoRule():
        # Birth conditions
        prob = random.random()*0.55+0.05 # Random number between 0.05 and 0.6
        rulestr = ruleB
        for elem in isotropiclistB:
            if random.random()<prob: rulestr+=elem
        # Ensure rule has a chance of supporting ships
        if len(rulestr) == 1:
            # Add a random rule element
            rulestr+=random.choice(isotropiclistB)
        if not rulestr[1] in '23':
            # Add two random 2x or 3x rule elements
            rulestr+=random.choice(isotropiclistB[:16])
            rulestr+=random.choice(isotropiclistB[:16])
       
        # Survival conditions (force S0 for dot survival)
        prob = random.random()*0.55+0.05 # Random number between 0.05 and 0.6
        rulestr+='/'+ruleS
        for elem in isotropiclistS:
            if random.random()<prob: rulestr+=elem
        return(rulestr)
       
    # ----------------------------------------------------------

    # Return the minimum and maximum of the absolute value of a list of numbers
    def minmaxofabs(v):
        v = map(abs, v)
        return min(v), max(v)

    # Test a pattern in the given rule to determine if it reappears
    def testRule(rulestr):
        r = g.getrect()
        if r:
            g.select(r)
            g.clear(0)
        g.putcells(testPatt)
        g.setrule(rulestr)
        for ii in xrange(maxGen):
            g.run(1)
            pop = int(g.getpop())
            if (pop < minPop or pop > maxPop):
                break
            elif (pop == testPop):
                # Test for periodicity
                r = g.getrect()
                if testPatt == g.transform(g.getcells(r),-r[0],-r[1]):
                    period = ii+1
                    if (r[0] == 0 and r[1] == 0 ):
                        # Oscillator (reject if low period or bOsc is False)
                        if bOsc and period >= minP:
                            return (period, )
                    elif ( period >= minShipP ):
                        # Spaceship (reject if low period)
                        return (r[0], r[1], period)
                    break # Pattern is a low period oscillator or spaceship
        return ()
       
    # Set up the search with the current pattern
    testRect = g.getrect()
    testPop = int(g.getpop())
    testPatt = g.transform(g.getcells(testRect),-testRect[0],-testRect[1])

    if bOsc: minPop = 2 # Patterns with 0, or 1 cells can not be oscillators
    else: minPop = 3 # Patterns with 0, 1, or 2 cells can not be ships

    g.new('spRulesrc')

    for ii in itertools.count(0,1):
        if bOsc==False:
            while 1:
                j=randIsoRule()
                if "2a" in j: break
                if "2c" in j: break
                if "3i" in j: break
        else:
            j=randIsoRule()
        result = testRule(j)
        if result:
            # Interesting pattern found
            break
        if (ii % 1000 == 0):
            g.select([])
            g.show('%d candidate rules tested for interesting patterns' % (ii))
            g.update()
            g.new("")
           
    g.new('Search result')
    if result:
        g.putcells(testPatt)
        if (len(result) == 1):
            # Pattern is an oscillator
            description = 'Found oscillator with period = %d' % result
        elif (len(result) == 3):
            dx, dy, period = result
            dy, dx = minmaxofabs( (dx, dy) )
            if dy == 0:
                description = 'Found orthogonal spaceship with speed = %dc/%d' % (dx, period)
            elif dy == dx:
                description = 'Found diagonal spaceship with speed = %dc/%d' % (dx, period)
            else:
                description = 'Found knightship with speed = (%d, %d)c/%d' % (dx, dy, period)
        else:
            g.exit('Unrecognised pattern')
        g.show(description)
        Spaceship = setminrule(str(g.getrule()), dx, dy, period)
        return Spaceship
    else:
        g.show('No results found')

textfile=open("iterRulesrc_results.txt","w+")
g.select(g.getrect())
g.copy()
textfile.write("\n"+g.getclipstr()+"\n\n")
ListRules = set()
while 1:
    newrule=Rulesrc()
    event = g.getevent()
    if event.startswith("key"):
        break
    if newrule[0] not in ListRules:
        ListRules.add(newrule[0])
        textfile.write(newrule[0]+"\t("+str(newrule[1])+","+str(newrule[2])+")/\t"+str(newrule[3])+"\n")
textfile.close()
g.exit("We have found %d results, found in your rule folder as iterRulesrc_results.txt. Thank you for your patience." % len(ListRules))



Proof of results, for a fairly narrowed-down search: with 3 transitions for
x = 4, y = 1, rule = B2ce3j/S01e
2obo!
gives this result after a few minutes
x = 4, y = 1, rule = B2ce3j/S01e
2obo!

B2cek3jry4irt5e6c7e/S01e4ct5iy7e   (1,0)/   9
B2cek3ij4i5i/S01e4n   (3,0)/   7
B2cek3jkqry4ijktw5akny6c/S01e2e3jr4iqz5ry6i8   (2,0)/   20
B2cek3j4ik5n6a7e/S01e2n4aejnrt5cij6acik7e8   (2,0)/   11
B2cek3ijqy4iqrwz5ir6c/S01e2ikn4intw5cinqry6ci   (3,0)/   15
B2cek3jr4i5iy/S01e2e3cq4ein7e   (3,0)/   14
B2cekn3ijry4ijnt6c7e/S01e2in3n4in5c6k   (2,0)/   17
B2ce3jnqr4ijr5q7e/S01e2k3eq   (2,0)/   12
B2cek3jnry4inr5e6c8/S01e   (1,0)/   8
B2cek3cjqry4ar5iy6c8/S01e2kn6k   (1,0)/   19
B2cek3jr4i/S01e4n5y7e   (1,0)/   8
B2cek3ijry4ijk5c/S01e2i3q4cin5ij   (3,0)/   9
User avatar
Rhombic
 
Posts: 790
Joined: June 1st, 2013, 5:41 pm

Re: Rulesrc: Finding rules for a spaceship

Postby AforAmpere » October 14th, 2017, 10:24 am

Is there a way to have the script constantly update the text file, or have it tell how many ships have been found while it is running?
Things to work on:
- An Isotropic version of All_Speeds
- Find more ships in B2ek3-ajny4ajqr5a/S02ack3ackny4aq5y
- Find a (3,1)c/5 ship in a Non-totalistic rule (someone please search the rules)
AforAmpere
 
Posts: 289
Joined: July 1st, 2016, 3:58 pm

Re: Rulesrc: Finding rules for a spaceship

Postby wildmyron » October 14th, 2017, 11:38 am

Here's my current version of the search script. It's still far from what I'd like it to be, but I think there's some useful bits that you guys can use. In particular I updated testrule() to include a naive stability test which gives a decent speed improvement when maxGen is set to large values. There's also a small change to giveRLE() for performance reasons and I've simplified randIsoRule() to use a fixed probability. It includes my version of setminisorule which has a lot of redundant code (c.f. the rule range testing code) and also heavily derived from getallisorule.py.

The search script outputs all results to a file, and a second script can be used to filter those results and output a file with a sorted list of (mostly) unique ships. The search script appends to it's output file, but the filter script overwrites its output file.

searchRule-matchPatt.zip
(8.18 KiB) Downloaded 9 times


Edit: From Misc discoveries thread:

Use this script to import ships in the scripts output format into Golly
# display_ship.py
# This script will take a string representing a ship with some additional metadata,
# and display it in the current layer
# It first checks the clipboard for a valid string and then requests input if necessary
# There is minimal error checking
# ship format: ['pop', 'rule', 'dx', 'dy', 'period', 'rle']

import golly as g

def parseshipstr(shipstr):
    if not shipstr[0] in '123456789':
        return
    ship = shipstr.split(', ')
    if not len(ship) == 6:
        return
    return ship

shipstr = g.getclipstr()
ship = parseshipstr(shipstr)
if not ship:
    shipstr = g.getstring('Enter ship string:')
ship = parseshipstr(shipstr)
if not ship:
    g.exit('Invalid ship string: ' + shipstr)
   
rulestr = ship[1].strip()
shiprle = ship[5].strip()

g.new('')
g.setrule(rulestr)
g.putcells(g.parse(shiprle))
wildmyron
 
Posts: 597
Joined: August 9th, 2013, 12:45 am

Re: Rulesrc: Finding rules for a spaceship

Postby wildmyron » October 15th, 2017, 12:56 pm

I just found out that I didn't create the zipfile correctly and several files were missing. Please download again from the post above if you would like to use the filtering script mentioned in the post.
wildmyron
 
Posts: 597
Joined: August 9th, 2013, 12:45 am

Re: Rulesrc: Finding rules for a spaceship

Postby Rhombic » October 16th, 2017, 10:35 am

Expanded version of iterRulesrc to support both oscillator and spaceship searches, here as iterAllRulesrc:
# iterAllRulesrc.py
#
# For both oscillator and spaceship searches, iterRulesrc algorithm.
# This version of Rulesrc (available: ConwayLife.com) aims to improve search efficiency for productive patterns+conditions.
# The results get listed to iterAllRulesrc_results.txt and the search is cancelled by pressing any key.

# Expanded from Rulesrc
# Arie Paap, Aug 2017
# Nathaniel Johnston (nathaniel@nathanieljohnston.com), June 2009.
# Updated by: Peter, NASZVADI (), June 2017.
# Grafted by Rhombic, Aug 2017.

import golly as g
import itertools
from glife import validint
from string import replace
import random

GENERATION_STRING=g.getstring('To stop this script, press any key at any point.\nHow many generations to remain unchanged:', '', 'Rules calculator')

def setminrule(RULE, DX, DY, PERIOD):
    # Rule computation script for use with Golly.
    # Author: Nathaniel Johnston (nathaniel@nathanieljohnston.com), June 2009.
    # Updated by: Peter, NASZVADI (), June 2017.

    # Gives the maximal family of rules that a still life, oscillator, or spaceship
    # works under. Must be called while the rule is set of one such family
    # For example, to find out what rules a glider works in, first set the rule
    # to Life or HighLife, not Seeds.
    # Handles nontotalistic rules, too, so it needs Golly 2.8 or newer.

    import golly as g

    g.setrule(RULE)

    Hensel = [
        ['0'],
        ['1c', '1e'],
        ['2a', '2c', '2e', '2i', '2k', '2n'],
        ['3a', '3c', '3e', '3i', '3j', '3k', '3n', '3q', '3r', '3y'],
        ['4a', '4c', '4e', '4i', '4j', '4k', '4n', '4q', '4r', '4t', '4w', '4y', '4z'],
        ['5a', '5c', '5e', '5i', '5j', '5k', '5n', '5q', '5r', '5y'],
        ['6a', '6c', '6e', '6i', '6k', '6n'],
        ['7c', '7e'],
        ['8']
    ]

    # Python versions < 2.4 don't have "sorted" built-in
    try:
        sorted
    except NameError:
        def sorted(inlist):
            outlist = list(inlist)
            outlist.sort()
            return outlist

    # --------------------------------------------------------------------

    def chunks(l, n):
        for i in range(0, len(l), n):
            yield l[i:i+n]

    # --------------------------------------------------------------------

    def rulestringopt(a):
        result = ''
        context = ''
        lastnum = ''
        lastcontext = ''
        for i in a:
            if i in 'BS':
                context = i
                result += i
            elif i in '012345678':
                if (i == lastnum) and (lastcontext == context):
                    pass
                else:
                    lastcontext = context
                    lastnum = i
                    result += i
            else:
                result += i
        result = replace(result, '4aceijknqrtwyz', '4')
        result = replace(result, '3aceijknqry', '3')
        result = replace(result, '5aceijknqry', '5')
        result = replace(result, '2aceikn', '2')
        result = replace(result, '6aceikn', '6')
        result = replace(result, '1ce', '1')
        result = replace(result, '7ce', '7')
        return result

    clist = []
    rule = g.getrule().split(':')[0]

    fuzzer = rule + '9'
    oldrule = rule
    rule = ''
    context = ''
    deletefrom = []
    for i in fuzzer:
        if i == '-':
            deletefrom = [x[1] for x in Hensel[int(context)]]
        elif i in '0123456789/S':
            if deletefrom:
                rule += ''.join(deletefrom)
                deletefrom = []
            context = i
        if len(deletefrom) == 0:
            rule += i
        elif i in deletefrom:
            deletefrom.remove(i)
    rule = rule.strip('9')

    if not (rule[0] == 'B' and '/S' in rule):
        g.exit('Please set Golly to a Life-like rule.')

    if g.empty():
        g.exit('The pattern is empty.')

    s = PERIOD
    numsteps = PERIOD
    if numsteps < 1:
        g.exit('Period must be at least 1.')

    g.select(g.getrect())
    g.copy()
    s = int(s)

    for i in range(0,s):
        g.run(1)
        clist.append(list(chunks(g.getcells(g.getrect()), 2)))
        mcc = min(clist[i])
        clist[i] = [[x[0] - mcc[0], x[1] - mcc[1]] for x in clist[i]]

    g.show('Processing...')

    ruleArr = rule.split('/')
    ruleArr[0] = ruleArr[0].lstrip('B')
    ruleArr[1] = ruleArr[1].lstrip('S')

    b_need = []
    b_OK = []
    s_need = []
    s_OK = []

    context = ''
    fuzzed = ruleArr[0] + '9'
    for i in fuzzed:
        if i in '0123456789':
            if len(context) == 1:
                b_need += Hensel[int(context)]
                b_OK += Hensel[int(context)]
            context = i
        elif context != '':
            b_need.append(context[0] + i)
            b_OK.append(context[0] + i)
            context += context[0]
    context = ''
    fuzzed = ruleArr[1] + '9'
    for i in fuzzed:
        if i in '0123456789':
            if len(context) == 1:
                s_need += Hensel[int(context)]
                s_OK += Hensel[int(context)]
            context = i
        elif context != '':
            s_need.append(context[0] + i)
            s_OK.append(context[0] + i)
            context += context[0]

    for i in [iter2 for iter1 in Hensel for iter2 in iter1]:
        if not i in b_OK:
            b_OK.append(i)
            execfor = 1
            # B0 and nontotalistic rulestrings are mutually exclusive
            try:
                g.setrule(rulestringopt('B' + ''.join(b_OK) + '/S' + ruleArr[1]))
            except:
                b_OK.remove(i)
                execfor = 0
            for j in range(0, s * execfor):
                g.run(1)
                try:
                    dlist = list(chunks(g.getcells(g.getrect()), 2))
                    mcc = min(dlist)
                    dlist = [[x[0] - mcc[0], x[1] - mcc[1]] for x in dlist]
                    if not(clist[j] == dlist):
                        b_OK.remove(i)
                        break
                except:
                    b_OK.remove(i)
                    break
            g.new('')
            g.paste(0, 0, 'or')
            g.select(g.getrect())
            b_OK.sort()

        if not i in s_OK:
            s_OK.append(i)
            execfor = 1
            # B0 and nontotalistic rulestrings are mutually exclusive
            try:
                g.setrule(rulestringopt('B' + ruleArr[0] + '/S' + ''.join(s_OK)))
            except:
                s_OK.remove(i)
                execfor = 0
            for j in range(0, s * execfor):
                g.run(1)
                try:
                    dlist = list(chunks(g.getcells(g.getrect()), 2))
                    mcc = min(dlist)
                    dlist = [[x[0] - mcc[0], x[1] - mcc[1]] for x in dlist]
                    if not(clist[j] == dlist):
                        s_OK.remove(i)
                        break
                except:
                    s_OK.remove(i)
                    break
            g.new('')
            g.paste(0, 0, 'or')
            g.select(g.getrect())
            s_OK.sort()

        if i in b_need:
            b_need.remove(i)
            g.setrule(rulestringopt('B' + ''.join(b_need) + '/S' + ruleArr[1]))
            for j in range(0, s):
                g.run(1)
                try:
                    dlist = list(chunks(g.getcells(g.getrect()), 2))
                    mcc = min(dlist)
                    dlist = [[x[0] - mcc[0], x[1] - mcc[1]] for x in dlist]
                    if not(clist[j] == dlist):
                        b_need.append(i)
                        break
                except:
                    b_need.append(i)
                    break
            g.new('')
            g.paste(0, 0, 'or')
            g.select(g.getrect())
            b_need.sort()

        if i in s_need:
            s_need.remove(i)
            g.setrule(rulestringopt('B' + ruleArr[0] + '/S' + ''.join(s_need)))
            for j in range(0, s):
                g.run(1)
                try:
                    dlist = list(chunks(g.getcells(g.getrect()), 2))
                    mcc = min(dlist)
                    dlist = [[x[0] - mcc[0], x[1] - mcc[1]] for x in dlist]
                    if not(clist[j] == dlist):
                        s_need.append(i)
                        break
                except:
                    s_need.append(i)
                    break
            g.new('')
            g.paste(0, 0, 'or')
            g.select(g.getrect())
            s_need.sort()

    g.setrule(oldrule)
    ruleres = 'B' + ''.join(sorted(b_need)) + '/S' + ''.join(sorted(s_need))
    ruleres = rulestringopt(ruleres)
    g.setrule(ruleres)
    g.run(0)
    RESULT = [str(g.getrule()), DX, DY, PERIOD]
    return RESULT


def Rulesrc():
    # Search parameters

    # Stop if pattern is a ship with this minimum period
    minShipP = 1
    # Stop if pattern is an oscillator with this minimum period
    minP = 3
    # Maximum period to test the pattern for
    maxGen = 1000
    # Maximum population in any phase
    maxPop = 300
    # Allow search for oscillators
    bOsc = True


    import golly as g
    from glife import validint
    from string import replace

    Hensel = [
        ['0'],
        ['1c', '1e'],
        ['2a', '2c', '2e', '2i', '2k', '2n'],
        ['3a', '3c', '3e', '3i', '3j', '3k', '3n', '3q', '3r', '3y'],
        ['4a', '4c', '4e', '4i', '4j', '4k', '4n', '4q', '4r', '4t', '4w', '4y', '4z'],
        ['5a', '5c', '5e', '5i', '5j', '5k', '5n', '5q', '5r', '5y'],
        ['6a', '6c', '6e', '6i', '6k', '6n'],
        ['7c', '7e'],
        ['8']
    ]

    # Python versions < 2.4 don't have "sorted" built-in
    try:
        sorted
    except NameError:
        def sorted(inlist):
            outlist = list(inlist)
            outlist.sort()
            return outlist

    # --------------------------------------------------------------------

    def chunks(l, n):
        for i in range(0, len(l), n):
            yield l[i:i+n]

    # --------------------------------------------------------------------

    def rulestringopt(a):
        result = ''
        context = ''
        lastnum = ''
        lastcontext = ''
        for i in a:
            if i in 'BS':
                context = i
                result += i
            elif i in '012345678':
                if (i == lastnum) and (lastcontext == context):
                    pass
                else:
                    lastcontext = context
                    lastnum = i
                    result += i
            else:
                result += i
        result = replace(result, '4aceijknqrtwyz', '4')
        result = replace(result, '3aceijknqry', '3')
        result = replace(result, '5aceijknqry', '5')
        result = replace(result, '2aceikn', '2')
        result = replace(result, '6aceikn', '6')
        result = replace(result, '1ce', '1')
        result = replace(result, '7ce', '7')
        return result

    clist = []
    rule = g.getrule().split(':')[0]

    fuzzer = rule + '9'
    oldrule = rule
    rule = ''
    context = ''
    deletefrom = []
    for i in fuzzer:
        if i == '-':
            deletefrom = [x[1] for x in Hensel[int(context)]]
        elif i in '0123456789/S':
            if deletefrom:
                rule += ''.join(deletefrom)
                deletefrom = []
            context = i
        if len(deletefrom) == 0:
            rule += i
        elif i in deletefrom:
            deletefrom.remove(i)
    rule = rule.strip('9')

    if not (rule[0] == 'B' and '/S' in rule):
        g.exit('Please set Golly to a Life-like rule.')

    if g.empty():
        g.exit('The pattern is empty.')

    s = GENERATION_STRING
    if not validint(s):
        g.exit('Bad number: %s' % s)

    numsteps = int(s)
    if numsteps < 1:
        g.exit('Period must be at least 1.')

    g.select(g.getrect())
    g.copy()
    s = int(s)

    for i in range(0,s):
        g.run(1)
        clist.append(list(chunks(g.getcells(g.getrect()), 2)))
        mcc = min(clist[i])
        clist[i] = [[x[0] - mcc[0], x[1] - mcc[1]] for x in clist[i]]

    g.show('Processing...')

    ruleArr = rule.split('/')
    ruleArr[0] = ruleArr[0].lstrip('B')
    ruleArr[1] = ruleArr[1].lstrip('S')

    b_need = []
    b_OK = []
    s_need = []
    s_OK = []

    context = ''
    fuzzed = ruleArr[0] + '9'
    for i in fuzzed:
        if i in '0123456789':
            if len(context) == 1:
                b_need += Hensel[int(context)]
                b_OK += Hensel[int(context)]
            context = i
        elif context != '':
            b_need.append(context[0] + i)
            b_OK.append(context[0] + i)
            context += context[0]
    context = ''
    fuzzed = ruleArr[1] + '9'
    for i in fuzzed:
        if i in '0123456789':
            if len(context) == 1:
                s_need += Hensel[int(context)]
                s_OK += Hensel[int(context)]
            context = i
        elif context != '':
            s_need.append(context[0] + i)
            s_OK.append(context[0] + i)
            context += context[0]

    for i in [iter2 for iter1 in Hensel for iter2 in iter1]:
        if not i in b_OK:
            b_OK.append(i)
            execfor = 1
            # B0 and nontotalistic rulestrings are mutually exclusive
            try:
                g.setrule(rulestringopt('B' + ''.join(b_OK) + '/S' + ruleArr[1]))
            except:
                b_OK.remove(i)
                execfor = 0
            for j in range(0, s * execfor):
                g.run(1)
                try:
                    dlist = list(chunks(g.getcells(g.getrect()), 2))
                    mcc = min(dlist)
                    dlist = [[x[0] - mcc[0], x[1] - mcc[1]] for x in dlist]
                    if not(clist[j] == dlist):
                        b_OK.remove(i)
                        break
                except:
                    b_OK.remove(i)
                    break
            g.new('')
            g.paste(0, 0, 'or')
            g.select(g.getrect())
            b_OK.sort()

        if not i in s_OK:
            s_OK.append(i)
            execfor = 1
            # B0 and nontotalistic rulestrings are mutually exclusive
            try:
                g.setrule(rulestringopt('B' + ruleArr[0] + '/S' + ''.join(s_OK)))
            except:
                s_OK.remove(i)
                execfor = 0
            for j in range(0, s * execfor):
                g.run(1)
                try:
                    dlist = list(chunks(g.getcells(g.getrect()), 2))
                    mcc = min(dlist)
                    dlist = [[x[0] - mcc[0], x[1] - mcc[1]] for x in dlist]
                    if not(clist[j] == dlist):
                        s_OK.remove(i)
                        break
                except:
                    s_OK.remove(i)
                    break
            g.new('')
            g.paste(0, 0, 'or')
            g.select(g.getrect())
            s_OK.sort()

        if i in b_need:
            b_need.remove(i)
            g.setrule(rulestringopt('B' + ''.join(b_need) + '/S' + ruleArr[1]))
            for j in range(0, s):
                g.run(1)
                try:
                    dlist = list(chunks(g.getcells(g.getrect()), 2))
                    mcc = min(dlist)
                    dlist = [[x[0] - mcc[0], x[1] - mcc[1]] for x in dlist]
                    if not(clist[j] == dlist):
                        b_need.append(i)
                        break
                except:
                    b_need.append(i)
                    break
            g.new('')
            g.paste(0, 0, 'or')
            g.select(g.getrect())
            b_need.sort()

        if i in s_need:
            s_need.remove(i)
            g.setrule(rulestringopt('B' + ruleArr[0] + '/S' + ''.join(s_need)))
            for j in range(0, s):
                g.run(1)
                try:
                    dlist = list(chunks(g.getcells(g.getrect()), 2))
                    mcc = min(dlist)
                    dlist = [[x[0] - mcc[0], x[1] - mcc[1]] for x in dlist]
                    if not(clist[j] == dlist):
                        s_need.append(i)
                        break
                except:
                    s_need.append(i)
                    break
            g.new('')
            g.paste(0, 0, 'or')
            g.select(g.getrect())
            s_need.sort()

    g.setrule(oldrule)
    ruleres = 'B' + ''.join(sorted(b_need)) + '/S' + ''.join(sorted(s_need)) + \
        ' - B' + ''.join(sorted(b_OK)) + '/S' + ''.join(sorted(s_OK))
    g.show(rulestringopt(ruleres))

    ruleB="B"+''.join(sorted(b_need))
    ruleS="S"+''.join(sorted(s_need))
    isotropiclistB = sorted(b_OK)
    isotropiclistS = sorted(s_OK)

    # Remove B0 and B1 conditions
    for wrongvalues in ["0","1c","1e"]:
        if wrongvalues in isotropiclistB:
            isotropiclistB.remove(wrongvalues)

    # Generate a random isotropic rule which is likely to allow spaceships to exist
    def randIsoRule():
        # Birth conditions
        prob = random.random()*0.55+0.05 # Random number between 0.05 and 0.6
        rulestr = ruleB
        for elem in isotropiclistB:
            if random.random()<prob: rulestr+=elem
        # Ensure rule has a chance of supporting ships
        if len(rulestr) == 1:
            # Add a random rule element
            rulestr+=random.choice(isotropiclistB)
        if not rulestr[1] in '23':
            # Add two random 2x or 3x rule elements
            rulestr+=random.choice(isotropiclistB[:16])
            rulestr+=random.choice(isotropiclistB[:16])
       
        # Survival conditions (force S0 for dot survival)
        prob = random.random()*0.55+0.05 # Random number between 0.05 and 0.6
        rulestr+='/'+ruleS
        for elem in isotropiclistS:
            if random.random()<prob: rulestr+=elem
        return(rulestr)
       
    # ----------------------------------------------------------

    # Return the minimum and maximum of the absolute value of a list of numbers
    def minmaxofabs(v):
        v = map(abs, v)
        return min(v), max(v)

    # Test a pattern in the given rule to determine if it reappears
    def testRule(rulestr):
        r = g.getrect()
        if r:
            g.select(r)
            g.clear(0)
        g.putcells(testPatt)
        g.setrule(rulestr)
        for ii in xrange(maxGen):
            g.run(1)
            pop = int(g.getpop())
            if (pop < minPop or pop > maxPop):
                break
            elif (pop == testPop):
                # Test for periodicity
                r = g.getrect()
                if testPatt == g.transform(g.getcells(r),-r[0],-r[1]):
                    period = ii+1
                    if (r[0] == 0 and r[1] == 0 ):
                        # Oscillator (reject if low period or bOsc is False)
                        if bOsc and period >= minP:
                            return (period, )
                    elif ( period >= minShipP ):
                        # Spaceship (reject if low period)
                        return (r[0], r[1], period)
                    break # Pattern is a low period oscillator or spaceship
        return ()
       
    # Set up the search with the current pattern
    testRect = g.getrect()
    testPop = int(g.getpop())
    testPatt = g.transform(g.getcells(testRect),-testRect[0],-testRect[1])

    if bOsc: minPop = 2 # Patterns with 0, or 1 cells can not be oscillators
    else: minPop = 3 # Patterns with 0, 1, or 2 cells can not be ships

    g.new('spRulesrc')

    for ii in itertools.count(0,1):
        if bOsc==False:
            while 1:
                j=randIsoRule()
                if "2a" in j: break
                if "2c" in j: break
                if "3i" in j: break
        else:
            j=randIsoRule()
        result = testRule(j)
        if result:
            # Interesting pattern found
            break
        if (ii % 1000 == 0):
            g.select([])
            g.show('%d candidate rules tested for interesting patterns' % (ii))
            g.update()
            g.new("")
           
    g.new('Search result')
    if result:
        g.putcells(testPatt)
        if (len(result) == 1):
            Oscillator = setminrule(str(g.getrule()),0,0,result[0])
            return Oscillator
        elif (len(result) == 3):
            dx, dy, period = result
            dy, dx = minmaxofabs( (dx, dy) )
            Spaceship = setminrule(str(g.getrule()), dx, dy, period)
            return Spaceship
        else:
            g.exit('Unrecognised pattern')
        g.show(description)   
    else:
        g.show('No results found')

textfile=open("iterAllRulesrc_results.txt","w+")
g.select(g.getrect())
g.copy()
textfile.write("\n"+g.getclipstr()+"\n\n")
ListRules = set()
while 1:
    newrule=Rulesrc()
    event = g.getevent()
    if event.startswith("key"):
        break
    if newrule[0] not in ListRules:
        ListRules.add(newrule[0])
        textfile.write(newrule[0]+"\t("+str(newrule[1])+","+str(newrule[2])+")/\t"+str(newrule[3])+"\n")
textfile.close()
g.exit("We have found %d results, found in your rule folder as iterRulesrc_results.txt. Thank you for your patience." % len(ListRules))




EDIT: could someone point out a way to make this addition to iterRulesrc?:
- When a spaceship is found with the current constraints, find what rules it works in (easy)
- Do not search rules where that spaceship is valid from that point onwards

Issues: you cannot do it by combinations because you'd end up with a list of 10^16 rules or so

What can be done?
User avatar
Rhombic
 
Posts: 790
Joined: June 1st, 2013, 5:41 pm

Re: Rulesrc: Finding rules for a spaceship

Postby wildmyron » October 31st, 2017, 12:20 am

Rhombic wrote:EDIT: could someone point out a way to make this addition to iterRulesrc?:
- When a spaceship is found with the current constraints, find what rules it works in (easy)
- Do not search rules where that spaceship is valid from that point onwards

Issues: you cannot do it by combinations because you'd end up with a list of 10^16 rules or so

What can be done?

This is readily doable for some cases, but I think for the general case of excluding all rules which any of the previously found results works in it will be slower to test whether or not to search the rule than it is to just search the rule. There are two readily apparent options to restrict the rules to search - both are based on generating the rule and then test if it should be skipped. They are probably easiest to implement with the rule represented as a list of rule elements which can be easily tested against.

  • For the rulespace with a spaceship to exclude: determine the rule elements to exclude. This is the set of rule elements which are allowed for the ship in addition to the required elements for the base search. Then for the rule to be tested: check if all the optional elements are in the list of rule elements for the excluded rulespace - if they are then skip. It would be possible to have multiple exclude lists, but this could become unmanageable fairly quickly.
  • Maintain a set with excluded rules - For every rulespace to be excluded: generate all combinations of the optional allowed rule elements and store them in the set (preferably as a string or tuple). Then for the rule to be tested: check if the optional rule element combination is in the set - if it is then skip the rule. Because elements of a set are hashed (and therefore need to be hashable), testing a candidate rule will be quick. But for large rulespaces to exclude the memory requirements will grow quickly.
I think you would need to have a very specific use case for this to be worthwhile implementing and doing. For example: using searchRule-matchPatt.py to search for ships which match the first 3 or 4 generations there are very few duplicate ships found by the script. This means that the vast majority of rules tested don't match one of the rules disallowed by the above idea. Some very rough numbers: Searching about 10,000,000 rules will give 300-500 results. Of these less than 10 will be duplicates. That means that for 9,999,990 of the rules tested the time taken to test if the rule should be skipped is wasted, as opposed to the time gained by not testing the 10 rules where a duplicate ship was found.

toroidalet wrote:I don't want to sound annoying by suggesting a lot of things, but (and this is probably extremely trivial) could Rulesrc be modified to just look for repetitions of the starting pattern (for finding guns, puffers and replicators)?

I don't see this as a trivial modification to the current Rulesrc scripts. The pattern detection for all of them is contained in the function testRule() which really does little more than the following:
  • Store the initial pattern and population
  • run the pattern for fixed number of generations
  • At every generation: if the current population matches the initial population, then
    • Get the current pattern and test if it is equal to the initial pattern
    • If it is, then return the successful result
In order to look for repetitions of the starting pattern, the initial pattern would need to be tested against subsections of the current pattern. So then you need to break up the pattern into suitable subsections, or use cross correlation or some other pattern matching technique. You also want a way to determine when to do this, rather than doing it at every generation (possible though, but much slower).

Alternatively the search could just look for linear growth of any kind. I haven't attempted something like this because I haven't really had a strong desire to find any particular category of linear growth. It seems to me that there are several design considerations in doing this to give a program which does something that apgsearch doesn't already do. First off, what is the search space? How do you want to constrain the search so that explosive rules don't bog it down, but the search will still find interesting results. Then you have to determine the method to detect linear growth when it happens. One option for this is readily available - the linearlyse() function from apgsearch (along with the deepperiod() function).

It's certainly possible to cobble together a script which will find something, even if it isn't particularly performant. Here's a brief outline:

  • set up the search paramaters
    • candidate pattern (or patterns)
    • candidate rule (or rulespace)
    • test run parameters (how long to run pattern, max period, etc.)
  • inside a loop:
    • Initialise layer with candidate rule and pattern
    • run pattern for fixed gen
    • call linearlyse()
    • test the return value - if it starts with 'y' then break out of the loop
  • restore layer to state with initial pattern and rule which resulted in linear growth
wildmyron
 
Posts: 597
Joined: August 9th, 2013, 12:45 am

Previous

Return to Scripts

Who is online

Users browsing this forum: No registered users and 3 guests