Игра «Жизнь» ( англ. Game of Life) — клеточный автомат , придуманный английским математиком Джоном Конвеем в 1970 году . Это игра без игроков , в которой человек создаёт начальное состояние, а потом лишь наблюдает за её развитием. В игре можно создать процессы с полнотой по Тьюрингу , что позволяет реализовать любую машину Тьюринга .

Правила

• Место действия игры — размеченная на клетки плоскость, которая может быть безграничной, ограниченной или замкнутой.
• Каждая клетка на этой поверхности имеет восемь соседей , окружающих её, и может находиться в двух состояниях: быть «живой» (заполненной) или «мёртвой» (пустой).
• Распределение живых клеток в начале игры называется первым поколением. Каждое следующее поколение рассчитывается на основе предыдущего по таким правилам:
  • в пустой (мёртвой) клетке, с которой соседствуют три живые клетки, зарождается жизнь;
  • если у живой клетки есть две или три живые соседки, то эта клетка продолжает жить; в противном случае (если живых соседей меньше двух или больше трёх) клетка умирает («от одиночества» или «от перенаселённости»).
• Игра прекращается, если
  • на поле не останется ни одной «живой» клетки;
  • конфигурация на очередном шаге в точности (без сдвигов и поворотов) повторит себя же на одном из более ранних шагов (складывается периодическая конфигурация)
  • при очередном шаге ни одна из клеток не меняет своего состояния (частный случай предыдущего правила, складывается стабильная конфигурация)

Игрок не принимает активного участия в игре . Он лишь расставляет или генерирует начальную конфигурацию «живых» клеток, которые затем изменяются согласно правилам. Несмотря на простоту правил, в игре может возникать огромное разнообразие форм.

Появление идеи

Джон Конвей ещё в детстве заинтересовался проблемой, предложенной в 1940-х годах известным математиком Джоном фон Нейманом , который пытался создать гипотетическую машину, способную воспроизводить себя. Джону фон Нейману удалось создать математическую модель такой машины с довольно сложными правилами — в автомате фон Неймана ячейка может иметь одно из 29-ти состояний, которые эти правила описывают. Конвей поставил целью придумать как можно более простой клеточный автомат с нетривиальным поведением, надеясь, что в таком случае он будет тьюринг-полным . Команда энтузиастов (Конвей, его коллеги и студенты) занималась перебором бесчисленных вариаций правил в поисках подходящих. Итогом стал набор из двух правил для клеток с двумя состояниями, получивших известность как игра «Жизнь». В 1970 году в письме к Мартину Гарднеру Конвей изложил правила и основные сведения о получившейся системе, которые удалось быстро выяснить. Гарднер изложил это в своей колонке о математических играх в журнале Scientific American . Игра «Жизнь» быстро получила тысячи поклонников по всей Америке и за её пределами, а её изобретатель приобрёл известность среди широкой публики .

Вскоре Конвей доказал тьюринг-полноту игры «Жизнь» (доказательство не было опубликовано). После этого он практически потерял интерес к данной теме.

Конвей был недоволен тем, насколько игра «Жизнь» более известна, чем другие его работы, и не слишком любил о ней рассказывать — кроме как отдельным интересующимся детям .

Компьютерная реализация

В компьютерных реализациях игры поле ограничено и, как правило, замкнуто — верхняя граница поля «соединена» с нижней, а левая граница — с правой, что представляет собой эмуляцию поверхности тора , но на экране поле всегда отображается в виде равномерной сетки.

Простейший алгоритм «смены поколения» последовательно просматривает все клетки решётки, для каждой подсчитывает соседей, определяя судьбу клетки в новом поколении (не изменится, умрёт, родится). Такой алгоритм использует два двумерных массива — для текущего и для следующего поколений.

Более быстрый алгоритм делает первый проход по всем клеткам, но при этом составляет список клеток для просмотра в последующем поколении. Клетки, которые через поколение принципиально не могут измениться, в список не вносятся. Например, если какая-либо клетка и все её соседи не изменились при текущем обсчёте нового поколения, то эта клетка не изменится и при следующем проходе.

Фигуры

Вскоре после опубликования правил было обнаружено несколько интересных шаблонов (вариантов расстановки живых клеток в первом поколении), в частности: r -пентамино и планер ( glider ).

Некоторые такие фигуры остаются неизменными во всех последующих поколениях, состояние других периодически повторяется, в некоторых случаях со смещением всей фигуры. Существует фигура (Diehard) всего из семи живых клеток, потомки которой существуют в течение ста тридцати поколений, а затем исчезают.

Конвей первоначально предположил, что никакая начальная комбинация не может привести к неограниченному размножению и предложил премию в 50 долларов тому, кто докажет или опровергнет эту гипотезу. Приз был получен группой из Массачусетского технологического института , придумавшей неподвижную повторяющуюся фигуру, которая периодически создавала движущиеся «планеры». Таким образом, количество живых клеток могло расти неограниченно. Затем были найдены движущиеся фигуры, оставляющие за собой «мусор» из других фигур.

