Равновесие по Нэшу - Программа построения равновесных стратегий для игры
В теории игр равновесием по Нэшу называется ситуация при который ни один из игроков не может увеличить свой выигрыш, в одностороннем порядке меняя свое решение. Допустим - игра n лиц в нормальной форме, где - набор чистых стратегий, а - набор выигрышей. Когда каждый игрок выбирает стратегию в профиле стратегий, игрок получает выигрыш. Профиль стратегий является равновесным по Нэшу, если изменения своей стратегии с на не выгодно ни одному игроку, то есть для любого :
В 1951 году Д. Нэш в своей работе по некорпоративным играм доказал, что в любой конечной игре будет существовать хотя бы одно равновесие в чистых или смешанных (то есть при выборе чистой стратегии стохастический с фиксированной частотой) стратегиях. Так как игра Omaha в модели Jam-Fold является конечной, то в ней будет существовать хотя бы одно равновесие по Нэшу.
Существует несколько методов нахождения равновесия по Нэшу в игре. В основном они основываются на работе с матричным представлением игры. Но так как у решаемой нами игры огромное количество чистых стратегий, использовать ее матричное представление проблематично. Для поиска равновесия Нэша в данной игре хорошо подойдет метод фиктивного разыгрывания. Суть этого метода в том, что для каждого игрока находится оптимальная чистая стратегия против смешанной стратегии соперника, потом эта стратегия добавляют в смешанную стратегию игрока. В 1951 году было доказано, что в антагонистической игре для двух игроков при многократном повторении этого алгоритма смешанные стратегии игроков будут стремится к равновесию по Нэшу [13]. Таким образом с помощью этого метода за конечное число итераций возможно найти равновесие по Нэшу в заданной игре.
Для того что бы определить оптимальную стратегию игрока A против стратегии игрока B, нам необходимо найти множество играемых кластеров карт для которых математическое ожидание игры против стратегии игрока B будет больше ноля:
, где
- множество кластеров начальных комбинаций при которых стратегия игрока A будет играть AllIn,
- множество кластеров начальных комбинаций при которых стратегия игрока B будет играть AllIn,
- множество кластеров возможных начальных комбинаций,
- множество исходов при вскрытии карт у двух игроков,
- множество выигрышей при конкретных исходах,
- множество вероятностей начальных комбинаций двух игроков,
- таблица предрасчетных данных.
Таким образом в самом худшем случае нам понадобится не более вариантов перебора.
Похожие статьи
-
Стратегии - Программа построения равновесных стратегий для игры
Так как игра случайная, платежная матрица будет состоять из математических ожиданий возможных сочетаний стратегий. Стратегия в данной игре определяет...
-
Интерпретация полученных результатов - Программа построения равновесных стратегий для игры
При изучении равновесных стратегий в модели jam-fold для двоих игроков можно заметить тот факт, что стратегии зависят только от соотношения...
-
Модель Jam-Fold - Программа построения равновесных стратегий для игры
Модель Jam-Fold подразумевает, что в раунде торговли на этапе "Пре-флоп" каждый игрок может сделать только одно из двух действий: Fold - отказаться от...
-
Введение - Программа построения равновесных стратегий для игры
Игра стратегия математический С появлением компьютеров широкое развитие получила тема искусственного интеллекта. Одним из направлений искусственного...
-
Эквиляторы для игры Omaha - Программа построения равновесных стратегий для игры
Эквилятор - это программа для расчета распределения исходов в случае вскрытия. Распределение исходов вскрытия является основной частью в расчете...
-
Обзорная часть - Программа построения равновесных стратегий для игры
Правила игры Omaha Перед тем как описывать правила игры, внесем несколько определений терминов игры. Колода карт -- это полный набор прямоугольных или...
-
Заключение - Программа построения равновесных стратегий для игры
В настоящие время популярность игры Omaha растет. Постепенно появляется все больше регулярных турниров по этой игре на сайте Pokerstars. net. При этом...
-
При заполнения каждой ячейки таблицы распределения исходов сравнения двух рук нам необходимо перебрать все возможные варианты общих карт. Таким образом...
-
Алгоритм для определения силы комбинации - Программа построения равновесных стратегий для игры
В играх типа Omaha для определения силы комбинации необходимо учитывать 9 карт: 4 стартовых карты игрока и 5 общих карт. По стандартным правилам покера...
-
Расчет равновесия по Нэшу - Программа построения равновесных стратегий для игры
В рамках данной ВКР была создана программа для расчета равновесных стратегий с помощью метода фиктивного разыгрывания. Благодаря использованию...
-
Обзор калькуляторов для покера - Программа построения равновесных стратегий для игры
Как правило под покерным калькулятором подразумевают программу которая позволяет рассчитать математическое ожидание действия в заданной ситуации....
-
Расчет таблицы - Программа построения равновесных стратегий для игры
В ходе разработки программы, для эффективной работы основного алгоритма программы будет понадобилось рассчитать некоторые предрасчетные данные. Для этого...
-
Классы StatMetric содержат всю логику библиотеки и предоставляют интерфейс для обновления и получения значений агрегатов. Рисунок 4. Диаграмма классов...
-
Целостность, Миграция - Программа расчета агрегатов по накапливающимся данным для построения отчетов
Еще одна возможная проблема -- целостность данных. Если приложение не уведомит Библиотеку об изменении данных, то ошибка останется в агрегате навсегда....
-
Предлагаемая библиотека хранит все данные в отдельных таблицах, таким образом он не обязан использовать ту же СУБД, что и основное приложение. В качестве...
-
Требования к программе, Описание задания, Описание игры и ее правил - Разработка игры "Морской бой"
Данная программа предназначена для работы под управлением операционных систем Windows 98, Windows ME, Windows 2000, Windows XP, Windows 7. Для корректной...
-
Реализация, Composer - Программа расчета агрегатов по накапливающимся данным для построения отчетов
Для эффективного тестирования и демонстрации библиотеки было решено разработать PHP-приложение, состоящее из: 1. Менеджера зависимостей composer; 2....
-
Рисунок 1. Пример сложной схемы БД Пример проблемной ситуации, которую этот проект должен разрешить представлен на рис. 1. Организатор проводит события...
-
Методология Все тесты будут необходимо провести на разных размерах базы данных, чтобы увидеть, как классические JOINы скалируются в сравнении с...
-
Концепция построения программы Список всех классов приведен на рисунке 3.1. Рисунок 3.1 - Диаграмма классов программы В качестве главного класса...
-
Модель данных - Программа расчета агрегатов по накапливающимся данным для построения отчетов
В файле dist/schema/schema. yaml (см приложение А) была описана схема будущей базы данных, по которой при помощи Doctrine были сгенерированы пустые...
-
Введение - Программа расчета агрегатов по накапливающимся данным для построения отчетов
Бесчисленное количество веб-приложений полагается на базы данных. Нередко архитектура этих баз данных недальновидна с самого начала, а постоянно...
-
ВВЕДЕНИЕ - Разработка программы на языке C++, реализующей игру "Морской бой"
Данная курсовая работа направлена на изучение принципов объектно-ориентированного программирования. Разработать программу на языке C++, реализующую игру...
-
Ожидается, что предлагаемая библиотека даст большой прирост в производительности операций чтения, заполнив собственную нишу среди решений проблем...
-
Анализ фильма "Опасные игры" - Encounter как способ игрового освоения пространства
Фильм вышел на первом канале в 2010 году. Режиссером, указанным в информации о фильме является - ОАО "Первый канал"_ Документальное кино: [Электронный...
-
Для замеров производительности использовалось три запроса, представляющих три наиболее типичные проблемные рассчеты. Ниже приведены эти запросы на языке...
-
База данные кеширование денормализация Предлагаемое решение -- скомбинировать некоторые идеи кеширования и денормализации в специальной библиотеке...
-
MapReduce, Кеш - Программа расчета агрегатов по накапливающимся данным для построения отчетов
MapReduce -- модель распределенных вычислений, используемая для параллельных вычислений над большими объемами данных в кластерах. MapReduce позволяет...
-
Сеть Петри это двудольный направленный граф с маркировкой, ребра которого задают причинно-следственные отношения "события-условия" и именуются дугами....
-
Обзор протокола Multi-Touch технологий передачи данных TUIO [7] - основной кроссплатформенный протокол с открытым исходным кодом Multi-Touch передачи...
-
Стек технологий При выборе стека технологий основное внимание уделялось следующим факторам, в порядке убывания значимости: § Кроссплатформенность; §...
-
Описанный метод, по сути, анализирует поведение веб-приложения на предмет совершения недопустимых относительно профиля нормального поведения операций....
-
ЗАКЛЮЧЕНИЕ - Разработка программы на языке C++, реализующей игру "Морской бой"
В данной курсовой работе была разработана игра "Морской бой". В программе использовались классы, наследование, виртуальные методы. В качестве языка...
-
При разработке практически всех инструментальных средств за основу принимается методология автоматизации проектирования на базе использования прототипов....
-
Множество D с двумя заданными на нем операциями (плюс) и (умножение) называется диоидом, если выполнены следующие аксиомы: § Ассоциативность. §...
-
Рассмотрим замкнутую сеть массового обслуживания с разнотипными заявками, которая является вероятностной моделью обслуживания заявок в УП "Проектный...
-
Обоснование выбранного метода При дизайне системы согласно требованиям или при оптимизации существующей необходимо ввести модель, позволяющую не только...
-
Введение - Разработка программы для реализации редактора временных графов синхронизации
Математическое моделирование дискретно-событийных динамических систем является относительно молодым направлением науки теории управления. Разработка...
-
Принцип построения помехоустойчивых кодов - Кодек каскадного кода Хэмминга
Помехоустойчивое кодирование представляет собой процесс преобразования передаваемых информационных символов по определенному алгоритму, и в результате...
-
Заключение, Источники - Программа расчета агрегатов по накапливающимся данным для построения отчетов
Расчет агреатов в сложных базах данных -- ресурсоемкая задача. Известные способы сокращения времени ответа запросов не всегда приемлемы, что поднимает...
Равновесие по Нэшу - Программа построения равновесных стратегий для игры