Увлекательная жизнь клеточных автоматов, или Как в «Жизни» «Тетрис» запустили

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

Начать лучше всего с «нуля», с самых основ, потому что если в «Тетрис» играл каждый, с «Жизнью» сложнее (если вы из тех, кто начинал знакомство с компьютером с программирования «Жизни», потерпите, прошу: в последовательности изложения есть свой смысл). Так вот, «Жизнь» — игра особого сорта и особая она по двум причинам.

Во-первых, потому что это одна из немногих игр с предельно простыми правилами. Действие её происходит на тетрадном листке в клеточку или, лучше, на готовом поле с фишками, например, от го. У каждой клетки может быть два состояния: живая или мёртвая. Чтобы понять, каким будет состояние конкретной клетки на следующем ходе, нужно проанализировать её окружение. Если клетка сейчас жива и вокруг неё две или три других живых клетки, она остаётся живой, иначе гибнет. Если клетка мертва и вокруг неё три живых, она станет живой. Напоминает биологию, правда? Отсюда и название.

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

Игра «Жизнь» в программе Golly — одном из лучших симуляторов клеточных автоматов (см. далее).

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

Автор «Жизни» — английский математик Джон Конвей (кстати, и сегодня ещё преподаёт любимый предмет в престижном университете в Штатах). Он создал игру в 1970 году как вариацию на тему классического труда Джона фон Неймана, который первым придумал такие вот, «живущие» по очень простым правилам, «микроскопические существа» и назвал их клеточными автоматами.

Фон Нейман работал над темой до самой смерти, а одного из его задач было показать, что машины способны копировать самих себя, то есть способны на самовоспроизводство. Для чего, собственно, он и привлёк идею клеточного автомата. И действительно, почти полвека спустя одно из описанных им «существ» смоделировали на компьютере и доказали правоту учёного. Но детище фон Неймана было сложным (поведение его определяется почти тремя десятками правил). Заслуга же Конвея как раз в том, что он искал и нашёл один из, вероятно, простейших клеточных автоматов, обладающих тем же свойством, что и прототип: правила «Жизни» обладают тьюринговой полнотой, что, попросту говоря, означает, что на игровом поле «Жизни», вот из этих самых простейших клеток, можно построить сколь угодно сложные логические структуры. Хоть электронные часы, хоть настоящий компьютер! Правда, оговорюсь, в теории. С практикой сложнее.

С тех самых пор, как Конвей опубликовал свою историческую статью в научно-популярном журнале, «Жизнь» и клеточные автоматы стали весьма популярной темой. Задача создания или открытия всё более и более сложных структур терзает миллионы любителей головоломок! Вот только вручную играть в такие игры непросто. Поэтому почти сразу после публикации Конвея, «Жизнь» запрограммировали на тогдашних вычислительных машинах (первой, говорят, была PDP-7, стоимостью в полмиллиона долларов в сегодняшнем эквиваленте: ну не изобрели ещё тогда персоналку!). Это значительно облегчило игру: избавило от ошибок, неизбежных при ручном анализе, и в тысячи раз ускорило.

Глайдер: одна из самых простых полезных структур в «Жизни». Если вы повторите этот рисунок на игровом поле «Жизни», он поведёт себя точно таким же образом.

Так и были открыты первые многоклеточные структуры, обладающие необычными свойствами. Например, знаменитый «Глайдер» — который словно бы летит по игровому полю («Глайдер» стал легендарным и впоследствии предложен на роль символа хакерского движения). Или «Галактика Кока»: чуть более сложное образование, напоминающее вращающуюся звёздную спираль с астрономических снимков.

Однако лишь с 90-х годов, когда производительность и доступность вычислительной техники выросли принципиально, начинаются открытия по-настоящему сложные. Всю летопись сегодня можно посмотреть, например, в открытой веб-энциклопедии по игре «Жизнь» (да, такая существует — и продолжает писаться!): по ней ясно видно, как с каждым годом сложность открытий росла, достигнув к концу нулевых невероятных величин. Вот, например, структура, названная «кораблём Gemini»: она занимает площадь в 4 миллиона на 4 миллиона клеток и живёт циклами по 34 миллиона ходов! Вообразите объём вычислений, необходимых для расчёта эволюции такого образования!

