Провинциальный: адаптируемый к королевству ИИ для Dominion

Этот ИИ легко конкурирует с опытными игроками Доминиона. Если вас не интересует теория написания ИИ для Dominion, перейдите к разделу «Стратегии покупки» или поиграйте с приложением, указанным выше.

СОДЕРЖАНИЕ

Dominion - карточная игра по сборке колод, разработанная Дональдом X. Ваккарино и изданная Rio Grande Games. Это очень популярная карточная игра со сложным взаимодействием карт и значительным количеством подписчиков в сети на таких сайтах, как Goko и Isotropic, хотя в настоящее время у вас будут проблемы с поиском AI-противника, который может соревноваться с опытными игроками. Одной из главных достопримечательностей Dominion является то, что игра начинается с случайного выбора десяти карт, чтобы сформировать начальный набор карт припасов (называемых в игре «картами королевства» или просто «королевством»). Это делает игру очень сложной для хорошей игры, потому что в каждой игре вам придется принимать решения о том, как играть в королевство, несмотря на то, что вы никогда раньше не играли с этим точным набором карт. Опытные игроки будут принимать решения на основе предыдущих игр с похожими,но все же совсем другие, королевства. Хотя это позволяет передавать знания о комбинациях и соотношениях карт, которые хорошо работают вместе, все же есть аспекты нового королевства, которые очень сложно понять без обширной игры с этими картами. Новое королевство может иметь новые комбинации карт, которые очень хорошо работают вместе, или у него могут быть карты, которые эффективно разрушают в противном случае мощные стратегии. Опытные игроки должны делать сложные суждения относительно того, какие стратегии доминируют в новом королевстве и насколько эффективны эти стратегии друг против друга. Что еще более усложняет задачу, Dominion - это игра со значительным количеством случайного поведения. Поскольку очень эффективная стратегия может проиграть посредственной,игрокам необходимо усреднить свой опыт в огромном количестве различных игр, чтобы научиться принимать правильные решения.

1. Создание искусственного интеллекта для доминиона

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

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

Провинциальный - это ИИ Dominion, о котором я писал, он пытается найти баланс между академической ценностью, эффективной игрой и общим удобством использования. При его разработке моей основной целью было получение результатов, которые будут полезны опытным игрокам Dominion. Для этого ИИ должен быть параметризован таким образом, чтобы люди могли легко его понять - такие методы, как нейронные сети и вспомогательные векторные машины, хотя они могут быть очень эффективными в задачах машинного обучения, по сути являются черными ящиками, внутреннее поведение которых ограничено. сложно понять даже специалистам по машинному обучению. Чтобы быть полезным для опытных игроков, ИИ также должен уметь соревноваться на высоком уровне игры и давать результаты в разумные сроки.Ядро Provincial - это очень агрессивная структура стратегии, основанная на конкурентной коэволюции, которая захватывает данное королевство и запускает миллионы игр против самого себя, создавая развивающийся список доминирующих стратегий. Затем проводится турнир между всеми ведущими стратегиями, а результаты визуализируются для пользователя (несколько примеров см. Ниже). Вот краткое изложение некоторых ключевых особенностей Provincial:

  • Специальное обучение для королевства -ИИ в провинциях изучает данное королевство и разрабатывает набор стратегий для конкретных королевств. Это имитирует то, как опытные люди играют в игру, и приводит к очень эффективному игроку, но также является недостатком, поскольку означает, что ИИ необходимо переучивать для каждого нового королевства. Если ИИ играет против набора королевства, на котором он не был обучен, он будет принимать практически случайные игровые решения, что приведет к очень плохой производительности.
  • Коэволюция поколений -чтобы определить, какие стратегии являются лучшими, ИИ начинает со случайного пула подходящих стратегий и гораздо меньшего набора доминирующих стратегий. Затем все стратегии в пуле кандидатов проверяются на соответствие ведущим стратегиям, и те, которые работают лучше всего, становятся лидерами в следующем поколении. Новый пул кандидатов формируется как мутации новых лидеров, и цикл повторяется.
  • Удобочитаемость -ИИ использует довольно простую параметризацию в пространстве стратегий Доминиона, более подробно объясненную ниже. Хотя эта более ограниченная параметризация не использует некоторые возможности, предлагаемые более сложными методами машинного обучения, возможность анализа людьми делает ИИ значительно более интересным. В разделе «Дальнейшая работа» я расскажу о том, какие преимущества можно получить, используя более сложную, но непрозрачную модель.
  • Производительность -ИИ очень быстро запускает игры. На восьмиъядерной машине типичная скорость составляет 40 000 игр в секунду. Частично это связано с выбором языка для бэкэнда (C ++), частично из-за многопоточности и частично из-за простоты Dominion. Типичная игра в Доминион длится где-то от 20 до 30 ходов, и большинство ходов включает в себя обработку только нескольких простых действий, таких как ввод сокровищ в игру или решение, что купить. Тем не менее, обучение в новом королевстве по-прежнему занимает несколько минут, поскольку для каждого поколения необходимо запускать сотни тысяч игр.

