Аркомаг. Начало игры. Несколько идей.

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

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


Но, это конечно частный случай и является чисто идеализированной ситуацией. Важно в том, что нужно фармить ресурсы в начале.

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

- Насчёт различия: Различие и вправду есть - различие в кулдауне и в информации о том как играл противник (его стиль игры). Из-за кулдауна мы на 100% знаем, что карта K там будет сидеть ещё X ходов.

Интересна вообще самая цепочка карт, которыми сыграли. Интересно к какому состоянию подходят лучше всего какие карты. И ещё - для перехода из одного состояния в другое нужно N ходов. Например какие серия из карт нужна, чтобы сделать цикл и вернутся обратно к начальному состоянию? Зачем это надо? - В начальном состоянии мы как бы начинаем игру с начала, т.е. если не задалось в начале, то может повезёт сейчас. Поэтому нужна серия карт (наши с противником по-очереди), с максимальной длинной D (distance), которая приведёт нас к началу, если противник доминирует (больше ресуров и предприятий в течении 10-20 ходов).

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

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

Метод такого типа можно применить не только к аркомагу.

Была идея отнестись к цепочки из карт как генетическому коду. Но с этим очень сложно получатся - у нас не 4 буквы, а 102, т.е. как-то по классам разбивать карты надо - сложновато если честно (однако можно анализировать не сами какие-то отдельные цепочки, а сравнивать их друг с другом (multiple sequence alignment)). Если hidden markov model, то проблема, что у нас не цепочка, а лесенка - карты и игровые состояния - цепочки могут быть схожими, но состояния на столе могли быть разными. Тоже не совсем ясно как-то. Была ещё идея отнестись к игровому состоянию как к протеину, а к карте как к ligand (key-lock model proteins), но тоже как-то не совсем ясно как можно перенять какие-то формулы из биохимической модели для комбинаторной проблемы.
Может у кого есть конкретная идея (формула или метод как переделать одну проблему в другую, но известную) в этом направлении, но у меня нет.

А на основе динамики игры можно делать интересные прогнозы: Нужно анализировать много текущих игр, разбивать по классам, искать схожые мотивы в цепочках. Тут как мне кажется есть ещё потенциал. Например даже чтобы узнать когда какой картой играют - например когда используют карту вор (например если противника 8 маны, и 2 руды). Можно придумать что-то умное и засунуть цепочки например в suffix tree, т.е. такие цепочки, которые приводят к доминированию (нужна какая-то простейшая оценка) или к победе.
Тут и рейтинг карт можно даже сделать. Проблема, что нужно очень много данных.

Ну а машинное обучение это отдельная история, но не какой-то святой грааль. Результат может быть и так себе.

Если у кого есть интересные идеи, которые работают хотя бы для большинства случаев - пишите в комментариях.

Да, писать ИИ для аркомага, который сможет обыграть опытного игрока не так уж и просто.