Применение методов Монте-Карло для решения задач теории игр

Аннотация 2
ВВЕДЕНИЕ 6
Глава 1 Теоретическое описание скрытых марковских моделей 9
1.1 Обзор работ, связанных с применением методов Монте-Карло для решения задач теории игр 9
1.2 Описание скрытой марковской модели 10
1.3 Постановка задачи и пошаговый алгоритм решения 11
1.4 Описание алгоритмов и инструментарий 14
1.4.1 Алгоритм Баума-Велша 15
1.4.2 Алгоритм Витерби 19
Выводы к первой главе 20
Глава 2 Тестирование методов Монте-Карло для решения задач теории игр 21
2.1 Тестирование на примере игры «Теннис» 21
2.1.1 Вычисление элементов матрицы B 22
2.1.2 Тестирование на данных, представленных в статье 25
2.1.3 Тестирование на данных матрицы B, найденной выше 28
2.1.4 Сравнение с другими подходами решения поставленной задачи 30
2.2 Применение модели к другой игре со схожими характеристиками 33
Выводы ко второй главе 38
ЗАКЛЮЧЕНИЕ 40
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 41
ПРИЛОЖЕНИЕ А Реализация алгоритма Баума-Велша из пакета «HMM» 43
ПРИЛОЖЕНИЕ Б Реализация алгоритма Витерби из пакета «HMM» 46
Купить

Многокритериальная задача - это математическая модель принятия оптимального решения одновременно по нескольким критериям. Эти критерии могут отражать оценки различных качеств объекта (или процесса), по поводу которых принимается решение, или оценки одной и той же его характеристики, но с различных точек зрения. В данной работе под многокритериальными задачами понимаются задачи теории игр.
Математическая теория игр - дисциплина, возникшая на стыке 2 наук: математики и экономики. В настоящее время область её практического применения достаточно широка: политические и дипломатические отношения, биология, информатика и другие. Предметом изучения данной дисциплины являются игры и связанные с ними стратегии (т.е. множества доступных игрокам действий), а целью - выработка методов нахождения оптимальных стратегий. Под игрой, как правило, понимается некоторая конфликтная ситуация, т.е. процесс, в котором принимают участие от двух и более сторон преследующих собственные цели [7].
Основополагающей работой в теории игр является книга Джона фон Неймана и Оскара Моргенштерна «Теория игр и экономическое поведение» (1944) [4]. Большая часть данной книги посвящена играм с нулевой суммой. Игры с нулевой суммой - игры, в которых выигрыш одной стороны равен проигрышу другой. Игры с нулевой суммой с участием 2-х игроков называются антагонистическими. К таким играм также можно отнести игры с постоянной суммой, при которых сумма общего выигрыша всех игроков фиксирована, и поэтому увеличение выигрыша одного из них возможно только за счёт уменьшения выигрышей других игроков.
В конце 1960-х годов Джон Харшаньи ввёл понятие игр с неполной информацией и разработал концепцию байесовских равновесий. Д. Харшаньи рассматривал ситуации, когда у одного игрока нет информации о возможных выигрышах другого игрока, и выигрыши приходится оценивать вероятностно.
Игры принято различать по типу. Например, кооперативные и некооперативные игры, с нулевой суммой и ненулевой суммой, параллельные и последовательные, метаигры, игры с полной или неполной информацией [4, 17]. Последние, с одной стороны, наиболее сложны для построения моделей прогнозирования, с другой - представляют значительный практический интерес, т.к., достаточно часто в реальных конфликтных ситуациях, участники не обладают полной информацией о действиях оппонентов [9, 13, 16].
Для дальнейших рассуждений понадобится следующее определение: ход игрока - это выбор действия из некоторого множества возможных действий игрока, определяемых правилами игры.
В работе рассматриваются игры, включающие в себя следующие элементы.
1. Чередование ходов, которые могут быть как личными, так и случайными.
2. Недостаточность информации.
3. Функция выигрыша [6].
Как уже было отмечено ранее, во многих реальных конфликтных ситуациях участники не обладают всей информацией об истинных состояниях процесса и могут оценивать результаты действий соперников только по некоторым ограниченным наборам данных. В этих условиях принятие решений может зависеть от нескольких факторов, в том числе - случайных. Один из возможных подходов к нахождению оптимальной стратегии в таких задачах это использование для описания исследуемой ситуации вероятностных моделей.
В данной работе используются Скрытые Марковские Модели (СММ) для описания состояний игры в различные моменты времени. СММ зарекомендовали себя как мощное средство обработки данных в самых различных областях, с примерами применения можно ознакомиться в [15]. Преимущества СММ перед другими моделями следующие.
1. СММ обладают простой математический структурой.
2. Структура СММ позволяет моделировать сложную цепочку наблюдений.
3. Параметры модели могут быть автоматически выбраны таким образом, чтобы описать имеющийся набор данных для обучения (под обучением СММ понимается определение оценок параметров модели).
В недавно опубликованной работе [14] был предложен метод нахождения оптимальной стратегии для игры с двумя участниками, основанный на применении СММ. В статье был описан подход к решению стратегических игр, в которых игроки могут менять стратегии в течении игры. Целью было увеличить шансы игрока, т.е. узнать какую стратегию принимает соперник в каждый момент времени. Предложенный подход основан на использовании алгоритма Баума-Велша, решения марковской игры поиска смешанного равновесия Нэша.
В бакалаврской работе данный подход получил развитие: предложен альтернативный метод, основанный на применении алгоритма Витерби для получения цепочки скрытых состояний и выбора наиболее вероятного хода вместо решения марковской игры.
Работа алгоритма иллюстрируется на двух демонстрационных примерах: игры в теннис и игры в «Камень, ножницы, бумага».
Данная работа организована следующим образом. В главе 1 дано теоретическое описание скрытых марковских моделей, а также предложена модель решения игры двух лиц с неполной информацией. В главе 2 тестируется предложенная модель решения по игре, описанной в [14], также алгоритм тестируется по другой игре со схожими характеристиками.
Купить