Я не игрок. И человек в принципе неазартный. Игры, как интерактивные компьютерные, так и классические настольные, никогда меня сильно не цепляли. Более того, я даже никогда не жаждал их делать. Но с год назад судьба занесла меня разработчиком в одну из успешных восточноевропейских игровых компаний, где теперь и приходится регулярно иметь дело с игроками в игры, самими играми, дизайнерами игр и программистами игр всех мастей. Интерес к теории игрового дизайна в такой атмосфере возникает сам собой, благо область полна разнообразнейших интересных задач, и последний год я нет-нет да и почитывал различные книги и статьи по дизайну игр, от строго теоретических до сугубо прикладных.
Большую часть литературы по теме можно отнести либо к первым, либо ко вторым: академические исследования традиционно проходят в башнях из слоновой кости, не демонстрируя, как правило, никаких примеров живых изданных игр; прикладные же тексты опускаются до формата рецептов и интуитивных советов, не давая никакой осязаемой модели работы тех или иных приемов.
Книга, что попалась не так давно на глаза, объединяет в себе оба мира: в ней, с одной стороны, описаны интересные в совокупности алгоритмические приемы; результат же работы — настольная игра «Yavalath» на приложенной картинке — был издан и пользовался достаточно широкой для абстрактной игры популярностью.
Итак, если вам интересны теория игрового дизайна, машинное обучение, генетические алгоритмы, универсальные игроки и изящные идеи, то обо всем этом можно прочитать в моем кратком научно-популярном пересказе сути книги под катом.
Так чем меня удивила книга? В двух словах: книга посвящена Ludi, системе автоматической генерации настольных игр за авторством Кэмерона Брауни (Cameron Browne). Система была разработана в рамках кандидатской работы (то есть западным аналогом кадидатской — PhD thesis) под названием «Эволюционный игровой дизайн» (Evolutionary Game Design) и способна самостоятельно формировать правила игр, играть в них против себя же, оценивать каждую на интересность и отбирать наилучшие варианты. В конце концов, она даже названия для игр подбирает самостоятельно!
Ну, хватит прелюдий, давайте перейдем к делу.
Ludi, система эволюционного игрового дизайна
Система состоит из следующих основных элементов:
- язык описания правил игры, или Game Description Language;
- универсальные игроки (General Game Players);
- модуль стратегии;
- модуль критики;
- модуль синтеза.
Язык описания игр позволяет описать а) конечные, б) дискретные, в) пошаговые, д) детерминированные игры с в) полной информацией. Сюда подойдут самые обычные шашки, шахматы, «крестики-нолики», Го и в целом существенная доля всех прочих классических настольных игр.
Универсальные игроки интерпретируют сформулированные на GDL правила, способны составить список легальных шагов и понять, что игра закончилась.
Модуль стратегии оценивает текущее положение каждого из игроков и оценивает возможные ходы.
Модуль критики оценивает уже саму игру на предмет различных объективных и не очень параметров, которые автор называет «эстетическими», т.е. оценивающими игру с точки зрения интереса живых игроков.
Модуль синтеза игр интегрирует все вышеприведенные подсистемы, формируя новые сочетания правил на базе оценок модуля критики.
В целом цикл работы системы выглядит следующим образом:
- на GDL описывается несколько десятков (79 в работе автора) игр, универсальные игроки их читают и играют друг с другом при помощи модуля стратегии;
- каждая из проведенных партий получает оценку модуля критики;
- эти оценки и правила игр (в виде дерева правил — сродни обычному абстрактному синтаксическому дереву) подаются на вход модулю синтеза, который, в свою очередь, формирует, скрещивая между собой, новые деревья правил — следующее поколение игр;
- отправляемся к п.1 с новым поколением игр.
Время работы алгоритма ограничивается только терпением разработчика. В случае автора получение новой игры заняло 2-3 недели.
Вот, в принципе, и все. Присмотримся к каждому из модулей по отдельности.
GDL, язык описания правил игр
Язык очень простой и можно сразу привести аналог «Hello, world!» из мира игрового дизайна, правила игры «крестики-нолики»:
(game Tic-Tac-Toe (players White Black) (board (tiling square i-nbors) (size 3 3)) (end (All win (in-a-row 3))))
Любители функциональных языков сразу узнают здесь Лисп. Подобный лиспоподобный язык имеет минимум три преимущества: его легко могут читать люди, его легко могут читать машины и над таким деревом (а код на Лиспе это и есть простейшее дерево) легко можно проводить любые необходимые преобразования. Более того, правила игр в таких терминах выражаются достаточно лаконично (здесь 19 токенов на 7 строк). Автор привел в пример описание шахмат, состоящее всего из 325 токенов на GDL. Существуют и более низкоуровневые языки для таких целей, но они многословны и менее доступны современному программисту, так как обычно связаны с совсем уж экзотическим логическим программированием.
Универсальный игрок
Игрок отвечает за чтение правил и их исполнение: парсит описание правил на языке GDL, отвечает за смену играющих сторон, список доступных ходов, предотвращение циклических ситуаций, определение победителя, пользовательский интерфейс (в случае живого игрока) и прочие служебные вещи. Проще говоря, универсальный игрок это компьютерная игра в привычном нам смысле.
Важно здесь только то, что игрок может как взаимодействовать с живым человеком, так и использовать…
Модуль стратегии
… модуль стратегии. Здесь нет никакого прорыва в искусственном интеллекте: используется алгоритм минимакс с альфа-бета отсечением. Этих страшных слов пугаться не стоит: на каждому ходу строится дерево возможных ходов, у которого по мере построения отбрасываются ветки с низкой предварительной оценкой. Конкретно в данной системе отбрасываются все поддеревья с глубиной более 1, и каждому варианту, таким образом, сразу выдается оценка. Условно можно сказать, что играет неопытный игрок, не способный проанализировать сложную перспективу партии.
Оценки каждому из возможных ходов выдают так называемые Советники (Advisors): большой набор функций (больше пятидесяти), каждая из которых дает потенциальному ходу оценку в диапазоне от 0 до 1. Например, в играх вроде шахмат можно проверять, насколько мобильны в проверяемом положении фигуры (считается, что чем больше фигурам доступно ходов, тем больше тактического преимущества у игрока).
Для разных игр важны разные Советники (в «крестиках-ноликах» мобильность, например, не имеет смысла), поэтому для каждой игры (каждого набора правил) вводятся разные Политики (Policies): векторы коэффициентов для советников, выводимые из правил игры.
Оценка возможного хода, соответственно, получается следующим образом:
E(S) = A_1(S)*P_1 + ... + A_n(S)*P_n,
где S — состояние игры, E — финальная оценка, A_n — значение n-ого Советника,
P_n — n-ая Политика.
Целиком каждая партия оценивается при помощи…
Модуль критики
… модуля критики. Модуль критики формирует оценку каждой отдельной игры на базе двух групп параметров: базирующиеся на оценке правил и следующие из партий компьютерных игроков. Всего критериев, оценивающих разные параметры, аж 57 штук, они описывают все аспекты игры, от сложости правил, до вероятности появления «ничьей». По сути, это функции, возвращающие значения от -1 до 1; и у каждой такой функции должны быть весовые коэффициенты, оценивающие их вклад в результирущую оценку.
Финальная оценка будет, как и в случае модуля стратегии, суммой значений функций, перемноженных на коэффициенты.
Описывать все критерии здесь, конечно, смысла нет, и я просто приведу несколько интересных примеров:
- критерий драмы — насколько часто в процессе игры преимущество переходит от игрока к игроку;
- критерий баланса — отношение числа побед одной стороны к другой, то есть игра должа быть сбалансированной;
- критерий длительности — игра не должна длиться часами;
- критерий неоднозначности — результат игры по возможности не должен определятся на первых же ходах;
- критерий ходов-убийц (killer moves) — наличие ходов, резко усиливающих позицию одного из игроков;
- и прочие.
Вручную раздавать весовые коэффициенту такому количеству функций, конечно, глупо; и здесь, очевидно, был смысл обратится к живым игрокам.
Автор обратился к игрокам одного из крупнейших онлайн-сообществ любителей настольных игр за оценками 79 начальных игр. Опрос проводился попарными сравнениями и методом кросс-энтропии. Таким образом, получился комплект из оценок каждой из первоначальных игр.
Имея эти оценки и функции-критерии уже можно получить коэффициенты для каждого из критериев самым тривиальным из методов машинного обучения: линейной регрессии.
В результате получается достаточно точная функция (порядка 95% точности) оценки «интересности» каждой из игр, что позволяет перейти к построению механики синтеза новых наборов правил.
Модуль синтеза
При наличии языка описания правил, метода оценки игры и компьютерных игроков очевидным шагом становится сборка системы воедино. Авторы выбрали привычные генетические алгоритмы для синтеза новых игры из старых.
Общая схема работы здесь ясна:
- первое поколение игр получают оценки и отправляются в пул особей;
- особи скрещиваются и мутируют с получением нового поколения правил;
- правила нового пула особей проходят тест на валидность, во время которого отбрасываются бессмысленные сочетания правил; правила, расчет ходов в которых занимает слишком много времени; игры, почти не отличающиеся от оригинального поколения и так далее;
- переходим к п.1 с последним поколением правил.
И так до тех пор, пока хватает времени.
Впечатления и замечания
Всего за неделю работы алгоритм предложил 19 наборов правил, два из которых были позже изданы в качестве коммерческих игр. Я попробовал в них поиграть, и действительно — это простые, элегантные и интересные игры. «It's Alive!»
Удивила стройность системы: ни в одной из подсистем автор системы не использовал сложные или незнакомые широкой публике алгоритмы, все понятно, даже очевидно.
Ну и, конечно, разве не впечатляет возможность генерировать игры автоматически? В конце концов, многие из современных популярных компьютерных и настольных игр довольно просты в правилах.
Ссылки по теме: