УДК 519.85 6.3.

Панченко О.О., Куликова Е.Б., Хоруженко А.С.

Науч. рук.: асс. Хоруженко А.С.

Донецкий национальный технический университет

Визуализация моделирования матричной игры "Поиск шумного объекта"

Введение

Игры можно классифицировать по различным признакам.

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

Во-вторых, коалиционные игры, в которых принимающие решение игроки согласно правилам игры объединены в фиксированные коалиции. Члены одной коалиции могут свободно обмениваться информацией и принимать полностью согласованные решения.

По выигрышу игры можно разделить на антагонистические и игры с ненулевой суммой.

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

По количеству стратегий игры делятся на конечные и бесконечные.

Изучение теории лучше начинать с простейшей статической модели – матричной игры, в которой участвуют два игрока, множество стратегий каждого из игроков конечно, а выигрыш одного игрока равен проигрышу другого [2].

Описание объекта исследования

Система Г= (X, Y, K), где X и Y – непустые множества, и функция K:X Y R¹ называется антагонистической игрой в нормальной форме.

Элементы x X и y Y называются стратегиями игроков 1 и 2 соответственно в игре Г, элементы декартового произведения X Y (пары стратегий (x, y), где x Х и y Y – ситуациями, а функция K – функция выигрыша игрока 1. Выигрыш игрока 2 в ситуации (x, y) полагается равным [-K(x, y)], поэтому функция K также называется функцией выигрыша самой игры Г, а игра Г – игрой с нулевой суммой. Таким образом, используя принятую терминологию, для задания игры Г необходимо определить множества стратегий X,Y игроков 1 и 2, а также функцию выигрыша K, заданную на множестве всех ситуаций X Y [2].

Игра Г интерполируется следующим образом. Игроки одновременно и независимо выбирают стратегии x Х и у Y. После этого игрок 1 получает выигрыш, равный K(x, y), а игрок 2 – (-K(x, y)).

Антагонистические игры, в которых оба игрока имеют конечные множества стратегий, называются матричными.

Пусть игрок 1 в матричной игре имеет всего m стратегий. Упорядочим множество Х стратегий первого игрока, то есть установим взаимно однозначное соответствие между множествами М={1, 2, …, m} и Х.

Аналогично, если игрок 2 имеет n стратегий, то можно установить взаимно однозначное соответствие между множествами N={1, 2, …, n} и Y. Тогда игра Г полностью определяется заданием матрицы А={ }, где = K(x_i, y_j), (i, j) М, j N (отсюда и название игры – матричная). При этом игра Г реализуется следующим образом. Игрок 1 выбирает строку i М, а игрок 2 (одновременно с ним) – столбец j N. После этого игрок 1 получает выигрыш , а второй – (- ). Если выигрыш равен отрицательному числу, то речь идет о фактическом проигрыше игрока.

Игру Г с матрицей выигрышей А обозначим Г_А и назовем (m n)-игрой (по размерности матрицы А). Если из изложения понятно, об игре с какой матрицей идет речь, то индекс А будем опускать [3].

Предположим, что игрок 1 ведет поиск подвижного объекта (игрок 2) с целью его обнаружения. Игрок 2 преследует противоположную цель (т. е. стремится уклониться от обнаружения). Игрок 1 может двигаться со скоростями , , , а игрок 2 — соответственно со скоростями , , .

Дальность действия средства обнаружения игрока 1 в зависимости от скоростей движения участников игры приведена в матрице:

Стратегиями игроков являются скорости движения, а в качестве выигрыша игрока 1 в ситуации примем производительность поиска , где элемент матрицы D [3]. Тогда задача выбора скоростей игроков при поиске – уклонении может быть представлена матричной игрой с матрицей:

Для визуализации моделирования данной матричной игры была разработана программа на языке C#.

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

Выводы

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

Дальнейшее развитие программы связано с написанием модуля игрока-компьютера, который бы выполнял роль "искателя" или "убегающего" согласно выбранной стратегии.

Литература

1. Губко М.В., Новиков Д.А. Теория игр в управлении организационными системами. – Москва, 2005. – С.138.

2. Крушевский А.В. Теория игр. – Киев: Объединение "Высшая школа", 1977. – С.216.

3. Петросян Л.А., Зенкевич Н.А. Теория игр. – Москва, 1998. – С.295.