Главная » Игры, Теория » Сокращения глубины поиска

0

Зачем еще и сокращения, когда есть выборочные продления? Не одно ли это и то же? Выборочные сокращения позволяют довольно гармонично на­строить поиск, а продления все равно остаются, и все мирно уживаются друг с другом.

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

Например, самая типичная схема статического поиска:

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

//если превышена максимальная глубина, вернем //приблизительную оценку позиции горизонта

if (depth <= 0) return Quies(…); //получим список перемещений Generate ();

while(moveList && alpha < beta) (

r_score = … //оценка после хода if (move_does_check || //если шах

move_is_capture I I        //если взятие

r_score > alpha)

{

MakeMove();

tmp = -Search(-beta,-alpha,depth-1,…); UnMakeMove();

if(tmp > alpha) alpha = tmp; ) //if

nextMove(); }//while

return alpha; )//end funct ion

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

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

if(depth <= 0) return Quies(); Generate ();

while(moveList && alpha < beta) {

//сокращение глубины счета extend = -1;

if(move_does_check) extend = 0; //если шах else iff !move_is_capture && //не взятие alpha >= r_score) extend = -2;

MakeMove();

tmp = -Search(-beta,-alpha,depth+extend,…); UnMakeMove();

if(tmp > alpha) alpha = tmp;

}//while

return alpha; }//function

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

if( alpha > -INFINITY+100 && beta < INFINITY-100) {

}

Можно ввести поле роста (margin) и эмулировать полный перебор:

if(r_score – margin >= alpha) { … }

Значение margin в последних двух полуходах можно взять равным половине пешки. На близких к корню дерева полуходах значение поля возрастает. Это мы получим Futility pruning и Razoring, вместе взятые.

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

Литература:

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

По теме:

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