Введение 4
Постановка задачи 5
Обзор литературы 7
Глава 1. Игра простого преследования на плоскости 9
1.1. Математическая модель игры простого преследования 9
1.2. Некоторые способы задания функции выигрыша 11
1.3. Некоторые стратегии игроков 12
1.4. Дискретная игра простого преследования 13
1.5. Игра с «линией жизни» 14
Глава 2. Игра простого преследования в круге 15
2.1. Математическая модель игры преследования в круге 15
2.2. Допустимость стратегий в игре преследования в круге 16
2.2.1. Допустимость стратегий для игры Гс 16
2.2.2. Допустимость стратегий для игры Г^ 18
2.3. Модификация стратегий для игры преследования в круге .... 20
2.3.1. Параллельное сближение в игре Гс 20
2.3.2. Уклонение в игре Гс 22
2.3.3. Параллельное сближение в игре Г^ 23
2.3.4. Уклонение в игре Г'с 24
Глава 3. Программная реализация 26
3.1. Вывод геометрических формул 27
3.1.1. Координаты пересечения окружностей 28
3.1.2. Координаты пересечения луча и окружности 30
3.1.3. Реализация геометрических расчетов 32
3.2. Программная реализация 33
3.2.1. Общая структура кодовой базы 33
3.2.2. Отрисовка содержимого экрана 35
3.2.3. Основные стратегии игроков 36
Глава 4. Численные эксперименты 37
4.1. Статистические эксперименты 37
4.1.1. Уклонение с шумом 37
4.1.2. Сравнение условий в стратегии параллельного сближения 39
4.1.3. Стратегия, основанная на отношений расстояний 42
4.2. Перебор с отсечением 44
4.2.1. Описание алгоритма 44
4.2.2. Реализация и результаты 47
4.3. Перебор на классе правдоподобных стратегий 48
Выводы 52
Заключение 53
Приложение 55
Таблицы наблюдений 55
Листинг программного кода 91
Main.hx 91
Demonstration.hx 94
Simulation.hx 98
LikelihoodEvasion.hx 106
PursuerStrats.hx 109
EvaderStrats.hx 113
Geom.hx 115
MovingCS.hx 117
Drawer.hx
Теория игр преследования изучает ситуации противостояния двух классов игроков - преследователей и убегающих. Преследователи стремятся как можно быстрее поймать всех убегающих (здесь поимка - суть сближение на заданное расстояние, например, равное длине вытянутой руки). Убегающие, напротив, стремятся как можно дольше избегать поимки, если возможно - не допускать ее в принципе. Основная задача теории игр преследования - вывести оптимальные стратегии (суть уравнения, выражающие зависимость скорости рассматриваемого игрока от местоположения каждого из игроков и, возможно, скорости оппонента) для каждого игрока. С другой стороны, многочисленные варианты игр преследования могут переопределять понятие стратегии игрока произвольным образом.
У игр преследования выделено значительное число классов и вариаций. Делят их, в том числе, по количеству преследователей и убегающих (наиболее простой и изученный вариант - игры с одним убегающим и одним преследователем); по размерности пространства, в котором проходит погоня (будь то преследование на плоскости, в трехмерном пространстве или даже в пространствах высшей размерности, в которых игра преследования носит уже более абстрактный, оторванный от реальности смысл); по ограниченности этого пространства (иначе говоря, наличие, расположение и форма “стен”, препятствующих движению).
Выделяется крупная категория игр преследования с «линией жизни» - в них цели игроков модифицируются: убегающий, в целом, стремится пересечь линию, называемую «линией жизни», гарантирующую ему неприкосновенность, а преследователь - поймать убегающего до того, как это случится. Пример, иллюстрирующие смысл «линии жизни» - берег в ситуации спасения от агрессивно настроенных морских обитателей.
Наконец, исследуются даже игры преследования в вихревых пространствах, где “ветер” словно помогает игрокам двигаться в определенных направлениях.
Приложения теории дифференциальных игр преследования довольно широки. Игры преследования на плоскости могут использоваться для корректировки программ дрессировки охотничьих собак. Если на плоскость добавить препятствия, становится возможно эффективное моделирование процессов поимки сбегающих заключенных, автомобильной погони.
К играм преследования в пространстве имеется большой интерес у военной отрасли, они позволяют разрабатывать высокоточные программы управления самонаводящимися ракетами. Становится возможным точный расчет оптимальных траекторий и для более сложных физических условий - переход из воздушной среды в водную, движение воздушных масс, уклонение от препятствий и огибание специальных зон. Сюда же относятся и игры преследования с «линией жизни», ведь они позволяют учитывать расстояние, на котором сигналы достигают управляемых ракет.
Различные вариации игр преследования, с другой стороны, в последнее время также используются и для разработки продвинутого ИИ в видеоиграх различных жанров, позволяя создавать ботов, моделирующих поведение реальных игроков с крайне высокой степенью точности.
В ходе работы были получены следующие результаты:
• Введено определение дискретного аналога игры преследования в круге;
• Проверена допустимость ряда стратегий, значимых для игры преследования на неограниченной плоскости, а также введены допустимые аналоги для тех из них, для которых допустимость нарушается;
• Разработана система проведения симуляций игры преследования в круге с использованием различных стратегий игроков;
• Система была успешно протестирована; с ее помощью доказан ряд статистических гипотез, сравнивающих эффективность стратегий игроков;
• Были созданы два алгоритма перебора стратегий убегающего, которые впоследствии были реализованы в рамках разработанной системы симуляций;
• С использованием алгоритмов перебора были получены стратегии, оптимальные на заданных классах.
Полученные результаты позволяют с уверенностью заявить, что поставленная задача была решена в полной мере.
