Ноябрь считается месяцем литературного творчества. Каждый год в интернете проходит мероприятие NaNoWriMo (National Novel Writing Month). Участники должны до конца месяца написать новеллу длиной не менее 50000 слов. За 17 лет в нем поучаствовали больше 20000 человек.

В 2013 году у программистов появилось аналогичное соревнование — NaNoGenMo (National Novel Generation Month). Задача NaNoGenMo — написать программу, которая сгенерирует новеллу длиной 50000 слов или больше. При этом требования к новелле довольно слабые — подойдет любой текст достаточной длины. Как вы увидите, это может быть сборник рассказов, пьеса, кулинарная книга, словарь или туристический путеводитель. На самом деле, произведение не обязано даже быть текстовым.

Графическая новелла «Сгенерированный детектив»

Сама по себе задача написать программу, которая сгенерирует текст из 50000 слов, проста. Для этого достаточно вот такого кода:

print 'мяу ' * 50000

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

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

Марковские цепи

Цепи Маркова — классический способ генерации текста. Он хорошо описан здесь. У цепей Маркова есть проблема: если выбрать для N-грамм большое значение N (обычно 5 и больше), то в тексте проявляются большие куски исходного корпуса, если взять N меньше, то он получается откровенно бессмысленным.

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

Другие произведения, основанные на цепях Маркова: эротические рассказы от Agrajag-Petunia, речи Рейгана (с примесью работ Шопенгауэра) от VincentToups, автобиографии на английском 19 века от lizrush.

Расширение шаблонов

Чаще всего осмысленные фрагменты текста генерируют с помощью шаблонов. Представим, что у нас есть такая грамматика:

sentence = '<greeting>, <world_phrase>!'
greeting = ['Привет', 'Приветик', 'Здравствуй', 'Добрый день']
world_phrase = ['<happy_adj> мир', '<sad_adj> мир', 'мир']
happy_adj = ['прекрасный', 'светлый', 'добрый']
sad_adj = ['унылый', 'жестокий', 'мрачный']

На основе нее мы можем сгенерировать много разных предложений — «Привет, унылый мир!» или «Добрый день, прекрасный мир!». Чем богаче грамматика, тем более интересные тексты она выдает.

В «The Gamebook of Dungeon Tropes» от maetl с помощью шаблонов генерируются описания подземелий.

В «Атеистах, которые верят в Бога» от tra38 используются данные какой-то переписи населения США. Герои новеллы — люди, которые сказали, что они атеисты, но верят в Бога. Они один за другим читают шаблонные лекции, в которые подставлены ответы на вопросы из переписи.

Шаблоны используются в новелле «Где-то что-то» от BenKybartas, сборнике «5000 рассказов» от tinyworlds, эротической новелле «Оргазмотрон» от enkiv2 (простите, больше эротики не будет) и спортивном комментарии «Федерация лжеамериканского футбола» от creade.

Рекурсия

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

Простой вариант: в «The transorbital anaphase provine biforn the pure-bred synostosis» от samcoppini берется одно предложение (оно вынесено в заголовок). А затем с помощью словаря дается определение некоторых слов. Для слов из определений тоже даются определения. И так пока не наберется пятьдесят тысяч.

«Гигант без сердца» от MichaelPaulukonis рассказывает вариации норвежской сказки о принце, который спас своих братьев от злого гиганта. Но в конце этот принц сам становится гигантом и похищает детей другого короля. И вся история повторяется, но уже немного по-другому.

Новелла «Надежды и воспоминания» от cpressey состоит из нескольких событий и диалога двух персонажей. По ходу новеллы они встречают вампира, зомби, дракона и других чудовищ. А всё остальное время они вспоминают свои встречи и предполагают, кого они увидят в будущем. А потом вспоминают, как вспоминали какую-то встречу, предполагают, будут ли они вспоминать, как предполагали другую встречу и так далее.

Похожа по структуре «Redwreath and Goldstar Have Traveled to Deathsgate» от erkyrath. Там тоже два персонажа ведут разговор. Они очень вежливые — спрашивают: «Могу ли я задать вопрос?» и «Правильно ли я понимаю, что...». И так пока в какой-то момент не доходит до такой реплики:

"You want to know whether I am asking whether you are asking whether you shall tell me whether you want to know whether I believe I can answer that?"

