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

0

Автор идеи — Эрнст Хайнц, применивший ее в своей программе DarkThough. Сама идея очень проста. На последних двух полуходах перебора оценка не­точна, и можно, основываясь на текущей статической оценке позиции и характеристике узла, подрезать целую ветвь поиска. Нельзя с определен­ностью сказать, что вносит погрешность, т. к. в двух послед­них узлах программа и так постоянно ошибается. Можно сказать, что ошибки будут, но несколько другого характера.

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

Как видно, всю это очень напоминает нулевой ход. Только на последних двух полуходах поиск недействительного перемещения не вызывается, если поле роста достаточно велико. Для нормальной работы хватит величины максимального стратегического приращения (полпешки).

Почему работает? Дело в том, что в позиции ожидается наш ход. Можно рассуждать так: если мы не сделали хода и имеем преимущест­во в материале (текущая оценка больше beta на величину материального приращения), то неужели мы не найдем такой ход, который, если и не со­хранит нашего материального преимущества, то хотя бы приведет к его ми­нимальной потере? Это маловероятно. Даже если бы мы выполнили полный поиск и не подрезались, то, т. к. поиск идет в двух граничных узлах, нельзя сказать с уверенностью, что его результат будет точнее. Мы имеем матери­альное преимущество и рассчитываем, что дополнительный ход поможет нам сохранить оценку. Дополнительной проверкой служит ход в эту пози­цию: он не шах, не взятие и т. д. Текущая строка является потенциально слабой строкой. Выглядит алгоритм примерно так:

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

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

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

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

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

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

notCapture(node) && //не взятие

!InCheck(node)       && //не шах

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

)

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

)

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

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

PMove move = Generate();

while(moveList) {

MakeMove(move);

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

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

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

notCheck(move)         && //ход не объявляет шах

notExtensiens(move) && //узел после хода не расширяется notCheckOwnKing  && //наш король не под шахом

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

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

)

//пропустим вычисление tmp = alpha;

}else{

tmp = -AlphaBeta(…); {…}

}

UnMakeMove(move) ; move = move->next; }//while return alpha;

}

Если мы отсекаем из преузла, то дополнительным условием служит отсутст­вие шаха нашему королю. Это подразумевает, что мы хотим получить точ­ный ответ на шах противника и не подрезаемся. Текущая оценка после хода и поле роста не должны улучшать alpha. Эффективность очень неплохая. Мы отсекаем множество статических поисков в форсиро­ванных вариантах без практического ухудшения качества счета. Если в кон­це перебора вызываются сложные (или плохо написанные) форсированные поиски, то ускорение может быть и большим. Можно не подрезаться, пока не выяснили все насчет мата для обеих сторон, но это дело вкуса.

Литература:

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

По теме:

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