## Rulesrc: Finding rules for a spaceship

For scripts to aid with computation or simulation in cellular automata.
LaundryPizza03
Posts: 759
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

### Re: Rulesrc: Finding rules for a spaceship

It would be interesting to have an option to specify a search space directly. For example, if you want to find a spaceship matching a certain pattern for a number of generations, but want to specify certain additional transitions to increase the likelihood of finding a spaceship, you could draw an extra spark whose evolution uses those transitions. But that might unintentionally narrow down other transitions you want to vary. If the transition occurs relatively early in the spark's evolution, progrulesrc is unlikely to find the rulespace with the requisite change without affecting desired transitions.

For example suppose you wanted to search the following pattern, matching 10 generations, which woks in 2^52 rules from B2eik3in4a/S2-i3nqr to B2eik3inq4aenqwz5-iry6-i7c8/S2-i3aknqr4-ij5678, but wanted to also specify S4az to increase your odds of finding a higher-period ship.

Code: Select all

``````x = 4, y = 3, rule = B2eik3in4a/S2-i3nqr4az
3o\$3bo\$b2o!
``````

Code: Select all

``````x = 3, y = 5, rule = B2eik3in4a/S2-i3nqr4az
2o\$2o\$bo\$b2o\$b2o!
``````
but doing so would also exclude S4r, which occurs in the very first generation. At this stage, progrulesrc could remove S4a and/or add B2c and produce a rulespace that is much more explosive than this one:

Code: Select all

``````x = 4, y = 3, rule = B2-an3in4a/S2-i3nqr4rz
3o\$3bo\$b2o!
``````
Compare:

Code: Select all

``````x = 4, y = 3, rule = B2eik3in4a/S2-i3nqr4arz
3o\$3bo\$b2o!
``````
(Nb: I first encountered this limitation with searchRule-matchPatt2.py in a rulespace with spaceships based on a particular replicator.)

Code: Select all

``````x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o\$b2o\$2o!
``````
LaundryPizza03 at Wikipedia

The latest edition of new-gliders.db.txt and oscillators.db.txt have 22470 spaceships and 998 oscillators from outer-totalistic rules. You are invited to help!

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

### Re: Rulesrc: Finding rules for a spaceship

LaundryPizza03 wrote:It would be interesting to have an option to specify a search space directly.
Thank you for the description of what you would like to be able to do. This comes under the TODO item "Decouple the rulespace matching from the target pattern". There are two ways I can see this being implemented:
• Manually over-ride the entire rulespace matching process - This could be done with two parameters for the min and max rule desired. They could be specified something like this:

Code: Select all

``````minrule = "B2eik3in4a/S2-i3nqr4az"
maxrule = "B2eik3inq4aenqwz5-iry6-i7c8/S2-i3aknqr4-ij5678"``````
If both these parameters are specified then the current rulespace checking is skipped and these parameters are used instead.
• Specify additional constraints on the rulespace with manually specified lists of rule elements. Something like

Code: Select all

``````B_need_extra = []
S_need_extra = ["4a", "4z"]
B_OK_extra = []
S_OK_extra = []
B_forbid_extra = []
S_forbid_extra = []``````
I don't think either of these is a big change and both could be made flexible enough that they would be entirely optional. Do you have a preference for either of these options? I'll try to implement one of these over the coming weekend.

Edit: In the meantime, if you want to try out the search you mentioned with an ad-hoc change to the code, you can do so by defining two of those parameters at the top of the script:

Code: Select all

``````# Rule space adjustments
B_need_extra = []
S_need_extra = ["4a", "4z"]``````
and changing this part of the code:

Code: Select all

``````    # Determine the rulespace to search
B_need, S_need, B_OK, S_OK = sss.getRuleRangeElems(numgen)
``````
to:

Code: Select all

``````    # Determine the rulespace to search
B_need, S_need, B_OK, S_OK = sss.getRuleRangeElems(numgen)
B_need.extend(B_need_extra)
S_need.extend(S_need_extra)
``````
The latest version of the 5S Project contains over 226,000 spaceships. There is also a GitHub mirror of the collection. Tabulated pages up to period 160 (out of date) are available on the LifeWiki.

LaundryPizza03
Posts: 759
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

### Re: Rulesrc: Finding rules for a spaceship

wildmyron wrote:
LaundryPizza03 wrote:It would be interesting to have an option to specify a search space directly.
Thank you for the description of what you would like to be able to do. This comes under the TODO item "Decouple the rulespace matching from the target pattern". There are two ways I can see this being implemented:
• Manually over-ride the entire rulespace matching process - This could be done with two parameters for the min and max rule desired. They could be specified something like this:

