acm-final.ps

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

-5754 0 R
(1 : 1.15) Rshow
1200 1531 M
63 0 V
5634 0 R
-63 0 V
-5754 0 R
(1 : 1.12) Rshow
1200 2069 M
63 0 V
5634 0 R
-63 0 V
-5754 0 R
(1 : 1.09) Rshow
1200 2621 M
63 0 V
5634 0 R
-63 0 V
-5754 0 R
(1 : 1.06) Rshow
1200 3190 M
63 0 V
5634 0 R
-63 0 V
-5754 0 R
(1 : 1.03) Rshow
1200 3774 M
63 0 V
5634 0 R
-63 0 V
-5754 0 R
(1 : 1) Rshow
1200 4359 M
63 0 V
5634 0 R
-63 0 V
-5754 0 R
(1.03 : 1) Rshow
1200 501 M
0 63 V
0 4175 R
0 -63 V
0 -4375 R
(3) Cshow
2150 501 M
0 63 V
0 4175 R
0 -63 V
0 -4375 R
(4) Cshow
3099 501 M
0 63 V
0 4175 R
0 -63 V
0 -4375 R
(5) Cshow
4049 501 M
0 63 V
0 4175 R
0 -63 V
0 -4375 R
(6) Cshow
4998 501 M
0 63 V
0 4175 R
0 -63 V
0 -4375 R
(7) Cshow
5948 501 M
0 63 V
0 4175 R
0 -63 V
0 -4375 R
(8) Cshow
6897 501 M
0 63 V
0 4175 R
0 -63 V
0 -4375 R
(9) 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
(CPU time ID-MTD\(f\) Relative to AspNS \(%\)) Cshow
grestore
4048 101 M
(Depth) Cshow
4048 4939 M
(Chess) Cshow
LT0
6234 4476 M
(AspNS time/leaves) Rshow
6354 4476 M
360 0 V
1200 3774 M
950 0 V
949 0 V
950 0 V
949 0 V
950 0 V
949 0 V
LT1
6234 4276 M
(MTD\(f\) time) Rshow
6354 4276 M
360 0 V
2150 2125 M
949 -217 V
4049 791 L
949 899 V
950 -445 V
6474 4276 D
2150 2125 D
3099 1908 D
4049 791 D
4998 1690 D
5948 1245 D
LT5
6234 4076 M
(MTD\(f\) leaves) Rshow
6354 4076 M
360 0 V
2150 2338 M
949 212 V
4049 1019 L
949 1106 V
950 -435 V
6474 4076 A
2150 2338 A
3099 2550 A
4049 1019 A
4998 2125 A
5948 1690 A
stroke
grestore
end
showpage
%%EndDocument
 @endspecial 1255 678 a(Figure)e(5:)15 b(Execution)9
