Beyond simple card scoring. Part 1: Collecting Ideas.

В прошлой блог-теме я описал довольно простой scoring карт. Теперь постараемся развить идею и учесть недостатки прошлого оценщика про создании новой модели.

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

Изображение 1: Взаимосвязь отдельных компонентов в аркомаге.

На первой картинке изображена очень упрощённая связь между предприятиями, ресурсами, башней, стеной и разными типами урона.

Схема читается так:

Предприятия генерируют ресурсы, а достаточное количество ресурсов позволяет строить предприятия. К тому же достаточное количество ресурсов позовляет строить башню и стену. Стена защищает башню от прямого урона, но башня и дальше продолжает быть подверженной уронам по самой башне. Получается что стена защищает башню от дополнительного урона, т.е. амортизирует урон. Получается при достаточно большой стене остаётся только один способ атаковать башню - через tower damage.

Изображение 2: Взаимосвязь отдельных компонентов в более развёрнутом виде.

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

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

Исхожу я здесь из следующих упрощённых наблюдений:

Красные карты (руда) связанны с рудой, шахтами и стеной
Синие карты (мана) связанны с маной, монастырями и башней
Зелёные карты (отряды) связанны с отрядами, казармами и уроном

Башни и стены никак напрямую не влияют на предприятия и ресурсы. Однако влияют косвенно: Их постройка стоит ресурсы, если наш income (получение ресурсов каждый ход от предприятий) слишком низкий и мы всё время тратим нашы ресурсы на остройку башни и стены, то у нас не будет ресурсов на постройку предприятий, т.е. income будет постоянно низкий и это скажется на наших возможностях строить башню и стену, а также наносить урон противнику и рушить его предприятия. Поэтому желательно всегда иметь резерв ресурсов и хорошое количество предприятий. Стоить отметить, что если мы будет например постоянно играть зелёными картами (например которые наносят чисто урон), чья стоимость выше того что мы получаем каждый ход - у нас просто закончатся ресурсы.

Однако во-первых нет столько зелёных карт в колоде, во-вторых существует механизм кулдауна - т.е. просто не получится постоянно на одной ноте играть только зелёными (выходят случайно) и в-третьих обычно во время игры чередуются фазы защиты, постройки + фарма, и нападения на противника.

На изображении 3 (противник победил) хорошо заметно как у противника идёт прирост а потом трата ресурсов, т.е. его динамика игры пилообразная (копит несколько ходов много ресурсов для какой-то определённой карты, играет дорогой картой, потом снова копит и так далее. В то время как копит один ресурс использует другой, т.е. использует ресурсы поочерёдно давая каждому ресурсу более менее восстановиться).

Изображение 3: Визуализация изменения количеста ресурсов у обеих игроков во время игры. Изображение доступно здесь.

Примеры визуализации различных фаз в игре можно найти здесь. Source code (statistical language R) можно найти здесь.

На время забудем об игровых фазах и вернёмся к изображениям 1 и 2. Из схем 1 и 2 следуют вопросы:

Сколько ресурсов вообще стоит тратить на постройку предприятий и нужно ли нам их много? - Какое количество оптимальное?
Что лучше - строить башню, а значит делать упор на ману и монастыри или фармить отряды и строить казармы, чтобы наносить урон вражеской башне?
Стоит ли фармить ресурсы на победу через накопление ресурсов или же мы ожидаем быстрее либо построить нашу башню либо разрушить башню противника?
Как правильно регулировать наш income и трату ресурсов на карты и защитить от турбулентностей вызванные рандомом и действиями противника

Интуитивно кажется, что строить башню дешевле чем разрушать башню противника. Башню можно строить напрямую, а у противника скорее всего будет стена, которую сначала придётся разрушить, и только после мы сможем приступить к разрушению его башни через direct damage и tower damage (При этом оптимальнее использовать direct damage, по причине того, что противник сможет отстроить стену, и тогда эффективно против башни мы сможем использовать только tower damage, в то время как до этого мы могли использовать и то и другое сразу).

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

Статистическое подтверждение данной идеи (если играть по правилам столицы) можно найти в этих двух статьях: статья 1, статья 2 (Примерно только 20% игр заканчиваются через разрушение вражеской башни).

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

Первая неточность состояла в том, что z-координата состояла из трёх типов ресурсов. Но этот факт не особо влиял на саму оценку.

