Предсказание колоды противника Hearthstone с помощью машинного обучения

Денис Парфенов    | 2021.08.09

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

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

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

После первоначального выпуска этой публикации в 2014 году у меня было несколько разговоров с разработчиками Hearthstone, которые назвали этот алгоритм « переломным для игры ». По их просьбе я согласился не выпускать инструмент или данные, чтобы не испортить игру (подробнее здесь).

Более «научная» трактовка основных результатов, описанных в этом сообщении в блоге, опубликована в этой исследовательской статье.

Эта запись в блоге является частью моей серии статей о применении машинного обучения в Hearthstone. Вот список сообщений:

  1. Какустанавливать цены на карты Hearthstone: представляет модель ценообразования карт, используемую в последующих публикациях для поиска недооцененных карт.
  2. Как автоматически находить недооцененные карты: основывается на модели ценообразования для автоматического поиска недооцененных карт.
  3. Цены на специальные карточки: демонстрирует, как оценить стоимость карточек со сложными эффектами, таких как VanCleef .
  4. Предсказание колоды противника в Hearthstone: демонстрирует, как использовать машинное обучение, чтобы предсказать, что будет играть противник ( это сообщение в блоге ).
  5. Прогнозирование результатов игры Hearthstone с помощью машинного обучения: обсуждает, как применять машинное обучение для прогнозирования результатов игры.

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

Последнее редактированиеЭто сообщение было в последний раз в октябре 2016 года . Введение было полностью переписано, чтобы отразить текущее состояние исследований. Чтобы сделать пост более понятным, контент был частично написан и добавлены иллюстрации.

Почему Hearthstone предсказуем?

Одним из преимуществ Hearthstone является разнообразие стилей игры: в распоряжении игроков есть более тысячи карт для создания колоды. Теоретически такое разнообразие позволяет создавать практически бесконечное количество колод.

Однако на практике играемые колоды имеют много предсказуемой структуры по следующим причинам:

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

Синергия карт: По замыслу, многие карты лучше всего работают в сочетании с другими очень специфическими картами.

Плохие карты: многие карты просто плохи или недостаточно эффективны, что означает, что они почти никогда не используются в соревновательных играх. Однако есть немало причин включить их в игру.

Netdecking: И последнее, но не менее важное: огромная часть игроков полагается на netdecking, который использует колоду, сделанную кем-то другим (обычно профессиональным игроком) и найденную в сети.

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

Как использовать предсказуемость Hearthstone

Чтобы предсказать, какие колоды у оппонентов Hearthstone, мы собираемся написать алгоритм, предназначенный для изучения возможных структур колод на основе 50 000 повторов игры. Изучение базовой структуры колод будет использовано для прогнозирования того, какие карты, вероятно, будут сыграны следующими, на основе уже разыгранных карт.

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

Однако на практике ко второй очереди алгоритм уже делает хорошие прогнозы. Например, он может предсказать две карты, которые есть в колоде оппонента, но которые еще не разыграны, с вероятностью успеха более 50% (66,3% для первой карты и 44,1% для второй карты).

Если вы попросите алгоритм предсказать 10 карт, которые есть в колоде оппонента, он получит правильные 23% из них. Это довольно впечатляюще, учитывая, что эти прогнозы основаны на просмотре только одной или двух сыгранных карт.

По мере прохождения игры алгоритм будет лучше понимать, во что играет противник, и точность прогнозов повысится. Пик точности наступает между 3 и 5 ходами, когда алгоритм может предсказать наиболее вероятную карту, которую противник имеет в руке, но еще не разыграл, с точностью выше 95%.

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

Цель алгоритма

На очень высоком уровне разрабатываемый нами алгоритм должен делать две вещи:

Извлечение: учитывая класс оппонента и список карт, которые он сыграл до сих пор, он должен вернуть список карт, которые, вероятно, есть в колоде у оппонента, но которые еще не разыграны.

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

На жаргоне информатики мы называем такой алгоритм алгоритмом ранжирования с машинным обучением.

Обзор алгоритма

Как видно на диаграмме, для построения нашего алгоритма прогнозирования нам необходимо:

  1. Смоделируйте отношения между картами,чтобы алгоритм имел структуру, необходимую для изучения «формы» колод. Обратите внимание, что мы создаем по одной модели для каждого класса, потому что у каждого класса есть несколько уникальных карт.
  2. Создайте функцию подсчета очков,которая по набору карт возвращает наиболее вероятные карты в колоде в зависимости от того, как карты связаны друг с другом.
  3. Обучите наш алгоритмна наборе повторов игры, чтобы он мог изучать формы колод и отношения между картами.
  4. Оцените наш алгоритм,чтобы увидеть, работает ли он, настройте его и сгенерируйте таблицу вероятностей, которая расскажет нам, насколько точен алгоритм при прогнозировании карт для данного хода.

Как мы можем смоделировать отношения между карточками?

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

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

Я избавлю вас от своих неудачных попыток с различными моделями и остановлюсь на той, которую я в конечном итоге использовал: вариант представления n-грамм. Эта модель, вероятно, является самым простым представлением, которое вы можете использовать, но из-за своей простоты она также очень надежна.

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

Оригинальная статья на n-граммах называется «Предсказание и энтропия печатного английского языка». Это одна из лучших статей, которые я когда-либо читал - она ​​блестящая, понятная и вдохновляющая. Если у вас есть интерес к информатике, я настоятельно рекомендую вам ее прочитать. Это того стоит.

