Hacker News Reader

Comment by nneonneo | Hacker News Reader

Context: a knightship is a glider (a structure that translates itself across the Life grid periodically) which moves 2 horizontal units for each 1 vertical unit (or vice-versa if rotated). This is in contrast to e.g. the most popular 3x3 glider which moves diagonally (1 for 1). A knightship is a type of oblique glider - one that doesn't move orthogonally (only horizontal/vertical) or 45º diagonally.

What makes this an elementary knightship is that it isn't built out of smaller discrete components, unlike (for example) the oblique glider Waterbear (http://conwaylife.com/wiki/Waterbear). It's the first elementary oblique glider discovered.

It also happens to move exactly 2 vertical units for each 1 horizontal unit of motion, and carries this out in 6 time-steps (the theoretical minimum). Thus, in some sense it has the simplest movement of any possible knightship.

View on HN

I find Game of Life utterly fascinating. Every time I read about it, I find myself wanting to understand more of the memephere surrounding it. One question that arises in me here:

> What makes this an elementary knightship is that it isn't built out of smaller discrete components

How is that determined?

In other words, can't you take small components, smash them together to get a bigger thing, and then pass it off as elementary?

Don't we need to "reverse the hash function" to determine if it's possible to make Sir Robin (that's what thing thing is going to be called) out of smaller things?

Or is it possible to prove for a given larger object that it can't possibly be the result of smaller things combining?

It's not about combining, it's about being designed as a construction based on other known patterns. See http://conwaylife.com/wiki/Gemini for an example of a non-elementary ship.

”Or is it possible to prove for a given larger object that it can't possibly be the result of smaller things combining?”

For some, that is possible. Trivial examples are objects of zero, one, or two pixels; less trivial are gardens of Eden (http://conwaylife.com/w/index.php?title=Garden_of_eden)

However, I don’t think “elementary” is synonymous with “can’t possibly be the result of smaller things combining”. http://conwaylife.com/wiki/Elementary defines it as

”A pattern is said to be elementary if it is not reducible to a combination of smaller parts.”

If one takes two gardens of eden and place them far enough apart, the result is a new garden of Eden that ”can’t possibly be the result of smaller things combining” (even stronger: it can’t possibly be the result of anything), but it is reducible to smaller parts.

I don’t think there is a formal definition of ‘elementary’ that everybody can agree on. In the limit, only patterns of a single cell are elementary.

The "elementary" vs. "engineered" distinction might be clearer with an example of an engineered spaceship, like one of the Corderships: http://conwaylife.com/wiki/13-engine_Cordership .

Inside the 13-engine Cordership are thirteen switch engines, each of which moves at a twelfth of the speed of light, but leaves junk behind. The thirteen pieces basically collaborate on cleaning up each other's junk to make a clean spaceship.

It's very difficult to prove that a large elementary spaceship can't possibly be created by crashing gliders together (for example). Several elementary spaceships do in fact have known glider constructions, but that doesn't stop them from being elementary -- you can't pick those spaceships back apart into their constitutent gliders once they're constructed, and often they're traveling a totally different speed and direction than a glider anyway.

I understand that, but those are the easy ones, and I think they are the exception, when looking at all possible spaceships, rather than the spaceships we know of.

A definition for ‘elementary’ that I think is closest to intuition is that ‘elements’ are connected (for some definition of connected) subsets of a pattern do not touch other parts of the pattern and that would survive individually in isolation.

Problems with that definition are that, after cutting of the obvious elements, you may be left with stuff. Using the term ‘elementary’ implies that that stuff either must be elementary, or be built of other elements. The former is the easiest way out, but (as an extreme example) the resulting element might be a garden of Eden with a billion cells that, in isolation, would die out. Would you really want to call such a monster an element?

Also, if a pattern of <50 cells can be constructed from a few dozen carefully placed small ‘obvious elementary’ parts, less than 100 or so time units in the past, I think many would agree the pattern’s elements are those parts.

Problem 1: AFAIK, it is an open problem to decide whether such a set of items exists for a given pattern.

Problem 2: that set may not be unique, and there may not even be a unique smallest (for whatever definition chosen) one in the set of solutions.

Problem 3: if the smallest such set is way, way larger than the pattern it constructs, and must be constructed way, way in the past, do you still consider the pattern to be constructed from those many, many elementary parts?

Yeah, Problem 1 definitely is a (very difficult) open problem, not likely to be solved any time soon.

Problem 2 just looks to me like a known fact, not really a problem... and Problem 3 is only a problem if you don't accept the standard definition of "elementary", and/or if you worry too much about leftover pieces.

As soon as you can see two separate pieces inside a larger spaceship, and each of the pieces in isolation would travel at the same speed as that larger spaceship, then that larger spaceship is not an elementary spaceship.

Once you take out the recognizable pieces, there may well be sparks and other junk left over. But they might just be side effects of the interaction of the recognizable pieces, not anything that can function independently. There are way too many such fading sparks and such for each one to deserve its own name.

Minor side note -- no spaceship of any size will ever contain a Garden of Eden, because every spaceship by definition has at least one predecessor (itself).

> each of which moves at a twelfth of the speed of light

I presume this is cellular-automata jargon for moving one cell per cycle?

edit: btw, I just saw the discussion about not posting to HN yet on the boards. My apologies, had I seen it I would have waited. I only posted this because (to my surprise) it looked like nobody else had and GoL posts are usually pretty popular around here.

Yup, the "c" in spaceship speeds, like "(2,1)c/6", is the same c as in "E=mc^2". It's a good analogy -- one cell per cycle is the maximum possible speed that information can travel in the Life universe.

I haven't read it yet, but you'd probably find Stephen Wolfram's "A New Kind of Science" pretty interesting.

From the talks I've seen a lot of it seems to stem from the idea of simple rules allowing a lot of complexity. He talks about other cellular automata other than Conway's Game of Life, but the ideas are similar.

http://blog.stephenwolfram.com/2017/06/oh-my-gosh-its-covere...

This idea comes up a little bit differently in Max Tegmark's book "Our Mathematical Universe" which I liked too.

If you want to experiment some more, I made this little webgl app [0] that makes it easy to mess with Conway's GoL while it's executing (you hold shift, which pauses the simulation, and click on cells to toggle them on or off). It's easy to 'paint' some basic gliders (e.g. http://images.slideplayer.com/25/8056158/slides/slide_3.jpg), then un-pause and watch them go off for instance. Or just try drawing a vertical or horizontal line of three cells (you get a simple oscillator), then try adding or removing things to it.

There's also a dropdown full of interesting patterns you can load up (with descriptions from mathematicians).

[0] http://symbolflux.com/conwayz/

It's actually easily provable, and simply by observation, because "smaller things combining" has a much simpler definition than what you're assuming! What it actually refers to is how some spaceships, such as the Waterbear -- https://www.youtube.com/watch?v=on3ZLLKQp-4 -- are constructed explicitly as a circuit of building blocks (as you can see in the video), whereas elementary spaceships like this knightship consist of "space dust" that isn't separable into independently-functioning components.

Also remember Conways compression- any series of bytes, could be interpreted as the endresult of several conway games, layed over one another with relational operations.

So it compresses titanic data down to some Booleans and chess expressions.

Size: 4096 x 4096 Offset: (0,0) Def: GameA Opening Lib:C3 Turns: 2567

[&] Size: 512x 512 Offset: (12,0) Def: GameB Opening Lib:G42 Turns: 12

[!] Size: 4096 x 4096 Offset: (0,0) Def: GameD Opening Lib: FULL_HOUSE Turns: 0

Its a pretty nifty way to compress files beyond the point of no return, knowing that the deterministic knowledge of the game- allows for a full recreation of any file, given enough processing power and time.

There are of course some attempts to optimize the whole process- having often used game snapshots to fast-forward from and re-wind back too.

Thanks for the explanation!

Do people searching for these rely on brute force to find interesting ships, or are there other techniques to designing them? It certainly doesn't look "designed", but almost organic.

The ship definitely wasn't "designed", but a SAT solver was used rather than direct brute force and constraints were used to cut down the search space (for example looking for a long-and-thin ship rather than one of arbitrary shape).

The code used to find this pattern is online if you're curious about the details: https://gitlab.com/apgoucher/metasat/tree/master

The discoverer developed a program called ikpx (https://gitlab.com/apgoucher/metasat/blob/master/ikpx.py), part of his larger "MetaSAT" project, which poses the problem of finding an oblique glider as a set of SAT constraints. Additional heuristic constraints were added to limit the search space. ikpx passes the resulting ball of constraints to a SAT solver, which does the computational work of attempting to find a satisfying solution.

It's a clever approach as modern SAT solvers are surprisingly powerful. I actually use this approach myself in some of my (personal) work, e.g. to automatically find execution paths through a target binary for reverse-engineering purposes.

>It's a clever approach as modern SAT solvers are surprisingly powerful. I actually use this approach myself in some of my (personal) work, e.g. to automatically find execution paths through a target binary for reverse-engineering purposes.

I'm interested in the latter, do you have any readings/blogposts/books you would recommend?

Take a look at Angr (http://angr.io/), which implements symbolic execution + SMT solving to analyze program execution (not my work, although I know a number of the authors).

SAT/SMT solving can be quite handy for assisting fuzzers in selecting good paths, which is something I've investigated in the past. Angr can help with that too, although the most recent developments in practical fuzzing have been in coverage-testing approaches (like afl) rather than in symbolic execution approaches.

I also play CTFs a fair bit, and in those we sometimes use Z3 and Boolector (two numerically-oriented SMT solvers) to solve challenges. As an example: https://github.com/pwning/public-writeup/tree/master/9447ctf...

Are there non-elementary knightships that move 2v1h?

I'm not really well versed in GOL, but from ths: http://www.conwaylife.com/wiki/Knightship

I would have thought that elementary knightship simply meant the most basic knightship: ie. 2v1h

In principle, one could construct a non-elementary knightship (the Geminoid construction is said to be capable of this - essentially it's a giant universal constructor that can be "programmed" to reconstruct itself an arbitrary distance from its initial position), but they're rather less interesting since they tend to be very large and not useful as building blocks.

In contrast an elementary object, like a knightship, tends to be nice and small, and therefore highly valued as a building block for more powerful systems. Orthogonal and diagonal gliders see a ton of use in complex Life systems, and it's probable that the new knightship will see good use too (once people start building and exploring the requisite tooling - guns, eaters, and other reactions).

See https://niginsblog.wordpress.com/2016/03/07/new-spaceship-sp... for a rundown of the difference.

It is definitely possible, and extremely probable, that extremely large "elementary" structures exist - but we lack the computational power to find such things.

also self-contained glider that leave no structures behind and don't require structure to move are essential in repeating mechanism, since they leave the path in a known state, i.e.

https://copy.sh/life/?gist=f3413564b1fa9c69f2bad4b0400b8090&...

> This table does not include oblique speeds, which causes little inconvenience because no elementary oblique ships are known.

Well, guess that needs to be updated :D

Another key point about this knightship, ignoring that it's elementary, is that it also moves at the fastest possible speed of 1/6 in an oblique direction. This had never been done before. The pre-existing non-elementary ships are all quite slow and it's hard to imagine them hitting the maximum possible speed.

If a genetic algorithm were used to search it seems like the fitness function is obvious (it moves across for ever two moves up using a minimum number of iterations), but the mating function is not obvious. So I'm wondering if it's a brute force sort of search.

People have tried to use genetic algorithms to search for patterns in Life, but have been unsuccessful because the evolution of a pattern is very sensitive to initial conditions.

Genetic algorithms tend to not work very well when the overwhelming majority of points in your search space have a fitness of zero.

I've done a lot of work with GAs, and they've got a place, but ironically Life is not where they belong. Apparently they're using SAT solvers for the search, which is a lot more reasonable. The problem is exactly as you state it -- there's no fitness function that can take you from infeasibility to feasibility.

A combination could be interesting - SAT to smooth the space for a GA search.

Yeah, a lot of the original work on how GAs would optimize NP-complete problems is pure hand-waving and wishful thinking. Building-block theory, schema processing, it all sounds nice, but tends to result in disappointment. The thing GAs are actually good at is population-based search -- maintaining a bunch of alternative ideas at once. Either your suggestion of using GAs as a local optimizer for the non-satisfiability part of a mixed problem, or the inverse, using the GA to suggest starting points and using a SAT solver for the local search, is much more likely to produce interesting results. It's an idea I keep coming back to, although I still haven't struck gold with it.

Reply on news.ycombinator.com