Во-вторых следует уделить внимание вспомогательным функциям, которые отвечали за оценку параметров карты. Какие значения получают вспомогательные функции? Если карта например наносит 20 урона, но у противника стена высотой 15, а башня высотой 30, то эффективный урон по башне будет 20-15 = 5.

Для начала опишем заново вспомогательные функции h и g и изменим их названия:

Для победы через фарм ресурсов:
Для победы через постройку башни:
Для победы через разрушение башни противника:

Изображение 4: Переход между двумя состояниями g1 и g2.

Вернёмся к вопросу какие значения получают эти функции - что такое v?

Сначала высчитываем разницу между двумя состояниями игры (Изображение 4): game state 1 (g1) и game state 2 (g2). Дальше выбираем то значение, которое отвечает за изменение башни нашего персонажа/противника или ресурсов. Это значение и есть v (value). Причём нужно учесть, что количество ресурсов не может быть меньше нуля. Башня противника может быть меньше нуля, а наша башня может быть выше порога тета.

В-третьих значения v находятся не между значениями 0 и 1, а между минус бесконечность и 0, но на самом деле нет таких карт, которые дадут такие огромные отрицательные значения. Отрицательные значения в оценке можно получить например, если мы сами себе наносим урон или теряем ресурсы (причём тут нужно учесть и стоимость самой карты тоже).

Проблемы оценщика

Никак не учитывается важность стены. Можно попробовать учитывать какой урон может выдержать стена прежде чем она падёт и враг напрямую сможет атаковать башню. Проблема в том, что можно разрушить башню и просто прямыми ударами по ней - не нанося никакого урона стене - и смысл стены встанет под вопрос. Давать же какие-то фиксированные значения для оценщика мы будем до последнего стараться избегать и только использовать, если на то будет веская причина. Каждое констатное значение подозрительно и должно оправдывать свою полезность.
Никак не учитывается важность предприятий: Оценщик не умеет считать наперёд. В принципе это поправимо, если использовать какой-то дополнительный алгоритм. Однако встаёт вопрос: Как считать полезность какой-то карты на постройку предприятий. Например можно исходить из того, что противник не будет нападать на нас все остальные ходы и не будем играть никакой картой. Но это конечно очень слабая аппроксимация. Например для победы через фарм ресурсов нужно 150 ресурсов каждого типа. У нас 50 отрядов и 4 казармы, т.е.: (150-50)/4 = 25 ходов до того как мы соберём 150 отрядов. Теперь у нас руках появилась карта, которая даёт +2 казарамы и стоит 7 отрядов, считаем: (150-(50-7))/6 = 17.83 = 18 ходов. Но это предполагает, что мы не будем тратить отряды вообще - играя по правилам столицы это не реалистично. Также проблема, если у нас например 0 шахт, то по сути +2 казармы это не плохо, но и при 50 отрядах не особо что-то даёт в принципе.
Проблема с ресурсами. На данный момент ресурсы учитываются только для победы через фарм ресурсов, а то что ресурсы нужно вообще для всего просто игнорируется. Проблема даже хуже чем со стеной, но примерно на одном уровне, что и проблема с предприятиями. Следует как-либо образом, по возможности, учесть игровые фазы описанные выше и следить за income.
Карты из категории "играем снова" не учитываются как эффект вообще. Их важность состоит в том, что мы можем почистить наши карты на руках от мусора (карты, которые не играют практически никакой роли во время всей игры (их значения слишком малы), либо чьи эффекты мы не можем использоват сейчас (пример: "если стена > врага, то ..."), либо они просто очень много стоят, а у нас совершенно нет ресурсов, ...).
Оценщик не учитывает ходы - он их просто не видит, а видит только разницу в значениях между игровыми состояниями (g1, g2). В принципе это не проблема, т.к. можно посчитать комбинацию карт (тактика) за одну карту и передать её оценщику. Как давать штраф или бонус за комбинацию состоящую из нескольких разных ходов (между которым находятся ходы противника) ещё пока неясно. Также он не используют информацию о кулдауне, не использует информацию о прошлых у будущих ходах (имеет смысл брать рамку (frame) размером в 2-3 хода).
Проблема с картами с условиями и эксплоитируемыми картами. Это такие карты как "если башня больше чем у врага, то будет то-то..." или такие карты, где можно максимировать эффект - такие как вор, если дождаться подходящего момента, или например карта сдвиг. Оценщик не может напрямую различить такие сложные эффекты. Можно каким-либо алгоритмом просчитывать такие сложные эффекты (примеры использования такого алгоритма для поиска минимальных и максимальных эффектов можно найти здесь и здесь).
У оценки нет веса. Оценка пока что линейная и никак не учитывает типы победы и количество различных эффектов и стоимость у карт. Например разное количество карт, которые строят стену и разное количество карт с уроном по башне и стене и так далее. Такую информацию можно тоже активно использовать.
Победа через фарм ресурсов практически не играет роли играя по правилам столицы. Нужен например weighted scoring.
Напрямую не учитываются действия противника, и принципиальная проблема с некоторыми картами. Для противника можно сделать аналогичную систему координат, т.е. по сути это не проблема. Однако проблема например есть с определёнными картами: есть карта, которая наносит 7 урона обоим башням. У нас башня 1, у противника 7. После приминения этой карты у нас будет башня -6, у противника 0. Теперь считаем скоринг: max(-7/50, 1) = 1, значит играть картой можно. В принципе проблема поправима.

