artificial-intelligenceminimaxnegamaxtree-search

What would Negamax' initial function call look like were it to minimize root node rather than maximize?


Negamax typically looks like the below:

function negamax(node, depth, α, β, color) is
    if depth = 0 or node is a terminal node then
        return color × the heuristic value of node
    childNodes := generateMoves(node)
    childNodes := orderMoves(childNodes)
    value := −∞
    foreach child in childNodes do
        value := max(value, −negamax(child, depth − 1, −β, −α, −color))
        α := max(α, value)
        if α ≥ β then
            break (* cut-off *)
    return value

And the initial call is negamax(rootNode, depth, −∞, +∞, 1) if the maximizing player called it.

I've implemented Negamax in a way where the maximizing player calls it, but each rootNode is one of the maximizing players moves:

function negamaxHandler() is
    bestValue := −∞
    bestNode := null
    childNodes := generateMoves(currentGameState)
    foreach child in childNodes do
        value := negamax(child, depth-1, ???, ???, ???)
        if value > bestValue then
            bestValue := value
            bestNode := child
    return bestNode

Because Negamax returns a value, I instead want a board state (move). So I do the first level of Negamax manually so I can parse where the best move is. But for what values should I call negamax on? To be more declarative, if maximizing player called negamaxHandler, should negamaxHandler call:

negamax(child, depth-1, −∞, +∞, 1)
-negamax(child, depth-1, −∞, +∞, 1)
negamax(child, depth-1, +∞, −∞, -1)
-negamax(child, depth-1, +∞, −∞, -1)

Or something else? To clarify:


Solution

  • The correct function call ended up being -negamax(child, depth-1, −∞, +∞, -1), although the negamaxHandler function needed to be changed:

    function negamaxHandler(α, β, color) is
        bestValue := −∞
        bestNode := null
        childNodes := generateMoves(currentGameState)
        foreach child in childNodes do
            value := -negamax(child, depth-1, -β, -α, -color)
            if value > bestValue then
                bestValue := value
                bestNode := child
            α := max(bestValue, α)
            if α ≥ β then
               break
        return bestNode
    

    With negamaxHandler being called as negamaxHandler(−∞, +∞, 1).