Реклама


Игра «Жизнь»

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

Содержание

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

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

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

Происхождение[ | код]

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

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

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

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

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

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

Фигуры[ | код]

Color coded racetrack large channel.gif

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

Планер (glider) на квадратной решётке 10 × 10 с периодическими условиями

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

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

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

Планерное ружьё Госпера — первая бесконечно растущая фигура

Райский сад[ | код]

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

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

«Цифры»[ | код]

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

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

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

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

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

Факты[ | код]

Модификации Game of Life[ | код]

Примечания[ | код]

  1. Martin Gardner. The fantastic combinations of John Conway's new solitaire game "life" // Scientific American. — № 4 (October 1970).
  2. Словарь Жизни: Долгожитель
  3. Digits in Life. www.radicaleye.com. Дата обращения 15 июля 2017.
  4. Тоффоли Т., Марголус Н. Машины клеточных автоматов. — М.: Мир, 1991. — ISBN 5-03-001619-8
  5. M. W. Mueller, W. D. Arnett. Propagating star formation and irregular structure in spiral galaxies (англ.) // The Astrophysical Journal. — 1976-12-01. — Vol. 210. — P. 670–678. — ISSN 0004-637X. — DOI:10.1086/154873.
  6. H. Gerola, P. E. Seiden. Stochastic star formation and spiral structure of galaxies (англ.) // The Astrophysical Journal. — 1978-07-01. — Vol. 223. — P. 129–135. — ISSN 0004-637X. — DOI:10.1086/156243.
  7. Jon Mitchel. How A Google Engineer Built A Universe In An Easter Egg (5 октября 2012).
  8. Siobhan Roberts. Prologue // Genius At Play: The Curious Mind of John Horton Conway. — Bloomsbury Publishing USA, 2015. — P. XV. — 480 p. — ISBN 1-620-40594-6, 978-1-620-40594-9.
  9. Журнал Наука и жизнь. № 8, 1972 г. Стр. 141—144

Литература[ | код]

Ссылки[ | код]

Реклама