AI: Minimax on a game tree

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, print value 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]}")

Lesson: Game playing with minimax →