Описание и программирование матричных игр

x1=1/2x0+1/2 =1/2(1, 0, 0)+1/2(0, 1, 0)=(1/2, 1/2, 0);

c1=1/2c0+1/2 =1/2(0, 1, 2)+1/2(4, 2, 1)=(2, 3/2, 3/2).

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

Итак, пусть x1=(1/2, 1/2, 0),  c1=(2, 3/2, 3/2).

 Найдём множество  индексов  , на которых игрок 1 может получить наименьший выигрыш: , значит, J1={2,3}. Для этих индексов выигрыш равен 3/2. Это есть значение нижней оценки цены игры, т. е. . Заметим, что .

Далее найдём компоненты векторов . Для этого рассмотрим подыгру . В силу симметричности матрицы ее решением будет вектор (1/2, 1/2), т. е. 1/2a1+1/2a2+0a3=

=(4/2, 3/2, 3/2).

Вычислим коэффициент e2. Для этого решим подыгру (2´3): . Стратегии игроков совпадают, поэтому e2=0. В этом случае цена игры совпадает со своим нижним значением, т. е. .  Возвращаемся к предыдущему шагу.

Итак, оптимальной стратегией игрока 1 является x*=x1=(1/2, 1/2, 0) и  .Задача решена.

На первый взгляд алгоритм практически трудно реализовать, так  как не известно, какого размера  будет получена матрица для подыгры ГN. Но на самом деле с вероятностью 1 на каждом шаге придётся решать подыгру размера не больше чем m´2.[9]

Инженерами-программистами алгоритм был реализован на языке  программирования Фортран-IV. Вычислительные эксперименты, проведённые на ЭЦВМ ЕС-1030, показали,  что для игр размерности от 25´25 до 100´100, элементы, матрицы выигрышей которых были заполнены случайными числами, алгоритм позволяет найти искомое приближение за 100-1000 итераций, причём их число слабо зависит от размера матрицы. Для решения одной задачи машина затрачивает не дольше 8 минут. Ими же были разработаны различные модификации алгоритма. [9]

 

6. Конструкторская часть

6.1 Разработка архитектуры программной системы

 

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

Для реализации "такой-то программы" была выбрана среда  программирования Nokia QT версии 4.5.0 фирмы Nokia, так как она предоставляет наиболее широкие возможности для программирования приложений для различных платформ.

С++ – это язык для  быстрого создания приложений. Высокопроизводительный инструмент визуального построения приложений включает в себя настоящий компилятор кода и предоставляет средства визуального программирования, несколько похожие на те, что можно обнаружить в Microsoft Visual Basic или в других инструментах визуального проектирования. В QT также входят локальные библиотеки для работы с базами данных, библиотеки визуальных компонентов, и прочее хозяйство, необходимое для того, чтобы чувствовать себя совершенно уверенным при профессиональной разработке информационных систем или просто кросплатформеных приложений.

Прежде всего, QT c++ предназначен для профессиональных разработчиков, желающих очень быстро разрабатывать. QT cодержит большой набор компонентов и классов, поэтому в QT должны быть прежде всего заинтересованы те, кто разрабатывает продукты на продажу. С другой стороны небольшие по размерам и быстро исполняемые модули означают, что требования к клиентским рабочим местам существенно снижаются – это имеет немаловажное значение и для конечных пользователей.

Преимущества С++ по сравнению  с аналогичными программными продуктами.

• быстрота разработки приложения;
• высокая производительность разработанного приложения;
• низкие требования разработанного приложения к ресурсам компьютера;
• наращиваемость за счет встраивания новых компонент и инструментов в среду C++;
• возможность разработки новых компонент и инструментов собственными средствами QT (QT поставляется с полным исходным кодом);
• удачная проработка иерархии объектов.

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

К тому же работодателей  интересует, прежде всего, скорость и  качество создания программ, а эти  характеристики может обеспечить только среда визуального проектирования, способная взять на себя значительные объемы рутинной работы по подготовке приложений, а также согласовать деятельность группы постановщиков, кодировщиков, тестеров и технических писателей. Возможности QT C++ полностью отвечают подобным требованиям и подходят для создания систем любой сложности.

 

В приложении приведена  реализация итеративного метода Брауна-Робинсона решения матричных игр в среде программирования QT 4.5.0 для платформы win32, на языке C++.

Пользователь вводит матрицу выигрышей размера  , где , .

Далее машина запрашивает информацию о том, кто из игроков начинает игру, какую стратегию он выбирает и количество итераций.

Во второй таблице  выводятся результаты разыгрывании игры за определённое число итераций.

