minimaxnegamax

What is the difference between Minimax and Negamax?

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?

Solution

  • 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)