2. Параметризация стратегии доминиона

В самом общем виде формулировка проблемы ИИ Доминиона с определенным королевством для игры выглядит примерно так:

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

Это утверждение упускает из виду многие важные тонкости, такие как стратегическое доминирование и равновесие по Нэшу. Однако, если оставить в стороне эти интересные темы, остается реальный вопрос: как мы можем количественно определить стратегию в Dominion?

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

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

3. Покупайте стратегии

Провинциальный использует простую модель, чтобы представить, какие карты должен покупать данный ИИ. Основным компонентом стратегии покупки является упорядоченный список пар карта-целое число, который мы будем называть меню покупки.. Карта представляет собой карту, которую нужно купить, а целое число - это количество карт, которые нужно купить. По причинам, которые станут очевидными, одна и та же карточка может появляться несколько раз в качестве разных записей в меню. Правило покупки простое: покупайте самую левую карту, которую можете себе позволить. После того, как карта куплена, соответствующий пункт меню уменьшается. Естественно, если вы не можете позволить себе карту или в запасе ее не осталось, вы переходите к следующей карте или ничего не покупаете, если у вас заканчиваются пункты меню. Это меню чаще всего используется для фазы покупки, но также вызывается в ответ на любое событие, которое заставляет вас получить карту, например, Мастерская и Диверсант. Второй компонент стратегии покупки определяет, когда покупать поместья, герцогства и провинции в зависимости от того, насколько близка игра к концу. Пока мы используем для этого простую модель:ИИ параметризован двумя целыми числами (3 для королевств с картами Процветания), которые определяют, сколько провинций (или колоний) должно быть оставлено, прежде чем ИИ переопределит свое меню покупки и вместо этого купит карты победы. Чтобы сделать визуализации как можно короче, ИИ всегда жадно покупает самую дорогую карту победы, хотя это требование легко убрать (см. Раздел «Работа на будущее»).

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

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

  • Карты королевства -показывает десять карт припасов, начальное состояние руки (3-4 против 2-5 медных сплит) и наличие специфических для расширения модификаций запаса, таких как платина и колонии из Процветания или Убежища из Темных веков.
  • Доминирующие стратегии -Визуальное описание меню покупки для каждой из пяти стратегий и условий, при которых каждая стратегия будет покупать поместья, герцогства и провинции. Они следуют алгоритму меню покупки, описанному выше. Например, если в стратегии A 3 монеты, она сначала купит серебро. Во второй раз, когда у него будет 3 монеты, он купит Часовню, а затем перейдет к покупке Городков-трущоб. С другой стороны, стратегия B будет покупать Часовню, когда в ней впервые будет 3 монеты. Стратегия также указывает, когда стратегия переключается на покупку победных карт. Например, стратегия A будет покупать поместья, когда остается только одна колония, и будет покупать герцогства и провинции, когда останется две или меньше колоний. Число, показанное рядом с каждой стратегией, представляет собой ожидаемый коэффициент выигрыша этой стратегии при игре против других четырех ведущих стратегий.
  • Турнир -В этой таблице показано ожидаемое соотношение выигрышей, когда каждая из пяти стратегий играет против друг друга, в среднем по 10 000 игр. Показанное значение представляет собой процент игр, которые игрок строки может ожидать выиграть по сравнению с игроком столбца. Конкретно, если игрок строки выигрывает X% игр, а игрок столбца выигрывает Y% игр, соответствующая запись будет (X - Y)%. Значение + 100% означает, что игрок строки всегда выигрывает, значение -100% означает, что игрок столбца всегда выигрывает, а значение + 50% соответствует коэффициенту выигрыша от 75% до 25%. Значения, показанные серым цветом, не являются статистически значимыми и указывают на то, что два игрока практически равны. Статистические аномалии могут возникать даже при запуске 10 000 игр; например, стратегия E, играющая в стратегию E, должна иметь ожидаемый коэффициент выигрыша 0%, но отображается как -2,3%.

