Run alpha-beta pruning on a game tree and measure what it saves.
What to build
A program that computes a game tree's value with alpha-beta pruning and counts the leaves it examines.
Requirements
- The tree format is the one from the minimax exercise: brackets, numbers as leaves, the root is MAX and levels alternate. Children are searched left to right, and the remaining children are skipped as soon as alpha ≥ beta.
- Print
value V, leaves evaluated E of L, where L is the total number of leaves.
Input
One line: the tree.
Output
One line.
Constraints
At most 100 leaves.
Example
Input:
((3 12 8) (2 4 6) (14 5 2))
Output:
value 3, leaves evaluated 7 of 9
Why it works
Once a node is known to be worse for the player choosing above it than an option already found, its other children cannot change the decision.
Examples
Example 1 · Input
((3 12 8) (2 4 6) (14 5 2))
Expected output
value 3, leaves evaluated 7 of 9
Example 2 · Input
(1 2 3)
Expected output
value 3, leaves evaluated 3 of 3
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Pass alpha and beta down; at a MAX node raise alpha, at a MIN node lower beta, and stop looking at children when alpha ≥ beta.
Hint 2
Count a leaf only when the search actually reaches it.
Solution
Show one correct solution (try it yourself first)
import re
tokens = re.findall(r"\(|\)|-?\d+", input())
leaves = sum(1 for t in tokens if t not in "()")
def read():
token = tokens.pop(0)
if token != "(":
return int(token)
children = []
while tokens[0] != ")":
children.append(read())
tokens.pop(0)
return children
evaluated = 0
def alphabeta(node, alpha, beta, is_max):
global evaluated
if isinstance(node, int):
evaluated += 1
return node
best = float("-inf") if is_max else float("inf")
for child in node:
v = alphabeta(child, alpha, beta, not is_max)
if is_max:
best = max(best, v)
alpha = max(alpha, v)
else:
best = min(best, v)
beta = min(beta, v)
if alpha >= beta:
break
return best
value = alphabeta(read(), float("-inf"), float("inf"), True)
print(f"value {value}, leaves evaluated {evaluated} of {leaves}")