Measure the effect of searching the best moves first.
What to build
A program that counts the leaves alpha-beta examines in a tree as given and in the same tree with perfect move ordering.
Requirements
- Tree format, MAX/MIN levels and the pruning rule (alpha ≥ beta, children left to right) as in the alpha-beta exercise.
- Perfect ordering sorts every MAX node's children by minimax value from high to low and every MIN node's from low to high, keeping ties in their original order. Print
value V,leaves in given order Aandleaves in best order B.
Input
One line: the tree.
Output
Three lines.
Constraints
At most 100 leaves.
Example
Input:
((3 12 8) (2 4 6) (14 5 2))
Output:
value 3
leaves in given order 7
leaves in best order 5
Why it works
When the best reply is examined first, alpha and beta reach their final values at once, so every later sibling is cut off as early as possible.
Examples
((3 12 8) (2 4 6) (14 5 2))
value 3 leaves in given order 7 leaves in best order 5
(((1 2) (3 4)) ((5 6) (7 8)))
value 6 leaves in given order 6 leaves in best order 5
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
First compute every node's minimax value; then build a reordered copy of the tree in which each MAX node's children are sorted from highest to lowest value and each MIN node's from lowest to highest.
Hint 2
Use a stable sort, so children with equal values keep their original order, and run the same alpha-beta counter on both trees.
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 minimax(node, is_max):
if isinstance(node, int):
return node
values = [minimax(child, not is_max) for child in node]
return max(values) if is_max else min(values)
def ordered(node, is_max):
if isinstance(node, int):
return node
sign = -1 if is_max else 1
children = sorted(node, key=lambda child: sign * minimax(child, not is_max))
return [ordered(child, not is_max) for child in children]
def count(node):
seen = [0]
def search(n, alpha, beta, is_max):
if isinstance(n, int):
seen[0] += 1
return n
best = float("-inf") if is_max else float("inf")
for child in n:
v = search(child, alpha, beta, not is_max)
if is_max:
best, alpha = max(best, v), max(alpha, v)
else:
best, beta = min(best, v), min(beta, v)
if alpha >= beta:
break
return best
search(node, float("-inf"), float("inf"), True)
return seen[0]
tree = read()
print("value", minimax(tree, True))
print("leaves in given order", count(tree))
print("leaves in best order", count(ordered(tree, True)))