Разработка и программная реализация

Размещено на http://www.allbest.ru/

Оглавление

Введение

Глава 1. Аналитический обзор способов моделирования игровых ситуаций

1.1 Последовательные игры с полной информацией

1.2 Обзор и сравнительный анализ алгоритмов для построения игровых стратегий

1.3 Описание игры Quarto

1.4 Ключевые моменты в процессе разработки генетических алгоритмов

1.5 Примеры использования генетических алгоритмов для моделирования игровых ситуаций

Глава 2. Генетический алгоритм построения выигрышной стратегии для игры Quarto

2.1 Анализ стратегии игроков в игре Quarto

2.2 Кодирование решений

2.3 Описание разработанного генетического алгоритма

2.4 Тестирование разработанного алгоритма

Заключение

Библиографический список

Приложения

алгоритм моделирование игровой quarto



Введение

Для разработки современных программ широко применяются различные алгоритмы. Во многих программных продуктах доминирующую позицию занимают четко формализованные алгоритмы, но в последние годы все большую популярность приобрели системы, работающие с использованием возможностей искусственного интеллекта. Основными причинами роста популярности систем с искусственным интеллектом являются гибкость, возможность к адаптации, снижение времени, затраченного на принятие решений.

Искусственный интеллект во многом повторяет процессы, происходящие в природе. Нейронные сети, созданные по принципу работы человеческого мозга, - одно из направлений в области искусственного интеллекта. Примерно также появились и генетические алгоритмы, функционирование которых основано на теории Дарвина об эволюции живых организмов. Генетические алгоритмы представляют собой адаптивные методы поиска. Они применимы для задач оптимизации и моделирования, так как позволяют быстрее отыскать точное или близкое к точному решение, в отличие от стандартных методов перебора и поиска среди множества всех существующих решений. Область применения генетических алгоритмов достаточно обширна: проектирование жестких конструкций, определение оптимального размещения деталей, управление загрузкой многопроцессорных компьютеров, решение транспортных задач.

Генетические алгоритмы применяются и в игровой индустрии. Виртуальный соперник, разработанный с использованием такого алгоритма, позволяет заложить в программу элементы случайности, увеличить скорость поиска оптимального решения и выработать более эффективную стратегию поведения. В связи с этим применение такого алгоритма дает возможность более точно имитировать игру реального человека. Николас Коул, Сушил Дж. Льюис и Крис Майлс в 2004 использовали генетический алгоритм для подбора параметров бота (члена команды виртуального соперника) в игре Counter-Strike [13]. Параметры включали в себя оружие (какое лучше выбрать), уровень агрессии, траекторию движения (какой путь предпочтительнее), стиль игры. В 2007 году М. Сиппер, Я. Азариа, Э. Хауптман и Й. Шичел применили генетические алгоритмы для создания виртуального соперника для трех игр: нарды, шахматы и Robocode [18]. Разработанный соперник довольно часто обыгрывал человека.

В данной работе особенности генетических алгоритмов будут использованы в качестве основы для поиска выигрышной стратегии для настольной игры Quarto. Игра предназначена для двух игроков, которые ходят по очереди. Она напоминает всем знакомую игру «Крестики-Нолики». В ней присутствуют 16 различных фигур, отличающихся по четырем признакам: высота, цвет, форма, наличие выемки, а также квадратное игровое поле 4х4. Возможны три исхода игры: победа первого игрока, победа второго игрока или ничья. Игрокам необходимо собрать ряд из четырех фигур, обладающих хотя бы одним общим признаком. Кто первым построит игровую комбинацию, где присутствует такой ряд, тот и выигрывает. Игра закачивается максимум после 16 ходов. На сегодняшний день недостаточно изучено, как выстроить выигрышную стратегию в игре Quarto, что и стало проблемой исследования. Чтобы создать генетический алгоритм для поиска выигрышной стратегии в игре Quarto необходимо рассмотреть методы, применяемые в играх для создания виртуального соперника.

Объект данного исследования - применение генетических алгоритмов для моделирования игровых ситуации.

Предметом данной работы является генетический алгоритм построения выигрышной стратегии для игры Quarto.

Целью данного исследования является разработка и реализация генетического алгоритма поиска выигрышной стратегии для игры Quarto. Для достижения данной цели необходимо решить следующие задачи:

Выполнить обзор алгоритмов, применяющихся в моделировании игр.

Выявить преимущества применения генетических алгоритмов.

Провести анализ игры Quarto и стратегий ее игроков.

Разработать и реализовать генетический алгоритм построения выигрышной стратегии для игры Quarto.

Выполнить тестирование созданного программного продукта.

Провести сравнительный анализ «рандомного» алгоритма и разработанного генетического алгоритма.



Глава 1. Аналитический обзор способов моделирования игровых ситуаций

1.1 Последовательные игры с полной информацией

Для анализа и моделирования игровых ситуаций целесообразно рассматривать поставленную задачу с точки зрения теории игр. На сегодняшний день область применения теории игр достаточно обширна: начиная от экономики и военного дела, заканчивая биологией. Основы данной науки были заложены Джоном фон Нейманом и Оскаром Моргенштерном в 1944 году. Хотя их работа больше затрагивала экономический аспект деятельности человека, постепенно данная наука получила свое распространение и на другие сферы деятельности человека.

Теория игр - это раздел математики, в котором исследуются математические модели принятия решений в условиях конфликта, т. е. в условиях столкновения сторон, каждая из которых стремится воздействовать на развитие конфликта в своих собственных интересах [6]. С помощью данной науки можно провести анализ не только экономического поведения человека, но и его стратегий поведения в традиционных играх, таких как шахматы, карточные игры, волейбол и многие другие. Следовательно, рассматриваемую в данной работе настольную игру Quarto возможно проанализировать с точки зрения теории игр.

Прежде чем перейти к анализу игры Quarto, необходимо рассмотреть ключевое понятие теории игр - игра. Оскар Моргенштерн и Джон фон Нейман определяли игру как взаимодействие двух и более игроков, основной целью каждого из которых было достижение выигрыша, при этом в ходе игры участники могли распоряжаться какими-либо ресурсами, а также делать ход в зависимости от поведения своих соперников. Данное определение кажется достаточно полным, однако впоследствии оно было расширено Джоном Нэшем и стало включать в себя понятия кооперативных игр и игр, где выигрыш не является константой. То есть игра - это своеобразный конфликт, в котором задействованы n игроков, определен способ принятия решений, существуют специальные правила для платежей между игроками [8].

Существует множество классификаций игр по различным основаниям. Рассмотрим некоторые из них. Первый самый простой способ - это разделение игр по количеству игроков: один, двое или же несколько участников. Например, шахматы игра для двоих, а в настольную игру «Монополия» можно играть двум и более участникам.

Второй тип классификация игр по виду взаимодействия игроков: кооперативные (коалиционные) и некооперативные (бескоалиционные). Кооперативными играми называются те игры, где возможно объединение действий двух игроков для достижения общего блага или же выигрыша. В некоторых играх при кооперации выигрыши игроков увеличиваются. Следует отметить, что к данному типу игр не будут относиться игры, в которых участники объединяются в коалиции, но каждый из них преследует свою собственную цель. К коалиционным играм можно отнести многим знакомые настольные игры «Activity» и «Alias», а к бескоалиционным - «Монополию».

Различают параллельные и последовательные игры. В последовательных играх игроки ходят поочерёдно в установленном порядке, а в параллельных играх игроки ходят одновременно. К последовательным относятся, например, такие игры, как шахматы, шашки, домино. Волейбол, футбол, баскетбол относятся к параллельным играм.

Игры могут быть отличны по количеству стратегий: существуют конечные и бесконечные игры. Если у всех игроков конечное число стратегий, то такая игра конечная, иначе - игра бесконечная [8].

Классификация по размеру выигрышей предполагает игры с нулевой и ненулевой суммой. Для определения класса игры необходимо сложить выигрыши всех игроков, если она будет равна нулю, то данная игра - это игра с нулевой суммой. К данному классу можно отнести покер, где ставки делают все, а выигрыш забирает лишь один из игроков. Следовательно, если мы сложим убыток каждого из проигравших с выигрышем победителя, получим ноль. Подвидом игр с нулевой суммой является антагонистические игры, в данных играх участвуют 2 игрока, которые не составляют коалиций. В антагонистических играх интересы игроков диаметрально противоположны. К таким играм можно отнести шашки, шахматы. Если обратиться к играм с ненулевой суммой, то выигрыш одного из игроков не означает проигрыш всех остальных участников игры, сумма игры может быть, как больше, так и меньше нуля. Так же такие игры больше приближены к реальности, ведь зачастую интересы людей не кардинально разные, в каких-то моментах они пересекаются, отсюда и возникает дополнительный выигрыш при, например, кооперации. Отрицательная сумма может возникнуть при не равном соотношении ресурсов, затрачиваемых на игру, с полученным выигрышем. К такому типу игр относятся лотереи, ведь зачастую призовой фонд (выигрыш) не равен стоимости всех выпушенных и купленных билетов.

По равноправности ходов различают симметричные и несимметричные игры. Игра будет симметричной тогда, когда сумма игры равна нулю и каждый из игроков имеет равные возможности, использование которых приводит к одинаковому результату [7]. Если игроки встанут на места друг друга, поменяют очередность совершения хода, то в игре ничего не изменится. А в несимметричных играх при таком же действии игра меняется, ведь в них соперники играют по разным правилам.

По количеству ходов различают одноходовые и многоходовые игры. Подвидом многоходовых игр являются позиционные игры, в которых несколько игроков ходят друг за другом и выигрыш зависит от порядка совершаемых ходов. К такому типу игр можно отнести карточные игры, шашки и шахматы.

Информированность игроков так же может представлять собой основание для классификации игр. Существуют игры с полной информацией и с неполной информацией, с совершенной и не совершенной информацией. В игре с совершенной информацией на каждом шаге игрокам известно, какие ходы были сделаны ранее [8]. Для того чтобы игра относилась к первому виду необходимо чтобы: во-первых, чтобы она являлась игрой со совершенной информацией, а также были бы известны все позиции соперников; порядок ходов определен правилами заранее и не зависит от случайных величин. Эти же игры являются последовательными, ведь в параллельных играх полная информация не доступна всем игрокам. В качестве примера игр с полной информацией можно привести крестики-нолики, шахматы, шашки. В игре с несовершенной информацией хотя бы один из игроков не знает полностью, как до этого момента развивалась игра, например, не осведомлен о ходе своего соперника [9]. А в неполных играх недостаточная информированность некоторых игроков может возникнуть еще до начала игры. К играм с неполной информации относятся некоторые карточные игры, маджонг, нарды.

Охарактеризуем рассматриваемую в данной работе настольную игру Quarto с точки зрения приведенных выше классификаций. Данная игра предназначена для двух игроков. Кооперация игроков не имеет смысла в данной игре, ведь если выиграет один, то проиграет другой, следовательно, игра не коалиционная. Игроки ходят по очереди - значит игра последовательная. Игра конечная, так как существует определенное число ходов за которое можно завершить игру. Выигрыш одного означает проигрыш другого, значит данная игра - игра с нулевой суммой. Так же, исходя из выше сказанного, по характеристикам игра относится и к классу антагонистических игр. По количеству ходов игра является многоходовой. По степени информированности игра является полной и совершенной: в каждый из ходов игроки знают позиции фигур, историю развития игры, возможные ходы.

Характеристика игры Quarto показала, что она относится к тем же классам игр, что и шашки, и шахматы, следовательно, методы, применяемые для их анализа и моделирования, будут актуальны и в случае с игрой Quarto.

