Главная » Игры, Теория » MTD(f)

0

Много было попыток сделать невозможное — решить проблему перебора. Одна из таких попыток — – Замечено, что перебор с нулевым окном выполняется быстрее:

int alpha = …

int beta = alpha+1;

score = AlphaBeta(alpha,beta);

if (score >= beta) alpha = score;

else if(score <= alpha) beta = score;

Так как реальная оценка неизвестна, но лежит в интервале от -infinity до +infinity, то можно производить двоичный поиск с нулевым окном, по­ка alpha и beta не сойдутся. Это и есть основная идея :

int MTDF(int depth) {

int min = -INFINITY; int max = INFINITY;

int test = Evaluate();//статическая оценка позиции

while (min < max) {

int tmp = AlphaBeta(test,test+1,depth);

if(tmp > test) {

min = tmp; test = min; ) else {

max = tmp; test = max-1;

}

}

Функция AlphaBeta должна вернуть, кроме оценки, и лучший ход. Он запи­сывается, только если возвращаемый результат больше alpha. Можно преду­смотреть проверку, которая выполняет повторный перебор, если результат последней итерации был меньше или равен test. Для используется alpha-beta с амортизацией отказов. Метод возвращает результат не всегда из alpha-beta диапазона, может вернуть отсечку:

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

int score = -INFINITY; //возвращаемое значение if(depth <= 0) return Evaluate(); Generate ();

while(MoveList) {

MakeMove();

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

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

1

return score;

}

Данный алгоритм может совершить множество проходов, если есть большое разнообразие оценок. Например, каждый проход может увеличивать ниж­ний предел только на 1. Чтобы избежать зависания функции, можно раз­бить промежуток между min и max пополам:

int SearchMT(int depth) {

int min = -INFINITY; int max = INFINITY; test = (max+min)/2; do{

int tmp = AlphaBeta(test,test+1,depth);

if(tmp > test) {

min = tmp; test = min; } else { max = tmp;

test = max-1; }

if(max-min >= 2) test = (max+min)/2; (while(min < max);

return min; }

Для определения начального значения и сокращения числа проходов можно совместить функцию счета с итеративными углублениями:

int MTDF(int depth, int test) {

int min = -INFINITY; int max = INFINITY;

while (min < max) {

int tmp = AlphaBeta(test,test+1,depth);

if(tmp > test) {

min = tmp; test = min; ) else { max = tmp;

test = max-1; }

}

return min; )

void IterativeDeepening(void) {

int test = Evaluate(); int depth = 1;

while ( depth <= MAX_DEPTH && ITimeUpO) {

test = MTDF(depth,test);

depth++; }

}

В MTD(0 можно задать точность, с какой мы извлекаем оценку. Чем ближе нулевое окно к действительному результату, тем дольше считает функция AlphaBeta. Если нам не существенна разница ± 1, то можно сужать промежу­ток поиска до этой величины. Если промежуток поиска сделать равным максимальной стратегической оценке, то алгоритм сосчитает только мате­риал. На практике желательно считать точно, иначе теряется всякий смысл.

Алгоритм использует множество повторных переборов и нуждается в хоро­шей хеш-таблице для ускорения поиска. Здесь кроется еще одна проблема . Она связана с нестабильностью поиска. Если поиск с нулевым ок­ном вернул оценку больше или равную beta, то это не всегда наш минимум. Следующий поиск может вернуть оценку меньше минимума. Теоретически этого быть не должно, но из-за использования результатов из хеша и искус­ственных отсечений (Forward pruning) это вполне возможно.

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

Литература:

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

По теме:

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