DROD — весьма необычная логическая игра. Главные ее особенности:
Головомки состоят в том, чтобы убить всех монстров в комнате 38x32 клетки. Игрок управляет персонажем занимающем 1 клетку, который держит меч, занимающий еще одну из 8 соседних клеток. Каждый ход можно либо пойти на одну из 8 соседних клеток, либо повернуть меч, либо подождать. После чего по очереди ходят оставшиеся в живых монстры. Если они смогут занять клетку, на которой стоит игрок, он проигрывает и возвращается к началу комнаты.
Дополнительный интерес к игре придает таблица рекордов скорости (по количеству ходов) прохождения комнат. Она-то и является нашей целью. Но как можно применить компьютер к игре, с концептуально различными головоломками и астрономическим количеством вариантов (в каждый момент у нас 11 вариантов хода, а общее число возможных состояний комнаты на много больше чем в шахматах)?! Выход один — переложить интеллектуальную часть задачи на человека, а рассчетную (оптимизация решения по количеству ходов) — на компьютер.
Когда я приступал к задаче я не надеялся на какой-либо успех. В конце-концов комнаты в DROD бывают столь сложны, что над ними приходится думать месяц. Но все же я решил рискнуть.
Первое что пришлось сделать — упростить модель игры для увеличения скорости симуляции ходов. Из-за этого упрощения многие элементы приходится заменять либо на равносильные в данной ситуации, либо на похожие, либо оптимизировать только решение части головоломки. Во-вторых пришлось придумать компактную схему хранения состояния комнаты и плюс к ней использовать архиватор, иначе место на жестком диске исчезает очень быстро, да и скорость IO заметно влияет на производительность. После чего был написан следующий простой переборщик:
В качестве первой оценочной функции для первой комнаты было выбрано количество монстров в комнате-координата игрока по оси y (это обусловлено спецификой комнаты). Каково же было мое удивление, когда после запуска с всего лишь N=100000 вариантами (напомню, что это соотвествует количеству вариантов где-то после 5 ходов, при типичной длине решения 300 ходов) программа через несколько часов работы не только смогла пройти комнату (точнее основную ее часть, после которой добить оставшихся монстров проще простого), над которой я безуспешно бился уже не первый день, но и сделала это почти в 2 раза быстрее самого лучшего человеческого решения для этой комнаты! В итоге тандем «оценочная функция, придуманная мной»+переборщик смог проходить весьма существенный процент комнат. Остановить его могли только неподдерживаемые элементы, комнаты, в которых неудается придумать никакой разумной оценочной функции и трэпдоры (еще есть «грязь», с которой сходная проблема)…
Трэпдор — это клетка, на которую можно встать только один раз. Как только вы с нее уходите, трэпдор падает вниз и образуется пустота. Каждый трэпдор увеличивает число вариантов в двое, а если учитывать, что они обычно заполняют целые области, то ни 10^5, ни 10^8 вариантов не помогают. Программа начинает рассчитывать множество по-существу одинаковых вариантов среди которых в один прекрасных момент правильного не оказывается. Казалось бы, ситуация безвыходная. Так я и думал, пока мне позарез не понадобилось найти решение подобной комнаты. Оказалось, простая модификация алгоритма решает проблему. В место выбора N лучших вариантов с точки зрения оценочной функции f, нужно выбирать N лучших вариантов с точки зрения величины random*exp(-const*f) (спасибо методу отжига за эту идею), где const определяется человеком с помощью пристального взгляда на потолок. Собственно при const стремящемся к бесконечности мы получим обычную схему выбора. Впрочем, в качестве платы, новый способ требует более аккуратного выбора оценочной функции (раньше было важно только упорядочение на множествах состояний, которое задает оценочная функция f, а теперь важны и сами значения). В нужной мне комнате, этот подход позволил найти неплохое решение. Хотя следует признать, что общая проблема трэпдоров осталось нерешенной, поскольку часто имеет значение топология остающихся трэпдоров, которую не удается выразить в виде оценочной функции, да и использование случайности больно бьет по вариантам решения, в которых не велика степень разумных разветвлений.
- Пошаговость. В отличие от supaplex реакция не имеет значения.
- Детерменированность. Элемент случайности отсуствует, любую позицию можно просчитать в уме, хотя обычно это очень не просто сделать.
- Большое концептульное разнообразие головоломок. Благодаря этому игра надоедает гораздо медленнее чем, например, судоку.
- Приключенческий антураж, придающий смысл процессу (в основной миссии мы делаем виртуальный мир DROD чуточку чище).
Головомки состоят в том, чтобы убить всех монстров в комнате 38x32 клетки. Игрок управляет персонажем занимающем 1 клетку, который держит меч, занимающий еще одну из 8 соседних клеток. Каждый ход можно либо пойти на одну из 8 соседних клеток, либо повернуть меч, либо подождать. После чего по очереди ходят оставшиеся в живых монстры. Если они смогут занять клетку, на которой стоит игрок, он проигрывает и возвращается к началу комнаты.
Дополнительный интерес к игре придает таблица рекордов скорости (по количеству ходов) прохождения комнат. Она-то и является нашей целью. Но как можно применить компьютер к игре, с концептуально различными головоломками и астрономическим количеством вариантов (в каждый момент у нас 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, а теперь важны и сами значения). В нужной мне комнате, этот подход позволил найти неплохое решение. Хотя следует признать, что общая проблема трэпдоров осталось нерешенной, поскольку часто имеет значение топология остающихся трэпдоров, которую не удается выразить в виде оценочной функции, да и использование случайности больно бьет по вариантам решения, в которых не велика степень разумных разветвлений.