Решение задач 1

8
7
3
9
9
8
2
4
1
8
8
9
9
9
3
4
MAX
MIN
MAX
MIN
MAX
MIN
MAX
MIN

8
7
3
9
9
8
2
4
1
8
8
9
9
9
3
4
MAX
MIN
MAX
MIN
MAX
MIN
MAX
MIN
≤8

8
7
3
9
9
8
2
4
1
8
8
9
9
9
3
4
MAX
MIN
MAX
MIN
MAX
MIN
MAX
MIN
7

8
7
3
9
9
8
2
4
1
8
8
9
9
9
3
4
MAX
MIN
MAX
MIN
MAX
MIN
MAX
MIN
7
≥7

8
7
3
9
9
8
2
4
1
8
8
9
9
9
3
4
MAX
MIN
MAX
MIN
MAX
MIN
MAX
MIN
7
≥7
≤3

8
7
3
9
9
8
2
4
1
8
8
9
9
9
3
4
MAX
MIN
MAX
MIN
MAX
MIN
MAX
MIN
7
≥7
≤3

8
7
3
9
9
8
2
4
1
8
8
9
9
9
3
4
MAX
MIN
MAX
MIN
MAX
MIN
MAX
MIN
7
7
≤3

8
7
3
9
9
8
2
4
1
8
8
9
9
9
3
4
MAX
MIN
MAX
MIN
MAX
MIN
MAX
MIN
7
7
≤3
≤7

8
7
3
9
9
8
2
4
1
8
8
9
9
9
3
4
MAX
MIN
MAX
MIN
MAX
MIN
MAX
MIN
7
7
≤3
≤7
≤9

8
7
3
9
9
8
2
4
1
8
8
9
9
9
3
4
MAX
MIN
MAX
MIN
MAX
MIN
MAX
MIN
7
7
≤3
≤7
8

8
7
3
9
9
8
2
4
1
8
8
9
9
9
3
4
MAX
MIN
MAX
MIN
MAX
MIN
MAX
MIN
7
7
≤3
≤7
8
≥8

8
7
3
9
9
8
2
4
1
8
8
9
9
9
3
4
MAX
MIN
MAX
MIN
MAX
MIN
MAX
MIN
7
7
≤3
≤7
8
≥8

8
7
3
9
9
8
2
4
1
8
8
9
9
9
3
4
MAX
MIN
MAX
MIN
MAX
MIN
MAX
MIN
7
7
≤3
7
8
≥8

8
7
3
9
9
8
2
4
1
8
8
9
9
9
3
4
MAX
MIN
MAX
MIN
MAX
MIN
MAX
MIN
7
7
≤3
7
8
≥8
≥7

8
7
3
9
9
8
2
4
1
8
8
9
9
9
3
4
MAX
MIN
MAX
MIN
MAX
MIN
MAX
MIN
7
7
≤3
7
8
≥8
≥7
≤1

8
7
3
9
9
8
2
4
1
8
8
9
9
9
3
4
MAX
MIN
MAX
MIN
MAX
MIN
MAX
MIN
7
7
≤3
7
8
≥8
≥7
≤1
deep cutoff

8
7
3
9
9
8
2
4
1
8
8
9
9
9
3
4
MAX
MIN
MAX
MIN
MAX
MIN
MAX
MIN
7
7
≤3
7
8
≥8
≥7
≤1
deep cutoff
≤8

8
7
3
9
9
8
2
4
1
8
8
9
9
9
3
4
MAX
MIN
MAX
MIN
MAX
MIN
MAX
MIN
7
7
≤3
7
8
≥8
≥7
≤1
deep cutoff
8

8
7
3
9
9
8
2
4
1
8
8
9
9
9
3
4
MAX
MIN
MAX
MIN
MAX
MIN
MAX
MIN
7
7
≤3
7
8
≥8
≥7
≤1
deep cutoff
8
8

