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

 

Эта простая динамика показывает интересное свойство реального движения машин: пробки на дорогах. Этот клеточный автомат показывает правило Вольфрама 184.

Клеточный автомат использует для целей моделирования линию  и одномерное соседство. Ячейки могут  быть в одном из трёх состояний: пустая ячейка (0), стоящая машина (1), движущаяся машина (2). Первоначально, машины располагаются  случайным образом на ячейках  линии. Состояние ячеек определяется в соответствии со следующим правилом:

 

n_i(t+1)=n_iⁱⁿ(t)(1-n_i(t))+ n_i(t) n_i^out(t),

 

где n_i(t) обозначает количество, занятое машинами (n_i=0: пустое место, n_i=1: место i занято машиной). n_iⁱⁿ(t) обозначает состояние исходной ячейки, т.е. той, из которой машина движется в ячейку i. Аналогично, n_i^out(t) определяет состояние ячейки назначения, т.е. той ячейки, в которую вы хотели бы попасть из текущей ячейки. Принцип определяет, что следующее состояние ячейки i равно 1, если присутствует машина и следующая ячейка занята или если сначала нет машины, а потом она перемещается в эту ячейку.

Автомобиль движется или  не движется в соответствии со своей  скоростью, переменная принимает случайные  значения на промежутке [0,1], которые изменяются на каждом временном шаге. Если машина имеет скорость, ниже чем пороговое значение, установленное в 0.05, потом она останавливается на один временной шаг. Когда машина достигает крайней левой ячейки своего ряда, она переносится на крайнюю правую ячейку решетки того же ряда и продолжает двигаться. Рис. 8а показывает пример обычного движения, где все машины двигаются справа налево на одну ячейку за шаг. Белые машины двигаются, серые машины стоят. На рис. 8б машины 1 и 2 стоят. Когда машина 1 стоит, все следующие за ней машины также стоят (так как нет пустых ячеек между ними) и становятся серыми. Машины впереди машины 1 продолжают двигаться влево, потому что предыдущая машина не стоит. Когда машина 2 стоит, за ней есть пустая ячейка. Именно поэтому следующие машины остаются белыми и продолжают двигаться влево, покрывая каждую пустую ячейку.

 

                                              а)                              б)

Рис. 8. Нормальный трафик (а) и трафик с автомобилями, которые не двигаются(б).

 

На рис. 9а показан другой пример нормального трафика. Машина, на которую указывает стрелка, останавливается и становится серой (рис. 9б). За ним есть пустая ячейка, поэтому все машины, которые следуют за ней, продолжают двигаться влево и остаются белыми.

 

                                              а)                               б)

Рис. 9. Нормальный трафик (а), а затем автомобиль останавливается (б).

 

И, наконец, последняя машина (рис. 10а) останавливается (и становится серой рис 10б). Все другие автомобили продолжают двигаться влево, покидая пустую ячейку впереди последней машины.

                                             а)                              б)

Рис.10. Нормальный трафик (а), а затем автомобиль останавливается (б)

 

Игру «Жизнь» рассмотрим в отдельной главе.

 

4. ИГРА «ЖИЗНЬ»

 

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

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

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

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

Короче говоря, правила  должны быть такими, чтобы поведение  популяции было непредсказуемым.

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

1. Выживание. Каждая фишка, имеющая вокруг себя две или три соседние фишки, выживает и переходит в следующее поколение.
2. Гибель. Каждая фишка, у которой больше трёх соседей, погибает, то есть снимается с доски из-за перенаселённости. Каждая фишка, вокруг которой свободны все соседние клетки или же занята всего одна клетка, погибает от одиночества.
3. Рождение. Если число фишек, с которыми граничат какая-нибудь пустая клетка, в точности равно трём (не больше и не меньше), то на этой клетке происходит рождение нового «организма», то есть следующим ходом на неё ставится одна фишка.

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

1. начать с конфигурации, целиком состоящей из черных фишек;
2. определить, какие фишки должны погибнуть, и положить на каждую из обреченных фишек по одной черной фишке;
3. найти все свободные клетки, на которых должны произойти акты рождения, и на каждую из них поставить по одной фишке белого цвета;
4. выполнив все эти указания, ещё раз внимательно проверить, не сделано ли каких-либо ошибок, затем снять с доски все погибшие фишки (то есть столбики из двух фишек), а всех новорожденных (белые фишки) заменить черными фишками.

Проделав все операции, вытекающие из генетических законов, вы получите первое поколение в эволюции первоначальной конфигурации. Аналогичным  образом получаются и все последующие  поколения. Теперь уже ясно, для чего нужны фишки двух цветов: поскольку  рождение и гибель «организмов» происходит одновременно, новорожденные (например, белые) фишки никак не влияют на гибель и рождение остальных (чёрных) фишек, и поэтому, проверяя новую конфигурацию, необходимо уметь отличать их от фишек, перешедших из предыдущего поколения. Допустить ошибку, в особенности, если вы играете впервые, очень легко. Со временем вы будете делать всё меньше и меньше ошибок, однако даже опытные  игроки должны очень внимательно  проверять каждое новое поколение  перед тем, как снимать с доски  погибшие фишки и заменять чёрными  фишками новорожденные белые.

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

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

Теперь посмотрим, что  происходит с некоторыми простыми конфигурациями.

Одна фишка, а также  любая пара фишек, где бы они ни стояли, очевидно, погибают после первого  же хода.

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

 

 

Рис. 11. Триплеты

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

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

Рассмотрим эволюцию пяти тетрамино (четыре клетки, из которых состоит элемент тетрамино, связаны между собой ходом ладьи).

 

 

Рис 12. Тетрамино

 

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

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

 

Рис.13. Навигационные огни

 

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

 

Рис. 14. Устойчивые конфигурации

 

Пасека является устойчивой конфигурацией из четырёх ульев, в которую после 14 ходов переходит  горизонтальный ряд из 7 фишек. Квадрат  размером 5×5 после первого же хода переходит в конфигурацию, которая  возникает лишь на четвёртом этапе  эволюции семиклеточного ряда. Поэтому квадрат 5×5 становится пасекой после 11 ходов.

Рис.15. Пасека

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

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

 

Рис.16. r-пентамино

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