AI: Expectimax for games of chance

Extend minimax to games with dice or random events.

What to build

A program that computes the value of a game tree with MAX, MIN and chance nodes.

Requirements

  • A node is written (max …), (min …) or (avg …) followed by its children; a number is a leaf. A chance node's outcomes are equally likely.
  • Print value V with V rounded to two decimal places.

Input

One line: the tree.

Output

One line.

Constraints

At most 100 leaves; leaves are whole numbers.

Example

Input:

(max (avg 3 5) (min 2 9) 4)

Output:

value 4.00

Why it works

At a chance node no one chooses, so the best estimate of what will happen is the average of the outcomes, while MAX and MIN still choose as in minimax.

Examples

Example 1 · Input
(max (avg 3 5) (min 2 9) 4)
Expected output
value 4.00
Example 2 · Input
(avg 1 2)
Expected output
value 1.50

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Read the tree recursively; each bracket starts with its kind: max, min or avg.

Hint 2

An avg node's value is the mean of its children's values.

Solution

Show one correct solution (try it yourself first)
import re

tokens = re.findall(r"\(|\)|[a-z]+|-?\d+", input())


def value():
    token = tokens.pop(0)
    if token != "(":
        return int(token)
    kind = tokens.pop(0)
    values = []
    while tokens[0] != ")":
        values.append(value())
    tokens.pop(0)
    if kind == "max":
        return max(values)
    if kind == "min":
        return min(values)
    return sum(values) / len(values)


print(f"value {value():.2f}")

Lesson: Alpha-beta pruning and chance →