Genetic searchers for spaceships -- viable?

[Kazyan]

High-period spaceships remain difficult to search for with current techniques due to the great computational demands. But a great deal of advancement in terms of computation comes not from hardware improvement, but developing better algorithms. Personally, I don't understand the algorithms used in existing software because I don't understand programming or scripting in general, but as far as I'm aware, there are no genetic searchers for spaceships or oscillators.

Here's a naive example of what I mean:

The naive algorithm would construct a series of soups of specified size, involving whichever fixed cell states are specified by the user (known partials, for example). These would be evolved by the desired period of the ship to result in a product, and the similarity between the soup and its product would be scored based on the number of matching ON cells and, to a lesser extent, OFF cells. Perhaps the "better" half of the soups would then be selected, and some combination of mutations and combinations would be performed to acquire a new series of soups based on the survivors. This new series would be evolved by the desired period of the ship, and so on. At each iteration, the top scoring soup would be printed to an output file, and when a soup that exactly matches its own product is found, it will be printed as well, and the search stopped.

Would a search program along these lines be feasible at all? It couldn't hurt to put together a python script along these lines and see how long it takes to find a c/3 ship or somesuch.

[biggiemac]

I was discussing exactly this topic with a CS professor the other week in the context of creating a (2,1)c/6 ship.

I think it is worth exploring but I wouldn't set hopes too high. The problem we identified is that Life is inherently a chaotic system, so moving in a direction of increasing fitness won't necessarily lead one to a 100% fit pattern; instead one would likely end up wandering around aimlessly in the middle of search space or getting stuck on a not-too-fit local maximum..

For what it's worth, see the fantastic program Boxcar2D for typical GA behavior.

In all, I would be happy if it existed but without wanting to code it up myself.

[dvgrn]

...as far as I'm aware, there are no genetic searchers for spaceships or oscillators.

Well, there's probably a reason for that. In random soup, information tends to propagate near light speed. Spaceships and oscillators don't really have any suitable genetic material -- there isn't anything that you can mutate slightly and expect a small change to result.

In other words, high-period spaceships are most likely tiny islands of functionality in a really huge sea of chaos. Even fairly near neighbors of spaceships may not be recognizable as near-spaceships, which means there's no obvious gradient that you can follow upwards to the spaceship pattern.

...I actually did start to write some code along these lines, over a decade ago, but the resulting code probably couldn't have found an LWSS, let alone a new higher-period spaceship. I can't say that I've made a thorough practical test of the idea, or anything like that -- just that after I had written a little trial code, I came up with what looked like really good reasons why genetic algorithms wouldn't work for this problem.

Would a search program along these lines be feasible at all? It couldn't hurt to put together a python script along these lines and see how long it takes to find a c/3 ship or somesuch.

Before anyone starts coding, I'd just suggest a small experiment. Here's a more-or-less randomly chosen phase of a loafer with three cells changed:

Code: Select all

x = 30, y = 10, rule = B3/S23
b2obo16b2obo$b5o15bob3o$o5b2o12bo5b2o$b7o13b7o$2b3o17b3o$7b3o17b3o$8b
2o13bo4b2o$5b2obo17bobo$5bo2bo16bo2bo$6b2o18b2o!

Can anyone come up with a scoring system that can find the original loafer, by incrementally mutating this slightly broken one?

Obviously we can do it by trying all possible three-cell mutations, but that's an exhaustive brute-force search, not a genetic algorithm.