1.2 Обзор и сравнительный анализ алгоритмов для построения игровых стратегий

Искусственный интеллект возник из-за желания человека понять способ и природу своего мышления и повторить его при помощи техники. В области компьютерных игр основной задачей искусственного интеллекта становится не моделирование мышления человека как таковое, а более широкая область - создание иллюзии для реальных игроков, что они играют не против «бездушной» машины, а против человека. В связи с этим для создания игрового искусственного интеллекта применимы различные методики и подходы, и алгоритмы.

Одними из первых программ, когда-либо написанных на компьютерах, стали программы, играющие в шашки и в шахматы, одна созданная К. Стрэчи, а другая Д. Принцем соответственно.

Пионером в области создания игрового искусственного интеллекта считается Артур Самуэль, его симулятор игры в шашки - это одна из первых самообучающихся программ в мире. Его программа впоследствии смогла бросить вызов чемпиону мира по шашкам. А. Самуэль заложил базовые понятия искусственного интеллекта, в условиях ограниченности в ресурсах создал метод альфа-бета отсечений, который подробнее будет рассмотрел ниже.

Главным событием в разработке компьютерного соперника для игр можно по праву считать игру в шахматы компьютера Deep Blue против чемпиона мира Гарри Каспарова в 1997 году. Компьютеру удалось выиграть матч из шести партий, первый случай выигрыша компьютера против человека (профессионала в данной игре).

Первые компьютерные игры для рядового пользователя появились в конце 1960-х и поддерживали лишь игру двух игроков и не содержали искусственного интеллекта. Затем в 70-х появились игры с режимом для одного игрока, там впервые появляется виртуальный соперник. Его поведение было запрограммировано и регламентировано шаблонами, созданными заранее. В 1978 году к четким шаблонам поведения добавили движения и события, зависимые от хеш-функций.

С развитием компьютерной индустрии и появлением новых жанров получили свое применение такие инструменты, как конечные автоматы. С усложнением игр возникает потребность в использовании недетерминированных методов, например, все чаще применяются нейронные сети и им подобные инструменты.

На данный момент игровой искусственный интеллект развивается и все так же пытается решить задачу - играть также, как бы это делал реальный человек.

Рассмотрим подробнее некоторые методы и алгоритмы применяемыми для игр схожего класса с игрой, рассматриваемой в данной работе.

Многие методы основаны на обработке дерево решений, которое целесообразно строить для детерминированных и дискретных игр. Первым простейшим методом является полное построение и обход дерева решений игры, то есть полный перебор всех существующих комбинаций. Для того чтобы обрабатывать дерево решений для игр требуются колоссальные вычислительные и временные ресурсы. Так для, казалось бы, простейшей игры в «крестики-нолики» необходимо дерево размером 362880 узлов (9!), естественно, чем больше игровое поле, чем более сложная игра, тем более большое будет и дерево игры.

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

Рисунок 1.1 Фрагмент дерева игры «Крестики-нолики» минимакс

Хотя стратегия минимакса немного упрощает поиск по дереву, она не делает его достаточно легким и быстрым, вычисления по-прежнему высоко-затратные.

Усовершенствованным методом минимакса является альфа-бета отсечение. Он позволяет сократить количество узлов необходимых для анализа. Главная идея данного метода заключается в следующем: оценка узлов производится лишь внутри интервала от альфы до беты, ведь соперник выберет самый «неудобный» ход для нас, значит, нет необходимости оценивать другие более лучшие ходы, ведь соперник их заведомо не выберет. При этом по мере обнаружения лучших ходов интервал будет постепенно уменьшаться [4]. Основным плюсом данного метода является то, что при рассмотрении одной из ветвей полностью возможно отсечь несколько ветвей более низкого уровня и не рассматривать их при совершении хода. Вернемся к ранее рассматриваемому фрагменту дерева игры «Крестики-нолики» при использовании метода альфа-бета отсечения из анализа были бы исключены ветви, которые заведомо не выгодны сопернику (рисунок 1.2).

Рисунок 1.2 Фрагмент дерева игры «Крестики-нолики» альфа-бета отсечение

Хотя данный метод и сокращает время поиска, он не дает достаточно быстрой обработки дерева игры, в худшем случае данный метод может быть сведен по количеству проверок как в минимаксе, а в лучшем - уменьшить пространство поиска на величину равную корню из числа всех возможных ходов.

Существует также большое количество наднастроек над алгоритмом альфа-бета, в большинстве своем они хоть и уменьшают время поиска, но не значительно. В худших условиях время их работы остается равным времени работы метода альфа-бета отсечения.

Очень часто для программирования игры в шахматы, схожей по характеристикам игре Quarto, применяется хеширование. С помощью него можно хранить уже рассмотренные позиции, и сократить пространство поиска, так как не нужно снова анализировать аналогичные позиции. Дело в том, что при построении дерева важен порядок ходов, а значит, существуют узлы, в которых повторяется расположение фигур на поле, хеширование позволяет не проводить анализ для таких узлов, воспользовавшись результатами предыдущего анализа. Один из методов, основанных на хешировании называется таблица перестановок, он позволяет отслеживать не было ли раньше схожей ситуации в игре, возможно ли применить предыдущее решение в данном случае. Данный метод позволяет значительно сократить время поиска, однако имеет единственную проблему: существует вероятность возникновения коллизий.

Расмотренные ранее методы обладают высокой степенью точности, но низкой скоростью работы, другой класс методов предлагает противоположный подход: быстрое время работы, но не такой уж точный результат (то есть, лучшее решение из доступных для анализа, но не лучшее из всех возможных). Зачастую точная, но медленная оценка, уступает глупой, но быстрой. В этом случае применяются различные инструменты нечеткой логики: недетерминированные автоматы, нейронные сети и генетические алгоритмы. Например, генетические алгоритмы в шахматах часто применяются для оценки позиций фигур, качества текущей комбинации.

