## Maze of Life - Stable state goals

The Y-start challenge introduced the idea of using stable-state cell arrangements as an alternative goal for Maze of Life. As goals go, the stable-states are certainly a rather more appropriate (life-orientated) choice. The inevitable question then arises... just how many stable-states can the blue-cell manufacture from an arbitrary start state, such as Y-start?

#### Mini challenge

It turns out that the blue-cell is really quite good at generating stables-states. The stable-state goal illustrated on the right is reachable in 4 moves from Y-start.

Discover a stable-state goal for yourself with this mini-challenge:

**From**: Y-start

**After**: SS<U<D>US/RS>/S

**Find**: a 14 cell stable-state (edge-dependent)
goal in 4 moves

This challenge has been pre-loaded, just click on the grid to move the blue cell.

from Y-start in 4

#### Controls

Click on **Edit** to set up a start position.

Click on **Play** to switch to play mode or to restart.

Use **Undo/redo** to replay previous moves (play mode only).

Click on **Load** to verify and rerun the move sequence in
the text box (play mode only).

#### Movement

In **Edit** mode click on the **grid** to toggle cell status
(black/blue/empty).

In **Play** mode click on the **grid** to move.

#### Keys

**u** - undo last move

#### Findings

Carl Hoff illustrated early on that a good number of stables-states
are indeed reachable from Y-start. An early collection can be
seen here. It includes stable-state
goals with 4 through 12 cells
(some free-standing, some edge-dependent)
along with several multi-cluster arrangements. However, due to
the limitations of the early V2 applet it was not easy to save
and load move sequences and some were lost along the way, so
for almost a year the collection included a number of *lost
goals*. Eventually in March 2001 the gaps were filled by a
Delphi search program written by Jacco Compier. Jacco's search
program rapidly proved that our hand-crafted collection of goals
was only a tiny subset of possible state-states reachable from
Y-start. The move sequences of all stables-states reached in
20 moves or less is listed here.

One of the findings that came out of the early manual searches
was that it was really quite easy to drop into a stable-state
almost by accident, and often this was bad news for the blue-cell.
Effectively the stable-states fall into two catagories, the *escapable*
and the *inescapable*. Inescapable stable-states are another
sort of dead-end. In effect the blue-cell doesn't have to die
in Maze of Life, it may simply be forced to *retire*, infact
Ed Pegg referred to all such states as *retirement-homes*.

It is worth noting that Jacco's list of stables-states (from Y-start in 20 moves) includes very few high-order stable-states, only 5 results with 20 or more cells. Carl Hoff once asked..."How many live cells can you put in a stable state on the board at once? I can put 30. Now require it be non-edge based. I can put 24. My gut tells me that 24 is the max in this case. Note if you could put 25 then the density of live cells would be above 50% and I think you can prove you can't do that on an infinite board. I'm not sure if 30 is the max in the other case or not". Is Carl right? Find out more on the Dense goals page.

Some remaining questions relating to stable-states:

Are *all* stable-state goals reachable from Y-start?

If yes... is it provable, and is this true for any size board?

If not... would another start do better?

Another way of looking at these question is to ask... given the global set of Life stable-states is it possible for the blue-cell to manufacture any stable-state from at least one other stable-state? Ie. is the behaviour of the blue-cell sufficiently powerful to create a connected tree of all stable-states?

**applet** - © Andrea Gilbert 2000-2002

**material & challenges** - Andrea, Carl Hoff, Jacco Compier

**applet JS conversion** - cheerpj transpiler from Leaning Technologies - 2020