|
|
One of the earliest yet most difficult challenges to date has been that of world domination. From an arbitrary start, such asY-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:
Load: SS<U<D>U<SSSU/D
Find: world-domination in 4 moves
Note: this challenge has been pre-loaded for you, just
click on the grid to move the blue cell.
Controls Movement Keys |
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.