On Optimal Game-Tree Search using Rational Meta-Reasoning

1 Introduction

The RALPH (Rational Agent with Limited-Performance Hardware) project is a long-term research effort aimed at understanding the effects of finite computational re­ sources on the performance of, and the design of algo­ rithms and architectures for, artificially intelligent sys­ tems. Rather than viewing AI as the production of human-like or commercially valuable programs, or as the design of systems containing only true beliefs, we see the AI problem as that of designing systems capable of achieving optimal behaviour (in a decision-theoretic sense) under computational constraints in complex task environments. Such a constrained optimization prob­ lem may have very different solutions from the compu­ tationally unconstrained case, for which a pure logical (or, more generally, decision-theoretic) · implementation may be appropriate. We therefore view the problem of finite resources for real-time behaviour as central to AI, rather than something that necessitates undesirable ap­ proximations to a 'perfectly rational' agent.

*This research was carried out with support from the AT&T Foundation and the Computer Science Division of the University of California, Berkeley. The second author is sup­ ported by a Shell Foundation Doctoral Fellowship.

In this paper, we outline the application of decision theory to the problem of reasoning about which compu­ tations to perform. The theory can be used to analyze the rationality of bounded agents, or to design optimal algorithms for real-time situations- situations in which the utility of an agent's actions depends significantly on the time at which they are carried out, rendering perfect deliberative rationality inoperable. We apply the theory to design a game-playing algorithm that selects nodes to expand according to the expected utility of the expan­ sion, and can beat alpha-beta with the same evaluation function while searching fewer nodes.

2 Optimal allocation of computational resources

We are studying the extent to which situation-dependent control of reasoning can benefit an agent operating in real time. In such an agent, choices concerning which computation to carry out, if any, must be made by meta­ level computations. This, of course, leads to the poten­ tial for an infinite regress of meta-levels. This regress can be avoided by, among other methods, the use of ap­ proximate decision-making (the outcome of which is not guaranteed to be optimal) at some point in the hierarchy, or by carrying out an unbounded computation at design time. For the tasks faced in AI the variety of situations and time pressures suggests that a combined approach is appropriate.

The basic proposal here is quite simple: choose com­ putations in the same way that any other actions are chosen. Decision theory is the standard normative the­ ory for actions, so let's apply it to computations too. This idea, although similar to the concept of informa­ tion value in decision science [Raiffa and Schlaifer, 1961, Howard, 1966, Good, 1968], is relatively new in AI. In ad­ dition, getting the model right and putting it into prac­ tice are not such easy tasks.

In this section, we give a general formula for the ex­ pected value of a computation. The following section discusses ways in which the formula must be modified to make it usable by a limited rational agent that has only estimates of utilities and their expectations. Subse­ quent sections develop the analysis needed, and the sim­ plifying assumptions employed, to create a game-playing program along these lines.

Notation: The agent's goal is to maximize its utility function U(w) on states of the world w. We denote the outcome of an action A performed in a situation Wj by [A, Wj], or simply (A] if performed in the "current" situation. At any given time the agent has a default base-level action, a, which is the action that currently appears best to the agent. At the same time it has available to it a set of possible computational actions S;, with which it can continue its deliberations. Computation S; might lead the agent to revise its choice of default action; the new default action will be called as;- The meta-level decision problem for the agent is thus to decide among the immediate options a, St. ... , Sk.

Computational actions are distinguished from base­ level actions in that they directly affect only the agent's internal state. We define the net value of a computa­ tional action to be the resulting increase in utility, com­ pared to the utility of taking the default action instead:

If S; is a "complete computation", i.e., is not followed by any further deliberation, then the utility of state [S;] is just the utility of the action as; chosen as a result of the computation, 1 , given that it is to be performed after the computation is complete, i.e., in the state [S; ]:

In the general case, the computation will bring about changes in the internal state of the agent that will af­ fect the value of possible further computational actions. We call such a computation a "partial computation". In this case, we want to assess the utility of the internal state in terms of its effect on the agent's ultimate choice of action. Hence the utility of the internal state is the expected utility of the base-level action which the agent will ultimately take, given that it is in that internal state. This expectation is defined by summing over all possible ways of completing the deliberation from the given inter­ nal state. We denote a computation sequence consisting of computation sl followed by computation s2 by the expression S1 .S2 · Thus, letting T range over all possible complete computation sequences followingS;, and aT represent the action chosen by computation sequence T, we have

