Главная » Алгоритмы, Игры » NegaScout

0

— самый популярный на сегодня алгоритм грубого усилия. Он чрезвычайно прост и дает некоторое (до 50%) ускорение, не внося ника­кой дополнительной погрешности в вычисление. Он очень хорошо сочета­ется с современными атрибутами шахматных программ — хеш-таблицами. не предусматривает извлечения строки главного изменения или других хитростей. Основная его идея следующая: прежде чем исследовать любой узел, мы его пытаемся сначала отсечь за перебором с нулевым окном (от alpha до alpha+1). Если результат счета улучшает alpha, тогда перебираем снова. Учитывается также один тонкий момент. Если мы перебрали с нуле­вым окном и получили результат больше, чем alpha, то это — наш мини­мум, и мы можем смело повторить перебор с пределами не от alpha до beta, а от полученной оценки до beta. Само собой, если этот наш минимум уже сравнялся с beta, то уточнять его не нужно. Можно сразу вернуть beta. Это очень похоже на Principal Variation, за исключением повышения alpha при повторном переборе. Первый ход в каждом узле рассматривается с полным окном. Какой это ход? Это зависит от генератора перемещений. Это может быть ход из хеш-таблицы, хорошее взятие или любой другой ход. Алгорит­мом это не определяется. Просто этот ход первый.

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

int tmp; PMove move;

if (depth <= 0) return EvaluateO;

//начало списка ходов

move = Generate();

//первый ход с полным окном

////////// first move search /////////

MakeMove;

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

if(tmp > alpha) alpha = tmp; move = move->next;

////////// end first move search //////

while(move && alpha < beta) {

MakeMove;

tmp = -(-(alpha+1),-alpha,depth-1);

if(tmp > alpha && tmp < beta) {

tmp = -(-beta,-tmp,depth-1);

}

UnMakeMove;

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

}

Привожу другое описание:

int (position p; int alpha, beta) {

int a,b,t,i;

determin successors p_l,…., p_w of p; if(w == 0) return Evaluate(p); a = alpha; b = beta;

for(i = 1; i <= w; i++) {

t = -(p_i,-b,-a);

if(t > a && t < beta && i > 1 && d < maxDepth-1)

а = -(p_i,-beta,-t) ; a = max(a,t); if(a == beta) return a; b = a + 1;

}

return a;

}

Предлагаемый вариант ждет сходимости а == beta. На практике это доволь­но опасно. Перебор продолжается, пока alpha меньше beta. Ключевой идеей является попытка отсечь узел перебором с нулевым окном, преж­де чем рассматривать его с полным alpha-beta диапазоном. Так как мы не отслеживаем явно Principal Variation и осуществляем грубое усилие, то мож­но и не перебирать первый ход с полным окном. В некоторых случаях будет чуть медленнее, в некоторых — чуть быстрее, а в среднем — то же самое.

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

iht score = -INFINITY, tmp;

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

while(moveList && alpha < beta) {

MakeMove;

tmp = -Search(-(alpha+1),-alpha,depth-1);

if(tmp > alpha && tmp <-beta) {

tmp = -Search(-beta,-tmp,depth-1);

}

UnMakeMove;

if(tmp > score) score = tmp; if(score > alpha) alpha = score; )//while return score;

}

Здесь есть два тонких момента. Это использование результата отсечки при повторном переборе:

if(tmp > alpha && tmp < beta) {

tmp = -(-beta,-tmp,depth-1);

Если бы мы не использовали отсечку, надо было бы написать:

if(tmp > alpha && tmp < beta) {

tmp = -(-beta,-alpha,depth-1);

}

Также функция возвращает не alpha, а результат отсечки score. Он может быть и меньше alpha. Это фрагмент alpha-beta алгоритма с амортизацией отказов. На практике от этих тонкостей толка никакого. Они только усили­вают нестабильность поиска. Хотя теоретически нельзя отрицать возмож­ность ускорения в исключительном случае. Без этих тонкостей программ­ный код выглядел бы следующим образом:

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

int tmp;

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

while(moveList ss alpha < beta) {

MakeMove;

tmp = -Search(-(alpha+1),-alpha,depth-1);

if(tmp > alpha && tmp < beta) {

tmp = -(-beta,-alpha,depth-1);

}

UnMakeMove;

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

}

Все эти манипуляции с alpha-beta окном мы проводили в преузле, если так можно выразиться. Если смотреть из следующего узла, то попытки отсечь за alpha в преузле выглядели бы как попытки отсечь за beta в нашем узле. Это немного неудобно, но суть дела от этого не меняется.

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

int score = -INFINITY, tmp,

newAlpha, searchNumber = 0; PMove move,fi rs t;

if(depth <= 0) return Evaluate О; newAlpha = beta – 1; //начало списка перемещений move = first = Generate();

loop:

while(moveList) (

MakeMove;

tmp = -Search(-beta,-newAlpha); UnMakeMove;

if(tmp > score) score = tmp; if(score > newAlpha) newAlpha = score; if(newAlpha >= beta) return newAlpha; }//while searchNumber++;

//до этой точки программа доходит редко

if(score > alpha && searchNumber == 1) {

beta = score; score = -INFINITY; newAlpha = alpha; move = first; goto loop;

}

return score; } / /function

Эту задачу можно рассматривать как своего рода упражнение для ума. По­пробуйте ответить: чем этот алгоритм отличается от ? Чего я толь­ко ни слышал по этому поводу.

Литература:

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

По теме:

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