Или вот другая примечательная структура: открытый в 2005-м «Метапиксель OTCA». Это образование размером 2058 на 2058 клеток, живущее циклами по (примерно) 35 тысяч ходов. Но именно оно оказалось очень важным для «Жизни» в целом. Дело в том, что «Метапиксель» способен имитировать одиночную клетку из «Жизни»: если расставить бок о бок несколько таких структур, можно сыграть ими в «Жизнь»! Попросту говоря, круг замкнулся: в игре создано образование, способное имитировать саму игру.

«Метапиксель OTCA»: одна из самых сложных полезных структур «Жизни». Для облегчения понимания работы, он раскрашен разными цветами. Каждая точка здесь это отдельная клетка на поле игры «Жизнь».

Чтобы понять, как работает такая имитация, представьте, что вы рассматриваете игровое поле не с расстояния вытянутой руки, а с нескольких метров или больше. Тогда квадрат 2058х2058 покажется вам одиночной клеткой — которая будет пустой или залитой цветом, как и обычная клетка «Жизни». Вот замечательный видеоролик, демонстрирующий это.

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

История этой задачки начинается 4 года назад, когда на популярном сайте головоломок для программистов кто-то предложил: поскольку «Жизнь» тьюринг-полная, то есть теоретически в ней можно создать что угодно, пусть кто-нибудь построит там «Тетрис»! Три года задача оставалась без ответа, а потом вокруг неё начал подбираться коллектив энтузиастов — и, потратив больше года на решение, они таки её решили.

За основу ребята взяли уже знакомый вам «Метапиксель OTCA». Он стал своеобразным кирпичиком, с помощью которого были созданы аналоги проводов (по которым бегут биты) и логических элементов (из которых построен любой настоящий компьютер). Из этого они уже собрали модель компьютера: не совсем обычного (он асинхронный: у него нет тактовой частоты и работает он блок за блоком, по мере распространения сигнала), но с привычными блоками оперативной и постоянной памяти, процессором (7 инструкций) и прочими атрибутами. Язык процессора они назвали ассемблером QFTASM, но чтобы проще было программировать, написали и более высокоуровневый язык COGOL. И вот на нём уже и запрограммировали «Тетрис».

Это один из ключевых блоков: процессор. Каждая клетка здесь — Метапиксель OTCA.

Запустить результат сегодня можно прямо в браузере (щёлкните там кнопку Run). Но теперь, зная, как это построено, вы в силах оценить и истинную сложность проекта. Построенный ребятами компьютер имеет размер 1436х5082 клеток, каждая из которых это «Метапиксель OTCA». Поэтому в сумме, если рассмотреть всю структуру под максимальным увеличением, получается гигантская структура примерно 3 на 10 миллионов клеток.

Теперь авторы этого невероятного компьютера планируют усовершенствовать процессор, добавив в него относительную адресацию, и запрограммировать на нём кое-какие другие игры, в частности, классический Pong. Но в общем важнее, что средствами «Жизни» такой компьютер построен: это можно считать высшей точкой поиска.

Однако исследования клеточных автоматов продолжаются — и «Жизни» в том числе. Энтузиастам по-прежнему удаётся открывать случайно или конструировать сложные структуры, обладающие необычными свойствами. При этом, бывает, они получают имена в честь создателей. Так что реально есть возможность вписать своё имя в историю.

Эксперименты здесь численные, возиться с пробирками не придётся — достаточно персонального компьютера, который сегодня способен за секунду обсчитывать миллионы ходов (не только в силу мощности, но и благодаря современным алгоритмам, которые сами по себе составляют отдельное направление в поиске). Важно понимать, чего вы хотите добиться, ну и обладать терпением, конечно. Потому что теория и грубая вычислительная мощь здесь пасуют: требуется чисто человеческая интуиция!

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

Поэтому не исключено, что следующей большой вехой станет воссоздание в «Жизни», например, простейшего червя — помните, над которым уже бьются программеры? А как вам задача перехитрить творца? Или сформулировать наконец критерий живого вообще? То ли ещё будет!

P.S. Отличная подборка исходников, реализующих «Жизнь» на разных языках программирования, есть в проекте Rosetta Code.

клеточный_автомат,Жизнь,Тетрис,игра,симуляция,цифра,жизнь,Джон_Конвей,Джон_фон_Нейман,машина_Тьюринга,проблема_останова