Программирование и искусство. Мир клеточных автоматов. Искусственная жизнь

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

Итак, искусство может «облагораживать» программирование. А можно ли программировать само искусство? Взгляните на рис. 35.1.

Это самый что ни на есть обычный фрактал, построенный на основе множества Мандельброта. Подобные работы стали возможны благодаря созданию в 1970-х годах фрактальной геометрии, отцом которой заслуженно считается профессор Гарвардского университета Бенуа Мандельброт. Именно Мандельброт и придумал термин «фрактал» (от латинского fractus — дробленый). Фрактал — это фрагментированная геометрическая форма, которая не обладает свойством непрерывности. Если взять какой-либо фрагмент такой структуры, он будет походить на уменьшенную копию исходного целого. Фракталы, как правило, самоподобны, их необычные свойства не зависят от масштаба. Фракталы окружают нас повсюду: падающая снежинка, причудливый морозный узор на стекле, сверкающая молния, прожилки опавшего листа. Идея фракталов давно витала в воздухе. В начале 1950-х годов австрийский математик Ф. Хундертвассер написал весьма эмоциональные строки: «Я понял, что прямая линия ведет человечество к упадку. Тирания прямой стала абсолютной. Прямая линия — это нечто трусливое, прочерченное по линейке, без эмоций и размышлений; это линия, не существующая в природе. И на этом насквозь прогнившем фундаменте построена наша обреченная цивилизация!».

Фрактальная геометрия Мандельброта бросила еще один вызов геометрии Евклида.

Фракталы — это множества дробной размерности (не одномерные, не двумерные); это нечто промежуточное между точкой и линией, линией и поверхностью, поверхностью и телом. Множество Мандельброта (один и примеров фракталов) на плоскости математически определяется очень просто — это множество всех таких комплексных «с», при которых итерационная последовательность z -> z² + с (начиная с z = 0, с = х + iy) остается ограниченной, не уходя на бесконечность. При графической интерпретации цвет точки на плоскости (х, у) может определяться, скажем, номером итерации. Что в результате может получиться, можно увидеть на рис. 35.1. На рис. 35.2 приводятся и другие иллюстрации, также полученные с помощью фракталов.

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

От изобразительного искусства обратимся теперь к музыке. Здесь тоже можно найти интересные задачи. Возьмем 8 нот, образующих одну октаву, и подсчитаем, сколько существует возможных вариантов мелодий, состоящих всего лишь из 10 нот. Их около 1 миллиарда, или 8¹⁰. Мы не учитывали вариации ритмов и разные длительности. Но даже это число впечатляет. Как же теперь выбрать из всего этого множества мелодий «благозвучные»?

В общем случае этого добиться непросто. Но если выделить вполне определенный стиль и обеспечивать вариации в довольно жестких рамках, то задача вполне разрешимая. Построением генераторов мелодий люди занимались давно. Еще в 1650 году увидел свет трактат немецкого иезуита Афанасиуса Кирхера «Универсальная музургия, или великое искусство созвучий и диссонансов». Описанная автором механическая машина («чудесная музарифмика») была построена в 1670 году. Она создавала полифонию путем относительного перемещения столбцов и считывания различных перестановок и сочетаний по строкам. В 1779 году австрийский композитор Максимилиан Штадлер выпустил наборы таблиц тактов для сочинения менуэтов с помощью игральных костей. Но самая известная работа — «Музыкальная игра в кости», объяснявшая, как с помощью двух игральных костей сочинять сколько угодно немецких вальсов, «вовсе не зная музыки»; она была впервые опубликована в 1792 году, через год после смерти Моцарта, которому и приписывалось авторство этого сочинения.

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

Но вернемся к нашему рассказу. Система Моцарта состоит из набора коротких тактов, пронумерованных числами от 1 до 176. Две игральные кости бросаются 16 раз. С помощью таблицы, в каждом из 8 столбцов которой перечислено по 11 номеров, первые 8 бросаний определяют первые 8 тактов вальса. Вторая таблица используется для 8 последующих бросаний, и найденные с ее помощью такты завершают вальс из 16 тактов. Карты составлены с таким расчетом, что вальс начинается с основного тона, или основной ноты, затем модулирует к доминанте и в заключение возвращается к основной ноте. Так как все такты, перечисленные в 8 столбцах каждой карты, имеют много общего, 11 вариантов выбора (11 сумм очков от 2 до 12, выпадающих при одновременном бросании двух игральных костей) существуют только для 14 тактов. Это позволяет системе порождать 11¹⁴ вальсов — созданных в отчетливо различимой моцартовской манере!

В 1940 году Шиллингер, математик из Колумбийского университета, разработал математическую систему музыкальной композиции. Утверждают, что Джордж Гершвин, работая над оперой «Порги и Бесс», пользовался системой Шиллингера.

Первая коммерческая запись вальсов, полученных по системе Моцарта, была сделана шотландским математиком Томасом 0'Берном. И рандомизация, и исполнение мелодий были поручены экспериментальному компьютеру Solidak, построенному в начале 1960-х годов в Глазго. 0'Берн запрограммировал его так, что он исполнял пьесы в тембре кларнета. В 1967 году производитель компьютера фирма Burr & Straud выпустила долгоиграющую запись избранных вальсов и контрдансов.

Из последних работ в этой области можно отметить использование фрактальной геометрии и так называемых генетических алгоритмов, о которых мы поговорим чуть позже.

Хотелось бы добавить, что принцип автоматического сочинения мелодий во многом опирается (по крайней мере, в системе Шиллингера) на идею игрушки, знакомой нам с раннего детства — на самый обычный калейдоскоп.

Мир клеточных автоматов

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

