AI: Count the leaves alpha-beta examines

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}")

Lesson: Alpha-beta pruning and chance →