Первой характеристикой, по которой можно сравнить рассмотренные выше алгоритмы -- это время их работы в худшем случае. Наиболее затратным по времени является полный перебор (обход всего игрового дерева). На втором месте по длительности работы находится минимакс, так как он работает несколько быстрее, чем полный перебор за счет установки порога глубины поиска, однако в худшем случае данный метод может свестись к полному перебору. Следующим следует метод альфа-бета отсечения, он превосходит минимакс, так как является его усовершенствованием. Он позволяет избавиться от рассмотрения заведомо не выгодных ходов и тем самым сократить время работы. Хеширование работает несколько быстрее своих предшественников, однако не является самым лучшим по данному параметру. Самыми быстрым являются инструменты нечеткой логики такие как нейронные сети и генетический алгоритм. Именно это является ключевой причиной их популярности и частоты использования. Однако генетический алгоритм не гарантирует правильности ответа.

Возможность распараллеливания работы метода позволяет существенно сократить время его работы, тем самым делая его более предпочтительным с точки зрения временных затрат. Распределенная работа доступна для методов хеширования и генетических алгоритмов. В случае генетического алгоритма существует специальная модель, позволяющая реализовать работу на разных вычислительных узлах.

Немаловажным параметром является и точность работы. Бесспорно, самым точным является полный обход всего игрового дерева, однако остальные характеристики данного метода сводят на нет данное преимущество. На втором месте стоит минимакс, так как он позволяет рассматривать достаточно большой объем узлов дерева. Как и предыдущий метод, он относится к классу точных методов. Следом за ним идет метод альфа-бета отсечения и хеширование. Точность работы генетического алгоритма во многом зависит от точности его настройки, но из-за того, что он не относится к классу точных, он может лишь приблизиться к точности предыдущих методов. Точность генетического алгоритма трудно контролировать за счет выбора параметров, однако после нескольких его запусков можно набрать достаточную статистику, для того чтобы сделать вывод о его точности.

Еще одной существенной характеристикой, по которой можно сравнить методы, является количество памяти расходуемой в ходе работы, или затраты на вычислительные ресурсы. Данная характеристика тесно связана со временем работы методов. Ранжирование методов по количеству затрачиваемой памяти такое же, как и для временных затрат: наиболее затратным является полный перебор, а наименее генетический алгоритм. Для генетического алгоритма корреляция между объемом расходуемой памяти и временем работы слабее, чем в остальных алгоритмах. Обобщающая таблица по критериям представлена ниже в таблице 1.1.

Таблица 1.1 Оценка методов по параметрам

Параметры Методы	Время работы	Возможность распараллеливания	Точность	Затраты памяти
Полный перебор	Очень долго O(n!)	Нет	Наивысшая	Очень большие
Минимакс	Долго O(n)	Нет	Высокая	Очень большие
Альфа-бета	Долго (от O() до O(n))	Нет	Высокая	Большие
Хеширование	Среднее (от O(1) до О(n))	Да	Средне	Средние
Генетические алгоритмы	Быстро (от O(nlogn) до О())	Да	В зависимости от настроек	Средние

1.3 Описание игры Quarto

Настольная игра Quarto предназначена для двух игроков. Чем-то она схожа со всем знакомой игрой «крестики-нолики». Обычно продолжительность игры составляет около 10 - 20 минут. Игровое поле представляет поле с 16 кругами (местами для фигур) расположенных в форме квадрата 4х4 (см. рисунок 1.3).

Рисунок 1.3 Игровое поле Quarto

В игре существуют 16 фигур, ни одна из которых не повторяется. Каждая из них обладает четырьмя признаками: высокая или низкая, круглая или квадратная, темная или светлая, и присутствие выемки сверху или же ее отсутствие (рисунок 1.4).

Рисунок 1.4 Фигуры

Фигуры в игре для двух игроков общие, в начале игры они ставятся рядом с полем. Для того чтобы выиграть в данной игре необходимо составить вертикальный или горизонтальный, или диагональных ряд из четырех фигур (рисунок 1.5), обладающих хотя бы одним общим признаком.

Рисунок 1.5 Возможное положение выигрышных рядов

Возможные выигрышные комбинации соответственно:

все фигуры ряда белые;

все фигуры черные;

все фигуры круглые;

фигуры ряда квадратные;

фигуры ряда высокие;

ряд низких фигур;

фигуры с выемкой;

фигуры с ровным верхом без выемки (рисунок 1.6).



Рисунок 1.6 Возможные выигрышные комбинации

Необычна игра тем, что при совершении хода игрок не сам выбирает фигуру, за него это делает его соперник. Игра начинается с выбора и передачи фигуры одним из игроков своему сопернику, тот в свою очередь должен поставить эту фигуру на какое-либо свободное место на поле. Затем игрок, поставивший фигуру выбирает фигуру из оставшихся 15 для соперника, и второй игрок ходит выбранной фигурой. Игроки продолжают ходить до тех пор, пока кто-то из них не построит ряд из 4 фигур с каким-либо общим признаком, а значит, выиграет, или же все поле заполнится и ни одной выигрышной комбинации на нем не будет, следовательно, игра завершится ничьей.

1.4 Ключевые моменты в процессе разработки генетических алгоритмов

Революционная работа Чарльза Дарвина «Происхождение видов» послужила толчком к развитию не только в сфере биологии и генетике, но и вдохновило многих исследователей и изобретателей в других областях науки. Так эволюционные принципы стали применяться для моделирования различных ситуаций и для решения задач оптимизации. Совокупность методов и алгоритмов, использующие данные принципы имеет соответствующее название: «эволюционные вычисления» и «эволюционные алгоритмы». Одним из наиболее популярным и часто используемым эволюционным алгоритмом является генетический алгоритм. Основные принципы работы генетических алгоритмов были сформулированы Джоном Холландом в 1975 году в его работе «Адаптация в природных и искусственных системах» [15].

