Рис.1. Эволюция пяти триплетов.
| Мартин Гарднер. Игра Жизнь > |
Предисловие Игра "Жизнь". Часть I Ответы Дополнения Игра "Жизнь". Часть II Игра "Жизнь". Часть III Литература | Вернуться |
Большая часть работ известного математика Дж. X. Конуэя относится к области чистой математики. Например, в 1967 г. он открыл новую группу — ее иногда называют "созвездием Конуэя" — включавшую в себя в качестве подгрупп все известные к тому времени "спорадические" группы, кроме двух, ("Спорадическими" эти группы были названы потому, что они не укладывались ни в какую известную классификацию.) Открытие Конуэя имело первостепенное значение не только для теории групп, но и для теории чисел. Оно тесно связано с другим, более ранним открытием Дж. Лича, обнаружившего необычайно плотную упаковку единичных сфер в пространстве 24 измерений. Хотя каждая сфера в этой упаковке касается 196 560 других, все же, как заметил Конуэй, между сферами "остается еще много места".
Помимо серьезных исследований, Конуэй увлекается также занимательной математикой. В этой области ему принадлежит немало работ, однако публикует он свои "занимательные" результаты чрезвычайно редко. Одним из исключений такого рода была статья Конуэя о "стеганом одеяле миссис Перкинс", посвященная одной задаче на разрезание, которая рассматривалась ранее в моей книге "Математический карнавал" ("Mathematical Carnival"), Другой его находкой явилась топологическая игра "Спрут", которую Конуэй придумал вместе с М. С. Патерсоном. Она также рассматривалась в одной из глав упомянутой мной книги.
Настоящая же глава посвящена самому знаменитому детищу Конуэя-игре, которую сам Конуэй назвал "Жизнь". Для игры "Жизнь" вам не понадобится партнер — в нее можно играть и одному. Возникающие в процессе игры ситуации очень похожи на реальные процессы, происходящие при зарождении, развитии и гибели колоний живых организмов. По этой причине "Жизнь" можно отнести к быстро развивающейся категории так называемых "моделирующих игр" — игр, которые в той или иной степени имитируют процессы, происходящие в реальной жизни. Для игры "Жизнь", если не пользоваться ЭВМ, вам понадобится довольно большая доска, разграфленная на клетки, и много плоских фишек двух цветов (например, просто несколько наборов обычных шашек небольшого диаметра или одинаковых пуговиц двух цветов). Можно также воспользоваться доской для игры в го, но тогда вам придется раздобыть маленькие плоские шашки, которые свободно умещаются в ячейках этой доски. (Обычные камни для игры в го не годятся потому, что они не плоские.) Можно также рисовать ходы на бумаге, но значительно проще, особенно для начинающих, играть, переставляя фишки или шашки на доске.
Основная идея игры состоит в том, чтобы, начав с какого-нибудь простого расположения фишек (организмов), расставленных по различным клеткам доски, проследить за эволюцией исходной позиции под действием "генетических законов" Конуэя, которые управляют рождением, гибелью и выживанием фишек. Конуэй тщательно подбирал свои правила и долго проверял их "на практике", добиваясь, чтобы они по возможности удовлетворяли трем условиям:
Короче говоря, правила игры должны быть такими, чтобы поведение популяции было достаточно интересным, а главное, непредсказуемым.
Генетические законы Конуэя удивительно просты. Прежде чем мы их сформулируем, обратим внимание на то, что каждую клетку доски (которая, вообще говоря, считается бесконечной) окружают восемь соседних клеток: четыре имеют с ней общие стороны, а четыре другие — общие вершины. Правила игры (генетические законы) сводятся к следующему:
Важно понять, что гибель и рождение всех "организмов" происходят одновременно. Вместе взятые, они образуют одно поколение или, как мы будем говорить, один "ход" в эволюции начальной конфигурации. Ходы Конуэй рекомендует делать следующим образом:
Проделав все операции, вы получите первое поколение в эволюции первоначальной конфигурации. Аналогичным образом получаются и все последующие поколения. Теперь уже ясно, для чего нам нужны фишки двух цветов: поскольку рождение и гибель "организмов" происходят одновременно, новорожденные фишки никак не влияют на гибель и рождение остальных фишек, и поэтому, проверяя новую конфигурацию, необходимо уметь отличать их от "живых" фишек, перешедших из предыдущего поколения. Допустить ошибку, в особенности, если вы играете впервые, очень легко. Со временем вы будете делать все меньше и меньше ошибок, однако даже опытные игроки должны очень внимательно проверять каждое новое поколение перед тем, как снимать с доски погибшие фишки и заменять черными фишками новорожденные белые.
Начав игру, вы сразу заметите, что популяция непрестанно претерпевает необычные, нередко очень красивые и всегда неожиданные изменения. Иногда первоначальная колония организмов постепенно вымирает, т. е. все фишки исчезают, однако произойти это может не сразу, а лишь после того, как сменится очень много поколений. В большинстве своем исходные конфигурации либо переходят в устойчивые (последние Конуэй называет "любителями спокойной жизни") и перестают изменяться, либо навсегда переходят в колебательный режим. При этом конфигурации, не обладавшие в начале игры симметрией, обнаруживают тенденцию к переходу в симметричные формы. Обретенные свойства симметрии в процессе дальнейшей эволюции не утрачиваются, а симметрия конфигурации может лишь обогащаться.
Конуэй высказал гипотезу, согласно которой не существует ни одной начальной конфигурации, способной беспредельно расти. Иначе говоря, любая конфигурация, состоящая из конечного числа фишек, не может перейти в конфигурацию, у которой число фишек превосходило бы некий конечный верхний предел. Это, наверное, наиболее глубокая и самая сложная задача, возникающая в игре "Жизнь". В свое время Конуэй предлагал премию в 50 долларов тому, кто до конца 1970 г. первым докажет или опровергнет его гипотезу. Опровергнуть предположение Конуэя можно было бы, например, построив конфигурацию, к которой, следуя правилам игры, все время приходилось бы добавлять новые фишки. К ним можно отнести, в частности, "ружье" (конфигурацию, которая через определенное число ходов "выстреливает" движущиеся фигуры вроде "глайдера", о котором мы еще будем говорить) или "паровоз, пускающий дым из трубы" (движущаяся конфигурация, оставляющая за собой "клубы дыма"). Результаты соперничества за объявленный Конуэем приз обсуждаются в следующей главе.
Рассмотрим теперь, что же происходит с некоторыми простыми конфигурациями. Одиночная фишка, а также любая пара фишек, где бы они ни стояли, очевидно, погибают после первого же хода.
Исходная конфигурация из трех фишек (мы будем называть ее триплетом), как правило, погибает. Выживает триплет лишь в том случае, если, по крайней мере, одна фишка граничит с двумя занятыми клетками. Пять триплетов, не исчезающих на первом же ходу, изображены на рис. 1. (При этом ориентация триплетов, т. е. как они расположены на плоскости — прямо, "вверх ногами" или косо, не играет никакой роли.) Первые три конфигурации (а, б, в) на втором ходу погибают. Относительно конфигурации в заметим, что любой диагональный ряд фишек, каким бы длинным он ни оказался, с каждым ходом теряет стоящие на его концах фишки и, в конце концов, совсем исчезает. Скорость, с которой шахматный король перемещается по доске в любом направлении, Конуэй называет "скоростью света". (Причины этого станут понятны в дальнейшем.) Пользуясь этой терминологией, можно сказать, что любой диагональный ряд фишек распадается с концов со скоростью света.
Конфигурация г на втором ходу превращается в устойчивую конфигурацию — "блок" (квадрат размером 2Х2). Конфигурация д служит простейшим примером так называемых "флип-флопов" (кувыркающихся конфигураций, возвращающихся в исходное состояние через каждые два хода). При этом она попеременно превращается то в вертикальный, то в горизонтальный ряд из трех фишек. Конуэй называет этот триплет "мигалкой".
На рис. 2 изображена эволюция пяти тетрамино (четыре клетки, из которых состоит элемент тетрамино, связаны между собой ходом ладьи). Как мы уже видели, квадрат а относится к категории "любителей спокойной жизни". Конфигурации б и в после второго хода превращаются в устойчивую конфигурацию, называемую "ульем". Отметим попутно, что "ульи" возникают в процессе игры довольно часто. Тетрамино, обозначенное буквой г, также превращается в улей, но на третьем ходу. Особый интерес представляет тетрамино д, которое после девятого хода распадается на четыре отдельные "мигалки", Вся конфигурация носит название "навигационные огни", или "светофоры". "Светофоры" относятся к разряду флип-флопов и возникают в игре довольно часто.
На рис. 3 представлены 12 наиболее часто встречающихся конфигураций из числа "любителей спокойной жизни" (т. е. устойчивых конфигураций).
Предоставляем читателю самостоятельно поэкспериментировать на досуге с двенадцатью фигурами пентамино (фигуры, состоящие из пяти фишек, связанных между собой так, что их клетки можно обойти ходом ладьи) и посмотреть, во что они превращаются. Оказывается, что пять из них на пятом ходу погибают, две быстро переходят в устойчивые конфигурации из семи фишек, а четыре после небольшого числа ходов превращаются в "навигационные огни". Единственным исключением в этом смысле является элемент пентамино, имеющий форму буквы r (рис. 4), превращения которого заканчиваются не столь быстро (превращения конфигурации считаются исчерпанными, если та исчезает, переходит в устойчивую конфигурацию или начинает периодически пульсировать). Конуэй проследил развитие r-образного пентамино вплоть до четыреста шестидесятого хода, после которого данная конфигурация распалась на множество "глайдеров". Конуэй пишет, что "от фигуры осталось множество мертвых (не изменяющихся) обломков и лишь несколько малых областей, в которых все еще теплилась жизнь, так что отнюдь не очевидно, что процесс эволюции должен происходить бесконечно долго". Судьба этой конфигурации подробно проанализирована в "Дополнении" к этой главе.
Изучая эволюцию подобного рода долгожителей, Конуэй иногда использует ЭВМ с дисплеем, на экране которого он может наблюдать все изменения, происходящие на игровом поле. Без машинной программы, которую составили М. Дж. Т. Гай и С. Р. Бурн, многие особенности игры могли бы быть обнаружены лишь с большим трудом.
В качестве простых упражнений я предлагаю читателям проследить до конца эволюцию следующих фигур, изображенных на рис. 4: "латинского креста", буквы "Н", "бакена", "часов", "жабы" и "вертушки". Последние три фигуры были обнаружены С. Нортоном. Проверить себя вы можете, заглянув в "Ответы".
Если перекладину в букве "Н" поднять на одну клетку вверх, чтобы получились "ворота" (или, как называет эту конфигурацию Конуэй, прописная буква "пи"), то произойдут совершенно неожиданные изменения. В противоположность букве "Н", эволюция которой заканчивается достаточно быстро, "ворота" оказываются весьма долгоживущей конфигурацией. Лишь после 173 ходов она распадается на пять "мигалок", шесть "блоков" и два "пруда". Конуэй проследил также эволюцию всех элементов гексамино и всех элементов гептамино, за исключением семи. При этом некоторые из элементов гексамино оказываются вовлеченными в эволюцию r-пентамино; например, этот элемент пентамино превращается в гексамино на первом же ходу.
Одним из самых замечательных открытий Конуэя следует считать конфигурацию из пяти фишек под названием "глайдер", изображенную на рис. 5. После второго хода "глайдер" немного сдвигается и отражается относительно диагонали. В геометрии такой тип симметрии называется "скользящим отражением", отсюда же и происходит название фигуры. В результате двух последующих ходов "глайдер" "выходит из пике", ложится на прежний курс и сдвигается на одну клетку вправо и на одну клетку вниз относительно начальной позиции. Выше уже отмечалось, что скорость шахматного короля в игре "Жизнь" принято называть скоростью света. Выбор Конуэя пал именно на этот термин из-за того, что в изображенной им игре большие скорости просто не достигаются. Ни одна конфигурация не воспроизводит себя достаточно быстро, чтобы двигаться с подобной скоростью. Конуэй также доказал, что максимальная скорость по диагонали составляет одну четверть скорости света. Поскольку "глайдер" воспроизводит сам себя после четырех ходов и при этом опускается на одну клетку по диагонали, то говорят, что он скользит по полю со скоростью, равной одной четвертой скорости света.
Конуэй также показал, что скорость любой конечной фигуры, перемещающейся по вертикали или по горизонтали на свободные клетки, не может превышать половину скорости света. Сумеет ли читатель самостоятельно найти достаточно простую фигуру, которая движется с такой скоростью? Напомним, что скорость движения определяется дробью, в знаменателе которой стоит число ходов, необходимых для воспроизведения фигуры, а в числителе — число клеток, на которое она при этом смещается. Например, если какая-нибудь фигура за каждые четыре хода передвигается на две клетки по вертикали или по горизонтали, повторяя свою форму и ориентацию, то скорость такой фигуры будет равна половине скорости света. Надо сказать, что поиски перемещающихся по доске фигур — дело чрезвычайно сложное. Конуэю известны всего четыре такие конфигурации, которые он называет "космическими кораблями". В их число входит уже известный нам "глайдер". ("Глайдер" считается "космическим кораблем" легчайшего веса, потому что все остальные корабли состоят из большего числа фишек.) Подробно об этих конфигурациях я расскажу в разделе "Ответы".
Три изящных фигуры, изображенные на рис. 6, были открыты самим Конуэем и его сотрудниками. "Пасека" (а) представляет собой устойчивую конфигурацию, в которую после 14 ходов превращается горизонтальный ряд из семи фишек. "Блок" (квадрат) размером 5Х5 после первого же хода превращается в конфигурацию, которая возникает лишь на четвертом этапе эволюции ряда из семи фишек. Поэтому "блок" становится "пасекой" после 11 ходов. "Восьмерка" (б) — это периодически восстанавливающая себя конфигурация, открытие которой принадлежит Нортону. Она не только по форме напоминает восьмерку, но и имеет период, равный восьми. Конфигурация, изображенная на рис. 6, в, называется "пульсар СР 48-56-72". Она также периодически восстанавливает себя через каждые три хода. Состояние пульсара, изображенное на рисунке, образовано 48 фишками; на втором этапе число фишек возрастает до 56, а на третьем — до 72, после чего пульсар снова возвращается в исходное состояние, а число фишек понижается до 48. Этот пульсар образуется после 32 ходов из элемента гептамино, имеющего вид растянутой буквы "П", т. е. горизонтального ряда из пяти фишек, у которого под первой и последней фишкой располагается еще по одной фишке.
Конуэй исследовал эволюцию всех горизонтальных рядов из 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 ходов превращается в четыре "мигалки", а эволюция следующего ряда, по замечанию Конуэя, "если наблюдать ее на экране дисплея, представляет собой совершенно изумительное зрелище". Окончательная судьба этой конфигурации прослеживается в "Дополнении".
