Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2020/artificial-intelligence/3/f/solution

The usual alpha-beta pruning inference fails because increasing B's utility need not decrease A's utility. A partially explored B-node may have found a child unfavorable to A, but B may prefer an unseen child favorable to A as well. An observed low A-coordinate therefore supplies no upper bound on the A-coordinate ultimately propagated by B.
For a concrete counterexample, let a root A-node already have an alternative outcome . In another B-node, the first explored child yields . A zero-sum-style cutoff would discard its remaining children because . But an unseen child with outcome is preferred by B, and makes the complete B-node return , which A strictly prefers to its incumbent. Such a cutoff changes the answer.
The problem persists even after observing a large B-coordinate: without a known relation between coordinates or useful global utility bounds, an unseen pair may have still larger values for both players. Hence there is no generally valid ordinary scalar alpha-beta pruning rule for unrestricted general-sum games. This does not rule out all search pruning: additional bounds, dominance information or a relationship between players' utilities can justify specific cutoffs, as in (g).

New to topics? Read the docs here!