where P(T) is the probability that the agent will perform the computation sequence T.

3 Estimating the Value of Computation

How should a limited rational agent use these equations to evaluate its own computational actions? The agent cannot simply apply equation 3 directly, because it does not know the exact utilities of its base-level actions. (If it did, it would not need to deliberate at all.) We will assume the agent makes a numerical estimate U([A]) of the utility of its available actions, and that deliberation proceeds by revising these estimated utilities. At the end of its deliberations it picks the action with high­ est estimated utility. This model applies to, or can be adapted to, mo!lt search algorithms in AI. Since it is im­ portant to distinguish the different utility estimates as computation proceeds, we will use S to denote the base­ level computation sequence carried out up to the current state. Then QS represents an estimate of a quantity Q calculated by computation S. Thus the estimated utility of a computationS; is given by:

1 We ignore learning as a means of generating utility for future situations.

Here A; ranges over all of the possible base level actions in the current state; hence <lT is just the action which maximizes uS.s; .T in the state [S;.T].

Finally, the estimated net value of computation S; is given by

Of course, before the computation S; is performed, V(S;) is a random variable. Although the agent can't know ahead of time what the exact value of V(S;) will be, given sufficient statistical knowledge of the distribu­ tion of V for similar actions in past situations, the agent can take its expectation,

Such an agent can thus employ meta-level rationality in its control decisions. The principle of rationality­ choose the action with highest estimated expected utility-applied to the meta-level decision problem is equivalent to:

1. Estimate the expected value E[V(S; )] of each com­ putational actionS;.
2. If any computational action has positive expected value, take the one with highest expected value. Otherwise, cease computing and take the current base-level action, a, with highest expected utility.

Thus far we have captured the real-time nature of the environment by explicitly including the situation in which an action is taken in the argument to the util­ ity function. Such a comprehensive function of the total state of affairs captures all constraints and trade-offs; in particular, any form of time constraint can be expressed in this way. However, the inclusion of this dependence on the overall state significantly complicates the analy­ sis. Under certain assumptions, it is possible to capture the dependence of utility on time in a separate notion of the cost of time, so that the consideration of the qual­ ity of an action can be separated from considerations of time pressure.

In applications, typically we are given some value es­ timator that is independent of time and takes just the action outcome as argument. We will call such a function the estimated intrinsic utility, denoted by 01· We can then define a function TC, for time cost, that simply ex­ presses the difference between total and intrinsic utility, assuming this difference depends only on the temporal duration IS; I of the computation:

Consider again the case of a complete computational actionS;, where S; results in taking action asp where a was the default action prior to Sj. In this case, the estimated net value of Sj is given by

Note that we use the later estimate u?·Si to evaluate both as . and a, the new and the old best moves. The reason for this is most obvious if we consider the case where as; = a, but uJ'·si([as;]) > Uj5([a]); i.e., Si simply revises upward the estimated intrinsic utility of a but does not alter the choice of move. Then the net value of Sj should depend only on the passage of time spent in deliberation, since the real intrinsic utility is of course constant. An important corollary of this is that if a= as; then V(Si) is guaranteed to be negative, that is a search action that doesn't change the system's preferred move will have had no value.

This points to deep issues which arise from the fact that the agents we are dealing with have only lim­ ited rationality. For instance, in [Russell and Wefald, 1989], we discuss differences between our formula and R. Howard's [1966], in which Howard analyzes the expected value of obtaining complete information about certain variables in a bidding problem. Briefly, Howard assumes

that the expected value of the error term u;'·si([A])­

Uf([A]) for a given action A is strictly 0. This is true for a perfectly rational agent, but cannot be assumed always to hold exactly for a limited rational agent, for instance one who uses a polynomial evaluation function to estimate expected move utilities.

4 Specific base-level problem-solvers

Up to this point, we have been working at a very general level, making no assumptions about the nature of the base-level decision-making mechanism. The above equa­ tions are applicable to a brain or a pocket calculator, in principle. Naturally, there are some attributes of cer­ tain mechanisms that make them amenable to meta-level control. The overall computation should be modular, in the sense that it can be divided into 'steps' that can be chosen between; the steps must be able to be carried out in varying orders. The steps can of course have any grain size.

