Reason about an opponent.

A decision depends on who responds

Choose a route in a one-round game. Safe earns 2 points if blocked and 4 if allowed. Risky earns −6 if blocked and 10 if allowed. The opponent sees your route before responding. A final fair weather draw adds either −2 or +2 points. Your opponent receives the negative of your score, so this is a zero-sum game.

A search tree represents these possibilities in order: your choice, the opponent’s response, then weather. The leaf numbers are your final points. Work upward to compare decisions. This fully enumerated teaching game has no hidden state, approximate leaf evaluator or neural search component.

Separate choices from chance

Weather is not chosen by the opponent. For Risky followed by Block, the possible final scores are −8 and −4. Their equal-probability average is −6. This is expected utility for a risk-neutral player; it is not a promise that a single game will pay −6.

At a decision you control, pick the action with the highest value. For an opponent assumed to minimize your expected score, use the smallest response value. This is a minimax backup. Because our game also has chance nodes, the complete procedure is more precisely called expectiminimax.

Let V(s) be your value at state s, a denote an available action, and sₐ the state after that action. At your node take maxₐ V(sₐ); at the adversary’s node take minₐ V(sₐ). At a chance node, pₐ is the probability of outcome a and the value is its probability-weighted average:

For our adversarial opponent, Safe has value min(2,4)=2. Risky has value min(−6,10)=−6. Choose Safe. This protects expected utility against either response in this game. It does not guarantee at least two points on every realized round: bad weather after Block leaves zero.

Model a likely response instead

Expectimax uses a response distribution rather than a worst-case choice. Suppose the opponent blocks either route with probability 0.25. Safe is worth 0.25×2 + 0.75×4 = 3.5 expected points. Risky is worth 0.25×(−6) + 0.75×10 = 6. Choose Risky under these assumptions.

The response probabilities are explicit inputs here, not estimated from the learner’s play. They need evidence in a real application and may depend on the action or change with time. An opponent who observes and adapts to your strategy may invalidate a fixed response model.

Keep the assumed rate at 25%, then make the actual opponent block 90% of the time. Risky now earns −4.4 expected points, while Safe earns 2.2. The gap is 6.6 points of expected regret: the best available expected score under the actual model minus your selected action’s expected score. More exhaustive search of the wrong opponent model would not remove this error.

Learn a policy from experience

The lab also alternates the two routes to collect reward samples. For each action it stores a count n and the sum of rewards. Its estimated value Q is the sample mean. After observing reward r, the equivalent incremental update is:

Read this as: move the old mean toward the new reward by one part in the new observation count. If two observations averaged 4 and the third reward is −2, the new mean is 4 + (−2−4)/3 = 2. No equation is used before the first observation; then the mean is simply that reward.

Choosing whichever action has the larger learned mean defines a policy, a rule for selecting actions. This one-state tabular policy learns actual sampled returns; it is not a neural network, a multi-step Q-learning implementation or a memorized exact search answer. Training alternates actions to avoid leaving one unexplored. In a larger problem, exploration, state representation, delayed reward and function approximation add important difficulties.

Freeze the learned policy before comparing it under a changed opponent. Its original training condition stays recorded. Evaluation and manual play never update its means. Repeating the public seed produces the same practice evidence, not a fresh independent test.

Compare mechanisms and evidence fairly

Search uses the supplied game model and eight terminal utilities. Learned inference compares two sample means, but obtaining them costs training rounds. Comparing only their final action-selection step would hide data collection and training costs. The lab reports these distinct counts without claiming equal total compute.

A learned policy may exploit a permissive opponent and fail when the opponent changes, just as expectimax can fail under a wrong probability model. Minimax can be conservative when the actual opponent makes mistakes. None is universally best without specifying the opponent, utility and evidence.

The tree is revealed manually from leaves upward. The full calculation is already bounded and exact; revealing a value does not perform additional search. For larger trees, depth limits, learned evaluators and pruning require additional correctness and approximation considerations. This lesson does not implement those extensions.

Try a different payoff table

Without using the lab’s values, consider Safe paying 1 or 3 for Block/Allow and Risky paying −4 or 8. The assumed Block rate is 20%. Which route does an adversarial planner choose? Which does an expected-value planner choose?

Check the arithmetic

The worst response values are 1 and −4, so the adversarial planner chooses Safe. Expected values are 0.2×1 + 0.8×3 = 2.6 and 0.2×(−4) + 0.8×8 = 5.6, so the probabilistic planner chooses Risky. The difference comes from the response assumption. This is explained practice, not an independent qualification.

For a guided project note, explain one backup and contrast a lucky reward with its expectation. For implementation practice, reproduce the tree and the learned sample means independently and test all response-probability endpoints. For a decision brief, record assumed and actual opponent behavior, quantify expected regret and propose a monitoring or retraining trigger. Human review, independent project assessment and learner pilots remain pending.