Maze of Life - the dense goals

Out of the search for stable-state goals came the question... what are the largest (densest) stables-state cell arrangements on a 7x7 grid, and can these states be manufactured by the blue-cell from an arbitrary start-point, such as the Y-start?



Stable-state cell arrangements are a well-explored topic in standard Game of Life, and a little web searching will soon tell you the limits on a 7x7 grid (see for example Stephen Silver's Dense Stable Patterns). However manufacturing these dense goals from Y-start is not easy. Read more below, or discover some dense stable-state goals for yourself with this mini-challenge:

Load: SS<U<DSR<S//UL/><
Find: a 24-cell stable-state in 4 moves, and then 26-cell in another 2 moves.
Note: this challenge has been pre-loaded for you, just click on the grid to move the blue cell.

Sorry, this is a Java applet.

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

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

u – undo last move.


The densest stable-state cell-arrangements for a standard 7x7 grid are infact 30 cells (edge-dependent) and 28 cells (edge-independent) but it is far from easy to manufacture these goals from Y-start. Jacco Compier's search program found only 5 arrangements with 20+ cells, in a complete search of all goals reachable in 20 moves or less. The longest, and most pleasing perhaps, is this goal: 24 cells in 20 moves. However Jacco Compier did eventually prove than it is possible to manufacture a 30-cell stable-state from the Y-start. Here it is: 30 cells in 37 moves.

If you use undo/redo to explore the last few moves of the above sequences you get a strong sense that the blue-cell is carefully crafting itself a grand retirement home, this blue-cell clearly plans to retire in good company! But what about the loner blue-cell who just wants to die alone? Is this possible? Find out on the world domination page.

We are left with one unsolved challange here. Is it possible for the blue-cell to manufacture that elusive 28-cell edge-independent stable-state from the Y-start? For example:

iLife pages: Maze of life V1 World domination Optimal sequences (new)
  The Y-start challenge Active oscillators Glider gun in 247 (new)
  Stable-state goals Riding the glider iLife play area
  Dense goals  Building a glider gun

material - Andrea Gilbert, Carl Hoff, Jacco Compier
applet - © Andrea Gilbert 2000-2001