Разработка метода обучения бота, учитывающего поведение человека-противника

1.

Волгоградский Государственный Технический Университет
Кафедра «Программное обеспечение автоматизированных систем»
Разработка метода обучения бота, учитывающего
поведение человека-противника
Исполнитель: студент группы ПОАС-1.1, Якимов Г. А.
Научный руководитель: Литовкин Дмитрий Васильевич,
кандидат технических наук, доцент
Волгоград, 2023

2.

Актуальность работы
• Игра – формализованное представление процесса
взаимодействия двух и более сторон, ведущих борьбу за
реализацию своих интересов.
• Каждая сторона пользуется некоторой стратегией в ходе данного
взаимодействия для удовлетворения своих интересов.
• Игра является упрощённой версией реальной задачи с
несколькими участниками.
• Научившись решать формализованные задачи общего вида,
можно переходить к реальным задачам, формализуемым на
данной модели.
2

3.

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

4.

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

5.

Объект и предмет исследования
• Объект исследования: принятие оптимальных решений
(стратегий) в условиях конфликта, участниками которых
являются как люди, так и киберфизические системы.
• Предмет исследования: стратегия, учитывающая поведение
человека-противника.
5

6.

Предметная область
6

7.

Предметная область
основа
7

8.

Предметная область
игровой менеджер
8

9.

Предметная область
игроки
9

10.

Входные и выходные данные
На вход:
- описание правил игры на
языке игр общего вида (Ludii);
- задание начальной
конфигурации/состояния игры.
На выходе: оптимальный ход,
исходя из текущего состояния
игры.
10

11.

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

12.

Представление игры
12

13.

Сравнительная таблица аналогов
Критерии сравнения
Полный
перебор
Минимакс Альфа-бета Метод Монтеалгоритм отсечение
Карло
Подходит для игр общего вида
+
+/–
+/–
+
+
Гарантирует выигрыш
+
+/–
+/–
+/–
+/-
Тип игрока-противника
идеальный
идеальный
игрок-человек
Скорость нахождения стратегии (1-4)
1
3
2.5
идеальный идеальный
2
2.5
Собственное
решение
13

14.

Предлагаемое решение
• Собственная функция оценки дерева состояний игры.
• Динамическое формирование эвристик из данных правил
игры на языке игр общего вида.
• Набор заданных эвристик, исходя из знания, что
противником выступает человек.
14

15.

Особенности человеческого поведения
• Человек может блефовать.
• Человек может допускать ошибки из-за:
• Усталости;
• Невнимательности;
• Самоуверенности;
• Ограниченность механизмов памяти;
• Неправильного определения проблемы;
• Неправильного анализа проблема;
• Неправильного исполнения необходимых действий.
15

16.

Средства реализации
• Язык программирования: Java
• Среда работы алгоритма: Ludeme/Ludii
(https://github.com/Ludeme/Ludii)
16

17.

Основные классы платформы
17

18.

Классы схем проведения турниров
18

19.

Классы сборщиков статистики
19

20.

Классы ботов
20

21.

Спасибо за внимание
21