We now look at some particular systems in more detail. 2 We will focus on the use of the complete­ computation formula, equation 8. This equation gives the net benefit of the computation as a random variable. In order to compute its expectation, we need informa­ tion about the distribution of possible effects of a com­ putation on the system's value estimates for its available actions.

In a search program, computation typically proceeds by expanding 'frontier nodes' of the partially-grown search tree. The value estimates for actions are cal­ culated by backing up values from the new leaf nodes through their parents. The effect on the value estimate for an action therefore is composed of two aspects: 1) the effect on the value of the leaf nodes that are expanded, and 2) the transmission of this effect back through the tree.

2 Space limitations prevent more than a cursory justifica­ tion of the results. For more detailed analysis, see [Russell and Wefald, 1988b].

The first component depends on the nature of the node being expanded, and the nature of the expansion compu­ tation. Statistical information on the probability distri­ bution can therefore be acquired by induction on a large sample of similar states using the same type of expan­ sion computation. The second component is an analytic function of the state of the tree (in particular, the cur­ rent value estimates for the nodes on the path to the root, and their children) that depends on the backing­ up method used by the search program.

In this paper, we consider systems that make decisions using simple search algorithms. In order to make calcula­ tion of the expected value of computation tractable, we will introduce explicit simplifying assumptions. These are related to what Pearl [1988] has called a "myopic policy". The notation used will be as above, with the addition of f3t. /h,, etc., to denote current second-best action, current third-best, and so on.

Meta-greedy algorithms·

Explicit consideration of all possible complete sequences of search steps is clearly intractable. The obvious simpli­ fication is to consider single computation steps (remem­ ber that a single step can represent an arbitrary amount of computation, but without interleaved control), and to estimate their ultimate effect; we then choose the step appearing to have the highest benefit. Such meta-greedy algorithms effectively have a fixed meta-meta-level policy of a depth-limit of 1 on the meta-level decision problem.

Single-step assumption

The expression for the estimated utility of a computation (equation 4) can be used directly with a meta-greedy al­ gorithm, but it is often somewhat hard to evaluate, par­ ticularly when the future availability of computational resources is hard to estimate. The computation is greatly simplified if we assume that it is reasonable to act as if we will take at most one more search step. In this case we can use the complete-computation formula 8. We call this the single-step assumption. The assump­ tion sometimes fails. Recall that a complete computa­ tion has no value unless it changes the choice of move; thus the single-step assumption will predict that cer­ tain search steps can have no value, whereas often those steps enable other steps to become valuable. We will see that, although it makes the expected-value computation tractable, this assumption also places certain limitations on the depth of search in some domains, including game­ playing.

It is worth emphasizing here that if either the meta­ greedy or single-step assumptions were completely re­ laxed, the other would become completely true. That is, if it were possible to consider all possible sequences of computations, then it would be no restriction to consider those sequences as complete computations. On the other hand, if we could accurately compute the full expected value of a single computation step considered as a possi­ bly partial computation, we would thereby be implicitly evaluating all possible continuations of that computation step, and hence we would not need to consider explicitly all possible computation sequences. Thus, the simpli­ fication lies in employing the two assumptions jointly; neither alone would be a restriction.

5 Error: The variation of estimated utility with search

According to equation 4, calculating the value of a com­ putation Si requires knowledge of how the estimated utility of the top-level moves A; will change as a re­ sult of S1. We will use the term error for the difference

Let Pii ( u) be the probability density function in the current state for the future value of the utility estimate u~· 5 i([A;]) after the search action Sj has been carried out. We assume that Sj is the expansion of a single leaf node, and that the search graph is a tree, so that the backed-up value of at most one top-level move will be affected by Sj. Hence 0~· 5 i ([A;]) = ijS ([A;]) if s1 does not expand a node in the subtree unaer move At. A search action can have positive value by changing the preferred move in only two ways: by raising the value of some move /3i above the current value of a, or reducing the value of a below the current value of /31 (see figure 1).

If we are considering a search action s 1 which affects the estimated utility of move /31, this will only change our move choice if u~· 5 i([/3;]) > Uf([a]). In that case, . s s we expect to be better off by an amount U 1 · '([/3;])- Uf([a]). Thus

In the other case, if Sk affects the move a, following similar reasoning we have:

These formulre allow the straightforward calculation of the optimal search action under the meta-greedy and single-step assumptions, and of the appropriate stopping point, given the distributions Pii and expected utilities U(A;), and a cost estimation function TC(!Si·l). Below, we show how these quantities can be calcu ated for a game-playing system in terms of easily obtainable, sta­ tistical quantities.

