Beyond simple card scoring. Part 2: Everything about Cards

HearthStone интересней Аркомага, но Аркомаг намного проще чем HearthStone и годится больше для анализа и сборки идей. ;)

---

Понятия

Для начала опишу некоторые мною используемые понятия:

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

Про карты с условиями и эксплуатируемые карты я писал тут.

Предприятия: шахта, монастырь, казарма

Ресурсы: руда, мана, отряды

Что такое "комбинация из карт" (cards combination)?



Комбинация из карт это серия карт, которая может быть разделенна ходами противника. Серия из карт может являтся какой-то тактикой, которой мы придерживались ;)

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

[["play=1"], ["play=3", "play=4"], ["play=6", "drop=7", "play=8"]]

В скобочках карты, которыми играет игрок, но нет ходов противника между ними
Вообще нужно различать ходы: Вариант 1 (V1) - каждая карта = 1 ход; Вариант 2 (V2) - карта играем снова, карта считаем как один слитный ход, состоящий из двух отдельных ходов первого варианта (зелёные клетки вместе взятые).

Например карта номер 8 очень сильная, но она требует много ресурсов. Картами 1,3,4,6,7 мы фармим ресурсы или строим предприятия и вместо того чтобы ждать например 10 ходов (V1) пока накопим ресурсы на карту 8, ждём 2 (V2) наших хода: [1](ход 1), [3,4](ход 2), [6,7,*8*](ходим на 3-ий).

Что такое "критичные точки" (critical points)?


При проверке на победу (критичные точки) главное не забыть про вот такие ситуации: ссылка

Что такое "псевдокритичные точки"?

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

---

Прошлая тема

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

Главные пункты из прошлой статьи:

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

В отличие от простого оценщика, где я использовал top-down подход я использую сейчас bottom-up подход. Top-down, так как сначала создал оценщик карт, и к нему пытался прикрутить сами карты, т.е. он существовал как бы вне карт. Новый же алгоритм, над которым сейчас идёт работа будет создаваться через bottom-up подход - мы смотрим на карты и их свойства, смотрим как люди играют ими и создаём на основе этого различные алгоритмы - на данный момент в основном такие, которые перебирают, ищут и фильтруют комбинации. Почему Bottom-up подход? - Мы начинаем наш подъём снизу (карты) и мелкими шажками идём выше и выше создавая новые алгоритмы и объединяя их в блоки, из которых будет создан ИИ для аркомага.

Для того чтобы как-то дальше развивать алгоритмы можно сделать следующие вещи:

1. Внимательнее посмотреть на карты - как их можно классифицировать. Уже ранее были осмотренны эффекты карт и на этих наблюдениях было созданны полезные алгоритмы (уменьшение времени ожидания карты, эксплоитирумемые эффекты и т.д.). Имея достаточное количество таких базовых блоков (полезных алгоритмов) можно будет задуматься над дизайном ИИ.
2. Имеет смысл собрать статистику о предприятиях в конце игры, в зависимости от районов и в зависимости от побед (для подсчёта среднего припроста предприятий во время игры).
3. Стоит подумать о некоторых ранее представленных алгоритмах и постараться улучшить их, либо добавить новые, речь например о функции do_nothing(...) (Наивная аппроксимация поведения игроков через выкидывание карт - т.е. ничего не делать и только получать новые карты и получать ресурсы от предприятий).
4. Постараться ответить на вопросы заданные ранее (ответы на два других вопроса были сделанны в прошлой теме):
   1. Сколько ресурсов вообще стоит тратить на постройку предприятий и нужно ли нам их много? - Какое количество оптимальное?
   2. Как правильно регулировать наш income и трату ресурсов на карты и защитить от турбулентностей вызванные рандомом и действиями противника

Некоторые из этих пунктов были уже реализованны. Пункту #3 я пока ещё не уделял внимание.

---

Income. Предпрятия и ресурсы.

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

Проблемы есть: (1) Отсутствие карт на постройку какого-то конкретного предприятия, (2) Неподходящая ситуация, (3) Отсутствие ресурсов на постройку предприятия, (4) Достаточное количество ресурсов, т.е. нет надобности строить вообще (например если разница между противником и так 2-3 предприятия каког-то типа).

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