«Сто шестьдесят пять дней Рождества» от hugovk — это продолжение английской народной песни «Двенадцать дней Рождества», где продолжают дарить новые и новые подарки (и их количество тоже растет).

Переработка существующих произведений

Если литературное произведение находится в публичном достоянии, его можно использовать любым способом. В том числе и для генерации нового произведения на его основе. Самые интересные примеры:

Моби Дик на кошачьем языке от hugovk. Это одна из самых известных работ NaNoGenMo про которую писали The Guardian, Vox и The Atlanctic. Просто приведу цитату:

Meow me Meeeeow. Meow meeow mew--meoow meow mew meow meeeeooow--meeeow meeeow me me meeow me me meoow, mew meeeoow meeeooooow me meooooow me me meeow, M meeooow M meoow meow meoow m meooow mew mew mew meooow meow me mew meeow.

Сравните с оригиналом:

Call me Ishmael. Some years ago--never mind how long precisely--having little or no money in my purse, and nothing particular to interest me on shore, I thought I would sail about a little and see the watery part of the world.

«Приключения Шарлотты Холмс» от emdaniels. Автор поменяла пол всех персонажей в рассказах о Шерлоке Холмсе. Звучит не очень серьезно, но на самом деле это непростая лингвистическая задача. C которой автор справилась не до конца (поэтому пришлось придумать местоимение herr).

To Charlotte Holmes he is always THE man. I have seldom heard her mention him under any other name. In herr eyes he eclipses and predominates the whole of him sex. It was not that she felt any emotion akin to love for Ivan Adler.

«Гомерическое ультранасилие» от lilinx. Из текста Илиады выбрали все предложения, в которых есть слово «ударить» в одной из форм. Получилось описание длинной и жестокой бойни, в которой уже даже непонятно, кто с кем сражается.

«Моби Дик, или :whale:» от pteichman — еще один вариант Моби Дика, в котором некоторые слова заменили соответствующими эмодзи.

Другие произведения: «Приключениях Тома Сойера» с героями из романа про Конана от MrDrews, «Гамлет» от dkurth, пропущенный через несколько этапов машинного перевода, «Гордость и предубеждение» с лексикой из Твиттера от michelleful, «Превращение» Кафки, в котором каждое слово заменено более абстрактным, от jonkagstrom.

Не обязательно использовать только одно произведение. Например, сборник коротких рассказов, состоящих из шести слов, от hugovk.

А в «Нашем прибытии» (PDF) от aparrish из корпуса «Проекта Гутенберг» выбраны предложения, в которых описываются какие-то природные объекты или явления. Собранные вместе, они составляют дневник некой экспедиции. Получилось очень красиво, эта новелла занимает одно из мест в моем личном топе новелл с NaNoGenMo.

Переработка других данных

Не обязательно брать в качестве основы литературное произведение. moonmilk составил новеллу из твитов участников NaNoWriMo (PDF) (это то соревнование, где люди сами пишут новеллы), а jimkinsey — из вопросов, которые ученые задают в аннотациях статей (PDF):

In what sense is this a novel situation? Should conflicts in the private domain be exempted from public scrutiny in cases where individual are being deprived of their basic legal rights? How many students study abroad and where do they go? Furthermore if the existing policies are found to be ineffective, what all policy measures can be suggested to the Government to put an end to this evil practice? Who are user entrepreneurs?

Сгенерированные новостные отчеты о NaNoGenMo от enkiv2 трудно отличить от настоящих статей.

В «Словаре языка D'skuban» от samcoppini словам из выдуманного компьютером языка даны определения терминов из реального словаря.

Новелла «Искатель» (PDF) от thricedotted рассказывает о том, как компьютер учится делать всё, что делают люди, с помощью сайта wikiHow.

Симуляция

Хорошей новелле нужны сюжет и развитие событий. Один из способов добиться этого — симуляция. Автор программы создает некоторый мир и описывает правила, по которым он функционирует. А потом просто перечисляет события, которые в этом мире происходят. Если эти события интересные, сюжет тоже получается интересным. Похоже на компьютерную игру, но вы не играете в нее, а читаете лог.

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

Похожим образом герои новеллы flexo бродят по арене и дерутся при встрече.

