Thread for basic questions

For general discussion about Conway's Game of Life.
User avatar
darkcodeninja
Posts: 7
Joined: April 3rd, 2017, 12:41 am

predecessor?

Post by darkcodeninja » January 7th, 2018, 10:01 pm

hello, it's been a while since I've posted, but what exactly is a predecessor, and how do you find them exactly? i'm a little confused.
Everybody believes in innovation until they see it. Then they think, 'Oh, no; that'll never work. It's too different.'

- Nolan Bushnell

User avatar
Majestas32
Posts: 549
Joined: November 20th, 2017, 12:22 pm
Location: 'Merica

Re: Thread for basic questions

Post by Majestas32 » January 7th, 2018, 11:06 pm

A pattern that evolves after some number of generations into a particular other pattern. People find them with this thing called WLS I believe.
Searching:
b2-a5k6n7cs12-i3ij4k5j8
b2-a3c7cs12-i

Currently looking for help searching these rules.

User avatar
Apple Bottom
Posts: 1034
Joined: July 27th, 2015, 2:06 pm
Contact:

Re: predecessor?

Post by Apple Bottom » January 9th, 2018, 2:21 am

darkcodeninja wrote:hello, it's been a while since I've posted, but what exactly is a predecessor, and how do you find them exactly? i'm a little confused.
This has already been answered, of course, but just for future reference, the wiki and Life Lexicon are great resources for answering such questions as well.
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

User avatar
gameoflifemaniac
Posts: 1242
Joined: January 22nd, 2017, 11:17 am
Location: There too

Re: Thread for basic questions

Post by gameoflifemaniac » January 9th, 2018, 10:19 am

What does each of the button colors on Catagolue mean?
I was so socially awkward in the past and it will haunt me for the rest of my life.

Code: Select all

b4o25bo$o29bo$b3o3b3o2bob2o2bob2o2bo3bobo$4bobo3bob2o2bob2o2bobo3bobo$
4bobo3bobo5bo5bo3bobo$o3bobo3bobo5bo6b4o$b3o3b3o2bo5bo9bobo$24b4o!

dani
Posts: 1222
Joined: October 27th, 2017, 3:43 pm

Re: Thread for basic questions

Post by dani » January 9th, 2018, 10:56 am

gameoflifemaniac wrote:What does each of the button colors on Catagolue mean?
Symmetry, colours based on some algorithm.

User avatar
gameoflifemaniac
Posts: 1242
Joined: January 22nd, 2017, 11:17 am
Location: There too

Re: Thread for basic questions

Post by gameoflifemaniac » January 9th, 2018, 12:53 pm

danny wrote:
gameoflifemaniac wrote:What does each of the button colors on Catagolue mean?
Symmetry, colours based on some algorithm.
I know that, but WHAT symmetries are they?
I was so socially awkward in the past and it will haunt me for the rest of my life.

Code: Select all

b4o25bo$o29bo$b3o3b3o2bob2o2bob2o2bo3bobo$4bobo3bob2o2bob2o2bobo3bobo$
4bobo3bobo5bo5bo3bobo$o3bobo3bobo5bo6b4o$b3o3b3o2bo5bo9bobo$24b4o!

User avatar
Apple Bottom
Posts: 1034
Joined: July 27th, 2015, 2:06 pm
Contact:

Re: Thread for basic questions

Post by Apple Bottom » January 9th, 2018, 5:12 pm

gameoflifemaniac wrote:
danny wrote:
gameoflifemaniac wrote:What does each of the button colors on Catagolue mean?
Symmetry, colours based on some algorithm.
I know that, but WHAT symmetries are they?
If by "button colors" you mean the sample soup link bullets, the colors are computed by taking the first six hex digits of the SHA-256 hash of the symmetry, and interpreting them as an RGB color value.

For instance, D8_4 hashes to "a621fb6a4036736e5b2e468c69d5cee9cfbef98b27200d4a9cca1f2ee3345291", so the color used for that symmetry is #A621FB, a brilliant purple.

Converting a given color back to the corresponding symmetry is left as an exercise for the reader.
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Thread for basic questions