Code: Select all

``````minrule = "B2eik3in4a/S2-i3nqr4az"
maxrule = "B2eik3inq4aenqwz5-iry6-i7c8/S2-i3aknqr4-ij5678"``````
If both these parameters are specified then the current rulespace checking is skipped and these parameters are used instead.
• Specify additional constraints on the rulespace with manually specified lists of rule elements. Something like

Code: Select all

``````B_need_extra = []
S_need_extra = ["4a", "4z"]
B_OK_extra = []
S_OK_extra = []
B_forbid_extra = []
S_forbid_extra = []``````
I don't think either of these is a big change and both could be made flexible enough that they would be entirely optional. Do you have a preference for either of these options? I'll try to implement one of these over the coming weekend.

Edit: In the meantime, if you want to try out the search you mentioned with an ad-hoc change to the code, you can do so by defining two of those parameters at the top of the script:

Code: Select all

``````# Rule space adjustments
B_need_extra = []
S_need_extra = ["4a", "4z"]``````
and changing this part of the code:

Code: Select all

``````    # Determine the rulespace to search
B_need, S_need, B_OK, S_OK = sss.getRuleRangeElems(numgen)
``````
to:

Code: Select all

``````    # Determine the rulespace to search
B_need, S_need, B_OK, S_OK = sss.getRuleRangeElems(numgen)
B_need.extend(B_need_extra)
S_need.extend(S_need_extra)
``````
The entry could use a single query, in the same form used by LLS or the naïve one produced by get-all-iso-rules.py, to make it easier to check consistency. In the former case, it would be pB2eik-acn3in-acejkry4a-cijkrty5-iry6-i7-c8/S2acekn-i3nqr-ceijy4az-ij5678. Macbi has a script for doing the conversion.

Code: Select all

``````x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o\$b2o\$2o!
``````
LaundryPizza03 at Wikipedia

The latest edition of new-gliders.db.txt and oscillators.db.txt have 22470 spaceships and 998 oscillators from outer-totalistic rules. You are invited to help!

LaundryPizza03
Posts: 759
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

### Re: Rulesrc: Finding rules for a spaceship

This isn't exactly the right place for this, but it may be significant with regards to searchRule.matchPatt2.py. When attempting to find the rules containing a moon, B2aceikn is shortened to the nonsensical "Baceikn" instead of "B2". This happens for many rulespaces containing B2a.

Code: Select all

``````x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o\$b2o\$2o!
``````
LaundryPizza03 at Wikipedia

The latest edition of new-gliders.db.txt and oscillators.db.txt have 22470 spaceships and 998 oscillators from outer-totalistic rules. You are invited to help!

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

### Re: Rulesrc: Finding rules for a spaceship

