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