Rule Tables + Weighted Life + Larger than Life

[gbagcn]

There should be a rule family that combines all 3 of these families together. I have created interesting rules in Rule Tables and Weighted Life but Larger than Life patterns tend to die to quickly. These combined rule families should allow a much larger diversity of patterns compared to what one rule can do by itself.

[jks]

I am guessing that Larger than Life patterns tend to die more quickly because there are so many cells in the neighborhood. There are 9 cells involved with Life while adding the next row brings it up to 25 cells. More interesting to me would be to have larger diameter neighborhoods, but only select cells in that neighborhood would have any effect on B & S.

[Axaj]

Weighted rules are possible (albeit very difficult) to make in a rule table, so I'm sure one could make a python script to simplify the process. Higher level Moore/Von Neumann neighborhoods are yet to be implemented in Golly, unfortunately.

[calcyman]

He/she is using MCell, not Golly.

Weighted Life is trivial to implement in a Golly rule table (tree works even better), but I don't think that MCell rules offer the same flexibility.


If you want a more general rule than those offered by MCell and Golly, then I suggest writing your own program.

[jks]

My understanding at this point is that the change to larger neighborhoods in golly would be easy at the source level. I do not have any specifics, only a hint from the writings of one of the authors of golly.

I'm pretty busy for a few weeks, but I think I will look into it some more.

[calcyman]

My understanding at this point is that the change to larger neighborhoods in golly would be easy at the source level.

It's actually rather difficult to do. Assuming that we're using the HashLife algorithm, then the 'leaf' nodes of the quadtree would need to be larger than 2*2. With a radius-k neighbourhood, they would need to be 2k*2k.

