2 %%Creator: vivaldi.ms.uky.edu:raphael (Raphael Finkel,POT959,7 6743,2660206)
3 %%Title: stdin (ditroff)
4 %%CreationDate: Wed Oct 14 11:38:59 1992
6 % Start of psdit.pro -- prolog for ditroff translator
7 % Copyright (c) 1985,1987 Adobe Systems Incorporated. All Rights Reserved.
8 % GOVERNMENT END USERS: See Notice file in TranScript library directory
9 % -- probably /usr/lib/ps/Notice
10 % RCS: $Header: psdit.pro,v 2.2 87/11/17 16:40:42 byron Rel $
11 /$DITroff 140 dict def $DITroff begin
12 /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def
13 /xi {0 72 11 mul translate 72 resolution div dup neg scale 0 0 moveto
14 /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def F
15 /pagesave save def}def
16 /PB{save /psv exch def currentpoint translate
17 resolution 72 div dup neg scale 0 0 moveto}def
19 /m1 matrix def /m2 matrix def /m3 matrix def /oldmat matrix def
20 /tan{dup sin exch cos div}bind def
21 /point{resolution 72 div mul}bind def
22 /dround {transform round exch round exch itransform}bind def
23 /xT{/devname exch def}def
24 /xr{/mh exch def /my exch def /resolution exch def}def
26 /xs{docsave restore end}def
28 /xf{/fontname exch def /slotno exch def fontnames slotno get fontname eq not
29 {fonts slotno fontname findfont put fontnames slotno fontname put}if}def
30 /xH{/fontheight exch def F}bind def
31 /xS{/fontslant exch def F}bind def
32 /s{/fontsize exch def /fontheight fontsize def F}bind def
33 /f{/fontnum exch def F}bind def
34 /F{fontheight 0 le {/fontheight fontsize def}if
35 fonts fontnum get fontsize point 0 0 fontheight point neg 0 0 m1 astore
36 fontslant 0 ne{1 0 fontslant tan 1 0 0 m2 astore m3 concatmatrix}if
37 makefont setfont .04 fontsize point mul 0 dround pop
38 %raphael.ms.uky.edu 7/89: changed 'setlinewidth' to pop right here:
40 /X{exch currentpoint exch pop moveto show}bind def
41 /N{3 1 roll moveto show}bind def
42 /Y{exch currentpoint pop exch moveto show}bind def
44 /ditpush{}def/ditpop{}def
45 /AX{3 -1 roll currentpoint exch pop moveto 0 exch ashow}bind def
46 /AN{4 2 roll moveto 0 exch ashow}bind def
47 /AY{3 -1 roll currentpoint pop exch moveto 0 exch ashow}bind def
48 /AS{0 exch ashow}bind def
49 /MX{currentpoint exch pop moveto}bind def
50 /MY{currentpoint pop exch moveto}bind def
52 /cb{pop}def % action on unknown char -- nothing for now
54 /p{pop showpage pagesave restore /pagesave save def}def
55 /abspoint{currentpoint exch pop add exch currentpoint pop add exch}def
56 /dstroke{currentpoint stroke moveto}bind def
57 /Dl{2 copy gsave rlineto stroke grestore rmoveto}bind def
58 /arcellipse{oldmat currentmatrix pop
59 currentpoint translate 1 diamv diamh div scale /rad diamh 2 div def
60 rad 0 rad -180 180 arc oldmat setmatrix}def
61 /Dc{gsave dup /diamv exch def /diamh exch def arcellipse dstroke
62 grestore diamh 0 rmoveto}def
63 /De{gsave /diamv exch def /diamh exch def arcellipse dstroke
64 grestore diamh 0 rmoveto}def
65 /Da{currentpoint /by exch def /bx exch def /fy exch def /fx exch def
66 /cy exch def /cx exch def /rad cx cx mul cy cy mul add sqrt def
67 /ang1 cy neg cx neg atan def /ang2 fy fx atan def cx bx add cy by add
68 2 copy rad ang1 ang2 arcn stroke exch fx add exch fy add moveto}def
69 /Barray 200 array def % 200 values in a wiggle
71 /D~~{counttomark Barray exch 0 exch getinterval astore /Bcontrol exch def pop
72 /Blen Bcontrol length def Blen 4 ge Blen 2 mod 0 eq and
73 {Bcontrol 0 get Bcontrol 1 get abspoint /Ycont exch def /Xcont exch def
74 Bcontrol 0 2 copy get 2 mul put Bcontrol 1 2 copy get 2 mul put
75 Bcontrol Blen 2 sub 2 copy get 2 mul put
76 Bcontrol Blen 1 sub 2 copy get 2 mul put
77 /Ybi /Xbi currentpoint 3 1 roll def def 0 2 Blen 4 sub
79 Bcontrol i get 3 div Bcontrol i 1 add get 3 div
80 Bcontrol i get 3 mul Bcontrol i 2 add get add 6 div
81 Bcontrol i 1 add get 3 mul Bcontrol i 3 add get add 6 div
82 /Xbi Xcont Bcontrol i 2 add get 2 div add def
83 /Ybi Ycont Bcontrol i 3 add get 2 div add def
84 /Xcont Xcont Bcontrol i 2 add get add def
85 /Ycont Ycont Bcontrol i 3 add get add def
86 Xbi currentpoint pop sub Ybi currentpoint exch pop sub rcurveto
89 /ditstart{$DITroff begin
90 /nfonts 60 def % NFONTS makedev/ditroff dependent!
91 /fonts[nfonts{0}repeat]def
92 /fontnames[nfonts{()}repeat]def
97 /oc {/pswid exch def /cc exch def /name exch def
98 /ditwid pswid fontsize mul resolution mul 72000 div def
99 /ditsiz fontsize resolution mul 72 div def
100 ocprocs name known{ocprocs name get exec}{name cb}
102 /fractm [.65 0 0 .6 0 0] def
104 {/fden exch def /fnum exch def gsave /cf currentfont def
105 cf fractm makefont setfont 0 .3 dm 2 copy neg rmoveto
106 fnum show rmoveto currentfont cf setfont(\244)show setfont fden show
107 grestore ditwid 0 rmoveto} def
108 /oce {grestore ditwid 0 rmoveto}def
110 /ocprocs 50 dict def ocprocs begin
111 (14){(1)(4)fraction}def
112 (12){(1)(2)fraction}def
113 (34){(3)(4)fraction}def
114 (13){(1)(3)fraction}def
115 (23){(2)(3)fraction}def
116 (18){(1)(8)fraction}def
117 (38){(3)(8)fraction}def
118 (58){(5)(8)fraction}def
119 (78){(7)(8)fraction}def
120 (sr){gsave .05 dm .16 dm rmoveto(\326)show oce}def
121 (is){gsave 0 .15 dm rmoveto(\362)show oce}def
122 (->){gsave 0 .02 dm rmoveto(\256)show oce}def
123 (<-){gsave 0 .02 dm rmoveto(\254)show oce}def
124 (==){gsave 0 .05 dm rmoveto(\272)show oce}def
126 % DIThacks fonts for some special chars
129 /FontName /DIThacks def
130 /FontMatrix [.001 0.0 0.0 .001 0.0 0.0] def
131 /FontBBox [-220 -280 900 900] def% a lie but ...
132 /Encoding 256 array def
133 0 1 255{Encoding exch /.notdef put}for
135 dup 8#040/space put %space
136 dup 8#110/rc put %right ceil
137 dup 8#111/lt put %left top curl
138 dup 8#112/bv put %bold vert
139 dup 8#113/lk put %left mid curl
140 dup 8#114/lb put %left bot curl
141 dup 8#115/rt put %right top curl
142 dup 8#116/rk put %right mid curl
143 dup 8#117/rb put %right bot curl
144 dup 8#120/rf put %right floor
145 dup 8#121/lf put %left floor
146 dup 8#122/lc put %left ceil
147 dup 8#140/sq put %square
148 dup 8#141/bx put %box
149 dup 8#142/ci put %circle
150 dup 8#143/br put %box rule
151 dup 8#144/rn put %root extender
152 dup 8#145/vr put %vertical rule
153 dup 8#146/ob put %outline bullet
154 dup 8#147/bu put %bullet
155 dup 8#150/ru put %rule
156 dup 8#151/ul put %underline
160 /cc exch def /fd exch def
161 /charname fd /Encoding get cc get def
162 /charwid fd /Metrics get charname get def
163 /charproc fd /CharProcs get charname get def
164 charwid 0 fd /FontBBox get aload pop setcachedevice
166 newpath 0 0 moveto gsave charproc grestore
168 /BuildChar load 0 DITfd put
170 /CharProcs 50 dict def
175 /rn{0 750 moveto 500 0 rls}def
176 /vr{20 800 moveto 0 -770 rls}def
177 /bv{20 800 moveto 0 -1000 rls}def
178 /br{20 770 moveto 0 -1040 rls}def
179 /ul{0 -250 moveto 500 0 rls}def
180 /ob{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath stroke}def
181 /bu{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath fill}def
182 /sq{80 0 rmoveto currentpoint dround newpath moveto
183 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath stroke}def
184 /bx{80 0 rmoveto currentpoint dround newpath moveto
185 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath fill}def
186 /ci{355 333 rmoveto currentpoint newpath 333 0 360 arc
187 50 setlinewidth stroke}def
189 /lt{20 -200 moveto 0 550 rlineto currx 800 2cx s4 add exch s4 a4p stroke}def
190 /lb{20 800 moveto 0 -550 rlineto currx -200 2cx s4 add exch s4 a4p stroke}def
191 /rt{20 -200 moveto 0 550 rlineto currx 800 2cx s4 sub exch s4 a4p stroke}def
192 /rb{20 800 moveto 0 -500 rlineto currx -200 2cx s4 sub exch s4 a4p stroke}def
193 /lk{20 800 moveto 20 300 -280 300 s4 arcto pop pop 1000 sub
194 currentpoint stroke moveto
195 20 300 4 2 roll s4 a4p 20 -200 lineto stroke}def
196 /rk{20 800 moveto 20 300 320 300 s4 arcto pop pop 1000 sub
197 currentpoint stroke moveto
198 20 300 4 2 roll s4 a4p 20 -200 lineto stroke}def
199 /lf{20 800 moveto 0 -1000 rlineto s4 0 rls}def
200 /rf{20 800 moveto 0 -1000 rlineto s4 neg 0 rls}def
201 /lc{20 -200 moveto 0 1000 rlineto s4 0 rls}def
202 /rc{20 -200 moveto 0 1000 rlineto s4 neg 0 rls}def
205 /Metrics 50 dict def Metrics begin
232 /s2 500 def /s4 250 def /s3 333 def
233 /a4p{arcto pop pop pop pop}def
235 /rls{rlineto stroke}def
236 /currx{currentpoint pop}def
237 /dround{transform round exch round exch itransform} def
240 /DIThacks exch definefont pop
241 %raphael.ms.uky.edu 7/89: for splines from gremlin: next 3 lines
244 /Dgl{lineto currentpoint stroke grestore moveto}def
249 2(Times-Italic)xf 2 f
251 4(Times-BoldItalic)xf 4 f
253 6(Helvetica-Bold)xf 6 f
255 8(Courier-Bold)xf 8 f
287 1606 1572(Department)N
291 1812 1689(University)N
294 1725 1806(Lexington,)N
304 1271 0.2404(experimentally)AX
317 2550 0.1979(principal-variation)AX
380 2381 0.2784(intelligence)AX
439 1633(simultaneously)X
597 2164(implementation)X
650 3523(tree-traversal)X
660 3063(branch-and-bound)X
663 576 1137(implemented)N
666 1345(multicomputer.)X
687 576 1353(message-passing)N
705 2325 0.2548(implementation)AX
728 576 1677(multiprocessor.)N
772 576 2142(information)N
796 1349(nonhomogeneous)X
835 576 2715(processors.)N
850 576 2823(\(represented)N
915 576 3288(unassigned)N
990 576 3861(unassigned)N
1025 576 4077(representation)N
1039 576 4185(representation\);)N
1085 1655(subdividing\),)X
1099 576 4617(searching,)N
1171 2516(``heartbeats'')X
1197 2500(\257exibility)X
1299 1610(game-speci\256c,)X
1336 576 1212(mandatory)N
1339 1463 0.1979(principal-variation)AX
1393 2455(combinations,)X
1403 1668 0.2050(implementation-independent)AX
1480 1709(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)X
1482 1442 3045(ef\256ciency)N
1494 2053(hhhhhhhhhhhhhhhhhhhhhhh)X
1512 576 3393(ef\256ciency)N
1525 576 3501(explained)N
1538 3236(communication)X
1549 2280(communicating)X
1582 3287(computation\).)X
1584 576 3933(relationship)N
1586 1411(communication)X
1644 1984(isoef\256ciency)X
1662 2857(ef\256ciency.)X
1675 2957(depth-\256rst)X
1693 576 4959(ef\256ciency.)N
1694 776 5100(Steinberg)N
1748 706 5565(un\256nished)N
1800 3056(simultaneously,)X
1839 576 1449(ef\256ciently.)N
1842 1494(corresponding)X
1905 2814(game-speci\256c)X
1908 576 1881(Alpha-beta)N
2077 576 3126(evaluated,)N
2193 776 3807(Following)N
2205 576 3915(algorithm,)N
2336 2413(integer\):integer;)X
2349 1152 3479(determine)N
2378 1663(\(StaticValue\(z\)\))X
2599 896 780(alphabeta\()N
2655 2795(\(straightforward)X
2656 3453 0.2321(tree-evaluation)AX
2657 576 1137(algorithm)N
2924 576 3417(precisely)N
3089 809(simultaneously.)X
3175 2586(worst-\256rst)X
3441 2580(worst-\256rst)X
3501 3278(tree-splitting.)X
3506 1246(tree-splitting)X
3526 1412(tree-splitting)X
3760 2464(tree-splitting)X
3765 576 5607(orderings)N
3770 1734(Worst-\256rst)X
4078 776 3297(Best-\256rst)N
4099 1121 3561(negamax\()N
4131 1508(tree-splitting)X
4157 950(tree-splitting)X
4196 978 -0.1979(Principal-variation)AX
4208 2168(tree-splitting)X
4365 576 5679(evaluating)N
4409 1892 0.2404(experimentally)AX
4445 576 1104(processor)N
4456 2938(tree-splitting)X
4478 1337(tree-splitting)X
4519 2715 0.2548(implementation)AX
4539 576 2097(evaluated,)N
4572 576 2313(Therefore)N
4627 3013(grandchildren)X
4657 2737(re-evaluation)X
4678 1368 0.2548(implementation)AX
4683 2687(grandchildren)X
4696 3076(grandchildren)X
4703 1657(grandchildren)X
4737 3143(sequentially.)X
4805 706 4281(algorithms.)N
4895 776 4962(Steinberg)N
4940 1435 5478(relative)N
4949 2364 5424(relative)N
4953 2252(hhhhhhhhhhhhhhhhhhh)X
4986 1585 789(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)N
4988 576 1023(Experiments)N
5002 576 1131(algorithm)N
5006 1559(suf\256ciently)X
5036 1574(ef\256ciencies)X
5123 576 2232(Evaluation)N
5151 576 2448(variation)N
5165 1228(DelaySplit\(z)X
5195 2048([1..MAXWIDTH])X
5211 1983(\(alphabeta\(z,)X
5226 1472 3252(determine)N
5251 1676(-DelaySplit\()X
5312 1760 3804(value[i])N
5314 2336(-DelaySplit\()X
5338 1760 3900(begincrit)N
5469 2985(worst-\256rst)X
5501 576 5556(\(Relative)N
5527 576 5772(algorithms)N
5555 1703(ef\256ciency,)X
5570 1772(respectively,)X
5588 2454 0.2723(parallelization)AX
5593 576 1104(structure)N
5613 576 1353(different)N
5693 3125 3292(alphabeta)N
5832 3135 2585(delaysplit)N
5891 [64 32 32 32] 0 setdash
6208 3118 1810(alphabeta)N
6278 3128 3038(delaysplit)N
6335 [64 32 32 32] 0 setdash
6348 3196 1093(TreeSplit10)N
6548 [64 32 32 32] 0 setdash
6653 1746(ef\256ciency,)X
6662 576 4716(processors)N
6757 3159 2702(alphabeta)N
6884 [64 32 32 32] 0 setdash
6897 3169 3122(delaysplit)N
6967 3068 2562(TreeSplit10)N
7322 3369(applications,)X
7324 576 5254(tic-tac-toe)N
7503 1935(signi\256cant)X
7602 2442(applications.)X
7621 3628(ef\256ciency,)X
7739 2527 4242(MWF\(EC-sorting\))N
7809 2541 3533(MWF\(NoSorting\))N
7977 2541 861(MWF\(NoSorting\))N
8047 2527 1266(MWF\(EC-sorting\))N
8120 2370 2164(SortTime\(EC-sorting\))N
8270 2527 4033(MWF\(EC-sorting\))N
8340 2541 3364(MWF\(NoSorting\))N
8525 1398(Unfortunately,)X
8531 2860(implementation)X
8575 576 1893(evaluated.)N
8628 1543(\(sequential\))X
8686 1007(ef\256ciency.)X
8754 2457 4358(MWF\(TT-sorting\))N
8824 2449 2871(MWF\(EC-sorting\))N
8897 2206 4115(SortTime\(EC-sorting\))N
8968 2337 4712(SortTime\(TT-sorting\))N
9150 2449 1348(MWF\(EC-sorting\))N
9220 2457 2669(MWF\(TT-sorting\))N
9450 576 4570(splitting)N
9483 3264(communication)X
9513 576 5143(demonstrated)N
9529 576 5251(improvement)N
9616 2428 1286(TotalTime\(DMWF\))N
9689 2446 2458(SortTime\(DMWF\))N
9759 2383 893(TotalTime\(MWF\))N
9826 2481 2089(SortTime\(MWF\))N
10124 576 474(Game-tree)N
10344 1868(Ef\256ciency)X
10376 2888(tic-tac-toe,)X
10380 576 3469(parameter)N
10407 2719(tic-tac-toe.)X
10414 576 474(Game-tree)N
10489 2349 1624(TotalTime\(DMWF\))N
10562 2367 2652(SortTime\(DMWF\))N
10632 2383 883(TotalTime\(MWF\))N
10699 2402 2559(SortTime\(MWF\))N
11021 576 474(Game-tree)N
11241 1868(Ef\256ciency)X
11261 2841(ef\256ciency)X
11300 1776(tic-tac-toe,)X
11314 2108(contributing)X
11329 2735(26-processor)X
11332 576 5240(machine.)N
11342 2782(multicomputer)X
11371 576 5597(practice,)N
11388 576 474(Game-tree)N
11393 576 780(References)N
11406 3049 0.2356(Implementation)AX
11409 776 1029(tracking,'')N
11412 1469(Transactions)X
11466 3244(Algorithms,'')X
11475 3258(Wisconsin-Madison)X
11476 776 1884(\(1981\).)N
11491 3689(Arti\256cial)X
11492 776 2133(Intelligence)N
11513 776 2382 0.2356(Implementation)AN
11519 2514(Algorithm,'')X
11525 3637(\(2\)\(March)X
11535 2034(``Parallelism)X
11540 3452(Arti\256cial)X
11562 776 2988(Trees,'')N