Правила Жизни

      Суть "Жизни" очень проста, как и суть обычной человеческой жизни. На игровом поле располагается в некотором начальном порядке определенное количество фишек, которые задают начальные условия эволюционного процесса. Каждая ячейка игрового поля может находиться в двух состояниях - либо оставаться пустой, либо быть занятой фишкой. Игра состоит из "циклов жизни", или из последовательности дискретных шагов, с помощью которых имитируется смена поколений. Переход от предыдущего поколения к следующему происходит по определенным правилам, которые применяются одновременно ко всем клеткам доски.

     Правила игры сводятся к следующему:
 

 
     Эти правила относятся всегда к состоянию, которое существует к началу "хода". Все изменения на игровом поле происходят как бы одновременно, хотя и состоят из нескольких этапов. На первом этапе определяется, на каких клетках будет происходить рождение и какие фишки будут в следующей генерации сняты с доски. На втором этапе происходит воплощение задуманного в жизнь - на отмеченных полях появляются новые "субъекты эволюции", а фишки, которые не выдержали суровых законов игры снимаются с доски.

Характеристики объектов Жизни

   Любой объект "Жизни", как совокупность активных элементов, число и взаимное расположение которых меняется от шага к шагу, характеризуется некоторыми численными параметрами. Прежде всего это - размер, определяющий количество одновременно присутствующих фишек на игровом поле. Начальный объект "Жизни", естественно, характеризуется и начальным размером.

      Чтобы подчеркнуть схожесть искусственной эволюции с ее естественным аналогом при описании игры используют термин популяция. Тогда можно легко рассуждать как о размере популяции, как числе особей на данном этапе ее развития, так и о мощности популяции. Мощность - это одна из важных характеристик популяции, которая характеризует запас ее жизненных сил и определяется, как сумма всех элементов в течении всех циклов Жизни или всей игры.

      Любой объект, начав эволюционировать в начале Игры, в какой-то момент прекращает свою еволюцию. Проявляется это в следующем:

популяция может полностью выродиться (игровое поле очищается);

популяция может деградировать к некоторому сочетанию стабильных объектов (некоторые из которых приведены, например, на рис.1,2);

популяция кроме фиксированных объектов содержит также и пульсирующие объекты. При этом в целом популяция периодически повторяет свое состояние - пульсирует.

      Любое из описанных состояний для популяции считается конечным. В связи с этим, для каждого начального объекта используется понятие длительности жизненного цикла или срока Жизни.

Особенности жизненных процессов

  Прежде чем перейти к практическому рассмотрению Игры, заметим, что в результате эволюции на игровом поле возникает множество стабильных объектов, некоторые из которых встречаются настолько часто, что получили даже собственные имена. Это достаточно удобно для описания результатов, получаемых в процессе эволюции. На рис.1 приведен полный перечень стабильных объектов размера 4, 5 и 6, а также единственный объект размера 3 («светофор»). На рис.2. приведена полная спецификация объектов размера 7.

 

Познать "Жизнь" на практике проще всего с помощью листа бумаги в клеточку и ручки. Можно воспользоваться также шахматной доской и обычными шашками двух цветов. Еще проще — использовать для этой цели компьютер.

     Пройдем вместе первый шаги. Зададим начальное расположение фишек в виде фигуры, получившей наименование «пентадекатрон» . Эта фигура принадлежит к классу пульсирующих объектов с периодом 15 - отсюда и столь странное ее наименование.

Полный цикл "Пентадекатрона" содержит 15 шагов. На 15-м шаге снова появится начальный объект и далее все повторится сначала - вечный круговорот Жизни. Теория характеризует этот и подобные объекты как пульсирующие или осциллирующие. А так как эти объекты имеют определенный период пульсации, то их можно назвать также и периодическими. Существует громадное количество таких объектов, начиная от простейших (линейка из трех элементов), до очень сложных, которые в принципе могут строиться в виде комбинаций из простых осциллирующих объектов.

Жизнь выходит из пробирки

     Игровой процесс оказался настолько увлекательным, а фигуры, которые начали появляться на игровом поле - настолько необычными, что игра увлекла в свою сферу огромное количество ученых из Американских университетов, аспирантов, программистов и т.д. Фиксированные правила игры позволяли задать только начальные условия, т.е. расположение фишек, а дальше "Жизнь" шла самостоятельно, приводя на каждом шаге к появлению новых и новых фигур. Процесс или обрывался - эволюция искусственной экосистемы завершалась крахом, или стабилизировалась - тогда появлялись цепочки, циклически повторяющие одни и те же фигуры, либо длилась вечно, т.е. процесс порождения новых фигур не замирал никогда. Что-то похожее сегодня можно увидеть во фракталах - простая начальная фигура порождает с каждым шагом все более и более замысловатую последовательность узоров. Наблюдение за ходом "Жизни" или "фрактальным" процессом занятие не менее увлекательное, чем любая компьютерная игра.

     Однако жизнь, развивающаяся на расчерченном листе бумаги или шахматном поле (in nature) ничем не отличается от жизни в пробирке (in vitro) - и та и другая столь же ограниченная и неполноценная. Выйти "Жизни" наружу помогли программисты, которые в свободное от работы время увлеклись этой игрой. А так как мозг программиста устроен не так, как у обычных людей, то вместо того, чтобы играть в эту игру на расчерченном листике бумаги, программисты начали эту игру программировать.

     Вот тут и начались чудеса. Производительности IBM 360 оказалось вполне достаточно, чтобы построить модель Игры и провести достаточно серьзные научные изыскания в этой области. Программисты ведь и отдыхают только тогда, когда решают какую-нибудь интересную задачу.

 
Первые результаты

      Вначале были выявлены достаточно простые конструкции, которые однако пробудили интерес к дальнейшим исследованиям. Например, такая конструкция, как «часы» (Рис.4) содержит внутри нечто похожее на стрелку. От шага к шагу эта "стрелка" меняет положение на 90 град, создавая иллюзию вращения ее по кругу.

     Еще одна фигура, получившая название «пчелиная матка», представляет собой объект, состоящий из двух "блоков" и расположенной между ними некоей фигуры (Рис.5). В процессе эволюции это "нечто" перемещается в пространстве между "блоками", непрерывно меняя свою форму и поочередно приближаясь то к одному, то к другому "блоку". Объект является осциллирующим (период 30) и относится к классу челноков (shuttle). По определению челнок - это осциллирующий объект, внутрення часть которого циркулирует между границами объекта туда и обратно.

     Интересно проследить эволюцию фигуры, которая находится внутри "пчелиной матки" без окружения из "блоков". Как показал эксперимент, такая фигура на 195-м ходу превращается в устойчивую комбинацию из 6 "блоков" и 2-х мигалок.

     На рис.6 представлена фигура, которая относится к классу фениксов -

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

     На рис.7 представлен полный цикл превращений объекта под названием "большой бакен" (big beacen), период которого составляет 8. 

     Осциллирующих объектов, подобных представленным на рис.4-7, существует огромное множество. Исследование "Жизни" с помошью тако 3aо мощного и удобного инструмента, как ЭВМ (вспомним, какими они были в начале Жизни - БЭСМ-6, IBM-360,...), позволило обнаружить и исследовать не только периодические объекты, но также и объекты, основным свойством которых является перемещение в пространстве.

 
Не только живем, но и движемся

     Одним из классов объектов Жизни являются так называемые космические корабли (spaceship). Космический корабль - это конечный объект игры "Жизнь", который воссоздается или появляется снова в своем начальном виде через определенное числа поколений, однако при этом изменяет свое пространственное положение в некотором направлении, т.е. движется. Это движение называется также трансляцией объекта.

     Трансляция объектов (или попросту перемещение) может происходить как ортогонально (вверх-вниз), так и диагонально (в любом из четырех направлений). Количество генераций между циклическим появлением обекта называется периодом космического корабля, по аналогии с периодом стационарного колебания. Скорость пермещения объекта по полю определяется, количеством шагов, которое необходимо для того, чтобы транслируемый объект принял свою исходную форму и расстоянием, на которое он переместился от своего исходного состояния. Максимальная (и естственно, недостижимая) скорость, с которой может перемещаться объект, называется скоростью светаи обозначается символом "с".

    Первые космические корабли были найдены вскоре после сотворения "Жизни" Конвеем. В порядке возрастания весовых категорий, а вес определяется минимальным числом активных ячеек для данного типа корабля, на первое место необходимо поставить корабль, который называется планером (glider).

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

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

