AI: How much does move ordering help?

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 A and leaves 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

Example 1 · Input
((3 12 8) (2 4 6) (14 5 2))
Expected output
value 3
leaves in given order 7
leaves in best order 5
Example 2 · Input
(((1 2) (3 4)) ((5 6) (7 8)))
Expected output
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)))

Lesson: Alpha-beta pruning and chance →