Игра Жизни Конвея

Игра Жизни Конвея

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

Содержание

Правила

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

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

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

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

Происхождение

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

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

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

Фигуры

Глайдер (glider)

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

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

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

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

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

Райский сад

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

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

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

И хотя игра состоит всего из двух простейших правил, она уже почти сорок лет привлекает пристальное внимание учёных. Игра «Жизнь» оказала определённое влияние на развитие многих разделов математики и информатики:

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

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

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

Ссылки


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Полезное


Смотреть что такое "Игра Жизни Конвея" в других словарях:

  • Игра Жизнь — Игра «Жизнь» (англ. Conway s Game of Life)  клеточный автомат, придуманный английским математиком Джоном Конвеем (англ.) в 1970 году. Описание этой игры было опубликовано в октябрьском выпуске (1970) журнала Scientific American, в рубрике… …   Википедия

  • Игра жизнь — Игра «Жизнь» (англ. Conway s Game of Life)  клеточный автомат, придуманный английским математиком Джоном Конвеем (англ.) в 1970 году. Описание этой игры было опубликовано в октябрьском выпуске (1970) журнала Scientific American, в рубрике… …   Википедия

  • Эволюция (игра) — Игра «Жизнь» (англ. Conway s Game of Life)  клеточный автомат, придуманный английским математиком Джоном Конвеем (англ.) в 1970 году. Описание этой игры было опубликовано в октябрьском выпуске (1970) журнала Scientific American, в рубрике… …   Википедия

  • Жизнь (игра) — У этого термина существуют и другие значения, см. Жизнь (значения). Игра «Жизнь» (англ. Conway s Game of Life)  клеточный автомат, придуманный английским математиком Джоном Конвеем в 1970 году. Содержание 1 Правила …   Википедия

  • Каратель (комикс) — Каратель «The Punisher» №22 (том 4) Художник: Тим Брэдстрит История Издатель Marvel Comics Дебют The Amazing Spider Man №129 (Феврал …   Википедия

  • Каратель — У этого термина существуют и другие значения, см. Каратель (значения). Каратель «The Punisher» № 22 (том 4) Художник: Тим Брэдстрит История публикаций …   Википедия

  • Список персонажей Grand Theft Auto IV — Основная статья: Grand Theft Auto IV Компьютерная игра Grand Theft Auto IV, действие которой разворачивается в 2008 году, знакомит игрока со множеством персонажей. Согласно словам Дэна Хаузера, «на самом деле ни один персонаж из предыдущих игр не …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»