«Жизнь» — математическая игра, моделирующая развитие колоний одноклеточных организмов и (при правильном использовании) множество других процессов. Превратности судьбы организмов, живущих на клетчатом поле, уже послужили темой многих научных исследований, поучаствовать в которых легко можете и вы.
Текущая игра
Управление
Оформление
Объекты
Сохранение и загрузка
Правила игры
Плоскость замощена квадратными клетками. Каждая клетка может быть либо живой, либо мёртвой. Пользователь (игрок) задаёт изначальный набор живых клеток и наблюдает за его эволюцией.
Система развивается по определённым правилам: в каждый ход (шаг по времени) некоторые живые клетки умирают, а на месте некоторых мёртвых рождаются живые.
Правила таковы:
- если клетка была жива, и две или три соседние клетки тоже были живы, клетка остаётся живой, в противном случае она умирает;
- если клетка была мертва, и ровно три соседние клетки были живы, то на её месте рождается живая, в противном случае она остаётся мёртвой.
При подсчёте соседних клеток учитываются соседи и по стороне, и по углу, то есть всего их восемь.
Кто и зачем это придумал
Широкой публике игру представил Мартин Гарднер, но правила «Жизни» придумал британский математик Джон Конвей, работая над идеями Джона фон Неймана, касающимися фундаментальных вопросов логики, информатики и теории алгоритмов. Требовалось придумать систему, описываемую достаточно простыми правилами, в которой существовали бы неограниченно растущие объекты и самокопирующиеся объекты, и чтобы поведение различных объектов было достаточно интересным и непредсказуемым. Такое поведение характерно и для живых организмов. Когда «Жизнь» исследовали более подробно, оказалось, что игра рождает ситуации, похожие на процессы, изучаемые в самых разных науках.
Впрочем, правила вполне самодостаточны. Игра в «Жизнь» заключается не столько в наблюдении развития конкретной конфигурации, сколько в постановке задач и поиске ответов на них. Например: какие существуют неограниченно растущие объекты? Сколько может продолжаться эволюция начальной конфигурации из пяти живых клеток? Как с помощью «Жизни» смоделировать машину Тьюринга?
На эти и многие другие вопросы ответы уже даны, но вопросов без ответов не меньше. Изучение игры «Жизнь» можно сравнить с занятием астрономией: требуется инструмент, знания и терпение; практическая польза, скажем так, не очевидна; не всякий сочтёт это занятие интересным; но для других это может быть самым увлекательным занятием.
Что математики выяснили про игру
Самые простые (и потому неинтересные) объекты, которые не исчезают мгновенно, — это натюрморты, неподвижные фигуры, такие как квадрат 2 на 2. Кроме этого, выделяют осцилляторы — фигуры, которые меняются периодически, оставаясь на месте; простейший пример — семафор, осциллятор с периодом 2. Он представляет собой три клетки рядом. Они получаются в изобилии из многих случайных начальных конфигураций.
Гораздо интереснее следить за эволюцией объектов, которые ведут себя нетривиально, например, движутся в заданном направлении. Такие объекты называются космическими кораблями. Простейшим космическим кораблём является глайдер. Он движется по диагонали. А глайдерная пушка умеет эти глайдеры выпускать. (Воспользуйтесь кнопками выше, чтобы увидеть её в действии.) Глайдерная пушка стала первым открытым объектом, который рос бесконечно.
Другой типичный космический корабль — ЛКК, лёгкий космический корабль. Он движется по горизонтали (или по вертикали, если его повернуть; для краткости говорят «ортогонально»). Выбрав объект Тагалонг, вы увидите два ЛКК, которые не только летят сами, но и тащат за собой конструкцию, которая без них бы распалась (можете проверить это, убрав один или оба ЛКК).
Поскольку правила рождения-умирания клеток короткодействующие, то никакой объект не может двигаться в любом ортогональном направлении со скоростью большей, чем 1 клетка за шаг. Эта скорость называется скоростью света и обозначается c. Например, скорость глайдера — c/4. Можно построить конструкцию, по которой возмущение распространяется ровно со скоростью света.
Глайдеры активно используют для передачи сигналов от одной группы клеток к другой при изготовлении различных устройств в клетчатой вселенной «Жизни». А устройств этих изготовлено множество. Большим успехом стало изобретение Джемини — космического корабля, передвигающегося путём самокопирования (к тому же это один из немногих известных космических кораблей, которые движутся ни ортогонально, ни диагонально), а на его основе — истинно самокопирующегося Репликатора; о такой конструкции думал ещё фон Нейман, её существование было доказано много лет назад, но построить её в правилах Конвея удалось лишь недавно.
Правила игры «Жизнь» позволяют реализовать на её поле даже саму игру «Жизнь».
В правилах Конвея рождение происходит при трёх соседях, выживание — при двух или трёх; такие правила обозначаются B3/S23 (от слов birth и survival — рождение и выживание) или 23/3. Эти правила можно менять. В новой «атмосфере» поведение всех объектов существенно меняется, и изучены лишь некоторые из вариаций. Заметим, однако, что существование космических кораблей — довольно редкое явление.
Но и это ещё не всё. Можно развивать идею и дальше. Например, почему бы не разрешить клеткам иметь не два, а три состояния?
Таким образом, существует огромный класс подобных игр. Они называются клеточными автоматами. Хорошо составленный клеточный автомат может стать хорошей моделью для биологического, физического или какого-то ещё процесса и обширным полем для интереснейших исследований, доступных каждому, кто умеет программировать.
Что можно добавить к этой реализации «Жизни»
- Регулирование масштаба
- Перемещение по полю
- Больше готовых объектов
- Автоматический анализ систем
- ...
Ссылки
- ConwayLife.com — этот сайт аккумулирует новости об изучении клеточных автоматов.
- Кроме того, этот сайт содержит wiki с описанием многих понятий и шаблонов, которые можно скачать в различных форматах.
- Golly — по-видимому, лучшая реализация «Жизни» в виде программы. Поддерживает различные обобщения игры. Также живёт на ConwayLife.
- Форумы сайта ConwayLife — то место, где идёт обсуждение текущих исследований «Жизни».
- Catagolue — активно пополняемый каталог объектов.
- Сайт Николая Белюченко содержит множество качественных статей об игре «Жизнь» на русском языке, от вводных до предназначенных специалистам. В частности, там есть русский перевод старого словаря «Жизни» Стивена Сильвера, который описывает стандартную терминологию, используемую в исследованиях игры.
- Статьи об игре в русской и английской Википедиях содержат качественные иллюстрации и дополнительные ссылки.
- Об обобщениях «Жизни» также есть множество материалов, в том числе в Википедии (cellular automaton, муравей Лэнгтона), на Хабрахабре (1, 2, 3 и т. д.), а также, например, в книге Game of Life Cellular Automata.
- Приведённую здесь реализация игры «Жизнь» создал Педро Веррума с использованием алгоритма List Life. Андрей Заболотский осуществил перевод интерфейса на русский язык, добавил многие функции и написал сопроводительный текст.
Чтобы максимально эффективно поиграться с известными объектами «Жизни», откройте вышеупомянутый словарь или вики, выберите интересующий вас объект, скопируйте оттуда шаблон в текстовое поле на этой странице и нажмите «Загрузить». В словаре шаблон обычно приводится прямо в статье про объект; в вики на странице объекта (например, здесь) ссылка на шаблон в нужном формате находится в синей табличке справа в свёрнутом разделе Pattern files, формат plaintext, RLE или LifeHistory, и встречающиеся у некоторых иллюстраций ссылки Download RLE тоже подходят.
2 комментария :
Лучшая реализация клеточных автоматов: http://golly.sourceforge.net/
Также стоит почитать про hashlife алгоритм: http://en.wikipedia.org/wiki/Hashlife
Golly -- действительно лучшая реализация (между прочим, я так и написал в разделе ссылок). Это пример очень, очень качественного свободного ПО.
Отправить комментарий