Важно отметить, что эти визуализации представляют только ведущие стратегии на определенном этапе эволюционного процесса. Стратегии ранних поколений могут быть очень плохого качества, поскольку ИИ все еще работает над тем, какие комбинации карт работают вместе. Даже стратегии более поздних поколений могут все еще претерпевать важные эволюционные изменения, потому что некоторые части стратегического пространства могут быть тонкими или трудными для исследования. Например, покупка Заговорщика может быть очень пагубной для стратегии до тех пор, пока не будет добавлено достаточное количество других карт «+ действие» и не будет сочтено возможным.

Для многих королевств у ИИ не будет проблем с захватом «классических» стратегий в разумном количестве поколений. Например, каноническая игра «королевский двор + мост»:

4. Простые и сложные царства

В некоторых королевствах доминирующие стратегии будут развиваться очень четко: лидеры поколения N, в среднем по тысячам игр, будут либо побеждать, либо связывать лидеров от поколения 1 к N; мы называем такие царства простыми царствами. С другой стороны, в сложных королевствахстратегии могут быть значительно более нестабильными, так как некоторые стратегии переходят и теряют популярность в ответ на выбор карт, сделанный конкурирующими стратегиями. Такое поведение характерно для королевств с сильными картами атаки и защиты или карт со сложными целями победы (Сады, Герцог) и называется стратегическим метагеймингом. В простых царствах, как правило, одна стратегия доминирует, всегда сопоставляя или превосходя все другие стратегии, давая понять, какую стратегию выбрать. В более интересном случае сложных царств,где ни одна стратегия не доминирует, оптимальный игрок должен случайным образом выбрать одну из стратегий-кандидатов для достижения стратегии равновесия.

Мы используем визуализацию прогресса,чтобы увидеть эволюцию метагейма. Эта визуализация показывает, как ведущая стратегия поколения N конкурирует с ведущей стратегией поколений с 1 по N. Ниже представлена ​​визуализация прогресса для простого королевства:

«Стратегия лидерства» показывает доминирующую стратегию у нынешнего поколения. «Конкурирующие стратегии» показывают ведущую стратегию из предыдущих N поколений и относительный коэффициент выигрыша, усредненный по 10 000 игр по сравнению с ведущей стратегией (для экономии места показано только каждое 4-е поколение). Справа мы отображаем соотношение выигрышей в зависимости от поколения. В этом простом царстве ведущая стратегия, по крайней мере, так же хороша, как и все предыдущие поколения, что указывает на постепенное улучшение эволюционного поведения. Если ИИ не изменит какую-то значительно лучшую стратегию, будущие поколения будут примерно сходиться с показанной стратегией, хотя небольшие колебания все равно будут происходить из-за статистической дисперсии, присущей сравнению двух стратегий.

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

Здесь поведение гораздо более изменчиво, чем медленное и неуклонное улучшение, наблюдаемое в простом королевстве. Стратегия лидерства в поколении 40 существенно лучше, чем у некоторых предыдущих лидеров, но значительно хуже, чем у других. Эти королевства часто более интересны для игры, потому что лучшая стратегия для выбора менее ясна. Даже если ИИ разрешено тренироваться на протяжении многих поколений, такое периодическое поведение продолжается. Вот тот же график, сравнивающий лидера поколения 132 со всеми предыдущими поколениями:

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

5. Оценка новых карточек

Одно интересное использование Provincial - это попытаться количественно оценить дизайнерские решения. Пир слишком слаб? Причал слишком мощный? Канцлер хороший? Если Wharf будет стоить 6, все равно будет хорошо? Поскольку Provincial очень быстро запускает игры и разрабатывает конкурентные стратегии, мы можем попытаться ответить на эти вопросы. Во-первых, давайте попробуем количественно определить, что представляет собой хорошо продуманная карта.

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

Провинциальный можно использовать для проведения экспериментов, которые непосредственно оценивают эту функцию. Мы рассмотрим два конкретных примера, Wharf и Plunder:

Начнем с пристани. Мы выбираем 30 случайных королевств, все из которых могут использовать Wharf. Затем мы запускаем Provincial для этих королевств, чтобы оценить, что составляет хорошую стратегию для каждого королевства, и вычислить процент королевств, в которых Wharf входил в одну из трех лучших стратегий. В этом эксперименте Уорф был выбран в 28 из 30 королевств. Это говорит о том, что, хотя Wharf, безусловно, силен, очень редко наличие других мощных карт может заставить опытного игрока принять решение относительно того, покупать ли Wharf. Затем мы можем переоценить Wharf до 6 и повторить тот же эксперимент. В этом случае 18 королевств содержат стратегию, при которой лучший игрок покупает причал, а 12 - нет. Несмотря на то, что Wharf заметно слабее, игрок все же может подумать о нем. К счастью,Доминион - симметричная игра, поэтому справедливость сохраняется даже при наличии очень сильных или очень слабых карт.

