Компьютерная "Жизнь"

Компьютерная "Жизнь"

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

Автор игры - Джон Хортон Конуэй, большая часть работ которого посвящена чистой математике. Например, ему принадлежит открытие новой группы, получившей название "созвездие Конуэя". Оно оказалось очень важным как для теории групп, так и для теории чисел. Другая страсть Конуэя - занимательная математика. Впрочем, "Жизнь" нельзя назвать несерьезной игрой, поскольку она неразрывно связана с теорией клеточных автоматов. Думаю, сначала стоит поговорить об игре, а уже потом - об автоматах.

Игра "Жизнь" очень проста. В нее играет один человек, партнер не нужен. Замечательно, что в "Жизнь" можно играть пользуясь как компьютером, так и листком бумаги в клеточку. Возможен своего рода промежуточный вариант, когда применяется шахматная доска и набор фишек. Это удобнее, чем рисование от руки, но играть при помощи компьютера, конечно, намного проще и увлекательнее.

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

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

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

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

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

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

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

Вас не воодушевляет перспектива посвятить свободное время подобным опытам? Как знать, вдруг родится стратегическая игра вроде "Цивилизации", "Звездных войн" и т.п.? Не спешите улыбаться: поиграв в "Жизнь", убеждаешься, что это стратегическая игра высшей пробы. Предельная простота "Жизни" оставляет игрока один на один с законами игровой вселенной. Им он противопоставляет стратегическое мышление и прозорливость. Хотя мы еще не обсуждали собственно процесс игры, уже должно быть очевидно, что она состоит в стратегическом планировании эволюции колонии и практической проверке плана. Наконец, можете ли вы представить себе более занимательное стратегическое и творческое занятие, чем изобретение универсальных законов развития? Замечательная простота правил игры делает ее программирование детской забавой. У меня "Жизнь" есть, но если бы не было, написал бы ее не более чем за полчаса. Судите сами. Чтобы клетки доски (экрана) были квадратными, нужно установить алфавитно-цифровой режим 80х60 символов. Для задания исходной позиции достаточно организовать перемещение курсора при помощи клавиатуры со стрелками, а фишку ставить/удалять, нажимая клавиши [Ins] или [Del] соответственно. Сохранить/восстановить позицию (массив символов) - проще не бывает, хотя, если лень, вполне можно обойтись и без этого удобства.

Для анализа позиции следует отобразить ее с экрана в массив символов и прогнать по нему несколько циклов, проверяющих законы. Результат проверки нужно выводить сразу на экран, не изменяя массива. Вот и весь алгоритм. Остаются всего две-три мелочи, наподобие обработки [Enter] и [Esc], запускающие и останавливающие генерацию поколений, да задержка перед очередной генерацией, чтобы не мелькало изображение. Ничего сложного - одно удовольствие. Можно приступать к исследованию игры.

Увы, как это обычно бывает, все самое интересное уже выяснено задолго до нас. Правда, в этом есть и светлая сторона: не нужно тратить время и силы, изобретая велосипед. Кое-что, не очень многое, мы сейчас обсудим. Если вы захотите подробно познакомиться с игрой, то обратитесь к литературе по занимательной математике.

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

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

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

Эта премия была выплачена в 1970 году группе математиков из Массачусетского технологического института, которые сумели построить из фишек своего рода "ружье", "выстреливающее" уже упомянутые движущиеся фигуры, названные планерами. Кроме "ружья" были изобретены фигуры, получившие название пентадекатлонов. Пентадекатлоны могут либо поглощать без остатка столкнувшиеся с ними планеры, либо отражать их, разворачивая на 180 градусов.

О виртуозности математиков из МТИ говорит и то, что они умудрились построить группу "ружей", испускающих потоки планеров так, что в месте пересечения их возникает "завод", запускающий раз в 300 поколений "космический корабль" - движущуюся фигуру, состоящую из большего числа фишек, чем планер.

Думаю, в свете описанного никто не усомнится, что по крайней мере некоторые из фигур в игре "Жизнь" можно в определенном смысле считать машинами или автоматами. Сомневающихся должен убедить авторитет Джона фон Неймана, благодаря которому в 1950 году началось то, что выросло в теорию так называемых клеточных автоматов.

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

