Гра Конвея «Життя»: Чотири Правила, Один Універсальний Комп'ютер

Чотири правила, без винятку

Ігри Conway's Game of Life - це клітинна автоматика на нескінченій площині. Кожна клітина або жива, або мертва, і кожна клітина дивиться на своїх вісьмох сусідів (Moore-середовище), щоб вирішити, чи стане вона в наступному поколінні. Все фізика цього всесвіту складається з чотирьох рядків:

жива клітина з 2 або 3 живими сусідами → виживає жива клітина з < 2 живими сусідами → помирає (недостатньо населення) жива клітина з > 3 живими сусідами → помирає (перенаселення) mертва клітина з точно 3 живими сусідами → стає живою (народження) У стандартній нотації це B3/S23: народжується на 3 сусідів, виживає на 2 або 3. Важливо зазначити, що всі клітини оновлюються одночасно з одного моменту часу. Оновіть клітину на місці і ви більше не запускаєте Life — ви запускаєте іншу автоматику, схильну до напрямку. Тому кожна правильна реалізація підтримує два буфери та міняє їх.

live cell with 2 or 3 live neighbours  → survives
live cell with < 2 live neighbours      → dies (underpopulation)
live cell with > 3 live neighbours      → dies (overcrowding)
dead cell with exactly 3 live neighbours → becomes alive (birth)

Зоопарк: незгурства, осцилятори, космічні кораблі

Після кількох сотень поколінь випадковий бульйон розкладається на невелику кількість повторюваних форм. Незгурства ніколи не змінюються: блок (2×2), улукба, хліб, човен. Осцилятори повертаються до свого початкового стану після пе від часу: блимкач (період 2), жабка (період 2), маяк (період 2), пульсар (період 3), пентедекагон (період 15).

Найвідоміший — це слайдер — п’ять клітин, які відтворюють себе по діагоналі кожні чотири покоління, тому вони рухаються зі швидкістю c/4, де c – одна клітина на покоління (максимальна швидкість передачі інформації на сітці). Легкий космічний корабель та його важчі родичі рухаються ортоґонально зі швидкістю c/2. Слайдер має значення, оскільки це рухомий, підрахунковий одиниця інформації: потік слайдерів — це дріт.

. O . слайдер, покоління 0 . . O O O O

. O .        glider, generation 0
. . O
O O O

Чому це Turing-повне

З використанням слайдів як сигналів та статичних композицій як стін, ви можете будувати логіку. Потік слайдів є потоком бітів — наявність слайда в слоті означає 1, відсутність — 0. Два потоки слайдів, що перетинаються під прямим кутом, знищують один одного, що дає вам НЕ-вихід проти посилання з гвинтівки; гвинтівки, споживачі (статичні композиції, які поглинають вхідний слайд і відновлюють його) та дзеркала надають AND, OR та розгалуження. Як тільки у вас є універсальний вихідний пристрій плюс спосіб маршрутизувати та затримувати сигнали, у вас є комбінаційна логіка; додайте цикл слайдів як пам'яті, і у вас є послідовна логіка.

Це достатньо для універсальної машини Тюрінга, тому Життя є Turing-повним: будь-яке обчислення, яке може виконати будь-який комп’ютер, цю сітку може виконати. Люди побудували бінарні лічильники, робочу машину Тюрінга, шаблон, який друкує прості числа, і навіть версію Життя, що працює всередині Життя. Наслідок є втручаючим — ніякий загальний шорток не може сказати вам, чи згодом вимикається будь-який заданий шаблон. Це питання еквівалентне проблемі зупинки, і тому нерозв’язне.

Реалізація швидко

Наївна версія складається з двох вкладених циклів та восьми читань сусідніх клітин на комірку: O(w·h) поколінь з великою сталою. Це підходить для полотна 300×200 при частоті 60 кадрів за секунду, і саме те, що робить симуляція на цьому сайті — один Uint8Array для поточної генерації, один для наступної, обмінюються кожен крок:

for (let y = 0; y < h; y++) { for (let x = 0; x < w; x++) { const i = y * w + x; 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 torus keeps the branchless inner loop const yy = (y + dy + h) % h, xx = (x + dx + w) % w; n += cur[yy * w + xx]; } next[i] = n === 3 || (n === 2 && cur[i]) ? 1 : 0; } } [cur, next] = [next, cur]; // never update in place

Два простих прискорення. Перше — біт-паралельна оцінка: запакуйте 32 або 64 клітин в одне ціле число та обчислюйте суму сусідніх клітин для цілого слова одночасно за допомогою зсувів і невеликої ланцюжка півдодавачів. Це добре відома техніка підсумовує три горизонтальні сусідні клітини на рядку в два бітплани та потім поєднує три рядки, оцінюючи B3/S23 для 64 клітин з приблизно двадцятью бітовими операціями — перемога 20–50 разів над арифметикою на комірку, точний коефіцієнт залежить від ЦП та шаблону.

Друге — пропускати порожні простір. Більшість великої дошки спочатку неактивна, тому відстежуйте, які плитки змінилися в попередньому поколінні і лише перераховуйте ці плитку та їхніх безпосередніх сусідів. Це само по собі робить інтерактивними дошки з мільйонів клітин.

for (let y = 0; y < h; y++) {
  for (let x = 0; x < w; x++) {
    const i = y * w + x;
    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 torus keeps the branchless inner loop
        const yy = (y + dy + h) % h, xx = (x + dx + w) % w;
        n += cur[yy * w + xx];
      }
    next[i] = n === 3 || (n === 2 && cur[i]) ? 1 : 0;
  }
}
[cur, next] = [next, cur];   // never update in place

HashLife та візерунок, який стає швидшим з часом

Ідея HashLife (1984) від Білла Госпера є зовсім іншою. Він зберігає дошку як квадродерево: вузол розміром 2ⁿ має чотири нащадків розміром 2ⁿ⁻¹. Вузли хеш-з'єднані — ідентичні піддерева зберігаються лише один раз, і для кожного вузла алгоритм запам’ятовує результат просування його центру на 2ⁿ⁻² поколінь.

Оскільки Life детермінований та локальний, цей запис можна використовувати будь-де, де з'являється однакова підвізерка, як у просторі, так і в часі: гарматний візерунок періоду 30 повторюється, нерухома візерунка повторюється, порожня область повторюється. Успішні попадання кешу дозволяють HashLife робити величезні стрибки вперед, а його час виконання вимірюється за допомогою пошуків у кеші, а не за клітинами. Дуже регулярні візерунки можуть бути просунуті на 2⁶⁴ поколінь за секунду – що жоден цикл з переглядом по клітинах не може досягти. Однак є й компроміси: таблиця записів росте без обмежень (її потрібно виганяти), неможливо дешево спостерігати кожне проміжне покоління, і на хаотичній, неповторюваній суміші кеш майже не потрапляє, що робить HashLife повільнішим за щільний бітпаралельний цикл. Тому інтерактивні полотна, такі як те, що знаходиться на цій сторінці, залишаються з підходом до біт-дошки.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Game of Life і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.