Thanks for the feedback. I think the partial rule format is a good idea - it's reasonably easy to express when writing it out manually. But i'll need to write a bit of extra code to interpret the format and update the rulespace determination code in sss.py to be able to easily determine rulespaces in that format. This will [robably take a bit longer as I don't have a lot of time to work on it at the moment.
LaundryPizza03 wrote:This isn't exactly the right place for this, but it may be significant with regards to searchRule.matchPatt2.py. When attempting to find the rules containing a moon, B2aceikn is shortened to the nonsensical "Baceikn" instead of "B2". This happens for many rulespaces containing B2a.
That's annoying, but seems to be cosmetic as far as searchRule-matchPatt2.py is concerned. It's not immediately obvious why that's happening, I'll look into it.
The latest version of the 5S Project contains over 226,000 spaceships. There is also a GitHub mirror of the collection. Tabulated pages up to period 160 (out of date) are available on the LifeWiki.

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

### Re: Rulesrc: Finding rules for a spaceship

gooddogtyson wrote:
October 8th, 2019, 7:23 pm
Every time I try to run searchRule-matchPatt2.py, it says "NameError: name 'ii' is not defined"

The Wiki page is no help, so I'm hoping someone here knows how to fix this. Thanks!
Hmm, that's odd. Where did you get your copy of the script from? There may have been a version posted with a bug.

To help with debugging, can you answer these questions:

What is the line number of the error?

What starting pattern did you use for the search?

Did you change any settings in the script? And if not do you have a copy of the *.sss.txt files? (Should get a useful error message if not, but just in case)
The latest version of the 5S Project contains over 226,000 spaceships. There is also a GitHub mirror of the collection. Tabulated pages up to period 160 (out of date) are available on the LifeWiki.

gooddogtyson
Posts: 4
Joined: September 11th, 2019, 7:17 pm

### Re: Rulesrc: Finding rules for a spaceship

wildmyron wrote:
October 8th, 2019, 8:10 pm
gooddogtyson wrote:
October 8th, 2019, 7:23 pm
Every time I try to run searchRule-matchPatt2.py, it says "NameError: name 'ii' is not defined"

The Wiki page is no help, so I'm hoping someone here knows how to fix this. Thanks!
Hmm, that's odd. Where did you get your copy of the script from? There may have been a version posted with a bug.

To help with debugging, can you answer these questions:

What is the line number of the error?

What starting pattern did you use for the search?

Did you change any settings in the script? And if not do you have a copy of the *.sss.txt files? (Should get a useful error message if not, but just in case)
I tried both from the google drive and the github, neither seem to work

The line number is 300

I started with a simple "T" shape just to test the script

I gathered all of the txt files and I have not changed anything within the script. Thanks for replying

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

### Re: Rulesrc: Finding rules for a spaceship

gooddogtyson wrote:
October 8th, 2019, 8:29 pm
I tried both from the google drive and the github, neither seem to work
OK, that's good - you've got the latest version then. I presume you also have a copy of sss.py from the same place, otherwise there'd be a different error.
The line number is 300
Right. That error is just masking another error which must have occurred before the main loop started - which is where ii will be defined. My try .. except .. finally code is a bit dodgy, but I thought the "except Exception, e: raise" should have surfaced the error. can you change that block (at line 290) to the following:

Code: Select all

``````except Exception, e:
g.note(str(e))
raise
``````
Run the script again and copy the content of the Note window here. That should be a much more useful error.

Edit: Or alternatively, temporarily comment out the last line and then the original exception will be raised after the finally block completes.
[/edit]
I started with a simple "T" shape just to test the script
The rule is important too. If this was a T-pentomino in CGoL then specifying more than 3 generations to match is not going to find any spaceships (because the pattern goes symmetric).

I gave a bit of detail about the options in an earlier post https://conwaylife.com/forums/viewtopic ... 608#p79608
Please note that with the default settings it's unlikely that a random pattern in a well known rule is going to give any results from the script. This is because it is unlikely to find new results for 5S in well explored parts of the search space. To contribute to 5S you should be a bit more selective about the starting pattern and number of generations to match - in particular you probably want to use starting patterns which have quite high periods.
However the script is useful for other things too if you change the options. For example, some very high period reflectorless rotating oscillators were found using the script with "bOsc = true" and using a high loopability RRO as a starting pattern. You can see these results on the last page of the RRO thread. And it can also be used for its original purpose - to find periodic patterns with a phase matching the start pattern - if you set stabCycles = 0 and use a small number for the generations to match.
The latest version of the 5S Project contains over 226,000 spaceships. There is also a GitHub mirror of the collection. Tabulated pages up to period 160 (out of date) are available on the LifeWiki.

LaundryPizza03
Posts: 759
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

### Re: Rulesrc: Finding rules for a spaceship

Something weird happens when I match the following ship, a 10c/490o moving down, for 12 generations. Most rules around here seem to explode, while this one does not.

Code: Select all

``````x = 4, y = 3, rule = B2ek3-cky4aci/S1c23ery
2b2o\$obo\$b2o!
``````
The rulespace has 30 degrees of freedom (equating to about a billion rules) and the original ship is endemic, yet rulesrc is likely to find the original ship in the first several thousand rules. This likely involves a peculiarity of the pseudorandom number generator used.

Code: Select all

``````x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o\$b2o\$2o!
``````
LaundryPizza03 at Wikipedia

The latest edition of new-gliders.db.txt and oscillators.db.txt have 22470 spaceships and 998 oscillators from outer-totalistic rules. You are invited to help!

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

### Re: Rulesrc: Finding rules for a spaceship

LaundryPizza03 wrote:
November 19th, 2019, 4:12 am
Something weird happens when I match the following ship, a 10c/490o moving down, for 12 generations. Most rules around here seem to explode, while this one does not.

Code: Select all

``````x = 4, y = 3, rule = B2ek3-cky4aci/S1c23ery
2b2o\$obo\$b2o!
``````
The rulespace has 30 degrees of freedom (equating to about a billion rules) and the original ship is endemic, yet rulesrc is likely to find the original ship in the first several thousand rules. This likely involves a peculiarity of the pseudorandom number generator used.
Yes, that is a bit odd and unexpected. I think it's partly related to the PRNG and also related to the starting rule having only one transition more than the min-rule of the search.

Note that the PRNG is not really a random number generator. It is intended to cycle through all values in it's range once within a full period. You could say that it enumerates the search space in a pseudo-random order. It uses a linear congruential generator (LCG) in order to do this, with parameters chosen to ensure the period matches the range. The choice of parameters isn't made to maximise the quality of randomness because that's not really important here.
The latest version of the 5S Project contains over 226,000 spaceships. There is also a GitHub mirror of the collection. Tabulated pages up to period 160 (out of date) are available on the LifeWiki.

LaundryPizza03
Posts: 759
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

### Re: Rulesrc: Finding rules for a spaceship

I encountered a fatal error in searchRule-matchPatt2.py when running o\$bo\$bo! for 1 generation. This is an instance where get-all-iso-rules.py malfunctions, but the crash reportedly involves the very last line. It's the same bug that causes the script to throw an error if the search is terminated without finding any spaceships.

Code: Select all

``````finally:
g.new('Search result')
g.putcells(origPatt)
if lastRule:
g.setrule(lastRule)
g.show('%d ships found after testing %d candidate rules.' % (Nfound, ii+1))
else:
g.setrule(origRule)

NameError: name 'ii' is not defined
``````

Code: Select all

``````x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o\$b2o\$2o!
``````
LaundryPizza03 at Wikipedia

The latest edition of new-gliders.db.txt and oscillators.db.txt have 22470 spaceships and 998 oscillators from outer-totalistic rules. You are invited to help!

yujh
Posts: 1022
Joined: February 27th, 2020, 11:23 pm
Location: China
Contact:

### Re: Rulesrc: Finding rules for a spaceship

Is there one for spaceships only?
B34kz5e7c8/S23-a4ityz5k!!!
Mission: find a rule with 2-5ob,7-15d,3-5o ships and 4 sparky hp osc.
B2ikn35j6i/S23-a8
B2ck3ar4ac5e6c7/S1e2-an3ejnr4air5iy6c7c8

Hunting
Posts: 3063
Joined: September 11th, 2017, 2:54 am

### Re: Rulesrc: Finding rules for a spaceship

yujh wrote:
April 12th, 2020, 7:46 am
Is there one for spaceships only?
I don't get it. matchPatt2 is spaceship only if bOsc = False.
MLP will live on forever, so does John Horton Conway.
Moosey wrote:
February 5th, 2019, 7:51 pm
“New knightship tagalong!”
“Quick, hide it!”
My TODO list

LeapLife - DirtyLife - LispLife

I could make a rule in ten seconds flat

yujh
Posts: 1022
Joined: February 27th, 2020, 11:23 pm
Location: China
Contact:

### Re: Rulesrc: Finding rules for a spaceship

Hunting wrote:
April 12th, 2020, 10:39 pm
yujh wrote:
April 12th, 2020, 7:46 am
Is there one for spaceships only?
I don't get it. matchPatt2 is spaceship only if bOsc = False.
I mean a rule search for only ships.
Warning: I know nothing about python.
The starting script of this thread searches for both osc and ship.
B34kz5e7c8/S23-a4ityz5k!!!
Mission: find a rule with 2-5ob,7-15d,3-5o ships and 4 sparky hp osc.
B2ikn35j6i/S23-a8
B2ck3ar4ac5e6c7/S1e2-an3ejnr4air5iy6c7c8

Hunting
Posts: 3063
Joined: September 11th, 2017, 2:54 am

### Re: Rulesrc: Finding rules for a spaceship

yujh wrote:
April 12th, 2020, 10:43 pm
Hunting wrote:
April 12th, 2020, 10:39 pm
yujh wrote:
April 12th, 2020, 7:46 am
Is there one for spaceships only?
I don't get it. matchPatt2 is spaceship only if bOsc = False.
I mean a rule search for only ships.
Warning: I know nothing about python.
The starting script of this thread searches for both osc and ship.
matchPatt2 does the work...
MLP will live on forever, so does John Horton Conway.
Moosey wrote:
February 5th, 2019, 7:51 pm
“New knightship tagalong!”
“Quick, hide it!”
My TODO list

LeapLife - DirtyLife - LispLife

I could make a rule in ten seconds flat

LaundryPizza03
Posts: 759
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

### Re: Rulesrc: Finding rules for a spaceship

I've noticed that rulesrc doesn't work for a single dot in the rule B0/S. (It does, however, work for most other B0 patterns.) This is also one of those cases where get_all_iso_rules.py glitches, by the way.

Code: Select all

``````x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o\$b2o\$2o!
``````
LaundryPizza03 at Wikipedia

The latest edition of new-gliders.db.txt and oscillators.db.txt have 22470 spaceships and 998 oscillators from outer-totalistic rules. You are invited to help!