Rule Tables + Weighted Life + Larger than Life

For discussion of other cellular automata.
Post Reply
gbagcn
Posts: 11
Joined: July 11th, 2010, 4:36 pm

Rule Tables + Weighted Life + Larger than Life

Post by gbagcn » July 25th, 2010, 4:03 pm

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
Posts: 8
Joined: July 22nd, 2010, 2:39 pm

Re: Rule Tables + Weighted Life + Larger than Life

Post by jks » July 25th, 2010, 4:39 pm

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
Posts: 232
Joined: September 26th, 2009, 12:23 am

Re: Rule Tables + Weighted Life + Larger than Life

Post by Axaj » July 26th, 2010, 12:22 pm

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

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

Re: Rule Tables + Weighted Life + Larger than Life

Post by calcyman » July 26th, 2010, 2:27 pm

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.
What do you do with ill crystallographers? Take them to the mono-clinic!

jks
Posts: 8
Joined: July 22nd, 2010, 2:39 pm

Re: Rule Tables + Weighted Life + Larger than Life

Post by jks » July 27th, 2010, 5:34 am

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.

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

Re: Rule Tables + Weighted Life + Larger than Life

Post by calcyman » July 27th, 2010, 9:55 am

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 = 8).

Simple in principle, but it would take a lot of re-wiring before Golly can handle this.
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
iconmaster
Posts: 42
Joined: July 2nd, 2009, 7:22 pm

Re: Rule Tables + Weighted Life + Larger than Life

Post by iconmaster » August 16th, 2010, 11:29 am

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
Posts: 343
Joined: June 18th, 2010, 8:18 pm

Re: Rule Tables + Weighted Life + Larger than Life

Post by 137ben » August 16th, 2010, 8:15 pm

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.

User avatar
ssaamm
Posts: 125
Joined: June 4th, 2010, 9:43 pm

Re: Rule Tables + Weighted Life + Larger than Life

Post by ssaamm » August 17th, 2010, 9:00 am

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.

User avatar
iconmaster
Posts: 42
Joined: July 2nd, 2009, 7:22 pm

Re: Rule Tables + Weighted Life + Larger than Life

Post by iconmaster » August 17th, 2010, 5:11 pm

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
Posts: 111
Joined: May 19th, 2010, 7:35 am
Location: Cambridge, UK

Re: Rule Tables + Weighted Life + Larger than Life

Post by Paul Tooke » August 17th, 2010, 7:47 pm

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
Posts: 232
Joined: September 26th, 2009, 12:23 am

Re: Rule Tables + Weighted Life + Larger than Life

Post by Axaj » August 17th, 2010, 9:39 pm

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

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

Re: Rule Tables + Weighted Life + Larger than Life

Post by calcyman » August 18th, 2010, 6:41 am

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?
What do you do with ill crystallographers? Take them to the mono-clinic!

Axaj
Posts: 232
Joined: September 26th, 2009, 12:23 am

Re: Rule Tables + Weighted Life + Larger than Life

Post by Axaj » August 18th, 2010, 10:10 am

calcyman 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!
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?
Image

137ben
Posts: 343
Joined: June 18th, 2010, 8:18 pm

Re: Rule Tables + Weighted Life + Larger than Life

Post by 137ben » August 18th, 2010, 10:30 am

Do rule tables/trees run in Hashlife?
No, I don't think so.

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

Re: Rule Tables + Weighted Life + Larger than Life

Post by calcyman » August 18th, 2010, 12:41 pm

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.
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
Andrew
Moderator
Posts: 765
Joined: June 2nd, 2009, 2:08 am
Location: Melbourne, Australia
Contact:

Re: Rule Tables + Weighted Life + Larger than Life

Post by Andrew » August 18th, 2010, 7:54 pm

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.

Post Reply