AlphaBeta является основным улучшением полного перебора. Подробное описание алгоритма было дано в известной статье Кнута и Мура (1975г.).  Из-за отсутствия информации алгоритм множество раз открывался заново (как и NegaMax).  Основная идея в следующем: нам не нужно исследовать обязательно все дерево перебора для получения лучшего хода (и его оценки). Дело в том, что в NegaMax мы завышаем оценка в каждом узле. Если результат перебора очередного хода меньше запомненной лучшей оценки, то он отбрасывается и не запоминается. Таким образом, переборы некоторых вариантов оказываются совершенно не нужны, так как они в результате не завышают оценку в узле. Если назвать лучшую оценку для узла alpha, а лучшую оценку противника, достигнутую до этого в строке - beta, то мы видим, что величины alpha и beta - меняются местами для каждого следующего узла в строке. Также видно, что если в строке мы достигли некоторой alpha, и в некотором узле далее в строке, который обсчитывается для противника, мы уже достигли beta, то перебор можно прекратить и вернуть эту оценку или beta, что безразлично. Когда перебор вернется в точку где была получена beta (для того узла это будет alpha), то результат будет отвергнут, так-как не улучшается alpha. Таким образом, мы можем не доводя перебор до конца, подрезать некоторую очевидную бесполезность.

int AlphaBeta(int alpha, int beta, int depth)
{
   int tmp;

   if(depth <= 0)
     return Evaluate();

   Generate();
   while(moveList)
   {
     tmp = -AlphaBeta(-beta,-alpha,depth-1);
     if(tmp > alpha) alpha = tmp;
     if(alpha >= beta) return beta;
   }//while
   return alpha;
}

Данный алгоритм при наилучшем порядке ходов исследует sqrt(N) позиций, где N - количество позиций, исследуемых при полном переборе. Это эквивалентно перебору на глубину в 2 раза больше, за то-же время.