6.2 Разработка структуры данных

Матрица, вводимая пользователем, будет записываться в динамически создаваемый массив типа int(целочисленный): int **array. Параметры, задаваемые пользователем в ходе работы программы будут храниться в классовых переменных. Результаты расчета программы будут заноситься в двумерные массивы(win_plone[150][10], win_pltwo[150][10]), после чего выводиться в организованном виде в таблице.

6.3 Разработка программного алгоритма

В программном модуле будет три основные функции: функция определения следующего хода для первого игрока (PlayerOne()), функция определения следующего хода для второго игрока (PlayerTwo) и функция решения матричной игры итерационным методом Брауна-Робинсона (реакция на нажатие кнопки StartBtn).

1. Размерность матрицы( )
2. Пользователь ввел матрицу.
3. Проверить, не являются ли все введенные элементы нулями?
4. Если все элементы равны нулям, вывести сообщение и не продолжать работу.
5. Найти минимальный элемент матрицы.
6. Проверить наличие отрицательных элементов в матрице пользователя.
7. Если есть отрицательные элементы, вычесть из них минимальный элемент, перезаполнить матрицу.
8. Какой игрок ходит первым?
9. Если первым ходит первый игрок, перейти к шагу 10, иначе к шагу 13
10. Сформировать матрицу выигрышей первого игрока.
11. Сформировать матрицу выигрышей второго игрока.
12. Перейти к шагу 15
13. Сформировать матрицу выигрышей второго игрока.
14. Сформировать матрицу выигрышей первого игрока.
15. Вывести информацию о выигрышах игроков на экран в виде таблицы.

 

 

 

Рисунок 1. Блок схема работы функции ‘PlayerOne’

 

Рисунок 2. Блок схема работы функции ‘PlayerTwo’

 

 

Рисунок 3. Блок схема работы основной программы

 

6.3 Организация интерфейса

 

Рисунок 4. Проектирование формы.

 

Основные компоненты и их назначение:

1. tableWidget – компонент таблица, предназначен для ввода пользовательской матрицы.
2. spinBox – компонент счетчик, предназначен для изменения количества строк таблицы tableWidget.
3. spinBox_2 - компонент счетчик, предназначен для изменения количества столбцов таблицы tableWidget.
4. player1, player2 – компоненты переключатели, устанавливают, какой игрок первым начинает ходить.
5. strateg – компонент текстовое поле, в него вводится выбранная игроком начальная стратегия.
6. iteration - компонент текстовое поле, в нем указывается количество итераций(выполняемых шагов).
7. startBtn – компонент кнопка, при нажатии начинает приближенное решение матричной игры методом Брауна-Робинсона.
8. defArrayBtn - компонент кнопка, при нажатии устанавливает значения таблицы tableWidget в значения по умолчанию(как при запуске программы).
9. outTable - компонент таблица, предназначен для вывода решений.

 

Для более приятного диалога с программой был использован интерфейс под названием «Plastique», использованный в операционной системе «Kubuntu».

 

Для более удобного использования  компоненты сгруппированы на панелях с заголовками.

 

Рисунок 5. Сравнение программы со стандартным оформлением и с оформлением «Plastique»

 

7. Экспериментально – прикладная  часть

7.1. Руководство программиста

Для написания программы были использованы библиотеки Nokia QT версии 4.5.0 скомпилированные и настроенные на платформу win32 операционной системы Windows.

Программа базируется на типе проекта «GUI приложение QT» (рис. 7.1), и использованными стандартными модулями.

Рисунок 7.1. Создание проекта.

 

На форме расположены  необходимые для работы программы  компоненты. Основные использованные классы компонентов:

• QMainWindow
• QWidget
• QToolBox
• QFrame
• QGroupBox
• QPushButton
• QLabel
• QSpinBox
• QTableWidget
• QRadioButton
• QLineEdit
• QTextBrouser
• QStatusBar

 

Рисунок 7.2. Иерархия расположения компонентов на форме.

 

Main.cpp:

 

#include <QtGui/QApplication>

#include <QWindowsVistaStyle>

#include <QFile>

#include "mainwindow.h"

 

int main(int argc, char *argv[])

{

    QApplication a(argc, argv);

 

    /*

        Загрузка таблицы стилей

    */

    QFile file(".\\style.txt");

    if(file.open(QIODevice::ReadOnly))

    {

        QByteArray line;

        while (!file.atEnd())

               line += file.readLine();

 

        //Применение таблицы стилей

        a.setStyleSheet(QString::fromLocal8Bit(line));

    }

    MainWindow w;

    w.show();

    return a.exec();

}

 

