Аротсечение. 
Символический искусственный интеллект: математические основы представления знаний

В Минимаксе порождение позиций и их оценка отделены друг от друга. Сначала происходит порождение, а только потом это порождение оценивается. Можно производить одновременную оценку прямо во время порождений, чтобы не порождать ничего лишнего. Такая процедура называется а-p-отсечение.

Этот механизм, видимо, был настолько необходим и актуален в середине XX в., что его разработками занялись многие ученые по всему миру. Сейчас сложно сказать, кто является автором этой процедуры, судя, но всему, она изобреталась неоднократно. Самуэль (A. Samuel) и другие исследователи независимо предлагали ранние версии этого алгоритма. Джон Маккарти (J. McCarthy) также выдвигал подобные идеи на Дармудском семинаре в 1956 г. Наш соотечественник А. Брудно независимо открыл алгоритм и опубликовал свои результаты в 1963 г.

Александр Львович Брудно, 1918—2009 — советский ученыйпрограммист.

Работал в команде наиболее талантливых программистов своего времени, занимавшихся игровыми задачами, задачами распознавания и диагностики, эвристическим программированием.

«Профессор Александр Львович Брудно работал на клавиатуре компьютера одним пальцем со скоростью символ в минуту, но более блестящего алгоритмиста мне в своей жизни видеть не приходилось».

(В. Р. Сигунов)

В 1965 г. в своей книге «Программирование в содержательных обозначениях» писал:

«Владение вычислительной техникой становится и станет элементом культуры человека».

Рассмотрим простой модельный пример, поясняющий основную идею а-p-отсечения. Пусть имеется некоторая игра, поддерево поиска которой имеет вид, как на рис. 3.21 (слева). Предположим, мы раскрыли и оценили только левое поддерево рассматриваемого узла (в нем есть единственная позиция, и ее оценка равна 7). Поскольку игрок Мах всегда выбирает узел с наибольшим значением оценочной функции, то вне зависимости от нераскрытого поддерева справа оценка корневой позиции будет > 7. Теперь рассмотрим выбор хода для игрока Min (рис. 3.21, справа). Пусть из двух возможных позиций раскрыта только одна (ее оценка 4). Поскольку игрок Min выбирает узел с наименьшим значением функции, то оценка выбранного хода будет < 4.

Рис. 3.21. Поддеревья некоторой игры.

Продолжим эти рассуждения и изучим рис. 3.22.

После рассмотрения правого поддерева узла, соответствующего ходу Min, известно, что его оценка не превзойдет 4. Однако при рассмотрении части левого поддерева оказывается, что оценка его корня будет > 7.

Это значит, что проводить дальнейшее раскрытие узлов в левом поддереве нс имеет смысла, гак как у игрока Min уже сеть заведомо лучший вариант. Поэтому происходит отсечение оставшейся части левого поддерева.

Рис. 3.22. Пример отсечения поддерева некоторой игры.

Приведенный пример формализуется следующим образом.

Пусть, а — граница снизу для значения оценки в данном узле, р — граница сверху для значения оценки в данном узле.

Заметим, что значение, а для Мах узла не могут уменьшаться, а значение р для Min не могут увеличиваться при любом раскрытии узлов. Следовательно, имеют место следующие правила.

• 1. Можно не искать из данного узла Min, если его верхняя оценка р меньше или равна нижней оценке, а для любого его Мах родителя.
• 2. Можно не искать из данного узла Мах, если его нижняя оценка, а больше или равна верхней оценке р для любого его Min родителя.

Обратите внимание, что формульная запись проверяемого неравенства для отсечения формально одна и та же: в первом случае (3 р, но смысл эти формулы имеют различный. В первом случае, для узла Min, мы берем только что полученную оценку Р и сравниваем ее с оценками, а для вышележащих узлов Мах. Во втором случае, для узла Мах, мы берем только что полученную оценку, а и сравниваем ее с оценками Р для вышележащих узлов Min. Однако в обоих случаях выполнение неравенства является основанием для отсечения.

Пример для игры в крестики-нолики приведен на рис. 3.23.

Порождение и оценивание производятся следующим образом. Сначала производится порождение трех узлов второго уровня. Потом производится порождение пяти узлов третьего уровня в левом поддереве и получается оценка -1 для узла второго уровня. При этом можно для корневого узла первого уровня сразу определить нижнюю оценку, а = -1. Далее начинается порождение узлов третьего уровня в среднем поддереве. Первый же узел имеет оценку -1, что дает верхнюю оценку р = — 1 и выполнение неравенства отсечения. Мы видим, что четыре узла на третьем уровне можно не порождать — их порождение не изменит оценки остальных узлов. В правом поддереве никакого отсечения не происходит — неравенство не выполняется.

Рис. 3.23. а-p-отсечение для игры в крестики-нолики.