Смешанный AI в игре DROD — человек+компьютер=?

    DROD — весьма необычная логическая игра. Главные ее особенности:
    • Пошаговость. В отличие от supaplex реакция не имеет значения.
    • Детерменированность. Элемент случайности отсуствует, любую позицию можно просчитать в уме, хотя обычно это очень не просто сделать.
    • Большое концептульное разнообразие головоломок. Благодаря этому игра надоедает гораздо медленнее чем, например, судоку.
    • Приключенческий антураж, придающий смысл процессу (в основной миссии мы делаем виртуальный мир DROD чуточку чище).

    Головомки состоят в том, чтобы убить всех монстров в комнате 38x32 клетки. Игрок управляет персонажем занимающем 1 клетку, который держит меч, занимающий еще одну из 8 соседних клеток. Каждый ход можно либо пойти на одну из 8 соседних клеток, либо повернуть меч, либо подождать. После чего по очереди ходят оставшиеся в живых монстры. Если они смогут занять клетку, на которой стоит игрок, он проигрывает и возвращается к началу комнаты.

    image

    Дополнительный интерес к игре придает таблица рекордов скорости (по количеству ходов) прохождения комнат. Она-то и является нашей целью. Но как можно применить компьютер к игре, с концептуально различными головоломками и астрономическим количеством вариантов (в каждый момент у нас 11 вариантов хода, а общее число возможных состояний комнаты на много больше чем в шахматах)?! Выход один — переложить интеллектуальную часть задачи на человека, а рассчетную (оптимизация решения по количеству ходов) — на компьютер.



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

    Первое что пришлось сделать — упростить модель игры для увеличения скорости симуляции ходов. Из-за этого упрощения многие элементы приходится заменять либо на равносильные в данной ситуации, либо на похожие, либо оптимизировать только решение части головоломки. Во-вторых пришлось придумать компактную схему хранения состояния комнаты и плюс к ней использовать архиватор, иначе место на жестком диске исчезает очень быстро, да и скорость IO заметно влияет на производительность. После чего был написан следующий простой переборщик:
    • Делаем из текущего набора позиций все возможные ходы. При этом одинаковые позиции убираются с помощью хэш-таблицы.
    • Выбираем N лучших по некоторой оценочной функции вариантов. (из-за дискретности значений оценочной функции их может получится чуть меньше чем N)
    • Печатаем наилучший вариант и возвращаемся к первому шагу.

    В качестве первой оценочной функции для первой комнаты было выбрано количество монстров в комнате-координата игрока по оси y (это обусловлено спецификой комнаты). Каково же было мое удивление, когда после запуска с всего лишь N=100000 вариантами (напомню, что это соотвествует количеству вариантов где-то после 5 ходов, при типичной длине решения 300 ходов) программа через несколько часов работы не только смогла пройти комнату (точнее основную ее часть, после которой добить оставшихся монстров проще простого), над которой я безуспешно бился уже не первый день, но и сделала это почти в 2 раза быстрее самого лучшего человеческого решения для этой комнаты! В итоге тандем «оценочная функция, придуманная мной»+переборщик смог проходить весьма существенный процент комнат. Остановить его могли только неподдерживаемые элементы, комнаты, в которых неудается придумать никакой разумной оценочной функции и трэпдоры (еще есть «грязь», с которой сходная проблема)…

    Трэпдор — это клетка, на которую можно встать только один раз. Как только вы с нее уходите, трэпдор падает вниз и образуется пустота. Каждый трэпдор увеличивает число вариантов в двое, а если учитывать, что они обычно заполняют целые области, то ни 10^5, ни 10^8 вариантов не помогают. Программа начинает рассчитывать множество по-существу одинаковых вариантов среди которых в один прекрасных момент правильного не оказывается. Казалось бы, ситуация безвыходная. Так я и думал, пока мне позарез не понадобилось найти решение подобной комнаты. Оказалось, простая модификация алгоритма решает проблему. В место выбора N лучших вариантов с точки зрения оценочной функции f, нужно выбирать N лучших вариантов с точки зрения величины random*exp(-const*f) (спасибо методу отжига за эту идею), где const определяется человеком с помощью пристального взгляда на потолок. Собственно при const стремящемся к бесконечности мы получим обычную схему выбора. Впрочем, в качестве платы, новый способ требует более аккуратного выбора оценочной функции (раньше было важно только упорядочение на множествах состояний, которое задает оценочная функция f, а теперь важны и сами значения). В нужной мне комнате, этот подход позволил найти неплохое решение. Хотя следует признать, что общая проблема трэпдоров осталось нерешенной, поскольку часто имеет значение топология остающихся трэпдоров, которую не удается выразить в виде оценочной функции, да и использование случайности больно бьет по вариантам решения, в которых не велика степень разумных разветвлений.
    Поделиться публикацией

    Комментарии 6

      +2
      А можно ссылочку на страничку с игрой?
        0
        может быть здесь?
          0
          Вы знаете, по слову DROD находится несколько игр, и все скриншоты не похожи на тот что выложен в топике.

          PS думаю что по указанной вами ссылке не та версия игры.
            +1
            не буду спорить, возможно Вы правы, тем не менее посмотрите тут
            большей похожести врядли можно найти
              0
              Да, Вы правы, на этот скриншот я не обратил внимание.
        +4
        caravelgames.com/Articles/Games_2/DownloadTCB.html — демо-версия TCB (DROD 3), в которую можно не ограниченно загружать user-made уровни, которые можно скачать здесь: forum.caravelgames.com/holds.php или из вложений к первым постам из топиков на этом форуме: forum.caravelgames.com/viewboard.php?BoardID=11. Так же имеет смысл посетить эту страничку: forum.caravelgames.com/downloads.php.

        Кроме того, имеется версия с уровнями KDD (не знаю точно полная версия или нет, в крайнем случае есть заведомо работающая альтернатива: caravelgames.com/Articles/Games_2/DownloadAE.html), с которых начиналась игра: caravelgames.com/Articles/Games_2/DownloadKDD.html.

        А полную версию TCB, улучшенную версию KDD и набор уровней JtRH (и кое-что еще) можно купить здесь: caravelgames.com/Articles/Games.html
        Когда у меня была подарочная карта, которой можно платить в интернете, я этой возможностью воспользовался, о чем не жалею.
        PS KDD=King's Dugan Dungeon, JtRH=Journey to Rooted Hold, TCB=The City Beneath.

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