Compute minimax values on a small game tree.
What to build
A program that computes the minimax value of a game tree and the best move at the root.
Requirements
- The tree is written with brackets:
(child child …)is a node and a number is a leaf. The root is MAX and the levels alternate. - Print
best move K, value V, where K is the root's child (from 1) with the best value (ties: the first). If the whole tree is a single leaf, printvalue V.
Input
One line: the tree.
Output
One line.
Constraints
At most 100 leaves; values are whole numbers.
Example
Input:
((3 12 8) (2 4 6) (14 5 2))
Output:
best move 1, value 3
Why it works
Each player chooses the child that is best for them, so values pass up the tree: maximum at MAX levels, minimum at MIN levels.
Examples
Example 1 · Input
((3 12 8) (2 4 6) (14 5 2))
Expected output
best move 1, value 3
Example 2 · Input
(1 2 3)
Expected output
best move 3, value 3
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Read the brackets recursively; a node at even depth (the root is depth 0) is MAX, at odd depth MIN.
Hint 2
A number is a leaf with that value.
Solution
Show one correct solution (try it yourself first)
import re
tokens = re.findall(r"\(|\)|-?\d+", input())
def read():
token = tokens.pop(0)
if token != "(":
return int(token)
children = []
while tokens[0] != ")":
children.append(read())
tokens.pop(0)
return children
def value(node, is_max):
if isinstance(node, int):
return node
values = [value(child, not is_max) for child in node]
return max(values) if is_max else min(values)
tree = read()
if isinstance(tree, int):
print(f"value {tree}")
else:
values = [value(child, False) for child in tree]
best = values.index(max(values))
print(f"best move {best + 1}, value {values[best]}")