Оценка позиции в шахматах довольно условна. Чтобы достичь приемлемого качества игры, программа должна глубже обдумывать те строки , которые она собирается поиграть. Идеальным является хранение всего дерева перебора в памяти, а лучшие ходы сдвигаются при переборе на верх списка для каждого узла. Если мы просчитали на глубину 5, то на глубине 6 мы можем уточнять результат. Наиболее оптимальным сочетанием пользы и эффективности является извлечение строки главного изменения, с тем, чтобы глубже исследовать ее на следующей итерации. Строка главного изменение (PV) - это строка, берущая свое начало от корня дерева и оценки всех узлов которой равны лучшей оценки корня, и, кроме того, все узлы имеют оценку больше alpha, но меньше beta для каждого узла. Извлечь строку главного изменения довольно просто.
#define MAXPLY 100
typedef struct{
TMove moves[MAXPLY];
int cnt;
}TLine;
void LineReset(TLine *line)
{
line->cnt = 0;
}
vois LineSave(TLine *source, TLine *dest,
TMove *move)
{
int n;
dest->moves[0] = *move;
dest->cnt = 1;
n = 0;
while( n < source->cnt &&
dest->cnt < MAXPLY)
dest->moves[dest->cnt++]
= source->moves[n++];
}
int ALphaBeta(int alpha, int beta,
int depth, int ply, TLine *line)
{
TMove move;
TLine bestLine;
int score;
if(depth <= 0 ||
ply >= MAXPLY)
return
StaticSearch(alpha,beta,depth,ply);
move = GenerateAndSortAllMoves(side);
while(move)
{
MakeMove(move);
LineReset(bestLine);
score = -AlphaBeta(-beta,-alpha,depth-Extensiens,ply+1,&bestLine);
UnMakeMove(move);
if(score > alpha){
alpha = score;
if(alpha < beta) LineSave(&bestLine,line,move);
else break;
}
move = move->next;
}
return alpha;
}
int d,score;
TLine line,bestLine;
void IterativDeep(void)
{
LineReset(&bestLine);
for(d = 1; (d <
MAXPLY) && !TimeUp(); d++)
{
LineReset(&line);
score = ALphaBeta(-INFINITY,INFINITY,d,0,&line);
if(line.cnt > 0)
memscpy(&bestLine,&line,sizeof(TLine));
if( score > INFINITY-MAXPLY )
break;
}
//выбранный ход в
bestLine.moves[0]
}