Мы также можем использовать Provincial для оценки параметров карт, которые еще не были напечатаны, и можем посмотреть на изменение любого параметра, а не только стоимости карты. Рассмотрим (гипотетическую) карту грабежа, показанную выше. Мы проводим тот же эксперимент, что и с Верфью, и обнаруживаем, что, как показано выше, Грабеж выбирается только в 3 из 30 королевств. Поигравшись с картой, я решил, что основная причина этой слабости заключается в том, что она дает 0 денег, поэтому она пагубна при попытке купить карты Победы и требует очень удачных рук, чтобы помочь купить сокровища, поскольку она должна сопровождаться другими. ценные сокровища. Чтобы усилить карту, я изменил ее, чтобы она более точно имитировала Камень и давала 1 монету при розыгрыше вместо 0 монет. Пройдя эксперимент заново, Грабитель был выбран в 10 из 30 королевств.Хотя он все еще не так силен, как Wharf, он является значительно более жизнеспособной картой и конкурирует со многими другими картами с 5 ценами. Было обнаружено, что грабеж особенно силен при наличии других хороших сокровищ, таких как Венчур:

6. Детали алгоритма

Здесь мы рассмотрим несколько основных компонентов алгоритма обучения искусственного интеллекта Provincial.

Процесс эволюции

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

Есть три очень важных параметра: количество стратегий в общем пуле, количество лидеров и количество поколений, для которых выполняется алгоритм. После небольшого экспериментирования я обнаружил, что от 5 до 10 лидеров работают хорошо, и ради эффективности я обычно выбираю 5 лидеров. Для общего пула я обычно использую 100 стратегий, что обеспечивает хорошее разнообразие для каждого поколения. Увеличение размера пула увеличивает время, необходимое для запуска поколения, но может также уменьшить количество поколений, которые необходимо запустить. Как показано выше, необходимое количество поколений во многом зависит от королевства. Некоторые сходятся всего за 20 поколений, в то время как некоторые все еще хорошо развиваются через 100 или более поколений. По умолчанию количество поколений, используемых Provincial, равно 32, что достаточно для большинства королевств.но я видел множество ситуаций, когда после этого периода были сделаны значительные стратегические улучшения.

Шаблоны меню

Если стратегиям разрешено видоизменяться без какой-либо структуры, алгоритм все равно будет работать хорошо, но много вычислений будет потрачено впустую, потому что подавляющее большинство мутаций явно не являются разумными стратегиями. Например, почти нет стратегий, которые отдавали бы предпочтение покупке серебра за платину или кузницы перед знати, или покупке проклятия или руин ни при каких обстоятельствах. Точно так же некоторые карты, такие как Platinum и Gold, универсальны и почти всегда должны рассматриваться как резервные покупки. Чтобы не тратить много времени на стратегии, которые, скорее всего, не будут жизнеспособными, провинция проводит выборку стратегий, используя предварительное распределение по пространству возможных меню покупок. В этом шаблоне менюв качестве основы используется стратегия больших денег. Для игр Prosperity это выглядит так:

Эта стратегия будет покупать Серебро, Золото и Платину до тех пор, пока стопки не закончатся (обозначено x99). Другими картами могут быть любые карты снабжения из стопки, хотя для каждого слота есть ограничение по диапазону допустимых цен. Например, последний слот меню не может стоить больше 2, потому что он всегда будет игнорироваться в пользу серебра.

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

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

Здесь ИИ, обученный по этой более гибкой модели, решает купить одну верфь и два золота перед своей первой провинцией:

Возникает естественный вопрос: влияет ли это предвзятое отношение к стратегиям больших денег на конечные результаты? Я провел несколько экспериментов, в которых стратегии, использующие полностью неограниченные меню, сравнивались со стратегиями, основанными на больших деньгах. Хотя неограниченные стратегии имеют тенденцию выглядеть немного странно из-за порядка карт, в конечном итоге стратегии имеют почти идентичную производительность по сравнению со стратегиями, начавшимися с больших денег. Вот таблица лидеров, обученная с использованием неограниченного меню:

