Владимиров А. Э., Эгипти Д. А., Курбанкадиева Е. М. Теоретико-игровая модель патрулирования на линейном графе // StudArctic forum. Выпуск 3 (11), 2018, DOI: 10.15393/j102.art.2018.3061


Выпуск № 3 (11)

Компьютерные и информационные науки

pdf-версия статьи

Теоретико-игровая модель патрулирования на линейном графе

Владимиров Антон Эдуардович
Петргу (г.Петрозаводск, ул. Белорусская д.15 к.433),
vladimirowant@yandex.ru
Эгипти Даниил Александрович
Петргу (Петрозаводск, Сулажгорская 4 корпус 1 квартира 4),
san.delli253@gmail.com
Курбанкадиева Елизавета Муслимовна
Петргу (Петрозаводск Октябрьский пр-кт 63 кв 42),
kurbankadievalisa@yandex.ru
Научный руководитель:
Дорофеева Юлия Александровна
Ключевые слова:
Теория игр
платежная матрица
графы
модель
чистые стратегии
Аннотация: В статье рассматривается задача патрулирования на линейном графе. Построение платежной матрицы всех возможных вариантов игры.
Определение выигрышных стратегий атаки и патрулирования. Выявлены следующие закономерности: как меняются стратегии патрулирования, меняется ли период игры, количество вершин графа (этажей).
Статья поступила: 25.09.2018; Принята к публикации: 12.12.2018;

Основной текст

Теория игр рассматривает ситуации, при которых сталкиваются инте­ресы двух или более сторон, преследующих различные цели. Такие ситуа­ции называют конфликтными. Стороны, участвующие в конфликте, назы­ваются игроками. Игроками могут быть как отдельные лица, так и группы лиц (партнеры в бизнесе, фирмы и т.д.). Последовательные действия каж­ дого из игроков зависят от действий, предпринятых ранее другими игро­ками. По возможности предварительных (до игры) договоренностей.[3]

1. В зависимости от видов ходов игры подразделяются на стратегические и азартные. Азартные игры состоят только из случайных ходов - ими теория игр не занимается. Если наряду со случайными ходами есть личные ходы, или все ходы личные, то такие игры называются стратегическими.

2. В зависимости от числа участников игры подразделяются на парные и множественные. В парной игре число участников равно двум, в множественной - более двух.

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

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

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

Исходом кооперативной игры является дележ выигрыша коалиции, который возникает не как следствие тех или иных действий игроков, а как результат их наперед определенных соглашений.

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

4. По количеству стратегий каждого игрока игры подразделяются на конечные (число стратегий каждого игрока конечно) и бесконечные (множество стратегий каждого игрока бесконечно).

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

6. По виду описания игры подразделяются на позиционные игры (или игры в развернутой форме) и игры в нормальной форме. Позиционные игры задаются в виде дерева игры. Но любая позиционная игра может быть сведена к нормальной форме, в которой каждый из игроков делает только по одному независимому ходу. В позиционных играх ходы делаются в дискретные моменты времени. Существуют дифференциальные игры, в которых ходы делаются непрерывно. Эти игры изучают задачи преследования управляемого объекта другим управляемым объектом с учетом динамики их поведения, которая описывается дифференциальными уравнениями.

Существуют также рефлексивные игры, которые рассматривают ситуации с учетом мысленного воспроизведения возможного образа действий и поведения противника.

7. Если любая возможная партия некоторой игры имеет нулевую сумму выигрышей fi, всех N игроков (), то говорят об игре с нулевой суммой. В противном случае игры называются играми с ненулевой суммой.

Очевидно, что парная игра с нулевой суммой является антагонистической, так как выигрыш одного игрока равен проигрышу второго, а следовательно цели этих игроков прямо противоположны.[5]

Конечная парная игра с нулевой суммой называется матричной игрой. Такая игра описывается платежной матрицей, в которой задаются выигрыши первого игрока. Номер строки матрицы соответвует номеру применяемой стратегии первого игрока, столбец - номеру применяемой стратегии второго игрока; на пересечении строки и столбца находится соответствующий выигрыш первого игрока (проигрыш второго игрока).[5]

Конечная парная игра с ненулевой суммой называется биматричной игрой. Такая игра описывается двумя платежными матрицами, каждая для соответствующего игрока.[5]

Различают чистые и смешанные стратегии. Чистые стратегии построены на инструк­циях, не использующих случайные числа. Профиль стратегий — это набор стратегий по одной для каждого игрока.

В качестве примера антогонистической игры рассмотрим модель патрулирования на линейном графе.

Граф G называется пара множеств (V,E), где  V – не пустое, конечное множество элементов, называемых вершинами. Графически это множество изображается точками.  E – конечное множество неупорядоченных пар различных элементов из V, называемых ребрами. Графически это множество изображается линией, соединяющей пару точек. Путь — неориентированный граф. Но при работе с путями удобно вводить направление прохода по пути, отличать начало и конец пути друг от друга. При замене направления на противоположное путь как граф не изменяется.[9]


На данный момент задача решена для разветвленного графа на линейном графе[8] нужно установить зависимость между характеристиками графа и значением игры. Рассмотрим граф всех возможных стратегий патрулирующего (рис.2) в виде одноподъездного дома с n-ым количеством этажей на каждом этаже которого есть сейф. На одном из этажей находится атакующий и начинает вскрывать сейф . В это время на первом этаже дома находится патрулирующий. Задача патрулирующего – поймать атакующего, посредством обхода этажей дома (обхода вершин линейно ориентированного графа). В свой ход патрулирующий может переместиться на соседний этаж (вершину графа с которой есть связь), а атакующий может либо вскрывать сейф, либо затаиться.

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

