Главное изменение

Оценка позиции в шахматах довольно условна. Чтобы достичь приемлемого качества игры, программа должна глубже обдумывать те строки , которые она собирается поиграть. Идеальным является хранение всего дерева перебора в памяти, а лучшие ходы сдвигаются при переборе на верх списка для каждого узла. Если мы просчитали на глубину 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]
}