Раздел «Образование».FIVTLecturesTerm4Lecture03:
<< Список лекций ФИВТ, 4-й семестр, 2009 г.

Лекция 3. Альфа-бета отсечение

Middle Game

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

Middle Game заканчивается либо матом, либо эндшпилем - игровой концовкой с малым количеством фигур, для которой можно просчитать, кто выигрывает и как ему ставить мат (см. PROBLEM:046).

Как написать компьютерную стратегию для Middle Game? Естественный ход мысли приводит к алгоритму продумывания дерева ходов.

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

Игровая позиция — это пара (состояние игрового поля; цвет игрока, чей ход).

Бета-отсечение

Пусть мы рассмотрели один вариант своего хода MOVE1 и получили некоторую его оценку — число Beta. Чем больше это число, тем лучше для нас.

Затем мы стали рассматривать второй ход MOVE2. Изучая возможные ответы на него нашего соперника мы обнаружили у него очень сильный ответ — например, он берёт у нас ферзя, а мы у него — нет. Если его ответ на наш ход имеет оценку меньше чем Beta (то есть хуже для нас), то не имеет смысла рассматривать другие его ответы на ход MOVE2. Мы и так уже нашли ответный ход хуже, чем все возможные ответные ходы на ход MOVE1. Дальнейшее изучение ответных ходов может только ухудшить оценку хода MOVE2. А это нам не интересно, так как у нас есть ход MOVE1.

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

Альфа-бета отсечение

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

* Описание алгоритма?

Эффект горизонта

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

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

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

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

Другая глубина — действительное число, которое с каждым ходом уменьшается на число от 0 до 1 в зависимости от интересности хода. Чем интереснее ход, тем меньше это число. Наиболее интересные ходы — это взятие фигур и шахи. Первая максимальная глубина задает точное ограничение на глубину дерева. Его можно сделать довольно большим, например в 20 ходов. Вторая глубина — это глубина интересности.

Прекращение рекурсивного перебора ответов соперника не происходит, если одна из этих глубин достигла числа 0.

Игра крестики нолики

Рассмотрим игру "крестики-нолики" 15x15, 5 в ряд.

В этой игре достаточно высокая степень ветвления дерева ходов, особенно в начале. Фигур на игровом поле нет. Эвристическую оценку ситуации естественно складывать из оценок множества мест, где потенциально может появится пять ваших крестиков в ряд (очки к оценке добавляются) или пять ноликов соперника в ряд (очки из оценки вычитаются). Чем больше крестиков в потенциальном ряду длины 5 стоит, тем выше оценка этого ряда. Эвристическую оценку ситуации вы можете придумать свою. Собственно в этом в значительной степени и будет определяться "интеллектуальность" вашей компьютерной стратегии. Сам алгоритм перебора дерева ходов с альфа бета отсечением общая компонента большинства компьютерных стратегий.

Полезные оптимизации

-- ArtemVoroztsov - 25 Mar 2010