mainwindow.h:

 

#ifndef MAINWINDOW_H

#define MAINWINDOW_H

 

#include <QMainWindow>

#include "windows.h"

#include "QWindowsVistaStyle.h"

 

namespace Ui {

    class MainWindow;

}

 

class MainWindow : public QMainWindow {

    Q_OBJECT

public:

    MainWindow(QWidget *parent = 0);

    ~MainWindow();

 

protected:

    void changeEvent(QEvent *e);

 

private:

    int **array;//матрица пользоателя

    int m, n;//размерность матрицы пользователя

    bool nol;//Все элеметы равны 0?

    bool otr;//Наличие отрицательных элементов

    int min, max;//Минимальный и максимальный элементы

    DWORD win_plone[150][10], win_pltwo[150][10];//Массивы для выигрышей игроков 1 и 2

    int a;//Счетчик итераций

    int pl;//Игрок

    short st,st1,st2;//Стратегии

    short kl;//Количество  итераций

    int PlayerOne();

    int PlayerTwo();

    void setOutTblItem(int row, int col, QString text);

    Ui::MainWindow *ui;

private slots:

    void StartBtn();

    void SetDefArray();

    void UpdateTableRows(int value);

    void UpdateTableColumn(int value);

};

#endif // MAINWINDOW_H

 

mainwindow.cpp:

 

#include "mainwindow.h"

#include "ui_mainwindow.h"

#include "QMessageBox.h"

 

MainWindow::MainWindow(QWidget *parent) :

    QMainWindow(parent),

    ui(new Ui::MainWindow)

{

    //Инициализация  графического интерфейса

    ui->setupUi(this);

 

    /*

      Установка  количества строк и столбцов  таблицы

    */

    this->ui->tableWidget->setRowCount(3);

    this->ui->tableWidget->setColumnCount(3);

 

    /*

      Установка  начальных значений для счетчиков

    */

    this->ui->spinBox->setValue(3);

    this->ui->spinBox_2->setValue(3);

 

    QHeaderView *h = new QHeaderView(Qt::Horizontal);

    h->setDefaultSectionSize(50);

    this->ui->tableWidget->setHorizontalHeader(h);

 

    //Активна вкладка  "Программа"

    this->ui->toolBox->setCurrentIndex(0);

 

    //Заполнение матрицы значениями по умолчанию

    this->SetDefArray();

 

    //Загрузка стартовой страницы справки

    this->ui->textBrowser->setSource(QUrl(QString("qrc:/help/index.html")));

 

    //Подключение событий

    this->ui->spinBox->connect(this->ui->spinBox, SIGNAL(valueChanged(int)), this, SLOT(UpdateTableRows(int)));

    this->ui->spinBox_2->connect(this->ui->spinBox_2, SIGNAL(valueChanged(int)), this, SLOT(UpdateTableColumn(int)));

    this->ui->defArrayBtn->connect(this->ui->defArrayBtn, SIGNAL(clicked()), this, SLOT(SetDefArray()));

    this->ui->startBtn->connect(this->ui->startBtn, SIGNAL(clicked()), this, SLOT(StartBtn()));

 

}

 

MainWindow::~MainWindow()

{

    delete ui;

}

 

void MainWindow::changeEvent(QEvent *e)

{

    QMainWindow::changeEvent(e);

    switch (e->type()) {

    case QEvent::LanguageChange:

        ui->retranslateUi(this);

        break;

    default:

        break;

    }

}

 

void MainWindow::SetDefArray()

{

    short a[3][3] =

    {

        {0,4,2},

        {3,1,0},

        {1,2,3}

    };

 

    this->ui->tableWidget->setRowCount(3);

    this->ui->tableWidget->setColumnCount(3);

 

    for(int i = 0; i < 3; i++)

        for(int j = 0; j < 3; j++)

        {

            QTableWidgetItem *item = new QTableWidgetItem(0);

            QString s;

            item->setText(s.setNum(a[i][j], 10));

            this->ui->tableWidget->setItem(i, j, item);

        }

}

 

void MainWindow::setOutTblItem(int row, int col, QString text)

{

    QTableWidgetItem *item = new QTableWidgetItem(0);

    item->setText(text);

    item->setTextAlignment(Qt::AlignHCenter | Qt::AlignVCenter);

    item->setFlags(Qt::ItemIsSelectable | Qt::ItemIsEnabled);

    this->ui->outTable->setItem(row, col, item);

}

 

void MainWindow::UpdateTableRows(int value)

{

    this->ui->tableWidget->setRowCount(value);

}