Об одном альтернативном утверждении относительно исхода дифференциальной игры "наведения–уклонения" нескольких лиц в классе "контр"-стратегий
Рассмотрение позиционной дифференциальной игры "наведения-уклонения" нескольких лиц. Формализация игры в классе "контр"-стратегий, стабильные мосты. Приведение фазового вектора игры на свое целевое множество. Динамика конфликтно-управляемого объекта.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | статья |
Язык | русский |
Дата добавления | 26.04.2019 |
Размер файла | 255,9 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Об одном альтернативном утверждении относительно исхода дифференциальной игры "наведения-уклонения" нескольких лиц в классе "контр"-стратегий
С.В. Лутманов
Рассматривается позиционная дифференциальная игра "наведения-уклонения" нескольких лиц. Игра формализована в классе "контр"-стратегий. В предположении, что целевые множества игроков попарно не пересекаются, доказывается альтернативное утверждение относительно исходов игры. Смысл утверждения состоит в следующем. Для каждой начальной позиции либо существует единственный игрок, разрешающий задачу наведения на свое целевое множество в классе "контр"-стратегий ("чистых" стратегий), либо найдется такой способ управления всех игроков в классе "чистых" стратегий ("контр"-стратегий), что ни один из игроков-"уклонистов" не сможет привести фазовый вектор игры на свое целевое множество при условии, что остальные игроки придерживаются указанного способа управления. Данная статья является непосредственным продолжением работы [3].
Ключевые слова: "чистые" стратегии; "контр"-стратегии; стабильный мост; теорема об альтернативе.
1. Постановка дифференциальной игры "наведения-уклонения" нескольких лиц в классе "контр"-стратегий© С. В. Лутманов, 2011
Динамика конфликтно-управляемого объекта описывается обыкновенным векторным дифференциальным уравнением
, (1.1)
где - текущее время, - фазовый вектор объекта, - вектор управляющих параметров i-го игрока, - вектор-функция, описывающая как внутреннее устройство объекта, так и воздействие различных внешних факторов. Будем предполагать, что множества компактны, а функция непрерывна по совокупности переменных .
Относительно правых частей дифференциальных уравнений (1.1) принимаются стандартные в теории дифференциальных игр предположения:
локальные условия Липшица
.
2) условия продолжимости решения
.В пространстве -му игроку ставится в соответствие компактное множество , которое будем называть целевым множеством этого игрока. Неформальная цель игрока состоит в приведении фазового вектора игры в конечный момент времени на свое целевое множество. В случае если в конечный момент времени фазовый вектор игры не принадлежит ни одному из целевых множеств, то считается, что в игре достигнут компромисс. Описанную дифференциальную игру назовем игрой "наведения-уклонения" нескольких лиц. игра конфликтный уклонение
Принимается, что в любой момент времени игроки имеют точную информацию о реализовавшейся позиции игры. Однако осведомленность игроков о действиях друг друга зависит от того, является ли данный игрок игроком-уклонистом или нет. Дифференциальная игра в этом случае формализуется в классе позиционных "контр"-стратегий.
2. Формализация игры в классе "контр"- стратегий
Формализуем дифференциальную игру нескольких лиц в классе контр-стратегий.
Определение 1. Позиционной "контр"-стратегией -го игрока называется произвольная функция
,
где .
Физический смысл "контр"-стратегии игрока состоит в том, что в каждой позиции он назначает вектор своих управляющих воздействий, основываясь не только на информации о реализовавшейся позиции , но и на информации о выбранных в этой позиции управляющих параметрах игроками с индексами .
Соответствие между позиционной "контр"-стратегией и реализующей ее парой будем обозначать символом . Очевидно, что набор позиционных "контр"-стратегий всех игроков должен быть согласованным относительно использования информации игроками о выборе ими векторов управляющих параметров других игроков.
Определение 2. Будем говорить, что набор "контр"-стратегии всех игроков является согласованным, если для всех позиций и последовательности попарно различных индексов нельзя построить цепочку включений
.
Для согласованных "контр"-стратегий исключена ситуация "порочного круга", когда в одной и той же позиции некоторый игрок при выборе своего управляющего вектора использует информацию о выбранном управляющем векторе другого игрока. Тот, в свою очередь, использует информацию о выбранном управляющем векторе следующего игрока и т. д., а некоторый игрок в этой цепочке использует информацию о выбранном управляющем векторе первого игрока.
Пусть - согласованный набор позиционных "контр"-стратегий и - конечное разбиение отрезка времени точками .
Определение 3. Ломаной Эйлера , выходящей из позиции и порожденной набором позиционных "контр"-стратегией , назовем всякую абсолютно непрерывную функцию , удовлетворяющую дифференциальному уравнению
,
, (2.1)
Определение 4. Движением, выходящим из позиции и порожденным набором позиционных "контр"-стратегией , , назовем всякую функцию , для которой найдется последовательность ломаных Эйлера
, равномерно сходящаяся к ней на отрезке при условии .
Совокупность всех движений, выходящих из позиции и порожденных набором позиционных "контр"-стратегией , , будем обозначать символом и называть пучком конструктивных движений. Можно показать [1], что для любой позиции и любого согласованного набора позиционных "контр"- стратегий пучок движений содержит хотя бы одно движение.
Уклонение -го, игрока от стратегии, предписываемой ему набором согласованных "контр"-стратегий , будем моделировать тем, что в определении ломаной Эйлера реализация вектора управляющих воздействий -го игрока определяется не в виде кусочно-постоянной функции
,
а в виде произвольного программного управления . Пучок конструктивных движений, получающийся в результате перебора всех возможных уклонений -го игрока, обозначим символом
.
Игрок под номером , принимая решение уклониться от стратегии, предписываемой ему каким-либо набором стратегий, должен учитывать возможность любых действий со стороны остальных игроков. Эту возможность будем моделировать тем, что в определении ломаной Эйлера реализация вектора управляющих воздействий -го игрока, определяется не в виде кусочно-постоянной функции (2.1), а в виде произвольного программного управления . Пучок конструктивных движений, получающийся в результате перебора всех возможных действий со стороны игроков , обозначим символом .
В общем случае множество номеров поделим на множества и . При построении ломаной Эйлера принимаем, что игроки с номерами из множества формируют свои управляющие воздействия по формуле (2.1), а остальные игроки формируют их в виде произвольного программного управления . Пучок конструктивных движений в этом случае обозначим символом . Очевидно, что
.
3. Стабильные мосты
В дальнейшем на базе сформулированной игры "наведения-уклонения" нескольких лиц будет рассматриваться вспомогательная антагонистическая дифференциальная игра "наведения-уклонения" двух лиц [1]. В этой игре первый игрок отождествляется с подмножеством игроков , а второй игрок - с подмножеством . Первый игрок решает задачу наведения на множество , а второй - задачу уклонения от этого множества.
В зависимости от классов стратегий, в которых игра формализована, будем применять следующие обозначения:
первый игрок применяет "контр"-стратегии;
второй игрок применяет "контр"-стратегии.
Определение 5. Множество будем называть -ста-бильным мостом, обрывающимся на множестве , если оно является стабильным мостом первого игрока [3], в антагонистической игре и при этом выполняется вложение
.
Дадим расшифровку приведенного определения.
Множество будет -стабильным мостом, , если для любых позиций , отображений ,
ставящих каждому вектору в соответствие набор векторов
и моментов времени , найдется такое решение дифференциального уравнения в контингенциях
для которого .
Из определения стабильности следует, что если два множества являются стабильными мостами, то и их объединение также будет стабильным мостом. Тогда существует максимальный стабильный мост, содержащий в себе любой другой стабильный мост. В работе [1] показано, что максимальный стабильный мост замкнут.
Лемма 1. Пусть максимальный -стабильный (-стабильный [3]) мост, обрывающийся на множестве . Тогда для любого найдется такое, что будет выполнено
.
Здесь максимальный -стабильный (-стабильный) мост, обрывающийся на множестве . Множество представляет собой замкнутую -окрестность множества .
Доказательство. Допустим, что утверждение леммы неверно. Тогда найдутся число и последовательность монотонно убывающих чисел , таких, что
,
где . Каждое из множеств замкнуто и ограничено, так как оно образовано пересечением двух замкнутых множеств, одно из которых ограничено.
Из монотонного убывания последовательности положительных чисел следует, что для любых номеров выполнено вложение . Отсюда в силу [2] выводим, что
.
Пусть . Тогда . Из того факта, что множество является максимальным -стабильным (-стабильным) мостом, обрывающимся на множестве , следует, что для начальной позиции не разрешима задача наведения в антагонистической дифференциальной игре (игре ).
По теореме об альтернативе [1] в игре (игре )
в позиции разрешима задача об уклонении от некоторой открытой -окрестности множества . Следовательно, позиция не может принадлежать ни одному из мостов , для которых . Последнее утверждение невозможно, т. к. из включения должно следовать включение при всех . Полученное противоречие доказывает лемму.
Определение 6. Множество будем называть -стабильным мостом в дифференциальной игре "наведения-уклонения" нескольких лиц, если оно является стабильным мостом второго игрока [3] в антагонистической игре
, .
Дадим расшифровку приведенного определения.
Множество будет -стабильным мостом, , если для любых позиций , отображений ,
ставящих каждому набору векторов
в соответствие вектор , и моментов времени найдется такое решение дифференциального уравнения в контингенциях
, для которого .
Определение 7. Систему множеств будем называть -стабильной, если для всех множество является -стабильным мостом в дифференциальной игре "наведения-уклонения" нескольких лиц.
4. Экстремальное прицеливание
Пусть замкнутое множество.
Определение 8. "Контр"-стратегия -го игрока называется экстремальной к множеству , если она является экстремальной стратегий первого игрока к множеству в игре
.
Дадим расшифровку приведенного определения. Полагаем
.(4.1)
В случае когда точек , доставляющих в (4.1), более одной, берется любая из них.
"Контр"-стратегия будет экстремальной к множеству , если
для тех позиций , в которых . В остальных позициях
произвольный вектор из множества .
Лемма 2. Пусть замкнутый -стабильный (-стабильный) мост в дифференциальной игре "наведения-уклонения" нескольких лиц, "контр"-стратегия ("чистая" стратегия [3]) является экстремальной к множеству и . Тогда для всякого движения , () будет выполнено включение для всех , если при всех .
Справедливость данной леммы следует непосредственно из лемм 82.1, 82.2 книги [1].
Пусть система попарно непересекающихся открытых множеств.
Определение 9. Набор "контр"-стратегий будем называть экстремальным к системе множеств , если при всех и позиций , для которых , имеют место равенства
,
,
где .(4.2)
В случае когда точек , доставляющих в (4.2), более одной, берется любая из них. Для остальных позиций управляющие воздействия игроков принимаются произвольными допустимыми воздействиями.
Заметим, что в силу условия набор "контр"-стратегий игроков, экстремальный к системе множеств является согласованным.
Лемма 3. Пусть система попарно непересекающихся открытых множеств является -стабильной [3] (-стабильной). Набор "контр"-стратегий ("чистых" стратегий [3]) всех игроков экстремален к системе множеств
, и
.
Тогда для любого номера и всякого движения (движения ), будет выполнено включение
для всех , если
при всех .
Справедливость данной леммы следует непосредственно из лемм 82.1, 82.2 книги [1].
Предположим, что целевые множества игроков попарно не пересекаются. Дадим определения возможных исходов дифференциальной игры "наведения-уклонения" нескольких лиц.
Определение 10. Будем говорить, что в начальной позиции "чистая" стратегия ("контр"-стратегия ) -го игрока , решает задачу наведения на целевое множество этого игрока, если для всех (для всех ) выполнено включение .
Определение 11. Будем говорить, что в начальной позиции набор "чистых" стратегий всех игроков (согласованный набор "контр"-стратегий всех игроков ) является компромиссным, если существует , что для всех и выполняется условие
.
Лемма 4. Пусть выполнено условие
Тогда где максимальный -стабильный мост (-стабильный мост), обрывающийся на множестве .
Доказательство. От противного приходим к паре индексов , для которых . Пусть . Тогда в силу леммы 2 стратегия , экстремальная к множеству , и стратегия , экстремальная к множеству , игроков и соответственно обеспечат включения
(),
.
().
С другой стороны, справедливо вложение
().
Для любого
,
()
должно выполняться
.
Последнее невозможно, что и доказывает справедливость леммы.
Из доказанной леммы следует, что для начальной позиции справедливо одно и только одно из следующих двух утверждений:
1) существует номер , что ;
2) ,
где максимальный -стабильный (-стабильный мост), обрывающийся на множестве .
В первом случае очевидно разрешима задача наведения -го игрока в классе "контр"-стратегий ("чистых" стратегий). Пусть имеет место второй случай. Тогда по лемме 1 найдется число , что , где максимальный -стабильный (-стабильный) мост, обрывающийся на множестве . Для всех номеров множество является открытым. Оно представляет собой совокупность тех и только тех начальных позиций, для которых не разрешима задача уклонения второго игрока в антагонистической дифференциальной игре
().
Тогда множество является максимальным стабильным мостом первого игрока в игре
(в игре ) и, следовательно, -стабильным (-стабиль-ным) мостом. Отсюда следует, что система открытых множеств является -стабильной (-стабильной.). Тогда по лемме 3 для всякой начальной позиции
набор "контр"-стратегий ("чистых" стратегий) всех игроков, экстремальный к системе множеств , будет компромиссным.
Таким образом, доказано следующее альтернативное утверждение относительно исходов дифференциальной игры "наведения-уклонения" нескольких лиц.
Теорема 1. Пусть в дифференциальной игре "наведения-уклонения" нескольких лиц целевые множества игроков попарно не пересекаются. Тогда для любой начальной позиции либо существует игрок, решающий задачу наведения на свое целевое множество в классе "контр"-стратегий ("чистых" стратегий), либо существует компромиссный набор "чистых" стратегий ("контр"-стратегий) всех игроков.
Список литература
1. Красовский Н.Н., Субботин А.И. Позиционные дифференциальные игры. М.: Наука, 1974. 456 с.
2. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа. М.: Наука, 1976. 544 с.
3. Лутманов С.В. Об одном альтернативном утверждении относительно исхода дифференциальной игры "наведения-уклонения" нескольких лиц в классе "чистых" и "смешанных" стратегий // Вестн. Перм. ун-та. Сер. Математика. Механика. Информатика. 2011. Вып. 1(5). С.53-61.
Размещено на Allbest.ru
Подобные документы
Реализация программы для решения матричных игр. Задание матрицы игры вручную и случайным образом, нахождение оптимальных стратегий игроков итерационным и методом чистых стратегий. Проектирование и листинг программного кода, сохранение матрицы игры.
контрольная работа [716,7 K], добавлен 11.06.2011Матричные игры и линейное программирование. Итеративный метод решения матричных игр. Игры на выживание, игры-погони. Критерии принятия решений. Персонал, набранный с помощью резерва в результате решения статистической игры по различным критериям.
курсовая работа [629,3 K], добавлен 08.10.2014Разработка компьютерной игры "Эволюция" с помощью игрового движка Unit. Сравнение критериев игры-аналога и разрабатываемой игры. Разработка графического интерфейса пользователя. Настройки камеры в редакторе Unity. Структура файла сохранения игры.
дипломная работа [3,6 M], добавлен 11.02.2017Основные подходы при создании Windows приложений. Изучение навыков работы с 2D графикой в Windows приложениях. Методы генерации псевдослучайных чисел. Разработка игры "Сапер" с расположением мин на основе нескольких методов генерации случайных чисел.
курсовая работа [63,2 K], добавлен 18.02.2009Алгоритмическое представление и описание правил игры "Эволюция". Построение диаграммы прецедентов. Разработка графического интерфейса пользователя. Реализация интерфейса в среде Unity. Структура файла сохранения игры. Проектирование поведения компьютера.
дипломная работа [3,3 M], добавлен 18.02.2017Проблема сокращения перебора при анализе сложных позиционных игр, древовидная структура выбора стратегий, в которых дерево игры в силу своего гигантского размера не может быть построено на практике полностью. Короткие нарды как конкретный пример игры.
дипломная работа [1,6 M], добавлен 27.10.2013Проект игры "Ловушка", созданный при помощи языка программирования C++. Описание заголовочных файлов. Правила и цель игры "Ловушка". Отображение движущихся объектов игры на экране с помощью заголовочного файла "gameclass.h". Описание игрового процесса.
курсовая работа [70,6 K], добавлен 14.10.2012Понятие и эволюция игр, анализ их различных жанров и существующих аналогов. Выбор программных средств для реализации игры, написание сюжета и выбор среды разработки игры. Алгоритмы для придания гибкости обучающей игре. Описание программных модулей.
дипломная работа [2,7 M], добавлен 27.10.2017Разработка и создание игры "Змейка". Использование динамически-активных принципов языка Java. Графические объекты программы. Описание игры, правила, теоретические сведения. Классы приложения. Типы данных. Реализация. Метод. Объект. Блок-схема игры.
курсовая работа [12,4 K], добавлен 18.06.2008Исследование спецификации логической игры "Сапёр". Системное и функциональное проектирование приложения. Разработка программных модулей. Обзор классов, необходимых для создания интерфейса данного приложения. Инструменты для реализации логической игры.
курсовая работа [1,2 M], добавлен 13.01.2016