Главная » Игры, Теория » Статический поиск

0

в том или ином виде используется во всех программах. Обычно он называется форсированным вариантом, хотя статический поиск может рассматривать не только форсированные ходы. В чем основная идея статического поиска? В процедуре поиска можно для каждого узла получить немедленную статическую оценку. Обычно функцией, вычисляющей эту оценку, является Evaluate. Что такое статическая оценка? Представьте, что фигуры замерли, и ходов больше нет, просто подсчитывается текущее со­стояние. Неважно, что белому королю на следующем ходу поставят мат. Движения нет, и этого функция Evaluate не увидит. Оценка для белых рав­на сумме всех весов и позиционных факторов белых фигур за вычетом всех весов и позиционных факторов черных. Позиционные факторы не опреде­лены однозначно. Есть средние значения для каждой фигуры, могут учиты­ваться структуры пешек, безопасность короля, проходные пешки, близость легких фигур к центру, близость королевы к королю противника и т. д. Нам в данном случае не важен характер позиционной оценки. Важно, что она

берется для неподвижных фигур. Можно, для простоты, ориентироваться на следующие таблицы, действительные для всех фигур:

int black[64] = {

1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,

17.18.19.20.21.22.23.24,            

25.26.27.28.29.30.31.32,            

33.34.35.36.37.38.39.40,            

41.42.43.44.45.46.47.48,            

49.50.51.52.53.54.55.56,            57,58,59,60,61,62,63,64 };

int white[64] = {

64.63.62.61.60.59.58.57,            

56.55.54.53.52.51.50.49,            

48.47.46.45.44.43.42.41,            

40.39.38.37.36.35.34.33,            

32.31.30.29.28.27.26.25,            24,23,22,21,20,19,18,17, 16,15,14,13,12,11,10, 9,

8, 7, 6, 5, 4, 3, 2, 1 } ;

В нашем простейшем случае для всех белых фигур одна таблица, и позици­онный фактор в ячейке таблицы, где стоит фигура. Функция выглядит сле­дующим образом:

int ALphaBeta(

int alpha, //наш максимум

int beta, //противника

int depth, //глубина

int player, //цвет наших фигур

int opponent //цвет фигур противника

)

(

if(depth <= 0) return Evaluate(player); PMove move = GenerateAllMoves(player);

while(move) {

MakeMove(move);

int tmp = -AlphaBeta(-beta,-alpha,depth-1,opponent,player); UnMakeMove(move); if(tmp > alpha) alpha = tmp; if(alpha >= beta) break;

}

return alpha;

}

Первый вызов может быть таким:

#define INFINITY (10*wQueen) //десять ферзей

ALphaBeta(-INFINITY,INFINITY,6,WHITE, BLACK);

Мы вызвали функцию AlphaBeta на глубину 6 с бесконечными пределами alpha и beta. Как видите, все достаточно просто. Как далеко сумеет просчи­тать такая функция? Число рассматриваемых позиций при полном переборе равно S в степени N, где S — среднее количество ходов в позиции, N — просчитываемая глубина. При alpha-beta отсечениях минимальное количе­ство рассматриваемых позиций равно корню квадратному из этого числа.

Когда depth = о, мы вызываем статическую оценочную функцию. Слишком глубоко полным перебором мы просчитать не сможем, и поэтому в конце вместо статической оценочной функции Evaluate о можно вызвать функ­цию статического поиска Quies о. Она устроена примерно так же, как и ос­новная процедура поиска, только alpha в ней повышается статической оценкой:

int Quies(

int alpha, //наш максимум

int beta, //противника

int depth, //глубина

int player, //цвет наших фигур

int opponent //цвет фигур противника

)

{

//статическая оценка узла

int score = Evaluate(player);

if(depth <= 0) return score;

//повышаем alpha статической оценкой

if(score > alpha) alpha = score;

if(alpha >= beta) return beta; //или alpha

PMove move = GenerateAllMoves(player);

while(move) {

MakeMove(move);

int tmp = -Quies(-beta,-alpha,depth-1,opponent,player);

UnMakeMove(move);

if(tmp > alpha) alpha = tmp;

if(alpha >= beta) break;

}

return alpha;

}

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

int Quies(

int alpha, //наш максимум

int beta, //противника

int depth, //глубина

int player, //цвет наших фигур

int opponent //цвет фигур противника

)

{

//статическая оценка узла int score = Evaluate(player);

if(depth <= 0) return score; //повышаем alpha статической оценкой if(score > alpha) alpha = score; if(alpha >= beta) return beta; //или alpha PMove move = GenerateAllCaptures(player);

while(move) {

MakeMove(move);

int tmp = -Quies(-beta,-alpha,depth-1,opponent,player); UnMakeMove(move); if(tmp > alpha) alpha = tmp; if(alpha >= beta) break;

}

return alpha;

}

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