Клеточные автоматы (cellular automata) устроены столь же просто, как и калейдоскоп. За несколько десятков лет своего развития они смогли настолько завоевать умы и сердца ученых, что послужили основой новому направлению научных исследований, котоpoe получило звучное название «искусственная жизнь» (artificial life). Так что же такое клеточный автомат? Возьмем карандаш и обычный тетрадный листок. Теперь произвольным образом в разных клетках поставим крестики. Это и есть начальное состояние нашего клеточного автомата. Обратите внимание, что вокруг каждой клетки находится ровно 8 других клеток (им иногда для удобства дают имена по названиям сторон света: север, юг, запад, восток и т. д.). Возьмем новый, чистый листок и тоже начнем проставлять там крестики, но уже не как попало, а в строгом соответствии с тремя правилами:

• если вокруг выбранной нами клетки больше трех или меньше двух соседей, то такая клетка «погибает», и на новом листке она остается пустой;
• если число соседей в точности равно трем, то на новом листке «рождается» новая клетка (проставляем крестик);
• если число соседей равно двум и в клетке был проставлен крестик, то на новом листке мы также ставим крестик.

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

Игра «Жизнь» представляет собой частный случай клеточного автомата. Здесь он работает в двумерном пространстве (2D), с радиусом 1 (1R — рассматриваются только соседи на расстоянии 1 клетки), с числом состояний клетки,равным 2 (2S — пустая или с крестиком). Да и глубина памяти (предыдущие состояния) в точности равна 1 (1М — мы рассматривали состояние только одного предшествующего поколения). Клеточные автоматы, оказывается, могут быть даже одномерными (1D). Простейшим клеточным автоматом называется автомат со следующими характеристиками: 1D, 1R, 2S, 1М. Состояние каждой клетки здесь зависит от ее предыдущего состояния и состояния двух ее соседей. Рассмотрим два разных правила:

• 010-> 1 (иначе 0)
• 000, 001, 100 -> 1 (иначе 0).

На рис. 35.3 вы видите результаты работы этих двух разных автоматов. Здесь каждое поколение представляется новой строкой точек, самая верхняя строка — начальное состояние.

Клеточные автоматы имеют свою историю. Еще в пятидесятых годах ими стал заниматься Джон фон Нейман, создавший так называемый универсальный конструктор (Universal Constructor). Этот конструктор представляет собой автомат, который способен выполнять следующие действия:

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

Джон фон Нейман стремился получить такой автомат, который был бы эквивалентен машине Тьюринга. При этом основное внимание он уделял проблеме самовоспроизводства (self-reproduction). В клеточном автомате фон Неймана самовоспроизводство достигалось за счет предоставления самому универсальному конструктору его описания и возможности копировать предоставленное описание. В 1966 году фон Нейман издал свой труд, который назывался «Теория самовоспроизводящихся автоматов».

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

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

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

На рис. 35.4, слева вы видите красивую раковину морского моллюска; на рис. 35.4, справа — она же, но уже сгенерированная с помощью клеточного автомата.

Наиболее яркой и доступной работой, которую хочется порекомендовать, явиляется книга двух американских ученых из Массачусетского технологического института Тома Тоффоли и Нормана Марголуса, которая в 1990 году вышла в переводе на русский язык в издательстве «Мир». Для анализа клеточных автоматов авторы этой книги использовали язык Forth (очень простой стековый язык, допускающий реализацию крайне компактных и эффективных программ). В книге они рассказывают о работе над специальной машиной САМ (Cellular Automata Machine).

Искусственная жизнь

Виртуальная реальность (virtual reality)... Этот термин столь хорошо нам знаком, что теперь вряд ли кого можно удивить специальными очками, шлемами, тренажерами и другими устройствами, входящими в состав так называемых VR-имитаторов, цель которых, в общем-то, одна — воздействуя на разные органы чувств (прежде всего на зрение), создать у человека иллюзию реальности происходящего.

При работе с VR-имитаторами человек думает, что это он хозяин, что именно он и воздействует на окружающий мир. В то время как все обстоит совершенно наоборот.

Alife-имитаторы, получившие свое название от термина «artificial life» — «искусственная жизнь», идут от обратного: человек с их помощью сам творит «несуществующую» жизнь. Искусственная жизнь — это уже не искусственный интеллект. Задача ставится иная и, на первый взгляд, куда более скромная. Как мы знаем, не все, что является живым, обладает разумом. Главная цель искусственной жизни — воссоздать «жизнь» в иной среде, воображаемой, где «суть жизни» отделена от деталей ее реализации.

В области искусственной жизни уже сформировалось несколько направлений исследований. Это и нейронные сети, о которых нужно рассказывать особо и обстоятельно, и уже известные нам клеточные автоматы, и автономные (интеллектуальные) агенты, и генетическое программирование.

Хотелось бы сказать еще несколько слов о машине клеточных автоматов, которая называется САМ-8. Она разработана в рамках проекта ARPA в Лаборатории компьютерных наук Массачусетского технологического института (MIT LCS) и представляет собой компьютерную архитектуру, построенную на клеточных автоматах. И в то же время — это параллельная масштабируемая архитектура для высокоскоростного моделирования пространственных систем средствами клеточных автоматов.

CAM-8 состоит из рабочей станции Sun, на которой под управлением операционной системы SunOS функционирует специальная среда программирования. Эта среда реализована в рамках коммерческого интерпретатора языка Forth для SunOS. САМ-8 представляет собой отдельный наращиваемый аппаратный модуль, в который встроены специально разработанные кристаллы STEP и который подключается к рабочей станции Sun через интерфейсную плату с шиной SBus. Для низкоуровневого управления модулями САМ-8 разработана библиотека Си-функций, что позволяет для программного подключения использовать различные интерпретаторы головного компьютера.