Генетические алгоритмы на сегодняшний день имеют довольно много различных разновидностей и модификаций. При этом помимо выбора самой модели генетического алгоритма разработчику так же необходимо решить какие характеристики установить для того или иного параметра алгоритма, а также решить для каждой операции каким методом предпочтительнее пользоваться. Сфера применения данных алгоритмов достаточно широка, следовательно, под каждую конкретную задачу необходимо модифицировать алгоритм для достижения максимальной продуктивности и результативности.

Первое с чем необходимо определиться - это как будут закодированы особи, то есть возможные решения задачи. Существует несколько вариантов того, как это можно осуществить.

Первый способ - это двоичное кодирование. Оно предполагает, что каждый из признаков особи мы кодируем битовым значением. При этом мы получаем ген определенной длины, где отражены все возможные значения признаков особи. Главный недостаток такого способа является то, что соседние числа отличаются в значениях нескольких битов. Для его устранения был предложен так называемый код Грея, он так же позволяет проводить двоичное кодирование генов особи, но при этом отличия геномов особи в идеале отражены в значении одного бита. Преимущества двоичного способа кодирования доказаны в «теореме о шаблоне» [15], она заключается в том, что двоичный алфавит позволяет обрабатывать максимальное количество информации. Основной недостаток такого способа кодирования является размеры генома, а также сложность и трудоёмкость поиска в пространства большой размерности, связи с этим для нашей задачи данный метод не самый удачный.

Второй способ кодирования - это вещественное кодирование. Оно применяется, когда необходимо производить поиск в непрерывной области допустимых значений переменных. При этом данный вид кодирования требует особых модификаций операторов скрещивания и мутации. В нашем случае такой вариант, кодирования не подходит, так как поиск мы осуществляем не в непрерывной области допустимых значений.

Третьим способом является целочисленное кодирование. Оно предполагает кодирование каждого из признака решения определенным целым числовым значением. Преимуществами данного метода является небольшой размер хромосомы гена при небольшом количестве признаков, а также возможность применения более привычных к понимаю математических операций. В нашем случае это наиболее приемлемый вариант, так как мы легко обозначим целыми числами все возможные позиции на поле, а также проведем кодирование фигур, согласно их признакам. При этом следует отметить, что геном будет не цельным, а «блочным» так как одна часть хромосомы будет отвечать за фигуры, а другая за позиции (подробнее описание данного процесса будет приведено в главе 2).

После того как был определен способ кодирования необходимо решить насколько большой будет популяция особей. Она может быть огромной, порядка ста тысяч, для задач, где важно разнообразие особей, в нашем случае особо большого разнообразия особей не требуется, в связи с этим возьмем стандартное количество особей в популяции равное ста. Уровень приспособленности особей определяется согласно фитнес-функции это ключевой элемент в генетических алгоритмах, описание разработанной фитнес-функции будет приведено далее в главе 2.

Далее должен производиться процесс отбора особей для создания нового поколения. Как и в природе в данном процессе участвуют наиболее приспособленные особи. Существует несколько способов отбора особей, определим наиболее подходящий для нашей задачи.

Первый самый популярный метод - это метод рулетки. Он заключается в том, что родители для следующего поколения выбираются из текущего поколения пропорционально их фитнесу: каждой особи соответствует сектор колеса рулетки, при чем его размер зависит от значения фитнеса у данной особи, то есть чем больше значение функции приспособленности, тем больше сектор. Это означает, что чем больше уровень приспособленности особи, тем более вероятно, что она будет выбрана в качестве родителя для следующего поколения. Недостатком данного метода считается быстрое исключение из популяции особей с небольшим значением фитнеса, что может привести к преждевременной сходимости алгоритма. Однако данный недостаток, можно считать и преимуществом, так как он позволяет существенно уменьшить время работы алгоритма. В задачах где не слишком важна точность решения, но важна скорость работы, такой метод может быть применен.

Второй метод турнирная селекция. Данный метод предполагает разделение популяции на произвольные группы (чаще по 2 или 3 особи) с последующим выбором в каждой из них наилучшей особи (согласно их фитнесу). При этом отбор особей может быть детерминированный с вероятностью один, и случайный с вероятностью меньше единицы. Минус данного метода в том, что он требует большое времени (по сравнению с остальными методами), так как необходимо производить большое количество сравнений.

Третий метод ранговая селекция. Ранжирование особей производится согласно их приспособленности (фитнесу). Количество копий каждой особи, введенных в родительскую популяцию, рассчитывается по заранее заданной функции в зависимости от ранга особи. Недостаток данного метода заключается в том, что необходимо заранее определять функцию, зависящую от ранга особей.

Четвертый метод элитарная стратегия. Она устраняет недостаток классических методов, где наилучшие особи могут не переходить в новое поколение, то есть увеличивают время сходимости алгоритма. Она заключается в том, что в каждом поколении сохраняются наиболее приспособленные особи - они переходят в новое поколение. Минус данной стратегии в том, что она не позволяет осуществлять обор родителей для нового поколения, а сразу же переводит часть особей в состав следующей популяции, то есть минуя операцию скрещивание.

Взяв во внимание все описанные ранее методы отбора особей и их плюсы и минусы, было принято решение сочетать два метода и применять метод рулетки для отбора родительских особей, и элитарную стратегию для повышения эффективности работы и достижения быстрой сходимости метода и небольшого времени работы. Последнее немаловажно для создания виртуального соперника, необходимо чтобы алгоритм работал достаточно быстро.

Определим также, как будет производиться скрещивание. Оно может быть точечным, двухточечным, многоточечным, равномерное (или скрещивание с маской).

