Главная » Игры, Теория » Поиск стремления

0

(Aspiration search) — еще одна идея ускорения alpha-beta перебора. Из корня дерева перебора функция AlphaBeta вызывается с преде­лами alpha = -infinity, beta = infinity, где infinity — максимально воз­можный результат.

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

score = Evaluate(); window = . . .; alpha = score – window; beta = score + window; score = AlphaBeta(alpha,beta,depth); if(score <= alpha){ alpha = -INFINITY;

score = AlphaBeta(alpha,beta,depth); }else if(score >= beta){ beta = INFINITY;

score = AlphaBeta(alpha,beta,depth);

}

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

score = Evaluate(); window = …; //полпешки depth = 1;

while(depth < MAX_DEPTH && !TimeUp()) {

alpha = score – window; beta = score + window; score = AlphaBeta(alpha,beta,depth); if(score <= alpha){ alpha = -INFINITY;

score = AlphaBeta(alpha,beta,depth); }else if(score >= beta){ beta = INFINITY;

score = AlphaBeta(alpha,beta,depth);

}

depth++;

}

Ожидается, что повторных пересчетов будет немного. Реальное ускорение от данного алгоритма достигается использованием стандартной процедуры alpha-beta. Если же у нас NegaScout и хеш-таблица, то практическое уско­рение отсутствует. Хеш при окне стремления будет не таким полным, а

NegaScout выжимает из alpha-beta практически все. При NegaScout или Principal Variation нам нужно быстрее сосчитать первый ход (или главную строку изменения, оставшуюся от предыдущей итерации). Остальные пере­мещения будут просматриваться с нулевым окном. Дальнейший поиск будет идти значительно быстрее.

Некоторые люди используют Aspiration search в корне дерева дополнительно к NegaScout. Это дело вкуса. Хочется только отметить, что экспоненциаль­ный рост дерева перебора с увеличением глубины поиска сохраняется в Aspiration search при любом окне стремления, и даже при нулевом окне.

Литература:

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

По теме:

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