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:
- maximizing player calls
negamaxHandler
- each top level call to
negamax
innegamaxHandler
should minimize
The correct function call ended up being
-negamax(child, depth-1, −∞, +∞, -1)
, although thenegamaxHandler
function needed to be changed:With
negamaxHandler
being called asnegamaxHandler(−∞, +∞, 1)
.