Первый способ предполагает выбор определенной позиции в геноме родителей, которая называется точка скрещивания. Для первого потомка первая часть генома наследуется от генома первого родителя до точки скрещивания включительно, а вторая часть от второго родителя начиная от точки скрещивания (не включая ее). Для второго потомка все протекает аналогичным образом, за исключением того, что первая часть генома наследуется от второго родителя, а вторая от первого соответственно (рисунок 1.7).



Рисунок 1.7 Точечное скрещивание

Второй метод - двухточечный, похож на первый, однако здесь производится выбор двух точек скрещивания. При этом обмен генами производится между двумя этими точками (рисунок 1.8).

Рисунок 1.8 Двухточечное скрещивание

Третий метод, как следует из его названия, предполагает большое количество точек скрещивания, и протекает схожим образом с предыдущим методом.

Отличным от предшествующих методом является равномерное скрещивание или скрещивание с маской. В этом случае существует случайно выбранный образец, или маска, определяющая, какие гены будут наследоваться от первого и какие от второго.

Определить преимущества и недостатки методов скрещивания достаточно проблематично, в связи с этим лишь обозначим, что в случае нашей задачи будет использоваться модифицированный метод двухточечного скрещивания (подробнее о нем будет написано в главе 2).

Так же не маловажным является выбор критерия остановки алгоритма. Возможно несколько разных условий. Для оптимизационных задач характерно завершение при достижении ожидаемого оптимального значения, или же при достижении заранее известного максимального значения приспособленности (фитнеса). В нашем случае данный критерий не подходит, так как мы не имеем ни заранее известного оптимального решения, ни наибольшего значения фитнеса. Следующий возможный критерий - это выход на «плато», когда для всех особей популяции достигается одинаковый фитнес. Данный критерий может существенно повлиять на время работы, оно может стать довольно большим, что так же в нашем случае представляется не самым приемлемым. Так же возможно использование времени работы в качестве критерия остановки. В этом случае велик риск получения не самого лучшего решения, что так же не очень хорошо для нашей задачи. Последний метод - это исчерпание количества поколений, отпущенных на эволюцию, то есть устанавливается конкретное число поколений, по прошествии которых алгоритм завершает свою работу. Данный вариант выглядит наиболее привлекательным, так как довольно прост в реализации и при регулировании числа поколений позволит получать достаточно хорошие решения за небольшое время работы алгоритма.

Итак, в ходе написания данного пункта были выбраны оптимальные параметры для разработки генетического алгоритма построения выигрышной стратегии для игры Quarto.

1.5 Примеры использования генетических алгоритмов для моделирования игровых ситуаций

Впервые генетические алгоритмы для игр были применены Робертом Аксельродом в 1987 для разрешения «дилеммы заключенного» [11]. До этого момента генетические алгоритмы для моделирования игровых ситуаций использовались совместно с другим инструментом - нейронными сетями.

С развитием компьютерных игр появилась потребность в более умном сопернике, с этого момента началось развитие искусственного интеллекта и применение нестандартных алгоритмов. В 2004 году Николас Коул, Сушил Дж. Льюис и Крис Майлс описали опыт применения генетических алгоритмов для настройки ботов в игре Counter-Strike [13]. В своей работе они использовали генетический алгоритм Cross-population selection (CHC) для подбора оптимальных значений параметров для бота. В хромосоме бота кодировались: вероятности выбора того или иного оружия, уровень агрессивности, использование гранат. В ходе обучения боты, управляемые генетическим алгоритмом, играли против ботов, настроенных вручную авторами. Результаты исследования показали, что боты, полученные после работы генетического алгоритма, ничем не уступают ботам, настроенным игроком-профессионалом.

Для игр схожих по классификации с игрой Quarto, в 2007 году М. Сиппер, Я. Азариа, Э. Хауптман и Й. Шичел использовали генетические алгоритмы для трех игр: нарды, шахматы и Robocode [18]. Для нард использовались два способа обучения: игра особей между собой (турнир) и игра с Pubeval, стандартный тестовый игрок созданный Джерри Тесауро в 1993 году. Для шахмат использовался лишь турнирный способ отбора. Для Robocode так же, как и для нард применялись два вида отбора турнирный и игры с внешним соперником, загруженным с ресурса HaikuBot league. В результате данной работы авторам удалось получить игрока в нарды выигрывающего Pubeval в 62.4% случаев, что на 10% больше чем результат предыдущего лучшего виртуального игрока. Созданный Robocode игрок занял 3 место в международной лиге HaikuBot среди программ, разработанными людьми.

В данной главе был проведен анализ игры Quarto c точки зрения теории игр, а также были рассмотрены ее правила. После этого был проведен анализ существующих алгоритмов для моделирования игровых ситуаций, в ходе которого был выбран генетический алгоритм в качестве метода для создания виртуального соперника. Затем были описаны ключевые параметры для разработки генетических алгоритмов и определены их значения и выбраны наиболее подходящие способы организации для ключевых операций алгоритма, которые впоследствии будут использованы для разработки алгоритма построения выигрышной стратегии для игры Quarto. Затем были приведены примеры удачного применения генетических алгоритмов в играх проделанные другими исследователями.



Глава 2. Генетический алгоритм построения выигрышной стратегии для игры Quarto

2.1 Анализ стратегии игроков в игре Quarto

В первой главе мы рассмотрели игру Quarto с точки зрения теории игр, сейчас же мы более подробно ее проанализируем. Игровое дерево игры составляет 16! узлов, что является большим числом, следовательно, построение такого дерева довольно трудоемкий процесс.

Для упрощения анализа было принято решение построить дерево для игры похожей на оригинальную за исключением того, что размер поля будет уменьшен до квадрата 2х2, то есть с шестнадцати ячеек до четырех. Следовательно, теперь игровое дерево будет состоять из 4! узлов, что вполне реалистично построить. Соответственно количество фигур было так же уменьшено до четырех. Данные фигуры являются так же различными, как и в игре 4х4, количество рассматриваемых признаков можно сократить с четырех до двух, так как их будет достаточно при игре на малом поле. Теперь набор фигур представляет собой: черную низкую, черную высокую, белую низкую и белую высокую фигуры.

