Now the whole point of search (as opposed to just picking whichever child looks best to an evaluation function) is to insulate oneself from errors in the evaluation function. When one searches below a node, one gains more information and one's opinion of the value of that node may change. Such "opinion changes" are inherently probabilistic. They occur because one's information or computational abilities are unable to distinguish different states, e.g. a node with a given set of features might have different values. In this paper we adopt a probabilistic model of opinion changes, de-1This is a super-abbreviated discussion of [Baum and Smith, 1993] written by EBB for this conference.
Commentary on Baum's "How a Bayesian..? I. J. Good, for example, suggested that a computation is Stuart Russell, Computer Science Division, University of California, Berkeley, CA 94720. This rules out computations that might reveal one's plan to be a blunder--OK for politicians, but Summary of the Paper not for game-playing programs. The paper divides the problem of game playing into two Part of the difficulty lies in the formulation. P(A]B) parts: growing a search tree and evaluating the possible should be independent of the form of B--i.e., any logically moves on that basis. The evaluation process is based in equivalent expression should be treated the same way-- part on the idea that leaf node evaluations should be probability distributions rather than point values, and should forms.
The best chess machines are competitive with the best humans, but generate millions of positions per move. Their human opponents, however, only examine tens of positions, but search much deeper along some lines of play. Obviously, people are more selective in their choice of positions to examine. The importance of selective search was first recognized by (Shannon 1950). Most work on game-tree search has focussed on algorithms that make the same decisions as fullwidth, fixed-depth minimax. This includes alpha-beta pruning (Knuth & Moore 1975), fixed and dynamic node ordering (Slagle & Dixon 1969), SSS* (Stockman 1979), Scout (Pearl 1984), aspiration-windows (Kaindl, Shams, & Horacek 1991), etc.