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

0

Поиск с основным вариантом имеет название (PVS). Мы делаем предположение, что нам известны лучшие ходы в неко­торых узлах. Тогда, если мы нашли такой ход, мы его рассматриваем с пол­ным alpha-beta окном, как при стандартном alpha-beta алгоритме. Ожидает­ся, что ход потенциально хороший и может повысить значение alpha в узле.

Остальные ходы мы условно относим к плохой категории и ожидаем, что они не улучшат значение alpha. Если ход не улучшает alpha, то зачем его рассматривать с полным окном? Мы можем взять данный ход с окном:

newAlpha = alpha; newBeta = alpha+1;

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

//поиск с основным вариантом

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

int tmp;

if(depth <= 0) return Evaluate(); //если нашли хороший ход

if( findPV) {

//делаем перемещение MakeMove;

//ищем с полным окном

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

//восстанавливаем позицию

UnMakeMove;

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

//получим список перемещений //из нашей позиции Generate();

while(moveList && alpha < beta) {

//сделали ход MakeMove;

//просчет с нулевым окном

tmp = -PrincipalVariation)-(alpha+1),-alpha,depth-1); //если эвристика не сработала, и ход улучшает // alpha, то пересчитаем с полным окном if(tmp > alpha && tmp < beta)

tmp = -PrincipalVariation(-beta,-alpha,depth-1); //восстановили позицию UnMakeMove;

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

Основные обозначения:

П alpha — наш максимальный результат, достигнутый в строке просчета до этого;

?    beta — максимальный результат противника;

?    depth — глубина просчета;

П Evaluate — функция, возвращающая статическую оценку позиции;

?    Generate — определяет все перемещения из данной позиции;

?    MakeMove — делает ход;

П unMakeMove — восстанавливает позицию;

?     findpv — ищет заведомо хороший ход.

Как программа ищет потенциально хороший ход? Способ состоит в извле­чении главной строки изменения после каждой итерации. Например: про­считали мы на 5 полуходов и извлекли главную строку изменения. Главная строка изменения, или главное изменение (PV) — это наилучшая игра для обеих сторон, по мнению программы. Когда мы будем при следующей ите­рации перебирать на 6 полуходов, узлы PV будут рассмотрены с полным окном, а остальные мы попытаемся сначала отсечь за alpha с нулевым ок­ном. Это старый, испытанный способ. В настоящее время применяют хеш- таблицы и другие методы для улучшения порядка ходов.

Для понимания работы этого алгоритма мы должны учитывать, что перебор с нулевым окном выполняется быстрее, чем с полным alpha-beta окном. Причина здесь в том, что если окно alpha-beta минимальное, это вызывает гораздо больше отсечек. Principal Variation считает быстрее на практике, чем стандартный метод alpha-beta. Ускорение может достигать 50% и более, осо­бенно в тех случаях, когда главное изменение не сильно отличается от PV предыдущей итерации. Principal Variation является простым и эффективным способом ускорения счета, хотя ускорение даже в два раза не является принципиальным. Это даст нам возможность сосчитать быстрее на глубину N, но мы не сможем сосчитать на глубину N+1, при том же контроле вре­мени.

Можно усовершенствовать приведенный пример с извлечением строки главного изменения и просмотра ее первой при следующей итерации. Если ход PV, рассматриваем с полным окном, если нет — пытаемся отсечь за alpha.

//описатель перемещения typedef struct tagMove{

int source, //откуда пошла фигура

dest; //куда struct tagMove *next; //следующий элемент списка }TMove, *PMove;

//строка перемещений

//если source = dest, то перемещение пустое

//строка всегда заканчивается пустым описателем

#define MAX_LINE 100

typedef TMove TLine[MAX_LINE];

//копирует описатель перемещения

#define COPY_MOVE(movel,move2)\

(move2).source = (movel).source;\

(move2).dest = (movel).dest;

//обнуляет описатель перемещения

#define RESET_MOVE(move)\

(move).source = (move).dest = 0;

//возвращает 1, если описатель перемещения пустой #define IS_ZERRO_MOVE(move)\ ( (move).source = (move).dest) //записывает ход + строка в line

void SaveLine(PMove move, PMove tmpLine, PMove line) {

int n;

//копируем наш ход + строка COPY_MOVE(*move,line[0]) ; n = 0;

while( n < MAX_LINE-2 &&

!ZERRO_MOVE(tmpLine[n]))

{

COPY_MOVE(tmpLine[n],line[n+1]); n++;

}

//запишем пустой описатель //в конец строки RESET_MOVE(line[n+1]);

}

///////////////// VAR /////////////////// //максимальная глубина просчета int maxPly;

//главное изменение от корня дерева перебора

TLine bestLine; I III search

///////////////////

int PrincipalVariation(int alpha, int beta, int ply, //глубина от 0 PMove line,//возврат строки bool PV //главное изменение?

)

{

TLine tmpLine; PMove move; if(ply >= maxPly) return Evaluate(); //если превышен лимит времени if(TimeUp) return …;//любое число //попробуем ход PV

if(PV && !ZERRO_MOVE(bestLine[ply])) {

move = SbestLine[ply]; MakeMove;

RESET_MOVE(tmpLine[0]);

tmp = -PrincipalVariation(-beta,-alpha,ply+l,

tmpLine, true);

UnMakeMove;

if(TimeUp) return …;

if(tmp > alpha) {

alpha = tmp; if(alpha < beta)

SaveLine(move,tmpLine, line);

}

}

//начало списка перемещений move = Generate();

while(move && alpha < beta) {

MakeMove;

RESET_MOVE(tmpLine[0]); //строка пуста tmp = -PrincipalVariation(-(alpha+1),-alpha, ply+1, tmpLine, false);

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

//повторно сбросим строку RESET_MOVE(tmpLine[0]); tmp = -PrincipalVariation(-beta,-alpha, ply+1, tmpLine, false);

}

UnMakeMove;

if(TimeUp) return . . .;

if(tmp > alpha) {

alpha = tmp; //запишем строку if(alpha < beta)

SaveLine(move,tmpLine,line); }//end if

move = move->next; (//while return alpha;

}

Idefine MAX_PLY 16 //итеративные углубления int Iterative Deepening(

PMove bestMove //лучший ход

)

{

int tmp, score;

//сбросим главную строку изменения RESET_MOVE(bestLine[0]);

for(maxPly = 1; maxPly <= MAX_PLY; maxPly++) {

tmp = PrincipalVariation(-INFINITY,INFINITY,0,

bestLine,true);

if(TimeUp) break; score = tmp;

}

//запишем лучший ход

COPY_MOVE(bestLine[0],*bestMove);

return score;

}

В дереве перебора может быть масса отрывочного PV, который никогда не достигнет корня дерева. Оценка в потенциальном узле PV больше alpha, но меньше beta. Существует вариант Principal Variation, который просматривает узел с полным окном, пока не найден хоть один ход PV:

int PrincipalVariation (int alpha, int beta, int depth)

{

int oldAlpha;

if(depth <= 0) return Evaluate(); oldAlpha = alpha; //запомним alpha

Generate () ;

while(moveList && alpha < beta) {

if(alpha == oldAlpha) {

//не было узла PV

tmp = – PrincipalVariation (-beta,-alpha,depth-1); )else{

tmp = – PrincipalVariation (-(alpha+1),-alpha,depth-1); if(tmp > alpha && tmp < beta)

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

}

if(tmp > alpha) alpha = tmp; }//While return alpha;

}

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

Литература:

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

По теме:

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