acm-final.ps

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

(and)f(that)g(entry)g(has)h(a)-75 1476 y(value)i(suf)o(\256cient)g(for)
f(a)i(cutof)o(f?)17 b(Conventional)9 b(implementations)-75
1522 y(will)g(miss)h(this)g(cheap)h(cutof)o(f.)-33 1574
y(The)20 b(Enhanced)g(T)o(ransposition)d(Cutof)o(f)h(\(ETC\))i
(attempts)f(to)-75 1620 y(maximize)f(the)g(bene\256ts)f(of)g(the)h
(transposition)d(table)i(by)g(doing)-75 1665 y(additional)11
b(lookups.)20 b(By)12 b(looking)f(up)h Fo(all)g Fq(successors)h(of)g(a)
g(node)-75 1711 y(in)i(the)h(table,)i(additional)c(transpositions)g(to)
h(other)g(parts)h(of)g(the)-75 1757 y(tree)e(can)h(be)f(detected.)27
b(In)14 b(particular)n(,)h(if)e(one)h(of)g(these)g(lookups)-75
1802 y(produces)i(a)g(value)g(suf)o(\256cient)f(for)g(a)i(cutof)o(f,)g
(the)e(search)i(can)f(be)-75 1848 y(stopped)10 b(at)g(this)g(node.)16
b(For)10 b(chess,)i(experiments)f(show)f(that)g(ETC)-75
1893 y(can)h(reduce)g(the)f(search)i(tree)e(by)g(28\045.)-33
1946 y(The)f(bene\256ts)f(of)h(these)g(enhancements)g(are)h(not)d
(independent)h(of)-75 1991 y(each)j(other)n(.)j(Experimental)c(results)
f(shows)h(that)f(the)h(combination)-75 2037 y(of)15 b(MTD\()p
Fl(\246)p Fq(\))f(and)h(ETC)g(results)g(in)f(a)h(35\045)f(reduction)g
(over)h(con-)-75 2083 y(ventional)f(aspiration)f(window)h(NegaScout.)30
b(Given)15 b(that)f(some)-75 2128 y(researchers)f(have)e(speculated)g
(that)g(there)g(is)f(little)f(of)i(interest)f(left)-75
2174 y(to)17 b(explore)f(in)h(sequential)f(\256xed-depth)h(Alpha-Beta)f
(searching)-75 2220 y([25)o(],)g(the)d(magnitude)h(of)f(the)h
(improvement)g(is)g(both)f(signi\256cant)-75 2265 y(and)d(surprising.)
-75 2390 y Fr(2)50 b(Curr)o(ent)12 b(State)f(of)h(the)g(Art)-75
2472 y Fq(There)i(are)g(two)e(popular)g(criteria)h(for)f(assessing)i
(the)f(search)h(ef)o(\256-)-75 2517 y(ciency:)g(the)9
b(quality)e(of)h(move)i(ordering)d(and)i(the)g(closeness)g(of)g(the)-75
2563 y(search)14 b(tree)f(to)g(the)f(theoretical)h(minimal)f(tree.)23
b(T)m(o)14 b(give)e(an)h(idea)-75 2609 y(of)j(the)h(state-of-the-art,)g
(we)g(present)g(measurements)h(for)e(these)-75 2654 y(two)8
b(criteria)h(for)f(a)i(tournament)e(quality)f(chess)j(program,)f
(Phoenix)-75 2700 y([24)o(].)1035 686 y @beginspecial
50 @llx 50 @lly 410 @urx 302 @ury 2352 @rwi @setspecial
%%BeginDocument: plot.mv.ord.ps
/gnudict 40 dict def
gnudict begin
/Color false def
/gnulinewidth 5.000 def
/vshift -66 def
/dl {10 mul} def
/hpt 31.5 def
/vpt 31.5 def
/vpt2 vpt 2 mul def
/hpt2 hpt 2 mul def
/Lshow { currentpoint stroke moveto
  0 vshift rmoveto show } def
/Rshow { currentpoint stroke moveto
  dup stringwidth pop neg vshift rmoveto show } def
/Cshow { currentpoint stroke moveto
  dup stringwidth pop -2 div vshift rmoveto show } def
