An Analysis of the Full
Alpha-Beta Pruning Algorithm
GErard M. Baudet
Department of Computer ScLence
CarnegLe-Metton Uni,versl.ty
Pi.ttsburgh, Pehnsylvanl, a 152[3
An anatysi,s of the alpha-beta pruning alBori,thm i.s
presented which takes i.nto account both shaU.ow and deep
cut-offs. A formula i,s fi.rst devetoped to measure the
average number of termi,na[ nodes examined by the alEori,thm
[n a uni.form tree of deRree n and depth d when ties are
all,owed among the bottom posi.tions: specifi.caliºy, act bottom
values are assumed to he {ndependent identi,catty distributed
random variables drawn from a di,screte probabii,i.ty
di.stri.butLon. A worst case analysi,s over all. possi.bte
probabi.ti.i,y distri,bui,i,ons i,s then presented by ¢onslderin6
the tlmLti,ng case when the dL’;crete probablU.ty dl.stri.buti.on
tends to a conti.nuous probabitLty distri.butl.on. The
branchi.ng factor of the alpha–beta pruni.nt~ atp, ori.thm [s
shown to grow wi.th n as e(nAn -), therefore confi.rming a
ctai.m by Knuth and Moore that deep cut-ells only have a
second order effect on the behavi.or of the at6ori.thm.
1 – Introduction
Most so-catted i, ntei,t[gent programs use some form of
t ree searchi.ng; among them, most game playing programs are
buLtt around an effi.ci.ent tree searchi,ng algorithm known as
the (~Lpha-beta prtzni.ng aLgorittznz. ThLs paper i,nvest[gates
the effi,ci,ency of this a[gori.thm wi, th respect to a test
measure fi.rst introduced by Knuth and Moore i.n [3] and
El.yen i.n the foltowi.ng.
D e f i n i t i o n ! .1 :
Let Nn, d be the number of terminal posi.ti.ons exami.ned
by some algori.thm A bm searchi.ng a uni.form tree of degree
n and depth d. The quanti.ty
°
is catted the branchin E factor corrOspondi.ng to the search
ai,gorLthm A. •
ThLs research was partly supported by the Nati.onal Sci,ence
Foundati.on under. Grant MCS 75-222-55 and the Offi,ce of
Naval Research under Contract N00014-76-C-0370,
NR 044-422 and partly by a Research Grant from the ]nsti.tut
de Recherche d’lnformat~que et d’Automati,que (IRIA),
Rocquencourt, France.
Si.mi.i,ar analyses have been attempted i,n two recent
papers by Fuli,er, Gaschni,g and Gi.ttogty [ t ] and by Knuth and
Moore [3]. Both papers address the problem of searchi,ng a
uni.form game tree of degree n. and depth d wi, th the
~-/~ pruni.ng algori,thm under the assumpUons that the n d
stati.c values assi.gned to the terminal nodes are i.ndependent
i,dent[cali,y clistributed random variables and that they are czll
dis[[net. We immedialety observe that, i.n order to evaluate
the branching factor, the tar, t as.-,umpti.on requires that the
n d di,stinct values assi,gned to the termi,naiº posi.ti,ons be
taken from arm i.nfi.ni.te range. For most practi.ca[ appti.cati.ons
this i.s, however, unreali sti,c.
Fuller, Gaschnig and Gitlogty developed i.n [1] a general
formula for time average number of terminal posi.ti.ons
e×amined by the ~,../~ procedure. Thei.r formula, however, i.s
computationalty intractable and leads to undesi.rabte
rounding errors for large trees (L e., for large n and d) siince
i.t i nvoi,ves, [n particular, a 2d-2 nested summati.on of terms
wLth atternati.ng si,gns and requi,res on the order of n d steps
for i.ts evaluai,i,on. Then they gave some empi,ri,cal resui,ts
based on a seri,es of simutati.ons, and compared the results
wi,th actual measurements obtai.ned by running a modLfi.ed
version of time Technology Chess Program [2].
In [3], Knui,h and Moore have analyzed, under the same
condi.t[ons, a si, mpler version of the full. w-./~pruni.ng
algori thm by not (:onsi,deri,ng the possi.bi.ti,ty of deep
cut-offs; they have shown, i.n parti.cular, that the branchi.ng
– 2 9 6 –
factor of the resuttiºng algori,tl~m is (9(n/tn n). Knuth and
Moore also considered other assumptions to account for
dependencies among the static val,ues assigned to the
term[nat positions and devei,oped anatytiic results under
those assumptions. Their paper gives, in addition, an
excel lent presentation and historical, account of the
=-/3 pruning algorithm.
Departing from the a.~sumptiions of the two papers we
just mentiioned, we first consider the effect of possible
equati,tLes between the values assigned to the terminal, nodes
of a uniform tree, assuming that these values are
independent i.dontical,l,y distributed random variables drawn
from any d~serete probabiitity distribution. |n Section 2, we
establish some notations and preiºiminary results, and in
Section 3, we derive a general formui,a for the number of
terminal nodes examined by the ~../t pruning algorithm when
we take into account both shallow and deep cut-offs. The
evaluation of this formula requires oni,y a finite summation
over the range of possible values assigned to the terminal.
nodes and i.s retatl,vety easy. We show, in partiicui,arj that,
when the termiinat nodes can only take on two diisti,nct
values, the branching /actor of the w-/3 pruning algorithm
can grow wdh n as O(n/l.n n) for some choice of the
probabiºti.ty di,stribution. }n Section 4, we show that, when
the discrete probabii,l,ty distribution tends to a continuous
probabi.t ity distribuUon, the summation derived in Section 3
can be replaced by an i,ntegral., which constitutes the worst
case over ai,t discrete probabitiºty distributions, tn
Section 5, an analysiis of this integral shows that the
branchi,ng factor of the ot../T pruning algorithm for a uniform
tree of degree tz grows with r~ as ®(n/in n), therefore
confiºrmi,ng a clairn by Knuth and Moore [3] that deep cut-offs
only have a second order effect on the average behavior of
the w-/~ pruning al.gorithm. Some concl,uding remarks and
open problems are given in the last section.
2 – Presentation and initial properties of the ~ – ~
pruning algorithm
There are two usual approaches for dealinR wi,th
searching a game tree. In [I], Futi,er, Gaschni.g and Giºttogty
adopted the Min-Mrzz approach, whiite, in [3], Knuth and
Moore chose the Nege-Mcz~c approach. We wiºl.t briefi,y
present, in Section 2.t, the two approaches and introduce
the w-/~ procedure in terms of the Nega-Max modet. Then, in
Section 2.2, we witi, reestabl,ish an initial, result of [1] which
was stated in terms of the Miin-Max approach.
2.1 – The 0~-/3 procedure
Let us consider a game (IHke chess, checkers, tic-tac-toe
or kalah) played by two players who take turns. It is
common to represent the evotutiion of the game by means of
a g,zme tree, where each positi,on of the game is represented
by a node. Lf the position is a dead-end, the node is
terminal, otherwise all possible moves from that posiºti,on are
represented as the successors of the node. The structure of
the tree is preserved by not generating moves leadiºng to
some posi,ti.ons already generated (thus, avoiding cyctes)l
thiis is the function of tile mo=,e Eetlerator. The eucb~Qtion
f~nct~on is another important function i.n game playing
programs ~ it assigns to each terminal position a static u,l~e
by esti.mati.ng various parameters such as piece counts,
occupation of the board, etc. The evaluati.on function
evatuates the terminal nodes from one player’s viewpoint,
giv ing higher val,ues to positions more favorabiie to thiis
ptayer. It is convenient at this point to name the two
ptay.ers Max and Min. Hence, Max’s strategy is to lead the
game towards positions wdh higher values, white Mi,n’s
strategy is to lead the game towards posiitions with tower
values.
The .~irLLmc=z p,.oced~Lre is directl,y based on this
formutation and can be used by eiither Max or Min to decide
on his next move from a giyen position, assuming that his
opponent wit[ respond with his best move. Using a rather
– 297-
brute force approach, the minimax procedure assigns values
to al l nodes of a game tree. It f irst assigns to terminal
nodes the results of the evaluation function, then it backs-up
to internal nodes corresponding to a position from which It
i s Max’s (Min’s) turn to play the maximum (minimum) of the
values assigned to its successors.
Suppose i t is Max’s turn to play from an init ial position
(corresponding to the root of the game tree), then it is his
turn to play from any positions at even depth and Mi.n’s turn
to p lay from any positions at odd depth. Therefore, the
minimax procedure w i l l back-up values to the nodes of the
game tree through a succession of Minimazi.ng/Maximazing
operat ions. This corresponds to the Mi . , -M~ approach.
By observing that:
max{ mini ~cl, z2, … }, mini :yj, :)’2 …. } …. } =
max{ -max{ -=1, “z2 …. }, -max{ -Yl, -:)’2 …. } …. } ,
the Min-Max approach can be directly reformul.ated into the
NeEa-M~z= approach. In the Nega-Max formulation, a
termina l node of a game tree should be assigned the result
of the evaluation function only if it is at an even depth
(assuming i t is in i t ia l ly Max’s turn to play) and it should be
assigned the opposite of the result of the evaluation
funct ion if i t is at an odd depth, The Nega-Max approach
requi res the same operator at all levels of a game tree, and
the uni formi ty of the notation wi l l make it easier to carry
out an analysis. This approach wit[ be used throughout.
Figure 2.1 – Searching a game tree
wi th the minimax procedure
Figure 2.1 shows the effect of the minimax procedure in
a uniform tree of degree 2 and depth 4. The values assigned
to the terminal nodes have been chosen arbitrari ly. The path
indicated by a darker line show~ the sequence of moves
selected by the procedure. The minimax procedure is
c lear ly a brute force search and, when exploring a node, i t
uses none of the information already available from the
nodes previously explored. Obviou.,,ty, by taking advantage
of the information previously acquired we (:an easily
improve on the brute force search. Figure 2.2 presents
some simple patterns in which the distribution of the
in format ion could lead to such improvements.
Ca) shallow cut-off “.
(b) deep cut-off
Figure 2.2 – Example~ of po,.;sible cut-offs
The circ led nodes have already been explored, and they are
labe led w i th their hacked-up vah.les; the values of the other
nodes are yet to be determined. We are interested in the
value u of the top level node in both patterns Ca) and (b).
Let us consider the pattern of Figure 2,2 Ca) first. From
the def in i t ion of the minimax procedure, the values u and x
sat isfy:
=, = m e × { . 7 , – z . } , ~. = m a x { – 2 . . . . } ,
which shows that ~ >. –2 or 2 ~. -z. Since 3~. 2;~ -~, i t
fo l lows that i.ndepenclen.t o f file e~ecl uall.~e o [ X, we wit [
have IJ .– 3. This .~,llows that we need not explore further the
succes.’,ors of the node labeled :~ if we are only interested in
the value of u. This leads to a f irst type of elLt-o,t[s known
as sha.ZLouJ clLt-oJ’fs.
The pattern of Figure 2.2. (b) il lustrates a deeper clLt-o[[.
As w i th the previous example, there are immediate relations
between the values of the nodes. In particular, we have
– 298 –
y > -z, which reads u’.; to consider two cases. Either y > -Z,
and thi.s means lhat the va[Ue y is determi,ned by i,ts r[ght
son(s) and certai,nty does not depend on the r ight son(s) of z.
Or y .– -z, i,n which case, sLnce z. ~ -y and z > -2, we deduce
~ – 2 or -~ .~ 2; but since u ,, max{3, -z } i,t fotl.ows that
,~ 3, i ,ndependent of the exact value of x and, a forti,or[,
i ndependent of the exact value of z. This shows that i.n
e i t he r case the successors of the node tabeted z need not be
fu r the r exp to red since the final vatue of u woutd LLn no way
be af fected.
The two examptes presented in Figure 2.2 indicate that a
reduc t ion of the search can be achieved Ef a node passes
down to i,ts sons the current value backed-up so far (3 [n the
case of the two above examptes) as a bound for pruni,ng
branches 2, 4, 6, … [evel.-~ betow; the bound can, of course, be
i ,mproved as the search progresses down the tree (!.eadi.ng to
more and more possible cut-.offs).
Using two bounds for even and odd revels of a tree,
these improvements are implemented in the foltowi.ng
p rocedure adapted from [3].
i.nteKe[ I~rocedure
ALPHA~3ETA(posHior~ P, Lnte~.’r atpha, integer beta):
beKi, n !nt/9_g- e_r j , t, , ;
determit~e the successor positions: Pl ….. Pr#)
i,l n ~ o . t h e n
ALPHABETA := [(P)
etse
fo~r j := I s_t_e:p_ I tjntE_At n do
t := -.ALPHAf]ITA(Pj,-beta,-a[pha)~
[( t > alpha then alpha := t;
.if atpha ;~ beta then F, ot__~o done (2.J)
.e n_ql;
done: AI.PttABETA := alpha
enc___ I_
end
The atpha-beta procedure (from [3])
The functi.on denoted by [ i,s the evatuation function whi.ch
assigns s ta t i c ualue,¢ to termi,nat posiHons.
Knuth and Moore [3 ] have shown this procedure to be
co r rec t i,n the sense that the ca|t ALPHAf3ETA(P,-oo,+oo)
assigns to pos[ti,on P the value MINIMAX(P), which i,s the
va lue assi,gned by the minimax procedure. More genera[i,y,
t hey showed [3, p. 297] that:
AI.PHABETA(P,alpha,beta) ~ atpha,
i.f MINIMAX(P) ~ atpha, (2.2)
ALPHABETA(P,atpha,beta) = MINIMAX(P),
i.f alpha < MINIMAX(P) < beta, (2.3)
ALPHABETA(P,atpha,beta) ~ beta,
[f MINIMAX(P) ~ beta. (2.4)
The same tree used in Figure 2.1 to i t [us[rate the
mEn[max procedure i.s shown i.n Fi.gure 2.3 to i.ttustrate the
ef fects of the w-/~ pro¢edure.
"W
• : k , ,_
Fi.gure 2.3 - Searching a game'[tee with the c¢-/~ procedure
The branches pruned by ti le procedure are indi.cated wi th
dashed ti.nes, and the nodes marked with a ci.rcte have not
been comp[ete ty exptored. We observe that onty 8 out of
the 16 te rmina l posi,t(ons and 19 out of ati, t i le 31 nodes are
examined by the ~--/'3 pruni,ng algorithm i,n this exampte,
reduci,ng 8 rea t ty the cost of searchinF, the tree. As i.s seen
by compar[nt~ Fi,gures 2.! and 2.3, the vatues backed-up by
the ~ - f l procedure to some [nternat nodes are not
necessar i ty the same as the values backed-up by the
mini.max procedure, as ref lected by the i,ndetermi,nati,on i,n
equati .ons.(2.2) and (2.4). The t o p value, however, i.s not
a f fec ted by thi,s i,ndetermi,nation.
2.2 - Some properties of the o~-f3 pruning algorilhm
In thi.s secti,on, we wi t [ introduce some notations whLch
wi.tt be used throughout, and we welt reestabti.sh, i.n terms of
the Nega-Max approach, an i,nit~at resutt of [],] givi,n 8 a
- 299-
necessary and suffi.ci.ent conddi.on for any node of a game
t ree to be exami,ned by the ot-/3 pruni,ng atgori,thm.
2.2.1 - Notations
As [n [3], we wi l t use the Dewey decimal notati,on to
represent a node i,n a tree. Ivloro preci,sety, let c, the empty
sequence, denote the root of the game tree. The.n, i.f
denotes some i.nternat node of the tree wi,th n sons, ~. j wi.tt
denote the j - t h son of node ~, for j = 1 ..... n. In Fi.gure 2.4,
node 4.L3.4.3 i,s the node at depth .5 whose path from the
root i,s i.ndi.cated wi,th a darker ti,ne.
¢(~) ,, 2
~4.D -
The value assodated wi,th some node c7 of a game tree
by the minimax procedure tsee Secti,on 2.1) wi, tt be denoted
by u(J). Then, if ~7 i,s a termi,nat node, rioT) i,s the #tat/c
ua£~ce asi,gned to that terminal posi.tion0 and, i.f c7 i,s an
Lnternat node, o(J) i,s the value backed-up to node ~ by the
mLni.rnax procedure. In the tatter case, i,f node ~/ has r¢ sons,
u(cT) i.s gi.ven by:
u(J) = max{ -v (2 . j ) l ! < j < , } . (2.5) In Fi,gure 2.4, the nodes on the path from the root to node 4.1.3.4.3 are evaluated through formula (2.5) whi,te the other nodes (Lnctuding 4.1.3.4.3) are shown as terminal nodes and are assLgned arbi t rary values. (Nodes are labeled wi.th thei.r values.) While the values u(J) deal wi.th the stati,c aspect of a game tree, the quantit ies we wi,tt i.ntroduce next deat more wi . th the dynamic aspect of the tree when bei,ng searched by the o~-/3 procedure. For any node J . j at depth d ;,_ 1, we define: c(J . j ) = max{ -v(; / . i ) I I .~ i ~ j - I } . (By convention, the maxi,mum over an empty set i.s defi,ned to be -co; Ln parti,cular, e(~/. l)= -oo.) For the root of the tree we also deft.no c(~) = -co, The quanti.ty c(~7) accounts for the i.nformati,on provi.ded to node 3 by Lts e/tier brothers. These values are i.ndi,cated to the right of the game tree shown Ln Fi.gure 2.4 for al l nodes on the path to node 4.L3.4.3; only the nodes i.ndk:ated wi,th .,;quares are used i.n computi.ng these vatues. We fLnatl.y defi,ne for any node c7 = Jl . . . . . Jd at depth d a X i.n a game tree two quanti.ti.es di.rectty associ,ated wi,th node ~ by the ¢v-/~ procedure. For i = 0 ..... d-X, tet o7i = J l . . . . . Jd-i" We deft.he: ¢e(~) = max{ c ( ~ i ) I i is e=/en, 0 ~ i ~; d - I } , /~(~/) = -max{ c (~ i ) l i i.s odd, O < i < d - I } . I t i.s convenient to £1efi.ne these two quanti.ti.es for the root of the game tree by ~(~)=-oa and /~(¢)= +oo (whi.ch i.s consi,stent wi,th the defi.ni,ti,on). These u- and /~-vatues are shown i.n Fi.gure 2.4 for the node 4.1.3.4.3 along wi.th thei.r defi.nLti.ons. 2.2.2 - Necessary and sufficient condition for a node to be explored by the ¢~-/J procedure The fottowi,ng lemma justifi,es the notati,ons we just in t roduced i.n the preceding secti,on. Lemma 2.1 : Assume that, i.nitia[ty, the root of a game tree i.s exp lored by the ~-/3 procedure through the call ALPHAE3E TA(root,-oo,÷oo) . (2.6) Then, i,f node J is examined, i.t i.s through a cart of procedure AI.PHA|3ETA i,n which the parameters alpha and beta sati,sfy: alpha = o f f ~ ) , and beta = /9(~) . (2.7) - 3 0 0 - Proof: If ~7 = Jl . . . . . Jd denotes some node explored by the procedure at depth d ~ 1, t,et, as before, ,-7 i ~ Jl ..... Jd4, for 0 < i ~d - l . Thus node //1 is the father of node ~, white, Lf j~y> 2, node ~ l l . ( j d – l ) Ls the brother of ~ immediately
preceding ~/. (and explored just before ~/). Observe that, Lf
Jd = 1, c(~ O) = e(~]) = -¢o and therefore:
oKo~) = max{ c(J i ) } i Ls even, 0 ~ i ~ d – I }
= – [ -max{ e(Ji,+l) I i, is odd, 0 < i, < d-2 } ]
(similarly,/~(,7) = -(v(t71)). Observe also that, if Jd ~ 2:
or(2) = max{ oK(72), eL,7) }
= max{ ~ q 2 ) , ¢ [ ; t l . (?d -D ] , -u [21 . ( ja -D] }
and that i3(,7) = t~ [J l . ( j d - l ) ] .
By the cat,L of tLne (2.6), retat~ons (2.7) certainly hold for
the root of the game tree, since eL( t )=- (~ and 13(t)= +co.
Then the proof folt,ows by induction from EnspectEon of the
procedure ALPHA(ETA, and 'from the relations we derived
above. I
The for,Lowing theorem states a useful ret,ati.on that
characteri.zes the fact that a node of a tree is explored by
the o¢-/3 pruning algorithm. This relation was first
estabtLshed by Futter, Gaschnig and GiLtogty [1] wi.th
d i f ferent notations Ln terms of the MLn-Max model,
Theorem 2.1 •
Assume that, ini t ial ly, the root of a game tree Ls
explored by the 0~-/3 procedure through the call
ALPHABE TA(root,-oo,+oo) .
Then, an arbitrary node ~7 of the game tree wi l l be
subsequen t l y explored i.f and only if
~(o~) < /~(~). (2.8)
Proof:
Because of the presence of Line (2.1) Ln the procedure
ALPHABETA, the result for,tows directly from the result of
Lemma 2. l . i
Since i.t wi l t be more convenient in the following
sections, rather than ~(c7) and /~(~), we wi l l use the
quantit ies:
At2) = rn~x{ c(c7 i ) l i i seve" ,O~;L~;d- ] } ,
B(J) ,,- max{ c(Ji:) I/. is odd, 0 < ~ < d- ! } ,
where J~ i.s defi, ned as before. The definEU.ons of A(~) and
B(~.) are more symmetricaL,, and relation (2.8) can at,so be
rewri.tten Ln a more symmetric:at way:
A(~I) + B i l l ) < 0 .
3 - Number of nodes exp lored
p rocedure : d iscrete case
(2.9)
by the o~-/3
As Ln [1] and [3], we wLtt evat,uate in this and the
fotlowLng section the amount of work performed Ln searchi.ng
a r a n d o m uni form, game tree usi.ng the ¢v-/~ pruning
algorithm. The defLni.tLon and some properties of random
uniform game trees are given tn Section 3.1. The amount of
work performed by the at-/3 procedure is measured by the
number of terminal nodes examLned during the search and Ls
evaluated tn SectLon 3.2.
3.1 - Random uniform game trees
In order to perform an anat,ysis of the ot-/~ pruning
atgorLthm, we wi.tt remit ourselves and consider the for,towing
class of game trees,
Definition 3.1 •
A game tree in which
(a) art internal, nodes have exactly n sons, and
(b) al l termLnat, nodes (or bottonz posit~on~) are at
depth d
Ls cat,ted a u n i [ o r m lzame tree of degree n and depth d. A
uniform game tree which satisfies the additional condi.tLon
(c) the vat.ues assigned to at,t terminal, nodes (or
bot tom ualu.es) are independent i.dentLcaLLy
distr ibuted random variables
Ls called a tone{on= uni.J'orn= g~nze tree, or, for short, a rug
tree. i
- 301 -
UnLess otherwise specified, we wttt only consider
throughout a rug tree of degree n and depth d.
Since the value backed-up to a node by the minimax
procedure only depends on the backed-up values of its sons,
we immediately observe that, by condition (c), the backed-up
values of aLL nodes at the sam.e depth are also independent
identicaLLy dist r ibuted random variables. In the remainder of
the section, we wiLL assunie that the bottom values are
drawn from the f inite set { k / m l - m ~ k ~m }, for some
nt ~ O, and we wi l t denote by {p i ( k ) }_m~k~m or simply
{ P i ( k ) } the common probabi l i ty distribution for the
backed-up values of at[ nodes at depth d - i ([. e., p i ( k ) [s
the p robab i l i t y that the value, u(J) , backed-up by the
minimax procedure to some node c7 at depth d - i be k /m) . In
par t icu lar , {pO(k) } t.q the common probabi l i ty distribution for
al l bottom values, and {pd (k ) } is the probabil i ty distribution
for the value backed-up to the root of the rug tree.
The foLLowing temma states the relations between these
p robab i l i t y distribution.-,.
Lemma 3.1 :
For i = O, .., d - I , we have:
p i . l ( - n t ) + ;.. + P i + l ( k ) = [P i t - k ) + ... * p i ( m ) ] n . (3.1)
Proof=
Let ~/ be some internal node at depth d - i - l , then by
equat ion (2.5), v ( d ) ~ k if and only if -u(o?.j) < k, for
j = 1, ..., n. Equation (3.1) foLLows easily from the fact that
a l l var iables u( ; ] . j ) are independent. B
Since the quanti ty P i t - k ) * ... * P i (m) wil t occur again
tater on, we define for i = O, 1, ... and - m ~; k ~; m:
F i ( k ) = p i ( - k ) + ... * P i ( m ) .
For c o n v e n i e n c e , we also define p i ( - m - J ) = O. Note that
p i ( k ) ts a non-decreasi.ng function of k which satisfies
P i t - m - l ) = 0 and P i (m) = P i t - m ) * ... ÷ p i (m) = 1. By
rewr i t i ng equation (3.1), we see that Pi satisfies:
p i . l ( - k - l ) = 1 - [ p i ( k ) ] n for i = O, 1 .... , (3.2)
ancI, therefore:
p i , 2 ( k ) = 1 - { ! - [ p i . ( k ) ] n ] a f o r i = O, 1, . . . . ( 3 . 3 )
The foLLowing quantities wi l t also be useful in
Section 3.2. For i = O, I, ... and -m. - I .~ k ~ m, define:
p i ( k ) = I + [ p i ( k ) ] * ... + [P i ( k ) ] n ' l , (3.4)
and
o ' i ( k ) = I * [ p i t - k - l ) ] + . . . . [ p i ( - k - l ) ] n - I . (3.5)
Observe that P i t - m - l ) = o ' i (nt) . 1 and p i (m) = o ' i ( - n t - l ) = n.
Lemma 3.1 establishes the probabi l i ty distributions for
at[ the values in the nodes of a rug tree. The next [emma
establ ishes a similar result for the quantities c(rT) defined in
Section 2.
Lemma 3.2:
Let J . j denote any node at depth i, where i = 1, .... d. If
, j = 1, c ( J . j ) = -oo. If j ~. 2, then the probabi l i ty distr ibution
of c ( ~ . j ) , denoted by {qk(c ] . j ) }_nt~k~m, satisfies:
q _ m ( ~ . y ) + .:. + qk( [ ] .y) = [ p d _ i ( k ) ] J ' l . (3.6)
Proof:
When j = 1, ¢ ( J . j ) =-oo by definition. When j ~ 2 ,
equat ion (3.6) foLLows from the same argument given in the
proof of Lemma 3.1. |
In order to evaluate, through equat[on (2.9), the
p robab i l i t y that a terminal node is explored, we first need to
determine the probabi l i ty distributions for the two
quant i t ies A( [ / ) and B{,7). This is clone in the foLLowing.
Lemma 3.3:
Let ~ = J d - I . . . . . j l . J o denote any terminal node.
(1) If Ji = I for aLL e~zeft integers i in the range
0 < i ~ d - l , then A ( d ) ~ -co.
(2) Otherwise, the. probabi l i ty distribution for A(~) ,
denoted by {ak(~ t ) }_m
var iables c(~7~) are i,ndependent, equal{on (3.7) foLLows from
equati.on (3.6) by observi.ng that, Ln the product T'[e, a factor
correspondEng to Ji = 1 amounts to 1. iii
The Last lemma [n thEs sect[on states the probab[t{ty of
exp lor ing a terminal node.
Lemma 3.4:
Let J = J d – I . . . . . j l . J o denote any termi.nat node. The
probab{t i . ty ;Y(07) that node ~/ i.s exam{ned by the
r~–/~ procedure {s gLven by ;Y(,}) = I if j~ = I for at{ euett
i,ntegers i: i,n the range 0 ~ i .~ d – l , or for at[ odd i,ntegers /,
[n the range 1 .,; i .~ d– I , and by
~(~7) — – m . ~ m – I ~k( ‘7) [ 6 – m ( 7 ) * . . . . b – k – l ( ~ t ) ] (3.9)
otherwLse.
Proof:
When j i = I for at[ even i’ntegers i [n the ranF.e
0 ~; ~ s; d – I t by Lemma 3.3 A(~)) ~ -co. Hence A(~/) + B(~/) = -oo
too, and by Theorem 2.1 node 0 7 [s certai,n[y exptored.
Si,.m[[arty when J i = 1 for al.L odd {ntegers [n the range
1 ~ i ~ d – l .
Otherw{se, both A ( J ) and H(,’~) are f[n{te. Let A(J ) ,= ~’k”
We observe that A(~7) + B(f’J) < 0 i,f and only [f -m ~; k ~; m- I
and -Z,n~ .~ B(, ')) .~ ~ - k - l " Hence, equati,on (3.9) foLLows from
Theorem 2.1 and the fact that A(,} ) and B(J ) are i,ndependent
var iables, m
Us[ng equati,ons (3.7) and (3.8), equati,on (3.9) can be
rewrLtten as:
~r(~) ,. -m,.~-.~n~-! ak(cT) Fie [Pi ( -k- l )] j i - I ,
~c~) = -m~.,-1 {Tie [W~)14-1 " Fie { W k ' l ) ] 4 - 1 )
~, T-[ o {(,,~-k-l)] j i - I (3.1o)
( recal l that p i ( - m - l ) = 0).
3.2 - Number of terminal nodes examined by the ~ - ~ pruning
algorithm: discrete ca.~e
We are now able to evaluate the amount of work
per formed by the w../;t procedure while searchi,ng a rug tree.
As i,n [1] and [3], we have chosen to measure the amount of
work by the number of termi,nat nodes exam[ned by the
procedure. (We wi.tt also consi,der briefly, at the end of the
secti,on, the total number of [nternat and fermi,nat nodes
exp lored by the procedure as a measure of performance.)
Theorem 3.1 :
The average number, Nn,d(nz) , of bottom posit[ons
exam{ned by the (~../;t procedure {n searchi,ng a rug tree of
degree n and depth d, for which the bottom values are
( f istr [buted accordi,ng to the di.screte probab[t[ty
di,str[buti,on {Po(k)} . .m.~k~m., i.s 6i.ven by:
N n , d ( n ' ) = t~[d/2J
* _,,L//~m [T[ e pi(k) - TT e pi(k-l)] TT o cri(k) , (3 .11)
where the quanti,t{es p£(k) and o' i (k) are def[ned by
equat{ons (3.4) and (3.5), and where the products denoted
by ]']'e and Fie are deft,ned i,n Lemma 3.3.
Proof:
By (:lefi,ni.ti,on of the probabi.t[ty ;Y(,}), the ave rage number
of bottom posi,tLons examined by the w-/3 procedure [s
Nn,d(n=) = ~ ~(fT) ,
where the sum I.s extended to air termi,nat nodes
- 303 -
~l = Jd - I . . . . . Jl'JO, and is actually a d-nested summation over
the range I .~ Jo -~ , , 1 .~ J l -~ n ..... 1 ~ Jd- I "~ n. The
summation can be rearranged as:
Nn,d (m) = ~ e ~([~) * ~o t((~/) + ~ " tC(~)
- ~t(l . . . . . 1 ) ,
where the three summations Ye, Z~o and z~' correspond to
the three expressions for ~(~) given Ln Lemma 3.4. The
four th term ~'(1 . . . . . f ) is subtracted from the sum si,nce i t Ls
counted by both z~ e and Yo" These two sums are easily
evaluated si,nce aLL the terms K(~) are 1. As ~(1 . . . . . 1) itself
Ls 1, we obtain:
Nn,d (m) - n [d/2] + n [d/2j - 1 "* Z ' tt(,7). (3.12)
It Ls to be noted that the first three terms correspond
exact ly to the number of term[nat nodes examined by the
u-/3 procedure under opti,mat ordering of the bottom' val,ues
(see [5, p. 201]).
We now evaluate the sum ~ ' . inside the sum the terms
~(~) can be eval,uated H1rough equation (3.10). We note that
aLL the summati,ons relat ive to Ji, for i = O, l , ..., d - l , can be
done i.ndependentLy, each one being the sum of a geometri.c
seri,es. Using the quanti,ties pi(k) and ¢ri(k) defined by
equations (3.4) and (3.5), we obtain:
Y ' tt([#) , - r n ~ , t - I []'Te pi(k) - H e I~i(k-l)] T'[° cri(k)
- ]"[e Pi ( m - l ) * 1 .
The theorem fol,tows from this Las t equation and
equatLon (3.12), using the facts that P i ( m ) - n and that
cr i (n t ) = 1. II
The formula of equati.on (3.11) can be easi.ty evaluated
and provides us wi th a measure of' performance for the
at-/3 prunLng al,gorithm. For some appti.cati.ons, however
(espocLatty when the cost of generati.ng moves i.s greater
than the cost of eval,uati,ng posi.ti.ons), i t i.s more convenient
to use the total number of nodes (internal. and termi,nat)
exp lo red by the procedure as a measure of performance. Let
Tr t ,d(m) denote the average of this number. The same way
we evaluated Nn,d(m) , we can eval,uate Tn,d(m) by summLng
the probabit i t i ,es ~'(J) over al,t nodes of the tree. We obtai,n:
° +
where Nin.,d(m) is the average number of nodes examined at
depth i, and is directl.y derived from the expression of
Nn ,d (m) i.n equation (3. t 1 ) by repl,acing d by /. and {PoCk)} by
{Pd_i(I¢)} (recal l that {PoCk)} i.s the probabiLity distri,bution
for the values assigned to the term[nat nodes and that
{Pd_ i (k ) } is the probabil,i.ty distributi,on for the values
backed-up to nodes at depth i).
3.3 - Bi -valued rug trees
Aiithough i t Ls retati,vety easy in most Kame pl,aying
programs to obtain (by inspecti,on of the eval,uation function)
an accurate bound for the range of distinct values assi,gned
to the various posi,ttons of the game, Lt is usuaLLy not so
easy to deri,ve a good estimate for the probabi l i ty
dLstri,buti,on of these val,ues. In the remainder of the section
we. w i l t study rug trees in which the terminal nodes can onty
take on two dist inct values, and we wit[ see, in parti.cutar,
that a change i,n the probabil,ity dL'~tributi.on of these val,ues
can Lead to very i.mportant differences in the growth rate of
Nn,d(n t ) .
We wi,tt assume i,n the fol,towing that the val,ues assigned
to the termLnat nodes of a rug tree can only be ei.ther -1 or
*1 wi,th respec t i ve probabili,ties l - p and p, for some
p ~" [0, 1]. Under these conditions, the number, Tn,d(p), of
termi.nal, nodes exami_ned by the at--/'3 procedure can be
obtai.ned as a parti.cular case of equation (3.11) in whLch
m = 1 and {Po(k)}_m~k~nt is defi,nod by P o t - l ) - l - p ,
Po(O) = O, po ( l ) = p.
Theorem 3.2:
Let PO = p, and , f ° r i . . . . 1,2 , ,i ,et p; = ! " P t - l "
Trt ,d(p) = n [d/2] + n[ d /2 j - I + (Pe-J ) (Po- l ) , (3.13)
wi,th
P e = ]-re P i * l , P o =' I -re Pi* l
1 - P i I - Pi '
- 3 0 4 -
where the product~ Tie and ]7" 0 are defined as before.
P r o o f :
Choose n= = I and define the probabi l i ty distribution
{po(k)}_m
= nfd/21 + nld/2J _ I . (3.14)
This last equation shows that Tn,d(p) reaches its minimum
n [d/2] * n ld /2 j .. I for p = 0 and p = 1. This is in agreement
w i th the result of Slagte and Dixon [5, p. 201] since i t
corresponds to the case when all terminal nodes are
assigned the same value and therefore all possibte cut-offs
do occur. Equation (3.1q) also shows that Tn,d(p) admits a
maxi.mum for p C (0, I); at:hough the exact maximum cannot
be read i ly obtained, we wi l t derive a lower bound m the
fo l low ing . We f i rst establish a preliminary result.
Lemma 3.5:
The unique positive, root, ~n, of the equation
~tt + ~ – 1 : 0
tS In the ~nterva| (0, I). Asymptotically (for large n) ~t
sat isf ies:
1 – ~’n ~ / in n . ( 3 . 1 5 )
P r o o f :
As there is no ambiguity, we wi l l drop the index n from
~’n i.n the fol lowing.
Let g(~.)= x n * x. – 1, note that ~ ‘ (0)=-1< 0 and R(I) = I > O. Since i~(x,) is continuous and strict ly increases
for ~ posi t ive, the equation R'(~) ~ 0 admi.ts a unique positive
root , [ , Whi.ch is in the interval (0, 1).
We observe that equation ~.n + ~. _ I – 0 can be rewri t ten
as
I – ~ ” = I
f rom which we deduce that
I. ~ E > _ _ L _ _ . ( 3 , 1 6 )
r ~ + l
On the other hand, since ~.n = I – ~’, we obtain
rt (.~ – 1) > n ln~” = in(I-T) ,
which shows, along wi th equation (3.16), that
1 – ‘~ < I l n ( n 4 1 ) .-- / L n . 0(.-2). (3.17) ÷ S~mi.tarl.y, taki.ng the logarithm of both sides- of equati~on (3.17), and using the facts that I - ~" - .~rt and that tn ~" > I – ~ , we, obtain:
1 :
~” < I + |n(nAn n+l ) '
hence:
I - ~" > / | n ( n A n n+l) + (9 [ ( / in n) 2]
– – I . . • In t . . ) .
Equation (3.15) fol lows direct ly from the previous equation
and equation (3.17). I
When p = ~’n we obtain immediately that, for i = O, 1, …,
Pi = ~’n” Hence
Pe = [.~n/(l-.~n )] [d/2] and eo = [ .~n/( l – [n ) ] [d /2 j ”
From equations (3.13) and (3.15) i t follows that, for large n:
T n , d ( [ n ) ~ [nAn n] d , (3.18)
wh i le equation (3.14)shows that
Tn,d(O ) = Tn,d( i ) ~ (3.19)
Equations (3,18) and (3.19) indicate that Tn,d(p) can be
la rge ly influenced by the variations of the probabiKty
d is t r ibu t ion for the static values. This result can be easily
genera l ized to Nn,d(m). In the next section, we wi l l derive
an approximat ion to Nn,d(.m) which corresponds to its worst
case behavior.
4 – Number of nodes exp lo red by t h e o~-/3
p r o c e d u r e : cont inuous case
In this section, we derEve an approximation to Nn,d(m)
by cons ide r ing , time l imit of the finite series of
– 305 –
equati.on (3.1 1) when m |ends to infi.ni.ty whi le the discrete
probabiAi. ty distri.buti,on {Po(k)}_m.~k~m tends to a conti.nuous
probabi.U.ty di.stributi.on. Thi,s corresponds to the case
studi,ed by Fui,ter, Gaschn[g and Gi.ttogty [1] and by Knuth
and Moore [3 ] when the terminal, nodes of a rug tree are at[
assi.gned di.sti.nct va!.ues. In parti.cutar, we wi,tt r~estabtiºsh
(wi,th a much si,mp[er formul.a) a resutt of [1].
4.1 – Notations end preliminary results
We fi.rst i.ntroduce the sequence of functiºons { f i } mapping
the i.ntervai, [0, / ] i.nto i,tsetf, and clef[ned recursi.vety by:
re(=.) = x ,
f i t= ) = I — {z – [ , r~_l (~ . ) ]”}” f o r ~ = 1, 2 . . . . .
] [ [s read [ ty veri,f[ed by i,nduct[on on i that art functi,ons f i
a re s l t r [c t ty i,ncreasing on [0, I ] and sati,sfy [i(O)= 0 and
f i t 1 ) = 1, L e., 0 and I are two fi,xed poi,nts of the functi,ons
f i , fo r at[ n and i. The functi,on [ i wi,i,t be shown to be
re ta ted to the quanti,ti,es ~2i(k) defi,ned i,n Secti,on 3.1.
Si.mi.l.arty, i.n rel.ati, on to the quant[ti.es P2i.(k) and o~2~,j(k) ,
we defi.ne the foitowi.ng functiºons on [0, 1]: for /. = 1, 2, …,
Let
l – [ f i _ / ( z ) ] n
r i (=) l_fi_l
si(x) [ [ i_ l
functions C m for m = O, 1, . . as follows. For – m ~ k ~m, Let
~’1¢ = k /m. Functi.on C,~ Is defined as the following step
function;
0
C.,(x) = C(x. k)
!
i f x < ~ _ t n =0,
if x k < x. < Xk. l , for -m ~; k ~; m-X,
if 1 = x.nt ~ ~..
The sequence of functions {C,m} constitutes a sequence of
approxi,mations to the continuous function G. (]t should be
noted that the convergence of the sequence is uniform on
the interval [0, 1].) The function Cnt corresponds to the
cumulat ive distributLon of the discrete probabi,tl.ty
d{stributl.on Polk )= Cm(xk ÷) -Cm(X.k-) associated with the
poi,nts =k = k/m., for k = -m, ..., m.
Usl.ng the approximation {Po(k)}_nt~;k~m to the densdy
functl.on g, equation (3.1 1 ) provides us with an
approxLmati.on to the average number of bottom posi.tLons
examl.ned by the oz-fl procedure in a rug tree in which the
bottom values are drawn from the continuous probabffity
densi,ty functLon @'. When nt becomes Larger, the
approxLmatl.on becomes better, and (due to the uni,form
convergence of the sequence C,t) it can actually be shown
(i,n a rather technical way) that the Limit of Nn,d(m) when
m -~ co corresponds exactly to the average number of bottom
posi t ions examined by the ~../3 procedure Ln the continuous
case. As .a matter of fact, equation (4.3) could be derived
d i rec t l y by considering a continuous probabUity distribution
rather than a discrete one in very much the same way we
der ived equatl.on (3.1 1) in Section 3. This result is stated [n
the fof fowing.
Theorem 4.2:
Let tO(X) = x, and, for i = 1, 2 ..... define:
f~(x) = I - { I - [f~_f~)].}n,
l - [r i_l(~)]"
r i ( = ; l - f ~ _ / ~ ) '
fix.)
si/~') [fi.l(x)]a '
- 307-
R~(¢) = r1(~) ~ ... × r[d2](~.) ,
S;/z) = s1(~) .... ~ ,[i./2j(~).
The average number, Nn,d, of termi,nal, nodes examined by
the =-/3 pruni.ng al.gorithm in a rug tree of degree n and
depth d for whi,ch the bottom values are drawn from a
conti,nuous distri,buti.on is given by:
Nn,c t = ntdl2J , fo I R'd(t).Sd(t).dt. (4.5)
]t i.s to be noted that, unl,ike the case of a diºscrete
prebabi t i ty diºstributi.on, when the bottom values are drawn
from a ¢onti.nuous di.stri,buti.on, the number of termi,nal,
posLLtiºons examined by the 0,-/3 procedure does not depend
on the di.stri,bution function.
4 . 3 - D i s c r e t e case v e r s u s continuous case
SLnce equation (4.5) has been derived as the U.mi.t of
equatiºon (3.1 1), i t is reasonable to investigate the val,i.di,ty of
the approximation of Nn,d(m) by Nn, d. As was seen iºn
Sectiºon 3.3, Nrt,d(m) strongi,y depends on the probabil,i,ty
di.strtbtJtion {PO(k)}_nz.,;k
Thus Defi.ni.tion 1.1 provides us with a measure of
performance useful to compare search algorithms. In the
fottowi,ng, we review some of the resui,ts which have already
been presented in the literat.ure.
Minimax search
The mi,nimax search examines systematically all. nodes of
a tree. It, therefore, examines Nn, d = n d terminal, nodes in a
uniform tree of degree n and depth d, [eading to a branchi.ng
factor
~ntittintct~(n) = n.
~- /3 procedure under optimal ordering
Stagte and Dixon [.5, p. 20J] have shown that, when al.t
possi.bte oz- and /3-(ut-offs occur, the u=/3 procedure
exami,nes
t , /n, d = n r d / 2 ] + nLd /2J _ S
termi.nat positions. In this case, the corresponding branching
factor [s
~opt(n) = e l~ 2 ,
o~-,d procedure (experimental results from El])
Based on a series of s[mulation results, Fuller, Gaschni,g
and Gi,i,i,ogty [1] have argLled that the formula
Nn,d = c(dj.nO.72d + 0.277
consti.tutes a reasonable approximation to the number of
bottom positions examined by the ~–/~ procedure for stoat{
values of n and d, and that 1 :; c(d)~; 2 (at [,east for the
range of vatues they considered). For comparison purposes,
tel us assume that their approximation can be extrapolated
for any n and d. Provided that c(d) l i d –~ I when d -~ oa, we
obtain
~oL..//n) ~ n 0.72 ”
In v iew of the results of Section 3.3, we can questi,on the
accuracy of the approximation for i,arge n st,ace it foi,i,ows
from Theorem 3.2 that
t~oo [Tn,d([n)] l id = O
The temma fot tows by observing that, for i = 1, 2, .., [ i -1 is a
o n e – t o – o n e funct ion from [0, 1] to i tself. •
Lemma 5.2 show~ that, in order to study the maximum of
pi(x) , when x (” [0, 1], i t is suff icient to study the maximum
of the po[ynomiat
pi(x ) = 1_1-__ xn-~ – J – (lx-nXn)n ‘ for xC [ 0 , 1 ] .
Observe that M n ~. p l (~n ) = [ f n / ( l – f n ) ] 2, in part icular,
s ince i t can be checked easi ly that, for n = 2, 3; …,
~,t > J-E/(l+J-E), i t fot tows that
M n > n for n = ,2 ,3 , . . . . (5.5)
Theorem 5.3
The branching factor of the ~-/~ pruning argot[thin for a
rug t ree of degree n satisfkes:
/~_p(n) ~ ,/-M-~n, (5.6)
where M n is def ined [n Lemma 5.2.
Proof=
From the def in i t ion of R2h(t), we obtain for h = 2, 3, …:
R’2h(t) = R’2h_2(t).rh(t) + R2h_2(t).r’h(t).
By mutt[pt[cation by S2h(t) i t fo l lows that
R’2h(t).S2h(t) = R’2h_2(t).S2h_2(t).Ph(t)
+ R2h_2(t).S2h_2(t).r’h(t).Sh(t).
Si.nce, for t 6 [0, I ] , atl. factors in this equation are
non-negat i .ve, we deduce, using the i’esuits of Lemma 5.2 and
the fact that Sh(t) ~; n when t C [0, 1], that:
R’2h(t)S2h(t) ~ MnR’2h_2(t)S2h.2(t) + n Mhh-I r’h(t).
Since , in addi t ion ,
R’2(t) S2(t) = r } ( t ) s l i t ) ~; n r ‘ l a ) ,
i t fo t tows that for t C [0, I ] and h = I, 2, …:
R’2h(t) S2h(t) ~ n Mn h ‘ l [ r i ( t ) + … + r ‘h(t)]. (5.7)
Let In, d be the integral, def ined in equation (4.5). By
i .n tegrat ing ineqt la l i ty (5.7) over [0, I ] we see that In, d
sat is f ies :
In ,2h ~; n Mnh-I [h(n..l)] = n(n- l ) h Mnh ‘ l
s i n c e ri(O) = 1 and r i ( l ) ~ n for i = 1,2,. . . . This shows that
Nn,2h ~; n h + n(n.-l) h. Mnh”J .
Equat ion (5.6) now fottows d i r e d | y from inequati ty (5.5). II
5 . 4 – Numerical results
Tabte 5.1 summarizes the results of this section. ]t
p resents time variou.,, lower and upper bounds we have
d e r i v e d for the branching factor of the w-/3 pruning
a tgor i thm from equations (5.3) and (5.6). Atthough we have
not been abte to give an estimate for the asymptotic growth
of vr-~n, we can ea.,dty deri.ve an upper bound for this
– 3 1 1 –
quant i ty by studying rug trees of depth 2 since:
M n < Nn, 2 .~ 2n l ' n / ( l -~n ) - [~n/(l-~n)] 2 ~ 2n2An n , whi.ch shows that ~ ~ O(n/.CYff~). The humeri.cat results of Table 5.1 l.ndical,e that VM n is a much better upper bound for 1~0"./3(n)than .~n~n/(l-~n) for the range of values we have consi.dered. n 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 l,ower bnd. ~n/(1-~n ) 1.618 2.148 2.630 3.080 3.506 3.915 4.309 4.692 5.064 5.427 5.782 6.130 6.473 6.809 7.141 7.468 7.791 8.110 8.425 8.736 9.045 9.350 9.653 9.952 10.250 10.545 10.838 11.128 11.416 11.703 11.987 1.622 2.168 2.678 3.166 3.638 4.098 4.549 4.993 5.430 5.862 6.290 6.713 7.133 7.549 7.963 8.373 8.782 9.188 9.591 9.993 10.393 10.791 11.188 11.583 11.976 12.369 12.759 13.149 13.537 13.924 14.310 upper bounds Vn~nl(l-~n; 1199 2.538 3.243 3.924 4.587 5.235 5.872 6.498 7.116 7.726 8.330 8.927 9.519 10.107 10.689 11.268 11.842 12.413 12.980 13.545 14.106 14.665 15.221 15.774 16.325 16.873 17.420 17.964 18.507 19.047 19.586 from [3] 1284 2.666 3.397 4.095 4.767 5.421 6.059 6.684 7.298 7.902 8.498 9.086 9.668 10.243 10.813 11.378 11.938 12.494 13.045 13.593 14.137 14.678 15.215 15.748 16.265 16.778 17.288 17.796 18.300 18.802 Table 5.1 - Bounds on the brsnchi.ng factor of the. 0'-/3 pruning algorithm 6 - C o n c l u s i o n s and open problems We have presented an an.atysi.s of the performance of the o~-/3 prunl.ng algorithm for searchi.ng a uniform tree of degree n and depth d when the values assi.gned to the terrninat nodes are independent identically di.stributed random variables. The analysis takes i.nto account both shal low and deep cut-offs and we have also consi.dered the effect of equatl, ti.es between the values assigned to the terml.nat nodes. A sl,mpl,e formula was derived, i.n Section 3, to measure the number of termi.nal, nodes examined by the or-/3 procedure when the bottom values are drawn from a flni.te range accordi.ng to an arbitrary discrete probabi.l,ity dl,stri.bution. Although the formula can be easi.l,y computed numerical ly, a direct analysis is made difficult by the presence of the probabfli.ty distr~butl.on. When only two di.stinct values can be assigned to the terminal, nodes, i.t i.s shown that the number of termi.nal, nodes examined by the 0..-/3 procedure (:an be at tea.~d el(n/In n)d]; and, i.n ti.ght of the results of Section 5, l,hi.s corresponds to the worst case behavi.or of the algorithm (over all. discrete probabi.l.i.ty di.stri.buti.ons). A formul,a was then presented i.n the form of an integral to measure the number of termi.nal, nodes explored by the e¢-/'3 procedure when the bottom values are all. di.st[nct. An analysis of the i.ntegrat shows that the branching factor of the ce-/3 pruning algorithm is E)(n//n n). a result whi.ch confi.rms a claim by Knuth and Moore [3] that deep cut-offs only have a second order effect on the behavi.or of the ¢e--/3 pruning algorithm. Although the assumpti.on used in Secti.ons 4 and 5 when the bottom values are all, distinct is not reati.stic for most practi.cat appti.cati.ons, the results we have alert.red from l.t gl,ve us some i.nsi.ght into the worst case behavior of the ¢e-/3 pruning algorithm when equati.ti.es between bqttom values are possible, and they are a useful, complement to the formula of Secti.on 3. Si.mil,arty, the branchi.ng factor anatyzed in Section 5 provi.des us only wi.th an asymptoti.c measure of performance for tile ez-/3 pruni.ng atgori.thm (i.. e., for trees of large depth). As i.ndicated by the results of Sectl,on 3.3, however, the branchi.ng factor can at,so be used as a real.isti.c measure of the worst case even for smart trees. We have measured the offi.ci.ency of the u-/3 pruni.ng atgori.thm by the average number of terminal, nodes explored - 312 - by the aLgorithm, it wouLd be interesting to also obtain an estimate for the standard deviation of this number. The scheme we have considered for assigning values to terminal nodes of a uniform tree tent itself easily to analysis; i t is, however, very simplistic. Different schemes tot assigning static values have been proposed in [ t ] , [3] and [4]. Analyses of those schemes would be helpful for various applications~ a step in this direction was presented in [4] for game trees of depth 2 and 3. Acknowledgements I wish to thank H. T. Kung and B. W. Weide for reading and cornmenting on earlier (Irafls of this paper. Re fe rences [ I ] Fuller, S. Ft., GaschnEg, J. G., and Giltogty, J. J., Analysis of the alpha-beta prl|nin 8 algorithm, Carnegie-Mellon University, Computer Science Department Report, July 1973. [2] Gitlol~ly, .1. J., The TechnolOgy chess proBram , Artificial InteUiEettce , Vet. 3, No. 3, 1972, pp. 145-163. [3] Knuth, D. E., and Moore, R. W., An analysis of alpha-beta pruni~ng, A,.ti[tci~zl lnlelliRence, Vet. 6, No. 4, 1975, pp. 293-326. [4] Newborn, M. M., The efficiency of the alpha-beta search on trees with branch--dependent terminal node scores, Art i f ic ia l Intelligence, Vet. 8, No. 2, 1977, pp. 137-153. [5] Slagte, J. R., and Dixon, J. K., Experiments with some programs that search game trees, Journal of the ACM, Vet. 16, 1969, pp. 189-207. - 313-