К настоящему времени более-менее сложилась следующая классификация фигур:

• Устойчивые фигуры : фигуры, которые остаются неизменными
• Долгожители : фигуры, которые долго меняются, прежде чем стабилизироваться ;
• Периодические фигуры : фигуры, у которых состояние повторяется через некоторое число поколений, большее 1;
• Двигающиеся фигуры : фигуры, у которых состояние повторяется, но с некоторым смещением;
• Ружья : фигуры с повторяющимися состояниями, дополнительно создающие движущиеся фигуры ;
• Паровозы : двигающиеся фигуры с повторяющимися состояниями, которые оставляют за собой другие фигуры в качестве следов;
• Пожиратели : устойчивые фигуры, которые могут пережить столкновения с некоторыми двигающимися фигурами, уничтожив их;
• Отражатели : устойчивые или периодические фигуры, способные при столкновении с ними движущихся фигур поменять их направление;
• Размножители : конфигурации, количество живых клеток в которых растёт как квадрат количества шагов;
• Фигуры, которые при столкновении с некоторыми фигурами дублируются.

Райский сад

Райским садом (садом Эдема) называется такое расположение клеток, у которого не может быть предыдущего поколения. Практически для любой игры, состояние клеток в которой определяется несколькими соседями на предыдущем шаге, можно доказать существование садов Эдема, но построить конкретную фигуру гораздо сложнее.

«Цифры»

С помощью простейшего «шрифта» размером 3 на 5 клеток, предложенного, по всей видимости, Эриком Анджелини в 2007 году, можно получить очень многие фигуры. Например, число 90, записанное этим шрифтом, порождает планер .

Влияние на развитие наук

Хотя игра состоит всего из двух простых правил, тем не менее она более сорока лет привлекает внимание учёных. Игра «Жизнь» и её модификации повлияли (в ряде случаев взаимно) на многие разделы таких точных наук, как математика , информатика и физика . Это, в частности:

• Теория автоматов ,
• Теория алгоритмов ,
• Теория игр и математическое программирование ,
• Алгебра и теория чисел ,
• Теория вероятностей и математическая статистика ,
• Комбинаторика и теория графов ,
• Фрактальная геометрия ,
• Вычислительная математика ,
• Теория принятия решений ,
• Математическое моделирование .

Кроме того, многие закономерности, обнаруженные в игре, имеют свои аналогии в других, подчас совершенно «нематематических» дисциплинах. Вот список наук, теории которых имеют интересные точки соприкосновения с феноменами «Жизни»:

• Кибернетика . Сама игра является удачной попыткой Конвея доказать существование простых самовоспроизводящихся систем, а также появление некоего «разума» у самовоспроизводящихся систем.
• Биология . Внешнее сходство с развитием популяций примитивных организмов впечатляет.
• Бактериология . Некоторые интересные вариации игры с дополнительными условиями могут с точностью повторить размножение бактерий, которые с случайной вероятностью могут мутировать (по условию модификации).
• Физиология . Рождение и смерть клеток подобны процессу возникновения и исчезновения нейронных импульсов.
• Астрономия . Эволюции некоторых сложных колоний удивительным образом схематично повторяют этапы развития спиралевидных галактик .
• Физика твёрдого тела . Теория автоматов вообще и игра «Жизнь» в частности используются для анализа «явлений переноса» — диффузии , вязкости и теплопроводности .
• Квантовая физика . Поведение «жизненных» ячеек (рождение новых и взаимное уничтожение) во многом напоминают процессы, происходящие при столкновении элементарных частиц .
• Наномеханика . Стационарные и пульсирующие колонии являются показательным примером простейших устройств, созданных на основе нанотехнологий.
• Электротехника . Правила игры используются для моделирования самовосстанавливающихся электрических цепей .
• Химия . Конфигурации, подобные строящимся в игре, возникают во время химических реакций на поверхности; в частности, в опытах М. С. Шакаевой возникают движущиеся молекулярные конструкции, аналогичные «жизненному» планеру. Также предпринимаются попытки объяснить периодические химические реакции с помощью многомерных клеточных автоматов. Самоорганизацией элементарных частиц также занимается супрамолекулярная химия .

Возможно, эта игра связана и с другими научными явлениями, в том числе и с теми, о которых современной науке пока неизвестно. Также возможно, что не открытые на сегодня законы природы и общества станут более понятными благодаря «Жизни» и её модификациям.

Варианты, модификации и обобщения