Кроме сражений, есть и другие симуляции. В «Вечере дождливого дня» от cpressey Алиса и Боб играют в карты. В новелле nothings Ханна решает задачу о Ханойской башне (для 50000 слов хватило двенадцати дисков). Во «Флоре и фауне» от amarriner ботаник ищет выход из лабиринта, встречая по пути животных и растения.

Иногда авторы симулируют перемещения по реальному миру. В «Вокруг света за X статей Википедии» от kevandotorg Филеас Фогг и Паспарту совершают кругосветное путешествие, рассказывая факты о местах, которые они посещают. «Книга Элизы» от greg-kennedy приводит подробный маршрут сорокалетнего путешествия Моисея по пустыне (даже есть карта!).

Высокоуровневая генерация сюжета

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

[ПредставлениеГероев, *, Развязка]

Вместо звездочки компилятор может вставлять любые события со своим началом и концом:

[ПредставлениеГероев, [СокровищаУкрадены, *, СокровищаНайдены, *], Развязка]

Когда событий достаточно, из последовательности можно удалить все звездочки, а сами события разбить на более мелкие:

ПредставлениеГероев = [ПредставлениеДетектива, ПредставлениеГрабителя]
СокровищаУкрадены = [ГрабительБеретСокровища, ГрабительСбегает]
СокровищаНайдены = [ДетективЛовитГрабителя, ДетективЗабираетСокровища]
Развязка = [ДетективИдетДомой, ГрабительСбегает]

После этого остается превратить каждое событие в его итоговое описание в новелле.

Другие форматы

Иногда авторы отходят от формата новеллы. Я уже упоминал несколько подобных, но вот еще:

• «Пустыни Запада» (PDF) от mewo2 — путеводитель по выдуманному миру, для которого специально генерируются карта и язык. И для карты, и для языка подробно описано, как именно они генерируются.
• «Великая книга трансмутаций» (PDF) от TobiasWehrum — сборник алхимических рецептов. Чтобы подбирать ингридиенты, используется какой-то корпус связанных понятий.
• Для «Обложки „И восходит солнце“» adregan взял изображение, а потом написал название цвета для каждого пикселя. Кстати, картинку потом смогли восстановить обратно.
• В «Отправьте по телефону» от hugovk приведен диалог двух человек, один из которых диктует другому программу. «Эс как доллар», только еще хуже. Немного красивой рекурсии: программа, которую диктуют, и сгенерировала этот диалог.

Графические произведения

Не всегда авторы ограничиваются текстовыми новеллами. doldrumorchids для «Людей нет» берет картинки с гугл-панорам, распознает объекты на них, а потом вставляет описания подобных объектов из произведений с «Проекта Гутенберг».

«Серафимы» от lizadaly — это загадочный манускрипт с картинками, написанный на неизвестном языке (с символами из рукописи Войнича).

«Что-то, благодарение и ничего» от zachwhalen и «Сгенерированный детектив» от atduskgreg — графические новеллы (комиксы). В первой текста нет, во второй он есть. Но оба автора постарались над стилизацией картинок, и получилось атмосферно.

Нейронные сети

Немного о плохом. Нейронные сети за последнее время научились многому: побеждать в го, накладывать фильтры на фотографии и сортировать огурцы. Но с генерацией текстов у них, похоже, как-то не клеится. В 2015 было несколько произведений, написанных нейронками (переосмысление Лавкрафта от R-Gerard, переосмысление Жюля Верна от estayton и что-то графическое от spikelynch). Все они меня не впечатлили. Думаю, это значит, что у нейронных сетей всё впереди, и в будущем мы еще увидим что-то более осмысленное от них.

Что дальше

Новый NaNoGenMo начался несколько дней назад. Вот репозиторий для него. Если вы хотите в нем поучаствовать — создайте в нем issue с заголовком вроде «intent to participate». В самом issue вы сможете обсудить свои идеи с другими участниками, а после завершения работы туда надо будет выложить ссылку на код и сгенерированную новеллу. Желаю успеха всем, кто решится!

Ссылки

1. Репозитории прошлых лет: 2013, 2014, 2015.
2. Серия статей, из которой я узнал про NaNoGenMo: 1, 2, 3, 4. В этом посте я использовал некоторые примеры оттуда.
3. Оригинал этого поста на Хабре