We can describe the qualitative behaviour of any algo­ rithm based on .our approach. There are two cases where further search will have very low expected value: when there is little overlap between the distributions of the top two moves, and when the moves overlap a great deal but the distributions are narrow. (This latter case has received scant attention in the literature.) We illustrate the three major situations graphically in Figure 2.

6 Game-playing: The MGSS* algorithm

In this section, we describe how the utility of a computa­ tion can be estimated for two-player games, in which the basic decision-making algorithm is some kind of looka­ head search using minimax backup. The choice of search steps is then made so as to maximize the system's overall utility, as determined by the move chosen and the time at which it is made. A system with low-overhead, nor­ mative control of search would be guaranteed to win, on average, against any other program with equal computa­ tional resources and domain-specific knowledge. We be­ lieve such a system can be achieved. In addition, we ob­ tain qualitative insight into the nature of efficient search.

We assume a standard evaluation function that is in­ dependent of time factors, and we therefore use the time cost function described above. The evaluation function is viewed as an intrinsic expected utility function, not as an estimate of the true value of the position. The true value for a game such as chess is 0 or ± 1 (on a scale in which 1 is a win); the estimated utility is a computationally­ bounded, probability-weighted value Pwin- Plou [Good, 1968].

In our analysis [Russell and Wefald, 1988b], we use both the meta-greedy and single-step assumptions, with individual node expansions as the chosen computational steps. We have developed an efficiently computable for­ mula for evaluating the integrals in equations 9 and 10. The principal tool is the re-expression of the probability distributions Pii in terms of the error distribution Pii at the leaf node affected by the search action S1. Since Pji is a function of only the board situation, and not of the game tree, it can be estimated from empirical data on the results of previous tree searches. A computable expression for the integral is then obtained by analyzing how the change in value of the leaf node is propagated to the top level.

The proof of correctness of the following equations, corresponding to equations 9 and 10, depends on a the­ orem proved in [Russell and Wefald, 1988b] that gives a simple recursive definition for the nodes that are Rele­ vant to a top-level move, that is, nodes whose expansion can affect the top-level move's value ( cf. singleton con­ spiracies in [McAllester, 1988]). The value of expanding any other node is strictly 0, and our algorithm derives considerable efficiency from restricting its attention to only relevant nodes.

