Skip to content

Instantly share code, notes, and snippets.

@adpoe

adpoe/minimax.py Secret

Last active Jun 5, 2020
Embed
What would you like to do?
Python implementation of the Minimax AI-algorithm
##########################
###### MINI-MAX ######
##########################
class MiniMax:
# 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
self.currentNode = None # GameNode
self.successors = [] # List of GameNodes
return
def minimax(self, node):
# first, find the max value
best_val = self.max_value(node) # should be root node of tree
# second, find the node which HAS that max value
# --> means we need to propagate the values back up the
# tree as part of our minimax algorithm
successors = self.getSuccessors(node)
print "MiniMax: Utility Value of Root Node: = " + str(best_val)
# find the node with our best move
best_move = None
for elem in successors: # ---> Need to propagate values up tree for this to work
if elem.value == best_val:
best_move = elem
break
# return that best value that we've found
return best_move
def max_value(self, node):
print "MiniMax-->MAX: Visited Node :: " + node.Name
if self.isTerminal(node):
return self.getUtility(node)
infinity = float('inf')
max_value = -infinity
successors_states = self.getSuccessors(node)
for state in successors_states:
max_value = max(max_value, self.min_value(state))
return max_value
def min_value(self, node):
print "MiniMax-->MIN: Visited Node :: " + node.Name
if self.isTerminal(node):
return self.getUtility(node)
infinity = float('inf')
min_value = infinity
successor_states = self.getSuccessors(node)
for state in successor_states:
min_value = min(min_value, self.max_value(state))
return min_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