Визуальное моделирование динамических процессов на примере простого клеточного автомата игры «Жизнь»

Изучая эволюцию долгожителей наподобие r-пентамино, Конуэй иногда пользуется вычислительной машиной, устройство которой позволяет выводить выходные данные на экран и таким образом наблюдать все изменения, происходящие на игровом поле. Без программы, которую написали М. Дж. Т. Гай и С. Р. Бурн, многие особенности игры были бы обнаружены лишь с большим трудом. Эволюция r-пентамино была прослежена до конца с помощью компьютерных вычислений. Она завершается лишь после тысяча сто третьего хода. Шесть возникших на доске планеров удаляются от центра на всё большее и большее расстояние (находятся за пределами рисунка), и, в конце концов, вокруг бывшего пентамино (показано красным цветом) остаются четыре мигалки, один корабль, одна лодка, один каравай, четыре улья и восемь блоков.

 

 

Рис.17. Эволюция r-пентамино

В качестве простых упражнений проследим до конца эволюцию двух фигур: латинского креста и буквы „Н“.

 Если перекладину в  букве „Н“ поднять на одну  клетку вверх, чтобы получились  ворота (или, как называет эту  конфигурацию Конуэй, прописная буква «пи»), то произойдут совершенно неожиданные изменения. В противоположность букве „Н“, эволюция которой заканчивается быстро, ворота оказываются весьма долгоживущей конфигурацией. Лишь после 173 ходов она распадается на 5 мигалок, 6 блоков и 2 пруда.

 

 

Рис.18. Латинский крест и буква H

 

Также легко проследить эволюцию вертушки, бакена, часов и жабы.

 

 

Рис.19. Вертушка, бакен, часы и жаба

 

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

Конуэй проследил эволюцию всех элементов гексамино и всех элементов гептамино, за исключением семи.

Одним из самых замечательных  открытий Конуэя следует считать конфигурацию из 5 фишек − планер.

 

 

Рис.20. Планер (glider)

 

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

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

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

 

Рис.21. Космические корабли

 

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

 

 

Рис. 22. Тяжелые космические корабли

 

Восьмёрка — это периодически восстанавливающая себя конфигурация, открытие которой принадлежит Нортону. Она не только по форме напоминает восьмёрку, но и имеет период, равный восьми.

 

 

Рис.23. Восьмерка

Следующая конфигурация называется пульсар СР 48-56-72. Она также периодически восстанавливает себя через каждые три хода. Начальное состояние пульсара образовано 48 фишками; на втором этапе число фишек возрастает до 56, а на третьем — до 72, после чего пульсар снова возвращается в исходное состояние, а число фишек понижается до 48.

 

 

Рис.24. Пульсар

 

 Пульсар образуется  после 32 ходов из элемента гептамино, имеющего вид растянутой буквы П: горизонтального ряда из пяти фишек, у которого под первой и последней фишкой располагается ещё по одной фишке.

Конуэй исследовал эволюцию всех горизонтальных рядов из n фишек вплоть до n = 20. Мы уже знаем, что происходит при n < 5. Пятиклеточный ряд переходит в навигационные огни, шестиклеточный исчезает, из семиклеточного получается пасека, из восьмиклеточного — четыре улья и четыре блока, девятиклеточный ряд превращается в два комплекта навигационных огней, а ряд, состоящий из десяти фишек, переходит в пентадекатлон − периодически воспроизводящую себя конфигурацию с периодом, равным пятнадцати. Ряд из одиннадцати фишек эволюционирует, превращаясь в две мигалки; двенадцатиклеточный ряд переходит в два улья, тринадцатиклеточный — в две мигалки. Если ряд состоит из 14 или 15 фишек, то он полностью исчезает, а если фишек 16, то получается большой набор навигационных огней, состоящий из восьми мигалок. Эволюция семнадцатиклеточного ряда заканчивается четырьмя блоками; ряды, состоящие из 18 или 19 фишек, полностью исчезают с доски, а эволюция двадцатиклеточного ряда завершается двумя блоками.

Конуэй также исследовал эволюцию рядов, образованных пятиклеточными группами, отделенными друг от друга одной свободной клеткой. Ряд 5-5 после двадцать первого хода превращается в пульсар СР 48-56-72. Ряд 5-5-5 переходит в четыре блока и четыре мигалки; в результате эволюции ряда 5-5-5-5 получаются четыре пасеки и четыре мигалки; ряд 5-5-5-5-5 заканчивает свои превращения «эффектно разбросанными» по доске восемью планерами и восемью мигалками. Затем планеры попарно сталкиваются и, разрушаясь, превращаются в восемь блоков. Ряд, состоящий из шести групп по пяти клеток в каждой (5-5-5-5-5-5), превращается в четыре мигалки, а эволюция следующего ряда 5-5-5-5-5-5-5, по мнению Конуэя, представляет «замечательное зрелище, если наблюдать её на экране вычислительной машины». Конфигурация после 323 ходов стабилизируется, превратившись в четыре навигационных огня, восемь мигалок, восемь караваев, восемь ульев и четыре блока, то есть в конфигурацию, насчитывающую 192 фишки.

 

 

Рис.25. Эволюция ряда 5-5-5-5-5-5-5

 

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

Стоит заметить, что ряды типа n-n-n-... интересны лишь тогда, когда n равно по крайней мере 5, поскольку при меньших значениях n группы из n фишек не взаимодействуют друг с другом. Ряды 1-1-1-... и 2-2-2-... сразу же исчезают. Ряд 3-3-3-... состоит из одних лишь мигалок, а ряд 4-4-4-... на втором ходу переходит в устойчивый ряд ульев.

В ноябре 1970 года Конуэю пришлось выдать обещанную премию. Группа математиков из Массачусетского технологического института сумела построить ружьё, стреляющее планерами! Каждые 30 ходов из ружья вылетает планер. С появлением нового планера число фишек на доске увеличивается на 5, следовательно, происходит неограниченный рост популяции.

 

 

Рис.26. Планерное ружье

Планерное ружьё позволило  его создателям совершить и много  других замечательных открытий. Например, на рисунке показано столкновение 13 планеров. Рассыпавшись на части, они  превращаются... в планерное ружьё!

 

 

Рис. 27. Столкновение 13 планеров

 

Та же группа исследователей обнаружила пентадекатлон − конфигурацию, способную «поглотить» сталкивающийся с ней планер.

 

Рис.28. Пентадекатлон

 

Вейнрайт, изобретатель планерного ружья, является автором многих любопытных исследований. Разместив случайным образом 4800 фишек в ячейках квадрата размером 120×120 (с плотностью фишек, равной 1/3), он проследил их эволюцию на протяжении 450 поколений. Плотность этого первообразного студня, как его называет Вейнрайт, сильно уменьшилась и стала равняться всего лишь 1/6. Исчезнут ли все фишки в конце концов или же будут, как утверждает Вейнрайт, продолжать просачиваться из поколения в поколение с некоторой минимальной постоянной плотностью — ответ на этот вопрос пока не известен. На протяжении 450 поколений удалось проследить появление 42 «короткоживущих» планеров.

Вейнрайту удалось обнаружить 14 конфигураций, которые после первого хода превращаются в один или несколько планеров. Например, из первой фигуры, показанной на рисунке ниже, получается один планер. Буква „Z“ (вторая конфигурация) после 12 ходов превращается в 2 планера, которые движутся в противоположных направлениях. Если два планера следуют наперерез друг другу (третья конфигурация), то после четвёртого хода все фишки с доски исчезают. Если два лёгких космических корабля движутся опасным курсом, ведущим к столкновению (последняя фигура), то после седьмого хода доска оказывается абсолютно пустой, как и в случае столкновения двух планеров.

 

 

Рис. 29. Конфигурации, образующие планеры

 

Вейнрайт, кроме того, экспериментировал с разными бесконечными полями, заполняя их правильными устойчивыми фигурами. Такие конфигурации он назвал агарами. (Агар − продукт, получаемый из некоторых морских водорослей. Хорошо растворяется в горячей воде, образуя после охлаждения плотный студень. Применяется при разведении бактерий в качестве твердой среды для выращивания микроорганизмов.)

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

 

 

Рис.30. Вирус

 

 Вирус постепенно поглотит  внутри агара все активные участки, оставив на поле пустую двусторонне симметричную область (грубо говоря, восьмиугольной формы). Её граница непрерывно расширяется во все стороны со скоростью света, и не исключено, что это расширение будет происходить бесконечно долго.

 

Рис.31. Разрушение агара вирусом

 

 

2. ПРАКТИЧЕСКАЯ ЧАСТЬ

 

МОДЕЛИРОВАНИЕ ПЛАНЕРНОГО РУЖЬЯ ГОСПЕРА (GOSPER’S GLIDER GUN)

 

N = 50;

X = zeros(N,N);

 colormap gray;

 figure(1); imagesc(1 – X); axis image; drawnow;

but=1;

 

 while but==1

     figure(1);

     [a, b, but] = ginput(1);

     yi = round(a);

     xi = round(b);

 

     if but==1

         if X(xi, yi)

             X(xi, yi) = 0;

         else

              X(xi, yi) = 1;

         end

     end

 

     figure(1); imagesc(1 – X); axis image; colormap gray; drawnow;

 end

 

N = length(X);

T = 200;

 

figure(1); imagesc(X); axis image; colormap gray; drawnow;

for t=1:T

    neighbors = circshift(X, [1, 0]) + circshift(X, [-1, 0]) +  circshift(X, [0, 1]) +  circshift(X, [0, -1]) + …

    circshift(X, [1, 1]) + circshift(X, [-1, 1]) + circshift(X, [1, -1]) + circshift(X, [-1, -1]);

    X(find(((neighbors > 3) | (neighbors < 2))  & X)) = 0;

    X(find((neighbors == 3) & ~X)) = 1;

    figure(1); imagesc(1-X); axis image; colormap gray;

    title(sprintf(‘Итерация: %d, Плотность: %f’, t, sum(sum(X))/(N*N)));

    drawnow;

 

end

 

 

 

Рис. 32

 

ВЫВОДЫ

 

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