- ALGORITHMS //
- DECISION MAKING //
-
Minimax
Dummy / Minimax
Maximize score, while taking into account that you will try to minimize my score.
""" Minimax algorithm - Dummy
Binary tree, with only two choices, left and right.
When is Max turn on list node, we evaluate each node children
on `not player` choise, because Min player will try to minimize
the Max score.
"""
def minimax(node, player):
if isinstance(node, int): # Base case
return node
lv = minimax(node[0], not player) # Recursive
rv = minimax(node[1], not player) # Recursive
if player:
best_score = max(lv, rv)
else:
best_score = min(lv, rv)
return best_score
tree = [[9, 5], [-3, -2]]
print('Max to play / Best score =', minimax(tree, True))
print('Min to play / Best score =', minimax(tree, False))
"""
Max to play / Best score = 5
Min to play / Best score = -2
"""
Prunning / Alpha Beta
In the maximising case, we could avoid visiting a subtree.
""" Minimax algorithm - Alpha beta prunning
This algorithm will hava a lot of work on big trees.
Some parts are irellevant and don't need to be traverse.
When maximising, check if value is too high when compared to beta.
When minimising, check if value is too low when compared to alpha.
When alpha is greater or equal than beta, it means that the current player
has found a better move in different branch.
"""
def minimax(node, player, alpha=float("-inf"), beta=float("+inf")):
if isinstance(node, int):
return node
print('Node:', node)
v = float("-inf") if player else float("+inf")
for k in node:
sub_val = minimax(k, not player, alpha, beta)
if (player):
if sub_val > v:
v = sub_val
alpha = max(alpha, v)
else:
if sub_val < v:
v = sub_val
beta = min(beta, v)
# if (player and v >= beta) or (not player and v <= alpha): break
if alpha >= beta: # pruning condition
break
return v
tree = [
[
[
[3, 4]
],
[
8,
[-2, 10],
5,
],
],
7,
]
print('Max to play')
move = minimax(tree, True) # [-2, 10] is ignored
print('Max best move =', move, '\n')
print('Min to play')
move = minimax(tree, False)
print('Min best move =', move, '\n')
"""
Max to play
Node: [[[[3, 4]], [8, [-2, 10], 5]], 7]
Node: [[[3, 4]], [8, [-2, 10], 5]]
Node: [[3, 4]]
Node: [3, 4]
Node: [8, [-2, 10], 5]
Max best move = 7
Min to play
Node: [[[[3, 4]], [8, [-2, 10], 5]], 7]
Node: [[[3, 4]], [8, [-2, 10], 5]]
Node: [[3, 4]]
Node: [3, 4]
Node: [8, [-2, 10], 5]
Node: [-2, 10]
Min best move = 5
"""
Last update: 357 days ago
