В субботу утром вернулись с В.М. из первого совместного путешествия — по северу Италии. День в Милане (сгоняли в Швейцарию), пять дней в тосканской деревушке не слишком далеко от Флоренции, и ещё шесть дней в Лигурии, у моря (сгоняли на день в Ниццу и Монако). Ехал я в том числе чтобы проверить, каково нам будет общаться на таком длительном промежутке, да ещё и в новой непривычной обстановке.
Серебро в Legends of Code and Magic. Вот эта штука заставила напрячься по настоящему. Во-первых, игра модальная — т.е. сперва идёт драфт и тебе нужен один движок ИИ, а потом начинается собственно матч и тебе нужен другой движок, тем не менее решения принятые первым влияют на решения второго. Во-вторых, игра достаточно случайная. Чтобы это нивелировать (видимо) с каждым соперником проводится по два матча. Я бы проводил вообще до двух побед, как в MtG принято. В третьих, сложность игровых ситуаций иногда просто зашкаливает — столько всего надо учесть и сделать за ход.
Как всегда, начал я с простых эвристик. Для драфта — оценочная формула, сравнивающая эффект карты с её стоимостью и приоритизирующая атаку. Игровой движок — просто "атакуй всеми в противника как можно быстрее", т.е. типичный архетип аггро. С этим добром я умудрился добраться до бронзы. В бронзе такой фигни стало критически не хватать, и я сел пилить симуляцию. Аггро решил оставить, поэтому для экономии ресурсов симуляция включалась только в случаях когда у противника есть Провокаторы — существа, не дающие атаковать оппонента напрямую. Тогда рассчитывался способ с минимальными для меня потерями ликвидировать защитников и самых хрупких атакующих, сохранив при этом максимум своих. Потом симуляции пришлось добавить ограничение по времени, ибо его стало не хватать для просчёта всех вариантов. Потом отсеивание лишних планов атак — например, раз у противника есть Провокаторы, то все планы начинающиеся не с атаки в провокатора просто убирались из пула. Ближе к концу я поступил даже эффективнее — выкидывал все планы, где атаки в провокатора шли после атак в любые другие цели. В итоге планы оставались только те где провокаторов выносили в самом начале.
Сама симуляция была написана отдельным классом и обвязана тестами. Оо, какими полезными в этой архитектуре оказались отдельные юнит-тесты. Сколько позиций я получил просто отлавливая и исправляя баги в симуляции — вспомнить страшно. Хорошо отлаженный посредственный код работает лучше гениального, но сляпанного абы как и с ошибками — особенно когда выполняется кучу раз в разных условиях, где вылезают все граничные состояния.
Ещё один серьёзный недостаток моей симуляции — я считал только один порядок атакующих. Т.е. сперва атакует существо m, потом n и так далее, необязательно в том порядке в котором они стоят на поле. Идея как перечислить все варианты планов для одного порядка пришла ко мне в автобусе по дороге на работу, и я радостно её реализовал. Но как перечислить все вероятные вариианты для всех порядков? Уже набросанный класс симуляции не позволял так легко передавать и учитывать разные порядки атак, да и по времени симуляции я иногда был впритык. У меня была мысль расширить то как в симуляции хранится план и просто изначально генерить все возможные перестановки атакующих, но там было бы много одинаковых по сути планов, которые просто занимали бы вычислительное время. Если все провокаторы убиты, неважно в каком порядке отстреляются по игроку остальные существа. Но лёгкого способа обрезать такие ветви я так и не придумал.
Но такой симуляции оказалось недостаточно, и пришлось оптимизировать ещё и призыв существ. На поздней игре, где маны много, уже возможно вызывать по 2~3 существа за ход. И какое сочетание существ (из имеющихся в руке) будет оптимальным, это сложный вопрос. Я уже знал что по сути это задача укладки рюкзака (точнее, её вариант под названием 0-1 рюкзак), но про алгоритм решения только слышал что на больших наборах он очень неоптимален. И да, я помнил что задача эта NP-сложная. Но теперь пришлось закопаться в это поглубже и выяснить для себя, как 0-1 рюкзак решается методами динамического программирования (на псевдокод метода ветвей и границ я только раз взглянул и понял что любой другой способ скорее всего будет проще). В итоге ДП-метод был сделан, немного протестирован и закинут в бота. С этими дополнениями бот рванул в первую сотню бронзовой лиги и плотно там обосновался.
Дальнейшая оптимизация выглядела так: я открывал те матчи, которые бот проиграл и отсматривал их в реальном времени, примечая где и что можно было сделать лучше. Для каждого такого случая я дописывал в бота отдельные ветки логики либо поправлял коэффициенты весов в симуляции. Помимо этого я задумался над оптимизацией логики в фазе драфта, которую я незаслуженно обходил вниманием до того. В итоге прошёл простым путём — отсмотрел список карт глазами, и вручную выбрал списки "бомб", которые надо брать в первую очередь и "агрессивных существ" которые хорошо ложаться в наш игровой план "разыгрывай парней и бей ими лицо".
С этими добавлениями через полчаса после очередного сабмита я наконец увидел заветное сообщение "Ты лучше босса и через две минуты будешь переведён в серебряную лигу". Это был триумф. Правы были люди из чатика — без симуляции и серьёзных минмаксов из Бронзы не вылезти. В серебре мой бот устаканился примерно на 300 месте из 450. Но там противники — мама не горюй, и в золото выйти, похоже, уже не получится. Но даже серебро в таком сложном соревновании, я считаю, очень значительное достижение.
Серебро в Code of Kutulu. Золото пока закрыто, в серебре я болтаюсь в самом низу. Такое впечатление что просто случайно хорошо подобрал эвристики и с противниками немного повезло. Ну и исправил много багов.
Выводы:
Есть впечатление что чтобы продвинуться выше в Code of Kutulu, обязательно придётся делать симуляцию и минимакс. Ну что ж, если так - это будет интересно. А пока жду третьего числа и открытия серебра в Legends of Code and Magic. Там надо написать минимакс хотя бы для одного боя.
Исправление было довольно простым - раз мы ориентируемся по графу, надо просто при его создании находить все узлы-тупики (у которых только одна связь) и удалять их, пока таких не останется. Такая схема полностью удалит лабиринт, в котором нет ни одного кольца, но таких я в картах пока не видел. Пока бот болтается примерно посреди ростера в бронзовой лиге. Надо делать нормальный поиск в ширину от текущей позиции, чтобы идти не просто в ближайшую менее опасную клетку а планировать перемещение хотя бы хода на три.
Только мы с другом заказали на двоих набор второй редакции BattleLore и я начал подумывать втянуть его в GorkaMorka, как Games Workshop выпускает Kill Team. Это skirmish-вариант Warhammer 40000 для тех кто побаивается сразу окунаться в такое долгое и затратное хобби.
Для Kill Team не нужна армия на 2000 очков - достаточно отряда до 10 фигурок. Бой, как я понял, более интерактивный чем в 40К, юниты активируются по очереди (а не "я сходил всеми своими, ты сходил всеми своими, которые остались в живых"). Цена стартового набора в 80 фунтов конечно немного расстраивает, но возможно получится обойтись кодексом (он же книга правил) и парой отрядов. Тем более я давно хотел поиграть Тау
Кстати, что меня порадовало - в стартовый набор не включён так горячо любимый Games Workshop космодесант. Нет, понятно, это лицо всей франшизы, но видеть его во всех стартерах как-то надоело. Зато здесь фракции стартера это Адептус Механикус (техножрецы) и Культ Генестилеров (здесь они не относятся к Тиранидам, Тираниды отдельная фракция).
Вчера взял с собой В.М. на настольные посиделки у друзей. С одним из них она уже знакома, заодно познакомил с остальной частью нашей игровой тусовочки. Сыграли всего одну партию в Мёртвый Сезон (зато долгую, ибо впятером), но вечер провели отлично. Посмотрели на кролика, поели вместе, повеселились. Под конец отправил её домой на такси.
Скоро должен приехать BattleLore, уже руки чешутся что-нибудь там покрасить
