Search: Games,
Minimax, and
Alpha-Beta
Галкина Екатерина
Шрамов Георгий
Глоссарий
Branching factor
(коэффициент ветвления)
Tree depth
(глубина
дерева)
Leaf nodes
(листовые узлы)
Галкина и Шрамов
2
Глоссарий
Linear scoring polynomial
Brute force
Minimax algorithm
Adversarial game
Crude measure
Alpha-beta pruning
Progressive deepening
Anytime algorithm
Галкина и Шрамов
3
Ways to play
Как человек
Анализ ситуации
Выбор хода на основании какой-либо стратегии и
тактики
Условные правила
Анализ последствий хода (с помощью статической
оценочной функции)
Построение всего дерева игры (алгоритм Британского
музея)
Анализ последствий хода максимально далеко (алгоритм
минимакс)
Галкина и Шрамов
4
Алгоритм минимакс
max
min
static value
ИЛИ-вершина
2
2
2
И-вершина
1
7
1
8
ИЛИ(max)-вершине приписывается оценка, равная максимуму
оценок ее дочерних вершин
И(min)-вершине приписывается оценка, равная минимуму
оценок ее дочерних вершин
Галкина и Шрамов
5
Альфа-бета-отсечение
α-величина
max
min
static value
>= 2 2
<= 1
<= 2 2
2
β-величина
7
?
1
?
α- и β-величины – предварительные оценки
α-величины не могут уменьшаться
β-величины не могут увеличиваться
Галкина и Шрамов
6
Альфа-бета-отсечение
α-отсечение: перебор можно прервать ниже любой
И(min)-вершины, β-величина которой не больше,
чем α-величина одной из предшествующих ей
ИЛИ(max)-вершин (включая корень).
β-отсечение: перебор можно прервать ниже любой
ИЛИ(max)-вершины, α-величина которой не меньше,
чем β-величина одной из предшествующих ей
И(min)-вершин.
Отсечение может быть глубоким
Галкина и Шрамов
7
Альфа-бета-отсечение
β-отсечение
max
3
min
? >= 4
3
1
<= 3 ?
<= 3 3
max
0
>= 3
3
4
3
3
2
α-отсечение
Оба отсечения неглубокие
Галкина и Шрамов
8
Постепенное углубление
0
1
2
…
d-1
d
bd-1
bd
S = 1 + b + b2 + … + bd-1 = bd-1 – немного лишних вычислений
Галкина и Шрамов
9
Deep Blue
Алгоритм минимакс с альфа-бетаотсечением и постепенным
углублением
Параллельные вычисления
Специальные инструкции для начала
и конца партии
Несбалансированное по высоте
дерево игры
Высота дерева – 14 - 16
Галкина и Шрамов
10