int Quies(int alpha, int beta, int
side, int xside)
{
int score;
TMove move;
score = Evaluate(side);
if(score > alpha)
alpha = score;
if(alpha >= beta)
return beta;
move = GenerateAndSortAllCapture(side);
while(move &&
(alpha < beta))
{
MakeMove(move);
score = -Quies(-beta,-alpha,xside,side);
UnMakeMove(move);
if(score > alpha) alpha = score;
move = move->next;
}//while
return alpha;
}
Как видите, параметра глубины у нас нет. Взятия рассматириваются до
конца. Список взятий должен быть отсортирован. Наиболее крупные приращения
оценки должны идти сначала. Также взятие пешка*ладья имеет больший приоритет,
чем ферзь*ладья.
Если смотреть из пре-узла, то мы ограничиваем максимум у каждого хода
статической оценкой. Некоторые перемещения, тем не менее, имеет смысл просмотреть
далее вместе со взятиями. В шахматах это в первую очередь шахи. Все остается
по старому, только у шахов мы не ограничиваем максимум.
int StaticSearch(int alpha, int
beta, int side,
int xside,int qdepth)
{
TMove move;
int score,nextDepth,
check;
if(qdepth <= 0)
return Quies(alpha,beta,side,xside);
GenerateAndSortAllMoves(side);
while(move = NextMove())
{
MakeMove(move);
check = Check(xside);
nextDepth = qdepth – 1;
if(check) nextDepth = qdepth;
if(!check && Evaluate(side) <= alpha)
score = alpha; //статическое отсечение
else
score = -StaticSearch(-beta,-alpha,xside,side,nextDepth);
UnMakeMove(move);
if(score > alpha) alpha = score;
If(alpha >= beta) return alpha;
}//while
return alpha;
}
Функция статического поиска вызывается после основного AlphaBeta поиска и qdepth как правило равен 2.. Основная задача этой функции - более углубленный просмотр шахов и сглаживание эффекта горизонта за счет статического отсечения. Некоторые программисты при единственном ответе на шах увеличивают глубина на 1 ( по крайней мере, до некоторой глубины). Чтобы данная функция считала точнее, желательно главное изменение рассматривать первым. Впрочем, это не единственный вариант статического поиска. В качестве оценки для отсечения можно использовать не только статическую оценку после хода, но и результат недействительного перемещения. Мы делаем 2 хода подряд и это засчитывается как наш возможный максимум.
int SelectivSearch(int alpha, int
beta, int side,
int xside,int qdepth)
{
TMove move;
int score,nextDepth,
check;
if(qdepth <= 0)
return Quies(alpha,beta,side,xside);
GenerateAndSortAllMoves(side);
while(move = NextMove())
{
MakeMove(move);
check = Check(xside);
nextDepth = qdepth – 1;
if(check) nextDepth = qdepth;
if(!check && SelectivSearch(alpha,beta,side,xside,qdepth-4)
<= alpha)
score = alpha; //Null-Move CutOff
else
score = -SelectivSearch(-beta,-alpha,xside,side,nextDepth);
UnMakeMove(move);
if(score > alpha) alpha = score;
If(alpha >= beta) return alpha;
}//while
return alpha;
}
Лучше этого для шахмат, пожалуй, никто ничего не придумал.