acm-final.ps

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

2999 501 M
(4) Cshow
3779 701 M
3779 764 L
3779 4539 M
3779 4476 L
3779 501 M
(5) Cshow
4558 701 M
4558 764 L
4558 4539 M
4558 4476 L
4558 501 M
(6) Cshow
5338 701 M
5338 764 L
5338 4539 M
5338 4476 L
5338 501 M
(7) Cshow
6117 701 M
6117 764 L
6117 4539 M
6117 4476 L
6117 501 M
(8) Cshow
6897 701 M
6897 764 L
6897 4539 M
6897 4476 L
6897 501 M
(9) Cshow
LTb
1440 701 M
6897 701 L
6897 4539 L
1440 4539 L
1440 701 L
200 2620 M
currentpoint gsave translate 90 rotate 0 0 moveto
(Total nodes Last Iteration Relative to MG \(%\)) Cshow
grestore
4168 301 M
(Depth) Cshow
4168 4739 M
(AspNS vs MG) Cshow
LT0
LT0
6234 4276 M
(MG) Rshow
6354 4276 M
6714 4276 L
1440 1153 M
1440 1153 L
2220 1153 L
2999 1153 L
3779 1153 L
4558 1153 L
5338 1153 L
6117 1153 L
6897 1153 L
6897 1153 L
LT1
6234 4076 M
(Phoenix) Rshow
6354 4076 M
6714 4076 L
2220 1785 M
2220 1785 L
2999 3388 L
3779 2010 L
4558 3749 L
5338 2056 L
6117 3546 L
6474 4076 D
2220 1785 D
2999 3388 D
3779 2010 D
4558 3749 D
5338 2056 D
6117 3546 D
stroke
grestore
end
showpage
%%EndDocument
 @endspecial 1127 1614 a(Figure)g(2:)k(Ef)o(\256ciency)e(Relative)d(to)
