Жизнь (игра)

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Игра́ «Жизнь» (англ. Conway's Game of Life) — клеточный автомат, придуманный английским математиком Джоном Конвеем в 1970 году.

Правила[править | править вики-текст]

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

Эти простые правила приводят к огромному разнообразию форм, которые могут возникнуть в игре.

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

Происхождение[править | править вики-текст]

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

Впервые описание этой игры было опубликовано в октябрьском (1970 год) выпуске журнала Scientific American, в рубрике «Математические игры» Мартина Гарднера (Martin Gardner)[1].

Компьютерная реализация[править | править вики-текст]

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

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

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

Фигуры[править | править вики-текст]

Color coded racetrack large channel.gif

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

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

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

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

Планерное ружьё Госпера (англ.) — первая бесконечно растущая фигура
  • Устойчивые фигуры: фигуры, которые остаются неизменными
  • Мафусаилы: фигуры, которые долго меняются, прежде чем стабилизироваться.
  • Периодические фигуры: фигуры, у которых состояние повторяется через некоторое число поколений
  • Двигающиеся фигуры: фигуры, у которых состояние повторяется, но с некоторым смещением
  • Ружья: фигуры, у которых состояние повторяется, но дополнительно появляется двигающаяся фигура
  • Паровозы: двигающиеся фигуры, которые оставляют за собой следы в виде устойчивых или периодических фигур
  • Пожиратели: устойчивые фигуры, которые могут пережить столкновения с некоторыми двигающимися фигурами
  • Сорняки (паразиты)[источник не указан 1325 дней]: фигуры, которые при столкновении с некоторыми фигурами дублируются.

Райский сад[править | править вики-текст]

Пример Райского сада

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

«Цифры»[править | править вики-текст]

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

Влияние на развитие наук[править | править вики-текст]

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

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

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

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

Интересные факты[править | править вики-текст]

  • Фигура «планер» (glider) в 2003 году была предложена в качестве эмблемы хакеров.
  • Первое русскоязычное упоминание Game of Life относится к 1971 г. В переводе журнала «Наука и Жизнь» известна как «Эволюция».


Модификации Game of Life[править | править вики-текст]

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

Литература[править | править вики-текст]

  • Уэзерелл Ч. Этюды для программистов. — М.: Мир, 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)

Ссылки[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Martin Gardner The fantastic combinations of John Conway's new solitaire game "life" // Scientific American. — № 4 (October 1970).
  2. Dean Hickerson’s Life page
  3. Тоффоли Т., Марголус Н. Машины клеточных автоматов. — М.: Мир, 1991. — ISBN 5-03-001619-8
  4. Журнал Наука и жизнь. № 8, 1972 г. С. 141-144