Using AI for ship search

[lemon41625]

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?

[Nickolas]

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]

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.

[pzq_alex]

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.

[LaundryPizza03]

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?

[googleplex]

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.

Bump

IIRC gfind works by representing spaceships as a graph, and then searching, breadth first, through this graph. I believe it would be quite possible to create a search program which uses an AI to prioritize graph nodes. I'll look into the feasibility of creating a search program based on this idea, but my programming skills and/or gfind knowledge may not quite be up to scratch.

EDIT1:

One issue I've come across so far with using a neural net is the inherently different width of the input to the hypothetical neural net, as the width of spaceships varies. One option is zero-padding, but I'd like to find a better option.

[Sokwe]

IIRC gfind works by representing spaceships as a graph, and then searching, breadth first, through this graph. I believe it would be quite possible to create a search program which uses an AI to prioritize graph nodes.

During qfind's depth-first search it prioritizes rows that have more predecessors (more 3-row stacks that evolve into that row). I reasoned that this would give more extension options. It did give a slight speed boost (~8% as I recall). I do think there may be potential for AI to decide that some branches look "bad" and throw them out early (even if they might have led to a spaceship) in order to make the search progress faster down more likely paths. However, it may also be that the "more likely" paths take up the large majority of the search time anyway, since they tend to have more options for extension.

[HartmutHolzwart]

AI methods may guide search directions by adapting certain search parameters together with the search direction and identifying the most promising direction. This would lead to ‘wiggling’ spaceship worms. AI colluded also help to identify promising branch points.

I’ve posted that before, I guess.

[googleplex]

AI methods may guide search directions by adapting certain search parameters together with the search direction and identifying the most promising direction. This would lead to ‘wiggling’ spaceship worms. AI colluded also help to identify promising branch points.

I’ve posted that before, I guess.

That's the main idea, one issue is going to be finding good training data. I'm going to have to do a lot of experimentation on what makes good inputs to the neural net. I'm currently working on a python implementation of these basic ideas using Pytorch for the machine learning part.

I'l post a github link as soon as a basic implementation is functioning