Skip to content

Instantly share code, notes, and snippets.

@kkweon

kkweon/minimax.py

Created January 28, 2017 22:12
Show Gist options
  • Save kkweon/ddec4d2786e25d63d2f9b9d62adb336f to your computer and use it in GitHub Desktop.
Save kkweon/ddec4d2786e25d63d2f9b9d62adb336f to your computer and use it in GitHub Desktop.
Download ZIP
Minimax Implementation
Raw
minimax.py
"""Implementation of Figure 5.2 in Artificial Intelligence: A Modern Approach
[MINIMAX Algorithm]
AIMA p.164 Ch.5 Adversarial Search
function Minimax(state) returns a value
if terminal-test(state):
return utility(state)
if player(state) == MAX:
return max( Minimax(RESULT(state, action)) for every action in Action(s) )
if player(state) == MIN:
return min( Minimax(RESULT(state, action)) for every action in Action(s) )
end function
[Figure 5.2 Description]
There are A~L states. "A" state is the root of the tree.
D,E,F,G,H,I,J,K,L are the terminal nodes of the tree.
Each state except terminal nodes has actions 1, 2, 3.
For instance,
"A" state has 3 actions ('a1', 'a2', 'a3')
"C" state has 3 actions ('c1', 'c2', 'c3')
"D" state has no action
MAX A
|
---------------+--------------------
a1--| a2--| a3--|
MIN B C D
| | |
+---------+------+ +----+-----+ +-----+-------+
b1| b2| b3| c1| c2| c3| d1| d2| d3|
| | | | | | | | |
MAX D(3) E(12) F(8) G(2) H(4) I(6) J(14) K(5) L(2)
"""
STATES = "ABCDEFGHIJKLM"
action_list = [a + b for a in "abcd" for b in "123"]
class Tree:
"""Example Game Tree
Attributes:
player (str): 'min' or 'max'
state (str): state character 'A', 'B', ..., 'L'
value (int): value of the node. At initial only terminal nodes have values
"""
def __init__(self, name="A", value=None, player='max'):
"""Constructor
Args:
name (str): name of the root state "A"
value (int, optional): initialized as None but will be calculated during minimax
player (str, optional): type of player 'min' or 'max'
"""
self.state = name
self.value = value
self._children = []
self.player = player
def add_children(self, other):
"""Add child nodes to the current node
Args:
other (Tree): Other nodes (class(Tree))
"""
self._children.append(other)
def get_children(self):
"""Returns child nodes of the current node
Example:
a = Tree("A")
b = Tree("B")
a.add_children(b)
a.get_children() # returns a list [b]
Returns:
list: [Tree1, ...]
"""
return self._children
@staticmethod
def find_by_state(tree, state):
"""DFS by state name
Args:
tree (Tree): Searchable Tree
state (str): Search node
Returns:
Tree: if found else False
Examples:
a = Tree('a')
b = Tree('b')
a.add_children(a)
Tree.find_by_state(a, 'b') # returns b
"""
if tree.state == state:
return tree
else:
children = tree.get_children()
if len(children) == 0:
return False
for child in children:
attempt = Tree.find_by_state(child, state)
if attempt:
return attempt
return False
def minimax(tree, s):
"""Perform minimax algorithm on Tree
Args:
tree (Tree): searchable tree
s (char): state value
Returns:
int: value if s is in tree else False
Examples:
tree = Tree('A')
tree.add_children(.....) # same structure as in book
minimax(tree, 'A') #returns 3
minimax(tree, 'E') #returns 12
"""
found = Tree.find_by_state(tree, s)
if not found:
return False
if terminal_test(found):
return found.value
if found.player == 'max':
return max([minimax(tree, result(found.state, action))for action in action_list if result(found.state, action) != -1])
if found.player == 'min':
return min([minimax(tree, result(found.state, action))for action in action_list if result(found.state, action) != -1])
def terminal_test(tree):
"""Check if given tree has no child nodes
Args:
tree (Tree): Searchable Trees
Returns:
Bool: True if terminal node else False
"""
return len(tree.get_children()) == 0
def result(s, a):
"""State-Action Map Function(?)
Args:
s (str): State String, A~L
a (str): Action String, a1, a2, a3, c1, c2, ...
Returns:
str: next state if action exists else -1
Examples:
result("A", "a1") => "B"
result("A", "a2") => "C"
result("A", "c1") => -1
result("B", "b1") => "D"
result("B", "a1") => -1
a1 a2 a3 b1 b2 b3 c1 c2 c3 d1 d2 d3
A B C D -1 -1 -1 -1 -1 -1 -1 -1 -1
B -1 -1 -1 E F G -1 -1 -1 -1 -1 -1
C -1 -1 -1 -1 -1 -1 H I J -1 -1 -1
D -1 -1 -1 -1 -1 -1 -1 -1 -1 K L M
B has child nodes
E,F,G = [3, 12, 8]
C has child nodes
H,I,J = [2, 4, 6]
D has child nodes
K,L,M = [14, 5 ,2]
"""
state_result = dict(
[(s, dict([(action, -1)for action in action_list])) for s in STATES])
state_result['A']['a1'] = "B"
state_result['A']['a2'] = "C"
state_result['A']['a3'] = "D"
state_result['B']['b1'] = "E"
state_result['B']['b2'] = "F"
state_result['B']['b3'] = "G"
state_result['C']['c1'] = "H"
state_result['C']['c2'] = "I"
state_result['C']['c3'] = "J"
state_result['D']['d1'] = "K"
state_result['D']['d2'] = "L"
state_result['D']['d3'] = "M"
return state_result[s][a]
def tree_add_helper(tree, **kwargs):
sub_tree = Tree(**kwargs)
tree.add_children(sub_tree)
return tree
def tree_add_multiple(tree, *node_value_list):
for node, value in node_value_list:
tree = tree_add_helper(tree, name=node, value=value, player='max')
return tree
def prepare_figure():
root = Tree("A", player='max')
sub_tree_1 = Tree("B", player='min')
sub_tree_2 = Tree("C", player='min')
sub_tree_3 = Tree("D", player='min')
sub_tree_1 = tree_add_multiple(sub_tree_1, ['E', 3], ['F', 12], ['G', 8])
sub_tree_2 = tree_add_multiple(sub_tree_2, ['H', 2], ['I', 4], ['J', 6])
sub_tree_3 = tree_add_multiple(sub_tree_3, ['K', 14], ['L', 5], ['M', 2])
root.add_children(sub_tree_1)
root.add_children(sub_tree_2)
root.add_children(sub_tree_3)
return root
if __name__ == '__main__':
root = prepare_figure()
assert minimax(root, "A") == 3
assert minimax(root, "E") == 3
assert minimax(root, "F") == 12
assert minimax(root, "B") == 3
assert minimax(root, "C") == 2
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment