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

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

Таким образом, в данной работе:
1) представлен алгоритм решения частных случаев стохастической игры с отсутствием полной информации;
2) использованы СММ (скрытые марковские модели) в качестве инструмента описания данного процесса (стохастической игры);
3) проведён обзор литературы на близкие темы;
4) изучены алгоритмы Баума-Велша и Витерби как инструмент решения задач, описанных СММ.
Предложенный алгоритм был протестирован на гипотетическом примере игры в «теннис», описанном в [14]. Результаты выполнения алгоритма, предложенного в данной работе, оказались лучше результатов, представленных в [14].
Было проведено сравнение результатов работы предложенного алгоритма с результатами применения других подходов к решению поставленной задачи. В качестве альтернативных подходов были взяты следующие: использование равномерной стратегии игроком и выбор последнего хода противника. Было рассмотрено 4 случая СММ противника (комбинаций почти равномерных и неравномерных матриц А и В). В каждом из случаев предложенный алгоритм отработал лучше, чем альтернативные подходы.
Предложенный алгоритм был протестирован на произвольных данных другой игры со схожими характеристиками: «камень, ножницы, бумага». В ходе экспериментов алгоритм показал высокую эффективность работы алгоритма, что подтверждает возможность использования предложенного алгоритма в любой игре со схожими характеристиками.
Возможные направления дальнейшей деятельности:
• применение алгоритма к играм с большим количеством игроков;
• адаптация и применение других подходов к решению такого класса игр.
Купить