Мутации

В каждом поколении новый пул стратегий формируется как мутации лидеров предыдущего поколения. Рассматриваются следующие типы мутаций меню покупки:

  • Заменить карту снабжения -заменить карту снабжения в меню другой картой, случайно выбранной из запаса.
  • Изменить количество покупок -изменить количество купленных карт на случайную сумму.
  • Поменять местами карточкиприпасов -поменяйте местами два пункта меню.
  • Измените пороговые значения для покупки карты победы -измените пороговые значения, управляющие покупкой имений, герцогств и провинций.
  • Изменениеигрового параметра для конкретной карты -изменение «игрового параметра», привязанного к определенной карте королевства. Например, ИИ может сместить параметр, управляющий порогом, ниже которого ИИ будет преобразовывать золото в провинцию (см. Раздел «Повестка дня»).

Чтобы улучшить скорость сходимости алгоритма, каждая мутация происходит с фиксированной вероятностью, пропорциональной тому, как часто мутации такого типа оказываются полезными. Если выполняется только одна мутация, также возможно, что важные части пространства стратегий будут недоступны, потому что промежуточные стратегии могут иметь очень низкий балл. Чтобы преодолеть эту проблему, выполняется гауссовское число мутаций, поэтому всегда есть шанс, что области с низкими показателями в области стратегии могут быть пропущены. Тем не менее, все еще существует вероятность того, что интересные стратегии будут пропущены, если алгоритм не будет использоваться для очень большого количества поколений. Чтобы увидеть, насколько распространена эта проблема, Provincial поддерживает параллельное выполнение нескольких независимых симуляций, что называется количеством используемых «тестовых камер».Для простых королевств обычно достаточно одной камеры. Однако для сложных королевств очень интересное поведение может быть достигнуто с помощью нескольких испытательных камер. Провинциальный будет автоматически запускать всех лидеров каждой камеры друг против друга и визуализировать итоговую таблицу лидеров.

Повестка дня игры

Подавляющее большинство навыков в Dominion заключается в том, чтобы определять, что и когда покупать. На самом деле, игра в карты, хотя и важна, обычно оказывает значительно меньшее влияние на игру в целом. Для большинства карт просто нет доступных вариантов: «Лаборатория», «Mountebank», «Венчурный банк» и т. Д. - это все карты, которые «разыгрывают сами себя». Тем не менее, в некоторых стратегиях используются карты, требующие более сложных стилей игры. Например, хотя обычно разумно раскрыть Ров, если у вас в руке есть библиотека, а ваш оппонент играет Ополчение, раскрытие Рва обычно не является оптимальным ходом. ИИ использует простую модель упреждающего воспроизведения, которую можно найти в PlayerHeuristic.cpp. Для многих карт это сводится к простой эвристике. Например, при игре в шпиона ИИ всегда сбрасывает карту противника, если только это не Проклятие, Медь, Руины,или чистая карта победы. Я провел несколько экспериментов с более сложными моделями (обсуждаемыми в разделе «Будущие работы»), но в настоящее время я не нашел их, чтобы существенно изменить стратегии, к которым сходится ИИ. Практически для всех королевств поведение ИИ при покупке имеет гораздо большее влияние, чем выбор, сделанный во время реальной розыгрыша карт.

Некоторые карты действительно допускают необходимость более сложного игрового поведения. Хорошими примерами являются Salvager и Remodel, игровые свойства которых могут резко меняться на протяжении всей игры. Например, если вы в настоящее время лидируете и хотите быстрее истощить кучу провинции, вы можете спасти провинцию, и аналогично, если вы очень поздно в игре, вы можете преобразовать золото в провинцию. Когда такие карты присутствуют в королевстве, они испускают параметры каждой карты, которые добавляются к набору параметров, доступных ИИ. Затем они изменяются таким же образом, как и параметры меню Buy, позволяя ИИ адаптировать хорошие игровые стратегии для этих типов карт.

7. Будущая работа

