Загрузка...
Поддержи Openmeetings

среда, 29 августа 2012 г.

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

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

Текущая игра

Поколение: | Живых клеток: | Время шага: мс
Правила:

Управление


Поле на торе

Оформление

Объекты

Сохранение и загрузка


Правила игры

Плоскость замощена квадратными клетками. Каждая клетка может быть либо живой, либо мёртвой. Пользователь (игрок) задаёт изначальный набор живых клеток и наблюдает за его эволюцией.

Система развивается по определённым правилам: в каждый ход (шаг по времени) некоторые живые клетки умирают, а на месте некоторых мёртвых рождаются живые.

Правила таковы:

  • если клетка была жива, и две или три соседние клетки тоже были живы, клетка остаётся живой, в противном случае она умирает;
  • если клетка была мертва, и ровно три соседние клетки были живы, то на её месте рождается живая, в противном случае она остаётся мёртвой.

При подсчёте соседних клеток учитываются соседи и по стороне, и по углу, то есть всего их восемь.

Кто и зачем это придумал

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

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

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

Что математики выяснили про игру

Самые простые (и потому неинтересные) объекты, которые не исчезают мгновенно, — это натюрморты, неподвижные фигуры, такие как квадрат 2 на 2. Кроме этого, выделяют осцилляторы — фигуры, которые меняются периодически, оставаясь на месте; простейший пример — семафор, осциллятор с периодом 2. Он представляет собой три клетки рядом. Они получаются в изобилии из многих случайных начальных конфигураций.

Гораздо интереснее следить за эволюцией объектов, которые ведут себя нетривиально, например, движутся в заданном направлении. Такие объекты называются космическими кораблями. Простейшим космическим кораблём является глайдер. Он движется по диагонали. А глайдерная пушка умеет эти глайдеры выпускать. (Воспользуйтесь кнопками выше, чтобы увидеть её в действии.) Глайдерная пушка стала первым открытым объектом, который рос бесконечно.

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

Поскольку правила рождения-умирания клеток короткодействующие, то никакой объект не может двигаться в любом ортогональном направлении со скоростью большей, чем 1 клетка за шаг. Эта скорость называется скоростью света и обозначается c. Например, скорость глайдера — c/4. Можно построить конструкцию, по которой возмущение распространяется ровно со скоростью света.

Глайдеры активно используют для передачи сигналов от одной группы клеток к другой при изготовлении различных устройств в клетчатой вселенной «Жизни». А устройств этих изготовлено множество. Большим успехом стало изобретение Джемини — космического корабля, передвигающегося путём самокопирования (к тому же это один из немногих известных космических кораблей, которые движутся ни ортогонально, ни диагонально), а на его основе — истинно самокопирующегося Репликатора; о такой конструкции думал ещё фон Нейман, её существование было доказано много лет назад, но построить её в правилах Конвея удалось лишь недавно.

Правила игры «Жизнь» позволяют реализовать на её поле даже саму игру «Жизнь».

В правилах Конвея рождение происходит при трёх соседях, выживание — при двух или трёх; такие правила обозначаются B3/S23 (от слов birth и survival — рождение и выживание) или 23/3. Эти правила можно менять. В новой «атмосфере» поведение всех объектов существенно меняется, и изучены лишь некоторые из вариаций. Заметим, однако, что существование космических кораблей — довольно редкое явление.

Но и это ещё не всё. Можно развивать идею и дальше. Например, почему бы не разрешить клеткам иметь не два, а три состояния?

Таким образом, существует огромный класс подобных игр. Они называются клеточными автоматами. Хорошо составленный клеточный автомат может стать хорошей моделью для биологического, физического или какого-то ещё процесса и обширным полем для интереснейших исследований, доступных каждому, кто умеет программировать.

Что можно добавить к этой реализации «Жизни»

  • Регулирование масштаба
  • Перемещение по полю
  • Больше готовых объектов
  • Автоматический анализ систем
  • ...

Ссылки

  • ConwayLife.com — этот сайт аккумулирует новости об изучении клеточных автоматов.
    • Кроме того, этот сайт содержит wiki с описанием многих понятий и шаблонов, которые можно скачать в различных форматах.
    • Golly — по-видимому, лучшая реализация «Жизни» в виде программы. Поддерживает различные обобщения игры. Также живёт на ConwayLife.
    • Форумы сайта ConwayLife — то место, где идёт обсуждение текущих исследований «Жизни».
  • Catagolue — активно пополняемый каталог объектов.
  • Сайт Николая Белюченко содержит множество качественных статей об игре «Жизнь» на русском языке, от вводных до предназначенных специалистам. В частности, там есть русский перевод старого словаря «Жизни» Стивена Сильвера, который описывает стандартную терминологию, используемую в исследованиях игры.
  • Статьи об игре в русской и английской Википедиях содержат качественные иллюстрации и дополнительные ссылки.
  • Об обобщениях «Жизни» также есть множество материалов, в том числе в Википедии (cellular automation, муравей Лэнгтона), на Хабрахабре (1, 2, 3 и т. д.), а также, например, в книге Game of Life Cellular Automata.
  • Приведённую здесь реализация игры «Жизнь» создал Педро Веррума с использованием алгоритма List Life. Андрей Заболотский осуществил перевод интерфейса на русский язык, добавил многие функции и написал сопроводительный текст.

Чтобы максимально эффективно поиграться с известными объектами «Жизни», откройте вышеупомянутый словарь или вики, выберите интересующий вас объект, скопируйте оттуда шаблон в текстовое поле на этой странице и нажмите «Загрузить». В словаре шаблон обычно приводится прямо в статье про объект; в вики на странице объекта (например, здесь) ссылка на шаблон в нужном формате находится в синей табличке справа в свёрнутом разделе Pattern files, формат plaintext, RLE или LifeHistory, и встречающиеся у некоторых иллюстраций ссылки Download RLE тоже подходят.

2 комментария :

Отправить комментарий