ConwayLife.com

I haven't been able to find a notation that fully covers this rulespace, so I've decided to make one myself.

The specification of the rulestring is as follows:
neighborhood,symmetry,transitions

neighborhood - The cells considered around the current cell when deciding what its next state will be. Valid symbols are 0, which represents a cell not being included in the neighborhood, 1, which represents a cell being included, and x, which represents the neighborhood's center cell. The neighborhood will be bound by a square, so the number of valid symbols in a neighborhood representation must be a perfect square. The neighborhood representation will be read from left to right, than up to down within the bounding square. The symbol x may only occur once in the neighborhood string (what would multiple center cells for a neighborhood even look like?). Any symbols other than those already specified will be ignored.

symmetry - Which symmetries will be respected by the transitions. These will affect how transitions is laid out, which will be elaborated upon later. Valid symmetries are C1, C2, C4, D2+, D2x, D4+, D4x, D8, and totalistic. For a symmetry to be allowed, the neighborhood surrounding the center cell must respect that symmetry. In the case of totalistic, the neighborhood must respect C1 symmetry, and the center cell is not included (so it is specifically outer-totalistic).

transitions - Which configurations of cells within a neighborhood correspond to a change in the center cell's state. Transitions will be represented in a similar way to MAPrule notation: each transition is listed in numerical order. As the cell configuration is encoded implicitly, only the state the cell changes to needs to be listed per transition.

The presence of a non-C1 symmetry will change the transition representation as such: only the first instance of a given configuration will be included in the transition list, any equivalent configurations in the given symmetry that would ordinarily occur later in the list will not appear. This serves to significantly cut down on the length of the rulestring when symmetries appear.

Since this rulespace is so large, there will be a great number of transitions for any given neighborhood, meaning the rulestring will be similarly large. Because of this, the transition list will be subject to run-length encoding. As such, numerals can't be used to represent a state, so letters will be used instead. The letter representation for a state may be any length, but must begin with a capital letter, which unambiguously will demark a separate state from the previous letter.

This format could produce vary large files for anisotropic rules with a large neighbourhood (>~12 cells). One possible solution is to switch from writing the transitions in a base-n encoding for n state rules to a base 64 encoding. For example, using base 64 to encode a 3 state rule could reduce the file size by ~75%. It could be done by treating the list of transitions as a base n number which is converted to base 64, and then into ASCII characters.

The resulting string could have pretty high entropy, so RLE wouldn't work that well. Instead the base64 string could be compressed using a scheme like Huffman coding, which is optimal for encoding individual characters.

This way of encoding the transitions should be much more compact, at the cost of using a significantly more complex system.

Additionally, how would one write the neighbourhood for rules with a higher symmetry? If the entire neighbourhood is written out with 0s and 1s, then the symmetry information seems somewhat redundant for the purpose of defining the rule.

silversmith wrote: December 10th, 2022, 6:21 pm Additionally, how would one write the neighbourhood for rules with a higher symmetry? If the entire neighbourhood is written out with 0s and 1s, then the symmetry information seems somewhat redundant for the purpose of defining the rule.

Are you asking why the symmetry isn't automatically determined from the neighborhood? If so, it is so that rules can have a highly symmetric neighborhood and still have configurations that are recognized as distinct from one another that wouldn't be if it were forced to respect the neighborhood's symmetry.

As for encoding, well, I'm not exactly an expert on that, so someone else would have to come up with a specification for something better than what I have here. However, I will say that that RLE encoding may do better than you think for all but the most complicated of rules, as most MAP rulestrings that are shared around here can attest (by which I am referring to the fact that a large proportion of the average rulestring is a long string of the character "A" on repeat).

Cyclotrons wrote: December 10th, 2022, 7:42 pm Are you asking why the symmetry isn't automatically determined from the neighborhood? If so, it is so that rules can have a highly symmetric neighborhood and still have configurations that are recognized as distinct from one another that wouldn't be if it were forced to respect the neighborhood's symmetry.

Ok. Could a rule with a highly symmetric neighborhood have a symmetry such as D4+, and have certain asymmetric transitions transitions? What would a program use the symmetry information for?

silversmith wrote: December 10th, 2022, 9:38 pm

Cyclotrons wrote: December 10th, 2022, 7:42 pm Are you asking why the symmetry isn't automatically determined from the neighborhood? If so, it is so that rules can have a highly symmetric neighborhood and still have configurations that are recognized as distinct from one another that wouldn't be if it were forced to respect the neighborhood's symmetry.

Ok. Could a rule with a highly symmetric neighborhood have a symmetry such as D4+, and have certain asymmetric transitions transitions? What would a program use the symmetry information for?

No. If the symmetry was D4+, all transitions would have to respect D4+ symmetry, but they wouldn't have to respect the higher symmetry of the neighborhood (D8 in this case). The program uses the symmetry information to determine how many transitions are represented by the mapstring, as most of the transitions in a full C1 mapstring would be entirely redundant in a higher symmetry, and thus waste space.

That makes sense, and I think I understand the format now.