Разработка программного модуля искусственного интеллекта для игры в шахматы
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?ерево игры и по нему ищут лучший ход.
2. Общие понятия теории игр
.1 Дерево возможных позиций
Пусть задано конечное ориентированное дерево G, множество В его вершин составлено из двух непересекающихся подмножеств B0 и B1 , а любой вершине p B , которая не является началом никакого звена этого дерева, поставлено в соответствие действительное число Oe(p) . Это определяет игру двух противников с полной информацией. Вершины ориентированного дерева G, принадлежащие подмножеству B0 , называются позициями с ходом белых, а принадлежащие подмножеству B1 - позициями с ходом черных; звенья этого дерева называются ходами белых или черных в зависимости от того, какому из подмножеств B0 или B1 принадлежит их начало. Если позиции p B поставлено в соответствие число Oe(p) , она называется заключительной, а Oe(p) называется статической оценкой этой позиции.
Ориентированное дерево G называется деревом игры.
Согласно определению для любой позиции p B существует единственный путь L{p0 > p1, p1 > p2 , ..., pk > p } с началом в корне p0 ориентированного дерева Г и концом в рассматриваемой позиции ,такой путь называется партией, приводящей к позиции p .
Корень p0 дерева игры G является выделенной позицией. Это - позиция, предложенная программе, и задача состоит в том, чтобы найти в ней лучший ход. Для этого достаточно определить Oep0 и Oepi для всех позиций, которые получаются из p0 за один ход. Определения оценки начальной позиции p0 , выполняется схемой полного перебора, а в теории игр этот алгоритм называется алгоритмом negamax.
Сложность игрового дерева вычисляется по формуле: w^d, где w-среднее кол-во возможных ходов, а d-глубина дерева.
Рисунок 1 - Дерево возможных позиций
2.2 Принцип минимакса
Данный алгоритм осуществляется с помощью поиска в глубину. То есть для каждой не пройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них. Мы откатываемся на вершину последней глубины и рассчитываем очки выигрыша относительно первого игрока. Затем от родительского ему узла переходим на следующий дочерний узел (если есть) и рассчитываем там очки выигрыша. Если количество дочерних узлов закончилось, то ищем минимум очков выигрыша (если уровень родительского узла нечетный) либо максимум (если четный). Родительский узел обладает полученным очком выигрыша. Делаем аналогичный поиск, но учитывая уже, что родительский узел уже дочерний[9].
В листьях дерева расчет очков происходит относительно первого игрока, т.е. считается, что первый игрок стремится максимизировать свой выигрыш, а второй игрок - минимизировать выигрыш первого игрока. Первый игрок выигрывает в том случае, если количество очков на вершине дерева уровня больше нуля.
Рисунок 2 - Поиск в дереве алгоритмом минимакс
В результате, процесс, используемый программой, соответствует чередованию решений (компьютер / человек), на каждом ходе компьютер выбирает максимальную оценку. Решение, возвращающееся в корень дерева, несомненно оказывается лучшим выбором, при предположении, что противник в каждом случае также делает самые сильные ходы. Статическое оценивание выполняется только в узлах последнего уровня (листья дерева) для позиции компьютера.
Этот алгоритм осуществляет полный перебор всех вариантов. Число рассмотренных позиций будет оцениваться как W в степени D, где W - примерное количество ходов в одной позиции, D - глубина просчета. Для шахмат W примерно равно 40, это значит, что считая на глубину 4, мы должны перебрать 40^4 = 2560 тыс. позиций, а для глубины 5 - 10240 тыс. позиций[21].
Дерево перебора растет экспоненциально. На сегодняшний день на самых мощных процессорах при самом оптимальном коде возможно считать на глубину 6 в реально оцениваемый промежуток времени. В этом заключается основная проблема разработки алгоритмов игры шахматы и все разработки направлены на сокращение рассматриваемых комбинаций.
На рисунке 3 представлена блок-схема алгоритма минимакс по выбору лучшего хода, представленный алгоритм возвращает лучший ход по оценке, полученной при более глубоком анализе. Блок-схема алгоритма по поиску оценки в глубину представлена на рисунке 4.
Рисунок 3 - Блок-схема по выбору лучшего хода
Рисунок 4 - Блок-схема по поиску оценки в глубину
При вызове алгоритма поиска оценки в глубину с очень большой требуемой глубиной, получим оценку при полном переборе всех возможных ходов.
2.3 Метод отрицательного максимума (NegaMax)
В данном алгоритме статическая оценка позиции для одной из сторон, равно статической оценка другой стороны с обратным знаком.
Рисунок 5 - Метод отрицательного максимума
Далее, для удобства восприятия, деревья будут рисоваться без учета NegaMax.
2.4 Статическая оценка позиции и основные требования к оценочной функции
Статическая оценка позиции - это способ объективного, количественного выражения того субъективного ощущения, которое возникает у человека при взгляде на позицию, без анализа возможных путей развития игры. В программировании игр, статическая оценка позиции называется функцией качества позиции.
Если нахождение лучшего хода с помощью дерева игры может с одинаковым успехом применяться для всех игр, то статическая оценка позиции - часть, специализированная под определенную игру. Её специализация определяет стиль игры искусственного