Чтобы проанализировать данную игру, для различных наборов входных данных поставим следующие задачи:

-рассмотреть все возможные комбинации стратегий атакующего и патрулирующего;

-построить платежную матрицу;

-найти выигрышные стратегии для атакующего и патрулирующего;

-найти закономерности.

Рассмотрим задачу, где в доме 3 этажа и с периодом вскрытия сейфа 2. Все возможные стратегии вора:110, 011,220,022,330,033(ноль в стратегии значит, что преступник затаился), (остальные стратегии не имеют смысла, так как не ведут к победе) и полицейского:111, 112, 121, 122, 123. Пусть стратегия вора -330, а стратегия полицейского – 123. Сейф и преступник находится на третьем этаже.(рис1)


Шаг 1: атакующий начинает вскрывать сейф, патрулирующий появляется на 1 этаже.

Шаг 2: атакующий продолжает вскрывать сейф и побеждает(так как патрулирующий не обнаружил его во время вскрытия сейфа), патрулирующий появляется на 2 этаже.

Шаг 3: патрулирующий поднимается на 3 этаж и не обнаруживает атакующего.

Теперь рассмотрим обратный сценарий стратегия атакующего – 220 и ту же стратегию патрулирующего - 123. Атакующий и сейф находятся на втором этаже.

Шаг 1: атакующий начинает вскрывать сейф, патрулирующий на 1 этаже.

Шаг 2: атакующий продолжает вскрывать сейф, а патрулирующий в это время поднимается на второй этаж и оказывается на одном этаже с атакующим и ловит его, так как он не затаился.

Аналогичные рассуждения повторяем для всех наборов стратегий и записываем результат в платёжную матрицу(один из методов статистической теории решений, помогающих в выборе одного из нескольких вариантов) (табл.1).

Решаем игру в чистых стратегиях(определенная реакция игрока на возможные варианты поведения других игроков): вычеркнем не доминирующие строки (которые содержаться в других строках) из платёжной матрицы. Сначала вычеркнем первую строку, так как она содержится во второй, вторую и четвёртую строку потому что, они содержится в третьей. После этих действий у нас остались доминирующие стратегии патрулирующего – 121 и 123. Если 121 выбирается с вероятностью p то 123 выбирается с вероятностью 1-p. У атакующего же очевидно, что выигрышная стратегия 330 и выбирается она с вероятностью p, так как в платёжной матрице все нули, то есть какую бы стратегию патрулирующий не взял он всегда проиграет. В результате оказалось, что все вышеперечисленные действия занимают много времени даже для таких небольших входных параметров. При увеличении входных параметров платёжная матрица растёт довольно быстро и например, для семиэтажного дома с сейфом с периодом игры 1 платёжная матрица имеет размерность [267х49]. Заполнение и анализ такой матрицы вручную был бы долгим, поэтому была создана программа на языке с++ стандарта 2017 года. С помощью программы мы получили данные о количестве оптимальных стратегий при изменении входных параметров (табл. 2). Из табл.2 понятно, что количество оптимальных стратегий патрулирующего увеличивается пропорционально сложности вскрытия сейфа и, следовательно, растет вероятность выигрыша патрулирующего. С помощью данных, полученных программой, можно сделать вывод, что, оказывается, для любого значения параметров у атакующего есть стратегия, при которой он выигрывает независимо от выбранной стратегии патрулирующего. Чтобы гарантированно выиграть атакующему нужно вскрывать сейф на последнем этаже, так как патрулирующий просто не успевает до него дойти, следовательно, входные параметры не влияют на количество оптимальных стратегий для атакующего.

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

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

Проанализировав данные, полученные при вводе различных параметров в программу, можно сделать вывод что при добавлении цокольных этажей у атакующего пропадает выигрышная стратегия. Пусть количество цокольных этажей равно К, а количество оставшихся этажей N, период игры равен двум. Если К=N, то оптимальных стратегий у вора две NN0 или КК0. Если К>N то оптимальная стратегия атакующего KK0. N>K то оптимальная стратегия NN0. У патрулирующего количество оптимальных стратегий не растёт.


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


Список литературы

1.В.В.Гусев,В.В.Мазалов,“Оптимальные стратегии в игре патрулирования на графе”, Вестн. С.-Петербург. ун-та. Сер. 10. Прикл. матем. Информ. Проц. упр., 2015, № 2, 61–76

2. Зыков А.А. Основы теории графов. - М.:Наука, 1987, 384 с.

3. Кобзарь, А.И. Теория игр: Играют все / А.И. Кобзарь, В.Н. Тикменов, И.В. Тикменова. - М.: Физматлит, 2015. - 272 c.

4.Мазалов В. В. Математическая теория игр и приложения. — Сант-Петербург - Москва - Краснодар: Лань, 2010. — 446 с.

5.Теория игр: Учеб. пособие для ун-тов:/Л.А. Петросян, Н.А. Зенкевич, Е. А. Семина. - М.: Высш. шк., Книжный дом «Университет», 1998. - 304 с:

6. Колесник, Г.В. Теория игр: Учебное пособие / Г.В. Колесник. - М.: КД Либроком, 2014. - 152 c.

7. Оре О. Теория графов.— 2-е изд.— М.: Наука, Главная редакция физико-математической литературы, 1980, 336 с

8. Теория игр : учебник и практикум для академического бакалавриата / В. Л. Шагин. — М. : Издательство Юрайт, 2016. — 223 с. — Серия : Авторский учебник.

9. Ф. Харари. Теория графов. // Москва, “Мир”, 1973. (Перевод с ан- глийского. F.Harary, Graph theory, Addison-Wesley, 1969.)



Просмотров: 286; Скачиваний: 50;

DOI: http://dx.doi.org/10.15393/j102.art.2018.3061