hk.ps

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

rf /Fx 136[66 1[50 28 39 39 1[50 50 50 72 28 1[28 28
50 1[28 44 1[44 50 50 32[92 17[25 46[{}20 100.000000
/Times-Italic rf /Fy 134[50 2[50 50 28 39 33 2[50 50
78 28 50 28 28 50 1[33 44 50 44 50 44 9[94 1[72 1[55
2[55 5[39 4[61 2[66 72 20[25 44[{}29 100.000000 /Times-Roman
rf /Fz 1 4 df<147014F8A81470007815F0007C1401B4EC07F8D87F80EB0FF0D83FE0EB
3FE0D80FF0EB7F80D803F8EBFE003900FE73F890383F77E090380FFF80D903FEC7FCEB00
F8EB03FE90380FFF8090383F77E09038FE73F83903F870FED80FF0EB7F80D83FE0EB3FE0
D87F80EB0FF0D8FF00EB07F8007CEC01F000781400C7140014F8A81470252B7AAD32>3
D E /FA 138[72 40 56 48 2[72 72 112 40 2[40 72 72 1[64
72 64 1[64 13[80 2[80 1[104 7[80 4[104 22[72 42[{}21
144.000000 /Times-Roman rf end
%%EndProlog
%%BeginSetup
%%Feature: *Resolution 600dpi
TeXDict begin
%%PaperSize: a4

%%EndSetup
%%Page: 1 1
1 0 bop 392 739 a FA(An)35 b(Algorithm)f(F)n(aster)g(than)h(Ne)n(g)o
(aScout)f(and)h(SSS*)f(in)1599 922 y(Practice)2063 869
y Fz(\003)773 1162 y Fy(Ask)o(e)25 b(Plaat,)g(Erasmus)f(Uni)n(v)o
(ersity)-6 b(,)47 b Fx([e-mail])o(s)-7 b(.mit)c(.edu)461
1279 y Fy(Jonathan)24 b(Schaef)n(fer)l(,)i(Uni)n(v)o(ersity)d(of)i
(Alberta,)49 b Fx([e-mail])758 1395 y
Fy(W)l(im)24 b(Pijls,)g(Erasmus)g(Uni)n(v)o(ersity)-6
b(,)47 b Fx([e-mail])o(w)-7 b(.eur)c(.nl)735 1511
y Fy(Arie)25 b(de)g(Bruin,)g(Erasmus)f(Uni)n(v)o(ersity)-6
b(,)47 b Fx([e-mail])o(w)-7 b(.eur)c(.nl)950 1701 y
Fw(Erasmus)19 b(Uni)n(v)o(ersity)-5 b(,)511 b(Uni)n(v)o(ersity)19
b(of)g(Alberta,)741 1792 y(Department)g(of)g(Computer)g(Science,)100
b(Department)20 b(of)e(Computing)i(Science,)809 1884
y(Room)f(H4-31,)h(P)-8 b(.O.)17 b(Box)i(1738,)229 b(615)20
b(General)f(Services)g(Building,)939 1975 y(3000)h(DR)e(Rotterdam,)532
b(Edmonton,)19 b(Alberta,)1003 2066 y(The)g(Netherlands)629
b(Canada)20 b(T6G)e(2H1)1691 2360 y Fv(Abstract)650 2482
y Fw(In)31 b(this)g(paper)i(we)e(introduce)i(a)e(frame)n(w)o(ork)h(for)
g(best)g(\256rst)e(search)i(of)g(minimax)g(trees.)538
2574 y(Existing)17 b(best)i(\256rst)e(algorithms)h(lik)o(e)g(SSS*)f
(and)i(DU)m(AL*)e(are)h(formulated)h(as)f(instances)g(of)g(this)538
2665 y(frame)n(w)o(ork.)27 b(The)18 b(frame)n(w)o(ork)h(is)f(b)o(uilt)f
(around)i(the)g(Alpha-Beta)f(procedure.)28 b(Its)17 b(instances)i(are)
538 2756 y(highly)h(practical,)h(and)f(readily)h(implementable.)31
b(Our)20 b(reformulations)h(of)f(SSS*)f(and)i(DU)m(AL*)538
2847 y(solv)o(e)32 b(the)h(percei)n(v)o(ed)g(dra)o(wbacks)h(of)e(these)
h(algorithms.)67 b(W)-6 b(e)32 b(pro)o(v)o(e)h(their)f(suitability)g
(for)538 2939 y(practical)18 b(use)i(by)f(presenting)h(test)f(results)f
(with)h(a)g(tournament)h(le)n(v)o(el)f(chess)g(program.)650
3030 y(In)27 b(addition)h(to)g(reformulating)g(old)g(best)f(\256rst)g
(algorithms,)j(we)d(introduce)h(an)g(impro)o(v)o(ed)538
3121 y(instance)21 b(of)f(the)h(frame)n(w)o(ork:)31 b(MTD\()p
Fu(\246)p Fw(\).)h(This)20 b(ne)n(w)h(algorithm)g(outperforms)g(Ne)o
(gaScout,)g(the)538 3213 y(current)i(algorithm)h(of)g(choice)g(of)g
(most)f(chess)i(programs.)41 b(Again,)25 b(these)f(are)f(not)h
(simulation)538 3304 y(results,)18 b(b)o(ut)h(results)f(of)h(tests)g
(with)f(an)i(actual)f(chess)g(program,)h(Phoenix.)330
3582 y Ft(1)119 b(Intr)n(oduction)330 3767 y Fs(Ov)o(er)28
b(the)g(last)i(thirty)e(years)g(most)g(practitioners)f(ha)n(v)o(e)h
(used)h(depth-\256rst)e(search)h(algorithms)f(lik)o(e)330
3867 y(Alpha-Beta)i(in)h(their)f(game)g(playing)f(programs.)56
b(Since)29 b(the)h(introduction)d(of)i(Alpha-Beta,)i(nu-)330
3966 y(merous)c(enhancements)e(ha)n(v)o(e)i(been)g(introduced)e(to)j
(reduce)f(the)g(search)g(space)h(of)f(game)g(playing)330
4066 y(programs,)c(impro)o(ving)e(the)j(performance)d(tremendously)-5
b(.)37 b(Among)23 b(the)h(enhancements)d(are:)37 b(iter)n(-)330
4166 y(ati)n(v)o(e)28 b(deepening,)f(transposition)g(tables,)j(the)e
(history)f(heuristic,)i(and)e(minimal)h(search)f(windo)n(ws)330
4265 y(\(see)18 b(for)e(e)o(xample)g([28)o(])i(for)f(an)g
(assessment\).)28 b(Whereas)18 b(in)f(other)g(\256elds)h(best)g
(\256rst)g(approaches)d(ha)n(v)o(e)330 4365 y(been)26
b(successful,)h(in)f(minimax)f(search)h(these)h(ha)n(v)o(e)f(been)f
(lar)o(gely)g(ignored)g(by)g(practitioners,)i(the)330
4465 y(reason)17 b(being)g(the)h(good)e(results)j(of)e(enhanced)f
(depth)h(\256rst)i(searches,)f(and)f(the)h(reportedly)d(e)o(xcessi)n(v)
o(e)330 4564 y(memory)j(usage)i(of)g(best)h(\256rst)g(searches.)455
4664 y(In)j(this)i(paper)e(we)h(will)h(sho)n(w)e(that)h(best)h(\256rst)
f(search)g(can)g(be)f(implemented)f(using)i(a)g(minimal)330
4763 y(windo)n(w)35 b(depth)g(\256rst)i(search)e(procedure,)j(solving)d
(numerous)f(reported)g(problems,)k(creating)d(a)330 4863
y(number)17 b(of)i(practical)g(best)h(\256rst)g(algorithms.)27
b(In)19 b(particular)m(,)f(we)h(describe)g(the)g(follo)n(wing)f
(additions)330 4963 y(to)i(our)g(understanding)d(of)j(depth)f(\256rst)i
(and)f(best)g(\256rst)h(minimax)e(search:)462 5130 y
Fr(\267)42 b Fs(Null)34 b(windo)n(w)f(search,)k(with)d(a)h(form)e(of)h
(storage,)j(can)d(be)g(used)g(to)g(construct)f(best)i(\256rst)538
5230 y(minimax)16 b(algorithms.)27 b(F)o(or)17 b(storage)g(a)h(con)m(v)
o(entional)c(transposition)i(table)h(can)h(be)f(used.)28
b(The)538 5329 y(null)19 b(windo)n(w)f(calls)i(generate)e(a)h(sequence)
f(of)h(bounds)f(on)h(the)g(minimax)f(v)n(alue.)28 b(The)19
b(storage)538 5429 y(contains)28 b(the)i(part)f(of)h(the)f(search)g
(tree)h(that)g(establishes)g(these)f(bounds,)h(to)g(be)g(re\256ned)e
(in)538 5529 y(subsequent)18 b(passes.)p 330 5594 1200
4 v 414 5647 a Fq(\003)450 5670 y Fp(This)e(paper)i(is)f(submitted)i
(for)e(publication.)27 b(Some)17 b(of)g(these)h(results)g(were)g
(originally)i(published)f(in)e([22)q(].)1809 5919 y Fs(1)p
eop
%%Page: 2 2
2 1 bop 462 390 a Fr(\267)42 b Fs(A)23 b(frame)n(w)o(ork)d(is)k
(presented)d(for)h(algorithms)f(that)i(generate)e(such)h(sequences)g
(of)g(bounds)f(in)538 490 y(dif)n(ferent)j(w)o(ays.)48
b(Interestingly)-5 b(,)26 b(certain)f(instances)i(of)f(this)g(frame)n
(w)o(ork)f(e)o(xpand)f(the)i(same)538 589 y(leaf)14 b(nodes)g(in)g(the)
h(same)f(order)f(as)i(SSS*)g(and)f(DU)m(AL*.)27 b(These)14
b(algorithms,)g(called)g(AB-SSS*)538 689 y(and)21 b(AB-DU)m(AL*,)g(are)
g(much)g(simpler)g(than)g(the)h(original)e(formulations:)30
b(the)o(y)21 b(consist)h(of)f(a)538 789 y(single)f(loop)f(of)h
(Alpha-Beta)f(calls.)462 954 y Fr(\267)42 b Fs(T)-7 b(o)25
b(circumv)o(ent)d(the)j(problems)f(of)g(arti\256cally)h(generating)e
(realistic)i(trees,)h(we)f(ha)n(v)o(e)g(used)f(a)538
1054 y(real)j(chess)g(playing)f(program)f(for)i(our)f(tests.)51
b(Using)27 b(the)h(Alpha-Beta)e(based)h(frame)n(w)o(ork,)538
1153 y(both)33 b(depth)f(\256rst)j(and)e(best)h(\256rst)h(algorithms)e
(are)g(gi)n(v)o(en)g(the)h(same)g(storage,)i(in)e(contrast)538
1253 y(to)28 b(pre)n(vious)g(comparisons.)52 b(The)29
b(results)g(con\256rm)e(that)i(AB-SSS*)g(and)g(AB-DU)m(AL*)f(are)538
1353 y(practical)19 b(algorithms,)g(contradicting)f(pre)n(vious)g
(publications)h([8)o(,)i(12)o(,)f(26)o(].)462 1518 y
Fr(\267)42 b Fs(W)-7 b(e)26 b(ha)n(v)o(e)f(tested)g(instances)h(of)f
(the)g(frame)n(w)o(ork)e(against)i(the)g(depth)f(\256rst)i(algorithm)e
(imple-)538 1617 y(mented)k(in)h(our)f(chess)h(program,)g(i.e.)56
b(Informed)26 b(Ne)o(gaScout)h(with)j(aspiration)e(windo)n(ws,)538
1717 y(representing)16 b(the)j(current)e(choice)h(of)g(the)h(game)e
(programming)f(community)-5 b(.)26 b(One)18 b(instance,)538
1817 y(MTD\()p Fr(\246)p Fs(\),)f(outperforms)d(Ne)o(gaScout)i(on)h
(leaf)g(node)f(count,)h(total)g(node)f(count,)h(and)g(e)o(x)o(ecution)
538 1916 y(time,)23 b(by)f(a)h(wider)f(mar)o(gin)f(than)h(Ne)o
(gaScout')-5 b(s)22 b(gain)f(o)o(v)o(er)h(Alpha-Beta.)35
b(W)-7 b(e)24 b(pro)o(vide)d(some)538 2016 y(e)o(xperimental)d(e)n
(vidence)g(as)j(to)g(why)e(MTD\()p Fr(\246)p Fs(\))h(performs)e(so)j
(well.)462 2181 y Fr(\267)42 b Fs(Interestingly)-5 b(,)17
b(all)j(the)g(tested)g(algorithms)f(perform)e(relati)n(v)o(ely)i(close)
h(together)m(,)e(much)h(closer)538 2281 y(than)31 b(pre)n(vious)f
(simulation)h(results)i(ha)n(v)o(e)e(indicated.)63 b(W)-7
b(e)33 b(conclude)d(that,)35 b(a\))d(arti\256cially)538
2380 y(generated)23 b(game)h(trees)h(often)g(do)f(not)h(capture)f(all)i
(essential)f(aspects)h(of)f(real)g(trees,)h(and)f(b\))538
2480 y(often)k(more)g(gains)h(are)g(obtained)f(from)g(the)h(so-called)f
(Alpha-Beta)h(enhancements,)g(than)538 2580 y(from)19
b(better)h(algorithms.)330 2860 y Ft(2)119 b(Null)31
b(W)n(indo)o(w)g(Sear)n(ch)g(and)f(Memory)330 3062 y
Fo(2.1)99 b(Null)25 b(W)n(indo)o(w)g(Sear)n(ch)330 3217
y Fs(In)h(the)h(Alpha-Beta)e(procedure,)g(a)i(node)f(is)h(searched)e
(with)i(a)g(search)f(windo)n(w)f(of)h(a)h(certain)f(size.)330
3317 y(A)37 b(narro)n(w)f(search)g(windo)n(w)g Fn(h)p
Fm(a)p Fr(,)13 b Fm(b)p Fn(i)37 b Fs(causes)g(more)f(nodes)g(to)h(be)g
(cutof)n(f)e(than)i(a)g(wide)g(windo)n(w)330 3417 y Fn(h)p
Fm(c)p Fr(,)14 b Fm(d)r Fn(i)30 b Fs(\(where)e Fm(c)35
b(<)h(a)30 b Fs(and)e Fm(d)36 b(>)f(b)p Fs(\).)56 b(The)29
b(narro)n(west)g(windo)n(w)f(possible\320the)g(one)h(causing)g(the)330
3516 y(most)j(cutof)n(fs\320is)g(the)g(null)g(windo)n(w)-5
b(,)34 b(where)e Fl(a)45 b Fs(=)40 b Fl(b)32 b Fn(\000)24
b Fs(1)33 b(\(assuming)e(inte)o(ger)g(v)n(alued)g(lea)n(v)o(es\).)330
3616 y(Man)o(y)22 b(people)g(ha)n(v)o(e)g(noted)g(that)h(null-windo)n
(w)e(search)i(has)g(a)g(great)g(potential)f(for)g(ef)n(\256cient)h
(search)330 3716 y(algorithms)16 b([1,)h(3,)h(4)o(,)g(6,)g(14)o(,)g(27)
o(].)28 b(The)18 b(widely)f(used)g(Ne)o(gaScout)f(algorithm)g(deri)n(v)
o(es)h(its)h(superiority)330 3815 y(o)o(v)o(er)25 b(Alpha-Beta)h(from)g
(null-windo)n(w)e(search.)48 b(Because)27 b(it)g(has)g(the)f(potential)
g(of)g(creating)g(v)o(ery)330 3915 y(ef)n(\256cient)e(algorithms,)g(a)h
(number)e(of)h(algorithms)g(ha)n(v)o(e)g(been)g(proposed)e(that)j(are)f
(solely)h(based)f(on)330 4014 y(null)15 b(windo)n(w)f(search.)28
b(F)o(or)15 b(e)o(xample,)f(Coplan)h(presented)f(the)h(C*)h(algorithm)e
([4)o(,)i(30)o(],)g(and)f(Schaef)n(fer)330 4114 y(and)20
b(Fishb)n(urn)f(ha)n(v)o(e)h(e)o(xperimented)d(with)j(Alpha)g(Bounding)
e([6)o(,)j(27)o(].)455 4214 y(Knuth)28 b(and)i(Moore)e(ha)n(v)o(e)i
(sho)n(wn)f(that)g(the)h(return)f(v)n(alue)g Fm(g)h Fs(of)f(an)h
(Alpha-Beta)f(search)g(with)330 4313 y(windo)n(w)19 b
Fn(h)p Fl(a)6 b Fr(,)14 b Fl(b)7 b Fn(i)20 b Fs(can)g(be)g(one)g(of)g
(three)g(things)g([9)o(]:)434 4478 y(1.)41 b Fl(a)28
b Fm(<)23 b(g)g(<)g Fl(b)7 b Fs(.)29 b Fm(g)21 b Fs(is)g(equal)e(to)i
(the)f(minimax)f(v)n(alue)g Fr(\246)j Fs(of)e(the)g(game)f(tree)h
Fm(G)p Fs(.)434 4643 y(2.)41 b Fm(g)22 b Fr(\243)h Fl(a)k
Fs(\(f)o(ailing)19 b(lo)n(w\).)29 b Fm(g)20 b Fs(is)h(an)f(upper)f
(bound)f(on)i(the)g(minimax)f(v)n(alue)h Fr(\246)h Fs(of)f
Fm(G)p Fs(,)g(or)g Fr(\246)k(\243)f Fm(g)p Fs(.)434 4808
y(3.)41 b Fm(g)22 b Fr(\263)h Fl(b)28 b Fs(\(f)o(ailing)19
b(high\).)28 b Fm(g)20 b Fs(is)h(a)g(lo)n(wer)f(bound)e(on)i(the)g
(minimax)f(v)n(alue)g Fr(\246)j Fs(of)e Fm(G)p Fs(,)g
Fr(\246)j(\263)g Fm(g)p Fs(.)330 4973 y(W)-7 b(e)28 b(see)g(that)f(a)h
(single)f(null)g(windo)n(w)f(search)g(will)i(ne)n(v)o(er)e(return)g
(the)h(true)g(minimax)f(v)n(alue)g Fr(\246)p Fs(,)k(b)n(ut)330
5073 y(only)20 b(a)h(bound)f(on)g(it)i(\(which)e(may)g(happen)f(to)j
(coincide)d(with)i Fr(\246)p Fs(,)h(b)n(ut)f(this)h(cannot)d(be)i
(inferred)f(from)330 5172 y(the)h(result)g(of)g(the)g(null)g(windo)n(w)
f(call\).)31 b(A)22 b(f)o(ail)f(lo)n(w)g(results)h(in)f(an)g(upper)e
(bound,)h(denoted)f(by)i Fr(\246)3180 5142 y Fk(+)3217
5172 y Fs(.)32 b(A)330 5272 y(f)o(ail)24 b(high)e(returns)h(a)g(lo)n
(wer)g(bound,)f(denoted)g(by)h Fr(\246)1845 5242 y Fj(\000)1901
5272 y Fs(.)39 b(Algorithms)23 b(lik)o(e)g(C*)h(and)f(Alpha)f(Bounding)
330 5372 y(use)27 b(multiple)f(null)g(windo)n(w)f(calls)j(to)e
(generate)g(bounds)f(to)h(home)g(in)h(on)f(the)g(minimax)g(v)n(alue.)47
b(A)330 5471 y(potential)31 b(problem)g(with)h(these)h(repetiti)n(v)o
(e)e(calls)i(is)g(that)f(the)o(y)g(re-e)o(xpand)d(pre)n(viously)i
(searched)330 5571 y(nodes.)d(F)o(or)19 b(Ne)o(gaScout)f(it)i(appears)e
(that)h(the)h(gains)e(of)h(the)h(tighter)e(bounds)g(out-weigh)g(the)h
(costs)h(of)330 5670 y(re-e)o(xpansions,)d(compared)h(to)j(a)f(single)h
(wide-windo)n(w)d(Alpha-Beta)h(call)i([16)o(].)1809 5919
y(2)p eop
%%Page: 3 3
3 2 bop 851 545 a Fw(max)19 b(solution)g(tree)988 b(min)19
b(solution)g(tree)1034 638 y(6)279 b(all)p 1088 677 4
105 v 1092 576 105 4 v 1088 681 V 1193 681 4 105 v 909
917 a Fi(m)p 759 1259 V 763 1157 105 4 v 759 1262 V 864
1262 4 105 v 716 1499 a(m)p 565 1840 V 569 1738 105 4
v 565 1843 V 670 1843 4 105 v 600 1917 a Fw(6)636 1737
y Fh(\002)664 1654 y(\002)670 1637 y(\002)734 1443 y(\002)762
1360 y(\002)767 1343 y(\002)35 b(B)858 1426 y(B)863 1443
y(B)909 1499 y Fi(m)p 759 1840 V 763 1738 105 4 v 759
1843 V 864 1843 4 105 v 794 1917 a Fw(2)830 1737 y Fh(\002)858
1654 y(\002)863 1637 y(\002)830 1156 y(\002)858 1073
y(\002)863 1056 y(\002)946 872 y(\034)1012 789 y(\034)1034
762 y(\034)84 b(\\)1250 845 y(\\)1272 872 y(\\)1564 929
y Fw(one)1374 917 y Fi(m)1377 1220 y Fw(all)p 1127 1259
V 1131 1157 105 4 v 1127 1262 V 1232 1262 4 105 v 1084
1499 a Fi(m)p 933 1840 V 937 1738 105 4 v 933 1843 V
1038 1843 4 105 v 968 1917 a Fw(4)1004 1737 y Fh(\002)1032
1654 y(\002)1038 1637 y(\002)1102 1443 y(\002)1130 1360
y(\002)1136 1343 y(\002)34 b(B)1226 1426 y(B)1231 1443
y(B)1449 1510 y Fw(one)1278 1498 y Fi(m)p 1127 1840 V
1131 1738 105 4 v 1127 1843 V 1232 1843 4 105 v 1162
1917 a Fw(3)1198 1737 y Fh(\002)1226 1654 y(\002)1231
1637 y(\002)1216 1156 y(\012)1271 1073 y(\012)1287 1049
y(\012)2676 638 y Fw(2)279 b(one)p 2730 677 V 2734 576
105 4 v 2730 681 V 2835 681 4 105 v 2780 929 a(all)2590
917 y Fi(m)p 2318 1259 V 2322 1157 105 4 v 2318 1262
V 2423 1262 4 105 v 2276 1499 a(m)p 2125 1840 V 2129
1738 105 4 v 2125 1843 V 2230 1843 4 105 v 2160 1917
a Fw(6)2196 1737 y Fh(\002)2224 1654 y(\002)2229 1637
y(\002)37 b(B)2322 1720 y(B)2327 1737 y(B)p 2318 1840
V 2322 1738 105 4 v 2318 1843 V 2423 1843 4 105 v 2354
1917 a Fw(2)2294 1443 y Fh(\002)2322 1360 y(\002)2327
1343 y(\002)2412 1156 y(\023)2474 1073 y(\023)2493 1047
y(\023)70 b(S)2687 1130 y(S)2707 1156 y(S)3004 1220 y
Fw(one)p 2754 1259 V 2758 1157 105 4 v 2754 1262 V 2859
1262 4 105 v 2805 1510 a(all)2634 1498 y Fi(m)p 2483
1840 V 2487 1738 105 4 v 2483 1843 V 2588 1843 4 105
v 2518 1917 a Fw(4)2554 1737 y Fh(\002)2582 1654 y(\002)2588
1637 y(\002)36 b(B)2680 1720 y(B)2686 1737 y(B)p 2677
1840 V 2681 1738 105 4 v 2677 1843 V 2782 1843 4 105
v 2712 1917 a Fw(3)2664 1449 y Fh(\024)2714 1366 y(\024)2727
1343 y(\024)2623 869 y(\012)2678 786 y(\012)2694 762
y(\012)1412 2175 y Fs(Figure)19 b(1:)30 b(Solution)19
b(T)m(rees.)330 2442 y Fo(2.2)99 b(Memory)330 2597 y
Fs(An)14 b(idea)f(to)h(pre)n(v)o(ent)e(the)i(re-e)o(xpansion)d(of)j
(pre)n(viously)d(searched)i(nodes)g(is)i(to)f(store)g(them)f(in)h