Главная » Алгоритмы, Игры » Сокращенное вычисление

0

Я использовал этот прием сам, но не относился к нему серьезно. Каково же было мое удивление, когда я увидел, что он используется в программах, за­нимающих первые строчки в рейтинге. Существует эвристика нулевого хо­да, позволяющая, основываясь на сокращенном поиске, отсечь неперспек­тивные ветви дерева. Мы пропускаем ход противника после нашего хода, делаем еще один сокращенный поиск, и если оценка все равно не улучшает alpha, то узел можно подрезать. Ожидается, раз мы сделали два хода подряд и не улучшили alpha, то если противник сделает ход, мы его подавно не улучшим. LazyEval работает по-другому. Мы ищем не на полную глубину, а на сокращенную.

D Текущая оценка после хода должна быть не больше alpha, мы не выпол­няем сокращенный поиск для всех узлов. Это зависит от alpha-предела, который постоянно уточняется.

?    Используют поле роста оценки — margin. {…}

MakeMove();

if(score + margin <= alpha) tryLazyEval;

?   Данный ход не должен быть взятием, шахом, и вообще, не должен рас­ширяться.

{…}

MakeMove(); score = Evaluate (); if(score+margin <= alpha && moveNotCapture && notCheck &&

)

tryLazyEval;

Метод очень хорошо взаимодействует с хеш-таблицей. Мы постоянно пере­бираем на глубину depth-2 и упорядочиваем хеш. Данная методика называ­ется Internal Iterative Deepening (Внутренние итеративные углубления). Только мы пользуемся результатом сокращенного счета и характеристикой узла, чтобы подрезать дерево.

Если наша программа уточняет главную строку изменения, то неточность LazyEval вообще сведена к минимуму.

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

#define L 2

int ALphaBeta(int alpha,int beta, int depth, bool lazyEval) {

if(depth <= 0) return Quies(alpha,beta); Generate ();

while(moveList) {

MakeMove();

extend = extansiens(); //приращение глубины

nextDepth = depth-1;

margin = wPawn/2; //полпешки

if(!lazyEval            && //не поиск сокращенной глубины

Evaluate)) + margin <= alpha && notCheckO && //не шах

moveNotCapture && //не взятие extend ==0  && //узел не расширяется

-ALphaBeta(-beta,-alpha,depth-l-L,true) <= alpha

)

{

tmp = alpha; )else{

tmp = -ALphaBeta(-beta,-alpha,nextDepth+extend,LazyEval);

}

UnMakeMove();

if(tmp > alpha) alpha = tmp; if(alpha >= beta) break;

}//while

return alpha;

}

Все это требует вдумчивого отношения. На последних полуходах полный перебор превращается в некий статический поиск. Если коэффициент зату­хания LazyEval равен 1, то на последних полуходах будет очень похоже на Futility pruning. Это значит, что если оценка после хода с учетом поля роста не улучшает alpha, подрезаемся без проверок.

Погрешность программы, в которой сокращается глубина не полного ши­ротного поиска, а выборочного, сведена к минимуму. При некоторой на­стройке, чтобы подрезать узел, достаточно взять из хеша оценку старой ите­рации. Даже если margin = о, поиск на глубину N не всегда вырождается в поиск на глубину N—2 или N—1.

Литература:

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

По теме:

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