Alpha-Beta Pruning implementation of the Minimax Algorithm, written in Python.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
########################## | |
###### MINI-MAX A-B ###### | |
########################## | |
class AlphaBeta: | |
# print utility value of root node (assuming it is max) | |
# print names of all nodes visited during search | |
def __init__(self, game_tree): | |
self.game_tree = game_tree # GameTree | |
self.root = game_tree.root # GameNode | |
return | |
def alpha_beta_search(self, node): | |
infinity = float('inf') | |
best_val = -infinity | |
beta = infinity | |
successors = self.getSuccessors(node) | |
best_state = None | |
for state in successors: | |
value = self.min_value(state, best_val, beta) | |
if value > best_val: | |
best_val = value | |
best_state = state | |
print "AlphaBeta: Utility Value of Root Node: = " + str(best_val) | |
print "AlphaBeta: Best State is: " + best_state.Name | |
return best_state | |
def max_value(self, node, alpha, beta): | |
print "AlphaBeta-->MAX: Visited Node :: " + node.Name | |
if self.isTerminal(node): | |
return self.getUtility(node) | |
infinity = float('inf') | |
value = -infinity | |
successors = self.getSuccessors(node) | |
for state in successors: | |
value = max(value, self.min_value(state, alpha, beta)) | |
if value >= beta: | |
return value | |
alpha = max(alpha, value) | |
return value | |
def min_value(self, node, alpha, beta): | |
print "AlphaBeta-->MIN: Visited Node :: " + node.Name | |
if self.isTerminal(node): | |
return self.getUtility(node) | |
infinity = float('inf') | |
value = infinity | |
successors = self.getSuccessors(node) | |
for state in successors: | |
value = min(value, self.max_value(state, alpha, beta)) | |
if value <= alpha: | |
return value | |
beta = min(beta, value) | |
return value | |
# # | |
# UTILITY METHODS # | |
# # | |
# successor states in a game tree are the child nodes... | |
def getSuccessors(self, node): | |
assert node is not None | |
return node.children | |
# return true if the node has NO children (successor states) | |
# return false if the node has children (successor states) | |
def isTerminal(self, node): | |
assert node is not None | |
return len(node.children) == 0 | |
def getUtility(self, node): | |
assert node is not None | |
return node.value |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment