NegaScout

int AlphaBetaWhite(int alpha, int beta, int depth)// поиск за белых
{
int tmp;
int max = -INFINITY;// устанавливаем локальный максимум в минус бесконечность
if(depth <= 0) return Evaluate();// на предельной глубине считаем оценку позиции
GenerateWhite ();// генерируем список ходов за белых
while(moveList)// списки ходов локальные, т.е. действуют только в узле
{
     MakeMoveWhite;// делаем ход
     if(i== 0)// первый ход перебираем с полным окном, потому что априорно считаем его лучшим
    {
        tmp = AlphaBetaBlack (alpha, beta, depth-1);
     }else{
        tmp = AlphaBetaBlack (alpha, (alpha+1), depth-1);// остальные пытаемся отсечь перебором с нулевым окном
        if ((value > alpha)&&(value < beta))// если результат все-таки улучшает alpha и beta,то перебираем снова
       {
          tmp = AlphaBetaBlack (tmp, beta, depth-1);// считаем от tmp до beta, так как найденный tmp – наш минимум
       }
     }
UnMakeMoveWhite;// откатываем ход
if(tmp > max) max = tmp; //
if(tmp > alpha) alpha = tmp; //
if(max >= beta) return max; //
}
return max;
}

int AlphaBetaBlack (int alpha, int beta, int depth)// поиск за черных
{
int tmp;
int min = INFINITY;
if(depth <= 0) return Evaluate();
GenerateBlack ();
while(moveList)
{
     MakeMoveBlack;
     tmp = AlphaBetaWhite (alpha, beta, depth-1);
     if(i== 0)// первый ход перебираем с полным окном, потому что априорно считаем его лучшим
    {
       tmp = AlphaBetaWhite (alpha, beta, depth-1);
     }else{
       tmp = AlphaBetaWhite ((beta-1), beta, depth-1);// остальные пытаемся отсечь перебором с нулевым окном
       if ((value > alpha)&&(value < beta))// если результат все таки улучшает alpha и beta,то перебираем снова
      {
         tmp = AlphaBetaWhite (alpha, tmp, depth-1);// считаем от alpha до tmp, так как найденный tmp – наш максимум
      }
    }
    UnMakeMoveBlack;
    if(tmp < min) min = tmp; //
    if(tmp < beta) beta = tmp; //
    if(min <=alpha) return min; //
}
return min;
}

Весь алгоритм строится на том, что мы пробуем перебрать с нулевым окном, т.е. beta = alpha
+ 1. Считается, что при нулевом окне отсечек будет гораздо больше и это позволит быстрее
просмотреть неинтересные ветки.

Почему alpha + 1, а не alpha + 2 или alpha + 0.1 - я не знаю. Тут надо думать. Также,
почему диапазон alpha,alpha + 1 назвали нулевым окном для меня загадка. Может умные люди
подскажут, в чем тут дело.

Считается, что NegaScout дает до 50% ускорения. Звучит довольно заманчиво особенно на
длинных контролях. Однако, меня ждал облом.
Надо сказать, что NegaScout в моей программе почти не дает ускорения, а в некоторых позициях
даже слегка притормаживает. В большинстве случаев речь идет об 5-10% , так что можно было бы
и не напрягаться. Несмотря на то, что он почти бесполезен, выкинуть жалко, тем более что он
все-таки слегка ускоряет счет.