Среднеарифметическая стоимость карт:



В скобочках (Таблица 1): Количество карт. C>1 значит карты какого-то цвета со стоимостью > 1.


Median имеет больше смысла чем mean, так как отсекает экстремальные точки. Median стоимость у всех карт: 6 очков. Я думаю это довольно неплохой ориентир для постройки предприятий.



Теперь вопрос такой: Что делать если предприятия есть, но ресурсов мало? Используем технику switching - меняем как бы рельсы - один ход играем зелёными (з), потом красными (к), потом синими (с). Если играть так (з)(к)(с)-(з)(к)(с)-(з)(к)(с)-..., то у нас есть 2 хода чтобы накопить ресурсы. Проблематично когда мало ресурсов и мало предприятий и проблема с самими картами, т.к. такая игра будет не совсем эффективна, НО даст время чтобы заполучить карты для фарма ресурсов либо постройки предприятий, а это ценно.

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

В обеих случаях проблема в том, что противник может украсть ресурсы, но с этим риском придётся жить.

Против кражы ресурсов есть следующее: зачем нам нужна например мана? - Чтобы сыграть сильной картой. Ресурсов не хватает на сильную карту, поэтому копим, есть риск что противник использует карту "вор". Значит нужно провоцировать его, чтобы он тратил зелёные карты, либо держать ману на минимуме, чтобы ему не было выгодно украсть ману, и копим ровно столько, чтобы отстроить монастыри. А когда будет нормальный income играем сильными.

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

В любом случае надёжная тактика при недостатке ресурсов и предпрятий это switching и скидывание карт, игра мелочью и копить хорошие и на постройку.

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

---

Scoring

Efficiency Score

Efficiency score, значит насколько эффективна карта. Причём здесь не рассматривается как она меняет ситуацию в сторону победы той или иной стороны (как в это было сделанно в simple card scoring), а рассматривается эффективность самой карты в зависимости от ситуации.


Пример как считается оценка: "-8 маны врагу" - если у врага 8 маны, то эффект 100%, т.е. 1 (8/8), если 4, то 50%, т.е. 4/8 = 0.5, и так далее. Проблема этой оценки, что если использовать, то нужен какой-то порог (threshold) - не совсем ясно какое значение нужно использовать. Однако можно сделать следующее: Смотрим "вилку урона" у эффекта какой-то карты. Если можно максимировать (нужна функция, которое такое говорит (пример 1, пример 2)). Это не сложно. Теперь проверяем различные комбинации из карт (поиск по дереву), при этом с какой-то максимальной глубиной N и смотрим можно ли будет например через N=1...6 ходов максимировать эффект. Если такая комбинация есть, смотрим насколько она вероятна (либо используем карты на руках для рассчётов, что более точно, либо прогнозы делаем какие карты могут придти, что очень не точно).
В этом месте напрашивается какой-то механизм, который будет рассчитывать оправдывает ли эффект этой карты, чтобы держать её например лишние 3-4 хода на руках.
В свою очередь нужно считать и для противника насколько сильний урон будет ему от использования нами этой карты и не будет ли ему по большому счёту всё равно максимируем ли мы эффект или нет.
Максимизация эффектов нужна, когда у нас очень мало ресурсов и где нужно играть крайне оптимально. Trade-off здесь такой - будем ждать слишком долго - противник может украсть ресурсы (функция для рассчёта сколько ресуров или предприятия может украсть/разрушить противник), а не будем ждать, будем использовать карты не по максимуму.
Скорее всего оптимальное решение использовать эффекты не по максимуму, а играть хотя бы на 2/3 (67%) от макс. возможностей карты.

---

Архитектура арко-мозга (v0.1)

