risk game ai agent
1.0.0
Риск - это стратегическая настольная игра дипломатии, конфликтов и завоевания для двух -шести игроков. Turn вращается среди игроков, которые контролируют армии игры, с которыми они пытаются запечатлеть территории у других игроков, с результатами определяются Dice Rolls. Цель игры состоит в том, чтобы занять каждую территорию на доске, и при этом устранить других игроков. Каждый ход состоит из двух действий:
Цель этого проекта состояла в том, чтобы внедрить игру риска с некоторыми изменениями, внесенными в правилах, и разработать искусственно интеллектуального агента, который способен правильно играть в игру и иметь очень высокие шансы на победу, когда они сталкиваются с другими противниками, включая оба реальных человека игроки или другие агентские игроки.
Игра реализована с использованием языка программирования Java. Контроль поворотов, выполнение запрашиваемых игроков, обновления игровой карты, проверка, происходит ли все в соответствии с правилами и т. Д., - это то, что делает эта часть кода. Пользовательский интерфейс Game также разработан с помощью файлов .fxml, которые рисуют карту и представляют собой платформу, соединяющую игрока с логикой игры.
В этом разделе фокусируется на реализации и оценке эвристики, которая приводит к сильному ИИ для риска игры.
Реализация основана на алгоритме Alpha-бета-бета. Игрок строит дерево прогнозирования на основе алгоритма DFS.
Всякий раз, когда настанет очередь агента играть, производится дерево. Узлы деревьев являются состояниями игры (карта игры в этом состоянии), и каждое преимущество является возможной атакой, сделанной от текущего состояния, чтобы атаковать состояние результата карты. Атака состоит из начала и целевых координат территорий и количества подразделений, выбранных для атакующей армии. Корневой узел - это текущее состояние карты, из которого должен выбирать свои движения. Хотя дерево не может предсказать до конечного состояния игры из -за большого количества возможных движений, которые игрок может иметь в каждом состоянии, которые не позволяют память и временные рамки. Следовательно, игрок может построить дерево только до определенной глубины, которую мы определили в коде. Есть также некоторые упрощения, применяемые к определенным частям игровой стратегии агента, которые будут объяснены в следующих разделах. Чтобы принять наилучшую возможную эвристику решений, определяется для самых глубоких узлов (листьев деревьев), которые оценивают, насколько достижение этого состояния может быть полезным для игрока. Сказанная эвристика будет дополнительно объяснена в отчете. Когда значения листьев будут определены, дерево будет передано минимальной обрезке альфа-бета, и этот известный алгоритм найдет лучшую серию действий, которые может иметь игрок.
Поставка единиц на территории может быть сложной задачей; В том смысле, что мы хотим улучшить нашу атакующую силу, но также убедитесь, что имели достаточную защиту на территориях, которые подвергаются опасности подвергнуться нападению. Развертывание подразделений в странах, прилегающих к вражеским территориям, может быть разумным способом сохранить баланс между этими двумя целями.
Проект Упрощение:
Прогнозирование и включение всех возможных сценариев черновиков в дерево прогнозирования приведет к сложному дереву, которое столкнется с проблемами, упомянутыми ранее; Следовательно, одно из сделанных упрощений заключается в том, что мы используем эвристику, которая, как оказалось, всегда имеет наилучший возможный результат, и предсказываем, что противники также делают этот подход в составлении; Другими словами, мы удаляем результаты составления, поскольку возможности формируют дерево предсказания и изменяем их на окончательные сценарии черновиков.
Для этого мы предпринимаем следующие шаги:
Эвристика на проекте:
Шаг 1:
Акинг суммирование всех подразделений в вражеских странах, примыкающих к стране X, даст меру, которую мы называем угрозой безопасности границ (BST) в x.
Шаг 2:
Разделение этого BST на подразделения, расположенные в X, дает коэффициент безопасности границы (BSR), который можно сравнить между всеми пограничными странами.
Страны с высоким BSR, скорее всего, будут завоеваны вражеским игроком, поскольку число вражеских подразделений в соседних вражеских странах относительно выше, чем количество единиц в самой стране. Выбор стран с высоким BSR для снабжения увеличит их оборонительную силу за счет снижения BSR. Поставка подразделений странам с более низким BSR, что означает, что у них уже есть лучшая оборонительная позиция, повысит их наступательную силу, повышая шансы на успешную атаку со стороны этих стран.
Шаг 3:
Нормализация BSR, разделяя его на сумму всех BSR стран, владеет игрок, даст прямое измерение, с помощью которого кто -то может организовать единицы. Нормализованный коэффициент безопасности границы (NBSR) рассчитывается по:
Это дает прямое соотношение того, как подразделения могут быть распределены между странами. На данный момент мы видим, что с этими отношениями возникнут проблемы, потому что некоторые данные не имеют значения, и мы не хотим добавлять единицы ко всем нашими территориям, поэтому мы устанавливаем порог между этапами второго и трех, сортируя данные BSRX в Порядок нисходящего (мы больше сосредотачиваемся на повышении силы защиты), разделяем данные со среднего и устанавливаем числа в нижней половине до нуля.
Шаг 4:
Шаг 4 будет продолжаться до тех пор, пока не будет больше доступных единиц.
В фазе атаки применяются некоторые упрощения, чтобы сделать дерево менее сложным, чтобы мы могли предсказать его на более глубокие уровни. Это может быть сделано, проверив, какие сценарии атаки имеют более высокий шанс выиграть битву и включить их только в дерево.
Чтобы оценить, насколько полезен лист дерева для этого конкретного игрока; Мы определили четыре эвристики, которые их наилучшие возможные веса находятся во время изучения эвристики, которая будет объяснена позже. Все функции возвращают результат от нуля к одному, потому что, когда функции оцениваются по отношению друг к другу, обучение и присвоение веса будут более точными.
Особенности:
Прибавление веса каждой из эвристики в предыдущей части помогает оценить, насколько важна и влияет каждый из них, чтобы агент выиграл игру. Процесс поиска этих весов через генетический и учится. Каждый ген представляет собой набор из четырех весов для этих четырех функций. Мы начинаем с генерации 100 набора случайных весов в диапазоне [0,10]. После этого произойдет 10 турниров. Для каждого турнира 10 генов из первичной популяции будут выбраны случайным образом. Все возможные пары генов будут играть друг против друга, и результат каждой игры в каждом турнире будет задокументирована. Функция фитнеса определяется как (количество побед / количество игр) для каждого гена. Будут выбраны три лучших гена в каждом турнире (на основе функции фитнеса), так что теперь у нас есть 30 выбранных генов. Среди них мы выбираем 12 случайных пар и для каждой пары выполняют кроссовер, который создает новый ген, расчет среднего веса пары генов. Поэтому у нас теперь есть 12 новых генов из этого кроссовера. С другой стороны, 3 гены случайным образом выбираются в 30 генах, которые у нас были, и мутируют их, изменяя один случайный вес каждого на другой случайный вес в диапазоне [0,10]. После всего этого у нас теперь есть 15 новых генов, которые помещаются в первичную популяцию, заменив 15 наименее хороших, которые у нас уже были. На этом этапе генерируется второе поколение генов. Этот процесс будет продолжать повторяться, пока не будет получено поколение генов. Лучший ген в этой популяции будет выбран как наши лучшие веса для чертов нашей эвристики, которую агент будет использовать для игры.
