AIC > Neil Yorke-Smith > Research > Still Life

Maximum Density Still Life

This page was last updated in 2007. Subsequently, Chu and Stuckey thoroughly analyzed the problem, finding optimal solutions up to size 69*69 in 2009, and then proving that all maximum-density still life problems can be solved in constant time (PDF) in 2012. This surprising breakthrough required deep analysis and powerful bounds and search.

For an accessible introduction to the problem, see Chu, G.; Petrie K. E.; and Yorke-Smith, N. Constraint Programming to Solve Maximal Density Still Life. In: Adamatzky, A. (ed). Game of Life Cellular Automata. Springer, 2010.

Here is a collated summary of all the results I know (as of 2007) for the maximum density still life problem.

[ Problem Statement | Results | Rotational Symmetry | Bilateral Symmetry | Bibliography ]

    ..OO.OO..
    .O.O.O.O.
    O..O.O..O
    OOOO.OOOO
    .........
    OOOO.OOOO
    O..O.O..O
    .O.O.O.O.
    ..OO.OO..    
A maximal density rotationally symmetric still life of size 9

Problem Statement

In a given, finite region of the board, construct a maximum density still life, i.e. a pattern that does not change from one generation to the next. We restrict our attention to square boards of size n. Note the still life need not be connected (a `pseudo still life' in some terminologies); a still life is also known as a `stable pattern'.

Results: Main Case

In the results tables, density for size n refers to the value of the maximal pattern divided by n*n; external density is the value divided by (n+1)*(n+1), i.e. the external board. Solutions denotes the number of non-symmetric solutions; the number of total solutions is in parenthesis. Times are approximate and for indication only, and show the time to determine the optimal value with the current best-known method.

Size Value Density (external) Solutions (total) Time (s) Reference Date (proved optimal) Remarks
1 0 0.0000 (0.0000) - - - -
2 4 1.0000 (0.4444) 1 (1) - - -
3 6 0.6667 (0.3750) 1 (2) - - -
4 8 0.5000 (0.3200) 2 - - -
5 16 0.6400 (0.4444) 1 (1) - - -
6 18 0.5000 (0.3673) 9 (48) - [14] September 1992 Attributed to Harold McIntosh
7 28 0.5714 (0.4375) 1 (2) - [14] September 1992 Attributed to Harold McIntosh
8 36 0.5625 (0.4444) 1 (1) - [1] May 1999
9 43 0.5309 (0.4300) 10 (76) - [1] May 1999
10 54 0.5400 (0.4463) >100 (3590) - [1] May 1999
11 64 0.5289 (0.4444) 1? (73) - [3] December 2001 First novel result by hybrid CP-IP
12 76 0.5278 (0.4497) ? (129126) - [3],[11] December 2001 Number of solutions by bucket elimination
13 90 0.5325 (0.4592) ? (1682) 2 [3] December 2001
14 104 0.5306 (0.4622) >1 (11) 2 [5] January 2002
15 119 0.5289 (0.4648) ? 58 [5] February 2002
16 136 0.531 (0.4710) ? 7 [11] July 2003 First novel result by hybrid BE
17 152 0.526 (0.469) ? 1090 [11] July 2003
18 171 0.528 (0.474) ? 2030 [11] July 2003
19 190 0.526 (0.475) ? 56020 [11] July 2003
20 210 0.525 (0.476) ? 200000 [11] July 2003
(These results last updated 04aug03.)  Top

    OO..OO.OO.O.OO.OO.OO
    O..O.O.O.OOO.O.OO.O.
    .O.O.O.O.....O.....O
    OO.O.O.OOOOOO.OOOOOO
    .O.O.O......O.O.....
    O..O.OOOOOO.O.O.OOOO
    OOOO......O.O.O.O..O
    ....OOOOO.O.O.O.O.O.
    OOOO....O.O.O.O.O.OO
    O..O.OO.O.O.O.O.O.O.
    .O.O.O.O.O.O.OO.O..O
    OO.O.O.O.O.O....OOOO
    .O.O.O.O.O.OOOOO....
    O..O.O.O.O......OOOO
    OOOO.O.O.OOOOOO.O..O
    .....O.O......O.O.O.
    OOOOOO.OOOOOO.O.O.OO
    O.....O.....O.O.O.O.
    .O.OO.O.OOO.O.O.O..O
    OO.OO.OO.O.OO.OO..OO
A maximal density still life of size 20 (due to Larrosa et al)

Rotationally Symmetric Case

First, with 90 degree rotational symmetry. Times are approximate and for indication only, and show the time to determine the optimal value with the method that first solved the instance.

Size Value Density (external) Solutions Time (s) Reference Date (proved optimal) Remarks
1 0 0.0000 (0.0000) - - - -
2 4 1.0000 (0.4444) 1 - - - Identical to main case
3 4 0.4444 (0.2500) 1 - - -
4 8 0.5000 (0.3200) 1 - - - Unique, unlike main case
5 16 0.6400 (0.4444) 1 - - - Identical to main case
6 18 0.5000 (0.3673) 1 - - - Unique, unlike main case
7 28 0.5714 (0.4375) 1 - - - Identical to main case
8 36 0.5625 (0.4444) 1 2 [1] May 1999 Identical to main case
9 40 0.4939 (0.4000) ? ? ?
10 52 0.5200 (0.4298) ? ? ?
11 64 0.5289 (0.4444) 1? ? ? Identical to main case
12 76 0.5278 (0.4497) ? ? ? Value as main case
13 88 0.5207 (0.4490) ? ? [1] May 1999
14 104 0.5306 (0.4622) ? ? ? Value as main case
15 116 0.5156 (0.4531) ? ? [1] May 1999
16 136 0.5313 (0.4706) ? ? ?
17 148 0.5121 (0.4568) ? ? ?
18 168 0.5185 (0.4653) >1 19,900 [15] January 2002
19 188 0.5208 (0.4700) ? 3,860 [17] April 2002
20 208 0.5200 (0.4717) ? 11,500 [17] April 2002
21 232 0.5261 (0.4793) ? 33,500 [17] April 2002
22 252 0.5207 (0.4764) ? 98,300 [17] April 2002
23 276 0.5217 (0.4792) ? 332,000 [17] September 2002
24 >295 ? ?
(These results last updated 23oct02.)  Top

Second, with 180 degree rotational symmetry (all results up to size 16 due to Bob Bosch):

Size Value Density (external) Solutions Time (s) Reference Date (proved optimal) Remarks
10 54 0.5400 (0.4463) ? ? [6] October 2002
11 64 0.5289 (0.4444) 1? ? [6] October 2002 Also has 90 degree rotational
12 76 0.5278 (0.4497) ? ? [6] October 2002 Value as main case
13 90 0.5325 (0.4592) ? ? [6] October 2002
14 104 0.5306 (0.4622) ? ? [6] October 2002 Value as main case; also has 90 degree
15 119 0.5289 (0.4648) ? ? [6] October 2002
16 136 0.5313 (0.4706) ? ? [6] October 2002 Value as 90 degree rotational
17 152 0.5260 (0.4691) ? 1,000,000 [17] November 2002
(These results last updated 27nov02.)  Top

    OO.OO.OO.O.OO.O.OO.OO.O
    .O.OO.O.OOO.O.OO.O.O.OO
    O.....O.....O....O.O...
    OOOOOO.OOOOO.OOOOO.O.OO
    .....O.O...O.O.....O.OO
    OOOO.O..OO.O.O.OOOOO...
    O..O.OO.O.O.O.O.O...OOO
    .O.O.O..O.O.O.O...OO..O
    OO.O..OOO.O.O.OOOO.O.O.
    ...OOO...O.O.O...O.O.OO
    OOO...OOO..O..OOO..O.O.
    O..OOO...OO.OO...OOO..O
    .O.O..OOO..O..OOO...OOO
    OO.O.O...O.O.O...OOO...
    .O.O.OOOO.O.O.OOO..O.OO
    O..OO...O.O.O.O..O.O.O.
    OOO...O.O.O.O.O.OO.O..O
    ...OOOOO.O.O.OO..O.OOOO
    OO.O.....O.O...O.O.....
    OO.O.OOOOO.OOOOO.OOOOOO
    ...O.O....O.....O.....O
    OO.O.O.OO.O.OOO.O.OO.O.
    O.OO.OO.O.OO.O.OO.OO.OO
A maximal density 90 degree rotationally symmetric still life of size 23

Bilaterally Symmetric Case

With horizontal (or vertical, but not necessarily both) symmetry.

Size Value Density (external) Solutions (total) Time (s) Reference Date (proved optimal) Remarks
1 0 0.0000 (0.0000) - - - -
2 4 1.0000 (0.4444) 1 (1) - - - Identical to main case
3 4 0.4444 (0.2500) 1 (1) - - -
4 8 0.5000 (0.3200) 1 - - - Unique, unlike main case
5 16 0.6400 (0.4444) 1 - - - Identical to main case
6 16 0.4444 (0.3265) ? - - -
7 26 0.5306 (0.4063) ? - - -
8 36 0.5625 (0.4444) 1 2 - - Identical to main case
9 43 0.5309 (0.4300) 1 51 - - Unique, unlike main case
10 52 0.5200 (0.4298) ? (133) 4.5 [10] -
11 64 0.5289 (0.4444) 1? 373 [3] December 2001 Identical to main case
12 76 0.5278 (0.4497) ? (8) 30,360 [10] -
13 90 0.5325 (0.4592) ? ? - -
14 104 0.5306 (0.4622) 1 ? [3],[10] December 2001 Value as main case
15 119 0.5289 (0.4648) ? ? [3] December 2001 Value as main case
16 136 0.5313 (0.4706) ? (3) ? [3] December 2001
17 152 0.5260 (0.4691) ? ? [3] December 2001 Greater than rotational case
18 170 0.5247 (0.4709) ? (4) ? [3],[10] December 2001 Greater than rotational case
19 189 0.524 (0.472) ? ? [11] July 2003
20 208 0.52 (0.4717) ? (1813) ? [10] March 2003 First novel result by bucket elimination
21 232 0.526 (0.479) ? ? [11] July 2003
22 252 0.5207 (0.4764) ? (635) ? [10] March 2003
23 ? ? (?) ? ? -
24 300 0.5208 (0.48) ? (5363) ? [10] March 2003
25 ? ? (?) ? ? -
26 350 0.5178 (0.4801) ? (55246) ? [10] March 2003
27 ? ? (?) ? ? -
28 406 0.5179 (0.4828) ? (12718) ? [10] March 2003
(These results last updated 04aug03.)  Top

    O.OO.OO.O.OO.OO.OO.O.OO.OO.O
    OO.O.O.OOO.O.OO.O.OOO.O.O.OO
    ...O.O.....O....O.....O.O...
    OO.O.OOOOOO.OOOO.OOOOOO.O.OO
    OO.O......O.O..O.O......O.OO
    ...OOOOOO.O.O..O.O.OOOOOO...
    OOO.....O.O.OOOO.O.O.....OOO
    O..OOOO.O.O......O.O.OOOO..O
    .O.O..O.O.OOOOOOOO.O.O..O.O.
    OO.O..O.O..........O.O..O.OO
    .O.OOOO.OOOOOOOOOOOO.OOOO.O.
    O......O............O......O
    OOOOOO.O.OOOOOOOOOO.O.OOOOOO
    .....O.O.O........O.O.O.....
    OOOO.O.O.O.OOOOOO.O.O.O.OOOO
    O..O.O.O.O.O....O.O.O.O.O..O
    .O.O.O.O.O.O.OO.O.O.O.O.O.O.
    OO.O.O.O.O.O.OO.O.O.O.O.O.OO
    ...O.O.O.O.O....O.O.O.O.O...
    OOOO.O.O.O.OOOOOO.O.O.O.OOOO
    O....OO.O.O......O.O.OO....O
    ..OOO...O.O.OOOO.O.O...OOO..
    .OO..OOOO.O.O..O.O.OOOO..OO.
    O...O.....O.O..O.O.....O...O
    OOOO.OOOOOO.OOOO.OOOOOO.OOOO
    ...O.O.....O....O.....O.O...
    OO.O.O.OOO.O.OO.O.OOO.O.O.OO
    O.OO.OO.O.OO.OO.OO.O.OO.OO.O
A maximal density bilaterally symmetric still life of size 28 (due to Larrosa et al)

Bibliography

  1. R. Bosch, Integer Programming and Conway's Game of Life. SIAM Review 41(3), 596-604, (1999). Online
  2. R. Bosch, Maximum Density Stable Patterns in Variants of Conway's Game of Life. Operations Research Letters 27(1), 7-11, (2000). PDF
  3. R. Bosch and M. Trick, Constraint Programming and Hybrid Formulations for Life. Proceedings of Formul'01 Workshop, CP'01, (2001). Postscript
  4. R. Bosch and M. Trick, Constraint Programming and Hybrid Formulations for Three Life Designs. Proceedings of CP-AI-OR'02, 77-91, (2002). PDF
  5. R. Bosch and M. Trick, CP/IP Life page.
  6. R. Bosch, private communication, October 2002.
  7. M. Cook, Still Life Theory. New Constructions in Cellular Automata, 93-118, OUP (2003). Postscript.
  8. N. D. Elkies, The still-life density problem and its generalizations. Voronoi's Impact on Modern Science, Book I, 228-253, (1998). Online
  9. I. Gent, T. Walsh and B. Selman, CSPlib problem 32.
  10. J. Larrosa and E. Morancho, Solving 'Still life' with Soft Constraints and Bucket Elimination. Proceedings of CP'03, 466-479, (2003). Postscript | Online.
  11. J. Larrosa, E. Morancho and D. Niso, On the Practical Use of Bucket Elimination: 'Still life' as a Case Study. JAIR 23:421--440. PDF.
  12. M. D. Niemiec, Mark D. Niemiec's Life Page.
  13. K. Petrie, B. Smith and N. Yorke-Smith, Dynamic Symmetry Breaking in Constraint Programming and Linear Programming Hybrids. APES Technical Report 81, (2004). Proceedings of STAIRS'04, Valencia, Spain, August 2004. Online.
  14. S. Silver, Dense Stable Patterns.
  15. B. M. Smith, A Dual Graph Translation of a Problem in 'Life'. Proceedings of CP'02, 402-414, LNCS 2470, (2002). Postscript | Online
  16. E. Weisstein, Density, Eric Weisstein's Treasure Trove of Life C.A.
  17. N. Yorke-Smith, Symmetric Still Life with a Hybrid Model. Working paper, IC-Parc (2002).
  18. Kenil C.K. Cheng and Roland H.C. Yap, Search Space Reduction and Russian Doll Search. AAAI'07.


Top | Home