Теория игр рассматривает ситуации, при которых сталкиваются интересы двух или более сторон, преследующих различные цели. Такие ситуации называют конфликтными. Стороны, участвующие в конфликте, называются игроками. Игроками могут быть как отдельные лица, так и группы лиц (партнеры в бизнесе, фирмы и т.д.). Последовательные действия каж дого из игроков зависят от действий, предпринятых ранее другими игроками. По возможности предварительных (до игры) договоренностей.[3]
1. В зависимости от видов ходов игры подразделяются на стратегические и азартные. Азартные игры состоят только из случайных ходов - ими теория игр не занимается. Если наряду со случайными ходами есть личные ходы, или все ходы личные, то такие игры называются стратегическими.
2. В зависимости от числа участников игры подразделяются на парные и множественные. В парной игре число участников равно двум, в множественной - более двух.
3. Участники множественной игры могут образовывать коалиции, как постоянные, так и временные. По характеру взаимоотношений игроков игры делятся на бескоалиционные, коалиционные и кооперативные.
Бескоалиционными называются игры, в которых игроки не имеют право вступать в соглашения, образовывать коалиции, и целью каждого игрока является получение по возможности наибольшего индивидуального выигрыша.
Игры, в которых действия игроков направлены на максимизацию выигрышей коллективов (коалиций) без последующего их разделения между игроками, называются коалиционными.
Исходом кооперативной игры является дележ выигрыша коалиции, который возникает не как следствие тех или иных действий игроков, а как результат их наперед определенных соглашений.
В соответствии с этим в кооперативных играх сравниваются по предпочтительности не ситуации, как это имеет место в бескоалиционных играх, а дележи; и сравнение это не ограничивается рассмотрением индивидуальных выигрышей, а носит более сложный характер.
4. По количеству стратегий каждого игрока игры подразделяются на конечные (число стратегий каждого игрока конечно) и бесконечные (множество стратегий каждого игрока бесконечно).
5. По количеству информации, имеющейся у игроков относительно прошлых ходов, игры подразделяются на игры с полной информацией (имеется вся информация о предыдущих ходах) и неполной информацией. Примерами игр с полной информацией могут быть шахматы, шашки и т. п.
6. По виду описания игры подразделяются на позиционные игры (или игры в развернутой форме) и игры в нормальной форме. Позиционные игры задаются в виде дерева игры. Но любая позиционная игра может быть сведена к нормальной форме, в которой каждый из игроков делает только по одному независимому ходу. В позиционных играх ходы делаются в дискретные моменты времени. Существуют дифференциальные игры, в которых ходы делаются непрерывно. Эти игры изучают задачи преследования управляемого объекта другим управляемым объектом с учетом динамики их поведения, которая описывается дифференциальными уравнениями.
Существуют также рефлексивные игры, которые рассматривают ситуации с учетом мысленного воспроизведения возможного образа действий и поведения противника.
7. Если любая возможная партия некоторой игры имеет нулевую сумму выигрышей fi, 
Очевидно, что парная игра с нулевой суммой является антагонистической, так как выигрыш одного игрока равен проигрышу второго, а следовательно цели этих игроков прямо противоположны.[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).
Данную задачу и программу можно модифицировать, добавив ещё один входной параметр – количество цокольных этажей. Это значит, что полицейский может двигаться как вверх, так и вниз, что усложняет задачу патрулирования.
Чтобы реализовать цокольные этажи в программе необходимо было изменить алгоритм генерации стратегий для атакующего и патрулирующего.
Проанализировав данные, полученные при вводе различных параметров в программу, можно сделать вывод что при добавлении цокольных этажей у атакующего пропадает выигрышная стратегия. Пусть количество цокольных этажей равно К, а количество оставшихся этажей 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.)