Post by calcyman » January 9th, 2018, 6:27 pm

Yes, apart from C1 which is special-cased as black (#000000).
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
gameoflifemaniac
Posts: 1242
Joined: January 22nd, 2017, 11:17 am
Location: There too

Re: Thread for basic questions

Post by gameoflifemaniac » January 10th, 2018, 1:33 pm

My die hard finder script is way faster now, but can it be improved?

Code: Select all

local g = golly()
local gp = require "gplus"
local selection = g.getselrect()
if #selection == 0 then
   g.exit("There is no selection.")
end
local lifespan = gp.int(tonumber(g.getstring([[
Enter the minimum lifespan of the die hard.]], "0", "Set minimum lifespan")))
g.show("Searching for die hard...")
while ( true ) do
   g.new("")
   g.select(selection)
   g.randfill(50)
   g.run(10000)
   if tonumber(g.getpop()) == 0 then
      g.reset()
      g.run(lifespan)
      if tonumber(g.getpop()) > 0 then
         g.reset()
         count = 0
         while ( true ) do
            g.run(1)
            count = count+1
            if tonumber(g.getpop()) == 0 then
               g.show("Found "..count.."-generation die hard")
               g.reset()
               g.exit()
               break
            end
         end
      end
   end
end
First it checks if the randomly filled region is a die hard, then runs it for your specified number of generations and checks whether there still is someting there (that means, that it lasts longer than the specified number of generations), and then checks how long it lasts.
BTW, is it called diehard or die hard?
I was so socially awkward in the past and it will haunt me for the rest of my life.

Code: Select all

b4o25bo$o29bo$b3o3b3o2bob2o2bob2o2bo3bobo$4bobo3bob2o2bob2o2bobo3bobo$
4bobo3bobo5bo5bo3bobo$o3bobo3bobo5bo6b4o$b3o3b3o2bo5bo9bobo$24b4o!

User avatar
dvgrn
Moderator
Posts: 10612
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Thread for basic questions

Post by dvgrn » January 10th, 2018, 1:39 pm

gameoflifemaniac wrote:My die hard finder script is way faster now, but can it be improved?
Sure -- you could skip the second g.reset(), and replace the second count=0 with count=lifespan.
gameoflifemaniac wrote:BTW, is it called diehard or die hard?
"Diehard" is the way it's listed in the Life Lexicon, for what that's worth.

User avatar
gameoflifemaniac
Posts: 1242
Joined: January 22nd, 2017, 11:17 am
Location: There too

Re: Thread for basic questions

Post by gameoflifemaniac » January 10th, 2018, 2:55 pm

dvgrn wrote:
gameoflifemaniac wrote:My die hard finder script is way faster now, but can it be improved?
Sure -- you could skip the second g.reset(), and replace the second count=0 with count=lifespan.
gameoflifemaniac wrote:BTW, is it called diehard or die hard?
"Diehard" is the way it's listed in the Life Lexicon, for what that's worth.
Lol, I knew that the first word of your answer will be 'sure'.
Thanks!
I was so socially awkward in the past and it will haunt me for the rest of my life.

Code: Select all

b4o25bo$o29bo$b3o3b3o2bob2o2bob2o2bo3bobo$4bobo3bob2o2bob2o2bobo3bobo$
4bobo3bobo5bo5bo3bobo$o3bobo3bobo5bo6b4o$b3o3b3o2bo5bo9bobo$24b4o!

dani
Posts: 1222
Joined: October 27th, 2017, 3:43 pm

Re: Thread for basic questions

Post by dani » January 15th, 2018, 4:20 pm

How would I search for a c/2 'agarship' that runs on this?:

Code: Select all

x = 21, y = 9, rule = B2ei3ein4-a5cer6-e7e8/S1c2e3-cer4a5-ein6-ei78
4bobobobobobobo$bobobobobobobobobobo$2bobobobobobobobobo$bobobobobobob
obobobo$obobobobobobobobobobo$bobobobobobobobobobo$2bobobobobobobobobo
$bobobobobobobobobobo$4bobobobobobobo!
I want to see because it looks possible that one of these:

Code: Select all

#C A breeder that creates chaos within itself, but remains stable nonetheless. It is unknown whether or not a c/2 signal is produced eventually that catches up and destroys the breeder, or whether or not such a signal exists.
#C danny, January 15th 2018
x = 19, y = 19, rule = B2ei3ein4-a5cer6-e7e8/S1c2e3-cer4a5-ein6-ei78
8b3o$8bobo$7bobobo$8bobo$7bobobo$6bobobobo$5bobobobobo$2bobobob3obobob
o$2obobobo3bobobob2o$obobobo2b2obobobobo$2obobobobobobobob2o$2bobobob
3obobobo$5bobobobobo$6bobobobo$7bobobo$8bobo$7bobobo$8bobo$8b3o!

Code: Select all

#C A breeder that creates D4_+1 symmetric chaos, with distinct lines showing on both axes, making the chaos look as if it is 'split' into 4 slices. It is also inverse/Day & Night symmetric along the X axis.
#C danny, January 15th 2018
x = 19, y = 19, rule = B2ei3ein4-a5cer6-e7e8/S1c2e3-cer4a5-ein6-ei78
8b3o$8bobo$7bobobo$8bobo$7bobobo$6bobobobo$5bobobobobo$2bobobob3obobob
o$2obobobo3bobobob2o$obobobob3obobobobo$2obobobobobobobob2o$2bobobob3o
bobobo$5bobobobobo$6bobobobo$7bobobo$8bobo$7bobobo$8bobo$8b3o!
...Can eventually be killed by this, producing a very impressive methuselah.

The only way I could think of is a script that runs one of these bubbles with random soup in the middle to about 2000 generations, then sees if it has died by checking whether specific cells are there, halting when they are not.

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Thread for basic questions

Post by calcyman » January 16th, 2018, 12:04 am

danny wrote:How would I search for a c/2 'agarship' that runs on this?
Let's denote your rule by R. There's a 'sister rule' S such that, for every pattern P, we have:

R(P xor chessboard) = S(P) xor chessboard

Or, in other words, finite live-cell patterns in a vacuum in Rule S behave like finite perturbations in a chessboard in Rule R.

It's similar to 'strobing duality' (mentioned on the LifeWiki) but more exotic and exists in the space of isotropic CA, rather than outer-totalistic CA. Indeed, we have both strobing duality and chessboard duality, so isotropic rules invariant under black/white reversal actually form quartets, rather than pairs.

In short, this means you can find the correct sister rule, write down its rulestring, and apgsearch it.

EDIT: Perhaps I should mention how to find the sister rule.

Let the 'B/S conditions' of a rule be the set of 3-by-3 boxes of cells such that, after iterating by one generation, result in a live centre cell. Clearly, a rule is determined uniquely by its B/S conditions. These black/white symmetric rules have exactly 256 B/S conditions (out of a possible 512).

The correct sister rule (in your case) is obtained by XORing each B/S condition with a 5-cell X, analogous to how the strobing dual is obtained by XORing each B/S condition with a 9-cell solid box.
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: Thread for basic questions

Post by Macbi » January 16th, 2018, 1:51 pm

Is there a data set anywhere of the stabilization times for a bunch of soups?

User avatar
dvgrn
Moderator
Posts: 10612
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Thread for basic questions

Post by dvgrn » January 16th, 2018, 2:16 pm

Macbi wrote:Is there a data set anywhere of the stabilization times for a bunch of soups?
I don't know if Nathaniel still has the accumulated results from TOLLCASS -- The Online Life-Like CA Soup Search. It seems like that's the most likely source of information along these lines, since it actually reported a stabilization time for each 20x20 soup, and collected methuselahs.

Catagolue/apgsearch mostly just make sure that a soup has run long enough to stabilize, and don't bother to go back to pinpoint the exact moment of stability. In fact if I remember right Nathaniel's script also only gave a number that was more or less in the right ballpark -- it was generally a little too big, so new-record methuselah lifespan numbers had to be corrected by hand.

Here's a brief article from August 2009, when TOLLCASS was still running, which took a shot at guessing the power law governing lifespan probabilities. It was a really rough guess, but I threw it into the LifeWiki's Did-You-Know list anyway... it would be good to get a more accurate estimate of that power law.

It wouldn't be too horribly difficult to hack apgsearch to generate really accurate lifespan numbers for methuselahs, and report statistics along these general lines. Maybe it could be done only for soups that last over 10,000 ticks or 25,000 ticks or whatever, to keep from wasting too much time on the run-of-the-mill <500-ticks-to-stability soups.

The difficult case is doing the backtracking for the soups that produce switch-engine puffers, but it's not that hard -- just figure out the population growth equation implied by the puffer's apgcode, and re-run from T=0 to the "definitely settled" point, finding the point where the chosen generation and all following generations match the equation.

That might underestimate the actual stabilization time by a tick or two, but seldom more than that. (?)

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: Thread for basic questions

Post by Macbi » January 16th, 2018, 2:30 pm

dvgrn wrote:It would be good to get a more accurate estimate of that power law.
That's more or less what I'm currently working on. I just wanted to make sure that I wasn't wasting my time by running a bunch of soups and finding their exact stabilization time.

User avatar
Apple Bottom
Posts: 1034
Joined: July 27th, 2015, 2:06 pm
Contact:

Re: Thread for basic questions

Post by Apple Bottom » January 16th, 2018, 4:16 pm

dvgrn wrote:I don't know if Nathaniel still has the accumulated results from TOLLCASS -- The Online Life-Like CA Soup Search. It seems like that's the most likely source of information along these lines, since it actually reported a stabilization time for each 20x20 soup, and collected methuselahs.
Sure hope he does, and that it'll be posted somewhere some day, for its historical significance if nothing else -- the LifeWiki article is, IIRC, based on the Internet Archive's last capture, not the final results when the project was stopped, and a lot of information is simply not available (e.g. on rarer patterns that didn't make the top 154).
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

AforAmpere
Posts: 1334
Joined: July 1st, 2016, 3:58 pm

Re: Thread for basic questions

Post by AforAmpere » January 17th, 2018, 5:15 pm

Would a script that backtracks a pattern to look for incoming gliders for synthesis be a feasible idea, or would it take way too much time to find anything?
I manage the 5S project, which collects all known spaceship speeds in Isotropic Non-totalistic rules. I also wrote EPE, a tool for searching in the INT rulespace.

Things to work on:
- Find (7,1)c/8 and 9c/10 ships in non-B0 INT.
- EPE improvements.

User avatar
dvgrn
Moderator
Posts: 10612
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Thread for basic questions

Post by dvgrn » January 17th, 2018, 5:38 pm

AforAmpere wrote:Would a script that backtracks a pattern to look for incoming gliders for synthesis be a feasible idea, or would it take way too much time to find anything?
For all anybody knows, it might be feasible. I've tried to start writing a search utility along these lines, two or three times in the last decade. But it seems I'm not clever enough to finish the coding -- and my particular implementation might not have worked anyway.

An exhaustive backtracking search stops being feasible pretty quickly, because a pattern's parents are going to be bigger than the pattern -- not always, but on average.

So the trick is to do a non-exhaustive search. Maybe you should go through all the 1-tick predecessors of a pattern, and pick out the top hundred -- the ones that "look the most like a glider synthesis". Then sort out the hundred "best" predecessors of each of those parent patterns. Of those ten thousand patterns, again pick the top hundred, and repeat.

If you can come up with an algorithm that reliably gives higher scores to patterns that are closer to being glider syntheses, then you'll be most of the way there. At that point someone else will probably be happy to write the rest of the search utility.

The most recent experiment along these lines is probably simsim314's tile-based backtracking experiment from a few years ago -- but the project never really reached a workable state.

TL:DR; It's really easy to find predecessors of almost any reasonable pattern.
It's even easy to make them include as many incoming gliders as you want.
It seems to be much harder to arrange it so that when you remove those gliders, the "unsolved" part of the pattern is reliably smaller and simpler than the pattern you started with.

AforAmpere
Posts: 1334
Joined: July 1st, 2016, 3:58 pm

Re: Thread for basic questions

Post by AforAmpere » January 17th, 2018, 5:45 pm

Maybe a neural network could work for this? Another idea might be looking for the top 100 lowest population predecessors. That might help track it to still life state, or still-lives plus reaction state. What have you tried implementing in your programs?
I manage the 5S project, which collects all known spaceship speeds in Isotropic Non-totalistic rules. I also wrote EPE, a tool for searching in the INT rulespace.

Things to work on:
- Find (7,1)c/8 and 9c/10 ships in non-B0 INT.
- EPE improvements.

User avatar
dvgrn
Moderator
Posts: 10612
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Thread for basic questions

Post by dvgrn » January 17th, 2018, 6:06 pm

AforAmpere wrote:Maybe a neural network could work for this? Another idea might be looking for the top 100 lowest population predecessors. That might help track it to still life state, or still-lives plus reaction state. What have you tried implementing in your programs?
Both simsim314 and I started by censusing 5x5 predecessors of 3x3 patterns, to try in various ways to bias a backtracking search toward the 5x5s that looked the most like gliders and still lifes (or blinkers or other "good stuff") and less like space dust.

I'd say simsim314 got a lot farther than I did, but neither of us conclusively proved that this particular kind of selective backtracking was actually a useful approach.

I'd certainly love to see a really determined attempt to apply neural networks or other machine learning techniques to the problem. If you put a whole lot of effort in, there's really no telling what might come out. Maybe nothing, but maybe a search utility that can come up with inhumanly good syntheses of surprisingly large objects.

Anybody know if the Google Alpha Zero team is looking for a really challenging new search space to try out their AI algorithm on?

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: Thread for basic questions

Post by Macbi » January 17th, 2018, 6:19 pm

I thought about this for a while, and one problem I came up with is that there are infinitely many predecessors. There can be some sparks arbitrarily far away from the object which proceed to die out. And sometimes a good synthesis will have such sparks. So any program that tries to backtrack will have to have some way of considering some of these possibilities but not infinitely many of them.

Another thought I had was that it might be smart not to look for low-population predecessors, but for predecessors in which as few cells as possible are about to change state. The idea would be to backtrack to a predecessor which is just a still life and an incoming glider.

Neural networks do seem like a good idea too, especially since deep neural nets have been so successful at board games recently. The problems seem very similar. Perhaps the nets could be trained on test cases produced by colliding a glider with a constellation of still lifes and then evolving forward a few generations. The negative examples could be randomly chosen patterns of the same population and size.

AforAmpere
Posts: 1334
Joined: July 1st, 2016, 3:58 pm

Re: Thread for basic questions

Post by AforAmpere » January 17th, 2018, 6:29 pm

Macbi wrote:Perhaps the nets could be trained on test cases produced by colliding a glider with a constellation of still lifes and then evolving forward a few generations. The negative examples could be randomly chosen patterns of the same population and size.
That is assuming that such patterns have some sort of connection to each other, that makes them 'look' like they came from a glider. If there is no such connection, wouldn't it then be that the network would just spit out random answers of 'Yes, it looks like a glider-constructible pattern' versus 'No, it does not' ? Maybe some test cases need to be run, but I have no idea how to write a net for this.
I manage the 5S project, which collects all known spaceship speeds in Isotropic Non-totalistic rules. I also wrote EPE, a tool for searching in the INT rulespace.

Things to work on:
- Find (7,1)c/8 and 9c/10 ships in non-B0 INT.
- EPE improvements.

bestazy
Posts: 1
Joined: January 20th, 2018, 6:10 am

Re: Thread for basic questions

Post by bestazy » January 20th, 2018, 6:38 am

Hello all!
May I ask here..
What's the real story behind the Conway’s Glider that was drilled into the casing for the MacBook Pro’s Retina display?

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: Thread for basic questions

Post by Macbi » January 20th, 2018, 7:21 am

bestazy wrote:Hello all!
May I ask here..
What's the real story behind the Conway’s Glider that was drilled into the casing for the MacBook Pro’s Retina display?
Eric S. Raymond proposed it as a symbol for hackers (in the sense of computer enthusiasts rather then system infiltrators) so it's probably a reference to that.

Post Reply