6 ms·

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

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 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.

0xdeadbeefbabe 9y ago
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.
- OscarCunningham 9y ago
  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.
- teraflop 9y ago
  Genetic algorithms tend to not work very well when the overwhelming majority of points in your search space have a fitness of zero.
- sevensor 9y ago
  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.
  - awwaiid 9y ago
    A combination could be interesting - SAT to smooth the space for a GA search.
    - sevensor 9y ago
      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.
paulgb 9y ago
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.
- OscarCunningham 9y ago
  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).
  - deleted 9y ago
    [deleted]
- panic 9y ago
  The code used to find this pattern is online if you're curious about the details: https://gitlab.com/apgoucher/metasat/tree/master https://gitlab.com/apgoucher/metasat/tree/master
- nneonneo 9y ago
  The discoverer developed a program called ikpx (https://gitlab.com/apgoucher/metasat/blob/master/ikpx.py 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.
  - ChickeNES 9y ago
    >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?
jMyles 9y ago
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?
- dazmax 9y ago
  It's not about combining, it's about being designed as a construction based on other known patterns. See http://conwaylife.com/wiki/Gemini http://conwaylife.com/wiki/Gemini for an example of a non-elementary ship.
- deleted 9y ago
  [deleted]
- Someone 9y ago
  ”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 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 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.
  - 9y ago
big_al337 9y ago
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 http://www.conwaylife.com/wiki/Knightship I would have thought that elementary knightship simply meant the most basic knightship: ie. 2v1h
- nneonneo 9y ago
  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-speed-in-conways-game-of-life/ 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.
  - LoSboccacc 9y ago
    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&step=512 https://copy.sh/life/?gist=f3413564b1fa9c69f2bad4b0400b8090&...
  - vanderZwan 9y ago
    > 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
- 9y ago

0xdeadbeefbabe 9y ago

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.

OscarCunningham 9y ago
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.
teraflop 9y ago
Genetic algorithms tend to not work very well when the overwhelming majority of points in your search space have a fitness of zero.
sevensor 9y ago
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.
- awwaiid 9y ago
  A combination could be interesting - SAT to smooth the space for a GA search.
  - sevensor 9y ago
    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.

paulgb 9y ago

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.

OscarCunningham 9y ago
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).
- deleted 9y ago
  [deleted]
panic 9y ago
The code used to find this pattern is online if you're curious about the details: https://gitlab.com/apgoucher/metasat/tree/master https://gitlab.com/apgoucher/metasat/tree/master
nneonneo 9y ago
The discoverer developed a program called ikpx (https://gitlab.com/apgoucher/metasat/blob/master/ikpx.py 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.
- ChickeNES 9y ago
  >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?

jMyles 9y ago

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?

dazmax 9y ago
It's not about combining, it's about being designed as a construction based on other known patterns. See http://conwaylife.com/wiki/Gemini http://conwaylife.com/wiki/Gemini for an example of a non-elementary ship.
deleted 9y ago
[deleted]
Someone 9y ago
”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 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 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.
- 9y ago

big_al337 9y ago

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 http://www.conwaylife.com/wiki/Knightship I would have thought that elementary knightship simply meant the most basic knightship: ie. 2v1h

nneonneo 9y ago
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-speed-in-conways-game-of-life/ 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.
- LoSboccacc 9y ago
  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&step=512 https://copy.sh/life/?gist=f3413564b1fa9c69f2bad4b0400b8090&...
- vanderZwan 9y ago
  > 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
9y ago