8
7
3
9
9
8
2
4
1
8
8
9
9
9
3
4
MAX
MIN
MAX
MIN
MAX
MIN
MAX
MIN
7
7
≤3
7
8
≥8
≥7
≤1
deep cutoff
8
8
≤8

8
7
3
9
9
8
2
4
1
8
8
9
9
9
3
4
MAX
MIN
MAX
MIN
MAX
MIN
MAX
MIN
7
7
≤3
7
8
≥8
≥7
≤1
deep cutoff
8
8
≤8
≤9

8
7
3
9
9
8
2
4
1
8
8
9
9
9
3
4
MAX
MIN
MAX
MIN
MAX
MIN
MAX
MIN
7
7
≤3
7
8
≥8
≥7
≤1
deep cutoff
8
8
≤8
9

8
7
3
9
9
8
2
4
1
8
8
9
9
9
3
4
MAX
MIN
MAX
MIN
MAX
MIN
MAX
MIN
7
7
≤3
7
8
≥8
≥7
≤1
deep cutoff
8
8
≤8
9
≥9

8
7
3
9
9
8
2
4
1
8
8
9
9
9
3
4
MAX
MIN
MAX
MIN
MAX
MIN
MAX
MIN
7
7
≤3
7
8
≥8
≥7
≤1
deep cutoff
8
8
≤8
9
≥9

8
7
3
9
9
8
2
4
1
8
8
9
9
9
3
4
MAX
MIN
MAX
MIN
MAX
MIN
MAX
MIN
7
7
≤3
7
8
≥8
≥7
≤1
deep cutoff
8
8
8
9
≥9

8
7
3
9
9
8
2
4
1
8
8
9
9
9
3
4
MAX
MIN
MAX
MIN
MAX
MIN
MAX
MIN
7
7
≤3
7
8
≥8
8
≤1
deep cutoff
8
8
8
9
≥9

6 листьев можно не рассматривать — экономим 6 операций
В двух узлах нет необходимости в принципе рассчитывать значения листьев — экономим много операций
Результат

Поменять порядок узлов не меняя топологии, чтобы не происходило отсечений

Ответ

Альфа-Бета поиск, напишите порядок вычисления узлов

Ответ: e f m o p i j

Что изменится, если начальные значения
alpha = 2, beta = 7 ? (было e f m o p i j )

Ответ: было e f m o p i j, стало e o p i j

Какой вершине соответствует наилучший ход?

Ответ: b

Какие узлы не будут рассмотрены альфа-бета алгоритмом в идеальном случае?

Будут рассмотрены только узлы n, p, r, s, j
Финальное значение пути: n

Спасибо за внимание!
Решаем Quiz

Задача 1: Используя чистый Минимакс алгоритм определить, какой из трех возможных ходов Максимайзер должен выбрать в вершине A? Какое финальное значение будет в вершине А?

Задача 1: ответ

Задача 2: Выполнить Минимакс поиск с альфа-бэта отсечением и перечислить порядок оцененных узлов

Задача 2: ответ

Задача 3:
Предположив, что
статический оценщик на дереве глубиной 2
выдал значения вершин такие же,
как алгоритм Минимакс в задаче 1,
нарисовать переупорядоченное дерево до глубины 2

Задача 3: ответ

Задача 4:
Какое множество оценок приведёт к пересортировке на втором уровне дерева из задачи 3?
E = 5 F = 8 G = 6 H = 7 I = 1 J = 3
E = 5 F = 7 G = 3 H = 2 I = 8 J = 9
E = 3 F = 9 G = 8 H = 5 I = 1 J = 10
E = 3 F = 7 G = 9 H = 2 I = 3 J = 4

Задача 4: ответ
E = 5 F = 8 G = 6 H = 7 I = 1 J = 3

Задача 5:
Используя статические оценки из предыдущей задачи,
запустить альфа-бэта поиск.
Сколько вершин придётся статически оценить
в результате этого
(включая вершины, оцененные на втором уровне)?