/DL { Color {setrgbcolor [] 0 setdash pop}
 {pop pop pop 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
/M {moveto} def
/L {lineto} def
/P { stroke [] 0 setdash
  currentlinewidth 2 div sub moveto
  0 currentlinewidth rlineto  stroke } def
/D { stroke [] 0 setdash  2 copy  vpt add moveto
  hpt neg vpt neg rlineto  hpt vpt neg rlineto
  hpt vpt rlineto  hpt neg vpt rlineto  closepath  stroke
  P  } def
/A { stroke [] 0 setdash  vpt sub moveto  0 vpt2 rlineto
  currentpoint stroke moveto
  hpt neg vpt neg rmoveto  hpt2 0 rlineto stroke
  } def
/B { stroke [] 0 setdash  2 copy  exch hpt sub exch vpt add moveto
  0 vpt2 neg rlineto  hpt2 0 rlineto  0 vpt2 rlineto
  hpt2 neg 0 rlineto  closepath  stroke
  P  } def
/C { stroke [] 0 setdash  exch hpt sub exch vpt add moveto
  hpt2 vpt2 neg rlineto  currentpoint  stroke  moveto
  hpt2 neg 0 rmoveto  hpt2 vpt2 rlineto stroke  } def
/T { stroke [] 0 setdash  2 copy  vpt 1.12 mul add moveto
  hpt neg vpt -1.62 mul rlineto
  hpt 2 mul 0 rlineto
  hpt neg vpt 1.62 mul rlineto  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
1440 701 M
1440 4539 L
LTb
1440 701 M
1503 701 L
6897 701 M
6834 701 L
1320 701 M
(80) Rshow
1440 1661 M
1503 1661 L
6897 1661 M
6834 1661 L
1320 1661 M
(85) Rshow
1440 2620 M
1503 2620 L
6897 2620 M
6834 2620 L
1320 2620 M
(90) Rshow
1440 3580 M
1503 3580 L
6897 3580 M
6834 3580 L
1320 3580 M
(95) Rshow
1440 4539 M
1503 4539 L
6897 4539 M
6834 4539 L
1320 4539 M
(100) Rshow
1440 701 M
1440 764 L
1440 4539 M
1440 4476 L
1440 501 M
(0) Cshow
2046 701 M
2046 764 L
2046 4539 M
2046 4476 L
2046 501 M
(1) Cshow
2653 701 M
2653 764 L
2653 4539 M
2653 4476 L
2653 501 M
(2) Cshow
3259 701 M
3259 764 L
3259 4539 M
3259 4476 L
3259 501 M
(3) Cshow
3865 701 M
3865 764 L
3865 4539 M
3865 4476 L
3865 501 M
(4) Cshow
4472 701 M
4472 764 L
4472 4539 M
4472 4476 L
4472 501 M
(5) Cshow
5078 701 M
5078 764 L
5078 4539 M
5078 4476 L
5078 501 M
(6) Cshow
5684 701 M
5684 764 L
5684 4539 M
5684 4476 L
5684 501 M
(7) Cshow
6291 701 M
6291 764 L
6291 4539 M
6291 4476 L
6291 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
(% Success \(CUT Nodes\)) Cshow
grestore
4168 301 M
(Depth) Cshow
4168 4739 M
(Move Ordering in Last Iteration) Cshow
LT0
LT0
2410 1085 M
(Phoenix) Rshow
2530 1085 M
2890 1085 L
2046 3771 M
2046 3771 L
2653 3004 L
3259 3963 L
3865 3388 L
4472 3771 L
5078 3196 L
5684 3196 L
6291 2620 L
2650 1085 D
2046 3771 D
2653 3004 D
3259 3963 D
3865 3388 D
4472 3771 D
5078 3196 D
5684 3196 D
6291 2620 D
stroke
grestore
end
showpage
%%EndDocument
 @endspecial 1141 773 a(Figure)h(1:)k(Quality)9 b(of)h(Move)h(Ordering)
e(by)h(Depth)1035 1527 y @beginspecial 50 @llx 50 @lly
410 @urx 302 @ury 2352 @rwi @setspecial
%%BeginDocument: plot.nsmg.ps
/gnudict 40 dict def
gnudict begin
/Color false def
/gnulinewidth 5.000 def
/vshift -66 def
/dl {10 mul} def
/hpt 31.5 def
/vpt 31.5 def
/vpt2 vpt 2 mul def
/hpt2 hpt 2 mul def
/Lshow { currentpoint stroke moveto
  0 vshift rmoveto show } def
/Rshow { currentpoint stroke moveto
  dup stringwidth pop neg vshift rmoveto show } def
/Cshow { currentpoint stroke moveto
  dup stringwidth pop -2 div vshift rmoveto show } def
/DL { Color {setrgbcolor [] 0 setdash pop}
 {pop pop pop 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
/M {moveto} def
/L {lineto} def
/P { stroke [] 0 setdash
  currentlinewidth 2 div sub moveto
  0 currentlinewidth rlineto  stroke } def
/D { stroke [] 0 setdash  2 copy  vpt add moveto
  hpt neg vpt neg rlineto  hpt vpt neg rlineto
  hpt vpt rlineto  hpt neg vpt rlineto  closepath  stroke
  P  } def
/A { stroke [] 0 setdash  vpt sub moveto  0 vpt2 rlineto
  currentpoint stroke moveto
  hpt neg vpt neg rmoveto  hpt2 0 rlineto stroke
  } def
/B { stroke [] 0 setdash  2 copy  exch hpt sub exch vpt add moveto
  0 vpt2 neg rlineto  hpt2 0 rlineto  0 vpt2 rlineto
  hpt2 neg 0 rlineto  closepath  stroke
  P  } def
/C { stroke [] 0 setdash  exch hpt sub exch vpt add moveto
  hpt2 vpt2 neg rlineto  currentpoint  stroke  moveto
  hpt2 neg 0 rmoveto  hpt2 vpt2 rlineto stroke  } def
/T { stroke [] 0 setdash  2 copy  vpt 1.12 mul add moveto
  hpt neg vpt -1.62 mul rlineto
  hpt 2 mul 0 rlineto
  hpt neg vpt 1.62 mul rlineto  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
1440 1153 M
1503 1153 L
6897 1153 M
6834 1153 L
1320 1153 M
(1 : 1) Rshow
1440 2281 M
1503 2281 L
6897 2281 M
6834 2281 L
1320 2281 M
(1.5 : 1) Rshow
1440 3410 M
1503 3410 L
6897 3410 M
6834 3410 L
1320 3410 M
(2.0 : 1) Rshow
1440 4539 M
1503 4539 L
6897 4539 M
6834 4539 L
1320 4539 M
(2.5 : 1) Rshow
1440 701 M
1440 764 L
1440 4539 M
1440 4476 L
1440 501 M
(2) Cshow
2220 701 M
2220 764 L
2220 4539 M
2220 4476 L
2220 501 M
(3) Cshow
2999 701 M
2999 764 L
2999 4539 M
2999 4476 L