Гарантированный проигрыш второго игрока

y* – оптимальная стратегия второго игрока, если

Гарантированный выигрыш первого игрока, применяющего свою оптимальную стратегию, равен гарантированному проигрышу второго игроку, применяющего свою оптимальную стратегию: – цена игры.

Сведение задачи теория игр к задаче линейного программирования

Задача максимизации гарантированного выигрыша первого игрока и задача минимизации гарантированного проигрыша второго игрока сводятся к паре взаимно двойственных задач линейного программирования:

Задача первого игрока	Задача второго игрока

Процесс решения задач упрощается, если перейти к Переменным . Это возможно, если.

Имеем:

Задача первого игрока	Задача второго игрока

Оптимальные стратегии игроков не изменятся, если матрицу игрызаменить на . Цена игры при этом увеличивается на с .

Методы решения задач теории игр во многом зависят от условий задачи и от матрицы А выигрышей первого игрока.

Если матрица А имеет седловую точку, то решение игры сводится к нахождению седловой точки матрицы А. Оптимальные стратегии игроков определяются при этом координатами (i ,j ) седловой точки матрицы А, а цена игры элементом в седловой точке.

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

Итерационный метод.

Разыгрывается мысленный эксперимент, в котором игроки А и В применяют против друг

друга свои стратегии. Эксперимент состоит из последовательности партий. А выбирает стратегию

Аi, игрок В уже знает об этом и отвечает своей стратегией Вj, наиболее выгодной для него в сложившейся ситуации. Далее, первый игрок выбирает дальнейшие стратегии основываясь на предыдущей игре. Таким образом, на каждом шаге итерационного процесса игрок отвечает на шаг другого той своей стратегией, которая является оптимальной относительно всех предыдущих ходов. Если партии продолжать достаточно долго, то средний выигрыш стремится к цене игры, а частоты – к вероятностям оптимальных стратегий. Главным достоинством этого метода является независимость его сложности от размерности игры.

4. Реализация программного средства

Среда разработки: С++ BuilderXE

Язык программирования: C++

4.1 Проектирование

Список модулей с кратким описанием:

1) Mainform.cpp – это главный модуль в котором, реализованы функции: расчёта в чистых стратегиях, сохранение/загрузка и ввод исходных данных .

2) Iter. cpp – это вспомогательный модуль в котором реализован итерационный метод решения матричной игры.

4.2 Листинг программного кода

Модуль Mainform . cpp :

//---------------------------------------------------------------------------

#include <vcl.h>

#pragma hdrstop

#include "Series.hpp"