Беседа с разработчиками: автоконструктор колод

Всем привет! Меня зовут Тянь, я старший специалист по обработке данных из команды Hearthstone. Сегодня я расскажу вам о новом автоконструкторе колод — и, надеюсь, отвечу на некоторые вопросы, которые вы часто задавали на форумах с тех пор, как мы анонсировали эту функцию.

Сейчас я в двух словах опишу принцип действия нашего алгоритма, а потом мы перейдем к самому главному. Во имя науки!

Что такое автоконструктор колод?
 

Мы знаем, что составлять новые колоды для Hearthstone — увлекательное занятие для опытных игроков, которое приносит хорошие результаты. Но, может, вы новичок или давно не играли в Hearthstone? Или у вас мало времени? Или вы просто хотите получить совет, как собрать из ваших карт колоду, которой можно гордиться? Вам поможет новый автоконструктор: мы сделаем за вас основную часть работы и поможем скорее начать игру с популярной и эффективной колодой всего лишь после пары щелчков мышкой!

Чтобы воспользоваться данной функцией, начните составлять колоду для стандартного формата и добавьте в нее любое количество карт. Затем нажмите «Завершить колоду» или «Готово», и мы дополним вашу колоду, изучив уже выбранные вами карты и использовав только доступные карты из вашей коллекции. Так, если вы выберете карты «Ундаста» и «Ложная смерть», а все остальное оставите на наше усмотрение, система примет во внимание несколько факторов и подготовит лучший (с ее точки зрения) вариант — например, популярную колоду охотника на предсмертных хрипах с Катреной Зимний Шорох.

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

Как все устроено
 

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

Первый этап создания колоды: подстройка под метаигру

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

На первом этапе создания колоды (этап метаигры) мы пытаемся создать лучшую колоду, учитывая уже выбранные вами карты, доступные карты в вашей коллекции и популярные колоды метаигры. Для анализа текущей метаигры мы используем вычислительный алгоритм, распределяющий популярные колоды по категориям и подгруппам. Каждая подгруппа соответствует какому-либо типу колод в метаигре: «Охотник на секретах», «Жрец на драконах», «Нечетный паладин» и т. п. Конкретные списки колод в подгруппе могут немного различаться, но в общем и целом это один и тот же архетип. В машинном обучении это называется «кластерный анализ». Наш алгоритм кластерного анализа обрабатывает миллионы колод, каждая колода считается одной единицей данных, и каждая единица данных — это многомерный вектор. Используя данные кластерного анализа и разные математические решения, алгоритм динамически добавляет карты в список, пока колода не будет готова или не сработает этап «резервных вариантов».

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

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

Второй этап создания колоды: резервные варианты

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

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

• Влияние на игру: как сильно эта карта влияет на процент побед выбранной колоды
  • «Элементаль воды» повышает вероятность победы мага сильнее, чем «Жуткий корсар».
• Стоимость: к какому блоку по стоимости маны относится эта карта
  • Если мы ищем карту со стоимостью 1-2 маны, «Сквайр Авангарда» будет хорошим выбором, но вместо карты со стоимостью 5 маны он никак не годится.
• Нельзя перегружать блоки
  • Если в одном из блоков по мане уже есть десять карт, мы стараемся больше не добавлять в колоду карты с такой стоимостью. Исключение может быть сделано в том случае, если альтернативы заметно хуже.

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

Дополнительные факторы: правила, период восстановления, ограничения

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

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

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

Непременно поделитесь с другими игроками интересными колодами, которые вы составили с помощью нового алгоритма. До встречи в таверне!