The expected value of expanding a leaf node j in the subtree of a move {3;, previously given by equation 9, is

where Pii is the density function of the random variable u~· 5 i(j), and 6 is the lowest value of the second-best children of the min nodes between j and the root. Simi­ larly, the expected value of expanding a leaf node k under a is given by

where PH is the density function of the random variable ur· 5 ·(k), and 6 is the highest value of the second-best children of the max nodes between k and the root.

7 Implementation of MGSS*

We have used the game of Othello for our experiments in this domain. In a direct implementation of the analysis of the previous section, the entire search tree is kept in memory, and the tree is grown one step at a time by choosing, at each step, a tip node to expand, and adding its successors to the tree.

The following information is maintained for each node:

1. a link to the top-level move, if any, to which the node is Relevant;
2. the Search Value of the node, i.e., the expected gain in utility from expanding the node, for leaf nodes;
3. the Game Value of the node, i.e., its Static Value if it is a leaf node, or its current backed-up value oth­ erwise;
4. the 6 value for the node, as defined above;
5. a link pointing to the Parent of the node; and
6. if the node has already been expanded, a pointer to a list containing the node's Children. The list is maintained in order of Game Value.

Relevant leaf nodes with positive Search Value are main­ tained in a Queue, in decreasing order of Search Value.

Algorithm MGSS*

1. Generate the successors of the Root. Place the Relevant ones in the Queue ordered by Search Value. For each successor, set its GameValue equal to its StaticValue. Place the successors in the Children list of the Root ordered by GameValue.
2. Remove the first element j of Queue. Compute E( Ll( Sj)) using equation 11 or 12. Estimate the time-cost TC of expanding node j. If E[Ll(Sj) - TC] ~ 0 then return the first element in the Children of the Root as the best move.

3. Otherwise

• (a) Carry out the computation Sj. For each result­ ing leaf node, set Game Value= StaticValue.
• (b) Place the new leaf nodes, ordered by GameValue, in the Children list of j.
• (c) Back up the Game Values of the successors to j's Game Value. If this changes, re-insert j in its parent's Children list and continue backing up recursively, stopping at the Root. When­ ever a Children list is re-ordered, or the best move in such a list increases its value, or the second-best move in such a list decreases its value, recompute the appropriate 6 values and Relevant node pointers. The latter step may involve updating Queue membership.
• (d) Add j's Relevant successors, ordered by Search Value, to the Queue.

4. Go to 2.

All this means that the. overhead for controlling the search is small, provided that the integral expression in equations 11 and 12 can be evaluated quickly and ex­ actly. We now show how this is done.

The leaf-node error distributions (the functions Pii in the integral) are generated by prior statistical sampling. For search steps consisting of a single node expansion, such as are used in MGSS*, the error is simply defined as the difference between the lears static value and its backed-up value from a depth one search. The data points are gathered into buckets according to selected features of the board situation. 35,000 data points were gathered into roughly 1000 buckets. A different error density function is created for each bucket. The func­ tions appear to be normal curves to a reasonable degree of approximation, and can thus be represented by two parameters, the mean J-L and standard deviation u.

Given normal curves Np, 17 for the density functions Pii and pu, we can simplify equations 11 and 12 consider­ ably, after some mathematical effort. The new equations

corresponding to equation (11), and

corresponding to equation (12). Here ~ is a tabulated integral of the normal curve N0 1 . Armed with these formulre, computing search value~ is a good deal quicker than computing the static evaluation function, enabling MGSS* to perform with very low overhead.

The time cost estimation function can also in princi­ ple be determined empirically. Assume that the average time needed to perform a search step is, say, a millisec­ ond. Then we want to determine empirically the effect of wasting a millisecond, in a given game situation, on the probability of ultimately winning the game. We then have a common utility scale for moves and time costs. In practice, it is sufficient to have C be an appropriate function of the number of seconds per move remaining, such that a loss on time is impossible. The appropri­ ate sort of time-cost function will depend heavily on the particular rules under which the game is played, such as whether there is a per-move or only a per-game time limit, and so on. For the purpose of testing the im­ plementation, we set a per-game time limit in terms of numbers of nodes expanded, and set the time cost to be an appropriately parameterized inverse function of the average time remaining per move.

8 Performance of MGSS*

The qualitative behaviour of the MGSS* algorithm is much like that described for the general decision­ theoretic case, with two distinct classes of search ter­ mination points (see figure 2). The search is highly se­ lective, with some branches reaching depths of 20.

Our experiments indicate that, with moderately small time allocations, MGSS* is significantly better than an alpha-beta search using the same evaluation function, even though MGSS* generates significantly fewer nodes of search. Our results vs. alpha-beta search to depths 2, 3, and 4 are summarized in table 1. For each search depth, the time cost function of MGSS* was adjusted to allow the algorithm to generate about as many nodes on average as alpha-beta; beyond depth 2, however, MGSS* chose to generate far fewer nodes. Each tournament con­ sisted of 32 games played from 16 different starting posi­ tions, with the two algorithms alternately playing black. (One game against depth-2 a-,13 was tied.)

Note that MGSS* is roughly even with depth-2 a-,13, and searches slightly more nodes; evidently, at this depth o:-,13 is wasting very little of its search effort. However, at greater effort limits, MGSS* plays significantly better, while doing much less search, in terms of nodes gener­ ated. In terms of time used, the performance of MGSS* is less impressive, using more time at depths 2 and 3, and slightly less at depth 4. It is important to emphasize that very little effort was made to optimize the implementation of MGSS* with respect to execution time, and we are confident that opportunities exist for considerable savings by improving the data structures used, replacing sorted lists with hash tables and binary search trees, and so on.

In terms of nodes generated, we expect further im­ provement with more work on the features used to clas­ sify the error density functions. The number of nodes searched can probably be further reduced by reducing the unit of computation to be the generation and evalu­ ation of a single successor node, as in alpha-beta, rather than the expansion of a node. Our algorithm will also make better use of a more reliable evaluation function - as the errors tend to zero, the value of search will de­ crease, and in the limit the algorithm will only search to depth 1. An interesting possibility is that the evaluation function of BKG [Berliner, 1980] has effectively reached this level already: because of the dice rolls, the branch­ ing factor in backgammon at the root is 20 but at all other levels is close to 400, so that no current program uses a significant amount of search. Jeff Conroy [Con­ roy, forthcoming] has extended MGSS* to handle prob­ abilistic outcomes, and initial results for backgammon indicate that additional search still pays significant div­ idends.

Although MGSS* seems extremely effective for small time allocations, the single-step assumption eventually begins to bar almost all nodes from being expanded as the tree grows larger. Hence comparisons against a much deeper-searching alpha-beta are unfavourable. Prelimi­ nary results indicate that MGSS* plays a slightly better than even game against depth-5 alpha-beta, while gen­ erating about 1/6 as many nodes of search. Against depth-6 alpha-beta, MGSS* appears to be incapable of generating large enough search trees to play effectively. Extension of the algorithm to consider sets of search steps may overcome this problem. We are also investi­ gating the effect of applying MGSS* to selectively extend search beyond the depth limit of an alpha-beta search. A simpler form of this method appears in the work on sin­ gular extensions by Campbell [Campbell, 1988], and has proved surprisingly effective in the HITECH and Deep Thought chess machines.

9 Related work

A detailed comparison with related work on selective search appears in [Russell and Wefald, 1988b]. Here we can only point the reader \9 the pertinent literature.

Many sophisticated programs have been constructed for game-playing, where the infeasibility of search to ter­ mination has long been accepted as a fact of life. In some excellent early work, statistician I. J. Good [1968, 1977] proposed a decision-theoretic analysis both of move choice and search step choice, but the proposal was never implemented.

Berliner [1979] pointed out that alpha-beta undertakes needless search when only one legal move is available, or when one move can be seen to be better than all others even without search. His B* algorithm attempts to find the shortest 'proor, based on heuristic value bounds, that one move is best. Palay [1982, 1985] has given heuristics for choosing how to expand the tree to pro­ duce a 'proof' quickly. In our terms, B* is using the wrong utility function at the meta-level, as illustrated by the case of symmetrical moves, where one should toss a coin rather than attempt to prove one better.

Rivest's Min/Max Approximation algorithm [Rivest, 1988] expands nodes that have the highest effect on the root value. This only weakly relates to the expansion's actual utility. McAllester's "Conspiracy Numbers" ap­ proach [McAllester, 1988] approach is more sophisti­ cated, considering the set of nodes that must change their values to increase or decrease the root value be­ yond given bounds.

10 Discussion

The principal contributions of the paper are the following:

• The rational choice of search steps was defined and operationalized. Both meta- and base-levels should use the same utility function. This leads to im­ proved choice of search steps compared to several other algorithms, and unifies pruning and termina­ tion in a natural framework.
• A class of meta-greedy algorithms was defined, us­ ing the single-step assumption, and a general for­ mula for the value of search was developed in this context. The formula depends on a notion of er­ ror in evaluation that is both coherent and directly available from empirical data.
• Theorems were proved that allow for efficient im­ plementation and for computation of search values using only simple, parameterized distributions.
• Good performance of the MGSS* algorithm, despite its restrictive assumptions, suggests that extensions of the approach to cover sequences of search steps may yield very high-quality algorithms that are also theoretically well-founded.

We also hope this work will help to reduce the gap be­ tween research on game-playing and that on more gen­ eral types of decision-making.

As usual in computer science, justification is the pre­ lude to synthesis, and we expect more new algorithms to appear as researchers prove various meta-level theorems concerning search action sequences which provide the ba­ sis for efficient implementations. Application to single­ agent search [Wefald and Russell, 1989a] has yielded an algorithm with excellent real-time search behaviour, and a proof that best-first search is in fact optimal in the sense of performing the most valuable node expansions given the information available.

Several problems and research tasks remain. The im­ plications of our approach for learning techniques are be­ ing investigated [Wefald and Russell, 1989b], as are its implications for the choice of backing-up procedure. We would like to apply the theory to provide optimal control of general decision-theoretic calculations, for example in an influence diagram system [Pearl, 1988]. However, the current analysis relies on the unit of computation only affecting the value of one top-level action, whereas re­ fining a probability value, for example, might affect the value of several actions. Other extensions are needed to handle the case where time cost cannot be treated as in­ dependent of move chosen. The most serious theoretical problem is the need for the single-step assumption. The theory of'conspiracy numbers' developed in [McAllester, 1988] may be of some help here.