«Святая троица»

      Среди многочисленных представителей группы космических кораблей можно отметить небольшое семейство простых космических кораблей,  cостоящее из 3-х объектов, получивших соответственно название легкий, средний и тяжелый космические корабли (lightweight, middleweight, heavyweight spaseship - LWSS, MWSS, HWSS). 

   В отличие от планера  космические корабли перемещаются в пространстве ортогонально (в данном случае - слева направо). Ниже представлен полный цикл перемещения объекта HWSS. На третьем фрагменте видно, что космический корабль повторяет себя, однако в виде зеркального отражения. Еще через два шага его исходная форма полностью восстанавливается. При этом можно заметить, что за 4 шага корабль переместился вправо на две клетки, что соответствует скорости v=c/2. 

 
Псевдокосмические корабли

     Глядя на космические корабли LWSS, MWSS и HWSS можно было бы предположить, что существует некий простой закон, согласно которому можно легко строить такие корабли неограниченной длины. Например, космический корабль длины 7 мог бы выглядеть следующим образом:
   Однако, такие конструкции, хотя внешне и напоминают космические корабли, на самом деле таковыми не являются. В этом очень легко убедиться. Оказывается, что космические корабли "без эскорта" не могут занимать в длину больше шести клеток и "разваливаются на части" в процессе движения.

     Конвей обнаружил, что более длинным кораблям, которые он назвал сверхтяжелыми, для их устойчивости необходим эскорт из двух или более кораблей меньших размеров. На рисунке приведен  Сверхтяжелый Космический Корабль длиной в 12 ячеек, который эскортируется двумя тяжелыми космическими кораблями (HWSS). 
Скорость объекта v=c/2, как и для обычных космических кораблей. Следует отметить, что обведенные на рисунке фишки, которые являются принадлежностью нижнего HWSS, не являются обязательными. В процессе трансляции корабль теряет эти элементы.
      Этот корабль является устойчивой конструкцией, перемещающейся в пространстве вместе со своей "командой".

     Для более длинных кораблей необходима целая флотилия эскорирующих кораблей. Конвей вычислил, что сверхтяжелый корабль длиной в 100 клеток требует эскорта, состоящего из 33 кораблей.

 
Планеры и планерные ружья

     Поскольку существовали объекты, которые в процессе эволюции спонтанно генерировали планеры, возникла идея создания объекта, который мог бы сам генерировать эти планеры - некоего планерного ружья (glider gun).

     Первое планерное ружье было изобретено Биллом Госпером (Bill Gosper) в 1970 г., и явилось первым примером объекта Жизни с неограниченно возрастающим числом элементов.Планерное ружье Госпера (Рис.13) продуцировало из себя (периодически выстреливало) планеры с периодом в 30 шагов. Следует отметить, что тут же был придуман объект, который эти самые планеры поглощал. Объект назвали просто и без претензий - "поглотитель планеров" и разместили на определенном расстоянии от ружья. Первым поглотителем планеров оказался уже знакомый нам пентадекатрон. Поглощая планеры объект вовсе не разрастался, как это было бы с объектами биологической эволюции, а снова приходил в исходное состояние. 

      Пентадекатрон является динамическим поглотителем планеров и его форма постоянно меняется от шага к шагу с периодом 15. Поэтому расположение этого поглотителя по отношению к ружью Госпера имеет огромное значение, так как процесс поглощения происходит лишь при определенном взаимном расположении поглотителя и подлетающего планера.

    На рис.14. приведен пример генерации и поглощения планеров другой разновидностью поглотителей - стационарным поглотителем. На рисунке чуть ниже ружья можно увидеть планер, который из него вылетел, а в правом нижнем углу рисунка - один из стационарных поглотителей планеров. Данный стационарный поглотитель, в отличие от такого динамического поглотителя, как пентадекатрон, не меняет свою форму вплоть до момента подлета к нему планера. Когда планер приближается на достаточно близкое расстояние к поглотителю, он проникает в него и бесследно растворяется. Одним из достаточно простых поглотителей является также фигура, называемая «пожиратель» (Eater) (Рис.2). Это наиболее простая стационарная фигура, выполняющая функции поглощения планеров.

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

