David Mutchler

AIJ Journal 1993 Journal Article

The multi-player version of minimax displays game-tree pathology

• David Mutchler

AAAI Conference 1986 Conference Paper

Optimal Allocation of Very Limited Search Resources

• David Mutchler

This paper presents a probabilistic model for studying the question: given n search resources, where in the search tree should they be expended? Specifically, a least-cost root-to-leaf path is sought in a random tree. The tree is known to be binary and complete to depth N. Arc costs are independently set either to 1 (with probability p ) or to 0 (with probability 1-p ). The cost of a leaf is the sum of the arc costs on the path from the root to that leaf. The searcher (scout) can learn n arc values. How should these scarce resources be dynamically allocated to minimize the average cost of the leaf selected? A natural decision rule for the scout is to allocate resources to arcs that lie above leaves whose current expected cost is minimal. The bad-news theorem says that situations exist for which this rule is nonoptimal, no matter what the value of n. The good-news theorem counters this: for a large class of situations, the aforementioned rule is an optimal decision rule if p 0.5. This report discusses the lessons provided by these two theorems and presents the proof of the bad-news theorem.

FOCS Conference 1986 Conference Paper

What search algorithm gives optimal average-case performance when search resources are highly limited?

• David Mutchler

This paper presents a probabilistic model for studying the question: given n search resources, where in the search tree should they be expended? Specifically, a least-cost root-to-leaf path is sought in a random tree. The tree is known to be binary and complete to depth N. Arc costs are independently set either to 1 (with probability p)or to 0 (with probability l-p). The cost of a leaf is the sum of the arc costs on the path from the root to that leaf. The searcher (scout) can learn n arc values. How should these scarce resources be dynamically allocated to minimize the average cost of the leaf selected? A natural decision rule for the scout is to allocate resources to arcs that lie above leaves whose current expected cost is minimal. The bad-news theorem says that situations exist for which this rule is nonoptimal, no matter what the value of n. The good-news theorem counters this: for a large class of situations, the aforementioned rule is an optimal decision rule if p ≤ 1/2 and within a constant of optimal if p ≫ 1/2.