2020-06-29
180
Рассмотрим следующее дерево:
S
A A
A … ………… B
f(A)=a
B
C ……
 |  | ||
A
D
……
B
E ……
f(E)=z£a
Пусть на известны оценки f(A)=a и f(E)=z£a. Докажем, что если f(E)£a, то ветви, исходящие из вершины D (на рисунке обозначенные синим цветом) можно отсечь.
Т.к. игрок B стремится минимизировать оценочную функцию, следовательно оценка вершины D будет не больше z (f(D) £ f(E)=z £a).
Т.к. игрок A стремится максимизировать оценочную функцию,
следовательно оценка вершины С будет не меньше оценки вершины D (f(C)³f(D)).
Возможны 2 случая:
1). f(C)=f(D), тогда f(C)=f(D) £ f(E) £a - т.е. имеем неглубокое a - отсечение.
2). f(C)>f(D), тогда вершина D для получения оценки f(C) не использовалась.
Пример.
5 S
A A
a=5 3
 |
B
b=5 7 3=z£a=5
 | |||
 |
A
a=1 5 3 7=w³b=5 3
B
3 1 4 1=z£a=1 6 5 3 5 8 9 7 3=z£a=5 4=£a=5
| Ход | Наилучшая оценка | Позиция на глубину | Оценка позиции | Условие отсечения | Действие |
| Свой A(max) | a | Своя | Z | z£a | a-отсечение |
| Противник B(min) | b | Противника | W | w³b | b-отсечение |
a возрастает при построении оценки снизу вверх
b убывает при построении оценки снизу вверх
Пусть оценивается дерево на n уровней. На каждом уровне имеется m вариантов выбора. Тогда сложность вычислений
для метода максимина - 
для метода a-b отсечений - 
(при больших n ~ 
)
Недостатки методов максимина и a-b отсечений
1). Оба метода не являются стратегиями и базируются на классических
переборных алгоритмах, с использованием оценочной функции.
2). Эффект горизонта (никакие жертвы, которые не дают выигрыш в пределах
обозрения программой не принимаются).
Пример.
Построение оценочной функции для игры в шахматы.
f(s)= 
,
f1 – оценка, учитывающая алгебраическую стоимость фигур;
f2 – оценка, учиьываюшая относительную безопасность короля;
f3 – оценка, учитывающая подвижность фигур;
f4 - оценка, учитываюшая степень контроля центра;
f5 - оценка, учиваюшая пешечный строй;
f6 – оценка, учитывающая аттакующие позиции;
