Using AI for ship search

For scripts to aid with computation or simulation in cellular automata.
Post Reply
lemon41625
Posts: 337
Joined: January 24th, 2020, 7:39 am
Location: 小红点 (if you know where that is)

Using AI for ship search

Post by lemon41625 » May 25th, 2022, 11:10 pm

Recently, I was thinking about searching for ships in Cellular Automata and particularly on how to decide which extension of the ship should be tested first. Being able to identify which extension is more promising would significantly speed up the ship searching speed.

One possible way to do this would be to use some kind of neural network (maybe some CNN, MLP, RNN or even a Transformer 👀) to find the number of new rows that need to be added in order to find an extension. I would think the best would be an RNN since the rows are some kind of a sequence. Transformers could work as well to model longer range relationships between the rows using self-attention for high period ships.

Of course there are a few issues with this:
- the inference time of the neural network would be quite large (but maybe this can be solved using Knowledge Distillation to compress the neural network size or running the search on a GPU)
- it seems that the neural network would need to be re-trained for different widths and speeds and rules which is a bit troublesome (perhaps there would be a way to give the neural network information about the speeds, maybe some similar to this?)
- the variable input size would also be a bit troublesome to deal with - what would be a good representation for the input to the neural network?
- the training data may also be a bit hard to obtain since it would need ships to be found first so that the training data can be inputted which would mean this can't be used to search for ships with new speeds? It would also need quite a number of ships of that speed to be found so...

I am considering trying to implement this in the latter half of this year when I'm more free but I don't really know how to resolve these issues. Any ideas? Or maybe there is another way to identify which extension is more promising?
Download CAViewer: https://github.com/jedlimlx/Cellular-Automaton-Viewer

Supports:
BSFKL, Extended Generations, Regenerating Generations, Naive Rules, R1 Moore, R2 Cross and R2 Von Neumann INT
And some others...

Nickolas
Posts: 6
Joined: April 15th, 2022, 7:04 pm

Re: Using AI for ship search

Post by Nickolas » June 7th, 2022, 1:14 pm

It seems to me that patterns that aren't assembled out of known components with predictable interactions are essentially random. That is, no one knows why, say, the Copperhead is a c/10 orthogonal spaceship, it just happens to be one, and knowing about it doesn't help you make other spaceships that aren't trivially derived from it. Assuming that claim is more or less correct (and I admit my knowledge of CGOL is very shallow), then a neural network wouldn't help you here, because there's no underlying structure to learn. It would be akin to training a neural network to factor integers.

HartmutHolzwart
Posts: 674
Joined: June 27th, 2009, 10:58 am
Location: Germany

Re: Using AI for ship search

Post by HartmutHolzwart » June 8th, 2022, 6:51 am

AI could be used to steer conventional search algorithms by tweaking various search parameters to guide sub-searches appropriately, though.

E.g., when searching for vertical or horizontal branches, general search direction matters. This I do manually by setting up specific searches for parts. AI could learn to set these parameters and use feedback reports on search progress for measuring success of specific parameter settings.

User avatar
pzq_alex
Posts: 401
Joined: May 1st, 2021, 9:00 pm
Location: in the life universe

Re: Using AI for ship search

Post by pzq_alex » June 8th, 2022, 9:19 pm

AI could also probably replace the lookahead algorithm in gfind / the SAT lookahead in ikpx2, as a heuristic for which branches of the search are more likely.
Make b38s23/C1 great again!
https://catagolue.hatsya.com/census/b3a ... a4ity6c/C1
救救kench
Working on a spaceship search program…
Stop turning this forum into a place for politics. Please.

Code: Select all

x=4,y=3,rule=B3S2-i3-a4ciz5j6c8
bo$3o$ob2o!

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

Re: Using AI for ship search

Post by LaundryPizza03 » June 9th, 2022, 7:55 pm

I had an idea of using a generative AI to find large numbers of similar objects in various rules. The premise is that some rules have many highly active objects with a similar moving frontend. Such objects are are highly sensitive to perturbations and changes in rule transitions.

For example, B-like rules have metastable c/2o engines resembling the B-heptomino, as is the case in regular Life. They usually have S4i to stabilize this frontend, and to make the R-pentomino evolve into a B-like object; and no S3a, which tends to drastically stabilize rules because the block vanishes instantly.

In parts of this rulespace, B-like frontends can be much more long-lived than in Life, and some rules have (predecessors to) high-period oscillators and spaceships; many of the spaceships found by the 5s project are B-like objects. In the classic B-like rule, Omosso, the following six objects are respectively three different diehards, a p112 RRO, a c/98o spaceship, and a 50c/100o.

Code: Select all

x = 5, y = 45, rule = B2k3acijr4ijqy6i7c/S2aek3ijnqr4it5n
2b2o$bo2bo$o3bo$2ob2o$b2o16$2b2o$bo2bo$bo2bo$2ob2o$b2o16$ob2o$2o2bo$4b
o$bob2o$b2o!
The idea is that beginning with a database of periodic B-like objects, we can train an appropriate generative model to find possible oscillators and spaceships, and then test which ones become oscillators or spaceships. Of course, we would need a preexisting database like a subset of 5s or a program that generates a suitable training set. The question remains: What kind of training set do we need, and which generative model is most suited for selecting these objects?

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

Post Reply