The smallest possible mutation would be to flip the state of one cell. We can easily try every possible one-cell flip, and score each one to see which mutation looks the most like a loafer at T=7. I haven't tried it, but I'll be a little surprised if one of the three changed cells ends up with the highest score, and if one of the two remaining cells then ends up with the highest score in the next cycle. (The final cell won't be a problem, of course.)

This is a really easy contrived example, so if we can't find a scoring system that works fairly reliably on this and similar cases, then I think we can say that there's just plain too much butterfly effect in Conway's Life. If small mutations will too often lead to huge unpredictable effects, then there's probably no workable gradual way to explore this kind of search space.

EDIT: Looking back through old emails, I find that Alan Wechsler did complete a search program using a basic genetic algorithm, and tested several variants of it by hunting for still lifes and p2 oscillators, back in 1994. The results were quite discouraging for still lifes, and even worse for period-2 oscillators.

[Scorbie]

Hmm.... I don't know much about algorithms but could one use genetic algos to find suitable predecessors for synthesis?

[dvgrn]

Hmm.... I don't know much about algorithms but could one use genetic algos to find suitable predecessors for synthesis?

Yeah, it does seem as if there should be some way to patch together partial predecessors to do a non-exhaustive backtracking search. I'm not sure if this would really end up being a genetic algorithm, though. Maybe it would, if you could figure out how to combine the promising left half of one predecessor with the promising right half of a completely different predecessor. Seems like that will be possible in a few cases but not in general.

It's not too computationally difficult to find all possible predecessors of a small-to-medium pattern. The hard part is the scoring system. How exactly do you decide which of the umpteen million options look the most like a possible step toward a glider synthesis? If we can be pretty sure that each step backward will get us just a little closer to a glider synthesis, then we can just let the search run -- we'll probably get back to all gliders eventually. But unfortunately that's a very big "if".

<handwaving subject="vaporware">
My big hope in this area is that someone will come up with a backtracking search that gives a high score to predecessors that are all small still lifes in the middle, or maybe stable/p2, with as thin as possible a ring of active stuff around the edges. There always has to be some active stuff, but we want it to be small well-separated areas if possible... and of course we eventually want it to look like a bunch of gliders.

The predecessors will tend to get bigger and bigger as you go back in time, but with a lot of luck, eventually they'll be big enough that there's room to fit colliding gliders and spaceships in there to build the active islands. Then all that's left is to find a construction for the stable/p2 stuff, and that should be relatively easy.
</handwaving>

[biggiemac]

It's not too computationally difficult to find all possible predecessors of a small-to-medium pattern.

I'm not convinced that even this is true.. Backtracking for predecessors is nearly intractable because there are so many sparks - a predecessor of A + spark is also a predecessor of A, but could have a more feasible predecessor. Checking for sparks that interact at T=-N for all N would be very intensive.

[simsim314]

Obviously Kazyans' solution is problematic due to chaotic nature of GOL, but consider this approach:

Use gsearch column by column approach but with the following scoring system:

1. For some potential column i, add all possible columns of i + 1 - and see the % of them that don't contradict the previous i -1 columns, after P generations.

2. From #1 we got our basic scoring system. The less contradictions some column is providing the more probable the spaceship/oscillator is there. Now take 10 best columns with this scoring and repeat the process.

3. As a side note

- One could use this scoring system just as a way to sort the search tree, although still keeping the search exhausted.

- One could add 3/4 cells as known and leave the rest unknowns in column i + 1 and use this scoring system, to improve performance.

- One could accelerate the system further to check P + k cells in a column (P - period, k small number), positioned at some distance from the border of the column, leaving rest of the cells unknown as a way to accelerate (the contradiction would be applied to k cells, instead of the whole column).

[dvgrn]

It's not too computationally difficult to find all possible predecessors of a small-to-medium pattern.

I'm not convinced that even this is true.. Backtracking for predecessors is nearly intractable because there are so many sparks - a predecessor of A + spark is also a predecessor of A, but could have a more feasible predecessor. Checking for sparks that interact at T=-N for all N would be very intensive.

True enough. I shouldn't have taken out the "T=-1" from my original version of that sentence -- or maybe I should have said "all possible immediate predecessors". That could still be a huge number of predecessors, but if I get to pick the right definition of "small-to-medium" then I can claim that they can all be enumerated in a reasonable amount of time.

Anyway, the picture that I was trying to draw was: step backward just one generation at a time, and come up with some magical metric whereby you can pick the "most likely" predecessor, or the top ten anyway, that on average will be just a little more likely to have an obvious glider synthesis than their successor. Keep the branching factor down, don't do an exhaustive search, and be prepared to step back a lot of generations to get to something workable.

I'm not at all sure that there is any such metric, or even what to try -- some kind of scoring system for all the MxN "fingerprints" in each predecessor, maybe?

[simsim314]

I'm not at all sure that there is any such metric, or even what to try

You need 2*p x 2*p square. Than you can use contradiction after p metric.