Clickmazes - ilife

Maze of Life - World domination

One of the earliest yet most difficult challenges to date has been that of world domination. From an arbitrary start, such as Y-start, is it possible to clear the board leaving the blue-cell the last and only cell left alive?

World domination is possible, but it took a computer search to prove it, find out more below. Alternatively discover world domination for yourself using this mini-challenge.

Mini challenge

From: Y-start
After: SS<U<D>U<SSSU/D
Find: world-domination in 4 moves

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

world domination

MAD or what?

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

For many months world domination remained an unsolved challange, but in March 2001 Jacco Compier proved by computer search that world domination was possible, in as little as 15 moves. A convincing vindication that world domination is probably possible from almost any start-state that the blue-cell can 'escape' from. Here is a selection of the shortest known solutions for world-domination from Y-start. x,y indicates the final resting place of the blue-cell.

Solution	Length	x,y
USS\D\UD/SSS>SD	15	4,3
SS<U<D>U<SSSU/D>\UD	19	3,6
SS<U<DS/D/</S<UL\/R	19	3,3
SS<U<DURSLSRS//D\>D	19	5,5
SS<U<DURURRD\URR/SL	19	6,2
SS<U<DURUR/<LS>\SD	18	3,5

And here are some slightly longer solutions that all end with the blue-cell back in the centre (4,4).

SS<U<D>US>/UL\SUSD</>U
SS<U<D>/D\/SSLD\>/\</R
SS<U<DU>>SUULSSS\RRLR

All these solutions are of course edge-dependent, which is true for many of the challenges posed and solved so far, but having proved world-domination is possible in as few as 15 moves, it is particularly tempting to ask... is world-domination also possible on an infinite board? And if so, what is the minimum size board?

We have shown it is possible for the blue-cell to manouvre itself into the tiniest one-cell state, but one-cell is never going to survive by itself. What is the smallest, indefinitely survivable, state for the blue-cell? Is it those two 4-cell stable-states 4a and 4b we've already seen? No. If the blue-cell is prepared to retire to an oscillator, rather than a stable-state, the minimum is actually 3 cells. If you a familiar with Game of Life, you probably know the 3-cell, 2-step, oscillator I refer too, but can the blue-cell retire to it from Y-start? I feel sure the answer is yes - but I do not know the shortest solution.

Carl Hoff stumbled on several oscillators in his early search for stable-states and we began to collect examples of a brand new type of oscillator which is unique to intelligent-cell life. To find out more see the page on active oscillators.