Conway's Game of Life

1. Origin and Conway

Ідею клітинних автоматів запропонував Джон фон Нейман у 1940-х роках: він шукав математичну модель самовідтворюваних машин. Його автомат мав 29 станів і тисячі правил. Конвей поставив собі завдання: знайти найпростіші правила, при яких самовідтворення залишається можливим.

Після кількох років ігор у го та пентаміно на аркушах паперу (буквально: клітини на папері в клітинку), Конвей у 1970 р. опублікував правила в колонці Мартіна Ґарднера «Mathematical Games» у Scientific American. Реакція — 100 000 листів читачів за тиждень. Гра Життя стала першим вірусним математичним явищем.

2. Four rules

Сітка: двовимірна решітка клітин. Кожна клітина або жива (1) або мертва (0). Сусіди — 8 клітин Мура (включно з діагональними). На кожному кроці всі клітини змінюються одночасно:

У нотації Голлі-Воффінгтона ці правила записуються як B3/S23: Birth при 3 сусідах, Survival при 2 або 3. Ця нотація дозволяє лаконічно задавати будь-які варіанти правил.

3. Grid and boundary conditions

Реальна сітка завжди скінченна — потрібно визначити поведінку на краях. Основні варіанти:

• Торична (wrapped) — ліво-правий та верхньо-нижній краї з'єднуються. Патерни можуть перетікати через межу. Найпоширеніший вибір для симуляцій.
• Мертві краї (dead boundary) — клітини за межами сітки вважаються мертвими. Патерни «відбиваються» від країв смертю.
• Нескінченна сітка — теоретична модель. На практиці реалізується через HashLife або sparse representation.

Для великих симуляцій (мільйони клітин) використовують алгоритм HashLife (Билл Ґосперт, 1984): зберігає квадтрічну ієрархію блоків з кешуванням повторюваних конфігурацій. Дозволяє симулювати 2^(n-1) кроків за O(n) часу — теоретично мільярди поколінь за секунду.

4. Patterns: still lifes, oscillators, spaceships

За 50+ років спостережень спільнота каталогізувала тисячі патернів. Основні класи:

Глайдер — емблема хакерів

Глайдер — найвідоміший патерн: 5 клітин, що рухаються діагонально зі швидкістю c/4 (1 клітина за 4 покоління). Він став символом хакерської культури — нашивкою, татуюванням і «прапором» open-source спільноти після пропозиції Релі Менорта.

Гармата Госпера

Білл Госпер у 1970 р. знайшов першу гармату: 36-клітинний патерн, що генерує глайдер кожні 30 поколінь — нескінченно. Це було доказом того, що популяція може зростати нескінченно, чим відповідало на поставлену Конвеєм задачу.

5. Turing completeness

У 1982 р. Госпер та інші побудували у Грі Життя повний комп'ютер: логічні вентилі AND, OR, NOT з поєднання гармат і відбивачів. У 2002 р. демонстрували повноцінну машину Тюрінга. Існують реалізації Game of Life всередині Game of Life.

Ключовий елемент — «глайдерний логічний вентиль»: глайдер, що влучає в правильне місце, спрацьовує як сигнал 1; відсутність глайдера — сигнал 0. Часова затримка між глайдерами — «такт» процесора.

6. Rule variants

Змінивши правило B3/S23, отримуємо зовсім інші «всесвіти». Деякі цікаві:

• HighLife (B36/S23) — B3/S23 плюс народження при 6 сусідах. Має власну «репліцируючу» структуру.
• Day & Night (B3678/S34678) — симетрія жити/мати: «мертве» і «живе» рівноправні. Ті самі патерни існують в двох версіях.
• Seeds (B2/S) — мертве середовище: клітини відразу помирають, але дають бурхливі вибухи.
• Brian's Brain (3 стани) — «вмираючий» проміжний стан. Щипавки і хвилі, схожі на нейрони.
• Wireworld (4 стани) — спеціально для моделювання цифрових схем. Провідники, сигнали, вентилі.

7. Efficient implementation

Naïve implementation

Для кожної клітини перерахувати 8 сусідів, застосувати правило. O(W × H) на крок — для сітки 1000×1000 це 1 000 000 операцій. При 60 FPS — 60 млн на секунду. У JS цілком можливо.

Double buffer

Критично важливо: всі клітини мусять оновлюватися одночасно. Наприклад клітина A зчитує сусіда B, але якщо B вже оновлена — помилка. Рішення: два масиви — поточний (current) і наступний (next). Рахуємо з current, пишемо в next, потім міняємо місцями.

Optimisation via "active cells"

На практиці більшість сітки мертва і незмінна. Tracked-set optimization: відстежуємо тільки клітини, що змінилися або мають живих сусідів. Потужні реалізації типу Golly обробляють трильйони клітин завдяки HashLife.

Bitboard optimisation

Зберігати сітку як масив 64-бітних цілих (по 64 клітини на int64). Підрахунок сусідів — через бітові зсуви. Для ширини W = 1024 потрібно лише 1024/64 = 16 int64 на рядок. Дає ~8x прискорення проти масиву булівських значень.

8. Pseudocode

// Гра Життя — подвійний буфер, торична сітка
const W = 200, H = 200;
let current = new Uint8Array(W * H);
let next    = new Uint8Array(W * H);

function countNeighbors(x, y) {
  let n = 0;
  for (let dy = -1; dy <= 1; dy++) {
    for (let dx = -1; dx <= 1; dx++) {
      if (dx === 0 && dy === 0) continue;
      // Торична межа (wrap around)
      const nx = (x + dx + W) % W;
      const ny = (y + dy + H) % H;
      n += current[ny * W + nx];
    }
  }
  return n;
}

function step() {
  for (let y = 0; y < H; y++) {
    for (let x = 0; x < W; x++) {
      const alive = current[y * W + x];
      const n = countNeighbors(x, y);

      // B3/S23: народження при 3, виживання при 2|3
      if (alive) {
        next[y * W + x] = (n === 2 || n === 3) ? 1 : 0;
      } else {
        next[y * W + x] = (n === 3) ? 1 : 0;
      }
    }
  }
  // Поміняти буфери місцями
  [current, next] = [next, current];
}

// Відмалювання на Canvas 2D
function draw(ctx) {
  const imageData = ctx.createImageData(W, H);
  const data = imageData.data;
  for (let i = 0; i < W * H; i++) {
    const alive = current[i];
    const b = i * 4;
    data[b]   = alive ? 255 : 10;  // R
    data[b+1] = alive ? 255 : 10;  // G
    data[b+2] = alive ? 255 : 10;  // B
    data[b+3] = 255;             // A
  }
  ctx.putImageData(imageData, 0, 0);
}

Ключова оптимізація для веб: використовувати Uint8Array замість звичайного масиву — доступ до TypedArray у 5–10 разів швидший. Для відображення — putImageData замість поклітинного малювання.