Главная » Игры, Теория » Razoring

0

Идея та же, что и Futility pruning. Только там подрезались два граничных узла, а теперь мы возьмемся за два следующих. Поле роста (margin) теперь больше и равно максимальной величине материального приращения. Обыч­но вполне достаточно величины одной королевы. Условия подрезки дерева:

?    мы в четырех конечных узлах поиска;

?    ненулевой ход и другой поиск сокращенной глубины;

?    текущая оценка больше beta на величину margin;

?    ход в данную позицию не взятие;

?    нет шаха нашему королю;

?   данный узел не расширяется (речь идет о выборочных продлениях).

Если эти условия соблюдены, мы можем подрезать целую ветвь и возвра­тить beta. Есть еще один прием, называемый сокращением глубины поиска. Он работает обратно выборочным продлениям. Если при выборочных про­длениях мы не сокращаем глубину поиска в определенных узлах, то теперь, наоборот, вместо того, чтобы подрезать целую ветвь статической оценкой, мы просто сокращаем глубину поиска в данном узле. Делается это в надеж­де на то, что если строка поиска станет вдруг интересной, она опять расши­рится, и оценка будет более точной. Вряд ли имеет смысл рассматривать жертву ферзя или аналогичных по ценности фигур на такой глубине. В по­давляющем большинстве случаев это деградирующие строки поиска, и их можно отсечь. Риска не больше, чем при нулевом ходе. Эффективность несколько меньше, чем Futility pruning. Вот примерная схема алго­ритма:

margin = wQueen; //поле роста

int AlphaBeta(PMove node, int depth, int alpha, int beta, …) {

extend = extensiens(); //выборочные продления depth += extend;

if( InullMove         && //не нулевой ход

depth <=4            && //если 4 последних полухода

!extend              && //узел не расширяется

notCapture(node) && //не взятие !InCheck(node) && //не шах

Evaluate() – margin >= beta //текущая оценка – поле роста

)

depth—; //сокращаем глубину поиска

// return beta; //возвратим beta {…}

Generate();

while(moveList) {

(…}

)

return ^lpha;

)

Если смотреть из преузла, то к условиям проверки можно добавить шах на­шему королю. Итак, если ход не объявляет шах, и нет шаха нашему королю:

int AlphaBeta(int depth, int alpha, int beta, …) {

PMove move = Generate(); while(moveList) (

MakeMove(move);

if(InullMove             && //не нулевой ход

depth-1 <=4           && //4 последних узла

notCapture(move)      && //ход не взятие

notCheck(move)        && //ход не оС^ьявляет шах notExtensiens(move) && //узел после хода не расширяется

notCheckOwnKing       && //наш король не под шахом

Evaluate() + margin <= alpha //оценка после хода +

// поле роста не улучшает alpha

)

{

//сократим глубину поиска на 1

//на 1 она сокращается в любом случае

nextDepth = depth-2;

(else nextDepth = depth-1+extensiens(move);

tmp = -ALphaBeta(nextDepth,-beta,-alpha,. . .) ;

UnMakeMove(move); {. . . }

move = move->next; (//while return alpha;

)

Приемы вроде требуют некоторой настройки в конечной програм­ме, и результат сильно зависит от конкретной реализации. Если программа расширяет строки с взятиями, то она строит огромные деревья поиска, и их нужно подрезать такими или аналогичными приемами. В результате мы по­лучаем результат, по качеству сопоставимый с полным перебором, хотя и не просматривали все дерево поиска.

Литература:

Корнилов Е. Н.  Программирование шахмат и других логических игр. — СПб.: БХВ-Петербург, 2005. – 272 е.: ил.

По теме:

  • Комментарии