Забавно, как видно на фотографии, Шеннон также глубоко интересовался использованием алгоритмов для игры в настольные игры. Это привело к тому, что в 1950 году он написал революционную статью об искусственном интеллекте о том, как заставить компьютеры играть в шахматы.

Как работают н-граммы

Ладно, хватит истории! Вот как работают н-граммы. N-грамма - это непрерывная последовательность n элементов из заданной последовательности элементов. В нашем случае n-граммы представляют собой последовательности карточек. Обычно мы работаем с последовательностями из двух элементов (« биграммы ») или трех элементов (« триграммы »), хотя некоторые алгоритмы используют 5-граммовые или даже больше, особенно для обработки естественного языка.

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

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

  1. Он моделирует случайный розыгрыш карт.
  2. Это объясняет тот факт, что порядок, в котором карты разыгрываются в одном и том же ходу, чаще всего не влияет, что заставляет игроков использовать их в произвольном порядке.

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

Затем все эти наборы биграмм и триграмм суммируются, так что в конце фазы обучения алгоритм знает, как часто карты в каждой паре или тройке разыгрываются вместе.

Например, как показано на рисунке выше, алгоритм может узнать, что комбинация Смертельный яд / Веер ножей является очень популярной комбинацией Разбойника, поскольку они вместе появляются в 500 играх.

Как мы можем предсказать предстоящие карты?

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

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

Алгоритм будет смотреть на все пары карт, содержащие Смертельный яд, и все пары, содержащие Шив (середина рисунка), и извлекать из него счетчик того, как часто каждая карта просматривалась вместе с другой (шаг 1). . В нашем примере Blade Flurry был показан 350 раз с Deadly Poison и 400 раз с Shiv . Фанат ножей был показан 300 раз со Смертельным ядом, а Амани Берсеркер - 400 раз с Шивом .

Затем алгоритм суммирует все эти подсчеты и сортирует карты по этому количеству (шаг 2). В нашем примере Blade Flurry оказывается самой просматриваемой / вероятной картой с количеством 750, Fan of Knives идет второй с количеством 550, а Amani Berserker идет последней с количеством 400.

Затем алгоритм упорядочивает карты по счету (шаг 3). Затем он просто возвращает карты с наибольшим количеством очков и исключает карты со слишком низким счетом (здесь, Амани Берсеркер).

Технически мы нормализуем (softmax) по общему количеству, чтобы отобразить процент, но это не меняет основного принципа, поэтому я удалил этот шаг из диаграммы для ясности.

Данные, данные, данные

Для работы нашему алгоритму требуется много игровых повторов. Экспериментируя с различными размерами наборов данных, я начал получать стабильные результаты при использовании более 10 000 игровых повторов. Более того, использование более 50 000 игр не улучшает результаты, поэтому я остановился на наборе данных из 50 000 повторов, сыгранных в период с мая по июль 2014 года.

Самым болезненным моментом на этом этапе было получение повторов и их обработка. Я преобразовал их в структуру игры, которая сообщала мне, какие карты были сыграны на каком ходу и каким игроком.

Одно предостережение по поводу набора данных: поскольку Blizzard не предлагает функцию повтора, повторы собирались напрямую от разных игроков, и, следовательно, мы не знаем, какие карты взял противник. Мы знаем только, какие карты сыграл противник. Это не проблема, поскольку отражает реальные игровые условия, в которых мы хотим, чтобы алгоритм работал, но об этом стоит упомянуть.

Оценка алгоритма

Теперь, когда у нас есть алгоритм и данные, остается только использовать алгоритм и посмотреть, насколько хорошо он работает!

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

Как бы то ни было, когда все заработало, я оценил точность алгоритма, обучив его на 45 000 игр, оставив 5 000 для тестирования.

Точность прогноза

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

Чтобы ответить на этот вопрос, я посмотрел на 10 лучших предсказанных карт на каждом из ходов со 2 по 15, возвращенных алгоритмом. Затем я посмотрел, как часто игрались эти предсказанные карты.

Как видно на диаграмме выше, алгоритм работает очень хорошо! Например, карта, которая, по мнению алгоритма, с наибольшей вероятностью окажется в колоде оппонента на 5-м ходу, в конечном итоге разыгрывается оппонентом в 96,2% случаев. Вторая наиболее вероятная карта была сыграна в 91,69% случаев и т. Д.

Точность ранжирования

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

Эволюция на поворотах

Интересно посмотреть на компромисс между получением большего количества информации по мере того, как разыгрывается больше карт, и меньшим количеством карт для прогнозирования по мере уменьшения количества карт в колоде оппонента.

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

С другой стороны, увеличение количества карточек продолжает увеличивать среднюю точность алгоритма до 9 хода, поскольку прогнозы с рейтингом от 2 до 10 становятся более точными.

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

В следующем посте этой серии рассматривается проблема прогнозирования результатов игры с помощью машинного обучения.

Если вы хотите получать уведомления о появлении следующей публикации в сети, подпишитесь на меня в Twitter, Google+ или Facebook.

Вы также можете получать полные сообщения прямо в свой почтовый ящик, подписавшись на список рассылки или RSS-канал.

Денис Парфенов Автор статей

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