Обзор и сравнительный анализ алгоритмов для построения игровых стратегий. Примеры использования генетических алгоритмов для моделирования игровых ситуаций. Анализ стратегии игроков в игре Quarto. Диаграмма классов, используемых в программном коде.
Аннотация к работе
Во многих программных продуктах доминирующую позицию занимают четко формализованные алгоритмы, но в последние годы все большую популярность приобрели системы, работающие с использованием возможностей искусственного интеллекта. Примерно также появились и генетические алгоритмы, функционирование которых основано на теории Дарвина об эволюции живых организмов. Виртуальный соперник, разработанный с использованием такого алгоритма, позволяет заложить в программу элементы случайности, увеличить скорость поиска оптимального решения и выработать более эффективную стратегию поведения. Льюис и Крис Майлс в 2004 использовали генетический алгоритм для подбора параметров бота (члена команды виртуального соперника) в игре Counter-Strike [13]. Шичел применили генетические алгоритмы для создания виртуального соперника для трех игр: нарды, шахматы и Robocode [18].Прежде чем перейти к анализу игры Quarto, необходимо рассмотреть ключевое понятие теории игр - игра. Оскар Моргенштерн и Джон фон Нейман определяли игру как взаимодействие двух и более игроков, основной целью каждого из которых было достижение выигрыша, при этом в ходе игры участники могли распоряжаться какими-либо ресурсами, а также делать ход в зависимости от поведения своих соперников. То есть игра - это своеобразный конфликт, в котором задействованы n игроков, определен способ принятия решений, существуют специальные правила для платежей между игроками [8]. Кооперативными играми называются те игры, где возможно объединение действий двух игроков для достижения общего блага или же выигрыша. Для определения класса игры необходимо сложить выигрыши всех игроков, если она будет равна нулю, то данная игра - это игра с нулевой суммой.Главным событием в разработке компьютерного соперника для игр можно по праву считать игру в шахматы компьютера Deep Blue против чемпиона мира Гарри Каспарова в 1997 году. Первые компьютерные игры для рядового пользователя появились в конце 1960-х и поддерживали лишь игру двух игроков и не содержали искусственного интеллекта. Затем в 70-х появились игры с режимом для одного игрока, там впервые появляется виртуальный соперник. Процедура оценки дерева запускается рекурсивно и продолжает вызов самой себя до тех пор, пока не будет достигнут узел, в котором игрок побеждает, проигрывает, ситуация, когда ни один из игроков не может совершить ход (ничья) [2]. Следуя методу минимакса, для игрока, играющего крестиками, необходимо выбрать ветвь минимизирующую выигрыш соперника и максимизирующую собственный выигрыш, в данном случае это вторая ветвь (рисунок 1.1).Настольная игра Quarto предназначена для двух игроков. Игровое поле представляет поле с 16 кругами (местами для фигур) расположенных в форме квадрата 4х4 (см. рисунок 1.3). В игре существуют 16 фигур, ни одна из которых не повторяется. Фигуры в игре для двух игроков общие, в начале игры они ставятся рядом с полем. Для того чтобы выиграть в данной игре необходимо составить вертикальный или горизонтальный, или диагональных ряд из четырех фигур (рисунок 1.5), обладающих хотя бы одним общим признаком.При этом помимо выбора самой модели генетического алгоритма разработчику так же необходимо решить какие характеристики установить для того или иного параметра алгоритма, а также решить для каждой операции каким методом предпочтительнее пользоваться. Сфера применения данных алгоритмов достаточно широка, следовательно, под каждую конкретную задачу необходимо модифицировать алгоритм для достижения максимальной продуктивности и результативности. Для его устранения был предложен так называемый код Грея, он так же позволяет проводить двоичное кодирование генов особи, но при этом отличия геномов особи в идеале отражены в значении одного бита. Он заключается в том, что родители для следующего поколения выбираются из текущего поколения пропорционально их фитнесу: каждой особи соответствует сектор колеса рулетки, при чем его размер зависит от значения фитнеса у данной особи, то есть чем больше значение функции приспособленности, тем больше сектор. Взяв во внимание все описанные ранее методы отбора особей и их плюсы и минусы, было принято решение сочетать два метода и применять метод рулетки для отбора родительских особей, и элитарную стратегию для повышения эффективности работы и достижения быстрой сходимости метода и небольшого времени работы.Впервые генетические алгоритмы для игр были применены Робертом Аксельродом в 1987 для разрешения «дилеммы заключенного» [11]. До этого момента генетические алгоритмы для моделирования игровых ситуаций использовались совместно с другим инструментом - нейронными сетями. Льюис и Крис Майлс описали опыт применения генетических алгоритмов для настройки ботов в игре Counter-Strike [13]. В своей работе они использовали генетический алгоритм Cross-population selection (CHC) для подбора оптимальных значений параметров для бота. В ходе обучения боты, управляемые генетическим алгоритмом, играли против ботов, настроенных вручную авторами.
План
Оглавление
Введение
Глава 1. Аналитический обзор способов моделирования игровых ситуаций
1.1 Последовательные игры с полной информацией
1.2 Обзор и сравнительный анализ алгоритмов для построения игровых стратегий
1.3 Описание игры Quarto
1.4 Ключевые моменты в процессе разработки генетических алгоритмов
1.5 Примеры использования генетических алгоритмов для моделирования игровых ситуаций
Глава 2. Генетический алгоритм построения выигрышной стратегии для игры Quarto
2.1 Анализ стратегии игроков в игре Quarto
2.2 Кодирование решений
2.3 Описание разработанного генетического алгоритма