b(T)o(ime)i(Chess)1025 817 y(world.)1066 866 y(Second,)j(MTD\()p
Fl(\246)p Fq(\))f(performs)g(better)f(than)h(all)f(other)g(tested)h
(al-)1025 912 y(gorithms.)28 b(The)15 b(intuition)d(that)i(starting)g
(close)h(to)g(the)f(minimax)1025 957 y(value)c(is)g(ef)o(\256cient)h
(has)f(been)h(experimentally)e(justi\256ed.)1066 1006
y(Third,)g(the)h(depth-\256rst)e(Aspiration)g(NegaScout)i(algorithm)e
(can)1025 1052 y(outperform)13 b(the)i(best-\256rst)f(SSS*)g
(algorithm.)28 b(NegaScout)15 b(uses)1025 1097 y(minimal-window)5
b(search,)k(like)d(our)h(reformulation)e(of)i(SSS*.)14
b(Us-)1025 1143 y(ing)9 b(a)i(non-optimal)e(start)h(value)h(of)f(+)p
Fl(\245)h Fq(leaves)g(room)g(for)f(SSS*)h(to)1025 1189
y(be)f(outperformed.)1066 1237 y(Fourth,)e(a)h(word)f(of)g(caution.)14
b(Since)9 b(the)f(tested)h(algorithms)e(per)o(-)1025
1283 y(form)13 b(quite)h(close)g(together)n(,)h(the)f(relative)f(dif)o
(ferences)i(are)g(quite)1025 1329 y(sensitive)e(to)h(variations)f(in)h
(input)e(parameters,)17 b(such)e(as)g(charac-)1025 1374
y(teristics)d(of)g(test)h(positions.)21 b(In)13 b(generalizing)f(these)
i(results,)f(one)1025 1420 y(should)8 b(keep)i(this)e(sensitivity)f(in)
i(mind.)14 b(Using)9 b(these)h(numbers)f(as)1025 1466
y(absolute)i(predictors)g(for)g(other)h(situations)e(would)h(not)g(do)h
(justice)1025 1511 y(to)c(the)h(complexities)f(of)h(real-life)g(game)h
(trees.)15 b(The)10 b(experimental)1025 1557 y(data)f(is)f(better)h
(suited)f(to)h(provide)f(insight)f(on,)i(or)g(guide)f(and)h(verify)1025
1603 y(hypotheses)g(about)h(these)h(complexities.)1066
1651 y(Other)g(results)g(borne)g(out)g(by)g(experiments)g(are)h(that)f
(the)g(mem-)1025 1697 y(ory)i(requirements)i(of)f(all)g(algorithms)f
(are)i(perfectly)f(acceptable)1025 1743 y(for)c(typical)h(tournament)f
(play)m(,)i(since)g(only)e(a)i(small)f(subset)g(of)g(the)1025
1788 y(visited)j(nodes)i(\(the)g(solution)e(tree\))i(has)g(to)g(be)g
(stored)g(in)f(mem-)1025 1834 y(ory)m(.)23 b(This)13
b(means)h(that)f(the)f(widely)h(held)f(belief)h(that)f(SSS*)i(uses)1025
1880 y(inordinate)8 b(amounts)i(of)g(memory)h(is)f(not)f(correct)i([19)
o(].)1025 1959 y Fp(SSS*:)j(A)d(Footnote)f(in)g(the)h(Game-T)m(r)o(ee)g
(Sear)o(ch)h(Literatur)o(e?)1025 2015 y Fq(For)e(many)g(years,)i(SSS*)f
(has)f(cast)i(doubt)d(on)h(the)g(ef)o(fectiveness)h(of)1025
2061 y(depth-\256rst)d(minimax)h(strategies,)h(because)h(a)f(number)g
(of)f(publica-)1025 2107 y(tions)g(showed)j(that)e(best-\256rst)h
(strategies)g(had)g(the)g(potential)e(to)i(be)1025 2152
y(better)n(.)j(W)m(e)d(show)e(that)h(best-\256rst)f(can)i(be)g
(reformulated)e(as)i(depth-)1025 2198 y(\256rst)d(plus)g(memory)m(.)16
b(This)9 b(reformulation)e(led)i(us)g(to)f(the)h(following)1025
2244 y(conclusions,)g(dispelling)f(a)j(number)f(of)g(myths:)1070
2312 y Fl(\267)21 b Fq(The)7 b(A*-like)g(OPEN)g(list-based)g(formulati)
o(on)g(of)f(SSS*)h(is)g(u)o(n-)1108 2358 y(clear)h(and)g(inef)o
(\256cient.)14 b(The)9 b(AB-SSS*)f(reformulation)e(using)1108
2403 y(a)k(recursive)h(depth-\256rst)e(procedure)i(and)f(a)h
(transposition)d(ta-)1108 2449 y(ble)j(shows)h(more)g(clearly)f(how)h
(the)f(algorithm)f(traverses)j(its)1108 2495 y(trees,)e(and)f(is)g
(easily)g(and)h(ef)o(\256ciently)f(implemented.)1070
2563 y Fl(\267)21 b Fq(SSS*)c(is)h(not)f(\252better)r(\272)h(than)f
(Alpha-Beta)h(\(contradicting,)1108 2609 y(for)c(example,)j([23)o(,)f
(28)o(]\).)29 b(It)14 b(is)h(a)g(special)h(case)g(of)f(Alpha-)1108
2654 y(Beta.)35 b(Other)17 b(variants)f(of)h(Alpha-Beta)g(outperform)f
(AB-)1108 2700 y(SSS*.)f(Thus,)c(the)f(claim)h(should)e(be)i(the)f
(other)g(way)g(around:)p eop
%%Page: 5 5
5 4 bop 219 413 a @beginspecial 0 @llx 0 @lly 128 @urx
139 @ury 992 @rwi 992 @rhi @setspecial
%%BeginDocument: etc.eps
/$F2psDict 200 dict def 
$F2psDict begin
$F2psDict /mtrx matrix put
/l {lineto} bind def
/m {moveto} bind def
/s {stroke} bind def
/n {newpath} bind def
/gs {gsave} bind def
/gr {grestore} bind def
/clp {closepath} bind def
/graycol {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul
4 -2 roll mul setrgbcolor} bind def
/col-1 {} def
/col0 {0 0 0 setrgbcolor} bind def
/col1 {0 0 1 setrgbcolor} bind def
/col2 {0 1 0 setrgbcolor} bind def
/col3 {0 1 1 setrgbcolor} bind def
/col4 {1 0 0 setrgbcolor} bind def
/col5 {1 0 1 setrgbcolor} bind def
/col6 {1 1 0 setrgbcolor} bind def
/col7 {1 1 1 setrgbcolor} bind def
/col8 {.68 .85 .9 setrgbcolor} bind def
/col9 {0 .39 0 setrgbcolor} bind def
/col10 {.65 .17 .17 setrgbcolor} bind def
/col11 {1 .51 0 setrgbcolor} bind def
/col12 {.63 .13 .94 setrgbcolor} bind def
/col13 {1 .75 .8 setrgbcolor} bind def
/col14 {.7 .13 .13 setrgbcolor} bind def
/col15 {1 .84 0 setrgbcolor} bind def
 /DrawEllipse {
	/endangle exch def
	/startangle exch def
	/yrad exch def
	/xrad exch def
	/y exch def
	/x exch def
	/savematrix mtrx currentmatrix def
	x y translate xrad yrad scale 0 0 1 startangle endangle arc
	savematrix setmatrix
	} def

	end
