Пользователь
0,0
рейтинг
6 августа 2014 в 23:33

Разработка → Эволюционный дизайн игр

image

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

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

Книга, что попалась не так давно на глаза, объединяет в себе оба мира: в ней, с одной стороны, описаны интересные в совокупности алгоритмические приемы; результат же работы — настольная игра «Yavalath» на приложенной картинке — был издан и пользовался достаточно широкой для абстрактной игры популярностью.

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

Так чем меня удивила книга? В двух словах: книга посвящена Ludi, системе автоматической генерации настольных игр за авторством Кэмерона Брауни (Cameron Browne). Система была разработана в рамках кандидатской работы (то есть западным аналогом кадидатской — PhD thesis) под названием «Эволюционный игровой дизайн» (Evolutionary Game Design) и способна самостоятельно формировать правила игр, играть в них против себя же, оценивать каждую на интересность и отбирать наилучшие варианты. В конце концов, она даже названия для игр подбирает самостоятельно!

Ну, хватит прелюдий, давайте перейдем к делу.

Ludi, система эволюционного игрового дизайна


Система состоит из следующих основных элементов:

  • язык описания правил игры, или Game Description Language;
  • универсальные игроки (General Game Players);
  • модуль стратегии;
  • модуль критики;
  • модуль синтеза.


Язык описания игр позволяет описать а) конечные, б) дискретные, в) пошаговые, д) детерминированные игры с в) полной информацией. Сюда подойдут самые обычные шашки, шахматы, «крестики-нолики», Го и в целом существенная доля всех прочих классических настольных игр.

Универсальные игроки интерпретируют сформулированные на GDL правила, способны составить список легальных шагов и понять, что игра закончилась.

Модуль стратегии оценивает текущее положение каждого из игроков и оценивает возможные ходы.

Модуль критики оценивает уже саму игру на предмет различных объективных и не очень параметров, которые автор называет «эстетическими», т.е. оценивающими игру с точки зрения интереса живых игроков.

Модуль синтеза игр интегрирует все вышеприведенные подсистемы, формируя новые сочетания правил на базе оценок модуля критики.

В целом цикл работы системы выглядит следующим образом:

  1. на GDL описывается несколько десятков (79 в работе автора) игр, универсальные игроки их читают и играют друг с другом при помощи модуля стратегии;
  2. каждая из проведенных партий получает оценку модуля критики;
  3. эти оценки и правила игр (в виде дерева правил — сродни обычному абстрактному синтаксическому дереву) подаются на вход модулю синтеза, который, в свою очередь, формирует, скрещивая между собой, новые деревья правил — следующее поколение игр;
  4. отправляемся к п.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. первое поколение игр получают оценки и отправляются в пул особей;
  2. особи скрещиваются и мутируют с получением нового поколения правил;
  3. правила нового пула особей проходят тест на валидность, во время которого отбрасываются бессмысленные сочетания правил; правила, расчет ходов в которых занимает слишком много времени; игры, почти не отличающиеся от оригинального поколения и так далее;
  4. переходим к п.1 с последним поколением правил.


И так до тех пор, пока хватает времени.

Впечатления и замечания


Всего за неделю работы алгоритм предложил 19 наборов правил, два из которых были позже изданы в качестве коммерческих игр. Я попробовал в них поиграть, и действительно — это простые, элегантные и интересные игры. «It's Alive!»

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

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

Ссылки по теме:

