Игра «Жизнь»

Последнее общение с 10 классом показало, что школьники не читают текстов, составляющих непременную часть математического образования. Например, оказалось, что 10-классники не знакомы с замечательной игрой «Жизнь». Ликвидирую этот пробел открытием новой рубрики в этом блоге: «математическое просвещение». Сегодня вниманию читателей предлагается выдержка из книги Мартина Гарднера «Математические головоломки и приключения» посвящённая игре «Жизнь».

 

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

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

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

 

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

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

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

 

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

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

 

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

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

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

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

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


Рис.1. Эволюция пяти триплетов. 

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

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


Рис.2. Эволюция пяти тетрамино. 

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


Рис.3. Наиболее часто встречающиеся устойчивые конфигурации.

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


Рис.4. Пентамино в форме буквы «r» (a)
и упражнения для читателей.
 

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

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

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

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


Рис.5. «Глайдер». 

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

Три изящных фигуры, изображенные на рис. 6, были открыты самим Конуэем и его сотрудниками. «Пасека» (а) представляет собой устойчивую конфигурацию, в которую после 14 ходов превращается горизонтальный ряд из семи фишек. «Блок» (квадрат) размером 5Х5 после первого же хода превращается в конфигурацию, которая возникает лишь на четвертом этапе эволюции ряда из семи фишек. Поэтому «блок» становится «пасекой» после 11 ходов. «Восьмерка» (б) — это периодически восстанавливающая себя конфигурация, открытие которой принадлежит Нортону. Она не только по форме напоминает восьмерку, но и имеет период, равный восьми. Конфигурация, изображенная на рис. 6, в, называется «пульсар СР 48-56-72». Она также периодически восстанавливает себя через каждые три хода. Состояние пульсара, изображенное на рисунке, образовано 48 фишками; на втором этапе число фишек возрастает до 56, а на третьем — до 72, после чего пульсар снова возвращается в исходное состояние, а число фишек понижается до 48. Этот пульсар образуется после 32 ходов из элемента гептамино, имеющего вид растянутой буквы «П», т. е. горизонтального ряда из пяти фишек, у которого под первой и последней фишкой располагается еще по одной фишке.


Рис.6. Три замечательные конфигурации — устойчивая (а) и периодически пульсирующие (б и в). 

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

Конуэй исследовал также эволюцию рядов, образованных группами из n фишек, отделенными друг от друга одной пустой клеткой. При n = 5 фишки начинают взаимодействовать друг с другом, образуя различные интересные конфигурации. Бесконечные ряды с n = 1 или n = 2 исчезают после первого же хода, а ряд вида …-3-3-3-… превращается в ряд из одних лишь «мигалок». Если же n = 4, то соответствующий ряд переходит в устойчивый ряд «ульев».

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

 

Пост получился немного длинным, но, надеюсь, полезным. Домашнее задание — написать программу, моделирующую игру «Жизнь».

Реклама

1 комментарий (+add yours?)

  1. Владимир
    Янв 14, 2012 @ 12:15:42

    О! АВТОМАТЫ!!!
    Динамические системы с конечным числом состояний и счетным временем — вообще вещь интересная. В данном случае это так называемый клеточный автомат (см. http://ru.wikipedia.org/wiki/Клеточный_автомат — там кстати на иллюстрации глайдерная пушка!).

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

    Я в 1990 г (более 20 лет назад!) написал прогу (боже! на ассемблере!) для MSDOSа которая моделирует такой автомат. Там была возможность (интерфейс на турбопаскале!) задать правило и задать начальную живую колонию. Экран 800х600 был тороидально замкнут.

    Красота получилась недецкая! Там и рост кристаллов и перколяция и, конечно, «жизнь». Кроме «конвеевской» я нашел еще несколько!

    Что? Есть повод поискать эту прогу? Вдруг сохранилась???

    В.В.

    Ответить

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход /  Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход /  Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход /  Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход /  Изменить )

Connecting to %s

%d такие блоггеры, как: