tr9417.ps

介绍各种经典算法的代码。说明详细

/Edieresis/Egrave/Iacute/Icircumflex/Idieresis/Igrave/Oacute/Ocircumflex
/apple/Ograve/Uacute/Ucircumflex/Ugrave/dotlessi/circumflex/tilde
/macron/breve/dotaccent/ring/cedilla/hungarumlaut/ogonek/caron
CVvec 128 128 getinterval astore pop
end
CanvasDict begin
0 setlinecap
0 setlinejoin
4 setmiterlimit
/currot 0 def
origmtx currentmatrix pop
[] 0 setdash
1 1 setpen
1 fg
0 pg
0 frg
1 bkg
newpath
/dbg F def
% ---- Object #1:5 Obj Type: 99
% ---- Object #2:6 Obj Type: 2
save
0 setgray
mark /|___Times-Bold /Times-Bold T cvRecFont
14 fts /|___Times-Bold findfont exch scalefont setfont
0 setgray
125 360 moveto
(DEPARTMENT OF COMPUTING SCIENCE)
F F 280.3589 3 31 0 0 fittext
restore
% ---- Object #3:7 Obj Type: 2
save
0 setgray
mark /|___Times-Bold /Times-Bold T cvRecFont
12 fts /|___Times-Bold findfont exch scalefont setfont
0 setgray
197 344 moveto
(The University of Alberta)
F F 131.6221 3 25 0 0 fittext
restore
% ---- Object #4:8 Obj Type: 2
save
0 setgray
mark /|___Times-Bold /Times-Bold T cvRecFont
12 fts /|___Times-Bold findfont exch scalefont setfont
0 setgray
194 328 moveto
(Edmonton, Alberta, Canada)
F F 145.3213 2 25 0 0 fittext
restore
origmtx setmatrix
systemdict /setpacking known {origpack setpacking} if end

%%EndDocument

 endTexFig
 eop
%%Page: 1 2
1 1 bop 1817 5841 a FF(i)p eop
%%Page: 2 3
2 2 bop 1332 763 a FD(SSS*)35 b(=)h FH(a)9 b FD(-)p FH(b)46
b FD(+)35 b(TT)773 1016 y FC(Ask)o(e)25 b(Plaat,)g(Erasmus)f(Uni)n(v)o
(ersity)-6 b(,)47 b FB([e-mail])o(s)-7 b(.mit)c(.edu)461
1132 y FC(Jonathan)24 b(Schaef)n(fer)l(,)i(Uni)n(v)o(ersity)d(of)i
(Alberta,)49 b FB([e-mail])758 1248 y
FC(W)l(im)24 b(Pijls,)g(Erasmus)g(Uni)n(v)o(ersity)-6
b(,)47 b FB([e-mail])o(w)-7 b(.eur)c(.nl)735 1364
y FC(Arie)25 b(de)g(Bruin,)g(Erasmus)f(Uni)n(v)o(ersity)-6
b(,)47 b FB([e-mail])o(w)-7 b(.eur)c(.nl)858 1685 y
FA(Erasmus)19 b(Uni)n(v)o(ersity)-5 b(,)554 b(Uni)n(v)o(ersity)19
b(of)h(Alberta,)625 1784 y(Department)f(of)h(Computer)e(Science,)99
b(Department)19 b(of)h(Computing)e(Science,)940 1884
y(P)-9 b(.O.)20 b(Box)g(1738,)479 b(615)19 b(General)h(Services)g
(Building,)845 1984 y(3000)f(DR)i(Rotterdam,)577 b(Edmonton,)18
b(Alberta,)917 2083 y(The)i(Netherlands)684 b(Canada)20
b(T6G)g(2H1)1676 2414 y Fy(Abstract)622 2572 y FA(In)d(1979)g(Stockman)
f(introduced)g(the)i(SSS*)g(minimax)f(search)g(algorithm)f(that)i
(domi-)497 2671 y(nates)i(Alpha-Beta)f(in)g(the)h(number)d(of)j(leaf)f
(nodes)g(e)o(xpanded.)26 b(Further)19 b(in)m(v)o(estigation)e(of)497
2771 y(the)g(algorithm)e(sho)n(wed)h(that)h(it)g(had)f(three)g(serious)
h(dra)o(wbacks,)e(which)h(pre)n(v)o(ented)e(its)k(use)497
2870 y(by)24 b(practitioners:)35 b(it)24 b(is)h(dif)n(\256cult)e(to)g
(understand,)g(it)h(has)g(lar)o(ge)f(memory)f(requirements,)497
2970 y(and)g(it)h(is)g(slo)n(w)-5 b(.)34 b(This)22 b(paper)f(presents)h
(an)g(alternate)g(formulation)d(of)j(SSS*,)h(in)f(which)g(it)497
3070 y(is)d(implemented)e(as)i(a)f(series)h(of)f(Alpha-Beta)g(calls)h
(that)f(use)g(a)h(transposition)e(table)h(\(AB-)497 3169
y(SSS*\).)29 b(The)19 b(reformulation)d(solv)o(es)i(all)i(three)e
(percei)n(v)o(ed)f(dra)o(wbacks)g(of)h(SSS*,)i(making)497
3269 y(it)g(a)f(practical)f(algorithm.)27 b(Further)m(,)18
b(because)g(the)h(search)f(is)i(no)n(w)e(based)h(on)f(Alpha-Beta,)497
3369 y(the)i(e)o(xtensi)n(v)o(e)e(research)g(on)h(minimax)f(search)h
(enhancements)f(can)h(be)g(easily)h(inte)o(grated)497
3468 y(into)g(AB-SSS*.)622 3568 y(T)-7 b(o)26 b(test)g(AB-SSS*)g(in)g
(practise,)h(it)f(has)g(been)f(implemented)f(in)i(three)f
(state-of-the-)497 3667 y(art)36 b(programs:)59 b(for)36
b(check)o(ers,)i(Othello)e(and)f(chess.)77 b(AB-SSS*)37
b(is)f(comparable)e(in)497 3767 y(performance)25 b(to)j(Alpha-Beta)e
(on)i(leaf)f(node)g(count)f(in)i(all)g(three)f(games,)h(making)f(it)h
(a)497 3867 y(viable)j(alternati)n(v)o(e)e(to)j(Alpha-Beta)e(in)h
(practise.)62 b(Whereas)31 b(SSS*)g(has)h(usually)e(been)497
3966 y(re)o(garded)j(as)k(being)e(entirely)g(dif)n(ferent)f(from)g
(Alpha-Beta,)39 b(it)d(turns)g(out)f(to)h(be)g(just)497
4066 y(an)26 b(Alpha-Beta)f(enhancement,)f(lik)o(e)i(null-windo)n(w)d
(searching.)44 b(This)26 b(runs)f(counter)f(to)497 4166
y(published)32 b(simulation)g(results.)68 b(Our)33 b(research)f(leads)h
(to)g(the)g(surprising)f(result)h(that)497 4265 y(iterati)n(v)o(e)f
(deepening)e(v)o(ersions)h(of)g(Alpha-Beta)h(can)g(e)o(xpand)e(fe)n
(wer)h(leaf)h(nodes)g(than)497 4365 y(iterati)n(v)o(e)20
b(deepening)e(v)o(ersions)h(of)h(SSS*)h(due)e(to)i(dynamic)d(mo)o(v)o
(e)h(re-ordering.)1805 5841 y FF(ii)p eop
%%Page: 3 4
3 3 bop 270 399 a Fx(Contents)270 602 y(1)68 b(Intr)n(oduction)2470
b(1)270 806 y(2)68 b(SSS*)2764 b(2)270 1010 y(3)68 b(Ref)n(ormulating)
24 b(SSS*)2173 b(5)270 1214 y(4)68 b(Example)2619 b(8)270
1418 y(5)68 b(AB-SSS*)21 b(Storage)k(Issues)1988 b(11)406
1531 y FF(5.1)96 b(Storage)25 b(Or)n(ganization)33 b
Fw(.)45 b(.)h(.)f(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h
(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)h(.)f(.)138 b FF(11)406
1643 y(5.2)96 b(Storage)25 b(Needs)78 b Fw(.)45 b(.)g(.)g(.)g(.)h(.)f
(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)
h(.)f(.)g(.)g(.)h(.)f(.)138 b FF(12)270 1847 y Fx(6)68
b(Dominance)2477 b(13)270 2051 y(7)68 b(Experiments)2422
b(15)406 2164 y FF(7.1)96 b(Storage)25 b(Requirements)66
b Fw(.)46 b(.)f(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f
(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)h(.)f(.)138 b FF(16)406
2277 y(7.2)96 b(T)m(ree)24 b(Size)63 b Fw(.)45 b(.)g(.)h(.)f(.)g(.)g(.)
g(.)h(.)f(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g
(.)g(.)g(.)h(.)f(.)g(.)g(.)h(.)f(.)138 b FF(20)406 2390
y(7.3)96 b(Ex)o(ecution)25 b(T)m(ime)h Fw(.)45 b(.)g(.)g(.)g(.)h(.)f(.)
g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h
(.)f(.)g(.)g(.)h(.)f(.)138 b FF(20)270 2594 y Fx(8)68
b(Addr)n(essing)24 b(the)f(Misconceptions)i(of)e(SSS*)1391
b(21)406 2707 y FF(8.1)96 b(Algorithm)25 b(Clarity)84
b Fw(.)45 b(.)g(.)h(.)f(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g
(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)h(.)f(.)138 b
FF(21)406 2819 y(8.2)96 b(Storage)25 b(Requirements)66
b Fw(.)46 b(.)f(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f
(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)h(.)f(.)138 b FF(21)406
2932 y(8.3)96 b(Ex)o(ecution)25 b(Ov)o(erhead)63 b Fw(.)45
b(.)h(.)f(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g
(.)g(.)g(.)h(.)f(.)g(.)g(.)h(.)f(.)138 b FF(22)406 3045
y(8.4)96 b(Domination)40 b Fw(.)45 b(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)
g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f
(.)g(.)g(.)h(.)f(.)138 b FF(22)406 3158 y(8.5)96 b(T)m(ree)24
b(Size)63 b Fw(.)45 b(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)h(.)f
(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)
h(.)f(.)138 b FF(22)406 3271 y(8.6)96 b(Other)24 b(Considerations)32
b Fw(.)45 b(.)h(.)f(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)h
(.)f(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)h(.)f(.)138 b FF(22)270
3475 y Fx(9)68 b(The)22 b(Case)i(Against)g(Simulations)1752
b(23)270 3679 y(10)23 b(Conclusions)h(and)e(Futur)n(e)h(W)-7
b(ork)1745 b(25)270 3883 y(A)47 b(A)n(ppendix:)32 b(Pr)n(oof)24
b(of)g(Equi)o(v)o(alence)1667 b(25)1792 5841 y FF(iii)p
eop
%%Page: 1 5
1 4 bop 270 399 a Fx(1)91 b(Intr)n(oduction)270 532 y
FF(The)28 b(Alpha-Beta)h(tree-searching)j(algorithm)e(has)e(been)h(in)f
(use)g(since)h(the)f(1960')-5 b(s.)49 b(No)27 b(other)270
645 y(minimax)h(search)i(algorithm)f(has)f(achie)n(v)o(ed)i(the)e
(wide-spread)j(use)d(in)g(practical)i(applications)270
758 y(that)d(Alpha-Beta)h(has.)43 b(Thirty)28 b(years)f(of)g(research)h
(has)g(found)g(w)o(ays)e(of)h(impro)o(ving)h(the)f(algo-)270
871 y(rithm')-5 b(s)24 b(ef)n(\256cienc)o(y)-6 b(,)24
b(and)g(v)n(ariants)h(such)f(as)f(Ne)o(gaScout)g([23)q(])g(and)h(PVS)d
([4])i(are)g(quite)i(popular)-5 b(.)270 984 y(Consequently)f(,)33
b(interesting)f(alternati)n(v)o(es)g(for)d(\256x)o(ed-depth)i
(searching,)h(such)e(as)f(breadth-\256rst)270 1096 y(and)24
b(best-\256rst)h(strate)o(gies,)g(ha)n(v)o(e)g(been)f(lar)n(gely)h
(ignored.)411 1209 y(In)32 b(1979)i(Stockman)f(introduced)i(SSS*,)e(a)f
(radically)i(dif)n(ferent)h(approach)f(from)f(Alpha-)270
1322 y(Beta)19 b(for)g(searching)j(\256x)o(ed-depth)f(minimax)e(trees)h
([30)q(].)32 b(It)18 b(b)n(uilds)j(a)e(tree)g(in)g(a)g(best-\256rst)h
(f)o(ashion)270 1435 y(by)25 b(visiting)i(the)f(nodes)g(in)f(the)h
(order)g(of)f(most)g(to)h(least)g(promising.)40 b(Alpha-Beta,)26
b(in)f(contrast,)270 1548 y(uses)36 b(a)f(depth-\256rst,)40
b(left-to-right)f(tra)n(v)o(ersal)e(of)f(the)f(tree.)70
b(Intuiti)n(v)o(ely)-6 b(,)40 b(it)35 b(w)o(ould)h(seem)g(that)270
1661 y(a)c(best-\256rst)i(strate)o(gy)f(should)h(pre)n(v)n(ail)g(o)o(v)
o(er)e(a)g(rigidly)i(ordered)g(depth-\256rst)g(one.)60
b(Stockman)270 1774 y(pro)o(v)o(ed)37 b(that)h(SSS*)c(dominated)39
b(Alpha-Beta;)45 b(it)36 b(w)o(ould)h(ne)n(v)o(er)g(e)n(v)n(aluate)h
(more)f(leaf)g(nodes)270 1887 y(than)d(w)o(ould)f(Alpha-Beta.)62
b(When)33 b(both)h(algorithms)h(are)e(gi)n(v)o(en)g(a)g(perfectly)i
(ordered)g(game)270 2000 y(tree)26 b(to)f(search,)i(the)o(y)f(visit)h
(the)e(same)h(lea)n(v)o(es,)h(b)n(ut)f(on)f(a)n(v)o(erage)i(SSS*)d(e)n
(v)n(aluates)j(considerably)270 2113 y(fe)n(wer)22 b(leaf)g(nodes.)34
b(This)21 b(has)h(been)h(repeatedly)h(demonstrated)h(in)d(the)g
(literature)i(by)d(numerous)270 2226 y(simulations)26
b(\(for)f(e)o(xample,)f([10)q(,)f(15)q(,)f(16)q(,)h(25)q(,)g(24)q(,)f
(26)q(]\).)34 b(Why)-6 b(,)23 b(then,)i(has)f(the)g(algorithm)h(been)
270 2338 y(shunned?)411 2451 y(SSS*,)16 b(as)f(formulated)g(by)g
(Stockman,)22 b(has)15 b(se)n(v)o(eral)g(problems.)36
b(First,)17 b(it)e(tak)o(es)g(considerabl)q(e)270 2564
y(ef)n(fort)25 b(to)f(understand)i(ho)n(w)e(the)g(algorithm)i(w)o
(orks,)e(and)g(still)h(more)f(to)f(understand)k(its)d(relation)270
2677 y(to)35 b(Alpha-Beta.)71 b(Second,)39 b(SSS*)34
b(maintains)j(a)e(data)h(structure)i(kno)n(wn)e(as)f(the)h(OPEN)d
(list,)270 2790 y(similar)g(to)g(that)g(found)h(in)e(other)i
(best-\256rst)g(search)f(algorithms)i(lik)o(e)e(A*)f([17)q(].)60
b(The)32 b(size)h(of)270 2903 y(this)26 b(list)g(is)f(e)o(xponential)k
(with)c(the)h(depth)g(of)g(the)f(search)i(tree.)40 b(This)25
b(has)h(led)g(man)o(y)f(authors)i(to)270 3016 y(conclude)f(that)e(this)
f(ef)n(fecti)n(v)o(ely)j(disquali\256es)f(SSS*)d(from)h(being)i(useful)
f(for)g(real)g(applications)270 3129 y(lik)o(e)h(game-playing)i
(programs)f([10)r(,)d(16)q(,)h(26].)36 b(Third,)25 b(the)g(OPEN)d(list)
j(must)f(be)h(k)o(ept)g(in)g(sorted)270 3242 y(order)-5
b(.)33 b(Insert)22 b(and)g(\(in)e(particular\))k(delete/pur)n(ge)h
(operations)e(on)e(the)g(OPEN)d(list)k(can)f(dominate)270
3355 y(the)34 b(e)o(x)o(ecution)i(time)e(of)h(an)o(y)f(program)h(using)
g(SSS*.)64 b(Despite)35 b(the)f(promise)i(of)e(e)o(xpanding)270
3468 y(fe)n(wer)21 b(nodes,)i(the)f(disadv)n(antages)j(of)c(SSS*)f(ha)n
(v)o(e)i(pro)o(v)o(en)g(a)f(signi\256cant)j(deterrent)f(in)f(practice.)
270 3580 y(The)h(general)i(vie)n(w)f(of)f(SSS*)f(then)i(is)f(that:)384
3763 y(1.)45 b(it)24 b(is)f(a)g(comple)o(x)h(algorithm)i(that)e(is)f
(dif)n(\256cult)i(to)e(understand,)384 3949 y(2.)45 b(it)29
b(has)h(lar)n(ge)h(memory)f(requirements)i(that)e(mak)o(e)g(the)f
(algorithm)i(impractical)h(for)e(real)497 4062 y(applications,)384
4248 y(3.)45 b(it)24 b(is)f(\252slo)n(w\272)h(because)h(of)f(the)g(o)o
(v)o(erhead)h(of)e(maintaining)j(the)e(sorted)h(OPEN)c(list,)384
4433 y(4.)45 b(it)23 b(has)g(been)h(pro)o(v)o(en)g(to)f(dominate)h
(Alpha-Beta)h(in)d(terms)i(of)e(the)i(number)g(of)e(leaf)i(nodes)497
4546 y(e)n(v)n(aluated,)i(and)384 4732 y(5.)45 b(it)24
b(has)h(been)g(sho)n(wn)f(by)h(simualtions)h(that)f(it)f(e)n(v)n
(aluates)i(signi\256cantly)h(fe)n(wer)d(leaf)h(nodes)497
4845 y(than)g(Alpha-Beta.)270 5028 y(Whereas)k(the)e(last)h(point)h(w)o
(as)e(the)g(main)h(reason)g(why)f(SSS*)f(attracted)j(e)o(xtensi)n(v)o
(e)g(theoretical)270 5141 y(and)23 b(e)o(xperimental)i(attention)g(in)d
(the)h(literature,)i(the)e(\256rst)f(three)h(points)h(were)f(major)g
(deterrents)270 5254 y(for)h(practitioners.)411 5367
y(This)e(report)h(presents)h(ne)n(w)d(results)j(to)d(sho)n(w)h(that)h
(the)f(obstacles)i(to)e(ef)n(\256cient)g(SSS*)f(imple-)270
5479 y(mentations)15 b(ha)n(v)o(e)g(been)g(solv)o(ed)q(,)22
b(making)15 b(the)g(algorithm)g(a)g(practical)g(al)q(ter)q(nat)q(i)n(v)
o(e)g(to)g(Alph)q(a-Bet)q(a)270 5592 y(v)n(ariants.)33
b(By)17 b(reformulating)k(the)e(algorithm,)h(SSS*)c(can)j(be)f(e)o
(xpressed)i(simply)e(and)h(intuiti)n(v)o(ely)1807 5841
y(1)p eop
%%Page: 2 6
2 5 bop 270 399 a FF(as)19 b(a)g(series)h(of)g(calls)g(to)f
(Alpha-Beta,)i(yielding)h(a)c(ne)n(w)h(algorithm)i(called)g(AB-SSS*.)29
b(AB-SSS*)270 511 y(does)k(not)g(need)g(an)f(OPEN)e(list;)37
b(a)32 b(f)o(amiliar)h(transposition)k(table)c(performs)g(as)g(well.)59
b(In)32 b(ef-)270 624 y(fect,)24 b(SSS*)f(can)h(be)g(reformulated)j(to)
d(use)g(well-kno)n(wn)i(technology)-6 b(,)27 b(as)d(a)g(special)h(case)
g(of)f(the)270 737 y(Alpha-Beta)h(procedure)h(enhanced)g(with)d
(transposition)28 b(tables.)411 850 y(AB-SSS*)22 b(has)j(been)g
(implemented)h(in)e(high-performance)k(game-playing)f(programs)f(for)
270 963 y(check)o(ers,)j(Othello)e(and)f(chess.)42 b(The)26
b(simulation)i(results)f(that)g(predict)h(signi\256cantly)g(reduced)270
1076 y(leaf)h(node)g(e)n(v)n(aluations)j(do)c(not)h(sho)n(w)g(up)f
(when)h(\252real\272)h(game)e(trees)h(are)g(used.)49
b(Search)29 b(trees)270 1189 y(such)g(as)g(those)g(b)n(uilt)h(by)e
(chess,)j(check)o(ers)f(and)f(Othello)h(programs,)h(use)d(iterati)n(v)o
(e)i(deepening)270 1302 y(to)24 b(help)g(achie)n(v)o(e)h
Fv(nearly)g(optimal)g FF(mo)o(v)o(e)e(ordering.)37 b(The)23
b(high)h(quality)i(of)e(mo)o(v)o(e)f(ordering)j(and)270
1415 y(the)k(prese