Провинциальный все еще в стадии разработки. Вот несколько мыслей о текущей реализации и следующих шагах:

  • Реализации карт - было реализованобольшинство карт из Base, Prosperity, Intrigue и Seaside, а также несколько пользовательских карт, разработанных моими друзьями. Хотя остается довольно много карт, он все же покрывает более чем достаточно карт, чтобы охватить королевства с очень сложными стратегиями. Реализация новых карт также довольно проста, поскольку они, как правило, повторно используют общие функции из предыдущих наборов, такие как «сбросить до N карт» или «положить N карт поверх вашей колоды».
  • Несколько противников -игра Dominion резко меняется, когда присутствует несколько противников. В настоящее время Provincial может играть против нескольких противников, но просто использует стратегии, которые он узнает из моделирования против одного игрока. Двигаясь вперед, было бы интересно взглянуть на построение стратегий для нескольких противников, хотя пространство жизнеспособных стратегий значительно больше, и их труднее искать.
  • Ускорение работы с новыми королевствами - внастоящее время провинциал должен тренировать разные стратегии для каждого нового королевства. Хотя он может создавать приемлемые стратегии за считанные минуты, в идеале он мог бы делать это еще быстрее, используя преимущества королевств, которые он ранее разработал, для которых есть в его базе данных стратегий. После того, как критическая масса королевств была изучена, должна появиться возможность засеять начальный пул стратегиями из «ближайших королевств» (например, тех, у которых есть как минимум 4 перекрывающиеся карты припасов). Это должно привести к гораздо более быстрой сходимости и продемонстрировать передачу знаний из предыдущих игр, аналогичную процессу, используемому опытными игроками-людьми.
  • Доступность в Интернете.Поскольку основная стратегия закупок Provincial представляет собой упорядоченный список пар «карта-целое число», ее довольно легко подключить к другим игровым системам. На Isotropic Provincial уже очень конкурентоспособен и выигрывает более половины своих игр даже на высоком уровне игры, хотя он страдает от начальной задержки, связанной с необходимостью паузы на две минуты во время моделирования. Неудивительно, что Provincial также может (тривиально) уничтожить ИИ, который в настоящее время используется реализацией доминиона Гоко, и было бы довольно просто заменить стратегию покупки Provincial стратегией специальной покупки, используемой ИИ Гоко.
  • Превосходные стратегии покупки -Провинция намеренно избегает использования сложных методов машинного обучения, чтобы ее стратегии могли быть визуализированы и поняты игроками-людьми. Если убрать это ограничение, ИИ Провинциала сможет добиться заметных успехов. Например, играя во многие игры, ИИ может использовать мультиклассовый классификатор, чтобы точно угадать, сколько еще перетасовок в колоде ИИ, вероятно, получит. Это гораздо лучший показатель для определения того, когда игра закончится, по сравнению с количеством провинций, оставшихся в запасе, и может привести к гораздо более элегантному поведению при принятии решения о переходе к покупке провинций, герцогств и поместий.
  • Более продвинутые игровые стратегии -Хотя Provincial использует изощренную стратегию покупки, его алгоритм игры в карты сравнительно прост. Для королевств, где это важно, можно применить классический подход ИИ. В этой модели мы сначала определяем функцию значения состояния, которая показывает, насколько нам нравится или не нравится состояние игры. Затем ИИ использует поиск по дереву Минимакс или Монте-Карло, чтобы рассмотреть возможность выбора множества различных ветвей, и выбирает вариант, который дает наивысший ожидаемый результат. Несмотря на то, что это несложно реализовать, Provincial не использует этот подход, поскольку он значительно увеличивает время обучения. Однако, когда вы играете против человека после того, как была разработана его стратегия покупки, этот метод очень привлекателен, потому что фактор разветвления Доминиона очень низкий для большинства королевств.Это позволит ИИ уловить многие тактики, используемые опытными игроками, такие как «Правило предпоследней провинции» и многие другие стратегии, часто обсуждаемые на сайте dominionstrategy.com.

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

8. Код

Пользовательский интерфейс этого проекта написан на C #, а серверная часть написана на C ++. Поскольку бэкэнд C ++ не использует внешних библиотек (это просто быстрый игровой движок Dominion), на самом деле не так уж сложно запустить приложение под Mono при работе в операционных системах Linux или Mac. Provincial также имеет репозиторий GitHub, и в будущем я планирую добавить файлы сборки для систем на базе UNIX.

Код структурирован с использованием простой объектно-ориентированной модели стека событий. Интерфейс карты вызывается всякий раз, когда играется карта или запускается другое событие, связанное с картой. Если карта имеет эффект, который может потребовать ответа от пользователя или других игровых сущностей (например, атаки, которые могут вызвать реакцию), она помещает объект Event в стек. Когда стек событий пуст, игра продвигается, используя основные правила текущей фазы игры. Когда стек событий не пуст, игра продолжается, обрабатывая событие в верхней части стека.

ПОПУЛЯРНЫЕ СТАТЬИ