Життя (гра)

«Гра́ життя́» — клітинний автомат, винайдений англійським математиком Джоном Конвеєм 1970 року.

Опис гри було опубліковано в жовтневому випуску журналу Scientific American, в рубриці «Математичні ігри» Мартіна Гарднера (Martin Gardner).

Опис

Перегоновий трек. Послідовність зображень створено на Java, потім кожну структуру пофарбовано у свій колір. Кілька низькорівневих структур взаємодіють, щоб забезпечити можливість ще одній структурі «промчати» по замкнутому шляху. Гонщик починає як планер на діагональному відрізку лівого верхнього кута треку. Планер кілька разів відбивається при зіткненнях від інших структур. У нижній частині треку гонщик при зіткненні з іншим планером тимчасово перетворюється на космічний корабель. Гонщик фінішує знову як планер.

Місце дії гри — «всесвіт» — являє собою площину, поділену на клітинки. Кожна клітина може перебувати в одному з двох станів: бути живою або бути мертвою. Клітинка має вісім сусідів. Розподіл живих клітин на початку гри називається першим поколінням. Кожне наступне покоління утворюється на основі попереднього за наведеними нижче правилами.

Правила

якщо в живої клітини два чи три живих сусіди – то вона лишається жити;
якщо в живої клітини один чи немає живих сусідів – то вона помирає від «самотності»;
якщо в живої клітини чотири та більше живих сусідів – вона помирає від «перенаселення»;
якщо в мертвої клітини рівно три живих сусіди – то вона оживає.

Дані правила отримали назву генетичних законів Конвея, вони задовольняють три основні умови:

не має бути жодної початкової конфігурації, для якої існувало б просте доведення можливості необмеженого росту популяції;
мають існувати такі початкові конфігурації, які заздалегідь мають здатність безмежно розвиватися;
мають існувати прості початкові конфігурації, які протягом значного проміжку часу ростуть, зазнають різноманітних змін і закінчують свою еволюцію одним із трьох наступних способів:
1. повністю зникають;
2. переходять у стійку конфігурацію та перестають змінюватися взагалі;
3. виходять у коливальний режим з певним періодом.

Гравець не бере прямої участі у грі, а лише розставляє початкову конфігурацію «живих» клітин, які потім взаємодіють відповідно до правил вже без його участі.

Фігури

Ці прості правила призводять до виникнення величезної кількості різноманітних форм, кожна з яких має дещо спільне з попередньою. На цей час склалася така система їхньої класифікації:

Стійкі фігури: фігури, що лишаються незмінними після кожної ітерації
Періодичні фігури (осцилятори): фігури, стан яких повторюється через деяку кількість поколінь.
Рухливі фігури (космічні кораблі, глайдери або планери): фігури, стан яких повторюється, але з деяким зсувом у просторі.
Гармати: фігури, стан яких повторюється, але кожен цикл вони додатково створюють фігури, що рухаються.
Паротяги: рухливі фігури, які залишають за собою сліди у вигляді стійких або періодичних фігур.
Пожирачі: стійкі (або періодичні) фігури, які можуть при зіткненні з деякими рухливими фігурами зберігати свій стан, знищуючи рухому фігуру.
Довгожителі: фігури, що довго змінюються, перш ніж стабілізуватися (тобто, перетворитися на групу фігур, стан яких постійний чи періодично повторюється)
Розмножувачі: фігури, які зростають квадратично, виробляючи багато копій вторинної фігури, кожна з яких виробляє багато копій третинної фігури.

У грі "швидкістю світла" називають швидкість шахового короля (тобто, зміщення на одну клітинку по горизонталі, вертикалі чи діагоналі). Очевидно, що з такими правилами жодна взаємодія не може передаватися з більшою швидкістю.

Приклади

Незабаром після публікації правил було виявлено кілька цікавих фігур, зокрема: r-пентаміно, глайдер (англ. glider).

Нерухомі фігури

Докладніше: Натюрморт (конфігурація клітинного автомата)

Нерухомі фігури не змінюються з плином часу. Найпростіший приклад нерухомої фігури — блок.

#	#
#	#

Блок

Осцилятори

Докладніше: Осцилятор (конфігурація клітинного автомата)

Осцилятор — фігура, що має певну періодичність. Приклад: лінія з 3-х клітин.

#

Смужка

Планери

Класичний планер

Докладніше: Планер

Планери (англ. glider) — рухомі фігури, які є періодичними, але з кожним циклом руху зміщуються на кілька клітин у певному (зазвичай сталому) напрямку.

Гармата планерів

Докладніше: Гармата (конфігурація клітинного автомата)

Анімація гармати планерів

Спочатку Конвей припускав, що не існує конфігурації, в якій кількість живих клітин збільшуватиметься нескінченно (коли для гри взяти необмежену площину). Він не міг довести це твердження самостійно й запропонував премію за його доведення або спростування. Премію отримала група хакерів під керівництвом Білла Госпера^[en]. Їм знадобилося півтора року, щоб створити фігуру, яка циклічно самовідтворюється й у циклі породжує планери. На жаргоні гри її називали «гарматою, що стріляє планерами»^[1].

Гармата планерів (глайдерна гармата)

Едемський сад

Докладніше: Едемський сад

Приклад Едемського саду

Едемським садом називається таке розташування клітин, у якого не може бути попереднього покоління. Практично для будь-якої гри, стан кліток в якій визначається декількома сусідами на попередньому кроці, можна довести існування садів Едему, хоча побудова конкретної фігури є набагато складнішою.

Див. також

Джерела

↑ Д.А. Шабанов. 9. Моделі на основі клітинних автоматів // Імітаційне моделювання надорганізмових систем в електронних таблицях та R : он-лайн підручник Харківського національного університету імені В. Н. Каразіна. — Batrachos. — Харків, 2021.

Посилання

Golly — симулятор гри «Життя» на SourceForge.net
Нотатник про клітинні автомати [Архівовано 27 березня 2014 у Wayback Machine.]

[batrachos_Cell_Automates-1] Д.А. Шабанов. 9. Моделі на основі клітинних автоматів // Імітаційне моделювання надорганізмових систем в електронних таблицях та R : он-лайн підручник Харківського національного університету імені В. Н. Каразіна. — Batrachos. — Харків, 2021.

[1]