1.2 Возможные алгоритмы поиска решения

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

Приведем три алгоритма при помощи которых было бы можно написать компьютерного бота-противника игры «реверси»:

1.2.1. Игровые модели эвристического поиска

Планирование в условиях конфликта предполагает, что на выработку плана действий влияет 2 или более противодействующие стороны. Модель таких ситуаций называется игрой.

Постановка задачи:

1. Имеется n>=2 конфликтных сторон (игроков)

2. Заданы правила определённых действий игроков

3. Определён набор конечных состояний

4. Для каждого возможного состояния существует оценка его стоимости по отношению к игроку

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

Игровая модель представляет собой комбинацию:

1. Дерево игры – вершины соответствуют состояниям, дуги – ходам. С каждой вершиной сопоставляется игрок, имеющий право хода в данной позиции. Дерево игры задаётся неявно с помощью корневой вершины и порождающей процедуры (ПП).

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

Критерии: конец игры, глубина.

3. Статическая оценочная функция оценивает качество игровой позиции без анализа её приемников, как правило, носит сугубо эвристический характер. Например, для игры «Шашки» статическая оценка может иметь вид: 6x+4y+z , где x – перевес в дамках; y – перевес в обычных шашках; z – перевес в подвижности (насколько больше ходов не приведёт к потере шашки противника)

Предполагается, что 1-ый из игроков стремится к увеличению оценки (Max), второй – к уменьшению оценки (Min). Всё дальнейшее рассмотрение ведётся с позиции Max.

4. Процедура формирования рабочих оценок. Рабочая оценка позиции основана на оценках её приемников. Из ПП, СОФ, ПФРО складывается процедура поиска и выбора хода.

5. Критерии окончания. Фрагмент дерева игры, сформированный ПП термин, вершины которого удовлетворяют критериям окончания, называется деревом поиска.

Общий принцип оценки

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

Минимаксная процедура - это процедура, представляющая собой комбинацию порождающей процедуры в глубину и рассмотренного выше принципа формирования рабочих оценок. Минимаксная процедура выполняет полное исследование дерева игры в глубину. Если максимальная глубина дерева равна m и в каждом состоянии имеются b допустимых ходов, то временная сложность этого минимаксного алгоритма составляет O(b^m). Безусловно, в реальных играх такие затраты времени полностью неприемлемы, но данный алгоритм служит в качестве основы математического анализа игр, а также более практических алгоритмов.

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

α-обозначается наименьшее значение оценки гарантированной для Макса.

β-обозначается наименьшее значение оценки гарантированной для Мина.