hk.ps

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

(memory)-5 b(.)330 2697 y(It)22 b(is)h(often)d(said)i(that)g(since)g
(minimax)e(trees)i(are)g(of)f(e)o(xponential)f(size,)i(this)g(approach)
e(is)i(infeasible)330 2797 y(since)32 b(it)g(needs)f(e)o(xponentially)d
(gro)n(wing)i(amounts)g(of)h(memory)-5 b(.)61 b(W)-7
b(e)32 b(will)g(sho)n(w)f(in)h(this)g(paper)330 2896
y(that)21 b(although)f(the)h(search)g(information)e(that)j(must)f(be)g
(stored)g(is)h(indeed)e(of)i(e)o(xponential)d(size,)j(it)g(is)330
2996 y(certainly)g(less)i(than)f(what)g(is)h(often)f(assumed.)37
b(F)o(or)23 b(today')-5 b(s)23 b(search)f(depths)h(it)h(\256ts)g
(comfortably)c(in)330 3096 y(today')-5 b(s)20 b(memories.)31
b(Projections)20 b(of)g(tomorro)n(w')-5 b(s)19 b(search)i(depths)f(and)
g(memory)g(sizes)h(predict)f(that)330 3195 y(this)h(situation)e(will)i
(persist)g(in)f(the)h(foreseeable)d(future.)455 3295
y(The)f(information)f(returned)g(by)i(an)g(Alpha-Beta)f(call)i(is)g
(either)e(a)i(bound)d(or)i(the)g(minimax)e(v)n(alue.)330
3394 y(Knuth)31 b(and)h(Moore)f(ha)n(v)o(e)g(sho)n(wn)h(that)g(the)g
(essential)g(part)g(of)g(the)g(search)g(tree)g(that)g(pro)o(v)o(es)f
(the)330 3494 y(minimax)23 b(v)n(alue)g(is)i(the)f(so)g(called)f
Fm(minimal)h(tr)m(ee)p Fs(.)41 b(F)o(or)23 b(a)i(minimax)d(tree)i(of)g
(uniform)e(width)h Fm(w)i Fs(and)330 3594 y(depth)c Fm(d)r
Fs(,)h(it)g(has)g Fm(w)880 3564 y Fj(b)p Fg(d)r Ff(/)p
Fk(2)p Fj(c)1038 3594 y Fs(+)d Fm(w)1159 3564 y Fj(d)p
Fg(d)r Ff(/)p Fk(2)p Fj(e)1318 3594 y Fn(\000)f Fs(1)k(lea)n(v)o(es,)g
(or)m(,)f(its)i(size)f(is)h Fm(O)p Fs(\()p Fm(w)2295
3564 y Fj(d)p Fg(d)r Ff(/)p Fk(2)p Fj(e)2434 3594 y Fs(\).)33
b(If)22 b(Alpha-Beta)f(returns)g(an)330 3693 y(upper)g(bound,)f(then)h
(its)i(v)n(alue)e(is)i(de\256ned)e(by)h(a)g(so)g(called)g(max)g
(solution)f(tree,)h(in)g(a)g(sense)h(one)e(half)330 3793
y(of)26 b(a)g(minimal)g(tree,)h(of)f(size)h Fm(O)p Fs(\()p
Fm(w)1361 3763 y Fj(d)p Fg(d)r Ff(/)p Fk(2)p Fj(e)1499
3793 y Fs(\).)47 b(If)26 b(Alpha-Beta)g(returns)f(a)h(lo)n(wer)g
(bound,)g(then)f(its)i(v)n(alue)330 3893 y(is)f(de\256ned)e(by)g(a)h
(min)g(solution)f(tree,)h(the)g(other)f(half)h(of)f(a)h(minimal)f
(tree,)i(of)f(size)g Fm(O)p Fs(\()p Fm(w)2970 3862 y
Fj(b)p Fg(d)r Ff(/)p Fk(2)p Fj(c)3109 3893 y Fs(\).)43
b(The)330 3992 y(\(theoretical\))28 b(background)d(for)k(these)g
(statements)h(can)f(be)g(found)f(in)h([5)o(,)h(10)o(,)g(21)o(,)f(29)o
(].)57 b(Figure)28 b(1)330 4092 y(sho)n(ws)20 b(a)h(max)f(and)f(a)i
(min)f(solution)f(tree.)455 4191 y(Since)i(recursi)n(v)o(e)e(null)i
(windo)n(w)f(Alpha-Beta)g(calls)i(return)e(only)g(bounds,)g(storing)g
(the)h(pre)n(vious)330 4291 y(search)j(results)h(comes)f(do)n(wn)g(to)h
(storing)e(a)j(max)e(or)g(a)h(min)f(solution)g(tree.)42
b(Although)23 b(not)h(e)o(xactly)330 4391 y(small)c(for)f(the)h(case)g
(of)g(chess,)g(assuming)f(a)h(search)f(depth)g(of)h(8)g(or)f(9)h(and)f
(a)h(branching)e(f)o(actor)h(of)g(36,)330 4490 y(the)25
b(numbers)e(are)i(not)g(completely)e(out)i(of)g(reach)f(of)g(todays)h
(technology)-5 b(.)40 b(In)25 b(addition,)g(these)g(are)330
4590 y(numbers)e(for)g(\(uniform\))f(trees.)41 b(Real)25
b(games)e(usually)h(ha)n(v)o(e)g(transpositions,)f(that)i(can)f(reduce)
f(the)330 4690 y(search)d(space)g(tremendously)e([19)n(].)455
4789 y(Here)24 b(we)g(arri)n(v)o(e)g(at)g(an)h(important)d(decision:)38
b(to)24 b(decide)g(on)f(a)i(method)e(that)i(is)g(suited)f(to)h(store)
330 4889 y(the)k(information)e(of)i(pre)n(vious)e(searches.)56
b(F)o(or)29 b(game)f(playing)g(programs)f(an)i(ob)o(vious)e(choice)i
(is)330 4988 y(the)f(transposition)f(table.)52 b(According)26
b(to)j(the)f(literature,)h(it)g(is)g(used)e(for)h(tw)o(o)g(reasons)g
(in)g(current)330 5088 y(programs)21 b([11)o(].)39 b(The)23
b(foremost)f(reason)g(is)i(to)g(increase)f(the)g(mo)o(v)o(e)f(ordering)
f(in)j(conjunction)c(with)330 5188 y(iterati)n(v)o(e)g(deepening,)d(to)
k(increase)f(the)g(number)e(of)i(Alpha-Beta)g(cutof)n(fs.)28
b(The)20 b(second)g(reason)f(is)i(to)330 5287 y(pre)n(v)o(ent)d(re-e)o
(xpansion)e(of)k(nodes)f(that)g(ha)n(v)o(e)g(already)g(been)f
(searched,)h(due)g(to)g(transpositions)g(in)h(the)330
5387 y(search)g(space.)455 5487 y(F)o(or)h(algorithms)g(using)h
(multiple)f(\(null-windo)n(w\))e(passes,)k(or)f(re-searches,)f(a)i
(third)e(reason)h(can)330 5586 y(be)30 b(added:)49 b(to)30
b(pre)n(v)o(ent)f(the)h(re-e)o(xpansion)e(of)i(nodes)g(searched)f(in)i
(a)f(pre)n(vious)f(pass.)60 b(The)30 b(only)1809 5919
y(3)p eop
%%Page: 4 4
4 3 bop 330 548 a Fw(/*)19 b(T)m(ransposition)h(table)f(\(TT\))f
(enhanced)i(Alpha-Beta)f(*/)330 639 y Fv(function)e Fw(Alpha-Beta\()p
Fe(n)p Fu(,)c Fd(a)5 b Fu(,)13 b Fd(b)6 b Fw(\))21 b
Fu(\256)g Fe(g)p Fw(;)446 731 y(/*)e(Check)h(if)e(position)i(is)e(in)h
(TT)f(and)h(has)h(been)f(searched)h(to)f(suf)n(\256cient)g(depth)h(*/)
446 822 y Fv(if)f Fw(retrie)n(v)o(e\()p Fe(n)p Fw(\))g(=)f(found)i
Fv(then)563 913 y(if)e Fe(n)p Fu(.\246)714 882 y Fc(+)768
913 y Fu(\243)j Fd(a)j Fv(or)19 b Fe(n)p Fu(.\246)1067
882 y Fc(+)1121 913 y Fw(=)i Fe(n)p Fu(.\246)1271 882
y Fq(\000)1342 913 y Fv(then)d(r)o(etur)o(n)g Fe(n)p
Fu(.\246)1813 882 y Fc(+)1845 913 y Fw(;)563 1005 y Fv(if)g
Fe(n)p Fu(.\246)714 973 y Fq(\000)787 1005 y Fu(\263)k
Fd(b)j Fv(then)18 b(r)o(etur)o(n)g Fe(n)p Fu(.\246)1377
973 y Fq(\000)1429 1005 y Fw(;)446 1096 y(/*)h(Reached)h(the)f(maximum)
h(search)f(depth)h(*/)446 1187 y Fv(if)f Fe(n)g Fw(=)f(leaf)h
Fv(then)563 1279 y Fe(n)p Fu(.\246)650 1247 y Fq(\000)723
1279 y Fw(:=)i Fe(n)p Fu(.\246)894 1247 y Fc(+)948 1279
y Fw(:=)g Fe(g)h Fw(:=)d(e)n(v)n(al\()p Fe(n)p Fw(\);)446
1370 y Fv(else)563 1461 y Fe(g)i Fw(:=)g Fb(\000)p Fu(\245)p
Fw(;)
%% correction
f Fe(a)j Fr(:=)f Fd(a)p Fr(;)
563 1553 y Fe(c)g Fw(:=)e(\256rstchild\()p Fe(n)p
Fw(\);)563 1644 y(/*)f(Search)h(until)g(a)g(cutof)n(f)g(occurs)h(or)f
(all)f(children)i(ha)o(v)o(e)f(been)h(considered)g(*/)563
1735 y Fv(while)d Fe(g)22 b(<)g Fd(b)j Fv(and)18 b Fe(c)k
Fb(6)p Fw(=)f Fb(?)c Fv(do)679 1826 y Fe(g)k Fw(:=)e(max\()p
Fe(g)p Fu(,)13 b Fb(\000)p Fw(Alpha-Beta\()p Fe(c)p Fu(,)g
Fb(\000)p Fd(b)6 b Fu(,)13 b Fb(\000)p Fe(a)5 b Fw(\)\);)679
1918 y Fe(a)26 b Fw(:=)19 b(max\()p Fe(a)5 b Fu(,)12
b Fe(g)p Fw(\);)679 2009 y Fe(c)21 b Fw(:=)e(ne)o(xtbrother\()p
Fe(c)p Fw(\);)563 2100 y(/*)f(Sa)o(v)o(e)h(in)f(transposition)i(table)f
(*/)563 2192 y Fv(if)f Fe(g)k Fu(\243)f Fd(a)j Fv(then)18
b Fe(n)p Fu(.\246)1056 2160 y Fc(+)1109 2192 y Fw(:=)k
Fe(g)p Fw(;)563 2283 y Fv(if)c Fd(a)26 b Fe(<)c(g)f(<)h
Fd(b)j Fv(then)18 b Fe(n)p Fu(.\246)1205 2251 y Fc(+)1259
2283 y Fw(:=)j Fe(n)p Fu(.\246)1430 2251 y Fq(\000)1504
2283 y Fw(:=)g Fe(g)p Fw(;)563 2374 y Fv(if)d Fe(g)k
Fu(\263)f Fd(b)k Fv(then)18 b Fe(n)p Fu(.\246)1051 2343
y Fq(\000)1125 2374 y Fw(:=)j Fe(g)p Fw(;)446 2466 y(store\()p
Fe(n)p Fw(\);)446 2557 y Fv(r)o(etur)o(n)d Fe(g)p Fw(;)899
2823 y Fs(Figure)h(2:)30 b(Alpha-Beta)19 b(for)h(use)g(with)h(T)m
(ransposition)d(T)-7 b(ables.)330 3090 y(dif)n(ference)19
b(with)j(the)f(second)g(reason)f(is)j(that)e(the)g(table)h(entries)f
(are)g(not)g(caused)g(by)g(transpositions,)330 3190 y(b)n(ut)k(by)f(a)h
(pre)n(vious)e(search)h(pass;)j(there)d(is)i(no)e(dif)n(ference)e(as)j
(f)o(ar)g(as)g(the)g(algorithm)e(is)i(concerned.)330
3289 y(The)c(basic)g(idea)g(is)h(that)f(it)h(is)g(possible)f(to)h
(store)f(the)g(search)g(tree)g(as)h(kno)n(wn)d(from)h(more)h
(theoretical)330 3389 y(w)o(ork)29 b([7)o(,)h(10)o(,)g(17)o(,)g(29)o(])
g(in)f(the)h(transposition)e(table.)57 b(Some)29 b(background)d(e)o
(xplaining)i(in)i(greater)330 3488 y(detail)20 b(why)f(the)h
(transposition)e(table)i(is)h(a)f(suitable)g(structure)f(for)g(storing)
g(search)h(or)f(solution)h(trees,)330 3588 y(and)e(why)f(it)i(gi)n(v)o
(es)f(correct)f(results)h(in)h(algorithms)e(doing)f(repetiti)n(v)o(e)h
(null)h(windo)n(w)g(searches,)g(can)g(be)330 3688 y(found)g(in)j([5)o
(,)f(21)o(].)330 3968 y Ft(3)119 b(MT)-9 b(:)30 b(Memory)f(enhanced)j
(T)-11 b(est)330 4153 y Fs(The)18 b(concept)f(of)i(null)f(windo)n(w)f
(search)i(w)o(as)g(introduced)d(by)i(Pearl,)h(who)f(called)g(the)h
(procedure)d(T)-6 b(est)330 4253 y([15)o(].)59 b(F)o(or)29
b(that)i(reason,)g(we)g(ha)n(v)o(e)e(named)g(our)h(memory)e(enhanced)g
(v)o(ersion)h(MT,)h(for)f(memory)330 4353 y(enhanced)j(T)-6
b(est.)73 b(\(Our)34 b(T)-6 b(est)35 b(returns)e(a)i(bound,)h(not)e
(just)h(a)g(boolean)e(v)n(alue.)71 b(This)34 b(v)o(ersion)g(is)330
4452 y(sometimes)16 b(called)h Fm(informed)h Fs(T)-6
b(est\).)29 b(The)16 b(code)g(for)g(MT,)h(in)f(its)i(Alpha-Beta)e
(form,)g(can)h(be)f(found)f(in)330 4552 y(\256gure)h(2.)29
b(In)16 b(this)i(paper)e(we)i(will)f(interchangeably)d(use)k(the)f
(terms)g(MT)g(and)g(Alpha-Beta)f(procedure)330 4652 y(\(as)27
b(opposed)d(to)j Fm(algorithm)p Fs(\).)46 b(\(Storing)25
b(both)g(bounds)g(at)h(the)h(same)f(time)g(is)i(necessary)d(for)h(some)
330 4751 y(algorithms,)d(while)g(for)g(others)f(it)i(impro)o(v)o(es)e
(the)h(ef)n(\256cienc)o(y)f(only)g(slightly)h([21)o(].)39
b(If)23 b(the)g(algorithm)330 4851 y(does)17 b(not)f(need)g(to)h(store)
g(tw)o(o)g(solution)f(trees)i(at)f(the)g(same)g(time,)h(then)e(in)h
(practice)f(the)h(e)o(xtra)f(memory)330 4950 y(needed)j(is)i
(considered)d(too)i(much.\))455 5050 y(So)d(f)o(ar)m(,)g(we)h(ha)n(v)o
(e)e(discussed)h(the)g(follo)n(wing)f(tw)o(o)h(mechanisms)f(to)i(be)f
(used)g(in)g(b)n(uilding)f(ef)n(\256cient)330 5150 y(algorithms:)40
b(\(1\))25 b(null)h(windo)n(w)e(searches)i(cutof)n(f)f(more)g(nodes)g
(than)g(wide)h(search)g(windo)n(ws,)g(and)330 5249 y(\(2\))e(we)h(can)g
(use)g(transposition)f(tables)h(to)g(glue)f(multiple)g(passes)i(of)e
(null)h(windo)n(w)f(calls)i(together)m(,)330 5349 y(so)j(that)f(the)o
(y)g(can)h(be)f(used)g(to)h(home)e(in)i(on)f(the)h(minimax)e(v)n(alue,)
j(without)d(re-e)o(xpanding)e(nodes)330 5449 y(searched)d(in)g(pre)n
(vious)f(passes.)37 b(W)-7 b(e)24 b(can)e(use)h(these)g(b)n(uilding)e
(blocks)h(to)h(construct)e(a)i(multitude)f(of)330 5548
y(dif)n(ferent)e(algorithms.)34 b(One)21 b(option)g(is)i(to)f
(construct)f(dri)n(v)o(ers)g(that)h(repeatedly)e(call)j(MT)f(at)g(the)g
(root)330 5648 y(of)28 b(the)h(game)e(tree.)54 b(Three)27
b(of)i(these)f(MT-dri)n(v)o(ers)f(are)h(sho)n(wn)g(in)g(the)h
(\256gures)f(3,)i(5,)g(and)e(6.)54 b(The)1809 5919 y(4)p
eop
%%Page: 5 5
5 4 bop 504 454 a Fv(function)18 b Fw(AB-SSS*\()p Fe(n)p
Fw(\))i Fu(\256)h(\246)p Fw(;)621 545 y Fe(g)g Fw(:=)h(+)p
Fu(\245)p Fw(;)621 637 y Fv(r)o(epeat)737 728 y Fd(g)32
b Fw(:=)21 b Fe(g)p Fw(;)737 819 y Fe(g)h Fw(:=)c(Alpha-Beta\()p
Fe(n)p Fu(,)13 b Fd(g)28 b Fb(\000)17 b Fw(1)p Fu(,)c
Fd(g)d Fw(\);)621 911 y Fv(until)17 b Fe(g)22 b Fw(=)f
Fd(g)10 b Fw(;)621 1002 y Fv(r)o(etur)o(n)17 b Fe(g)p
Fw(;)600 1268 y Fs(Figure)i(3:)30 b(SSS*)21 b(as)g(a)f(Sequence)f(of)h
(memory)f(enhanced)f(Alpha-Beta)h(Searches.)767 2886
y @beginspecial 50 @llx 50 @lly 410 @urx 302 @ury 2551
@rwi 1700 @rhi @setspecial
%%BeginDocument: plot.sss.tt.p.ps
/gnudict 40 dict def
gnudict begin
/Color false def
/Solid false def
/gnulinewidth 5.000 def
/vshift -66 def
/dl {10 mul} def
/hpt 31.5 def
/vpt 31.5 def
/M {moveto} bind def
/L {lineto} bind def
/R {rmoveto} bind def
/V {rlineto} bind def
/vpt2 vpt 2 mul def
/hpt2 hpt 2 mul def
/Lshow { currentpoint stroke M
  0 vshift R show } def
/Rshow { currentpoint stroke M
  dup stringwidth pop neg vshift R show } def
/Cshow { currentpoint stroke M
  dup stringwidth pop -2 div vshift R show } def
/DL { Color {setrgbcolor Solid {pop []} if 0 setdash }
 {pop pop pop Solid {pop []} if 0 setdash} ifelse } def
/BL { stroke gnulinewidth 2 mul setlinewidth } def
/AL { stroke gnulinewidth 2 div setlinewidth } def
/PL { stroke gnulinewidth setlinewidth } def
/LTb { BL [] 0 0 0 DL } def
/LTa { AL [1 dl 2 dl] 0 setdash 0 0 0 setrgbcolor } def
/LT0 { PL [] 0 1 0 DL } def
/LT1 { PL [4 dl 2 dl] 0 0 1 DL } def
/LT2 { PL [2 dl 3 dl] 1 0 0 DL } def
/LT3 { PL [1 dl 1.5 dl] 1 0 1 DL } def
/LT4 { PL [5 dl 2 dl 1 dl 2 dl] 0 1 1 DL } def
/LT5 { PL [4 dl 3 dl 1 dl 3 dl] 1 1 0 DL } def
/LT6 { PL [2 dl 2 dl 2 dl 4 dl] 0 0 0 DL } def
/LT7 { PL [2 dl 2 dl 2 dl 2 dl 2 dl 4 dl] 1 0.3 0 DL } def
/LT8 { PL [2 dl 2 dl 2 dl 2 dl 2 dl 2 dl 2 dl 4 dl] 0.5 0.5 0.5 DL } def
/P { stroke [] 0 setdash
  currentlinewidth 2 div sub M
  0 currentlinewidth V stroke } def
/D { stroke [] 0 setdash 2 copy vpt add M
  hpt neg vpt neg V hpt vpt neg V
  hpt vpt V hpt neg vpt V closepath stroke
  P } def
/A { stroke [] 0 setdash vpt sub M 0 vpt2 V
  currentpoint stroke M
  hpt neg vpt neg R hpt2 0 V stroke
  } def
/B { stroke [] 0 setdash 2 copy exch hpt sub exch vpt add M
  0 vpt2 neg V hpt2 0 V 0 vpt2 V
  hpt2 neg 0 V closepath stroke
  P } def
/C { stroke [] 0 setdash exch hpt sub exch vpt add M
  hpt2 vpt2 neg V currentpoint stroke M
  hpt2 neg 0 R hpt2 vpt2 V stroke } def
/T { stroke [] 0 setdash 2 copy vpt 1.12 mul add M
  hpt neg vpt -1.62 mul V
  hpt 2 mul 0 V
  hpt neg vpt 1.62 mul V closepath stroke
  P  } def
/S { 2 copy A C} def
end
gnudict begin
gsave
50 50 translate
0.050 0.050 scale
0 setgray
/Times-Roman findfont 200 scalefont setfont
newpath
LTa