What is the difference between Minimax and Negamax?

Question

I'm confused with these two. is Negamax just an optimization for minimax? or is Negamax is another search tree algorithm? If negamax is another search tree algorithm, then which one is better?

Mythify

Answer 1

Extracted information from here

Negamax is a simplification of MinMax by using the following property :

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

So, instead of having a conditonnal value compute in minmax, which is the following:

if maximizingPlayer then
    value := −∞
    for each child of node do
        value := max(value, minimax(child, depth − 1, FALSE))
    return value
else (* minimizing player *)
    value := +∞
    for each child of node do
        value := min(value, minimax(child, depth − 1, TRUE))

you have a single line that does the same in Negamax:

value := max(value, −negamax(child, depth − 1, −color))

and the boolean is replaced by the notion (in the article) of color, which is just a value of 1 or -1 to alternate between player turn (if we should minimize or maximize the next turn)

Allveta

This is correct. Just to clarify the initial question, Negamax and Minimax is the "same" algorithm and have the same efficiency/performance. – Earthling

For the non-programmers out there (or programmers who want an easier answer): Negamax is simpler but only works with two player games where the "value" of one player's move has the exact opposite value to the other player. So, if player A does something that gains him a +2.393 strategic value, then player B would see that move having as having a value of -2.393. These are called "zero-sum games." For example chess, go, or connect4. But fox-and-geese or any coop game are not zero-sum. – Zionism

@Zionism I'm not sure this is True. NegaMax and MinMax are pratically the same algorithm, only the implementation changes to compute the value,. The game doesn't need to be zero-sum. Negamax will just use the above property of max(a,b) = -min(-a,-b). This will still try to minimize the opponent move and maximize your moves. – Allveta

@Sami Tahri If the game is not zero-sum (symmetric) such that, for example, a particular state is A for one player but is not -A for the other, then the the Negamax algo will not be properly predicting the opponents moves. Essentially, there would have to be two decision trees, not one, based on whose turn it is. I suppose Negamax could be modified to do that; but that is not how the algorithm is generally described. It would be interesting though, as each player mis-judges the other based on bias. Almost human-like in that sense :-) . – Zionism

@Zionism I think you misunderstand the negamax algorithm. It is not +A or -A, it is still searching the tree for evaluation of moves, minimizing it when it's the opponent one, maximizing it when it's your turn. Because the evaluation is at the leaf, the evaluation function doesn't care at all if the game is symetrical. Again, negamax IS minmax, just with a fancy math trick. – Allveta

Probably not worth discussing too much further; but the "math trick" is that max(a,b) == -min(-a, -b). If each player is evaluating the game differently, then max(a, b) != -min(-a, -b). My experience has been that pretty much breaks Negamax and you must fall back to the more general Minimax. But, perhaps I'm not considering some border case. – Zionism

The math trick is independant of evaluation ... – Allveta

I'll finally add: Minmax (Negamax and alpha/beta) algorithm is independant of the evaluation function. Your game have state, you declare an evaluation function for a state, that's all, minmax will evaluate all possible state maximize which final state at the end will be good for you. The evaluation is responsible for choosing next move, wether the game is symetrical or not. Still minmax will optimize the choice. – Allveta