Игра жизни Конвея
"Игра Конвея" перенаправляет сюда. Для теории игр сюрреалистических чисел Конвея см. Сюрреалистическое число.
Игра жизни, также известная просто как Жизнь, представляет собой клеточный автомат, разработанный британским математиком Джоном Хортоном Конвеем в 1970 году. Это игра с нулевым игроком, это означает, что его эволюция определяется его начальным состоянием, не требуя дальнейшего ввода. Человек взаимодействует с Игрой Жизни, создавая начальную конфигурацию и наблюдая, как она развивается. Это полный Тьюринг и может имитировать универсальный конструктор или любую другую машину Тьюринга.
Правила[править]
Вселенная Игры жизни представляет собой бесконечную двумерную ортогональную сетку квадратных ячеек, каждая из которых находится в одном из двух возможных состояний, живом или мертвом (или населенном и незаселенном соответственно). Каждая клетка взаимодействует со своими восемью соседями, которые являются соседними по горизонтали, вертикали или диагонали. На каждом шаге во времени происходят следующие переходы:
- Любая живая клетка с менее чем двумя живыми соседями умирает, как будто из-за недостаточной численности населения.
- Любая живая клетка с двумя или тремя живыми соседями живет в следующем поколении.
- Любая живая клетка с более чем тремя живыми соседями умирает, как будто от перенаселения.
- Любая мертвая клетка с ровно тремя живыми соседями становится живой клеткой, как бы размножаясь.
Эти правила, которые сравнивают поведение автомата с реальной жизнью, можно свести к следующему:
- Любая живая клетка с двумя или тремя живыми соседями выживает.
- Любая мертвая клетка с тремя живыми соседями становится живой клеткой.
- Все остальные живые клетки умирают в следующем поколении. Точно так же все остальные мертвые клетки остаются мертвыми.
Начальный паттерн составляет семя системы. Первое поколение создается путем одновременного применения вышеуказанных правил к каждой клетке семени, живой или мертвой; рождение и смерть происходят одновременно, и дискретный момент, в который это происходит, иногда называют тиком.[nb 1] Каждое поколение является чистой функцией предыдущего. Правила продолжают применяться неоднократно для создания последующих поколений.
Происхождение[править]
Станислав Улам, работая в Лос-Аламосской национальной лаборатории в 1940-х годах, изучал рост кристаллов, используя в качестве модели простую решеточную сеть. В то же время Джон фон Нейман, коллега Улама в Лос-Аламосе, работал над проблемой самовоспроизводящихся систем.[8]: 1 Первоначальный проект фон Неймана был основан на идее одного робота, создающего другого робота. Эта конструкция известна как кинематическая модель.[9][10] Разрабатывая эту конструкцию, фон Нейман осознал огромную трудность создания самовоспроизводящегося робота и большую стоимость обеспечения робота "морем деталей", из которых можно построить его репликанта. Нейман написал статью под названием "Общая и логическая теория автоматов" для симпозиума Хиксона в 1948 году.1 Улам был тем, кто предложил использовать дискретную систему для создания редукционистской модели самовоспроизведения. xxix Улам и фон Нейман создали метод расчета движения жидкости в конце 1950-х годов. Движущая концепция метода состояла в том, чтобы рассматривать жидкость как группу дискретных единиц и вычислять движение каждой из них на основе поведения ее соседей.: 8 Так родилась первая система клеточных автоматов. Как и решетчатая сеть Улама, клеточные автоматы фон Неймана двумерны, а его саморепликатор реализован алгоритмически. В результате получился универсальный копировальный аппарат и конструктор, работающий в клеточном автомате с небольшой окрестностью (соседями являются только те клетки, которые соприкасаются; для клеточных автоматов фон Неймана - только ортогональные клетки) и с 29 состояниями на клетку. Фон Нейман дал доказательство существования того, что определенный паттерн будет создавать бесконечные копии себя в данной клеточной вселенной, разработав конфигурацию из 200 000 клеток, которая могла бы это сделать. Эта конструкция известна как модель тесселяции и называется универсальным конструктором фон Неймана.
Мотивированный вопросами математической логики и частично работой над симуляционными играми Улама, среди прочего, Джон Конвей начал проводить эксперименты в 1968 году с различными двумерными правилами клеточных автоматов. Первоначальная цель Конвея состояла в том, чтобы определить интересный и непредсказуемый клеточный автомат. По словам Мартина Гарднера, Конвей экспериментировал с различными правилами, стремясь к правилам, которые позволили бы шаблонам "по-видимому" расти без ограничений, в то же время затрудняя доказательство того, что любой данный шаблон будет делать это. Более того, некоторые "простые начальные паттерны" должны "расти и меняться в течение значительного периода времени", прежде чем осесть в статическую конфигурацию или повторяющийся цикл. Позже Конвей писал, что основной мотивацией для жизни было создание "универсального" клеточного автомата.
Игра впервые появилась в октябре 1970 года в Scientific American, в колонке Мартина Гарднера "Математические игры", которая была основана на личных беседах с Конвеем. Теоретически Игра жизни обладает силой универсальной машины Тьюринга: все, что может быть вычислено алгоритмически, может быть вычислено в Игре жизни. Гарднер писал: "Из-за аналогий Жизни с подъемом, падением и изменениями общества живых организмов, этоотносится к растущему классу так называемых "симуляционных игр" (игр, напоминающих реальные процессы)".
С момента своей публикации Игра жизни привлекла большой интерес из-за удивительных способов, которыми шаблоны могут развиваться. Она представляет собой пример возникновения и самоорганизации. Версия Жизни, включающая случайные флуктуации, использовалась в физике для изучения фазовых переходов и неравновесной динамики. Игра также может служить дидактической аналогией, используемой для передачи несколько нелогичного представления о том, что дизайн иорганизация может спонтанно возникнуть в отсутствие дизайнера. Например, философ Дэниел Деннет широко использовал аналогию с игрой жизни "вселенная", чтобы проиллюстрировать возможную эволюцию сложных философских конструкций, таких как сознание и свободная воля, из относительно простого набора детерминированных физических законов, которые могут управлять нашей вселенной.
Популярности Game of Life способствовало ее появление одновременно со все более недорогим доступом к компьютеру. Игра могла быть запущена в течение нескольких часов на этих машинах, которые в противном случае остались бы неиспользованными ночью. В этом отношении она предвосхитила более позднюю популярность компьютерных фракталов. Для многих Игра в жизнь была просто задачей программирования: забавный способ использовать впустую потраченные циклы процессора. Для некоторых, однако, Игра жизни имела более философские коннотации. В 1970-е и последующие годы она стала культовой; современные разработки зашли так далеко, что создали теоретические эмуляции компьютерных систем в рамках доски Game of Life.
Примеры паттернов[править]
В Игре жизни встречается много различных типов паттернов, которые классифицируются в соответствии с их поведением. Распространенные типы паттернов включают в себя: натюрморты, которые не меняются от одного поколения к другому; осцилляторы, которые возвращаются в исходное состояние после конечного числа поколений; и космические корабли, которые переводятся через сетку.
Самые ранние интересные закономерности в Игре жизни были обнаружены без использования компьютеров. Простейшие натюрморты и осцилляторы были обнаружены при отслеживании судеб различных небольших стартовых конфигураций с использованием графической бумаги, досок и физических игровых досок, таких как те, которые используются в Go. Во время этого раннего исследования Конвей обнаружил, что R-пентомино не смог стабилизироваться в небольшом количестве поколений. На самом деле, для стабилизации требуется 1103 поколения, к этому времени его население составляет 116 человек, и он произвел шесть спасающихся планеров; [22] это были первые космические корабли, когда-либо обнаруженные.
Часто встречающиеся примеры (в том смысле, что они часто возникают из случайной начальной конфигурации клеток) трех вышеупомянутых типов паттернов показаны ниже, причем живые клетки показаны черным цветом, а мертвые - белым. Период относится к числу тиков, которые шаблон должен пройти, прежде чем вернуться к своей первоначальной конфигурации.
| Натюрморты | Осцилляторы | Космические корабли |
|---|---|---|
Блок  |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
Пульсар является наиболее распространенным осциллятором периода 3. Подавляющее большинство естественных осцилляторов имеют период 2, как мигалка и жаба, но известны осцилляторы многих периодов и осцилляторы периодов 4, 8, 14, 15, 30, и некоторые другие , как было замечено, возникают из случайных начальных условий. Паттерны, которые эволюционируют в течение длительных периодов времени, прежде чем стабилизироваться, называются Мафусаилами, первым обнаруженным из которых был R-пентомино. Несгибаемый - это паттерн, который в конечном итоге исчезает, а не стабилизируется, после 130 поколений, что, как предполагается, является максимальным для паттернов с семью или менее клетками. Желудю требуется 5206 поколений, чтобы генерировать 633 клетки, включая 13 сбежавших планеров.
Первоначально Конвей предположил, что ни один паттерн не может расти бесконечно, т.Е. Что для любой начальной конфигурации с конечным числом живых клеток популяция не может расти дальше некоторого конечного верхнего предела. В оригинальном появлении игры в "Математических играх" Конвей предложил приз в пятьдесят долларов первому человеку, который сможет доказать или опровергнуть гипотезу до конца 1970 года. Приз был выигран в ноябре командой из Массачусетского технологического института во главе с Биллом Госпером; "Gosper glider gun" производит свой первый планер в 15-м поколении и еще один планер каждые 30-е поколение с тех пор. В течение многих лет эта планерная пушка была самой маленькой из известных. В 2015 году была обнаружена пушка под названием "Simkin glider gun", которая выпускает планер каждое 120-е поколение, которая имеет меньше живых клеток, но которая распределена по большей ограничивающей коробке на ее концах
Позже были обнаружены более мелкие модели, которые также демонстрируют бесконечный рост. Все три модели, показанные ниже, растут бесконечно. Первые два создают единый блок-кластер switch engine: конфигурацию, которая оставляет после себя два на два блока натюрморта, когда она переводится через вселенную игры. Третья конфигурация создает два таких шаблона. Первая имеет только десять живых клеток, что, как было доказано, минимально. Вторая помещается в квадрат пять на пять, а третья имеет только одну клетку высотой.
Более поздние открытия включали другие пушки, которые неподвижны и которые производят планеры или другие космические корабли; поезда фугу, которые движутся, оставляя за собой след обломков; и грабли, которые двигаются и испускают космические корабли.Госпер также построил первый паттерн с асимптотически оптимальной квадратичной скоростью роста, называемый селекционером или омаром, который работал, оставляя за собой след из пушек.
Планеры могут взаимодействовать с другими объектами интересными способами. Например, если два планера стреляют в блок в определенной позиции, блок будет двигаться ближе к источнику планеров. Если три планера выстрелят в правильном направлении, блок будет двигаться дальше. Этот скользящий блок памяти можно использовать для имитации счетчика. Можно построить логические элементы, такие как И, ИЛИ и НЕ используя планеры. Можно построить шаблон, который действует как конечный автомат, связанный с двумя счетчиками. Она обладает той же вычислительной мощностью, что и универсальная машина Тьюринга, поэтому теоретически Игра жизни так же мощна, как любой компьютер с неограниченной памятью и без ограничений по времени; она является полной по Тьюрингу. Фактически было реализовано несколько различных программируемых компьютерных архитектур в Игре жизни, в том числе паттерн, имитирующий Тетрис.
Кроме того, шаблон может содержать коллекцию пушек, которые стреляют планерами таким образом, чтобы создавать новые объекты, включая копии исходного шаблона. Можно построить универсальный конструктор, который содержит полный компьютер Тьюринга и который может строить много типов сложных объектов, включая больше копий самого себя.
В 2018 году первый по-настоящему элементарный рыцарский корабль, сэр Робин, был открыт Адамом П. Гоучером. Рыцарский корабль - это космический корабль, который перемещает два квадрата влево на каждый квадрат, который он перемещает вниз (как конь в шахматах), в отличие от перемещения ортогонально или по диагонали 45 °. Это первый новый образец движения космического корабля для элементарного космического корабля, найденного за сорок восемь лет. "Элементарная" означает, что она не может быть разложена на более мелкие взаимодействующие паттерны, такие как планеры и натюрморты.
Неразрешимость[править]
Многие паттерны в Игре жизни в конечном итоге становятся комбинацией натюрмортов, осцилляторов и космических кораблей; другие паттерны можно назвать хаотичными. Шаблон может оставаться хаотичным в течение очень долгого времени, пока в конечном итоге не достигнет такой комбинации.
Игра жизни неразрешима, что означает, что, учитывая начальный шаблон и более поздний шаблон, не существует алгоритма, который мог бы сказать, появится ли когда-либо более поздний шаблон. Это следствие проблемы остановки: проблема определения того, завершит ли данная программа работу или продолжит работать вечно с начального ввода.
Действительно, поскольку Игра жизни включает в себя паттерн, эквивалентный универсальной машине Тьюринга (UTM), этот решающий алгоритм, если бы он существовал, мог бы быть использован для решения проблемы остановки, взяв начальный паттерн как соответствующий UTM плюс входные данные, а более поздний паттерн - как один из них соответствует состоянию остановки UTM. Из этого также следует, что существуют некоторые шаблоны, которые остаются хаотичными навсегда. Если бы это было не так, можно было бы прогрессировать игру последовательно, пока не появится не хаотический паттерн, а затем вычислить, появится ли более поздний паттерн.
Самовоспроизведение[править]
18 мая 2010 года Эндрю Уэйд анонсировал самоконструирующийся паттерн, получивший название "Gemini", который создает копию самого себя, уничтожая своего родителя. Этот паттерн повторяется в 34 миллионах поколений и использует ленту инструкций, сделанную из планеров, колеблющихся между двумя стабильными конфигурациями, сделаннымиЧэпмен–Грин констракшн армс. Они, в свою очередь, создают новые копии шаблона и уничтожают предыдущую копию. Gemini также является космическим кораблем и является первым космическим кораблем, построенным в Game of Life, который является наклонным космическим кораблем, который не является ни ортогональным, ни чисто диагональным. В декабре 2015 года были построены диагональные версии Gemini.
23 ноября 2013 года Дэйв Грин построил первый репликатор в Game of Life, который создает полную копию самого себя, включая ленту с инструкциями.
В октябре 2018 года Адам П. Гоучер закончил строительство метаячейки 0E0P, метаячейки, способной к самовоспроизведению. Это отличалось от предыдущих метаэлементов, таких как метапиксель OTCA Брайса Дью, который работал только с уже построенными копиями рядом с ними. Метасеть 0E0P работает, используя строительные рычаги для создания копий, имитирующих запрограммированное правило.Фактическое моделирование Игры жизни или других правил окрестности Мура выполняется путем моделирования эквивалентного правила с использованием окрестности фон Неймана с большим количеством состояний. Название 0E0P является сокращением от "Ноль, закодированный нулевой популяцией", что указывает на то, что вместо того, чтобы метаклетка находилась в "выключенном" состоянии, имитирующем пустое пространство, метаклетка 0E0P удаляет себя, когда ячейка входит в это состояние, оставляя пустое пространство.
Итерация[править]
Из самых случайных начальных паттернов живых клеток на сетке наблюдатели обнаружат, что население постоянно меняется с поколениями. Закономерности, возникающие из простых правил, можно считать формой математической красоты. Небольшие изолированные подшаблоны без начальной симметрии имеют тенденцию становиться симметричными. Как только это произойдет, симметрия может увеличиться в богатстве, но она не может быть потеряна, если соседний подшаблон не подойдет достаточно близко, чтобы нарушить его. В очень немногих случаях общество в конце концов вымирает, и все живые клетки исчезают, хотя это может произойти не в течение многих поколений. Большинство начальных паттернов в конечном итоге выгорают, производя либо стабильные фигуры, либо паттерны, которые вечно колеблются между двумя или более состояниями; многие также производят один или несколько планеров или космических кораблей, которые бесконечно удаляются от исходного местоположения. Из-за правил, основанных на ближайших соседях, никакая информация не может проходить через сетку с большей скоростью, чем одна ячейка в единицу времени, поэтому эта скорость называется скоростью клеточного автомата света и обозначается c.
Алгоритмы[править]
Ранние паттерны с неизвестным будущим, такие как R-пентомино, привели программистов к написанию программ для отслеживания эволюции паттернов в Игре жизни. Большинство ранних алгоритмов были похожи: они представляли шаблоны в виде двумерных массивов в памяти компьютера. Обычно используются два массива: один для хранения текущего поколения и один для вычисления его преемника. Часто 0 и 1 представляют мертвые и живые клетки соответственно. Вложенный цикл for рассматривает каждый элемент текущего массива по очереди, подсчитывая живых соседей каждой ячейки, чтобы решить, должен ли соответствующий элемент массива-преемника быть 0 или 1. Отображается массив-преемник. Для следующей итерации массивы могут поменяться ролями, так что массив-преемник в последней итерации станет текущим массивом в следующей итерации, или можно скопировать значения второго массива в первый массив, а затем снова обновить второй массив из первого массива.
Возможны различные незначительные усовершенствования этой базовой схемы, и есть много способов сэкономить ненужные вычисления. Ячейка, которая не изменилась на последнем временном шаге, и ни один из соседей которой не изменился, гарантированно не изменится и на текущем временном шаге, поэтому программа, которая отслеживает, какие области активны, может сэкономить время, не обновляя неактивные зоны.
Чтобы избежать решений и ветвей в цикле подсчета, правила могут быть перестроены с эгоцентрического подхода внутреннего поля относительно его соседей на точку зрения научного наблюдателя: если сумма всех девяти полей в данной окрестности равна трем, состояние внутреннего поля для следующего поколения будет жизнью; если все девять полей в данной окрестности равны трем, то состояние внутреннего поля для следующего поколения будет жизнью.сумма всех полей равна четырем, внутреннее поле сохраняет свое текущее состояние, а любая другая сумма приводит внутреннее поле к смерти.
Чтобы сэкономить память, хранилище может быть уменьшено до одного массива плюс два буфера строк. Один буфер строки используется для вычисления состояния преемника для строки, затем второй буфер строки используется для вычисления состояния преемника для следующей строки. Затем первый буфер записывается в свою строку и освобождается для хранения состояния-преемника для третьей строки. Если используется тороидальный массив, необходим третий буфер, чтобы исходное состояние первой строки в массиве можно было сохранить до вычисления последней строки.
В принципе, поле Game of Life бесконечно, но компьютеры имеют конечную память. Это приводит к проблемам, когда активная область посягает на границу массива. Программисты использовали несколько стратегий для решения этих проблем. Самая простая стратегия - предположить, что каждая ячейка вне массива мертва. Это легко запрограммировать, но приводит к неточным результатам, когда активная область пересекает границу. Более сложный трюк состоит в том, чтобы считать левый и правый края поля сшитыми вместе, а также верхний и нижний края, что дает тороидальный массив. В результате активные области, которые перемещаются по краю поля, снова появляются на противоположном краю. Неточность все еще может привести, если шаблон становится слишком большим, но нет никаких патологических краевых эффектов. Также можно использовать методы динамического распределения памяти, создавая все большие массивы для хранения растущих шаблонов. Игра жизни на конечном поле иногда явно изучается; некоторые реализации, такие как Golly, поддерживают выбор стандартного бесконечного поля, поля, бесконечного только в одном измерении, или конечного поля, с выбором топологий, таких как цилиндр, тор или полоса Мебиуса.
В качестве альтернативы программисты могут отказаться от представления поля Game of Life с помощью двумерного массива и использовать другую структуру данных, такую как вектор пар координат, представляющих живые клетки. Это позволяет шаблону беспрепятственно перемещаться по полю, пока популяция не превышает размер массива живых координат. Недостатком является то, что подсчет живых соседей становится поиском по хеш-таблице или поисковой операцией, замедляющей скорость моделирования. С помощью более сложных структур данных эта проблема также может быть в значительной степени решена.
Для изучения больших паттернов на больших глубинах времени могут быть полезны сложные алгоритмы, такие как Hashlife. Существует также метод реализации Игры жизни и других клеточных автоматов с использованием произвольных асинхронных обновлений, в то же время точно эмулируя поведение синхронной игры. Примеры исходного кода, реализующие базовый сценарий Game of Life на различных языках программирования, включая C, C++, Java и Python, можно найти в Rosetta Code.
Вариации[править]
Основная статья: Жизнеподобный клеточный автомат
С момента создания Игры жизни были разработаны новые, похожие клеточные автоматы. Стандартная игра жизни символизируется как B3/S23. Клетка рождается, если у нее ровно три соседа, выживает, если у нее есть два или три живых соседа, и умирает в противном случае. Первое число или список чисел - это то, что требуется для рождения мертвой клетки. Второй набор - это требование к живой клетке, чтобы выжить до следующего поколения. Следовательно, B6 / S16 означает "клетка рождается, если есть шесть соседей, и живет, если есть один или шесть соседей". Клеточные автоматы на двумерной сетке, которые можно описать таким образом, известны как клеточные автоматы, подобные жизни. Другой распространенный жизнеподобный автомат, Highlife, описывается правилом B36 / S23, потому что наличие шести соседей, в дополнение к правилу B3 / S23 оригинальной игры, вызывает рождение. Хайлайф наиболее известен своими часто встречающимися репликаторами.
Существуют дополнительные жизнеподобные клеточные автоматы. Подавляющее большинство из этих 2 18 различных правил[56] создают вселенные, которые либо слишком хаотичны, либо слишком пустынны, чтобы представлять интерес, но большое подмножество демонстрирует интересное поведение. Дальнейшее обобщение дает изотропное пространство правил с 2 102 возможными правилами клеточных автоматов [57] (игра жизни снова является одним из них). Это правила, которые используют ту же квадратную сетку, что и Жизнеподобные правила, и ту же восьмиклеточную окрестность, а также инвариантны при вращении и отражении. Однако в изотропных правилах положения соседних клеток относительно друг друга могут быть приняты во внимание при определении будущего состояния клетки, а не только общего числа этих соседей.
Некоторые вариации Игры жизни изменяют геометрию Вселенной, а также правила. Приведенные выше варианты можно рассматривать как двумерный квадрат, потому что мир двумерен и выложен в квадратную сетку. Были разработаны одномерные квадратные вариации, известные как элементарные клеточные автоматы, и трехмерные квадратные вариации, а также двумерные гексагональные и треугольные вариации. Также был сделан вариант с использованием апериодических плиточных сеток.
Правила Конвея также могут быть обобщены таким образом, что вместо двух состояний, живого и мертвого, есть три или более. Переходы состояний затем определяются либо системой взвешивания, либо таблицей, определяющей отдельные правила перехода для каждого состояния; например, разноцветная таблица правил Целлебрации Мирека и взвешенные семейства правил жизни включают в себя примерные правила, эквивалентные Игре жизни.
Паттерны, относящиеся к фракталам и фрактальным системам, также могут наблюдаться в определенных жизнеподобных вариациях. Например, автомат B1 / S12 генерирует четыре очень близких приближения к треугольнику Серпинского при применении к одной живой клетке. Треугольник Серпинского также можно наблюдать в Игре жизни, исследуя долгосрочный рост бесконечно длинной линии живых клеток толщиной в одну клетку[60], а также в Highlife, Seeds (B2 / S) и Wolfram Rule 90[61].
Иммиграция - это вариация, которая очень похожа на Game of Life, за исключением того, что есть два состояния, часто выражаемых двумя разными цветами. Всякий раз, когда рождается новая клетка, она принимает состояние on, которое является большинством в трех клетках, давших ей рождение. Эта функция может быть использована для изучения взаимодействия между космическими кораблями и другими объектами в игре.[62] Другая подобная вариация, называемая QuadLife, включает в себя четыре различных состояния on. Когда новая клетка рождается из трех разных соседей, она принимает четвертое значение, а в противном случае, как и иммиграция, она принимает значение большинства. За исключением вариации среди on-клеток, обе эти вариации действуют идентично Игре Жизни.
Музыка[править]
Различные методы музыкальной композиции используют Игру жизни, особенно в MIDI-секвенировании.[64] Существует множество программ для создания звука из паттернов, генерируемых в Game of Life.
Известные программы[править]
Компьютеры использовались для отслеживания конфигураций Game of Life с момента ее первой публикации. Когда Джон Конвей впервые исследовал, как развивались различные стартовые конфигурации, он отслеживал их вручную, используя доску go с ее черными и белыми камнями. Это было утомительно и подвержено ошибкам. Первая интерактивная программа Game of Life была написана в ранней версии ALGOL 68C для PDP-7 M. J. T. Guy и S. R. Bourne. Результаты были опубликованы в октябрьском номере журнала Scientific American за 1970 год вместе с заявлением: "Без его помощи было бы трудно сделать некоторые открытия об игре".
Цветная версия Game of Life была написана Эдом Холлом в 1976 году для микрокомпьютеров Cromemco, и дисплей из этой программы заполнил обложку июньского номера Byte за 1976 год. Появление цветной графики на основе микрокомпьютеров от Cromemco было приписано возрождению интереса к игре.
Две ранние реализации Игры жизни на домашних компьютерах были Малкольмом Банторпом, написанным на BBC BASIC. Первая была в январском номере журнала Acorn User за 1984 год, а Банторп последовал за ней с трехмерной версией в майском номере 1984 года.Сьюзан Степни, профессор компьютерных наук Йоркского университета, в 1988 году разработала программу Life on the Line, которая генерировала одномерные клеточные автоматы.
В настоящее время существуют тысячи онлайн-программ Game of Life, поэтому полный список здесь не будет представлен. Ниже приводится небольшая подборка программ с некоторыми особыми претензиями на известность, такими как популярность или необычные функции. Большинство из этих программ включают в себя графический пользовательский интерфейс для редактирования и моделирования паттернов, возможность моделирования нескольких правил, включая Игру жизни, а также большую библиотеку интересных паттернов в Игре жизни и других правилах клеточных автоматов.
- Golly - это кроссплатформенная (Windows, Macintosh, Linux, iOS и Android) система моделирования с открытым исходным кодом для Игры в жизнь и других клеточных автоматов (включая все жизнеподобные клеточные автоматы, семейство клеточных автоматов Generations от Cellebration Мирека и 29-state Джона фон Неймана клеточный автомат) Эндрю Треворроу и Томаса Рокицки. Он включает в себя алгоритм Hashlife для чрезвычайно быстрой генерации и Lua или Python для редактирования и моделирования.
- Mirek's Cellebration - это бесплатная программа для просмотра, просмотра и редактирования одно- и двумерных клеточных автоматов для Windows. Он включает в себя мощные средства для моделирования и просмотра широкого спектра правил клеточных автоматов, включая Игру жизни, и редактор сценариев.
- Xlife - лаборатория клеточных автоматов Джона Беннетта. Стандартное приложение UNIX X11 Game of Life simulation в течение длительного времени также было портировано на Windows. Он может обрабатывать правила клеточного автомата с тем же соседством, что и Игра жизни, и до восьми возможных состояний на клетку[72].
- Организм доктора Блоба - это стрелялка, основанная на жизни Конвея. В игре Жизнь постоянно генерируется на группе клеток в "чашке Петри". Сформированные узоры сглажены и закруглены, чтобы выглядеть как растущая амеба, извергающая меньшие (на самом деле планеры). Специальные "зонды" захватывают "каплю", чтобы она не переполнила чашку, разрушая ее ядро.
Google реализовал пасхальное яйцо Игры жизни в 2012 году. Пользователям, которые ищут этот термин, отображается реализация игры на странице результатов поиска.
См. Также[править]
- Искусственная жизнь – Область изучения
- Сезон славы – научно-фантастический роман Дэвида Брина 1993 года, действие которого происходит в обществе будущего, где Игра жизни ведется в конкурентном режиме для двух игроков
- Муравей Ленгтона – двумерная машина Тьюринга с эмерджентным поведением
- Poietic Generator – социальная сетевая игра, играемая на двумерной матрице, "человеческая" Игра Жизни.
- Самоорганизация § Информатика
Читать[править]
Пруф[править]
curlie.org/Computers/Artificial_Life/Cellular_Automata/Conway%27s_Game_of_Life