Ход игроков состоит из двух действий: постановки фигуры и передачи фигуры. Из-за правил игры ход первого игрока состоит лишь из одного действия передачи фигуры, для простоты анализа будем все же считать данное действие полноценным ходом.

Упрощенная игра 2х2 из-за сокращения количества ячеек и фигур может закончиться только победой первого игрока А или победой второго игрока В. Ничья в данном случае не возможна. В связи с этим игра завершается после трех ходов, в случае победы первого игрока или после четырех, в случае победы второго игрока.

Для игры 2х2 было построено дерево. Ходы игрока А (первый игрок) нарисованы тёмно-синим цветом, а ходы игрока В (второй игрок) - голубым. Поле представляет собой таблицу 2х2. Фигуры при постановке на поле обозначаются большими буквами: например, черная низкая будет изображена как «ЧН». При одинаковой структуре поддеревьев между родительскими вершинами ставится знак равенства. Полное дерево для данной игры можно увидеть в приложении А.

Поддеревья для каждой из фигур абсолютно аналогичны, повторяют структуру друг друга. Рассмотрим одну из веток построенного дерева, например, когда игрок А передал первой черную низкую фигуру. Его соперник, игрок В, может поставить ее на любую из 4 ячеек. Так же, как и для фигур поддеревья для позиций имеют идентичную друг другу структуру. Например, игрок В поставил фигуру в верхний левый угол. Затем он должен передать фигуру, например, он передал черную высокую. Следующим ходит игрок А и мы видим, что куда бы он не поставил данную фигуру он выигрывает игру. Аналогичный исход произойдет при передаче игроком В белой низкой фигуры. Однако при передаче белой высокой фигуры ситуация иная: после постановки фигуры игроком А игра не завершается. Поставив фигуру игрок А выбирает фигуру для своего соперника, например, он выбирает белую низкую. Игрок В ставит данную фигуру и выигрывает, аналогично этому происходит при выборе игроком А и другой фигуры (рисунок 2.1).

Рисунок 2.1 Фрагмент дерева игры 2х2

Общее количество листовых вершин в дереве составляет 288, для игрока А - 96 и для игрока В 192 соответственно. Для того чтобы оценить шансы каждого из игроков на победу необходимо рассмотреть формулу полной вероятности. Если событие А может произойти только при выполнении одной из гипотез , которые образуют полную группу несовместных событий, то вероятность события А вычисляется по формуле (1).

(1)

где P(A) - вероятность наступления события А, - вероятность выполнения гипотезы , - условная вероятность наступления события А при выполнении гипотезы и т.д.

Рассчитаем вероятность выигрыша игрока А. Всего будет существовать шестнадцать гипотез, при которых игрок А выбрал одну из 4 фигур, затем игрок В выбрал одну из 4 позиций и две фигуры из трех (так как именно при таком выборе игрок А побеждает). Соответственно вероятность выигрыша игрока А равна:

(2)

При расчете аналогичным образом для игрока В данная вероятность будет равна 1/3 соответственно. Значит, шансы на выигрыш равны 2 к 1.

Однако, в ходе анализа построенного дерева так же удалось установить, что для игрока В существует выигрышная стратегия, при которой он выиграет если будет делать ходы осознано не случайно. На ходе 2 при выборе той или иной фигуры игрок В определяет исход игры, при выборе двух из 3 фигур он проиграет (данные фигуры имеют общий признак с фигурой уже стоящей на поле), или при выборе фигуры не имеющей ничего общего с уже стоящей на поле игрок обеспечивает себе победу. Для игрока А такой стратегии нет, он зависит от выбора игрока В если тот ошибется и выберет фигуру имеющую общий признак с стоящей на поле, то игрок А победит, если же игрок В поступит иначе, то игрок А проиграет. После анализа дерева игра 2х2 была смоделирована с помощью созданной программы, описание которой будет подробно рассмотрено далее в данной главе. Для сбора статистики были запущены 1000 игр, двух игроков, которые ставят фигуры случайным образом. Полученные результаты подтверждают аналитические выводы, сделанные в ходе анализа дерева игры: количество побед игрока А превосходит количество побед В практически в 2 раза.

Рисунок 2.2 Диаграмма количество побед игроков при игре 2х2 из 1000 игр

Возможно, выявленные закономерности и схожие законы справедливы и для оригинальной игры 4х4. Так же, как и для игры 2х2 смоделируем игру двух игроков, совершающих ходы случайным образом. Запустим 1000 игр и получим следующие результаты: для оригинальной игры количество побед игрока А составило 485 игр, а для игрока В 484 игры, ничьей закончились 31 игра (рисунок 2.3).

Рисунок 2.3 Диаграмма возможных исходов игры в процентном соотношении

Из этого можно сделать вывод, в отличие от игры 2х2, в оригинальной игре Quarto у игрока А и игрока В равные шансы на победу. Так же интересно и то, что 3% игр может завершиться ничьей. Затем была собрана статистика, отражающая за какое количество ходов какой-либо из игроков достиг победы. На ее основе построена диаграмма, представленная ниже, она отражает процент игр от общего количества игр, завершенных за определенное количество ходов, например, совершив 6 ходов игрок В выиграл 24% игр (см. рисунок 2.4).

Рисунок 2.4 Диаграмма процент игр, завершенных за определенное количество ходов

Данная диаграмма показывает нам, что чаще всего игра завершается победой одного из игроков на 6 или 7 ходе, то есть ближе к концу игры. Следует отметить что на шансы завершить игру в свою пользу на четвертом, пятом и шестом ходе больше у игрока В, в тоже время завершить игру своей победой для игрока А более вероятно начиная с 7 хода. Из этого можно сделать вывод, что для игрока А выгодно «затягивать» игру, а для игрока В попытаться завершить игру как можно скорее.

