Глубокое -отсечение

Рассмотрим дерево игры на рис. 2.4. Пусть известны оценки f(X) =иf(E) =z..

Докажем следующую лемму.

Лемма 2.3.Еслиf(E), то ветви, исходящие из вершиныDи помеченные штриховой линией, можно отсечь.

Доказательство. Так как игрокB стремится минимизировать оценочную функцию, то для вершиныD будет справедлива следующая оценкаf(D)  f(E)  , а для вершиныC, ход из которой делает игрокA, стремящийся максимизировать оценочную функцию, соответственноf(C)  f(D).

Рассмотрим две возможности:

1. f(C) =f(D), что означаетf(C)  f(E)  , т.е. имеем согласно лемме 2.2 неглубокоеотсечение, означающее неперспективность для игрокаAвообще всех продолжений из вершиныY.

2. f(C)  f(D), что означает неучастие (неперспективность) вершиныD для получения оценкиf(C).

Лемма доказана.

Рис. 2.5 иллюстрирует применение метода - отсечений.

Рис. 2.5. Глубокое-отсечение

Из рис. 2.5 видно, что игроку Aрекомендуется в качестве первого хода выбрать продолжение, ведущее к вершинеX.

Рис. 2.6. Применение метода-отсечений

Табл. 2.1 иллюстрирует процедуру - отсечения.

Таблица 2.1

Заметим, что оценка возрастает при движении по дереву снизу вверх, а оценка, наоборот, убывает.

Приведем сравнительные оценки методов максимина и  отсечений. Пусть оценивается дерево на глубину ходов (уровней)n(для равенства ходов игроковn должно быть четным) и на каждом уровне имеетсяmвариантов выбора. Тогда сложность вычислений равна:

• mⁿдля метода максимина;

• 2m^n/2 для метода-отсечения.

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

К недостаткам рассмотренных методов относятся:

• по сути оба метода не являются стратегиями и базируются на классических переборных алгоритмах с использованием оценочной функции;

• наличие эффекта горизонта, т.е. методы «не видят» выигрыша, который находится за горизонтом (ниже по дереву) оцениваемых вершин.