/$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def
/$F2psEnd {$F2psEnteredState restore end} def

$F2psBegin
0 setlinecap 0 setlinejoin
-90.0 175.0 translate 0.900 -0.900 scale
0.500 setlinewidth
% Ellipse
n 129 99 11 11 0 360 DrawEllipse gs col-1 s gr
% Ellipse
n 209 99 11 11 0 360 DrawEllipse gs col-1 s gr
% Polyline
n 179 59 m 179 39 l  159 39 l  159 59 l  clp gs col-1 s gr
% Polyline
n 164 59 m 134 89 l gs col-1 s gr
% Polyline
n 174 59 m 204 89 l gs col-1 s gr
% Polyline
n 134 109 m 149 139 l  139 159 l  159 159 l  149 139 l gs col-1 s gr
% Polyline
n 204 109 m 189 139 l  159 179 l  219 179 l  189 139 l gs col-1 s gr
% Polyline
n 124 109 m 109 139 l  99 159 l  99 159 l  119 159 l  109 139 l gs col-1 s gr
% Polyline
n 214 109 m 229 139 l gs col-1 s gr
	[4.000000] 0 setdash
% Interpolated spline
n 229 139 m
	227.461 145.134 226.211 147.634 224 149 curveto
	220.045 151.444 212.737 150.548 209 149 curveto
	200.191 145.351 192.809 127.649 184 124 curveto
	177.771 121.420 165.456 120.545 159 124 curveto
	155.508 125.869 153.008 129.619 149 139 curveto
gs col-1 s gr
	[] 0 setdash
/Times-Roman findfont 12.00 scalefont setfont
139 174 m 
gs 1 -1 scale (A) col-1 show gr
/Times-Roman findfont 12.00 scalefont setfont
234 149 m 
gs 1 -1 scale (C) col-1 show gr
/Times-Roman findfont 12.00 scalefont setfont
184 194 m 
gs 1 -1 scale (B) col-1 show gr
/Times-Roman findfont 12.00 scalefont setfont
204 104 m 
gs 1 -1 scale (N) col-1 show gr
$F2psEnd
%%EndDocument
 @endspecial 83 501 a Fq(Figure)10 b(6:)k(Enhanced)d(T)o(ransposition)d
