Minimax Alpha-Beta Pruning Added Pseudo Code
With Alpha-Beta Pruning added, it is less confusing to have both maximizing and minimizing methods. The player whose move it is calls the maximizing method, which calls the minimizing method, which calls the maximizing method, etc until the end search depth is reached.
Minimax-Max Pseudocode
minimaxMax(gameSituation, depthSoFar, alpha, beta)
If depthSoFar = this.maxDepthSearch OR gameSituation is end of game
heurEval = ratePosition(this.colorPlaying)
return minimax results object with heurEval and null path
else
successors = moveGenerate(this.maxWidthSearch) /// possible moves
if no successors
heurEval = ratePosition(this.colorPlaying)
return minimax results object with heurEval and null path
else
alpha beta cutoff = false
loop through successors
if not at alpha beta cutoff
create game situation that would result from move
resultForSucc = minimaxMin(adjusted game situation – adjusted board,
opposite color playing, depth+1, alpha, beta
newValue = resultForSucc.getHeurVal()
curr path = put current successor in front of best path returned
by call to minimaxMin
if newValue > alpha (i.e. is better than best value so far )
alpha = newValue
update best value and best path
END IF
If alpha >= beta // We can cut off search below any maximizing node having an
// alpha value greater than or equal to the beta value of any of
// its minimizing ancestors
Alpha beta cutoff = true
Ensure best value is set to alpha in case never go into above branch
END IF
END IF
END LOOP
If not at alpha beta cutoff
If object to return hasn’t been set up
(because never cut off but never got new best value so far
– because didn’t beat alpha passed down)
Set up object to return with best value = alpha
END IF
END IF
END IF
END IF
Include adjusted game situation for best move in the object to return (so caller knows result of move selected)
Return object with best value and best path
Minimax-Min Pseudocode
minimaxMin(gameSituation, depthSoFar, alpha, beta)
If depthSoFar = this.maxDepthSearch OR gameSituation is end of game
heurEval = ratePosition(this.colorPlaying)
return minimax results object with heurEval and null path
else
successors = moveGenerate(this.maxWidthSearch) /// possible moves
if no successors
heurEval = ratePosition(this.colorPlaying)
return minimax results object with heurEval and null path
else
alpha beta cutoff = false
loop through successors
if not at alpha beta cutoff
create game situation that would result from move
resultForSucc = minimaxMax(adjusted game situation – adjusted board,
opposite color playing, depth+1, alpha, beta
newValue = resultForSucc.getHeurVal()
curr path = put current successor in front of best path returned
by call to minimaxMax
if newValue < beta (i.e. is better than best value so far – for minimizer )
beta = newValue
update best value and best path
END IF
If alpha >= beta // We can cut off search below any minimizing node having a
// beta value less than or equal to the alpha value of any of
// its maximizing ancestors
Alpha beta cutoff = true
Ensure best value is set to beta in case never go into above branch
END IF
END IF
END LOOP
If not at alpha beta cutoff
If object to return hasn’t been set up
(because never cut off but never got new best value so far
– because didn’t beat beta passed down)
Set up object to return with best value = beta
END IF
END IF
END IF
END IF
Include adjusted game situation for best move in the object to return (so caller knows result of move selected)
Return object with best value and best path