Это доказательство использовало понятие однородного клеточного пространства, подобного бесконечной шахматной доске - совсем как в "Жизни". Любая клетка доски могла находиться в конечном числе состояний, в ряде случаев оставаясь и пустой. На состояние клетки оказывало влияние положение конечного числа соседних клеток. Состояния клеток должны были изменяться дискретно, путем одновременного применения к ним всем заранее описанных правил перехода. Клетки соответствуют частям автомата с конечным числом состояний, а конфигурация непустых клеток - идеализированной модели автомата.

Нейман, применяя правила перехода к пространству, каждая клетка которого могла находиться в 29 состояниях и имела 4 соседние клетки (диагональное соседство не учитывалось), доказал существование самовоспроизводящейся конфигурации, состоящей примерно из 200,000 клеток.

С течением времени доказательство, найденное Нейманом, удалось значительно упростить: выпускник инженерного факультета МТИ Эдвин Бэнкс обошелся клетками всего с четырьмя возможными состояниями. Этот факт, впрочем, нельзя рассматривать как свидетельство недальновидности именитого математика: у него были веские причины прибегнуть к столь громоздкому построению.

Дело в том, что фон Нейман намеревался применить свое доказательство к реальным автоматам и подобрал клеточное пространство, которое по своим характеристикам было бы способно моделировать машину Тьюринга. "Погруженная" в клеточное пространство машина Тьюринга становится своего рода конструктором, позволяющим породить лю-бую наперед заданную конфигурацию в пустых клетках пространства, в том числе саму себя.

Создание самовоспроизводящихся клеточных конфигураций, не включающих в себя машину Тьюринга, оказалось довольно простой задачей, что послужило основанием назвать их тривиальными. От себя я должен прибавить: таким эпитетом эти конфигурации наградили Эдвард Фредкин, предложивший простую самовоспроизводящуюся систему, Терри Виноград, обобщивший правила Фредкина, Станислав Улам, построивший множество аналогичных автоматов и опубликовавший совместно с Робертом Шрандтом статью "О рекурсивно определенных геометрических объектах и схемах роста". Боюсь, многое из того, что эти люди сочли бы тривиальным, не просто для тех, кто лишен блестящих математических способностей.

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

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

Скажем, примем на веру почерпнутое из популярной литературы по физике представление о вакууме как о сложном континууме, который буквально кипит, порождая и немедленно уничтожая элементарные частицы. Извлечем из того же источника сведения о том, что физики, описывая реалии микромира, прибегают к математике, оперирующей в многомерных пространствах состояний и/или координат. У вас не возникает подозрения, будто представление микромира в терминах клеточного n-мерного пространства со множеством состояний способно не только быть полезно физикам, но и соответствовать действительности? Такое же подозрение закономерно возникает по отношению к живым существам, состоящим, как известно, из клеток. Этот факт вызывает непосредственное желание уподобить хотя бы в ограниченном смысле и хотя бы простейшие организмы клеточным автоматам. Трудно судить о правомерности такого сравнения, но я не первый и не последний, кому оно приходит в голову. Так, Эдвард Мур опубликовал статью, посвященную клеточным автоматам, назвав ее "Математика в биологических науках". В любом случае можно ожидать пользы от нетрадиционного приложения математики.

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

Алви Смит нашел способ применить теорему Мура к игре Конуэя и показал, что конфигурация по типу "садов Эдема" возможна и в "Жизни". Формулы, выведенные Муром, позволили Смиту утверждать, что подобная конфигурация всегда может быть заключена в квадрат со стороною в 10,000,000,000 клеток. Это, правда, не слишком облегчает поиски "садов". А теперь - последняя из обещанных спекуляций.

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

Понимаете, что это будет означать? Ни больше ни меньше как математически строгое доказательство акта Творения! Если такое случится, то материализму не "отвертеться", а "основной вопрос" философии перестанет быть таковым.

Не правда ли, занятная вещь - компьютерная игра "Жизнь"?

Евгений Щербатюк