Если смотреть из преузла, то функция не повышает alpha, а понижает beta, или свой потолок роста. Выглядит это так:

int Quies(

int alpha, //наш максимум

int beta, //противника

int depth, //глубина

int player, //цвет наших фигур

int opponent //цвет фигур противника

)

{

if(depth <= 0) return Evaluate(player); //повышаем alpha статической оценкой if(score > alpha) alpha = score; if(alpha >= beta) return beta; //или alpha PMove move = GenerateAllMoves(player);

while(move) {

int nextBeta; // beta

int nextScore; //оценка узла после хода

MakeMove(move);

nextScore = Evaluate(player);//оценка после хода nextBeta = beta;

if(nextScore < beta) nextBeta = nextScore;

if(nextBeta <= alpha) {

tmp = alpha; //отсечка }else(

int tmp = -Quies(-nextBeta,-alpha,depth-1,opponent,player) ;

}

UnMakeMove(move);

if(tmp > alpha) alpha = tmp;

if(alpha >= beta) break;

}

return alpha;

}

В этой функции мы делаем то же самое, что и раньше, только в преузле. Если оценка после хода меньше beta, мы понижаем beta. Как видите, пока мы не ввели ничего нового, только делаем статическую корректировку в предыдущем узле. На этом примере видно, что при статическом поиске мы для каждого хода ограничиваем прирост его захватываемой частью. Напри­мер, взяли пешку, максимум ограничен, и если дальше в строке будет выиг­рыш больше пешки, программа этого не увидит. Максимум прироста огра­ничен приростом хода в узле. То же самое относится и к позиционной оценке. Если новый максимум (nextBeta) меньше или равен alpha, то нет смысла считать далее, можно сразу принять оценку хода как alpha. Заметьте, что отрицательный ход автоматически вычеркнется, если значение alpha до перемещения уже повышено текущей оценкой.

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

int Quies(

int alpha, //наш максимум

int beta, //противника

int depth, //глубина

int player, //цвет наших фигур

int opponent //цвет фигур противника

)

{

if(depth <= 0) return Evaluate(player); //повышаем alpha статической оценкой if(score > alpha) alpha = score; if(alpha >= beta) return beta; //или alpha PMove move = GenerateAllMoves(player); while(move) (

int nextBeta; //новое значение beta int nextScore; //оценка узла после хода MakeMove(move);

nextScore = Evaluate(player);//оценка после хода nextBeta = beta; if( !inCheck(move) && nextScore < beta

)

nextBeta = nextScore;

if(nextBeta <= alpha) {

tmp = alpha; //отсечка )else{

int tmp = -Quies(-nextBeta,-alpha,depth-1,opponent,player);

}

UnMakeMove(move);

if(tmp > alpha) alpha = tmp;

if(alpha >= beta) break;

)

Функция inCheck — детектор шахов. Если ход объявляет шах королю про­тивника, мы не ограничиваем его максимум. Такой статический поиск, хотя и считает приближенно, но увидит уже гораздо больше. Заменим функцию inCheck функцией Extensiens, которая возвращает 1, ИЛИ true, когда ход продлевается. Мы можем просмотреть глубже не только шахи, а взятия или атаки. Чем больше ходов мы продлеваем, тем точнее результат, но тем мед­леннее идет счет. Введем еще переменную, аргумент функции Quies, кото­рая показывает, продлевался ли ход в преузле. Назовем ее ext.

int Quies(

int alpha, //наш максимум

int beta, //противника

int depth, //глубина

int player, //цвет наших фигур

int opponent,//цвет фигур противника

bool ext //продлевался ли ход в преузле

)

{

if(depth <= 0) return Evaluate(player); //повышаем alpha статической оценкой if(score > alpha) alpha = score; if(alpha >= beta) return beta; //или alpha PMove move = GenerateAllMoves(player);

while(move) {

int nextBeta; //новая beta

int nextScore; //оценка узла nocyie хода

int nextExt; //продлевается ли ход

MakeMove(move);

nextScore = Evaluate(player);//оценка после хода nextBeta = beta; nextExt = Extensiens(move); if( !nextExt      &&

nextScore < beta

)

nextBeta = nextScore;

if(nextBeta <= alpha) {

tmp = alpha; //отсечка )else(

int tmp = -Quies(-nextBeta,-alpha,depth-1, opponent,player,nextExt);

UnMakeMove(move);

if(tmp > alpha) alpha = tmp;

if(alpha >= beta) break;

}

return alpha;

}