(Cutof)o(f)8 636 y(Alpha-Beta-based)g(algorithms)f(are)h(better)g(than)
g(SSS*,)h(both)8 681 y(in)h(clarity)f(and)h(performance.)-30
745 y Fl(\267)21 b Fq(Best-\256rst)g(algorithms)f(such)i(as)g(MTD\()p
Fl(\246)p Fq(\),)i(DUAL*)e(and)8 791 y(SSS*)10 b(do)g(not)g(need)g(too)
g(much)h(memory)f(in)g(practice.)-30 855 y Fl(\267)21
b Fq(There)11 b(are)g(many)g(application-independent)c(enhancements)8
900 y(to)g(Alpha-Beta.)14 b(Ignoring)6 b(them)i(in)f(simulated)h
(performance)8 946 y(assessments)k(leads)f(to)e(incorrect)h(results.)
-30 1010 y Fl(\267)21 b Fq(The)c(boundary)e(between)h(best-\256rst)f
(and)h(depth-\256rst)f(algo-)8 1056 y(rithms)7 b(in)g(minimax)h(search)
h(is)f(fuzzy)m(.)15 b(If)7 b(best-\256rst)h(is)f(outper)o(-)8
1101 y(formed)12 b(by)g(depth-\256rst,)g(and)h(if)f(best-\256rst)f(can)
i(be)g(reformu-)8 1147 y(lated)d(as)h(a)g(special)f(case)i(of)e
(depth-\256rst,)g(perhaps)g(we)h(should)8 1193 y(look)c(for)g(a)h(dif)o
(ferent)f(criterion)f(to)h(classify)h(search)g(strategies.)8
1238 y(Interestingly)m(,)f(the)g(literature)f(on)h(single-agent)f
(search)j(shows)8 1284 y(this)h(conver)o(gence)j(of)e(depth-\256rst)f
(and)h(best-\256rst)g(too,)g(IDA*)8 1330 y([13)o(])g(being)e(the)h
(best)h(known)e(example.)-30 1393 y Fl(\267)21 b Fq(MTD\()p
Fl(\246)p Fq(\))14 b(performs)g(better)f(than)h(the)g(current)f
(algorithm)g(of)8 1439 y(choice)j(by)f(chess)i(programmers,)g(and)f(is)
f(just)g(as)h(easy)g(\(or)8 1485 y(hard\))10 b(to)g(implement.)-75
1549 y(In)i(light)e(of)i(this,)g(we)g(believe)h(that)e(SSS*)h(should)f
(now)h(become)h(a)-75 1594 y(footnote)c(in)g(the)i(history)d(of)i
(game-tree)i(search.)-75 1680 y Fk(3.2)45 b(Effective)12
b(Use)f(of)h(T)m(ranspositions)-75 1740 y Fq(T)o(ransposition)6
b(tables)g(are)g(one)g(of)g(the)g(Alpha-Beta)g(enhancements.)-75
1786 y(Normally)m(,)11 b(transpositions)d(are)k(checked)f(at)g(each)h
(visit)d(to)h(a)h(node.)-75 1832 y(If)c(no)g(transpositi)o(on)f(table)h
(cut)o(of)o(f)f(occurs,)g(then)h(the)g(best)g(move)g(sug-)-75
1877 y(gested)h(by)g(the)f(table)h(is)g(expanded)g(depth-\256rst,)f
(before)h(its)f(brothers)-75 1923 y(are)12 b(considered.)18
b(A)12 b(simple)f(and)g(relatively)f(cheap)i(enhancement)-75
1969 y(to)7 b(improve)g(search)h(ef)o(\256ciency)h(is)e(to)g(try)f(and)
i(make)g(more)g(ef)o(fective)-75 2014 y(use)j(of)f(the)g(transposition)
e(table.)15 b(Consider)9 b(interior)g(node)h Fo(N)i Fq(with)-75
2060 y(children)d Fo(B)i Fq(and)f Fo(C)f Fq(\(\256gure)h(6\).)15
b(The)10 b(transposition)e(table)i(suggests)-75 2106
y(move)e Fo(B)g Fq(and)g(as)h(long)d(as)j(it)e(produces)h(a)g(cutof)o
(f,)g(move)g Fo(C)g Fq(will)e(never)-75 2151 y(be)14
b(explored.)24 b(However)n(,)16 b(node)d Fo(C)h Fq(might)e(transpose)i
(into)e(a)i(part)-75 2197 y(of)e(the)h(tree,)h(node)f
Fo(A)p Fq(,)h(that)e(has)h(already)g(been)h(analyzed)f(and)g(can)-75
2243 y(potentially)d(produce)j(an)g(immediate)g(cutof)o(f.)22
b(Before)12 b(doing)g(any)-75 2288 y(search)h(at)e(an)h(interior)e
(node,)i(a)g(quick)f(check)h(of)f(all)g(the)h(positions)-75
2334 y(arising)g(from)h(this)f(node)h(\(nodes)g Fo(B)g
Fq(and)g Fo(C)p Fq(\))g(in)f(the)h(transposition)-75
2380 y(table)g(may)h(result)e(in)h(\256nding)f(a)i(cutof)o(f.)23
b(W)m(e)14 b(call)f(this)f(technique)-75 2425 y Fo(Enhanced)h(T)n
(ransposition)c(Cutoffs)p Fq(,)j(ETC.)h(It)f(performs)g(transpo-)-75
2471 y(sition)e(table