• Существуют модификации игры «Жизнь» / «Эволюция» по:
  • размерности — на плоскости, в объёме;
  • цветности — однотоновая, чёрно-белая (шахматная), полноцветная;
  • направлению алгоритма — прямой, обратный;
  • константам эволюции — классические (B3/S23), изменённые;
  • размерам игрового поля — ограниченное, неограниченное, полуограниченное;
  • активности поля — активное, пассивное;
  • количеству игроков — zero-game, один, два;
  • активности игры — пассивная, активная;
  • геометрии поля — прямоугольная, шестиугольная.
• Представляет интерес обратная задача Конвея — поиск предшественника заданной фигуры . Для решения её может привлекаться аппарат статистики: метод Монте-Карло , имитационное моделирование , а также весь арсенал эвристических методов .
• Эффективным алгоритмом полноцветной игры является декомпозиция исходного изображения на однотоновые, с последующей, после применения к ним классических правил жизни, их суперпозицией; для объёмных вариантов — ортогональный алгоритм преобразований. Примеры практического применения этого — всевозможные заставки, абстрактные изображения, дизайн произведений искусства.

• В шахматном, чёрно-белом варианте участвуют два игрока, цвет рождения определяется по преобладанию цвета в порождающей триаде, запись ходов осуществляется по правилам шахматных нотаций. Кроме оригинальных граничных образований, здесь наблюдаются коллизии цвета, например, «глайдер» в нотации : белые a2b2c2, чёрные c3b4 — полностью обесцвечивается за цикл преобразований, а то же: белые a2b2, чёрные c2c3 b4 — демонстрируется хроматическая цикличность «глайдера» в рамках его геометрической цикличности.
• В активной шахматной игре игрокам представляется возможность влиять на события «Жизни/Эволюции» единичным введением — выведением ограниченного количества фишек своего цвета с целью экспансии, стабилизации хода истории, противодействия в этом противнику. Теоретические основания здесь — методы принятия решения , аппарат теории игр .
• В трёхмерной реализации игры каждая клетка граничит с 26 другими клетками, выживает при 4-5 соседях, и рождается новая при 5 соседях, а также есть трёхмерные стабильные структуры, некоторые из которых схожи с двухмерными .
• В 2018 году Бертом Ван-Чаком было создано семейство клеточных автоматов как непрерывное обобщение «Игры жизни» Конвея с состояниями непрерывными в пространстве и во времени .

Интересные факты

• Правила игры таковы, что никакое взаимодействие не может передаваться быстрее хода шахматного короля . Его скорость — одна клетка в любом направлении — часто называют « скоростью света ».
• Фигура «планер» в 2003 году была предложена в качестве эмблемы хакеров .
• Первое русскоязычное упоминание « Game of Life » относится к 1971 году и в переводе журнала «Наука и жизнь » известна как «Эволюция».
• Если ввести в строке поиска Google « conway's game of life », то, помимо стандартного результата запроса, как фоновая анимация будет отображаться подобие этой игры .

• Существуют программы для создания звука из паттернов, сгенерированных в игре «Жизнь», в том числе в MIDI - секвенции ^{[ неавторитетный источник ]} .

Примечания

Литература

• Andrew Adamatzky. Game of Life Cellular Automata. — Springer-Verlag London, 2010. — ISBN 978-1-84996-216-2 , 978-1-4471-6154-7, 978-1-84996-217-9. — doi : .
• Paul Rendell. Turing Machine Universality of the Game of Life. — Springer International Publishing, 2016. — (Emergence, Complexity and Computation ; vol. 18). — ISBN 978-3-319-19841-5 , 978-3-319-19842-2. — doi : .
• Уэзерелл Ч. Этюды для программистов. — М. : Мир, 1982. — С. 19—22.
• Гарднер М. Крестики-нолики. — М. : Мир, 1988. — С. 287—343. — ISBN 5030012346 .
• Щеглов Г. Шахматная Эволюция. — Lambert Academic Publishing, 2012. — 88 с. — ISBN 9783848424603 .
• Трофимов М. Жизнь на Макинтоше // Монитор, 1995. — № 2, с.72; № 4, с.72; № 5, с.66.
• Журнал Наука и Жизнь. № 8, 1971, с. 130—133.
• Журнал В мире научных открытий. № 5.4(11), 2010, с. 50-53, 139. ISSN 2072-0831 (print), ISSN 2307-9428 (online)
• Приложение к журналу Юный техник. № 8 август 1989, с. 11-13
• Хэйес Б. Клеточный автомат создает модель мира и мир вокруг себя. // В мире науки , 1984, № 5, с.97-104
• Siobhan Roberts. . — Bloomsbury USA, 2015. — . — ISBN 9781620405932 .

Ссылки

• — игра «Жизнь» и родственные клеточные автоматы, программа Golly
• Клумова И. Н. // Квант . — 1974. — № 9 . — С. 26—30 .
• Martin Gardner . // Scientific American . — Vol. 223, № 4 (October 1970) . — P. 120—123. 1 мая 2013 года.