Clickmazes - ilife

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

Applet-runner plugin required

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?