Игра жизнь джона конвея

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

Содержание

Правила [ править | править код ]

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

• в пустой (мёртвой) клетке, рядом с которой ровно три живые клетки, зарождается жизнь;
• если у живой клетки есть две или три живые соседки, то эта клетка продолжает жить; в противном случае, если соседей меньше двух или больше трёх, клетка умирает («от одиночества» или «от перенаселённости»)

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

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

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

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

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

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

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

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

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

Фигуры [ править | править код ]

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

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

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

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

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

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

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

«Цифры» [ править | править код ]

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

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

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

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

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

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

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

Реализация знаменитой игры «Жизнь» — клеточного автомата, изобретённого английским математиком Джоном Конвеем.

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

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

Лично меня поражает, что такие простые правила могут породить великое разнообразие форм жизни. На этой странице я привожу лишь немногие из известных. В основном, это движущиеся и осциллирующие фигуры. Разве они не удивительны!

Этим игра «Жизнь» похожа на фракталы, где замысловатые формы порождаются весьма небольшим набором правил.

Этот движок поддерживает два метода отображения. Более приоритетный — canvas. Если браузер его не поддерживает, то используется простая HTML-таблица, которая работает значительно медленней. Кроме того, в таблице не так удобно редактировать картинку. Если вы видите красноватые квадраты, значит ваш браузер не поддерживает canvas. Я очень рекомендую использовать более современный браузер. Если квадраты тёмно-синие, значит вы используете самые передовые технологии.

Если у вас что-то не работает, — пишите, — буду очень признателен.

Игра жизни Конвея — это метод клеточной автоматизации, созданный Джоном Конвеем. Эта игра была создана с учетом биологии, но применялась в различных областях, таких как графика, рельеф местности и т. Д.

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

Как работает игра

Поскольку Игра Жизни построена на сетке из девяти квадратов, каждая ячейка имеет восемь соседних ячеек, как показано на данном рисунке. Доступ к данной ячейке (i, j) в симуляции осуществляется по сетке [i] [j], где i и j — индексы строк и столбцов соответственно. Значение данной ячейки в данный момент времени зависит от состояния ее соседей на предыдущем временном шаге. Игра жизни Конвея имеет четыре правила.

1. Если ячейка включена и у нее включено менее двух соседей, она выключается
2. Если ячейка включена и имеет двух или трех соседей, которые включены, она остается включенной.
3. Если ячейка включена и имеет более трех соседей, то она выключается.
4. Если ячейка выключена и имеет ровно три соседних узла, она включается.

Так как мы знаем, как это работает, нам нужно выяснить, как заставить это работать.

Подход

После того, как мы закончим, давайте разберемся с кодом.

Требования

NumPy

: Для манипулирования двумерным массивом (матрицей).

Matplotlib

: Для обновления симуляции или в простых словах, чтобы заставить вещи двигаться.

argparse

: Передать аргументы командной строки в коде.