Первоначальный выбор фигуры не имеет особого значения, так как поддеревья для каждой из выбранных фигур аналогичны, так же, как и в игре 2х2, которая была рассмотрена ранее. Однако выбор позиции накладывает ограничения на тип поддерева, в случае с игрой 4х4, на поле не все ячейки равноценны, существует три типа ячеек (рисунок 2.5).



Рисунок 2.5 Типы ячеек на поле 4х4

Оранжевым цветом выделены угловые ячейки, они относятся к первому типу. Ко второму типу относятся не закрашенные (белые) ячейки, и наконец, к третьему типу относятся зеленые ячейки, находящиеся в центре поля.

Для выявления выигрышной стратегии поведения проанализируем поведение игроков и принятые ними решения по поводу выбора позиций на каждом из ходов. В анализе по-прежнему рассматриваются 1000 игр, игроков А и В, действующих случайным образом. Рассмотрим второй ход в игре и первый ход игрока В, а именно постановка переданной фигуры. Как видно из диаграммы ниже на рисунке 2.6, для игрока В при выборе первого типа ячеек вероятнее проиграть, однако выигрыш так же возможен, но его вероятность несколько ниже. При выборе второго типа ячеек вероятнее всего достичь победы, или хотя бы не проиграть, так как в данном типе самая высокая вероятность ничьи. При третьем типе равновероятны как победа, так и проигрыш, ничья так же возможно, но ее вероятность не много ниже.

Рисунок 2.6 Диаграмма исход игры в зависимости от выбора первой позиции игроком В



Исходя из полученных данных можно сделать вывод, что для того чтобы хотя бы не проиграть или выиграть игроку В предпочтительнее поставить первую фигуру на ячейку типа 2.

Предположим, что игрок В поставил фигуру на ячейку типа 2, так как это наиболее выгодный для него первый ход. После этого игрок А должен решить куда же ему лучше всего сходить, рассмотрим полученные результаты (рисунок 2.7).

Рисунок 2.7 Выпор позиции игроком А после хода игрока В типа 2

Если игрок выберет тип 1, то наиболее вероятна победа, однако и проигрыш возможен. При типе 2 скорее всего игра закончится ничьей. При типе 3 вероятна победа. Однозначно рекомендовать какой-либо из типов ячеек невозможно, так как разрыв между альтернативами составляет не более двух-трех процентов. Все же наиболее «безопасным» выглядят ячейки типа 3, так как при их выборе наиболее вероятна победа и ничья.

2.2 Кодирование решений

Прежде чем перейти непосредственно к созданию и кодированию генетического алгоритма необходимо создать программу, которая позволит смоделировать игру Quarto, а затем и впоследствии создать полноценную электронную версию игры.

Во-первых, необходимо продумать, как именно будет функционировать система, ее логическую структуру. Первой сущностью необходимой для работы системы будет являться судья. Он будет начинать игру и регулировать порядок совершения ходов игроками. Также он будет проверять поле на наличие выигрышной комбинации, после обнаружения которой он завершит игру и назначит победителем игрока, сделавшего последний победный ход. При заполнении всего поля фигурами и отсутствии комбинаций с общими признаками судья завершает игру и «объявляет» ничью.

Игра будет представлена в виде игровой сессии. Судья при запуске игры создает игровую сессию, а затем отслеживает состояние поля в ней. Каждая игровая сессия содержит поле и текущее положение фигур, а также фигуру, которую передают друг другу игроки. Из этого вытекает, что в системе так же должны присутствовать сущность поле и сущность фигура. Для простоты будем считать, что поле содержит не только само поле, матрицу 4х4, но и «набор фигур» еще не поставленных на поле.

Очевидно, что в игре будут еще две сущности: игрок А и игрок В. Каждый из них будет ходить поочередно, при этом передачу хода контролирует судья. При совершении хода игроки вначале ставят переданную им фигуру («берут» ее из игровой сессии), затем выбирают фигуру для соперника и «передают» ее в игровую сессию, исключением является лишь первый ход: там совершается только передача фигуры. После каждого хода судья проверяет поле на наличие выигрыша какого-либо из игроков или ничьи. Совершение ходов, передача хода и проверка поля осуществляется в цикле, он прерывается при достижении или выигрыша одного из игроков или ничьи.

Упрощенная схема функционирования системы представлена ниже на рисунке 2.8.



Рисунок 2.8 Логическая схема функционирования системы

После создания логической схемы функционирования системы необходимо более подробно остановиться на кодировании поля и фигур. Поле будет представлять собой матрицу (таблицу) 4х4, в ячейки которой будут записываться значения фигур, которые игроки туда поставят. Пустым ячейкам на поле присваивается значение -1 (рисунок 2.9).

Рисунок 2.9 Пример поля игры 4х4

Перейдем к фигурам. Как уже говорилось ранее в игре существует 16 различных фигур с четырьмя признаками. Значения каждого из признаков бинарные, значит для каждого из ни можно присвоить значение: белый - 1 и черный - 0, высокий - 1 низкий - 0; выемка есть - 1 и нет выемки - 0; круглый - 1 и квадратный - 0. Порядок следования цифр будет определять к какому признаку присвоено то или иное значение: первая цифра относится к цвету, вторая - к высоте фигуры, третья описывает наличие выемки, и наконец, четвертая форму фигуры. Тем самым каждая фигура будет закодирована четырехзначным числом в двоичной системе исчисления. Преимущество применения бинарных значений и двоичной системы исчисления является возможность применения побитовых операций. Например, для определения общих признаков можно применить операцию исключающего или. Однако храниться фигуры будут в десятичной системе исчисления для простоты записи в массив, то есть каждое полученное при кодировании признаков фигуры число из двоичной системы переводится в десятичную (рисунок 2.10).

...