Проекты

Модуль для поиска решения задачи N×N в теории игр

Работа призёра открытой городской научно-практической конференции «Инженеры будущего» в секции «Информационные технологии, программирование, прикладная математика, социальный инжиниринг» среди работ учащихся 10−11 классов

Направление работы: Программирование
Авторы работы: ГБОУ Школа № 1502
Предметы: Информатика
Классы: 10 класс
Мероприятия: Открытая городская научно-практическая конференция «Инженеры будущего» 2020 года

Актуальность

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

Цель

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

Задачи

1. Выяснить, какой математический аппарат необходим для создания такого рода проекта.

2. Изучить базовые понятия теории игр.

3. Изучить понятие матрицы и основные действия, совершаемые над ней.

4. Применить полученные знания для создания конечного продукта.

Оснащение и оборудование, использованное при создании работы

  • Язык программирования С++

Описание

У каждой платёжной матрицы есть цена игры – средний выигрыш игрока А. Цена игры определяется с помощью принципа максимина (минимакса). Он заключается в том, что мы находим лучшую стратегию для каждого из игроков с учётом того, что их противник действует наихудшим для них образом. Игрок А исходит из того, что игрок В будет использовать свою наиболее выгодную стратегию, которая даст игроку А наименьший выигрыш. Следовательно, в каждой строке необходимо найти минимальный элемент, а среди них найти максимальный, который и будет соответствовать нижней цене игры, то есть максимину. В этот же момент игрок В полагает, что игрок А будет использовать стратегию, которая принесёт ему максимальный выигрыш. Это значит, что чтобы найти верхнюю цену игры, нам надо найти максимум в каждом из столбцов, а затем выделить среди этих значений минимальное. Это и будет соответствовать минимаксной стратегии.

Результаты работы/выводы

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

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

Перспективы использования результатов работы

В дальнейшем планируется создать модули для решения игр M×N различными способами и модули для решения игр 2×2, 2×n, m×2.