Вдохнем "Жизнь" в РС

     Вспомнив, как выручала эта игра на скучных лекциях в институте (хотя такие парные игры как крестики-нолики по пять в ряд и японская игра "го" привлекали не меньше энтузиастов), автор решил написать простую программу для РС, чтобы воочию увидеть процесс "Жизни" на экране компьютера. Причина такого решения заключалась в том, что эволюция фигур, собранных на шахматной доске или специально нарисованном поле, как показал опыт, происходит слишком медленно, неэффективно и чревата ошибками. 

     Первая версия программы была написана в образовательных целях на языке Turbo Pascal. Автор счел возможных все-же привести версию программы на Borland C/C++. Программа сознательно сделана очень простой. Она формирует игровое поле размера NxN клеток, позволяет нарисовать любой начальный объект используя курсор для перемещения по экрану и клавишу пробела для создания фишки. Клавиши "Delete" и "Backspace" удаляют ошибочно нарисованный элемент. Перемещение к левой и правой границе поля осуществляется клавишами "Home" и "End", а к верхней и нижней - клавишами "PageUp" и "PageDown".

     Запуск в автоматическом режиме прозводится по нажатии "Enter". Запуск в пошаговом режиме - "Ctrl Enter". Для пошагового выполнения используется клавиша "Пробел". Выход из игры - по "Esc".

     На листинге приведена одна из основных функций программы - функция Step_Game(), которая выполняет анализ состояния ячеек игрового поля, определяет места рождения новых фишек, отмечает гибнущие фишки, а также рисует на экране новые фишки и удаляет "погибшие".

     В заголовочном файле "evolut.h" определена структура игрового поля (struct base), а также прототипы функций. 

     Переменная field определяет игровое поле в виде матрицы размера NxN. В начале игры происходит выделение памяти под двойной указатель char** field, тем самым формируется двумерный массив, предназначенный для хранения состояния ячеек игрового поля. В начальном состоянии все ячейки поля обнулены - field[j][i]==0.

     Структура basepar определяет характеристики игрового поля и заполняется в фунциях main() и Num(). 

     Функция Step_Game() вызывается после установки начальной конфигурации, т.е. формирования на поле некоторой начальной фигуры. Ячейки, заполненные фишками принимают значения field[j][i]=1. В течении каждого цикла игры функция Step_Game() анализирует состояние игрового поля (матрицу field[j][i]) за три прохода.

     При первом проходе игрового поля происходит просмотр всех ячеек (переменная field). Завершающий оператор этого прохода 

if (summa==3) filed [j][i]=2;

определяет, что если ячейка граничит ровно с тремя активными ячейками, то на очередном шаге игры на ней должна быть установлена фишка. Сразу установить фишку (присвоить field[j][i]=1) в данной ячейке нельзя потому, что при проходе производится анализ окрестности каждой ячейки (8 соседних ячеек) и новорожденная ячейка может повлиять на подсчет количества соседей для других ячеек, что приведет к ошибке.

     Второй проход предназначен для определения кандидатов на вымирание. Если такие кандидаты найдены (заполненная ячейка одинока или соседствует больше, чем с 3 активными ячейками), то выпоняется оператор

if ( (summa<2)||(summa>3) ) field [j][i]=3;

     При третьем проходе игрового поля осуществляется "истинное" рождение и умирание фишек. При этом, происходит замена временных значений переменной field (2 и 3) на постоянные (для данного шага игры) значения (0 и 1):

if (field[j][i]==2) field[j][i]=1;

if (field[j][i]==3) field[j][i]=0;

     Одновременно происходит прорисовка элементов игрового поля. Для этого используется функция Draw_Element(), которой передается цвет, которым закрашивается ячейка. Если фишку необходимо удалить, то цвет должен совпадать с цветом фона (basepar.field_color). Если необходимо прорисовать новую фишку, то цвет устанавливается равным активному цвету элемента (basepar.el_color).

     Полное описание Игры с исходными текстами программ доступно в электронной версии журнала, а также на данной Web-странице.

     Продукт является бесплатным и открыт автором для доработки и усовершенствования. Общий размер файлов в архиве составляет около 30 Кбайт. Автор c благодарностью примет любые замечания и мнения,  равно как и пожелания вступить в клуб любителей игры "Жизнь", открываемый при редакции журнала "Компьютеры+Программы".