hk.ps

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

LTb
1200 827 M
63 0 V
5634 0 R
-63 0 V
-5754 0 R
(90) Rshow
1200 1479 M
63 0 V
5634 0 R
-63 0 V
-5754 0 R
(100) Rshow
1200 2131 M
63 0 V
5634 0 R
-63 0 V
-5754 0 R
(110) Rshow
1200 2783 M
63 0 V
5634 0 R
-63 0 V
-5754 0 R
(120) Rshow
1200 3435 M
63 0 V
5634 0 R
-63 0 V
-5754 0 R
(130) Rshow
1200 4087 M
63 0 V
5634 0 R
-63 0 V
-5754 0 R
(140) Rshow
1200 4739 M
63 0 V
5634 0 R
-63 0 V
-5754 0 R
(150) Rshow
1770 501 M
0 63 V
0 4175 R
0 -63 V
0 -4375 R
(14) Cshow
2909 501 M
0 63 V
0 4175 R
0 -63 V
0 -4375 R
(16) Cshow
4049 501 M
0 63 V
0 4175 R
0 -63 V
0 -4375 R
(18) Cshow
5188 501 M
0 63 V
0 4175 R
0 -63 V
0 -4375 R
(20) Cshow
6327 501 M
0 63 V
0 4175 R
0 -63 V
0 -4375 R
(22) Cshow
1200 501 M
5697 0 V
0 4238 V
-5697 0 V
0 -4238 V
200 2620 M
currentpoint gsave translate 90 rotate 0 0 M
(Leaves Relative to ID Alpha-Beta \(%\)) Cshow
grestore
4048 101 M
(lg of Entries in Transposition Table) Cshow
4048 4939 M
(Chess - Sensitivity of ID AB-SSS* to Storage) Cshow
LT0
6234 4476 M
(ID Alpha-Beta) Rshow
6354 4476 M
360 0 V
1200 1479 M
570 0 V
569 0 V
570 0 V
570 0 V
570 0 V
569 0 V
570 0 V
570 0 V
569 0 V
570 0 V
LT1
6234 4276 M
(ID AB-SSS* depth 7) Rshow
6354 4276 M
360 0 V
2258 4739 M
81 -782 V
2909 1675 L
570 -587 V
570 -65 V
569 0 V
570 65 V
570 0 V
569 0 V
6474 4276 D
2339 3957 D
2909 1675 D
3479 1088 D
4049 1023 D
4618 1023 D
5188 1088 D
5758 1088 D
6327 1088 D
LT2
6234 4076 M
(ID AB-SSS* depth 6) Rshow
6354 4076 M
360 0 V
2150 4739 M
2339 3696 L
2909 1935 L
570 -717 V
4049 957 L
4618 827 L
570 -65 V
570 0 V
569 -65 V
6474 4076 A
2339 3696 A
2909 1935 A
3479 1218 A
4049 957 A
4618 827 A
5188 762 A
5758 762 A
6327 697 A
LT3
6234 3876 M
(ID AB-SSS* depth 5) Rshow
6354 3876 M
360 0 V
1770 1153 M
569 65 V
570 0 V
570 0 V
570 65 V
569 0 V
570 0 V
570 0 V
569 0 V
6474 3876 B
1770 1153 B
2339 1218 B
2909 1218 B
3479 1218 B
4049 1283 B
4618 1283 B
5188 1283 B
5758 1283 B
6327 1283 B
stroke
grestore
end
showpage
%%EndDocument
 @endspecial 1158 3151 a(Figure)g(4:)30 b(Leaf)20 b(node)f(count)g(ID)h
