Реферат на тему:


Воспользуйтесь поиском к примеру Реферат        Грубый поиск Точный поиск






Загрузка...

Альфа бета отсечений (Alpha-Beta Pruning) при программировании компьютерных игр

ВВЕДЕНИЕ

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

Определены основные понятия, связанные с деревом игры, описывается, называемая альфа-бета отсечениями (alpha-beta pruning), и тесно связанный с ней метод, однако, не столь эффективен, поскольку он не делает "нижних отсечений "; тут же доказана корректность обоих методов.

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

1. Игры и оценки позиций

Игры "один на один", а только с ними мы и имеем здесь дело, обычно описывают множеством "позиций" и совокупностью правил перехода из одной позиции в другую, причем предполагают, что игроки ходят по очереди. Будем считать, что правилами разрешены только конечные последовательности позиций и в каждой позиции имеется лишь конечное число разрешенных ходов. Тогда для каждой позиции p найдется число N (p) такое, что никакая игра, начавшаяся в p, не может продолжаться более N (p) ..

Терминальными называются позиции, из которых не разрешенных ходов. На каждой из них определена целочисленная функция f (p), что задает выигрыш того из игроков, которому принадлежит ход в этой позиции; выигрыш второго игрока считается равным-f (p).

Если с позиции p является d разрешенных ходов p1, ..., pd, возникает проблема выбора лучшего из них. Будем называть ход лучшим, если по окончании игры он приносит наибольший возможный выигрыш при условии, что противник выбирает ходы, лучшие для него (в том же смысле). Пусть F (p) является крупнейший выигрыш, достижимый в позиции p игроком, которому принадлежит очередь хода, против оптимальной защиты. Т.к. после хода в позицию pi выигрыш этого игрока равна-F (pi), имеем

(1)

Эта формула позволяет индуктивно определить F (p) для каждой позиции p.

В большинстве работы по теории игр используется чуть другая формулировка; в ней игроки называются Max и Min и изложение ведется с "точки зрения" игрока Max. Таким образом, если p является терминальная позиция с ходом Max, его выигрыш равен, как и раньше f (p), если же в терминальной позиции p ходить должен Min, то его выигрыш равен

(2) g (p) =-f (p).

Max пытается максимизировать свой конечный выигрыш, а Min пытается минимизировать его. Соотношению (1) при этом соответствуют две функции, а именно

(1 '),

задающий максимальный гарантированный выигрыш игрока Max в позиции p и

равной оптимума, легкодоступном для игрока Min. Как и раньше, здесь предполагается, что p1, ..., pd есть разрешенные в позиции p ходы. Индукцией по числу ходов легко показать, что функции, обусловленные соотношениями (1) и (3), совпадают и для всех p

(5) G (p) =-F (p).

Таким образом, оба подхода эквивалентны.

Т.к. нам конечно легче оценивать позиции с точки зрения одного какого-то игрока, иногда удобнее использовать "минимаксный" подход (3) и (4), а не рассуждать в "плюс-минус-максимальных" терминах соотношения (1). С другой стороны, соотношение (1) предпочтительнее, когда мы хотим доказать что-либо, - при этом нам не приходится исследовать два (или больше - по числу игроков) различных случая.

Функция F (p) равна тому максимуму, что гарантирован, если оба игрока действуют оптимально. Следует, однако, видно, что она отражает результаты очень осторожной стратегии, не обязательно хорошая против плохих или игроков игроков, действующих в соответствии с другого принципа оптимальности. Пусть, например, есть два хода в позиции p1 и p2, причем p1 гарантирует ничью (выигрыш 0) и не дает возможности выиграть, в то время, как p2 дает возможность выиграть, если противник пересмотрит очень тонкий ход, выигрывает. В такой ситуации мы можем предпочесть рискованном хода в p2, если только мы не уверены в том, что наш противник всемогущ. Очень возможно, что люди выигрывают в шахматных программ в такой же способ.

2. Разработка алгоритма

Нижеследующий алгоритм (на специально придуманной алголоподибний языке), пожалуй, вычисляет F (p) в соответствии с определением (1):

integer procedure F (position p):

begin integer m, i, t, d

Определить позиции p1, ..., pd, подчиненные p

if d = 0 then F = f (p) else

begin

m = -

for i: = 1 step 1 until d do

begin

t =-F (pi)

if t> m then m: = t

end

F = m

end

end.

Здесь + обозначает число, не менее abs (f (p)) для любой терминальной позиции p; назад - не более F (p) и-F (p) для всех p. Этот алгоритм вычисляет F (p) на основе "грубой силы": для каждой позиции он оценивает все возможные продолжения; "Лемма о бесконечности" гарантирует окончание вычислений за конечное число ходов.

Перебор, осуществляющий этот алгоритм, можно уменьшить, используя идею метода "ветвей и границ" [14]. Идея заключается в том, что можно не искать точную оценку хода, о Который стало известно, что он не может быть лучше, чем один из ходов, рассмотренных ранее. Пусть, например, в процессе перебора стало известно, что F (p1) = -10. Мы заключаем отсюда, что F (p) 10, и поэтому нам не нужно знать точное значение F (p2), если каким-либо образом мы как-то узнали, что F (p2) -1 (и, таким образом, что-F ( p2) 10). Итак, если p21 допустимый ход с p2 и F (p21) 10, мы можем не исследовать другие ходы с p2. В терминах теории игр ход позицию p2 "опровергается" (по ходу в p1), если у противника в позиции p2 есть ответ, по крайней мере столь же хорош, как его лучший ответ в позиции p1. Ясно, что если

Загрузка...

Страницы: 1 2 3 4