Владимир Казанов @VlK
карма
190,6
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (21)

  • 0
    Сдается мне, что принципиально новой игры таким способом не получить. Лишь модификацию существующей, как превратить классические шашки в поддавки.
    • +1
      Смотря что считать принципиально новой игрой. Шашки и шахматы — суть одна, но разница между ними огромна. В Yavalath, например, ключевой парой правил является «собери 4 в ряд, но 3 в ряд — это проигрыш». Точно знаю, что похожих пар в классических играх нет.
    • 0
      Принципиально новые игры — это вообще очень большая редкость. Подавляющее большинство игр как раз и являются такими модификациями.

      Скажем все шутеры по большому счету модификации Wolfensteinn 3D и DOOM.

      А вот сгенерить на основании DOOM скажем Quake, Half-Life и Call of Duty такая система в теории смогла бы, если бы в нее заложили все разнообразие правил и особенностей таких игр. Но я уже написал ниже что это маловероятно из-за нелинейного роста сложности алгоритмов.

      Хотя если взглянуть шире то все компьютерные игры являются эволюционными модификациями игр из реальной жизни. В войнушку дети играли за тысячи лет до появления компьютеров и DOOM.

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

        В конечном счете творчество остается за человеком. Смена декораций важна. Причем нельзя просто сменить декорации к существующей механике — это будет слишком заметно. Как шахматы с фигурками из резной слоновой кости против простых деревянных — все-равно это шахматы. И обратно, недостаточно изменить 1-2 параметра механики игры, чтобы получить что-то новое. В качестве негативного примера такой штамповки можно вспомнить популярную в свое время игровую консоль «Break game», на которой ушлые китайцы писали «999 игр», хотя по-сути там было только 3: тетрис, змейка и пинбол.
      • 0
        особенно portal и katamary damacy
  • 0
    Я сейчас пытаюсь сделать свою настолку. По сложности сопоставима с настольной игрой престолов. Проблему поиска баланса обычно решают ручным тестированием — играют опытные игроки в своей компании, дорабатывают и по новой итерация. Долго и не интересно игрокам тестить сырые правила. Вот бы автоматизировать, прогнать пару тысяч тестов на компьютере, посмотреть статистику, поменять правила, прогнать ещё пару раз, а потом уже вручную потестить. Кроме книги, вы софта никакого не видели?
    • 0
      Как вариант: напишите несложный AI и прогоните тесты. Можно даже с разными уровнями соперников (смоделировать игру новичка с опытным, например). Ясно, что приближение не очень точное получится, но иногда этого достаточно.
      • +1
        Вопрос в том будет ли это экономически оправдано… т.е. какова будет стоимость написания такого AI.
        • 0
          Как и везде, в общем-то. Плейтесты тоже время отнимают. Если игра достаточно сильно зависит от баланса (некоторые игры делают фокус на тему, например, или что еще, где баланс не критичен), то написание простого алгоритма может быть оправдано. И если AI будет нацелен лишь на тестирование, то можно сильно не заморачиваться о его оптимальности (все равно ему с людьми не играть, лишь бы он играл по правилам и в сторону выигрыша). ИМХО, для большинства игр хватит простого A*.
          • –1
            Эм. А при чем здесь A*? :-) Мы не путь на графе ищем вроде как.
    • 0
      Готового вот прям софта, честно говоря, не видел. Есть языки, на которых можно описывать правила в игры; и если есть такие языки, то почти наверняка есть универсальные игроки в игры, описанные в таких терминах.

      Но для конкретной игры, или хотя бы просто ограниченно меняющейся в деталях игры, простейших игроков можно сравнительно быстро сделать.
  • 0
    Есть подозрение что по мере усложнения игр сложность оценки и генерации будет расти нелинейно и сделает дальнейшее развитие этого способа невозможным. Ведь интересность игр — это по сути дела отражение человеческой психологии, а она до сих пор слишком сложная для полноценного моделирования — иначе давно бы уже и социальные процессы точно рассчитывали и книги с фильмами генерили.

    Но сама по себе статья очень интересная, расширяет кругозор.
    • 0
      Не надо что-то подозревать, я совершенно точно скажу, что сложность игры будет, эм, экспоненциальной функцией :))) Секрета здесь нет.

      Однако, абсолютно выигрышный ход не нужен, практически всегда используются эвристики. В приведенной работе автор вообще все считал очень поверхностно, и, как видите, этого было достаточно.
      • 0
        Автор считал достаточно простые игры сами по себе, если я правильно статью понял.
        • 0
          Если шахматы простые, то да. Вообще, у него там была отсечка: если ходы считаются дольше 15 секунд, то такой комплект правил выбрасывается.
          • 0
            Я имел в виду простоту правил. Сравните сложность правил шахмат и Starcraft II например. Или Civilization 5.
            • 0
              Да, в них, конечно, minimax просто вечность будет обсчитывать варианты, именно поэтому проще брать ограниченный класс игр. Однако, есть кой-какие другие алгоритмы…

              Построение такого рода игр надо, конечно, делать кусками, либо апроксимируя, скажем, среднюю скорость сбора ресурсов; или разбивая на небольшие подигры. Уж карты-то для Старкрафта точно можно автоматически генерировать и балансировать. И, скажем, гарантировать, чтобы при равном количестве ресурсов зерги и терраны имели при разном количестве юнитов разную огневую мощь.

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


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

                Собственно он в этом плане как раз близок к шахматам — важно не количество а правильно подобранная стратегия и набор юнитов.

                Даже для карт придется учитывать и разные типы урона, и скорость перемещения, и рельеф самих карт.

                Например есть такой параметр как удобство дропа — насколько удобно прилететь и высадить десант к рабочим.
                • 0
                  я не недооцениваю, а сознательно упрощаю. В обсуждаемом в работе автора классе игр шесть десятков критериев оценки каждой игры. Для старткрафта будет по меньшей мере не меньше, и это нормально, подобная задача — не на вечер работы, и даже не на месяц, разумеется.

                  Даже только карты, их генерация и оценка — уже сама по себе отдельная большая тема, конечно.
  • +1
    А можно ссылку на саму систему Ludi? я не вижу на сайте автора никаких ссылок и гуглится почему-то с трудом.
    • 0
      Саму систему я не нашел. Зная как работают аспиранты что здесь, что на западе, там просто стопка разнородных скриптов :-)

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.