Теперь мы в каждом узле знаем, продлевался ли ход в предыдущем. Что это нам дает? Если ход продлевался в предыдущем узле, и максимум этого хода не был ограничен, мы можем рассмотреть точный ответ на него. Например, если противник нам объявил шах, мы можем иметь более точный ответ на шах, а не ограниченный максимумом. Выглядит это примерно так:

int Quies(

int alpha, //наш максимум

int beta, //противника

int depth, //глубина

int player, //цвет наших фигур

int opponent,//цвет фигур противника

bool ext //продлевался ли ход в преузле

)

{

if(depth <= 0) return Evaluate(player); //завышаем alpha статической оценкой if(score > alpha) alpha = score; if(alpha >= beta) return beta; //или alpha PMove move = GenerateAllMoves(player);

while(move) {

int nextBeta; //новая beta

int nextScore; //оценка узла после хода

int nextExt; //продлевается ли ход

MakeMove(move);

nextScore = Evaluate(player);//оценка после хода nextBeta = beta; nextExt = Extensiens(move); if( !Ext      &&

!nextExt            &&

nextScore < beta

)

nextBeta = nextScore;

if(nextBeta <= alpha) {

tmp = alpha; //отсечка

}else{

int tmp = -Quies(-nextBeta,-alpha,depth-1, opponent,player,nextExt);

}

UnMakeMove(move);

if(tmp > alpha) alpha = tmp;

if(alpha >= beta) break;

}

return alpha;

}

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

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

int Quies(

int alpha, //наш максимум

int beta, //противника

int depth, //глубина

int player, //цвет наших фигур

int opponent,//цвет фигур противника

bool ext, //продлевался ли ход в преузле

int evalu //текущая оценка узла

)

{

if(depth <= 0) return evalu;

//завышаем alpha статической оценкой

if(score > alpha) alpha = score;

if(alpha >= beta) return beta; //или alpha

PMove move = GenerateAllMoves(player);

while(move) {

int nextBeta; //новая beta

int nextScore; //оценка узла после хода

int nextExt; //продлевается ли ход

MakeMove(move);

nextScore = evalue + //текущая оценка

delEvaluate(player);//приращение при ходе

nextBeta = beta;

nextExt = Extensiens(move);

if( !Ext   && //нет шаха нашему королю

!nextExt &&    //ход не объявляет шах противнику

ImoveNotCapture(move) //ход не взятие

)

(

//нет хода

tmp := evalue; //оценка узла до хода }else{

if (

!nextExt && nextScore < beta

)

nextBeta = nextScore;

if(nextBeta <= alpha) f

tmp = alpha; //отсечка )else{

int tmp = -Quies(-nextBeta,-alpha,depth-1,

opponent,player,nextExt.-nextScore);

}

UnMakeMove(move);

}

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

)

return alpha;

}

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

int Quies(

int alpha, //наш максимум

int beta, //противника

int depth, //глубина

int player, //цвет наших фигур

int opponent //цвет фигур противника

)

{

//статическая оценка узла int score = Evaluate(player);

if(depth <= 0) return score; //если вышли за beta

if(score >= beta) return beta; //или alpha PMove move = GenerateAllMoves(player);

while(move) {

MakeMove(move);

int tmp = -Quies(-beta,-alpha,depth-1,opponent,player) , UnMakeMove(move); if(tmp > alpha) alpha = tmp; if(alpha >= beta) break;

}

return alpha;

}

Если смотреть из преузла, то это выглядит так:

int Quies(

int alpha, //наш максимум

int beta, //противника

int depth, //глубина

int player, //цвет наших фигур

int opponent //цвет фигур противника

)

{

if(depth <= 0) return Evaluate(player); //завышаем alpha статической оценкой if(score > alpha) alpha = score; if(alpha >= beta) return beta; //или alpha PMove move = GenerateAllMoves(player);

while(move) {

int nextBeta; //новая beta

int nextScore; //оценка узла после хода

MakeMove(move);

nextScore = Evaluate(player);//оценка после хода

if(nextScore <= alpha) {

tmp = alpha; //отсечка )else{

int tmp = -Quies(-beta, -alpha, depth-1,opponent,player);

}

UnMakeMove(move);

if(tmp > alpha) alpha = tmp;

if(alpha >= beta) break;

}

return alpha;

}

Это уже имитация полного перебора. Пока текущая оценка в alpha-beta ко­ридоре, отсечки нет. Можно оставлять некоторое поле роста (margin). Мож­но отсечку оговорить дополнительными условиями.

Литература:

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

По теме:

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