ikpx 2.2

For scripts to aid with computation or simulation in cellular automata.
User avatar
calcyman
Posts: 2389
Joined: June 1st, 2009, 4:32 pm

ikpx 2.2

Post by calcyman » October 12th, 2020, 6:48 pm

Since there hasn't been an official announcement, I thought I'd mention that ikpx 2.2 is available here:

https://gitlab.com/apgoucher/ikpx2

It's a considerable improvement over the original ikpx in a number of ways:
  • Supports arbitrary isotropic 2-state Moore-neighbourhood cellular automata (not just B3/S23);
  • Makes use of top-tier modern SAT solvers (namely Armin Biere's cadical and kissat);
  • Uses the 'multi-armed bandit' notion from reinforcement learning to learn which of the SAT solvers are best for which subproblems;
  • More efficient, being written in C++ and statically linked against the solvers instead of spawning subprocesses and using named pipes;
  • Better method of avoiding redundant repetition of work;
  • More user-friendly: can digest partials as RLEs (oriented to move between north and north-west) without requiring manual truncation or running that awkward golly2ikpx script.
  • Better lattice basis: it tries to grow spaceships in the direction exactly antiparallel to the direction of travel;
  • Internal priority heap: it tries to extend the partials with the narrowest backends first (as they're more likely to admit a completion), using length as a tie-breaker (to prefer shorter completions);
  • Adaptive symmetry switching: for orthogonal velocities, it can find spaceships which mix and match components of different symmetries (such as a c/3 turtle with an asymmetric tagalong);
  • Integrated apgsearch: you can use the familiar -n and/or -k flags from apgsearch, and it will run every phase of every intermediate partial through apgsearch (without requiring Unix pipes!) and upload the results to Catagolue's ikpx2_stdin symmetry. This is useful for finding higher-period spaceships and puffers travelling at the target speed.
A speed comparison between ikpx 2.2 and the original ikpx is that the old version took 8 hours running on 72 threads of a mainframe to extend Tom Rokicki's partial to find Sir Robin; the new version took 52 minutes running on 8 threads of a laptop to perform the same feat.

As an example, here's a period-24 c/2 puffer it quickly found in MirrorTLife:

Code: Select all

x = 21, y = 14, rule = B3-kq4j/S2-i34q
3bo13bo$b2ob2o9b2ob2o$b2ob2o9b2ob2o$bo3bo9bo3bo$2o3b2o7b2o3b2o2$2o3b2o
2b3o2b2o3b2o$2bobo3b2ob2o3bobo$2bo4bo5bo4bo$4bobo2bobo2bobo$8bo3bo$6bo
7bo$5bobo5bobo$6bo7bo!
and here's a period-12 c/3 spaceship in the same rule (note that the frontend is asymmetric, with a symmetric backend, followed by an asymmetric high-period tagalong):

Code: Select all

x = 13, y = 41, rule = B3-kq4j/S2-i34q
b4ob3o$b2obob2obo$obo3b4o$bo2b3o$2bo4bo$b2obo3bo$b2o2bo3bo$7bobo$5bo$4b2o$4b
2o$5b2o$6bo$9bo$3b3obob2o$2bobo$7bo$5b2o2$5bo4bo$5bob2ob2o$11b2o2$4b3ob3o$4b
3obobo$6bo$6bo$5bobo$5bobo2$4b2ob2o$6bo$3b2o3b2o$3b2obob2o$4bo3bo3$4bo$3b2o$
2bobo$3bo!
What do you do with ill crystallographers? Take them to the mono-clinic!

wwei23

Re: ikpx 2.2

Post by wwei23 » October 13th, 2020, 11:29 pm

It works like a charm, but: From my own runs of ikpx2, doesn't it print far less than 10000 partials in a reasonable amount of time? How would we reach 10000 partials to upload an ikpx2_stdin haul?
EDIT: I'm just going to try it and hope for the best.

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

Re: ikpx 2.2

Post by calcyman » October 14th, 2020, 6:55 am

wwei23 wrote:
October 13th, 2020, 11:29 pm
It works like a charm, but: From my own runs of ikpx2, doesn't it print far less than 10000 partials in a reasonable amount of time? How would we reach 10000 partials to upload an ikpx2_stdin haul?
EDIT: I'm just going to try it and hope for the best.
Only a small subset of the partials are printed to the terminal (because otherwise your terminal would get constantly bombarded with partials).

On the other hand, ./ikpx2 -n 10000 -v [velocity] runs every phase of every partial (not just the ones that are printed to the terminal).
What do you do with ill crystallographers? Take them to the mono-clinic!

wwei23

Re: ikpx 2.2

Post by wwei23 » October 14th, 2020, 8:12 am

This program is so much faster than JLS or gfind! Why haven't c/8 and 3c/8 orthogonal spaceships been found yet?
Also, where are all the higher-period spaceships? I thought there were supposed to be high-period spaceships on the ikpx2_stdin symmetry.
https://catagolue.hatsya.com/census/b3s2/ikpx2_stdin

User avatar
Moosey
Posts: 4183
Joined: January 27th, 2019, 5:54 pm
Location: A house, or perhaps the OCA board. Or [click to not expand]
Contact:

Re: ikpx 2.2

Post by Moosey » October 14th, 2020, 7:29 pm

wwei23 wrote:
October 14th, 2020, 8:12 am
This program is so much faster than JLS or gfind! Why haven't c/8 and 3c/8 orthogonal spaceships been found yet?
Also, where are all the higher-period spaceships? I thought there were supposed to be high-period spaceships on the ikpx2_stdin symmetry.
https://catagolue.hatsya.com/census/b3s2/ikpx2_stdin
(1) because small ones don't exist (or they would have already been found
(2) because none were found [thinking emoji]
My CA rules can be found here

Bill Watterson once wrote: "How do soldiers killing each other solve the world's problems?"
Nanho walåt derwo esaato?

leaplife advertising bad!

wwei23

Re: ikpx 2.2

Post by wwei23 » October 14th, 2020, 7:30 pm

Moosey wrote:
October 14th, 2020, 7:29 pm
(1) because small ones don't exist (or they would have already been found
(2) because none were found [thinking emoji]
1. I mean that I'm surprised that no one has found c/8 or 3c/8 orthogonal with this program because it's so fast.
2. I'm surprised since there are high period spaceships in literally every other rule that's been ikpx2_stdin'd, unless I missed some (Or maybe B3/S2 is just that fragile.)

User avatar
Moosey
Posts: 4183
Joined: January 27th, 2019, 5:54 pm
Location: A house, or perhaps the OCA board. Or [click to not expand]
Contact:

Re: ikpx 2.2

Post by Moosey » October 14th, 2020, 7:35 pm

wwei23 wrote:
October 14th, 2020, 7:30 pm
1. I mean that I'm surprised that no one has found c/8 or 3c/8 orthogonal with this program because it's so fast.
It's basically comparable to qfind+co for smaller widths (and inferior for very small widths), the only difference is that it doesn't segfault with large widths and you don't have to tell it a width since it widens when it wants-- which makes it difficult to find smaller ships since it can't be told to stay at a width.
My CA rules can be found here

Bill Watterson once wrote: "How do soldiers killing each other solve the world's problems?"
Nanho walåt derwo esaato?

leaplife advertising bad!

wwei23

Re: ikpx 2.2

Post by wwei23 » October 14th, 2020, 7:39 pm

Moosey wrote:
October 14th, 2020, 7:35 pm
which makes it difficult to find smaller ships since it can't be told to stay at a width.
It doesn't widen when it wants. It widens because there are no ships at a given width.

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

Re: ikpx 2.2

Post by LaundryPizza03 » October 16th, 2020, 4:54 pm

Would it be possible to apply symmetry to diagonal ships as well? It would speed up diagonal searches like this one.

Code: Select all

#C Longest partial at width 20
x = 39, y = 36, rule = B34567/S348
2b2o$4b2o$ob3o$ob6obo$b4o4bo$bobo2b2o2b2o$3bob5obo$3bob5ob3o$6b3o5bo$
3b2ob2o2bob2ob2o$5bo3bo3bo2bo$5b3o3bo5b2o$7bobo2b5obo$7bob2obo2b2o$8bo
3bob7o$9bo2b3ob2o3b2o$9b2ob4o2b2o4bo$11bo2b2o5bo2bo$11b2obobo3b2o2b2o$
14bobo2b3o2b4o$14bo3b2obob3o2bo$15bob5ob3o2bo$15bo5b2ob2o2b2obo$21b2ob
o2b5obo$16b4obob11o$18bo2b3ob3ob4o2bo$18bo2b3o6bobo3bo$19b3obo2bo3bo2b
o3bo$21bo2bobo3b2obo2b3o$25bo3b2o3b4o$25b2o3b2o3bo$22b4o2bo2bo2bo$24b
2ob6o$24bob3ob2o$26b3o$26bo!

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 31531 spaceships and 1293 oscillators from outer-totalistic rules. You are invited to help!

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

Re: ikpx 2.2

Post by calcyman » October 17th, 2020, 5:59 am

LaundryPizza03 wrote:
October 16th, 2020, 4:54 pm
Would it be possible to apply symmetry to diagonal ships as well? It would speed up diagonal searches like this one.
Good idea. I've added symmetric and glide-reflective searching for even-period diagonal searches. (Adding symmetry to odd-period diagonal searches would be extremely difficult.)
What do you do with ill crystallographers? Take them to the mono-clinic!

wwei23

Re: ikpx 2.2

Post by wwei23 » October 17th, 2020, 8:26 am

calcyman wrote:
October 17th, 2020, 5:59 am
(Adding symmetry to odd-period diagonal searches would be extremely difficult.)
Out of curiosity, why so?
Also, could ikpx2 be adapted to oscillator searches as a "0c spaceship"?

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

Re: ikpx 2.2

Post by calcyman » October 17th, 2020, 11:35 am

wwei23 wrote:
October 17th, 2020, 8:26 am
calcyman wrote:
October 17th, 2020, 5:59 am
(Adding symmetry to odd-period diagonal searches would be extremely difficult.)
Out of curiosity, why so?
Also, could ikpx2 be adapted to oscillator searches as a "0c spaceship"?
I'll answer these questions in the reverse order.

Let's start by considering how to represent the problem of 'a pattern that moves by (a,b) every p generations'. We can think of this as being an infinite three-dimensional pattern of live and dead cells (in Z^3) satisfying the following:
  • (x, y, t) is a function of [(x+u, y+v, t-1) for u in [-1, 0, 1] for v in [-1, 0, 1]] according to the cellular automaton;
  • (x, y, t) is always equal to (x+a, y+b, t+p);
Now, there's a lot of redundancy here as a result of the second of these rules. So the space in which these patterns live isn't Z^3, but rather the quotient space Z^3 / <(a, b, p)>. It can be shown that this space is isomorphic to the product of Z^2 and a cyclic group of order gcd(a, b, p).

The 'torsion-free' case where gcd(a, b, p) = 1 is conceptually much simpler, because it means that the patterns just live on an ordinary grid isomorphic to Z^2; ikpx2 was written using this assumption for the sake of simplicity, and as such can't find oscillators.

As for the lattice, it's not canonically isomorphic to Z^2; you need to choose a somewhat arbitrary pair of basis vectors. These influence the possible shapes that partials can form. The first basis vector is chosen in the direction of the spaceship; the second basis vector is chosen to be reduced with respect to this first vector.

For even-period diagonal velocities, it's possible for the second basis vector to be perpendicular to the first. That way, even/odd reflections about a vertical axis (in the 'logical' quotient lattice) correspond to glide-reflections and diagonal reflections (in the 'physical' pattern). For odd-period diagonal velocities, the second vector doesn't end up being completely perpendicular, and you don't get this nice property.
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
otismo
Posts: 652
Joined: August 18th, 2010, 1:41 pm
Location: Florida
Contact:

Re: ikpx 2.2

Post by otismo » October 17th, 2020, 12:47 pm

you guys make me want to "study math" again ;-)
In the Game of Life there are no winners there are no losers there are only SURVIVORS.
.....**
...****
.******
*( ͡° ͜ʖ ͡°)*

Code: Select all

#CXRLE Pos=0,0
x = 26, y = 34, rule = B3/S23
23bo$23bobo$23b2o9$2b3o2$o5bo$o5bo$o5bo2$2b3o5b2o$10b2o3$2b2o$2b2o10$
15b2o$15b2o!

Jackk
Posts: 116
Joined: March 13th, 2012, 3:49 pm

Re: ikpx 2.2

Post by Jackk » October 17th, 2020, 4:09 pm

Got myself a file it can't find at compile...
Image
There's files around called base85.h, if those are relevant?

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

Re: ikpx 2.2

Post by calcyman » October 17th, 2020, 7:39 pm

Maybe clone the repository again? It looks like your submodules are somehow confused.
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
silversmith
Posts: 79
Joined: June 15th, 2020, 6:20 pm

Re: ikpx 2.2

Post by silversmith » October 18th, 2020, 12:59 pm

Is there by any chance a way to save completed ships or pause when a ship is completed? I am running a long search and it would be a shame to just lose a result due being unable to find it.

Jackk
Posts: 116
Joined: March 13th, 2012, 3:49 pm

Re: ikpx 2.2

Post by Jackk » October 18th, 2020, 3:09 pm

calcyman wrote:
October 17th, 2020, 7:39 pm
Maybe clone the repository again? It looks like your submodules are somehow confused.
Seems to have worked, thanks! :D

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

Re: ikpx 2.2

Post by calcyman » October 18th, 2020, 5:26 pm

silversmith wrote:
October 18th, 2020, 12:59 pm
Is there by any chance a way to save completed ships or pause when a ship is completed? I am running a long search and it would be a shame to just lose a result due being unable to find it.

Code: Select all

./ikpx2 [OPTIONS] | tee -i progress.txt
will make a persistent copy of the terminal output that you can later search through.
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
silversmith
Posts: 79
Joined: June 15th, 2020, 6:20 pm

Re: ikpx 2.2

Post by silversmith » October 18th, 2020, 6:12 pm

calcyman wrote:
October 18th, 2020, 5:26 pm

Code: Select all

./ikpx2 [OPTIONS] | tee -i progress.txt
will make a persistent copy of the terminal output that you can later search through.
That should work. Thank You.

MathAndCode
Posts: 4325
Joined: August 31st, 2020, 5:58 pm

Re: ikpx 2.2

Post by MathAndCode » October 19th, 2020, 9:20 pm

calcyman wrote:
October 17th, 2020, 11:35 am
The 'torsion-free' case where gcd(a, b, p) = 1 is conceptually much simpler, because it means that the patterns just live on an ordinary grid isomorphic to Z^2; ikpx2 was written using this assumption for the sake of simplicity, and as such can't find oscillators.
So then shouldn't that prevent it from finding spaceships like the XWSSes? (This is not intended to imply that the program should not be able to find XWSSes but instead intended to imply that it should be able to find oscillators.) I think that adaptive symmetry switching should allow it to find both as long as the oscillator has a stator.
I have historically worked on conduits, but recently, I've been working on glider syntheses and investigating SnakeLife.

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

Re: ikpx 2.2

Post by calcyman » October 20th, 2020, 4:07 am

MathAndCode wrote:
October 19th, 2020, 9:20 pm
calcyman wrote:
October 17th, 2020, 11:35 am
The 'torsion-free' case where gcd(a, b, p) = 1 is conceptually much simpler, because it means that the patterns just live on an ordinary grid isomorphic to Z^2; ikpx2 was written using this assumption for the sake of simplicity, and as such can't find oscillators.
So then shouldn't that prevent it from finding spaceships like the XWSSes? (This is not intended to imply that the program should not be able to find XWSSes but instead intended to imply that it should be able to find oscillators.) I think that adaptive symmetry switching should allow it to find both as long as the oscillator has a stator.
Correct; it can't find XWSSes or oscillators.
What do you do with ill crystallographers? Take them to the mono-clinic!

wwei23

Re: ikpx 2.2

Post by wwei23 » October 20th, 2020, 8:38 am

MathAndCode wrote:
October 19th, 2020, 9:20 pm
(This is not intended to imply that the program should not be able to find XWSSes but instead intended to imply that it should be able to find oscillators.)
calcyman wrote:
October 20th, 2020, 4:07 am
Correct; it can't find XWSSes or oscillators.
?????

MathAndCode
Posts: 4325
Joined: August 31st, 2020, 5:58 pm

Re: ikpx 2.2

Post by MathAndCode » October 20th, 2020, 11:24 am

wwei23 wrote:
October 20th, 2020, 8:38 am
calcyman wrote:
October 20th, 2020, 4:07 am
Correct; it can't find XWSSes or oscillators.
?????
I was surprised as well.
I have historically worked on conduits, but recently, I've been working on glider syntheses and investigating SnakeLife.

wwei23

Re: ikpx 2.2

Post by wwei23 » December 9th, 2020, 3:22 pm

How do I build ikpx2 on replit? I'm getting this error:

Code: Select all

g++: internal compiler error: Killed (program cc1plus)
Please submit a full bug report,
with preprocessed source if appropriate.
See <file:///usr/share/doc/gcc-7/README.Bugs> for instructions.

MathAndCode
Posts: 4325
Joined: August 31st, 2020, 5:58 pm

Re: ikpx 2.2

Post by MathAndCode » December 9th, 2020, 8:16 pm

calcyman wrote:
October 20th, 2020, 4:07 am
Correct; it can't find XWSSes or oscillators.
Can it find period-2 oscillators that flip across a diagonal line, such as the blinker?
I have historically worked on conduits, but recently, I've been working on glider syntheses and investigating SnakeLife.

Post Reply