(AB-SSS*.)330 3419 y(dri)n(v)o(ers)f(dif)n(fer)g(in)h(the)h(w)o(ay)f
(the)g(null)g(windo)n(w)f(is)i(chosen)f(\(denoted)e(by)i
Fl(g)32 b Fs(in)20 b(the)g(\256gures\).)330 3656 y Fo(3.1)99
b(SSS*)330 3812 y Fs(The)20 b(dri)n(v)o(er)f(in)i(\256gure)e(3)i
(constructs)f(an)g(algorithm)f(that)h(starts)i(with)e(an)h(upper)e
(bound)f(of)i(+)p Fr(\245)p Fs(.)31 b(From)330 3912 y(Alpha-Beta')-5
b(s)20 b(postcondition)e(we)i(see)h(that)g(this)f(call)h(will)g(f)o
(ail)g(lo)n(w)-5 b(,)20 b(yielding)f(an)h(upper)f(bound.)27
b(By)330 4011 y(feeding)d(this)h(upper)f(bound)f Fr(\246)1235
3981 y Fk(+)1298 4011 y Fs(again)h(to)h(an)g(MT)g(call,)h(we)g(will)f
(get)g(a)h(sequence)e(of)g(f)o(ail)i(lo)n(ws.)44 b(In)330
4111 y(the)25 b(end,)g(if)h Fm(g)j Fs(=)h Fl(g)12 b Fs(,)25
b(we)h(will)g(ha)n(v)o(e)e(a)h(f)o(ail)h(high)e(with)h
Fm(g)30 b Fs(=)f Fr(\246)2124 4081 y Fj(\000)2210 4111
y Fs(=)h Fl(g)41 b Fs(=)30 b Fr(\246)2473 4081 y Fk(+)2510
4111 y Fs(,)c(which)f(means)g(the)g(game)330 4210 y(v)n(alue)d
Fr(\246)i Fs(is)g(found.)35 b(T)-7 b(o)23 b(compute)f(the)h(ne)o(xt)f
(upper)f(bound,)h(AB-SSS*)h(re\256nes)g(a)g(max)g(solution)f(tree)330
4310 y([20)o(,)e(17)o(,)h(18)o(].)455 4410 y(This)c(dri)n(v)o(er)e(e)o
(xpands)g(the)i(same)g(leaf)g(nodes)f(in)h(the)g(same)f(order)g(as)i
(Stockman')-5 b(s)15 b(SSS*)j([18)n(,)g(21)o(].)330 4509
y(In)23 b(this)h(sense,)h(we)e(ha)n(v)o(e)g(constructed)f(an)h(equi)n
(v)n(alent)f(formulation)f(of)i(SSS*,)i(constructing)c(a)j(best)330
4609 y(\256rst)15 b(algorithm)d(using)i(depth)f(\256rst,)i(memory)e
(enhanced,)g(search.)26 b(F)o(ormulating)12 b(SSS*)j(as)f(a)h(sequence)
330 4709 y(of)j(null)h(windo)n(w)e(searches)i(mak)o(es)f(clear)g
Fm(why)h Fs(it)h(searches)e(less)i(lea)n(v)o(es)e(than)h(a)g(single)f
(wide)h(windo)n(w)330 4808 y(Alpha-Beta)f(call,)i(as)g(has)f(been)f
(pro)o(v)o(en)f(by)i(Stockman:)27 b(because)19 b(of)g(the)g(smaller)g
(search)g(windo)n(ws.)455 4908 y(The)33 b(ne)n(w)g(formulation)f(has)h
(a)h(number)e(of)i(practical)f(adv)n(antages)f(o)o(v)o(er)g(the)i(old)f
(Stockman)330 5007 y(formulation.)38 b(The)24 b(biggest)f(adv)n(antage)
f(is)j(that)f(this)h(formulation)c(is)k(readily)e(implementable)f(in)i
(a)330 5107 y(re)o(gular)17 b(Alpha-Beta)h(based)g(chess)h(program.)27
b(This)19 b(enables)f(us)h(to)g(\256nally)f(test)h(the)g(performance)d
(of)330 5207 y(SSS*)21 b(in)f(a)h(real)f(application.)28
b(Section)19 b(4)i(gi)n(v)o(es)e(these)i(test)g(results.)455
5306 y(Another)29 b(quite)h(interesting)g(test)i(is)g(to)f(see)g(ho)n
(w)f(much)g(storage)g(is)i(needed)d(to)i(store)g(the)g(re-)330
5406 y(search)16 b(information\320is)f(it)i(indeed)f(of)g(the)h(order)e
(of)i(the)f(max)g(solution)g(tree?\320in)g(the)h(transposition)330
5506 y(table.)29 b(Of)21 b(the)f(three)g(uses)h(of)f(the)g
(transposition)f(table\320better)g(mo)o(v)o(e)g(ordering,)f(no)i(re-e)o
(xpansions)330 5605 y(through)k(transpositions,)j(and)f(no)g(re-e)o
(xpansions)d(from)j(pre)n(vious)e(passes\320we)j(are)g(interested)e(in)
1809 5919 y(5)p eop
%%Page: 6 6
6 5 bop 504 454 a Fv(function)18 b Fw(AB-DU)m(AL*\()p
Fe(n)p Fw(\))j Fu(\256)g(\246)p Fw(;)621 545 y Fe(g)g
Fw(:=)h Fb(\000)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)d Fu(,)j
Fd(g)28 b Fw(+)17 b(1\);)621 911 y Fv(until)g 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(;)556 1268 y Fs(Figure)i(5:)30 b(DU)m(AL*)19
b(as)i(a)g(Sequence)e(of)g(memory)g(enhanced)f(Alpha-Beta)i(Searches.)
330 1535 y(the)e(third)f(one.)28 b(That)18 b(w)o(ould)f(sho)n(w)h(us)g
(whether)f(the)h(assumption)f(of)h(section)f(2.2,)h(that)g(the)g
(re-search)330 1635 y(information)24 b(\256ts)j(in)f(memory)-5
b(,)26 b(is)h(v)n(alid.)47 b(Therefore,)25 b(we)i(ha)n(v)o(e)e
(conducted)f(tests)k(with)e(a)h(v)n(ariable)330 1734
y(size)18 b(transposition)d(table,)j(and)e(sho)n(w)h(the)g(number)e(of)
i(e)o(xpanded)d(nodes)j(for)f(a)i(multi-pass)e(algorithm)330
1834 y(di)n(vided)23 b(by)i(the)g(nodes)f(e)o(xpanded)f(by)h(a)h
(one-pass)f(algorithm.)42 b(T)-7 b(o)25 b(put)g(it)h(dif)n(ferently)-5
b(,)23 b(ho)n(w)i(much)330 1933 y(memory)32 b(does)h(AB-SSS*)g(need)g
(to)g(beat)g(Alpha-Beta?)68 b(Figure)33 b(4)g(sho)n(ws)g(the)g(test)i
(results)e(for)330 2033 y(Phoenix.)51 b(The)28 b(graph)f(sho)n(ws)h