h(Minimal)f(Graph)1025 1757 y Fk(2.1)45 b(Quality)11
b(of)g(Move)g(Ordering)1025 1828 y Fq(Considerable)f(research)j(ef)o
(fort)e(has)h(been)g(devoted)f(to)g(improving)1025 1874
y(the)h(move)i(ordering,)e(so)h(that)g(cutof)o(fs)f(will)g(be)h(found)f
(as)i(soon)e(as)1025 1919 y(possible)f(\(for)h(example,)j(the)d
(history)f(heuristic,)i(killer)f(heuristic,)1025 1965
y(iterative)i(deepening)h(and)g(transposition)e(tables)i([25)o(]\).)30
b(Ideally)m(,)1025 2011 y(only)8 b(one)i(move)g(should)f(be)h
(considered)g(at)g(nodes)g(where)g(a)h(cutof)o(f)1025
2056 y(is)f(expected.)1066 2106 y(Figure)d(1)g(shows)h(how)f(often)g
(the)g(\256rst)h(move)g(considered)f(caused)1025 2152
y(a)13 b(cutof)o(f)g(at)g(nodes)g(where)h(a)g(cutof)o(f)e(occurred)i
(\(note)e(the)i(vertical)1025 2198 y(scale\).)40 b(The)19
b(algorithm)e(used)i(is)f(NegaScout)h(enhanced)g(with)1025
2243 y(iterative)8 b(deepening,)i(transposition)d(tables,)j(aspiration)
e(windows)1025 2289 y(and)g(the)g(history)f(heuristic.)13
b(The)c(data)g(points)e(were)i(averaged)g(over)1025 2335
y(twenty)d(test)h(positions.)12 b(The)c(quality)d(of)i(move)h(ordering)
e(of)g(the)h(last)1025 2380 y(ply)j(is)g(shown.)17 b(For)10
b(nodes)h(that)f(have)i(been)f(searched)h(deeply)m(,)g(we)1025
2426 y(see)6 b(a)g(success)g(ra)q(te)g(of)g(over)g(90\26195\045,)j(in)d
(line)g(with)g(results)g(reported)1025 2472 y(by)13 b(others)g([9].)25
b(Since)14 b(the)g(searches)h(used)f(iterative)f(deepening,)1025
2517 y(all)e(but)g(the)h(deepest)g(nodes)g(bene\256ted)g(from)g(the)g
(presence)h(of)e(the)1025 2563 y(best)e(move)h(of)f(the)g(previous)g
(iteration)f(in)h(the)g(transposition)e(table.)1025 2609
y(Near)12 b(the)g(leaf)g(nodes,)g(the)g(quality)e(of)h(move)h(ordering)
f(decreases)1025 2654 y(to)k(roughly)f(90\045.)30 b(Here)17
b(the)e(program)h(does)g(not)f(bene\256t)g(from)1025
2700 y(the)j(transposition)e(table)i(and)h(has)g(to)f(rely)g(on)g(move)
h(ordering)p eop
%%Page: 3 3
3 2 bop -75 42 a Fq(heuristics.)28 b(Unfortunately)m(,)15
b(the)f(majority)g(of)g(the)h(nodes)g(in)f(the)-75 87
y(search)d(tree)f(are)h(at)f(the)g(deepest)g(levels.)15
b(Thus,)c(there)f(is)g(still)e(some)-75 133 y(room)i(for)g
(improvement.)-33 178 y(A)i(phenomenon)g(visible)f(in)h(the)g(\256gure)
h(is)f(an)h(odd/even)e(oscil-)-75 224 y(lation.)k(At)10
b(even)h(levels)g(in)f(the)g(tree,)i(the)e(move)h(ordering)f(appears)
-75 270 y(to)h(be)g(less)h(ef)o(fective)g(than)f(at)h(odd)e(levels.)19
b(This)11 b(is)g(caused)i(by)e(the)-75 315 y(asymmetric)k(nature)f(of)g
(the)g(search)i(tree,)f(where)g(nodes)f(along)g(a)-75
361 y(line)g(alternate)h(between)h(those)e(with)g(cutof)o(fs)h(\(one)g
(child)f(exam-)-75 407 y(ined\))8 b(and)h(those)g(where)g(all)g
(children)f(must)h(be)g(examined.)15 b(This)9 b(is)-75
452 y(clearly)g(illustrated)e(by)i(the)g(formula)f(for)h(the)f(minimal)
h(search)h(tree,)-75 502 y Fo(w)-47 487 y Fj(b)p Fi(d)q
Fh(/)p Fg(2)p Fj(c)33 502 y Fq(+)h Fo(w)95 487 y Fj(d)p
Fi(d)q Fh(/)p Fg(2)p Fj(e)174 502 y Fm(\000)g Fq(1)i(leaf)h(nodes)f
(\(assuming)g(\256xed)g(width)f Fo(w)h Fq(and)-75 548
y(depth)f Fo(d)q Fq(\),)g(whose)h(growth)e(ratio)g(depends)h(on)g
(whether)g Fo(d)h Fq(is)f(even)-75 594 y(or)e(odd.)-33
639 y(The)g(evidence)g(suggests)f(that)g(the)g(research)i(on)e
(move-ordering)-75 685 y(techniques)h(for)g(Alpha-Beta)f(search)j(has)f
(been)f(very)g(successful.)-75 762 y Fk(2.2)45 b(The)12
b(Minimal)f(T)m(r)o(ee)-75 817 y Fq(In)e(a)i(seminal)e(paper)h(in)f
(1975,)h(Knuth)e(and)i(Moore)f(introduced)g(the)-75 863
y(notion)j(of)i(the)f(minimal)g(tree)i([12)o(].)26 b(Any)13
b(algorithm)f(that)i(wants)-75 908 y(to)i(\256nd)g(the)h(minimax)f
(value)g(has)h(to)f(search)i(at)f(least)f(this)g(tree.)-75
954 y(For)f(actual)g(games,)j(where)d(the)g(game)h(tree)f(is)g
(nonuniform,)g(the)-75 1000 y(minimal)e(tree)h(is)f(usually)g(taken)g
(to)g(be)h(Alpha-Beta')n(s)f(best-case.)-75 1045 y(Ebeling)k(describes)
g(a)h(procedure)g(to)e(compute)i(the)f(size)h(of)f(the)-75
1091 y(search)11 b(tree)g(in)f(relation)f(to)h(Alpha-Beta')n(s)f
(best-case)i([8].)-33 1137 y(The)d(minimal)f(tree)i(has)f(been)g(used)g
(by)g(many)g(authors)f(as)i(a)f(yard-)-75 1182 y(stick)j(to)g(compare)h
(the)f(performance)i(of)e(their)f(search)j(algorithms)-75
1228 y(in)h(practice.)29 b(For)14 b(example,)j(in)d(chess,)j
Fo(Belle)e Fq(is)f(reported)g(to)g(be)-75 1274 y(within)g(a)i(factor)f
(of)h(2.2)f(of)g(the)h(minimal)f(Alpha-Beta)g(tree)h([8)o(],)-75
1319 y Fo(Phoenix)d Fq(within)f(1.4)h(\(measured)i(in)d(1985\))h([24)o
(],)h Fo(Hitech)f Fq(within)-75 1365 y(1.5)c([8])g(and)h
Fo(Zugzwang)e Fq(within)g(1.2)h([9].)14 b(Using)9 b(Ebeling')n(s)f
(proce-)-75 1411 y(dure,)i(we)g(measured)h(the)f(performance)g(of)g
(the)f(current)h(version)f(of)-75 1456 y(Phoenix.)14
b(The)8 b(results)f(of)g(the)g(comparison)h(of)f(NegaScout)h(against)
-75 1502 y(this)k(minimal)g(tree)i(are)f(shown)g(in)f(\256gure)h(2)f
(\(based)i(on)e(all)h(nodes)-75 1548 y(searched)i(in)e(the)g(last)g
(iteration\).)23 b(The)14 b(\256gure)f(con\256rms)h(that)f(the)-75
1593 y(program)d(can)h(search)g(close)g(to)f(the)g(minimal)g(tree.)-33
1639 y(An)j(interesting)g(feature)h(is)g(that)f(Phoenix)g(has)i(a)f
(signi\256cantly)-75 1685 y(worse)d(performance)h(for)f(even)h(depths.)
17 b(The)12 b(reason)f(for)g(this)f(can)-75 1730 y(be)j(found)e(in)h
(the)h(structure)f(of)g(the)g(minimal)g(tree.)23 b(This)12
b(leads)h(to)-75 1776 y(an)e(important)f(point:)15 b(reporting)9
b(the)i(ef)o(\256ciency)h(of)f(a)g(\256xed-depth)-75
1822 y(search)j(algorithm)d(based)j(on)f(odd-ply)e(data)i(is)g
(misleading.)22 b(The)-75 1867 y(odd-ply)14 b(iterations)g(give)h(an)h
(in\257ated)f(view)h(of)f(the)g(search)i(ef)o(\256-)-75
1913 y(ciency;)10 b(even-ply)g(data)g(is)g(more)h(representative)f(of)g
(real)h(program)-75 1959 y(performance.)33 b(In)15 b(light)f(of)i
(this,)g(the)g Fo(Hitech)g Fq(result)f(of)g(1.5)h(for)-75
2004 y(8-ply)9 b(searches)j(seems)g(even)f(more)f(impressive)g([8].)-75
2098 y Fr(3)50 b(Impr)o(ovements)-75 2157 y Fq(The)14
b(measurements)h(of)e(the)g(previous)g(section)g(indicate)g(that)g(the)
-75 2203 y(search)c(ef)o(\256ciency)h(of)e(Alpha-Beta)g(is)g(at)g(a)h
(high)e(level.)15 b(W)m(e)9 b(present)-75 2248 y(three)15
b(new)h(Alpha-Beta)f(enhancements)i(to)d(further)h(narrow)g(the)-75
2294 y(gap)f(between)h(trees)g(built)d(in)i(practice)g(and)h(the)f
(minimal)f(search)-75 2340 y(tree.)-75 2417 y Fk(3.1)45
b(Best-First)12 b(versus)f(Depth-First?)-75 2472 y Fq(Alpha-Beta)g
(does)h(a)h(rigid)d(depth-\256rst,)h(left-to-right)e(traversal)j(of)-75
2517 y(the)h(tree.)23 b(In)12 b(contrast,)i(the)e(best-\256rst)h
(approach)g(of)f(SSS*)h(seems)-75 2563 y(more)d(appealing.)k(It)9
b(was)g(proven)g(that)f(SSS*)i(will)d(never)j(examine)-75
2609 y(more)16 b(nodes)f(than)h(Alpha-Beta)f([5)o(,)h(28],)h(and)f
(numerous)f(simu-)-75 2654 y(lations)c(showed)i(it)f(to)f(build)g
(signi\256cantly)g(smaller)i(trees)g(\(recent)-75 2700
y(publications)8 b(include)i([3)o(,)h(7,)g(10)o(,)g(11,)f(23]\).)1083
50 y Ff(function)f Fs(AB-SSS*\()p Fe(n)p Fs(\))h Fd(\256)h(\246)p
Fs(;)1141 91 y Fe(g)f Fs(:=)h(+)p Fd(\245)p Fs(;)1141
133 y Ff(r)o(epeat)1199 174 y Fc(b)j Fs(:=)d Fe(g)p Fs(;)1199
216 y Fe(g)f Fs(:=)g(Alpha-Beta-with-TT\()p Fe(n)p Fd(,)d
Fc(b)12 b Fb(\000)c Fs(1)p Fd(,)f Fc(b)s Fs(\);)1141
257 y Ff(until)j Fe(g)g Fs(=)h Fc(b)s Fs(;)1141 299 y
Ff(r)o(eturn)d Fe(g)p Fs(;)1025 407 y Fq(Figure)j(3:)16
b(SSS*)c(as)g(a)g(Sequence)h(of)e(Alpha-Beta)g(Searches)i(with)1025
452 y(a)d(T)o(ransposition)f(T)m(able)1066 583 y(Despite)k(the)h
(encouraging)e(results,)i(SSS*)g(has)g(been)g(shunned)1025
628 y(in)9 b(practice)i(because)h(of)e(a)g(number)h(of)f(perceived)g
(drawbacks:)1070 689 y Fl(\267)21 b Fq(It)11 b(is)g(a)h(complex)g
(algorithm)f(that)g(is)g(dif)o(\256cult)g(to)g(understand)1108
735 y(or)k(adapt.)32 b(The)17 b(algorithm)d(is)i(formulated)f(as)i(an)f
(implicit)1108 780 y(\256nite-state)g(machine)h(with)f(six)h
(ingeniously)d(interlocking)1108 826 y(state-space)i(operators)e(that)g
(manipulates)h(a)g(sorted)g(OPEN)1108 872 y(list.)1070
933 y Fl(\267)21 b Fq(It)16 b(is)h(slow)m(,)j(because)e(of)f(the)g
(overhead)h(of)f(maintaining)f(a)1108 979 y(sorted)9
b(OPEN)i(list.)1070 1040 y Fl(\267)21 b Fq(It)10 b(has)i(memory)g
(requirements)f(that)g(are)h(exponential)e(in)h(the)1108
1086 y(search)e(depth.)14 b(It)8 b(is)h(widely)e(believed)i(that)f
(this)f(makes)j(SSS*)1108 1132 y(unsuitable)f(for)g(practical)i(use.)
1066 1192 y(This)23 b(unsatisfactory)g(state)g(of)g(af)o(fairs)h(has)g
(left)e(many)i(re-)1025 1238 y(searchers)6 b(in)g(the)g(\256eld)g(with)
g(a)g(nagging)g(feeling.)14 b(Although)6 b(Alpha-)1025
1283 y(Beta-based)14 b(programs)g(achieve)h(good)e(results,)i(it)e
(could)g(be)i(that)1025 1329 y(depth-\256rst)e(strategies)i(are)g
(missing)f(out)g(on)g(some)h(fundamental)1025 1375 y(notion,)8
b(and)j(that)e(best-\256rst)h(is)g(a)h(better)f(way)m(.)1698
1360 y Fg(1)1025 1445 y Fp(Alpha-Beta)f(Goes)i(Best-First)1025
1494 y Fq(The)i(idea)g(of)g(minimal)f(window)g(search)i(can)f(be)h
(taken)f(to)f(its)g(ex-)1025 1539 y(treme:)i(perform)9
b(all)g(Alpha-Beta)g(searches)i(with)d(a)i(minimal)f(win-)1025
1585 y(dow)m(.)15 b(Since)10 b(the)f(result)h(of)f(a)h(minimal)g
(window)e(search)j(is)f(a)g(lower)1025 1631 y(or)i(upper)g(bound)g(on)g
(the)h(true)f(value,)i(a)f(series)g(of)g(searches)h(must)1025
1676 y(be)9 b(conducted)f(to)h(conver)o(ge)g(on)g(the)g(value.)14
b(Doing)8 b(extra)h(searches)1025 1722 y(sounds)k(expensive,)i(but)e(a)
h(cache)h(\(the)f(transposition)d(table\))i(can)1025
1767 y(be)d(used)h(to)e(prevent)h(unnecessary)h(re-searching.)1066
1813 y(Figure)17 b(3)g(shows)h(one)f(instance)h(of)f
(minimal-windows-only)1025 1859 y(search.)23 b(Start)13
b(with)e(+)p Fl(\245)i Fq(as)h(an)f(upper)f(bound)g(on)h(the)f(search)i
(and)1025 1904 y(then)f(repeatedly)g(decrease)j(it)d(until)f(the)h
(true)g(value)h(is)f(found.)25 b(It)1025 1950 y(has)15
b(been)i(formally)d(proven)h(that)g(this)g(code,)i(called)f(AB-SSS*,)
1025 1996 y(expands)c(the)f(same)j(leaf)e(nodes)g(as)g(SSS*)g([17)o(,)h
(20)o(,)g(21)o(].)20 b(Surpris-)1025 2041 y(ingly)m(,)10
b(a)i(best-\256rst)f(algorithm)f(can)i(be)f(reformulated)g(as)h(a)g
(special)1025 2087 y(case)f(of)f(a)h(depth-\256rst)e(algorithm.)1066
2133 y(Other)j(conver)o(gence)h(schemes)h(are)f(possible.)20
b(Starting)11 b(with)g(a)1025 2178 y(lower)d(bound)f(of)h
Fm(\000)p Fl(\245)h Fq(and)f(re\256ning)g(it)g(upward)g(yields)g(the)g
(DUAL*)1025 2224 y(algorithm)15 b(\(AB-DUAL*\))h([15)o(,)h(22].)34
b(Another)16 b(idea)h(is)g(to)f(use)1025 2270 y(the)f(bounds)g(that)h
(are)h(returned)e(by)h(Alpha-Beta)f(in)h(a)g(bisection)1025
2315 y(scheme,)c(yielding)c(the)i(C*)g(algorithm)f([6].)1066
2361 y(Instead)k(of)g(starting)e(with)h(an)h(extreme)h(initial)d
(value,)j(one)f(can)1025 2407 y(use)19 b(a)g(heuristic)f(value)h(to)g
(\252guess\272)h(at)f(an)g(initial)e(bound,)j(and)1025
2452 y(then)10 b(conver)o(ge)h(either)g(upward)g(or)f(downward)g
(towards)h(the)g(min-)1025 2498 y(imax)k(value,)h(depending)e(on)h
(whether)g(the)f(bound)g(was)i(a)f(lower)p 1025 2532
250 2 v 1077 2560 a Fa(1)1092 2575 y Fs(There)e(is)i(potential)f(for)h
(confusion)e(between)g(algorithms)h(such)f(as)1025 2617
y(SSS*,)5 b(which)h(are)g(principally)g(\256xed-depth)g(b)o
(est-\256rst)g(minimax)g(se)o(arche)o(s,)1025 2658 y(and)11
b(a)i(very)f(dif)o(ferent,)j(variable-depth,)e(best-\256rst)g(minimax)g
(algorithm)1025 2700 y(by)8 b(Korf)i(and)e(Chickering)h([14].)p
eop
%%Page: 4 4
4 3 bop -87 579 a @beginspecial 50 @llx 50 @lly 410 @urx
302 @ury 1984 @rwi @setspecial
%%BeginDocument: plot.1.p.a.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
LTb
1200 829 M
63 0 V
5634 0 R
-63 0 V
-5754 0 R
(1 : 1.15) Rshow
1200 1168 M