acm-final.ps

这是博弈论算法全集第四部分:剪枝算法,其它算法将陆续推出.以便与大家共享

%!PS-Adobe-2.0
%%Creator: dvips 5.55 Copyright 1986, 1994 Radical Eye Software
%%Title: acm50j2.dvi
%%CreationDate: Mon Dec  4 09:38:42 1995
%%Pages: 7
%%PageOrder: Ascend
%%BoundingBox: 0 0 612 792
%%DocumentFonts: Times-Roman Times-Bold Times-Italic Symbol
%%EndComments
%DVIPSCommandLine: dvips acm50j2
%DVIPSParameters: dpi=300, comments removed
%DVIPSSource:  TeX output 1995.12.04:0937
%%BeginProcSet: tex.pro
/TeXDict 250 dict def TeXDict begin /N{def}def /B{bind def}N /S{exch}N
/X{S N}B /TR{translate}N /isls false N /vsize 11 72 mul N /hsize 8.5 72
mul N /landplus90{false}def /@rigin{isls{[0 landplus90{1 -1}{-1 1}
ifelse 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale
isls{landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div
hsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul
TR[matrix currentmatrix{dup dup round sub abs 0.00001 lt{round}if}
forall round exch round exch]setmatrix}N /@landscape{/isls true N}B
/@manualfeed{statusdict /manualfeed true put}B /@copies{/#copies X}B
/FMat[1 0 0 -1 0 0]N /FBB[0 0 0 0]N /nn 0 N /IE 0 N /ctr 0 N /df-tail{
/nn 8 dict N nn begin /FontType 3 N /FontMatrix fntrx N /FontBBox FBB N
string /base X array /BitMaps X /BuildChar{CharBuilder}N /Encoding IE N
end dup{/foo setfont}2 array copy cvx N load 0 nn put /ctr 0 N[}B /df{
/sf 1 N /fntrx FMat N df-tail}B /dfs{div /sf X /fntrx[sf 0 0 sf neg 0 0]
N df-tail}B /E{pop nn dup definefont setfont}B /ch-width{ch-data dup
length 5 sub get}B /ch-height{ch-data dup length 4 sub get}B /ch-xoff{
128 ch-data dup length 3 sub get sub}B /ch-yoff{ch-data dup length 2 sub
get 127 sub}B /ch-dx{ch-data dup length 1 sub get}B /ch-image{ch-data
dup type /stringtype ne{ctr get /ctr ctr 1 add N}if}B /id 0 N /rw 0 N
/rc 0 N /gp 0 N /cp 0 N /G 0 N /sf 0 N /CharBuilder{save 3 1 roll S dup
/base get 2 index get S /BitMaps get S get /ch-data X pop /ctr 0 N ch-dx
0 ch-xoff ch-yoff ch-height sub ch-xoff ch-width add ch-yoff
setcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-yoff
.1 sub]{ch-image}imagemask restore}B /D{/cc X dup type /stringtype ne{]}
if nn /base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{dup dup
length 1 sub dup 2 index S get sf div put}if put /ctr ctr 1 add N}B /I{
cc 1 add D}B /bop{userdict /bop-hook known{bop-hook}if /SI save N @rigin
0 0 moveto /V matrix currentmatrix dup 1 get dup mul exch 0 get dup mul
add .99 lt{/QV}{/RV}ifelse load def pop pop}N /eop{SI restore showpage
userdict /eop-hook known{eop-hook}if}N /@start{userdict /start-hook
known{start-hook}if pop /VResolution X /Resolution X 1000 div /DVImag X
/IE 256 array N 0 1 255{IE S 1 string dup 0 3 index put cvn put}for
65781.76 div /vsize X 65781.76 div /hsize X}N /p{show}N /RMat[1 0 0 -1 0
0]N /BDot 260 string N /rulex 0 N /ruley 0 N /v{/ruley X /rulex X V}B /V
{}B /RV statusdict begin /product where{pop product dup length 7 ge{0 7
getinterval dup(Display)eq exch 0 4 getinterval(NeXT)eq or}{pop false}
ifelse}{false}ifelse end{{gsave TR -.1 .1 TR 1 1 scale rulex ruley false
RMat{BDot}imagemask grestore}}{{gsave TR -.1 .1 TR rulex ruley scale 1 1
false RMat{BDot}imagemask grestore}}ifelse B /QV{gsave newpath transform
round exch round exch itransform moveto rulex 0 rlineto 0 ruley neg
rlineto rulex neg 0 rlineto fill grestore}B /a{moveto}B /delta 0 N /tail
{dup /delta X 0 rmoveto}B /M{S p delta add tail}B /b{S p tail}B /c{-4 M}
B /d{-3 M}B /e{-2 M}B /f{-1 M}B /g{0 M}B /h{1 M}B /i{2 M}B /j{3 M}B /k{
4 M}B /w{0 rmoveto}B /l{p -4 w}B /m{p -3 w}B /n{p -2 w}B /o{p -1 w}B /q{
p 1 w}B /r{p 2 w}B /s{p 3 w}B /t{p 4 w}B /x{0 S rmoveto}B /y{3 2 roll p
a}B /bos{/SS save N}B /eos{SS restore}B end
%%EndProcSet
%%BeginProcSet: texps.pro
TeXDict begin /rf{findfont dup length 1 add dict begin{1 index /FID ne 2
index /UniqueID ne and{def}{pop pop}ifelse}forall[1 index 0 6 -1 roll
exec 0 exch 5 -1 roll VResolution Resolution div mul neg 0 0]/Metrics
exch def dict begin Encoding{exch dup type /integertype ne{pop pop 1 sub
dup 0 le{pop}{[}ifelse}{FontMatrix 0 get div Metrics 0 get div def}
ifelse}forall Metrics /Metrics currentdict end def[2 index currentdict
end definefont 3 -1 roll makefont /setfont load]cvx def}def
/ObliqueSlant{dup sin S cos div neg}B /SlantFont{4 index mul add}def
/ExtendFont{3 -1 roll mul exch}def /ReEncodeFont{/Encoding exch def}def
end
%%EndProcSet
%%BeginProcSet: special.pro
TeXDict begin /SDict 200 dict N SDict begin /@SpecialDefaults{/hs 612 N
/vs 792 N /ho 0 N /vo 0 N /hsc 1 N /vsc 1 N /ang 0 N /CLIP 0 N /rwiSeen
false N /rhiSeen false N /letter{}N /note{}N /a4{}N /legal{}N}B
/@scaleunit 100 N /@hscale{@scaleunit div /hsc X}B /@vscale{@scaleunit
div /vsc X}B /@hsize{/hs X /CLIP 1 N}B /@vsize{/vs X /CLIP 1 N}B /@clip{
/CLIP 2 N}B /@hoffset{/ho X}B /@voffset{/vo X}B /@angle{/ang X}B /@rwi{
10 div /rwi X /rwiSeen true N}B /@rhi{10 div /rhi X /rhiSeen true N}B
/@llx{/llx X}B /@lly{/lly X}B /@urx{/urx X}B /@ury{/ury X}B /magscale
true def end /@MacSetUp{userdict /md known{userdict /md get type
/dicttype eq{userdict begin md length 10 add md maxlength ge{/md md dup
length 20 add dict copy def}if end md begin /letter{}N /note{}N /legal{}
N /od{txpose 1 0 mtx defaultmatrix dtransform S atan/pa X newpath
clippath mark{transform{itransform moveto}}{transform{itransform lineto}
}{6 -2 roll transform 6 -2 roll transform 6 -2 roll transform{
itransform 6 2 roll itransform 6 2 roll itransform 6 2 roll curveto}}{{
closepath}}pathforall newpath counttomark array astore /gc xdf pop ct 39
0 put 10 fz 0 fs 2 F/|______Courier fnt invertflag{PaintBlack}if}N
/txpose{pxs pys scale ppr aload pop por{noflips{pop S neg S TR pop 1 -1
scale}if xflip yflip and{pop S neg S TR 180 rotate 1 -1 scale ppr 3 get
ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg TR}if xflip yflip
not and{pop S neg S TR pop 180 rotate ppr 3 get ppr 1 get neg sub neg 0
TR}if yflip xflip not and{ppr 1 get neg ppr 0 get neg TR}if}{noflips{TR
pop pop 270 rotate 1 -1 scale}if xflip yflip and{TR pop pop 90 rotate 1
-1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg
TR}if xflip yflip not and{TR pop pop 90 rotate ppr 3 get ppr 1 get neg
sub neg 0 TR}if yflip xflip not and{TR pop pop 270 rotate ppr 2 get ppr
0 get neg sub neg 0 S TR}if}ifelse scaleby96{ppr aload pop 4 -1 roll add
2 div 3 1 roll add 2 div 2 copy TR .96 dup scale neg S neg S TR}if}N /cp
{pop pop showpage pm restore}N end}if}if}N /normalscale{Resolution 72
div VResolution 72 div neg scale magscale{DVImag dup scale}if 0 setgray}
N /psfts{S 65781.76 div N}N /startTexFig{/psf$SavedState save N userdict
maxlength dict begin /magscale false def normalscale currentpoint TR
/psf$ury psfts /psf$urx psfts /psf$lly psfts /psf$llx psfts /psf$y psfts
/psf$x psfts currentpoint /psf$cy X /psf$cx X /psf$sx psf$x psf$urx
psf$llx sub div N /psf$sy psf$y psf$ury psf$lly sub div N psf$sx psf$sy
scale psf$cx psf$sx div psf$llx sub psf$cy psf$sy div psf$ury sub TR
/showpage{}N /erasepage{}N /copypage{}N /p 3 def @MacSetUp}N /doclip{
psf$llx psf$lly psf$urx psf$ury currentpoint 6 2 roll newpath 4 copy 4 2
roll moveto 6 -1 roll S lineto S lineto S lineto closepath clip newpath
moveto}N /endTexFig{end psf$SavedState restore}N /@beginspecial{SDict
begin /SpecialSave save N gsave normalscale currentpoint TR
@SpecialDefaults count /ocount X /dcount countdictstack N}N /@setspecial
{CLIP 1 eq{newpath 0 0 moveto hs 0 rlineto 0 vs rlineto hs neg 0 rlineto
closepath clip}if ho vo TR hsc vsc scale ang rotate rwiSeen{rwi urx llx
sub div rhiSeen{rhi ury lly sub div}{dup}ifelse scale llx neg lly neg TR
}{rhiSeen{rhi ury lly sub div dup scale llx neg lly neg TR}if}ifelse
CLIP 2 eq{newpath llx lly moveto urx lly lineto urx ury lineto llx ury
lineto closepath clip}if /showpage{}N /erasepage{}N /copypage{}N newpath
}N /@endspecial{count ocount sub{pop}repeat countdictstack dcount sub{
end}repeat grestore SpecialSave restore end}N /@defspecial{SDict begin}
N /@fedspecial{end}B /li{lineto}B /rl{rlineto}B /rc{rcurveto}B /np{
/SaveX currentpoint /SaveY X N 1 setlinecap newpath}N /st{stroke SaveX
SaveY moveto}N /fil{fill SaveX SaveY moveto}N /ellipse{/endangle X
/startangle X /yrad X /xrad X /savematrix matrix currentmatrix N TR xrad
yrad scale 0 0 1 startangle endangle arc savematrix setmatrix}N end
%%EndProcSet
TeXDict begin 40258431 52099146 1000 300 300
(/usr/maligne2/guest/aske/Txts/ACM/acm50j2.dvi) @start
/Fa 206[12 49[{}1 25.000000 /Times-Roman rf /Fb 1 1 df<FFFFFEFFFFFE1702
7D891E>0 D E /Fc 157[18 98[{.167 SlantFont}1 33.333332
/Symbol rf /Fd 81[33 7[17 24 120[8 44[{}4 33.333332 /Symbol
rf /Fe 145[19 6[19 103[{}2 37.500000 /Times-Italic rf
/Ff 138[21 12 1[17 1[21 19 21 1[10 2[10 2[12 17 1[17
1[19 97[{}12 37.500000 /Times-Bold rf /Fg 205[15 15 49[{}2
29.166668 /Times-Roman rf /Fh 208[7 47[{}1 25.000000
/Symbol rf /Fi 155[15 100[{}1 29.166668 /Times-Italic
rf /Fj 4 102 df<40C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0
FF7F081E7B950F>98 D<0103030303030303030303030303030303030303030303030303
0303FFFF081E80950F>I<7FFFC0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0
C0C0C0C040081E7B950F>I<FFFF03030303030303030303030303030303030303030303
030303030301081E80950F>I E /Fk 134[23 1[33 23 25 15 18
20 1[25 23 25 38 13 2[13 25 23 15 20 25 20 1[23 11[33
30 1[33 35 1[35 1[43 30 5[28 30 33 1[30 2[23 11[23 23
23 2[11 15 45[{}37 45.643555 /Times-Bold rf /Fl 72[17
5[21 10[19 27 165[{}4 37.500000 /Symbol rf /Fm 1 1 df<FFFFFF80FFFFFF8019
027D8A20>0 D E /Fn 157[21 24 97[{.167 SlantFont}2 37.500000
/Symbol rf /Fo 55[14 25[21 51[16 18 18 28 18 21 12 16
16 1[21 21 21 30 12 18 1[12 21 21 12 18 21 18 21 21 6[23
3[25 1[23 21 25 1[25 1[28 35 23 28 18 14 30 1[25 25 1[28
25 25 6[14 21 21 2[21 21 21 21 21 3[14 10 2[14 14 14
39[{}57 41.666668 /Times-Italic rf /Fp 134[21 1[30 1[23
14 16 18 1[23 21 23 35 12 2[12 23 2[18 23 18 1[21 12[28
23 30 5[28 32 3[32 25 3[28 30 1[21 4[14 12[14 2[21 42[{}30
41.666668 /Times-Bold rf /Fq 47[42 7[14 13[18 8[21 1[23
23 3[18 47[18 21 21 30 21 21 12 16 14 21 21 21 21 32
12 21 12 12 21 21 14 18 21 18 21 18 3[14 1[14 3[39 30
30 25 23 28 30 23 30 30 37 25 30 16 14 30 30 23 25 30
28 28 30 1[18 1[23 1[12 12 21 21 21 21 21 21 21 21 21
21 12 10 14 10 23 21 14 14 14 1[35 3[14 33[{}83 41.666668
/Times-Roman rf /Fr 136[36 25 28 17 19 22 1[28 25 28
41 14 28 1[14 28 25 17 22 28 22 28 25 13[28 36 8[19 2[30
2[36 1[36 11[25 25 25 25 25 10[41 38[{}33 50.000000 /Times-Bold
rf /Fs 81[21 52[19 19 27 19 19 10 15 12 1[19 19 19 29
10 19 10 10 19 19 12 17 19 17 19 17 3[12 1[12 5[27 23
21 25 1[21 27 27 2[27 2[27 27 1[23 27 25 25 27 34 2[21
1[10 10 1[19 19 19 19 19 19 19 19 19 1[9 12 9 21 19 12
12 40[{}62 37.500000 /Times-Roman rf /Ft 139[13 18 15
2[23 23 1[13 23 2[23 1[15 20 1[20 1[20 13[25 2[25 5[18
8[33 65[{}16 45.643555 /Times-Roman rf /Fu 136[43 30
1[17 23 20 1[30 1[30 1[17 2[17 30 30 1[27 30 27 1[27
13[33 4[43 11[40 43 19[20 45[{}20 59.999973 /Times-Roman
rf end
%%EndProlog
%%BeginSetup
%%Feature: *Resolution 300dpi
TeXDict begin

%%EndSetup
%%Page: 1 1
1 0 bop 490 31 a Fu(New)15 b(Advances)f(in)g(Alpha-Beta)f(Searching)411
160 y Ft(Jonathan)d(Schaef)o(fer)535 b(Aske)10 b(Plaat)195
201 y Fs(Dept.)k(of)9 b(Computing)g(Science,)f(University)h(of)g
(Alberta,)50 b(Dept.)14 b(of)9 b(Computer)g(Science,)f(Erasmus)g
(University)n(,)349 243 y(615)h(General)f(Services)g(Building,)349
b(Room)9 b(H4-31,)g(P)l(.O.)h(Box)f(1738,)300 284 y(Edmonton,)f
(Alberta,)i(Canada)d(T6G)i(2H1)235 b(3000)8 b(DR)h(Rotterdam,)g(The)g
(Netherlands)401 326 y([e-mail])471 b([e-mail])n
(.mit)n(.edu)333 484 y Fr(Abstract)8 564 y Fq(Alpha-Beta)15
b(has)g(been)g(the)g(algorithm)f(of)h(choice)g(for)8
610 y(game-tree)f(search)h(for)e(over)g(three)g(decades.)26
b(Its)13 b(suc-)8 656 y(cess)f(is)e(lar)o(gely)g(attributable)e(to)i(a)
h(variety)f(of)g(enhance-)8 701 y(ments)h(to)g(the)g(basic)g(algorithm)
f(that)g(can)i(dramatically)8 747 y(improve)g(the)h(search)h(ef)o
(\256ciency)m(.)24 b(Although)10 b(state-of-)8 793 y(the-art)g
(game-playing)g(programs)h(build)e(trees)i(that)f(are)8
838 y(close)19 b(in)g(size)g(to)g(the)g(minimal)f(Alpha-Beta)g(search)8
884 y(tree,)f(this)c(paper)i(shows)g(that)f(there)h(is)f(still)g(room)g
(for)8 930 y(improvement.)27 b(Three)15 b(new)f(enhancements)i(are)f
(pre-)8 975 y(sented:)j(best-\256rst)11 b(Alpha-Beta)h(search,)i
(better)d(use)i(of)8 1021 y(transpositions,)6 b(and)h(improving)t
(aspiration)f(search)i(un-)8 1067 y(der)h(real-time)f(constraints.)14
b(Measurements)c(show)e(that)8 1112 y(these)18 b(improvements)f(can)h
(reduce)g(search)g(ef)o(fort)f(by)8 1158 y(35\045.)-33
1248 y Fp(Keywords:)f Fq(Alpha-Beta,)10 b(best-\256rst)g(search,)i
(SSS*,)g(heuristic)-75 1294 y(search,)g(computer)e(chess.)-75
1401 y Fr(1)50 b(Intr)o(oduction)-75 1470 y Fq(The)14
b(Alpha-Beta)e(search)i(algorithm)e(is)h(at)g(the)g(heart)g(of)f(the)h
(pro-)-75 1515 y(gramming)8 b(strategy)f(for)h(many)g(games.)16
b(Although)6 b(this)h(simplistic)-75 1561 y(depth-\256rst,)13
b(brute-force)g(approach)g(has)h(not)e(found)g(favor)h(in)g(the)-75
1607 y(arti\256cial)f(intelligence)e(community)m(,)j(it)e(is)h(hard)g
(to)g(ar)o(gue)g(with)f(its)-75 1652 y(success.)16 b(Programs)8
b(such)g(as)g(Deep)h(Thought)d(in)i(chess)g(\(playing)f(at)-75
1698 y(Grandmaster)13 b(strength)e([10)o(]\),)i(Chinook)d(at)i
(checkers)i(\(the)e(Man-)-75 1744 y(Machine)k(W)m(orld)f(Champion)g
([27)o(]\))h(and)f(Logistello)g(in)g(Othello)-75 1789
y(\(much)9 b(stronger)f(than)g(all)h(humans)g([4)o(]\))g(have)g
(achieved)h(spectacu-)-75 1835 y(lar)g(success)i(with)d(this)g
(algorithm.)14 b(Alternative)9 b(search)j(strategies)-75
1881 y(are)e(promising)e(in)h(theory)f(but)h(the)g(results)f(have)i
(yet)f(to)g(be)h(demon-)-75 1926 y(strated)d(in)g(practice)h(\(for)f
(example,)i(BPIP)e([1],)h(B*)f([2],)h(Conspiracy)-75
1972 y(Numbers)j([16)o(]\).)-33 2020 y(Three)g(decades)g(of)f(research)
i(into)d(Alpha-Beta)h(has)g(resulted)g(in)-75 2065 y(a)h(lar)o(ge)f
(number)h(of)f(enhancements)h(to)f(the)g(algorithm)f(including:)-44
2132 y(1.)21 b Fo(T)n(ranspositions)p Fq(.)d(Usually)12
b(the)f(search)j(space)f(is)f(referred)g(to)8 2177 y(as)18
b(a)g(tree.)37 b(However)n(,)21 b(it)16 b(is)i(actually)f(a)h(directed)
f(acyclic)8 2223 y(graph.)38 b(Recognizing)18 b(previously)e(visited)h
(nodes)h(allows)8 2269 y(one)e(to)f(eliminate)h(potentially)d(lar)o(ge)
j(portions)e(of)i(the)f(tree)8 2314 y(traversed)c(by)g(Alpha-Beta.)16
b(T)o(ransposition)9 b(tables)i(are)g(used)8 2360 y(to)c(save)i
(information)c(about)i(visited)g(nodes,)h(in)f(the)h(event)f(that)8
2406 y(these)k(nodes)f(are)h(revisited)e([25].)1056 484
y(2.)21 b Fo(Move)14 b(or)n(dering)p Fq(.)28 b(The)15
b(ef)o(fectiveness)g(of)g(Alpha-Beta)e(cut-)1108 529
y(of)o(fs)d(is)g(maximized)h(if)f(the)g(best)g(move)h(is)f(considered)g
(\256rst)g(at)1108 575 y(all)f(interior)f(nodes)i(of)f(the)g(search)i
(tree.)16 b(Hence)11 b(research)g(has)1108 621 y(concentrated)g(on)f
(static)h(\(knowledge-based\))f(and)h(dynamic)1108 666
y(\(information)j(extracted)j(from)g(the)g(search)g(tree\))g(schemes)
1108 712 y(for)8 b(ordering)f(moves)i(in)f(a)h(best-to-worst)d(order)n
(.)15 b(T)m(echniques)1108 758 y(such)7 b(as)g(iterative)g(deepening)g
(and)g(t)o(he)g(hi)o(story)f(heuri)o(stic)h(h)o(ave)1108
803 y(shown)k(that)h(it)f(is)h(possible)g(to)f(achieve)j(excellent)e
(move)g(or)o(-)1108 849 y(dering)d([25)o(].)1056 916
y(3.)21 b Fo(Minimal)12 b(windows)p Fq(.)27 b(Alpha-Beta)14
b(searches)j(with)c(a)i(lower)1108 962 y(bound)7 b(\()p
Fn(a)s Fq(\))g(and)h(an)g(upper)g(bound)f(\()p Fn(b)s
Fq(\))h(on)f(the)h(range)h(of)f(useful)1108 1008 y(search)j(values,)g
(the)f(so-called)g(search)i(window)m(.)i(Narrowing)1108
1053 y(this)7 b(window)h(can)i(increase)f(the)g(likelihood)d(of)j(a)g
(cutof)o(f)f([25].)1108 1099 y(The)f(narrowest,)i(or)d(minimal,)i
(window)e(occurs)i(when)f Fn(a)e Fq(+)s(1)12 b(=)1108
1145 y Fn(b)h Fq(\(for)c(integer)o(-valued)h(leaf)g(nodes\).)1056
1212 y(4.)21 b Fo(V)-5 b(ariable)11 b(sear)n(ch)h(depth)p
Fq(.)18 b(All)11 b(moves)g(are)h(not)f(equal.)18 b(Some)1108
1258 y(moves)g(are)g(weak)h(and)f(should)e(be)i(allocated)g(few)g
(search)1108 1303 y(resources.)48 b(Other)21 b(moves)g(have)h
(potential)d(and)i(should)1108 1349 y(be)16 b(explored)g(further)n(.)33
b(Instead)17 b(of)f(a)h(\256xed-depth)f(search,)1108
1395 y(many)d(game-playing)g(programs)g(reduce)h(the)f(search)i(depth)
1108 1440 y(for)9 b(weak)i(moves)g(and)f(increase)i(it)d(for)h(strong)f
(moves.)1066 1508 y(The)h(ef)o(fects)h(of)e(points)g(1\2613)g(can)h(be)
g(easily)g(quanti\256ed.)k(All)9 b(one)1025 1553 y(has)k(to)g(do)g(is)h
(build)d(\256xed-depth)i(search)i(trees)f(with/witho)o(ut)c(the)1025
1599 y(enhancement)16 b(and)g(compare)h(the)e(tree)h(size.)32
b(Unfortunately)m(,)16 b(it)1025 1645 y(is)c(dif)o(\256cult)g(to)g
(quantify)g(the)h(ef)o(fects)h(of)e(variable)h(search)h(depths.)1025
1690 y(Here)d(not)e(only)g(the)h(size)h(of)f(the)g(search)i(tree)e
(must)g(be)h(considered,)1025 1736 y(but)d(also)i(the)g(quality)e(of)h
(the)g(answer)i(provided.)j(W)m(e)c(do)f(not)g(know)1025
1782 y(of)g(any)i(fair)f(way)g(of)g(doing)f(this)h(comparison.)1066
1830 y(In)20 b(this)f(paper)i(we)g(consider)f(three)g(new)h
(enhancements)h(to)1025 1876 y(the)16 b(Alpha-Beta)h(algorithm.)33
b(The)18 b(\256rst)f(one)f(concerns)i(aspira-)1025 1921
y(tion)11 b(searching.)25 b(An)13 b(Alpha-Beta)f(search)j(can)f(be)f
(called)g(with)g(a)1025 1967 y(lower)e(bound)g(of)h Fm(\000)p
Fl(\245)g Fq(and)g(an)g(upper)g(bound)f(of)h(+)p Fl(\245)p
Fq(.)20 b(Experience)1025 2013 y(shows)13 b(that)g(narrowing)g(this)f
(window)h(can)h(signi\256cantly)e(reduce)1025 2058 y(the)f(search)i(ef)
o(fort.)19 b(Aspiration)11 b(search)h(makes)h(the)f(initial)e(call)i
(to)1025 2104 y(Alpha-Beta)d(with)g(a)h(small)g(search)h(window)e
(centered)i(around)e(the)1025 2150 y(expected)j(value.)19
b(No)11 b(problems)g(occur)h(if)f(the)g(search)i(value)f(falls)1025
2195 y(in)7 b(the)h(window)f(\(has)i(an)f(accurate)i(value\))e(or)g
(exceeds)h(the)f(window)1025 2241 y(\(fail)k(high\320a)f(better)i
(value)g(than)f(expected\).)24 b(The)14 b(problem)e(oc-)1025
2287 y(curs)f(when)h(the)f(value)h(of)f(the)h(\256rst)f(move)h(is)f
(less)h(than)g(the)f(search)1025 2332 y(window)e(\(fail)g(low\).)1066
2380 y(In)h(the)h(fail)f(low)g(scenario,)i(our)e(search)i(value)f
(expectations)f(are)1025 2426 y(seriously)h(wrong.)21
b(The)14 b(usual)e(resolution)e(of)j(this)e(problem)h(is)h(to)1025
2472 y(re-search)i(the)f(move)h(with)e(the)h(correct)g(search)i(window)
d(to)g(\256nd)1025 2517 y(its)j(true)g(value,)j(and)f(then)e(continue)g
(to)h(examine)g(other)g(moves)1025 2563 y(looking)10
b(for)i(an)g(improvement.)21 b(In)12 b(the)g(critical)g(period)g(until)
e(the)1025 2609 y(program)j(\256nds)h(the)g(right)e(move,)k(it)d(may)h
(not)f(be)i(able)f(to)f(play)h(a)1025 2654 y(reasonable)7
b(move)h(if)f(forced)g(to)g(move)h(because)h(of)e(\(time\))f(resource)
1025 2700 y(constraints.)20 b(Instead,)14 b(on)e(a)h(fail)f(low)g(we)h
(propose)f(to)g(restart)g(the)p eop
%%Page: 2 2
2 1 bop -75 42 a Fq(search)14 b(and)g(use)f(the)g(transposition)e
(table)i(values)h(to)e(seed)j(a)e(new)-75 87 y(iterative-deepening)7
b(search.)16 b(In)9 b(this)e(way)m(,)j(the)f(new)g(best)g(move)g(is)-75
133 y(quickly)g(found.)15 b(Experiments)10 b(in)g(chess)i(show)e(that)g
(this)f(not)h(only)-75 178 y(\256nds)g(an)h(alternative)f(best)h(move)g
(quickly)m(,)f(but)g(also)g(does)h(so)g(with)-75 224
y(less)g(search)g(ef)o(fort.)-33 276 y(The)i(second)h(enhancement)g
(takes)g(the)f(idea)g(of)g(minimal)f(win-)-75 322 y(dows)e(to)g(the)g
(extreme:)15 b(all)10 b(searches)i(are)f(performed)f(with)f(a)i(min-)
-75 368 y(imal)f(window)m(.)15 b(The)c(result)f(of)g(the)g(search)h(is)
g(a)g(bound)e(on)h(the)g(true)-75 413 y(value.)27 b(A)15
b(series)f(of)g(searches)i(allows)e(one)g(to)g(conver)o(ge)h(on)f(the)
-75 459 y(minimax)c(value.)16 b(One)10 b(way)h(of)f(using)f(this)h(is)g
(to)f(start)h(with)g(an)g(up-)-75 505 y(per)f(bound)f(of)h(+)p
Fl(\245)h Fq(and)f(search)h(to)f(successively)g(lower)g(that)g(bound)
-75 550 y(until)j(the)i(exact)h(value)f(is)g(found.)26
b(Surprisingly)m(,)13 b(this)g(algorithm)-75 596 y(expands)8
b(the)f(same)i(leaf)e(nodes)h(in)f(the)g(same)i(order)e(as)h(the)f
(best-\256rst)-75 641 y(algorithm)k(SSS*)i([28)o(].)22
b(In)12 b(ef)o(fect,)j(SSS*)d(is)h(now)f(a)h(special)g(case)-75
687 y(of)d(depth-\256rst)f(Alpha-Beta.)-33 739 y(Instead)j(of)f
(starting)g(at)h(+)p Fl(\245)h Fq(and)f(lowering)f(the)g(bound)g
(\(SSS*\),)-75 785 y(or)i(starting)f(at)h Fm(\000)p Fl(\245)g
Fq(and)g(raising)g(the)g(bound)f(\(DUAL*)h([15)o(]\),)h(we)-75
831 y(can)f(start)g(with)f(an)h(approximation)e(of)h(the)h(bound)e(and)
i(conver)o(ge)-75 876 y(from)c(there.)16 b(Using)8 b(the)i(score)g
(from)g(the)f(previous)g(iteration)f(of)h(an)-75 922
y(iterative-deepening)d(search)i(yields)f(the)g(new)h(MTD\()p
Fl(\246)p Fq(\))f(algorithm.)-75 968 y(For)17 b(chess,)k(experimental)d
(results)f(show)h(this)f(to)g(be)h(a)g(9\26116\045)-75
1013 y(improvement)f(over)g(the)g(algorithm)e(of)i(choice)h(by)f(most)g
(chess)-75 1059 y(programmers)7 b(\(aspiration)f(window)g(enhanced)i
(NegaScout)f([22)o(]\).)-33 1111 y(The)12 b(third)d(enhancement)k
(improves)e(the)g(bene\256t)h(of)f(transposi-)-75 1157
y(tions.)i(For)8 b(each)h(node,)f(a)h(transposition)c(table)j
(typically)e(stores)i(the)-75 1202 y(depth)13 b(to)g(which)h(that)f
(node)g(was)i(searched,)h(the)e(score)g(achieved)-75
1248 y(and)e(the)h(best)f(move.)22 b(When)12 b(a)h(node)f(is)h(visited)
e(in)h(the)g(search,)i(if)-75 1294 y(the)d(table)h(entry')n(s)e(value)i
(does)g(not)e(cause)j(a)f(cutof)o(f,)g(then)f(the)h(best)-75
1339 y(move)e(saved)g(in)f(that)g(entry)g(is)g(searched)i(\256rst)e
(before)h(other)f(moves)-75 1385 y(are)14 b(considered.)23
b(However)n(,)15 b(what)e(if)g(another)f(move)i(transposes)-75
1431 y(into)7 b(a)i(previously)e(searched)j(part)e(of)g(the)h(tree)g