Главная   Гостевая   Галерея   Разное   Ссылки   Новости   Магазин

 

 

Теория катастроф   Самоорганизованная критичность   Игра ЖИЗНЬ

 

 

 
 
 

Теории.



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

Извините, Ваш браузер не поддерживает Java.
 
     



 
 
 

Эта картинка создана при помощи апплета, иллюстрирующего математическую игру, являющуюся детищем Джона Хортона Конвея (Conway), американского математика. Сам он назвал эту игру "Жизнь", поскольку возникающие в процессе игры ситуации очень похожи на реальные процессы, происходящие при зарождении, развитии и гибели колонии живых организмов. Игра происходит на большой (условно бесконечной) доске, разграфленной на клетки. Также необходимо много плоских фишек двух цветов. Можно рисовать ходы на бумаге. (Заметим, что игра возникла задолго до появления персональных компьютеров).

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

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

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

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

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

погибает на третьем ходу

рис.1а

погибает на третьем ходу

рис.1б

погибает на третьем ходу

рис.1в

на втором ходу образуется устойчивая конфигурация (блок)

рис.1г

на втором ходу образуется "мигалка" (устойчивая конфигурация)

рис.1д

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

устойчивый блок

рис.2а

на третьем ходу образуется "улей"

рис.2б

на третьем ходу образуется "улей"

рис.2в

на четвертом ходу образуется "улей"

рис.2г

на десятом ходу образуются четыре "флип-флопа"

рис.2д

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

рис.3
(вся конфигурация носит название "навигационные огни"). "Ульи" и "навигационные огни" возникают в игре довольно часто. На рисунке 3 показаны двенадцать наиболее часто встречающихся устойчивых конфигураций

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

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

Одной из самых замечательных конфигураций следует считать фигуру из пяти фишек,

рис.5
называемую "планер" и демонстрирующую эффект скользящей симметрии (отсюда и название фигуры: glide - скользить, glider - планер). На четвертом ходу планер переходит сам в себя, сдвинувшись на одну клетку (см. рисунок 5). То есть скорость планера равна одна четвертая скорости света. Планер является простейшей фигурой со скользящей симметрией. Удалось обнаружить еще три подобных, но более сложных конфигурации (см. рисунок 6). Конвей назвал их "космическими кораблями",

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

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

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

Было открыто много других периодически воспроизводящихся конфигураций.

рис.8

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

Итак, мы рассмотрели некоторые типичные фигуры, возникающие в процессе игры. Другим принципиальным вопросом является процесс развития конфигурации, полученной в результате случайного расположения фишек на доске. Такая ситуация проиллюстрирована с помощью java-апплета, созданного Фабио Цусси (Fabio Ciucci) (см. рисунок в начале статьи). На рисунках 10а и 10б показаны начальные конфигурации для разных коэффициентов плотности.

рис.10а

рис.10б

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

Согласно наблюдениям, плотность "первобытного студня" после нескольких десятков ходов сильно уменьшается, и игровое поле разбивается на несколько слабо взаимодействующих активных участков, между которыми находятся устойчивые конфигурации, описанные выше (см. рисунок 3). Взаимодействие между активными участками, как правило, осуществляется "планерами". Через несколько сотен ходов все активные участки вырождаются. В качестве причины можно предположить, что поскольку игровая площадь мала, влияние объекта на самого себя весьма существенно. Происходит эффект отрицательной обратной связи: чем активней объект, тем сильнее он действует на себя, подавляя свою же активность. Если увеличить размер апплета при неизменной плотности расположения фишек, время жизни активных конфигураций увеличивается, так как влияние фигур на самих себя уменьшается. Ниже приводится ссылки на апплет размером 400х400 (против апплета 180х200 в начале страницы) и апплет размером 40х40 для сравнения.
А также интерактивный апплет, на котором Вы сможете поставить простейшие эксперименты (установка и удаление организмов одним кликом).


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

А.Алфёров (по материалам работ М.Гарднера)

 
     

Наверх

Copyright © 2004-2015 Erender Inc. All Rights Reserved.