Введение 3
Постановка задачи 5
Обзор литературы 6
Глава 1. Базовые понятия теории игр 8
Глава 2. Алгоритмы контрфактической минимизации сожалений 11
Глава 3. Практическая часть 17
Вывод 33
Заключение 34
Список литературы 35
Математические модели все чаще используются социологами, экономистами и аналитиками для моделирования реальных процессов в обществе и последующего их анализа. Одними из таких моделей являются модели принятия решений в условиях, когда имеются две и более конкурирующих стороны.
Теория игр - это прикладной раздел математики, исследующий модели принятия решений в условиях конфликта. Изучая эти модели и применяя их на практике, можно оптимизировать многие процессы в экономике, а также предотвращать чрезвычайные ситуации. Так, на-пример, по мнению Л. А. Петросяна и Н. А. Зенкевича, отсутствие исследований в области теории игр привело к финансовому кризису [10].
В 2000 году Харт и Мас-Колелл представили важный для теории игр алгоритм - “Regret matching” [7]. Игроки достигают равновесной игры, отслеживая сожаления за предыдущие игры и действуя в дальнейших раундах пропорционально накопленным положительным сожалениям.
Техника не только проста и интуитивна, она произвела революцию в компьютерном решении некоторых самых сложных игр с блефом. В частности, все побеждавшие с тех пор на ежегодных соревнованиях по компьютерному покеру программы основывались на ней [8].
Игры с несовершенной информацией моделируют стратегические взаимодействия между множеством агентов или игроков, обладающих частичной информацией. Они широко применяются в различных сферах жизни: в переговорах, аукционах, в кибербезопасности. Как правило, в таких играх каждый хочет найти приблизительное равновесие, при котором ни один игрок не сможет улучшить свой результат, отклонившись от равновесия в одиночку.
Контрфактическая минимизация сожаления - самый популярный алгоритм решения антагонистических игр с двумя игроками в развернутой форме с несовершенной информацией и достигает результатов на уровне развития области.
Существует несколько модификаций данного алгоритма, отличающихся скоростью сходимости. Данная работа посвящена исследованию этих модификаций.
Постановка задачи
Целью работы является изучение, реализация и сравнительный анализ алгоритмов контрфактической минимизации сожаления в играх с неполной информацией на примере игры Дудо.
Для достижения цели были поставлены следующие задачи:
1. Реализовать CFR с семплингом Монте-Карло.
2. Реализовать “Vanilla CFR” в векторной форме.
3. Реализовать CFR+ в векторной форме.
4. Реализовать семейство алгоритмов “Discounted CFR” в векторной форме.
5. Проведение сравнительного анализа эффективности реализованных алгоритмов.
В результате работы над ВКР были решены следующие задачи:
1. Реализован CFR с семплингом Монте-Карло.
2. Реализован “Vanilla CFR” в векторной форме.
3. Реализован CFR+ в векторной форме.
4. Реализовано семейство алгоритмов “Discounted CFR” в векторной форме.
5. Проведен сравнительный анализ эффективности реализованных алгоритмов.