Итоги

Была надежда использовать какой-нибудь очень простой оценщик карт, для всех игровых ситуаций. Мотивацией было создать оценщик, который бы мог динамично оценивать карты, но не использовать какие-либо фиксированные значения, как это можно было увидеть в мною описанном боте (Проблема оценщика с фиксированными значениями это огромное количество свободных параметров, которые постоянно придётся оптимировать). К сожалению всё не так просто и приходится штопать наш оценщик где только можно, при этом штопая одну щель, открывается в другом месте иная. Использование оценщика для описания трёх возможных типов побед ведёт с собой тоже некие неприятные проблемы - так победа через фарм ресурсов не играет практически никакой роли при правилах столицы, но существенно усложняет ситуацию с ресурсами. Также оценщик в первую очередь умеет только оценивать карту в данный момент. Данный оценщик лишь даёт информацию о том что даёт карта в плане победы, т.е. насколько ближе она нас подвинет к победной ситуации, но не умеет думать наперёд, т.е. иногда лучше приберечь очень хорошую карту до определённого подходящего момента, а не пользоваться ей прямо сейчас. По сути оценщик очень слепой, поэтому есть желание создать например алгоритм-оценщик (т.е. гибрид из оценщика и анализатора комбинаций и ситуаций), который бы мог тактичным, но и мог бы реагировать на ходы противника и мог бы амортизировать турбулентности во время игры. Иными словами нужен более умный подход в целом.

Идеи

Есть следующие вопросы: Как оценивать карты и комбинации карт - как посчитать какая из комбинаций лучше? Карт имплементировать тактику - как научить ИИ планировать свои ходы в аркомаге? Проблема прошлого подхода была в том, что была создана функция оценки и карты уже подстраивались под него, т.е. подбивали молотком где только можно.

Теперь попробуем иной подход - сначала соберём различные идеи, мотивированные человеческой игрой, создадим различные функции-помощники, где каждая функция будет делать хорошо именно свою задачу и после этого подумаем как решать какая из комбинаций лучше. Уже после этого можно будет подумать какая фунция-оценщик будет подходящей.

Для начала нам нужно несколько вспомогательных функций. Как именно они работают и какие второстепенные параметры они получают на данный момент нас не интересует. Главное понять их идею и зачем они будут нужны далее.

