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

Рассмотрим дерево игры на рис. 2.3.

Рис. 2.4. Неглубокое-отсечение

Пусть известны оценки f(X) =иf(C) =z.. Справедлива следующая лемма.

Лемма 2.2.Еслиf(C), то ветви, исходящие из вершиныYи обозначенные штриховой линией, можно отсечь.

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

Мы рассмотрели отсечение, соответствующее выбору игрокаA. Аналогичные рассуждения справедливы и для отсечения в ситуации, когда выбор делает игрокBпри справедливости следующих оценок:f(X) = , f(C) = w  .