Search Larger Rule Spaces

The 256 elementary rules are small enough to enumerate.

Most interesting cellular-automata design spaces are not.

Add more states, a larger neighborhood, continuous parameters, or several channels and exhaustive search quickly becomes impossible.

So we need search strategies.

Why the rule space explodes

For k possible cell states and a neighborhood containing n cells, there are:

k^n possible neighborhood configurations

A deterministic rule chooses one of k outputs for every configuration, giving:

k^(k^n) possible rules

(This is the general counting law behind Chapter 3’s 2^8 = 256.)

For elementary CA:

k = 2
n = 3
2^(2^3) = 256

Increase the neighborhood to five cells:

2^(2^5) = 4,294,967,296

Enumeration is already unattractive.

Parameterized rules

One way to make a huge rule space tractable is to define a lower-dimensional family.

For a totalistic binary rule, the next state might depend only on the number of active neighbors:

def totalistic_step(active_neighbors, birth_counts, survive_counts, alive):
    if alive:
        return int(active_neighbors in survive_counts)
    return int(active_neighbors in birth_counts)

Instead of specifying every neighborhood separately, we search sets of counts.

This introduces inductive bias, but also makes exploration manageable. The Life-like family of Chapter 8 is exactly such a parameterization: 262,144 rules instead of the 2^512 possible lookup tables over a nine-cell Moore neighborhood.

Random search

The simplest strategy is often underrated:

def random_rules(sample_rule, evaluate, trials, seed=42):
    rng = np.random.default_rng(seed)
    results = []

    for _ in range(trials):
        rule = sample_rule(rng)
        score = evaluate(rule)
        results.append((score, rule))

    return sorted(results, reverse=True)

Random search provides a baseline.

Any clever strategy should beat it under an equal evaluation budget.

Local mutation search

Start from a promising rule and perturb it:

def mutate_bits(genome_bits, rng, flips=1):
    child = genome_bits.copy()
    positions = rng.choice(len(child), size=flips, replace=False)
    child[positions] ^= 1
    return child

Then keep a child if it improves the objective.

parent
  ↓ mutate
child
  ↓ evaluate
better? -> keep
worse?  -> reject

This is hill climbing over rule space.

Novelty instead of a fixed objective

Sometimes we do not know what behavior we want.

Then search for rules that are behaviorally different from those already seen — the novelty-search program of Lehman and Stanley (2011), who showed that abandoning fixed objectives can find behaviors that objective-driven search never reaches.

Represent each run using the fingerprint keys from previous chapters:

vector = np.array([
    metrics["mean_density"],
    metrics["mean_change"],
    metrics["mean_entropy"],
    metrics["compression_ratio"],
    metrics["tail_activity"],
])

(All five keys exist in the extended record built in the previous chapter — fingerprint plus entropy and compression columns.)

A simple novelty score is distance to the nearest archived behaviors:

def novelty(candidate, archive):
    if not archive:
        return float("inf")
    return min(np.linalg.norm(candidate - old) for old in archive)

The loop, with the archive as accumulating memory:

    flowchart LR
    C[candidate rule] --> V[behavior vector]
    V --> N[distance to nearest archived behavior]
    N --> A{novel enough?}
    A -->|yes| K[keep + add to archive]
    A -->|no| D[discard]
    K --> C
  

Now search rewards new kinds of behavior rather than one predefined target — with the guardrails Part III has earned:

novel
  ≠ useful

diverse
  ≠ high quality

far apart in rule encoding
  ≠ far apart in behavior

That last line has a demonstration inside this book: Chapter 3’s mirror and complement equivalences put behaviorally identical rules at distant rule numbers. Distance in genotype space never implied distance in behavior space; novelty search works precisely because it measures in behavior space instead.

The three strategies side by side — different questions, different failure modes:

Cache evaluations

Search repeatedly revisits candidates.

Do not rerun deterministic experiments unnecessarily.

cache = {}


def cached_evaluate(rule_key, evaluate):
    if rule_key not in cache:
        cache[rule_key] = evaluate()
    return cache[rule_key]

For stochastic rules, cache by the complete experiment identity:

rule
seed
initial condition
world size
number of steps
metric version

This turns reproducibility into a performance feature.

Search needs budgets

Make the resource limit explicit:

MAX_EVALUATIONS = 10_000

Then compare algorithms under the same budget.

Without this, a more expensive search strategy can appear better simply because it performed more simulations.

Search is now part of the subject

Once rule spaces become large, the object of study is no longer only:

cellular automaton

It is:

rule representation
    +
simulator
    +
measurements
    +
search strategy
    +
selection criterion

That architecture will carry directly into continuous and learned cellular automata later in the book.

In the next chapter we will turn local mutation into a full evolutionary search process and evolve rules toward explicit behavioral goals.

Research

• Lehman, J. & Stanley, K. O. — Abandoning Objectives: Evolution through the Search for Novelty Alone (Evolutionary Computation 19(2), 2011). The foundation for this chapter’s novelty section: objective-driven search gets trapped by deception, while rewarding behavioral novelty finds what fixed scores miss. Read before assuming a higher score means a better rule. https://dl.acm.org/doi/10.1162/EVCO_a_00025

• Zenil, H. & Martinez, G. J. — Cellular Automata (Scholarpedia). Backs the chapter’s counting and scoping: the general rule-table combinatorics behind the explosion argument, and the finite-observation limits that make caching by full experiment identity necessary rather than tidy. http://www.scholarpedia.org/article/Cellular_automata