Программная реализация метода приближенного решения матричных игр

NovaInfo 39, скачать PDF
Опубликовано
Раздел: Технические науки
Язык: Русский
Просмотров за месяц: 6
CC BY-NC

Аннотация

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

Ключевые слова

СМЕШАННЫЕ СТРАТЕГИИ, ПРИБЛИЖЕННЫЙ МЕТОД ОПРЕДЕЛЕНИЯ ЦЕНЫ ИГРЫ, ТЕОРИЯ ИГР

Текст научной работы

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

Однако для матриц большого размера методы линейного программирования малопригодны, т.к. приводят к значительным трудностям при вычислениях. Зачастую при решении задач теории игр точные решения не требуются, к тому же выигрыши игроков в каждой конкретной ситуации могут не всегда определяться точными значениями. Например, исходная платежная матрица игроков может быть получена на основе некоторых исходных данных (в том числе экспериментальных), уже содержащих в себе некоторые ошибки (связанные с погрешностями измерений). В итоге, числа матрицы уже сами по себе не будут являться точными значениями, и поэтому точность в определении значения цены игры и распределении стратегий игроков не будет оправдана. Кроме того, некоторая погрешность в оценке игроком своего выигрыша на практике не будет приводить к каким-либо серьезным последствиям: небольшое отклонение игрока от его истинной оптимальной стратегии не приведет к заметному изменению в его выигрыше.

В таких случаях лучше использовать приближенные методы решения. Одним из таких методов является метод фиктивного разыгрывания игры [1, 2], или метод Брауна-Робинсона, относящийся к итеративным методам.

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

К преимуществ такого метода относится его простота, однако имеется и недостаток — малая скорость сходимости (причем она сильно зависит от значений элементов матрицы). Стоит также отметить, что сложность и объем вычислений относительно слабо растут с ростом размера матрицы (примерно пропорционально числу строк и столбцов матрицы).

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

Метод Брауна-Робинсона удобно реализовать программно для определения решений игры с использованием ЭВМ. Ниже в работе представлена программа для получения приближенного решения матричных игр, реализованная в системе программирования Delphi. Программа поддерживает работу с матрицами размером до 100×100, окно программы изображено на рис. 1.

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

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

На рис. 2-4 показаны некоторые примеры работы с программой для матриц различных размеров.

Для рис. 2 точное решение имеет следующий вид: X \left (\frac {1}{3}; \frac{2}{3}; 0 \right), Y \left (\frac {1}{8}; \frac{5}{8}; \frac{1}{4} \right), V=1, для рис. 3: X \left (\frac {11}{20}; \frac{4}{20}; \frac{5}{20} \right), Y \left (\frac {8}{20}; \frac{7}{20}; \frac{5}{20} \right), V=1,85. Здесь X и Y — оптимальные стратегии первого и второго игроков соответственно, V — цена игры. Видно, что для рис. 2 требуемая точность достигается всего за 48 итераций, тогда как для рис. 3 — уже за 60030 итераций.

На рис. 4 рассмотрен пример для матрицы размером 7×8. Количество итераций для достижения указанной точности — более 10 млн.

Пример 1: нахождение решений прямоугольной игры 3×3
Рисунок 2. Пример 1: нахождение решений прямоугольной игры 3×3
Пример 2: нахождение решений прямоугольной игры 3×3
Рисунок 3. Пример 2: нахождение решений прямоугольной игры 3×3
Пример 3: нахождение решений прямоугольной игры 7×8
Рисунок 4. Пример 3: нахождение решений прямоугольной игры 7×8

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

Читайте также

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

  1. Булатова З.А., Дмитриев В.Л. Практикум по теории игр и исследованию операций. Уфа: РИЦ БашГУ, 2011. – 124 с.
  2. Дж. Мак-Кинси. Введение в теорию игр. М.: Государственное изда-тельство физико-математической литературы, 1960. – 420 с.
  3. Хачатрян С.Р., Пинегина М.В., Буянов В.П. Методы и модели решения экономических задач. М.: Изд-во «Экзамен», 2005. – 384 с.

Цитировать

Дмитриев, В.Л. Программная реализация метода приближенного решения матричных игр / В.Л. Дмитриев, А.Р. Тугузбаева. — Текст : электронный // NovaInfo, 2015. — № 39. — URL: https://novainfo.ru/article/3991 (дата обращения: 06.12.2022).

Поделиться