That way, for a radius-8 neighbourhood, the leaf nodes must be 16*16. Then, a 32*32 block of four leaves determines the central 16*16 block in the next generation. A 64*64 block determines the central 32*32 block in two generations; a 4k*2^n block determines the 2k*2^n block in 2^n generations (here k = .

Simple in principle, but it would take a lot of re-wiring before Golly can handle this.

[iconmaster]

I can't believe with Weighed Life that Golly hasn't added a seperate algorithm for it yet.
It would be much easyier then making a rule table.

[137ben]

I'm not going to pretend to be an expert in programming when I'm not, but it seems like adding another algorithm would be a lot more work than writing a rule table.

[ssaamm]

Well, writing a rule table is not easy for this, and it can get pretty bloated with all the scripts and in-between neighbors to simulate it, so I think writing an algorithm would be better.

[iconmaster]

I mean, algorithms are simply easier.
Instead of having to tweak a file for a new rule, you just punch in a few numbers in a textbar!

[Paul Tooke]

Iconmaster wrote:

I mean, algorithms are simply easier.
Instead of having to tweak a file for a new rule, you just punch in a few numbers in a textbar!

Easier for whom?
You seem to be overlooking one simple detail. Somebody has to write some code for Golly to make this happen before you get your text dialog. I've implemented Weighted Life rules in my own home-brew programs to only a limited extent and realise that this really isn't straightforward and is going to be tricky to implement in a program like Golly in a way that doesn't impact on performance. If you have a way of implementing Weighted Life in Golly which doesn't affect its performance then please submit a patch to the dev team. I suspect that many people (myself definitely included) would welcome this contribution.

I'm sorry if I come across as blunt and curmudgeonly, but I'm more impressed by people who make things happen than by people who talk about making things happen. The Golly team have done, and are doing, a great job. If there is a rule-set or neighbourhood out there that isn't catered for it probably means that it isn't simple to integrate into the code.

[Axaj]

When I get better at python, I'll try making a script to automate the rule table creation. However, school just started, so I may not find time.

[calcyman]

If you have a way of implementing Weighted Life in Golly which doesn't affect its performance

Use the "Rule Table to Tree" script. There are only 512 possible neighbourhoods (for 2-state, which is all MCell supports), which would result in a relatively small rule tree.

I mean, algorithms are simply easier. Instead of having to tweak a file for a new rule, you just punch in a few numbers in a textbar!

Implementing a new algorithm is much more difficult than creating a rule table/tree. The reason that rule tables run so fast is because Golly uses a multi-state HashLife programmed by Tom Rokicki. And even describing the algorithm, never mind actually programming it, is lengthly:

In HashLife, the entire universe is stored in a compressed (hashed) quadtree. For a 10^12 * 10^12 pattern, this quadtree is as many as 40 levels deep. The 'leaf' nodes contain four numbers between 0 and 255; the other nodes contain four numbers (pointers to addresses in memory) between 0 and 2^32-1 (resp. 2^64-1) in 32-bit (resp. 64-bit) Golly.

You may have used a Life simulator where cells are grouped into 2*2 boxes, and four of those determine the central 2*2 box in the next generation. This is what occurs near the leaves of the quadtree. At the 'trunk' of the quadtree, this is scaled up by many orders of magnitude. Another technicality is that the central 2^n*2^n box is offset by 2^n-1 cells with respect to its parent 2^n*2^n boxes, so the grid alternates, similar to the Margolus neighbourhood.

But that isn't the entirity of HashLife. If that were so, it would rapidly engulf all available memory. HashLife has to combine identical nodes into a single node, in order to compress huge patterns such as wedge-grow+2^60 into the minuscule amount of RAM on a personal computer. That requires some way of being able to compare vast branches of the quadtree, which can represent squares of cells larger than the known universe. This usually involves a sophisticated hash function, which has to be ingeniously designed to minimise the possibility of hash collision. And even that isn't enough -- HashLife requires a dedicated garbage collector, to prune unused branches of the quadtree.


Easier than writing a rule table/tree?

[Axaj]

I mean, algorithms are simply easier. Instead of having to tweak a file for a new rule, you just punch in a few numbers in a textbar!

Implementing a new algorithm is much more difficult than creating a rule table/tree. The reason that rule tables run so fast is because Golly uses a multi-state HashLife programmed by Tom Rokicki. And even describing the algorithm, never mind actually programming it, is lengthly:

In HashLife, the entire universe is stored in a compressed (hashed) quadtree. For a 10^12 * 10^12 pattern, this quadtree is as many as 40 levels deep. The 'leaf' nodes contain four numbers between 0 and 255; the other nodes contain four numbers (pointers to addresses in memory) between 0 and 2^32-1 (resp. 2^64-1) in 32-bit (resp. 64-bit) Golly.

You may have used a Life simulator where cells are grouped into 2*2 boxes, and four of those determine the central 2*2 box in the next generation. This is what occurs near the leaves of the quadtree. At the 'trunk' of the quadtree, this is scaled up by many orders of magnitude. Another technicality is that the central 2^n*2^n box is offset by 2^n-1 cells with respect to its parent 2^n*2^n boxes, so the grid alternates, similar to the Margolus neighbourhood.

But that isn't the entirity of HashLife. If that were so, it would rapidly engulf all available memory. HashLife has to combine identical nodes into a single node, in order to compress huge patterns such as wedge-grow+2^60 into the minuscule amount of RAM on a personal computer. That requires some way of being able to compare vast branches of the quadtree, which can represent squares of cells larger than the known universe. This usually involves a sophisticated hash function, which has to be ingeniously designed to minimise the possibility of hash collision. And even that isn't enough -- HashLife requires a dedicated garbage collector, to prune unused branches of the quadtree.


Easier than writing a rule table/tree?

Do rule tables/trees run in Hashlife?

[137ben]

Do rule tables/trees run in Hashlife?

No, I don't think so.

[calcyman]

Do rule tables/trees run in Hashlife?

They certainly use HashLife. Try running this in Hyperspeed mode:

Code: Select all

x = 12, y = 7, rule = Codd
.5B$BAF.2AB$BA3BAB$BAB.BAB$BA3BA5B$B2A.G6AB$.10B!

If that didn't use HashLife, then it wouldn't run into quintillions of generations.

[Andrew]

Do rule tables/trees run in Hashlife?

Just to clear up any possible confusion, the "HashLife" algorithm included in Golly is a highly optimized implementation for two-state CA. The RuleTable and RuleTree algorithms use a more generalized version of HashLife that supports multi-state CA (up to 256 states). This is also true for the JvN and Generations algos. In fact, QuickLife is currently the only algo that doesn't use a hashing scheme.

Tom has done an excellent job of making it relatively easy to write a new algorithm based on the multi-state hashlife (not as easy as writing a new .table or .tree rule, but certainly much easier than writing a completely new algo from scratch). I'd urge people interested in writing a new algo to download Golly's source code and have a look at the code that implements the Generations algo. This is in generationsalgo.h and generationsalgo.cpp. The .h file is almost trivial, and even the .cpp file has less than 200 lines of code. Essentially you need to write a setrule() routine that decides which rule strings your algo will support, and a slowcalc() routine that returns the new state of a cell based on its neighboring cells.

[confocaloid]

Bump.

[...]
Tom has done an excellent job of making it relatively easy to write a new algorithm based on the multi-state hashlife (not as easy as writing a new .table or .tree rule, but certainly much easier than writing a completely new algo from scratch). I'd urge people interested in writing a new algo to download Golly's source code and have a look at the code that implements the Generations algo. This is in generationsalgo.h and generationsalgo.cpp. The .h file is almost trivial, and even the .cpp file has less than 200 lines of code. Essentially you need to write a setrule() routine that decides which rule strings your algo will support, and a slowcalc() routine that returns the new state of a cell based on its neighboring cells.

I'm interested in what kinds of algorithms can be added in a way that would interact nicely with already existing Golly codebase / existing features.
Could there be some kind of outline / introduction to Golly (for people who might want to implement something), in addition to "studying the source code to attempt to understand what's possible"?

To be specific, I'm currently interested in how one could add to Golly support for "transient rules" (when the @RULE text is appended to the pattern, instead of being stored in a separate file). That already works in LifeViewer making it possible to share self-contained patterns / patterns relying on a specific version of a ruletable.

At this point, I don't understand possibilities well enough to say what I could do. However, at the very least, I'll be willing to test the functionality, in case it is implemented.

Would the following work? Are there missing details / scenarios? Are there non-obvious stumbling blocks that would immediately render the entire idea hopeless?

• Define a new algorithm "TransientRuleLoader", which is the same as RuleLoader as far as evolving the patterns goes, but is treated differently in user interface and when reading or writing pattern files.
• Define a new "self-contained" pattern format (pattern data followed by @RULE definition, with the name of @RULE matching the rulename in the RLE header).
• When loading a "self-contained" pattern from a .rle file, switch to the TransientRuleLoader algorithm and load both the pattern data and the @RULE info. If loaded successfully, then do not add the @RULE info to pattern comments (thus View -> Pattern Info would show only actual pattern comments).
  Otherwise, load the pattern the same way as before, and preserve all pattern comments.
• When saving a pattern from the current layer to a .rle file, if the current algorithm is TransientRuleLoader, then write the @RULE info from memory after writing the pattern. Otherwise, save the pattern the same way as before.
• When pasting a clipboard pattern in the "self-contained" format, if preferences/the way of pasting dictate that the rule should be changed to what was specified in the clipboard, then switch to TransientRuleLoader and load both the pattern data and the @RULE info.
  Otherwise, paste the clipboard pattern the same way as before.
• When copying a selected region of the pattern to clipboard, if the current algorithm is TransientRuleLoader, then append the @RULE info from memory to the pattern data, and copy the result to clipboard. Otherwise, proceed the same way as before.
• When the current algorithm is TransientRuleLoader, instead of displaying the rulestring/rulename in the window title, display a generic placeholder string, for example "untitled [unnamed rule]".
  edit 1: Alternatively, display the specified rulename but make it clear that it's transient, for example "untitled [RuleName, transient]".
• In the "Control -> Set Rule..." dialog, when the selected algorithm is TransientRuleLoader, disable the UI for entering a rulestring, because it most likely will not make sense in this case.
  When the user switches from TransientRuleLoader to another algorithm, "forget" the transient rule currently in use (although it will be possible to do "Undo" to switch back).
  When the user switches from another algorithm to TransientRuleLoader, assume a 256-state "do nothing" rule (an empty ruletable).
• Internally, represent a transient rule as a (fairly long and variable-length) "rulestring", which would encode the appended @RULE info (minus formatting style such as optional whitespace -- probably there would be a simplification step to make the "rulestrings" shorter).
  
  I think it would make sense to allow setting such "rulestrings" from a Golly script (but probably not via user interface). If a script could set a TransientRuleLoader "rulestring" via g.setalgo / g.setrule, then it would be possible to implement custom notations for rulespaces by writing a script, without creating any temporary rulefiles.

[...]
So the intention is that if there is an @RULE definition in the pattern file it should be used in preference to any local rule or repository rule. That way you can safely share a pattern knowing that it will work as you intended since it comes with the specific version of the rule you chose to append.
[...]

A cleaner solution might be to make pattern comment rules transient (i.e. not saved). All of the valid comments in this thread above are handling the situation where we're trying to persist the rule and deal with name clashes and so on.

When opening a pattern if it contains an @RULE section in the pattern comments then:

1. Use the rule definition from the pattern comments (even if there is local rule with the same name).
2. Do not add this rule to the local rule folder.

If you modify and save the pattern then the rule is maintained since it's still in the comments.
The rule name is now irrelevant.

This would require some changes to Golly.