26
Игра
«Жизнь»
И. Н. Клумова
— А может вы исчезать и появляться не так внезапно? — спросила Алиса. — А моу меня волова идем кругом.
— Хорошо, — сказал Ком и исчез—на этом раз очень медленно. Первые исчез кончик его хвоста, а последней—улыбка. Она долго парила в воздухе, когда все остальное уже пролало.
— Д-да, подумала Алиса. — Видала я комов без улыбок, но улыбка без кома! Такого я в жизни не встречала.
Льюис Кэрролл. «Алиса в стране чудес».
В октябряом номере журнала «Scientific American» за 1970 год появилось описание увлекательнейшей игры — «Жизнь», придуманной современным американским математиком Джоном Хортоном Конвеем. О ней прекрасно рассказано в книге известного американского специалиста в области заиматательной математики М. Гарднера. Игра эта очень не похожа на все остальные; лишь вычислительная машина дает возможность полностью ощутить, насколько эта игра необыча и красива.
В игру «Жизнь» можно игrarть одному, без партера. Внимательному и уже очень опытному игру достаточно иметь большой лист клетчатой бумаги и карандаш, чтобы делать ходы. Но начинающему игру лучше запастись dockой, разграфленой на клетки, и фишки дыхов их цветов, например, черными и белыми (и лист, и доска считаются бесконечными).
Правила игры
Идей игры состоит в том, чтобы, начав с какого-нибудь простого расположения черных фишек («организмов») на доске, проследить, что будет проискодить с этой исходной позицией («колонней») под действием «генетических законов» Конвея. «Генетические законы»— это и есть правила игры, они управляют розделением и в нем, гибелью и в жизни и нем фишек на доске.
Заметим, что каждая клетка dockи может находиться в одном из двух состояний — либо она пустая, либо же на ней стоит одна черная фишка, — и что у нее есть восем соседи клеток (четыре имеются с ней общее стороны, и еще четыре — общее вершины). Будем называть колонню, получающего из предыдущей в результате одного хода, следующим поколением. Сформируем теперь правила игры, то есть определим, когда фишка «погибает», когда «рождается» и когда «выживает».
Фишка вы жи и вает (остается на доске на своем месте) и переходит в следующей поколение, если у нее есть две или три соседи фишки.
Фишка поги ибает, — снимается с dockи,— если она имеет большие, чем три или меньше, чем два соседи (соответствие из-за перемещности или же от одиночства).
Фишкарождается в некоторых случаях, если в клетках соседи с этой пустой клеткой, стоит проверить три фишки. Процессы «рождания» и «гибели» проискодят одновременно.
Конвей рекомендует производить ходы следующим образом. Определьить, какие фишки должны получить и положить на каждую из них еще по одному черной фишке. Затем определить, в каких клетках должны «родиться» фишки, — и поместить в каждой такую клетку белую фишку. Внимательно проверить еще раз, все ли сделано правильно (допустить ошибку, особенно, если играешь впервые, очень легко), и затем убрать с dockки все столбики из черных фишек, а белые фишки заменить черными — при этом получится следующей поколение исходной колонии (для этого нам и нужны фишки двух цветов).
Начав игру, вы обнаружите, что первооначальная колоння может претерпеть самые неожиданные и порой очень красивые изменения. Иногда колоння вымирает (с dockи исчезают все клетки); произойти это может и не сразу, а лишь после того, как смениться очень много поколений. Но чаще всего исходные конфигурации либо переходят в устойчивые, то есть перестановят изменяющиеся вообщество (их Конвей называет «любителями способной жизни»), либо «выходят на колбательный режим», то есть испытывать цикл превращений с определенным периодом. Во всех этих трех случаях эволюция конфигурации считается законченной.
Проискождение «видов»
Посмотрим, что проискодит с некоторыми простыми конфигурациями.
27
Одна или две фишки всегда погибают после первого же хода. Конфигурация из трех фишек (ее Конвей называет тр и п л е т о м) чаще всего погибает. На рисунке 1 изображены пять триплетов. Первые три погибают уже на втором ходу. Триплет (2) переходит в устойчивую конфигурацию из четырех фишек, называемую «блоком». Триплет (3) Конвей называет «мцалкой» — он превращается попеременно то в вертикальный, то снова в горизонтальный ряд.
Отметим еще, что любой диагональный ряд фишек постепенно вымирает: с каждым ходом число фишек на доске уменышается на два («погибают» крайние фишки).
На рисунке 2 изображена эволюция пяты террамино — так Гарднер называет конфигурацию из четырех клеток, связанных между собой ходом ладьи. Конфигурация (a) нам уже известна — это «блок», террамино (б), (в) и (2) переходит также в устойчивую конфигурацию, называемую «ульем»: (б) и (в) — на втором ходу, а (2) — на третьем. Конфигурация (δ) называется «навигационными осими», замещальная она тем, что на девятом ходу распадается на четыре отдельные «мигалки», дальнейшие превращения которых в
Рис. 1. Эволюция пяты триплетов
Рис. 2. Эволюция пяты террамино
28
Рис. 3. Устойчивые конфигурации
Рис. 4.
Рис. 5. «Планер»
самом деле напоминают «действность» светофоров.
На рисунке 3 изображены две надцатьные наиболее часто встречающиеся устойчивых конфигураций — «любителей спокойной жизни».
Задание 1. Существует две надцатьные конфигурации из пятки клеток, связанных между собой ходом ладьи («пентамино»). Самый сложной из них является pentamino в форме буквы г (рис. 4 a). Эта конфигурация превращается в устойчивую лишь после тысяча сто третьего хода, распадаясь при этом на восемь «блоков», четыре «мигалки», четыре «улья», «каравай», «лодку» и «кораабль» (см. рис. 3!) Попучить этот результат без ЭВМ было бы, конечно, невозможно; при этом счетная машина должна обладать устроястом, позволяющим выводить выходные данные на экран, — только тогда мы сможем наблюдать за всеми изменениями, произходящими на доске. Попробуйте выяскить, что будет проискоить с остальным одинаковым конфигурациями.
Задание 2. Выясните судьбу конфигурации, изобравенных на рисунке 4б—e.
Заметим лишь, что если эвволюция буквы Н заканчивается быстро, то буква П (или «ворота»), неожиданное оказывается «долгожительем» — лишь после 173 хода она распадается на пятку «мигалок», шесть «блоков» и два «пруда»!
На рисунке 5 изображены конфигурация из пятки фище, которое Гарднер считает одним из самых изумительных открытий игры «Жизнь»; Конвей назвал ее «планером». Замечательно здесь то, что «планер» является фигурой, действительно перемещающегося по доске («летящей»): после второго хода он «входит в пикке», а на четвертом ходу переходит в себя, смешая при этом на одну клетку вправо и одну вниз относительно начальной позиции. В игре «Жизнь» скорость, с которой
29
Рис. 6. «Космические корабли»
по доске перемещается шахматный король, называется «скоростью света». Связано это с тем, что большие скорости в этой игре просто не достигаются: ни одна конфигурация не воспроизводит себя настолько быстро, чтобы двигаться с такой скоростью. Скорость движения фигуры у Конвея равна дюби, в знаменатель которого стоит число ходов, необходимых для воспроизведения фигуры, а в числитель — число клеток, на которой она при этом смешается. Скорость «планера» (по диагонали) составляет 1/4 скорости света (проверьте это!). Конвей доказал, что в «Жизни» такая скорость (по диагонали) будет максимальным и что скорость любой конечной фигуры, перемещаются по вертикали или по горизонтиали, не может превышать половины скорости света. На рисунке 6 показаны три «космических кораблей» («планер» — самый «легкий» из всех «космических кораблей»), передвигающиеся по горизонтиали со скоростью, равной половине скорости света. «В полете из них вылетают «искры», — пишет Гарднер, — которые тут уже гаснут при дальнейшем движении «корабля». Оказывается, что «сверхяжеемые космические корабли» (у них горизонтальный ряд состоит более чем из шести фишек) уже требуют эскорота из двух или большого числа «кораблей». Меныших размеров, в противном случае на доске появляются мелкие фигуры, мешающее движению. На рисунке 7 изображен самый тяжелый из «космических кораблей», который достигно имеет два сопроводящих более легких «корабля». Как вычислил Конвей, «кораблю» длиной в 100 клеток нужно эскорот, состоящий уже из тридцати кораблей.
ПРОБЛЕМА «РОСТА»
Пожалуйста, самой сложной задачей игры «Жизнь» была следующая: сущность имитация макая конечная исходная колоння, число «организмов» которой просто бы при перехождение от поколения к поколению бесконечно.
Опубликовав свою игру, Конвей пообещал premio тому, кто найдет ответ на этот вопрос. Задча была решена в ноябре 1970 года группой математиков Массачу-Рис. 8. «Планерное ружье»
30
ла бы засевать поле с той же скоростью, с которой живейка его убирает».
И, наконец, отметим, что игра «Жизнь» — далеко не только игра; она по праву заняла видное место в «теории клеточных автоматов», вызван интересу многих ученых, занимающихся проблемами использования ЭВМ. «Например, создание «планерного ружья», — пишет Гарднер, — открывает волнуощую возможность имитации в игре Конвея машины Тьюринга*), способной (в принципе) произвольить все действия, которые только доступны самым совершенным из современных ЭВМ».
Читательям, занимающиеся игрой Конвея, мы предлагаем еще несколько задач.
Задание 3. Что проискодит с горизонтальным рядами из n фишек при n=5, 6, …, 9?
Задание 4. Как ведут себя конфигурации, изображенные на рисунке 11a, 6, 8 («восьмерка», буква Z, два «планера», леташие навстречу друг другу).
Рис. 9. «Чеширский кот»
Рис. 10. «Жнейка»
Рис. 11.
*) Машина Тьюринга — это идеальный автомат, способный произвольить юбьи в вычисления, изображен английским математиком А. М. Тьюрингом.