difference between negamax and alpha-beta

[Carbec]

Hello,

Sorry for this very beginner question, but what is the difference beteween these 2 ?
I loked at the wiki, but found it is the same, or perhaps i didn't understantood.

thanks for clarification

Philippe

[op12no2]

Hello,

Sorry for this very beginner question, but what is the difference beteween these 2 ?
I loked at the wiki, but found it is the same, or perhaps i didn't understantood.

thanks for clarification

Philippe

They will give you the same result, it's just that negamax is arranged such that you are always maximising the side to move; it's nicer to implement and work with thereafter.

[lithander]

The simplest search algorithm suitable for zero-sum games like chess is minmax which doesn't use pruning at all. You can introduce alpha-beta pruning to the search and you will get the exact same results, but much faster.

Now many programmers don't like to maintaine a minimizing and a maximizing version of their search seperately. Instead they use a variant of minmax which is called negamax which simplifies the implementation of minmax based on the realization that

Code: Select all

max(a,b)=-min(-a,-b)

With that insight applied to the minmax code a single procedure can be used for both sides!

This negamax variant of minmax also supports alpha-beta pruning! And that's what the chess programming wiki refers to as Alpha Beta inside the Negamax Framework and is demonstrated with the following listing:

Code: Select all

int alphaBeta( int alpha, int beta, int depthleft ) {
   if( depthleft == 0 ) return quiesce( alpha, beta );
   for ( all moves)  {
      score = -alphaBeta( -beta, -alpha, depthleft - 1 );
      if( score >= beta )
         return beta;   //  fail hard beta-cutoff
      if( score > alpha )
         alpha = score; // alpha acts like max in MiniMax
   }
   return alpha;
}

[pedrojdm2021]

Alpha-Beta is more like a pruning technique than a complete algorithm. You use alpha-beta to prune some nodes that will result in a faster search.

You can use alpha-beta in minimax. Minimax uses 2 functions to work min() and max().

Negamax is an improvement from minimax, it combines the behavior in one single function, with the same output.

Most engines just uses negamax because is easier to develop and maintain that code, rather than minimax.

There are some other variants that came from negamax like Negascout.