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:
negamaxHandler
negamax
in negamaxHandler
should minimizeThe 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)
.