change_waiting_time(card, ...) - Функция делает следующее: Она получает карту и старается уменьшить или увеличить время ожидания этой карты. Напрямую уменьшить или увеличить время ожидания можно через получение и уничтожение ресурсов и предприятий. Функцию можно применить к нам - т.е. какими-то картами уменьшить например нафармить ресурсы напрямую - например карта вор ворует у врага ману и руду и даёт её нам - т.е. мы получаем дополнительные ресурсы не от предприятий. Аналогичная ситуация и с противником - воруя у него ресурсы или разрушая предприятия, мы не даём сыграть ему какой-то сильной картой и тем самым выигрываем время. Если для тех карт, которых могут уменьшить время ожидания карты Х не хватает ресурсов, то мы рекурсивно ищем ресурсы для них (нужно не забыть учесть множество нюансов). Об этом можно прочитать ещё здесь.
maximize_effect(card, ...) - эта функция получает карту и старается найти такую комбинацию (или несколько) из карт, которая позволила бы нам предсказать как скоро мы смогли бы сыграть какой-то картой ещё больше в нашу пользу, т.е. максимировать эффект этой карты. Пример карты наподобие "если башня > противника, то будет то-то ...".
min_max_card_effects(card, ...) - данная функция даёт нам информацию о минимальных и максимальных эффектах какой-либо карты. Важно знать на что принципиально способна какая-либо карта, т.к. наивная симуляция не всё сможет увидеть.
get_cheapest_series_combos(...) - идея состоит в том чтобы потратив как можно меньше маны, можно было например за 2-3 хода победить через постройку башни. Иногда бывают такие ситуации, что синих карт на руках много, а маны мало - и нужно найти такую комбинацию из нескольких ходов, где можно победить через минимальные затраты. Не обязательно для башни или маны, но суть в экономии.
can_win_in_x_turns(...) - ничего примечательного - смотрит можно ли победить какими-либо способами через Х ходов. И для противника и для меня. Учитывает и победу через ожидание и смеси (действия и ожидание). Ожидание = сбросить какую-то ненужную карту. Ненужность можно оценить функциями выше.
do_nothing(...) - довольно примитивный аппроксиматор, который симулириет то что я или противник или оба вместе несколько ходов ничего не будет делать. От части может использоваться в функциях описанных наверху. Здесь стоит развить идею дальше - т.е. помимо наивной идеи придумать как ещё можно описать будущие действия (прогнозировать). Например конечно можно использовать старые данные (data recycling). Такое можно сделать, если сохранять все предыдущие игровые состояния. Аппроксимацию можно использовать при малых количествах ходов (2-3). Однако если использовать слишком долго и часто, то может сказаться негативный эффект этой слишком простой аппроксимации. Однако если использовать слишком сложный симулятор, то скорее всего могут возникнуть другие проблемы. Здесь нужно проверять - лучше даже просчитывать.
play_card(card, ...) - симулятор игры какой-то картой. Получает как все вышеописанные функции какое-то состояние игры - которое может быть и фейковым. Симуляцию используют все выше указанные функции. В основном с фейковыми состояниями игры (game state).

Далее нужен будет поисковик по картам - который ищет карты по каким-то заданным эффектам. При нахождении новых интересных функций, они будут собранны и выложены здесь в блог (идеи. никому не нужные горы исходного кода я не буду выкладывать).

Примечание: На этом месте я и закончил где-то год назад. Теперь нужно двигаться дальше и посмотреть как можно связать все эти функции вместе: нужен какой-то алгоритм, который будет решать как играть на основе комбинаций, которые предоставяет ему эти функции-помощники. По сути нам уже не нужна будет просто оценка единичных карт, а нужно будет оценка различных тактик. Возможно здесь не нужно сильно абстрагировать, а использовать более насущные вещи как слежка за действиями противника и реакция на его ходы (деф, контратака, фарм), стараться поддерживать хороший income и придерживать хорошие и сильные карты (теперь уже можно оценить теоретическую и актуальную силу карты (здесь можно уже оценивать эффект и стоимость карты через least squares)). Но честно говоря это начинает напоминать проблему с тем ботом у которого было слишком много свободных параметров. На языке вертится слово machine learning, но для начала было бы всё-таки интересно создать бота без него.

Дальнейшие идеи, которые пока промелькивали в моём блоге, но где я пока ещё не успел подумать насколько от них есть толк:

Проблема алтернативных издержек в том, что нужно посчитать упущенную возможность. Для этого делается оценка всех возможностей. Но сейчас и стоит вопрос как оценить карту. Естественно имея оценку каждой карты или комбинации я уже смогу сказать что я упускаю на данный ход. Мне кажется, что это не совсем правильный подход к проблеме на данный момент, т.к. не имеем пока что ещё никакой нормальной оценки вообще.

Насчёт скрытой марковской модели (hidden markov model): В принципе это интересный подход, т.к. можно описать вероятностями переход из одного состояния игры в другое. Это интересно, но ещё не до конца ясно как можно применить.

Кстати вот эта игра: 74555157 навела меня на мысль посчитать постройку шахт, монастырей и казарм в среднем (т.е. чего ожидать в среднем). Проблема в этой игре состоит в том, что эти персонажи помогали друг другу строить, а нужно учесть ситуацию, где будут рушить у друг друга. Тут можно взять статические данные прошедших игр и посмотреть как выглядят производства в конце игры (в зависимости от типа победы) и примерно прикинуть их рост в среднем (Пример: размер шахты / количество ходов).

Т.е. если после какого-то хода у нас значение ниже среднего, то могут возникнуть проблемы с ресурсами и т.д.

Собрание полезных ссылок