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

Размещено на http://www.allbest.ru/

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

Технические науки

Дмитриев Владислав Леонидович, кандидат наук, доцент, доцент

Тугузбаева Анжелика Рафаиловна, студент Башкирский государственный университет

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

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

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

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

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

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

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

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

программный реализация задача игра

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

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

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

Для рис. 2 точное решение имеет следующий вид: , , , для рис. 3: , , . Здесь X и Y - оптимальные стратегии первого и второго игроков соответственно, V - цена игры. Видно, что для рис. 2 требуемая точность достигается всего за 48 итераций, тогда как для рис. 3 - уже за 60030 итераций.

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

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

Рис. 3. Пример 2: нахождение решений прямоугольной игры 3Ч3

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

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

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

1. Булатова З.А., Дмитриев В.Л. Практикум по теории игр и исследованию операций. Уфа: РИЦ БашГУ, 2011. - 124 с.

2. Дж. Мак-Кинси. Введение в теорию игр. М.: Государственное издательство физико-математической литературы, 1960. - 420 с.

3. Хачатрян С.Р., Пинегина М.В., Буянов В.П. Методы и модели решения экономических задач. М.: Изд-во «Экзамен», 2005. - 384 с.

Размещено на Allbest.ru