What is the difference between Minimax and Negamax?

user_14996453 0
Viewed 2628

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?

negamax minimax
1 Answers

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)

user_100341770
Related