Функция change_waiting_time(card, ...) играет крайне важную роль в моём ИИ, т.к. я использую сами карты как каркас для арко-мозга. На данный момент я генерирую дерево с различными возможностями и ищу такие карточные комбинации, которые могут уменьшить или увеличить время ожидания какой-то сильной карты. По сути игра строится на сильных картах и дополняется мелкими. Вот вспомните про такие карты как "Вампир", "Дракон", "Глаз дракона", "Сердце дракона" или "Сдвиг" - они очень мощные и на них есть смысл копить, хотя и стоят они очень много ресурсов. Победить можно конечно и без них, но при всего 102-ух картах их вес очень даже существенный. Поэтому нужно следить за своими ресурсами и за ресурсами противника, а также за своей и его башней.
Их стоимость в принципе и диктует размер предприятий.

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

Слышится немного заумно, может даже нудно (but i don't care) - но подход на самом деле очень естественный - я смотрел как играют люди. Но в отличии от человека ИИ может просчитывать тысячи комбинаций в секунду, если не делать комбинаторное дерево слишком глубоким - 3-4 отдельных хода максимально. Ненужные карты не используются, чтобы уменьшить размер поиска.

Однако ИИ для аркомага использующий только такой поисковик будет слабым. Если не использовать эвристики, а искать какое-то решение через брутфорс, то комбинаторное дерево будет гигантским (мы можем переделать рандом в громадное дерево со всеми возможностями). Т.к. нет такой компьютерной мощности нигде, то нужен какой-то способ, который будет находить не оптимальное решение, а неплохое, или неплохое в большинстве случаев (например винрейт против человека будет 50-60%). Отсюда сразу вопрос - как такое сделать? Для этого есть эвристики. Я решил сделать эвристику похожую на человеческую игру, но улучшить её в каких-то определённых местах. Поэтому я разбил "проблему аркомага" на мелкие кусочки и стараюсь сделать так, чтобы каждый кусочек работал хорошо отдельно и вместе со всеми другими кусочками тоже хорошо. Теперь вернёмся к тому почему если использовать только такой поисковик, то ИИ будет слабым - я смогу оптимировать время ожидания любой карты (кстати работает и наооборот для противника: можно увеличить время ожидания карты противника просто например украв у него ресурсы или уничтожив его предприятия или спровоцировав на атаку используя мелкие карты), но не буду знать какой картой лучше играть, потом не учитываются прошлые ходы и нет планировки будущих ходов - т.е. нет сравнения с другими комбинациями.



Изображение 6: Схематическое изображение ИИ для аркомага. Для увеличения размера клинкните по картинке.

Архитектура арко-мозга (версия 0.1) состоит из четырёх блоков:

1. cards: карты (какие карты у противника, cooldown)
2. critical points: критичные точки (поиск таких)
3. strategy: стратегия (планирование на много ходов вперёд. правильней скорее всего тактика, т.к. слишком надолго мы не можем планировать, т.к. карты выдаются рандомно)
4. data analysis: анализ данных (прошлые игровые состояния, анализ ходов противника)

Первые два пункта по большому счёту готовы уже и сейчас. Не хватает самого главного: Анализа данных и Механизма обработки комбинаций (engine), по идее это функция, которая консумирует комбинацию из прошлого хода, смотрит на новые предложенные комбинации и решает оставлять старую или как-то изменить, либо выбрать новую. Всякие помощники предлагают этой функции данные (с контекстом, "Если у противника есть карта Х, то используй эту комбианцию"), а она решает дальше что с ними делать. На 100% проработанной идеи пока нет, но можно представить, себе, что такая функциия будет как-то оценивать комбинации и выдавать лучшую. После этого уже всё просто - нужно будет лишь играть картами до следующего хода.

Я думаю можно сделать ИИ без дополнительного анализа данных и без планировщика стратегий. Но мне лично интересно попробовать добавить их тоже.

Про первый блок (cards) нужно дополнить, что есть 3 способа получить данные о картах противника: (1) Всевозможные карты, (2) Те с самой высокой вероятностью (либо что они у него есть, либо что он ими будет играть), (3) Только те, на которые у него хватает ресурсов.
В принципе первый способ особой важности не представляет.

Примечание: ИИ любит рисковать.

---

Карты

• на русском
• на английском