diff options
Diffstat (limited to 'parallel/214-92.ps')
| -rwxr-xr-x | parallel/214-92.ps | 11579 |
1 files changed, 11579 insertions, 0 deletions
diff --git a/parallel/214-92.ps b/parallel/214-92.ps new file mode 100755 index 0000000..23b1a28 --- /dev/null +++ b/parallel/214-92.ps @@ -0,0 +1,11579 @@ +%!PS-Adobe-1.0 +%%Creator: vivaldi.ms.uky.edu:raphael (Raphael Finkel,POT959,7 6743,2660206) +%%Title: stdin (ditroff) +%%CreationDate: Wed Oct 14 11:38:59 1992 +%%EndComments +% Start of psdit.pro -- prolog for ditroff translator +% Copyright (c) 1985,1987 Adobe Systems Incorporated. All Rights Reserved. +% GOVERNMENT END USERS: See Notice file in TranScript library directory +% -- probably /usr/lib/ps/Notice +% RCS: $Header: psdit.pro,v 2.2 87/11/17 16:40:42 byron Rel $ +/$DITroff 140 dict def $DITroff begin +/fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def +/xi {0 72 11 mul translate 72 resolution div dup neg scale 0 0 moveto + /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def F + /pagesave save def}def +/PB{save /psv exch def currentpoint translate + resolution 72 div dup neg scale 0 0 moveto}def +/PE{psv restore}def +/m1 matrix def /m2 matrix def /m3 matrix def /oldmat matrix def +/tan{dup sin exch cos div}bind def +/point{resolution 72 div mul}bind def +/dround {transform round exch round exch itransform}bind def +/xT{/devname exch def}def +/xr{/mh exch def /my exch def /resolution exch def}def +/xp{}def +/xs{docsave restore end}def +/xt{}def +/xf{/fontname exch def /slotno exch def fontnames slotno get fontname eq not + {fonts slotno fontname findfont put fontnames slotno fontname put}if}def +/xH{/fontheight exch def F}bind def +/xS{/fontslant exch def F}bind def +/s{/fontsize exch def /fontheight fontsize def F}bind def +/f{/fontnum exch def F}bind def +/F{fontheight 0 le {/fontheight fontsize def}if + fonts fontnum get fontsize point 0 0 fontheight point neg 0 0 m1 astore + fontslant 0 ne{1 0 fontslant tan 1 0 0 m2 astore m3 concatmatrix}if + makefont setfont .04 fontsize point mul 0 dround pop +%raphael.ms.uky.edu 7/89: changed 'setlinewidth' to pop right here: + pop}bind def +/X{exch currentpoint exch pop moveto show}bind def +/N{3 1 roll moveto show}bind def +/Y{exch currentpoint pop exch moveto show}bind def +/S /show load def +/ditpush{}def/ditpop{}def +/AX{3 -1 roll currentpoint exch pop moveto 0 exch ashow}bind def +/AN{4 2 roll moveto 0 exch ashow}bind def +/AY{3 -1 roll currentpoint pop exch moveto 0 exch ashow}bind def +/AS{0 exch ashow}bind def +/MX{currentpoint exch pop moveto}bind def +/MY{currentpoint pop exch moveto}bind def +/MXY /moveto load def +/cb{pop}def % action on unknown char -- nothing for now +/n{}def/w{}def +/p{pop showpage pagesave restore /pagesave save def}def +/abspoint{currentpoint exch pop add exch currentpoint pop add exch}def +/dstroke{currentpoint stroke moveto}bind def +/Dl{2 copy gsave rlineto stroke grestore rmoveto}bind def +/arcellipse{oldmat currentmatrix pop + currentpoint translate 1 diamv diamh div scale /rad diamh 2 div def + rad 0 rad -180 180 arc oldmat setmatrix}def +/Dc{gsave dup /diamv exch def /diamh exch def arcellipse dstroke + grestore diamh 0 rmoveto}def +/De{gsave /diamv exch def /diamh exch def arcellipse dstroke + grestore diamh 0 rmoveto}def +/Da{currentpoint /by exch def /bx exch def /fy exch def /fx exch def + /cy exch def /cx exch def /rad cx cx mul cy cy mul add sqrt def + /ang1 cy neg cx neg atan def /ang2 fy fx atan def cx bx add cy by add + 2 copy rad ang1 ang2 arcn stroke exch fx add exch fy add moveto}def +/Barray 200 array def % 200 values in a wiggle +/D~{mark}def +/D~~{counttomark Barray exch 0 exch getinterval astore /Bcontrol exch def pop + /Blen Bcontrol length def Blen 4 ge Blen 2 mod 0 eq and + {Bcontrol 0 get Bcontrol 1 get abspoint /Ycont exch def /Xcont exch def + Bcontrol 0 2 copy get 2 mul put Bcontrol 1 2 copy get 2 mul put + Bcontrol Blen 2 sub 2 copy get 2 mul put + Bcontrol Blen 1 sub 2 copy get 2 mul put + /Ybi /Xbi currentpoint 3 1 roll def def 0 2 Blen 4 sub + {/i exch def + Bcontrol i get 3 div Bcontrol i 1 add get 3 div + Bcontrol i get 3 mul Bcontrol i 2 add get add 6 div + Bcontrol i 1 add get 3 mul Bcontrol i 3 add get add 6 div + /Xbi Xcont Bcontrol i 2 add get 2 div add def + /Ybi Ycont Bcontrol i 3 add get 2 div add def + /Xcont Xcont Bcontrol i 2 add get add def + /Ycont Ycont Bcontrol i 3 add get add def + Xbi currentpoint pop sub Ybi currentpoint exch pop sub rcurveto + }for dstroke}if}def +end +/ditstart{$DITroff begin + /nfonts 60 def % NFONTS makedev/ditroff dependent! + /fonts[nfonts{0}repeat]def + /fontnames[nfonts{()}repeat]def +/docsave save def +}def + +% character outcalls +/oc {/pswid exch def /cc exch def /name exch def + /ditwid pswid fontsize mul resolution mul 72000 div def + /ditsiz fontsize resolution mul 72 div def + ocprocs name known{ocprocs name get exec}{name cb} + ifelse}def +/fractm [.65 0 0 .6 0 0] def +/fraction + {/fden exch def /fnum exch def gsave /cf currentfont def + cf fractm makefont setfont 0 .3 dm 2 copy neg rmoveto + fnum show rmoveto currentfont cf setfont(\244)show setfont fden show + grestore ditwid 0 rmoveto} def +/oce {grestore ditwid 0 rmoveto}def +/dm {ditsiz mul}def +/ocprocs 50 dict def ocprocs begin +(14){(1)(4)fraction}def +(12){(1)(2)fraction}def +(34){(3)(4)fraction}def +(13){(1)(3)fraction}def +(23){(2)(3)fraction}def +(18){(1)(8)fraction}def +(38){(3)(8)fraction}def +(58){(5)(8)fraction}def +(78){(7)(8)fraction}def +(sr){gsave .05 dm .16 dm rmoveto(\326)show oce}def +(is){gsave 0 .15 dm rmoveto(\362)show oce}def +(->){gsave 0 .02 dm rmoveto(\256)show oce}def +(<-){gsave 0 .02 dm rmoveto(\254)show oce}def +(==){gsave 0 .05 dm rmoveto(\272)show oce}def +end +% DIThacks fonts for some special chars +50 dict dup begin +/FontType 3 def +/FontName /DIThacks def +/FontMatrix [.001 0.0 0.0 .001 0.0 0.0] def +/FontBBox [-220 -280 900 900] def% a lie but ... +/Encoding 256 array def +0 1 255{Encoding exch /.notdef put}for +Encoding + dup 8#040/space put %space + dup 8#110/rc put %right ceil + dup 8#111/lt put %left top curl + dup 8#112/bv put %bold vert + dup 8#113/lk put %left mid curl + dup 8#114/lb put %left bot curl + dup 8#115/rt put %right top curl + dup 8#116/rk put %right mid curl + dup 8#117/rb put %right bot curl + dup 8#120/rf put %right floor + dup 8#121/lf put %left floor + dup 8#122/lc put %left ceil + dup 8#140/sq put %square + dup 8#141/bx put %box + dup 8#142/ci put %circle + dup 8#143/br put %box rule + dup 8#144/rn put %root extender + dup 8#145/vr put %vertical rule + dup 8#146/ob put %outline bullet + dup 8#147/bu put %bullet + dup 8#150/ru put %rule + dup 8#151/ul put %underline + pop +/DITfd 100 dict def +/BuildChar{0 begin + /cc exch def /fd exch def + /charname fd /Encoding get cc get def + /charwid fd /Metrics get charname get def + /charproc fd /CharProcs get charname get def + charwid 0 fd /FontBBox get aload pop setcachedevice + 40 setlinewidth + newpath 0 0 moveto gsave charproc grestore + end}def +/BuildChar load 0 DITfd put +%/UniqueID 5 def +/CharProcs 50 dict def +CharProcs begin +/space{}def +/.notdef{}def +/ru{500 0 rls}def +/rn{0 750 moveto 500 0 rls}def +/vr{20 800 moveto 0 -770 rls}def +/bv{20 800 moveto 0 -1000 rls}def +/br{20 770 moveto 0 -1040 rls}def +/ul{0 -250 moveto 500 0 rls}def +/ob{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath stroke}def +/bu{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath fill}def +/sq{80 0 rmoveto currentpoint dround newpath moveto + 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath stroke}def +/bx{80 0 rmoveto currentpoint dround newpath moveto + 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath fill}def +/ci{355 333 rmoveto currentpoint newpath 333 0 360 arc + 50 setlinewidth stroke}def + +/lt{20 -200 moveto 0 550 rlineto currx 800 2cx s4 add exch s4 a4p stroke}def +/lb{20 800 moveto 0 -550 rlineto currx -200 2cx s4 add exch s4 a4p stroke}def +/rt{20 -200 moveto 0 550 rlineto currx 800 2cx s4 sub exch s4 a4p stroke}def +/rb{20 800 moveto 0 -500 rlineto currx -200 2cx s4 sub exch s4 a4p stroke}def +/lk{20 800 moveto 20 300 -280 300 s4 arcto pop pop 1000 sub + currentpoint stroke moveto + 20 300 4 2 roll s4 a4p 20 -200 lineto stroke}def +/rk{20 800 moveto 20 300 320 300 s4 arcto pop pop 1000 sub + currentpoint stroke moveto + 20 300 4 2 roll s4 a4p 20 -200 lineto stroke}def +/lf{20 800 moveto 0 -1000 rlineto s4 0 rls}def +/rf{20 800 moveto 0 -1000 rlineto s4 neg 0 rls}def +/lc{20 -200 moveto 0 1000 rlineto s4 0 rls}def +/rc{20 -200 moveto 0 1000 rlineto s4 neg 0 rls}def +end + +/Metrics 50 dict def Metrics begin +/.notdef 0 def +/space 500 def +/ru 500 def +/br 0 def +/lt 250 def +/lb 250 def +/rt 250 def +/rb 250 def +/lk 250 def +/rk 250 def +/rc 250 def +/lc 250 def +/rf 250 def +/lf 250 def +/bv 250 def +/ob 350 def +/bu 350 def +/ci 750 def +/bx 750 def +/sq 750 def +/rn 500 def +/ul 500 def +/vr 0 def +end + +DITfd begin +/s2 500 def /s4 250 def /s3 333 def +/a4p{arcto pop pop pop pop}def +/2cx{2 copy exch}def +/rls{rlineto stroke}def +/currx{currentpoint pop}def +/dround{transform round exch round exch itransform} def +end +end +/DIThacks exch definefont pop +%raphael.ms.uky.edu 7/89: for splines from gremlin: next 3 lines +/Dg{gsave}def +/Dgi{rlineto}def +/Dgl{lineto currentpoint stroke grestore moveto}def +ditstart +(psc)xT +576 1 1 xr +1(Times-Roman)xf 1 f +2(Times-Italic)xf 2 f +3(Times-Bold)xf 3 f +4(Times-BoldItalic)xf 4 f +5(Helvetica)xf 5 f +6(Helvetica-Bold)xf 6 f +7(Courier)xf 7 f +8(Courier-Bold)xf 8 f +9(Symbol)xf 9 f +10(DIThacks)xf 10 f +10 s +1 f +xi +%%EndProlog + +%%Page: 1 1 +10 s 0 xH 0 xS 1 f +15 s +867 807(A)N +983(comparison)X +1574(of)X +1704(some)X +1988(parallel)X +2379(game-tree)X +2889(search)X +3225(algorithms)X +1878 942(\(Revised)N +2335(version\))X +14 s +1553 1203(Jaleh)N +1812(Rezaie)X +12 s +2201(\([email protected]\))X +14 s +1482 1329(Raphael)N +1877(Finkel)X +12 s +2247(\([email protected]\))X +13 s +1606 1572(Department)N +2123(of)X +2236(Computer)X +2678(Science)X +1812 1689(University)N +2278(of)X +2391(Kentucky)X +1725 1806(Lexington,)N +2204(KY)X +2380(40506-0027)X +8 f +14 s +576 2127(Abstract)N +1 f +12 s +776 2268(This)N +1002(paper)X +1271 0.2404(experimentally)AX +1905(compares)X +2329(several)X +2658(sequential)X +3105(and)X +3300(parallel)X +3646(game-tree)X +576 2376(search)N +850(methods:)X +1231(alpha-beta,)X +1685(mandatory)X +2125(work)X +2350(\256rst,)X +2550 0.1979(principal-variation)AX +3295(splitting,)X +3662(tree)X +3834(split-)X +576 2484(ting,)N +775(ER,)X +947(and)X +1111(delay)X +1345(splitting.)X +1734(All)X +1882(have)X +2089(been)X +2296(implemented)X +2826(in)X +2927(a)X +2996(common)X +3359(environment)X +3872(pro-)X +576 2592(vided)N +814(by)X +934(the)X +1076(DIB)X +1265(package.)X +8 f +14 s +576 2796(Key)N +844(words:)X +1 f +12 s +1326(game)X +1559(trees,)X +1789(heuristic)X +2145(search,)X +2439(alpha-beta)X +8 f +14 s +576 3000(1.)N +844(Introduction)X +1 f +12 s +776 3141(In)N +892(this)X +1067(paper)X +1318(we)X +1467(compare)X +1836(some)X +2076(of)X +2193(the)X +2348(parallel)X +2675(methods)X +3038(for)X +3187(searching)X +3593(large)X +3823(game)X +576 3249(trees.)N +831(These)X +1086(trees)X +1293(arise)X +1500(in)X +1600(the)X +1743(area)X +1929(of)X +2034(arti\256cial)X +2381 0.2784(intelligence)AX +2857(and)X +3021(are)X +3164(closely)X +3462(related)X +3750(to)X +3850(trees)X +576 3357(searched)N +946(in)X +1054(other)X +1285(application)X +1748(areas.)X +2028(Exhaustive)X +2490(search)X +2770(of)X +2884(a)X +2961(tree)X +3140(is)X +3238(prohibitively)X +3770(expen-)X +576 3465(sive.)N +803(There)X +1052(are)X +1194(several)X +1491(ways)X +1712(to)X +1811(ameliorate)X +2243(the)X +2385(problem.)X +10 f +624 3606(g)N +1 f +706(Search)X +992(only)X +1187(to)X +1286(a)X +1353(given)X +1591(depth.)X +10 f +624 3714(g)N +1 f +706(Apply)X +970(heuristics,)X +1387(such)X +1587(as)X +1691(the)X +1833(alpha-beta)X +2259(method,)X +2596(to)X +2695(cut)X +2837(off)X +2973(fruitless)X +3307(search.)X +10 f +624 3822(g)N +1 f +706(Apply)X +970(many)X +1208(computers)X +1633(simultaneously)X +2240(in)X +2339(pursuing)X +2699(the)X +2841(search.)X +576 3963(We)N +734(concentrate)X +1203(on)X +1323(distributed)X +1759(variants)X +2088(of)X +2192(the)X +2334(alpha-beta)X +2760(heuristic)X +3116(that)X +3285(try)X +3416(to)X +3515(avoid)X +3754(search-)X +576 4071(ing)N +723(unnecessary)X +1217(parts)X +1428(of)X +1532(the)X +1674(tree)X +1843(while)X +2081(keeping)X +2410(many)X +2648(processors)X +3077(fruitfully)X +3449(busy.)X +776 4212(The)N +987(algorithms)X +1460(we)X +1633(compare)X +2026(are)X +2205(alpha-beta,)X +2692(mandatory)X +3165(work)X +3423(\256rst,)X +3657(principal-)X +576 4320(variation)N +947(splitting,)X +1315(tree)X +1488(splitting,)X +1856(ER,)X +2031(and)X +2198(delay)X +2434(splitting.)X +2825(To)X +2959(be)X +3077(able)X +3265(to)X +3367(make)X +3603(a)X +3673(fair)X +3834(com-)X +576 4428(parison)N +884(between)X +1230(the)X +1373(above)X +1628(algorithms,)X +2089(we)X +2226(have)X +2433(extended)X +2806(the)X +2949(DIB)X +3139(package)X +3479([1])X +3617(to)X +3718(use)X +3872(it)X +3952(as)X +576 4536(a)N +643(framework)X +1089(for)X +1225(implementing)X +1785(all)X +1906(the)X +2048(algorithms)X +2484(we)X +2620(compare.)X +776 4677(Section)N +1097(2)X +1177(describes)X +1567(the)X +1717(DIB)X +1914(package.)X +2310(Section)X +2632(3)X +2713(introduces)X +3147(the)X +3298(alpha-beta)X +3733(pruning)X +576 4785(and)N +749(brie\257y)X +1034(describes)X +1426(the)X +1578(algorithms)X +2024(used)X +2234(in)X +2342(the)X +2493(experiment.)X +3008(Section)X +3330(4)X +3411(presents)X +3759(experi-)X +576 4893(mental)N +876(results)X +1164(that)X +1346(compare)X +1716(the)X +1872(algorithms.)X +2370(Section)X +2697(5)X +2783(compares)X +3190(the)X +3346(effects)X +3641(of)X +3759(several)X +576 5001(sorting)N +872(strategies)X +1264(on)X +1388(the)X +1534(above)X +1792(algorithms.)X +2280(Section)X +2597(6)X +2673(illustrates)X +3076(the)X +3222(new)X +3410(results)X +3689(achieved)X +576 5109(by)N +703(adjustments)X +1195(made)X +1436(to)X +1543(MWF)X +1804(algorithm.)X +2259(Section)X +2580(7)X +2660(summarizes)X +3152(the)X +3302(results,)X +3609(and)X +3780(details)X +576 5217(remaining)N +991(parts)X +1202(of)X +1306(this)X +1469(experiment.)X +8 f +14 s +576 5439(2.)N +840(DIB)X +1104(\320)X +1234(A)X +1364(distributed)X +2164(implementation)X +3165(of)X +3362(backtrack-)X +576 5547(ing)N +1 f +12 s +776 5688(In)N +892(this)X +1067(section)X +1376(we)X +1524(describe)X +1881(how)X +2082(DIB)X +2283(works)X +2553(and)X +2728(how)X +2929(we)X +3077(use)X +3241(it)X +3331(to)X +3443(implement)X +3893(dif-)X +576 5796(ferent)N +825(tree-search)X +1272(algorithms.)X + +2 p +%%Page: 2 2 +12 s 0 xH 0 xS 1 f +10 s +3 f +576 474(Game-tree)N +963(search)X +3992(2)X +8 f +14 s +576 780(2.1.)N +978(Description)X +1782(of)X +1983(DIB)X +1 f +12 s +776 921(DIB)N +971(is)X +1065(a)X +1138(multi-purpose)X +1708(package)X +2054(developed)X +2480(by)X +2606(Finkel)X +2882(and)X +3051(Manber)X +3380(for)X +3523(tree-traversal)X +576 1029(problems)N +958([1].)X +1168(It)X +1277(allows)X +1578(applications)X +2094(such)X +2320(as)X +2450(backtrack)X +2875(and)X +3063(branch-and-bound)X +3817(to)X +3941(be)X +576 1137(implemented)N +1122(on)X +1260(a)X +1345(multicomputer.)X +2003(DIB's)X +2279(requirements)X +2824(from)X +3053(the)X +3213(distributed)X +3668(operating)X +576 1245(system)N +886(are)X +1047(minimal.)X +1460(The)X +1653(machines)X +2060(must)X +2289(be)X +2422(connected)X +2855(by)X +2993(a)X +3078(network)X +3435(that)X +3622(supports)X +3989(a)X +576 1353(message-passing)N +1263(mechanism;)X +1770(each)X +1988(machine)X +2356(must)X +2584(be)X +2716(able)X +2918(to)X +3035(communicate,)X +3621(not)X +3786(neces-)X +576 1461(sarily)N +817(directly,)X +1163(with)X +1361(all)X +1485(other)X +1710(machines.)X +2149(Our)X +2325 0.2548(implementation)AX +2958(of)X +3065(DIB)X +3257(is)X +3348(programmed)X +3867(in)X +3968(C)X +576 1569(and)N +741(runs)X +932(in)X +1033(the)X +1177(Unix)X +1395(environment)X +1908(across)X +2174(machines)X +2564(connected)X +2981(by)X +3103(an)X +3220(internet)X +3541(or)X +3647(on)X +3770(a)X +3840(Unix)X +576 1677(multiprocessor.)N +776 1818(The)N +953(application)X +1409(program)X +1762(must)X +1976(specify)X +2281(the)X +2426(root)X +2609(of)X +2717(the)X +2863(problem)X +3212(tree,)X +3409(how)X +3602(to)X +3705(generate)X +576 1926(children,)N +955(and)X +1133(calculations)X +1633(needed)X +1945(at)X +2054(each)X +2270(node.)X +2544(It)X +2642(can)X +2815(also)X +3009(optionally)X +3438(specify)X +3754(how)X +3957(to)X +576 2034(generate)N +937(values)X +1217(of)X +1331(a)X +1408(tree)X +1587(node)X +1808(from)X +2029(combining)X +2475(its)X +2600(children's)X +3019(values)X +3299(and)X +3472(how)X +3671(to)X +3781(spread)X +576 2142(information)N +1055(either)X +1299(globally)X +1639(or)X +1743(locally)X +2030(throughout)X +2476(the)X +2618(tree.)X +776 2283(DIB)N +969(divides)X +1276(the)X +1423(problem)X +1773(into)X +1952(subproblems)X +2472(and)X +2640(assigns)X +2946(them)X +3168(to)X +3272(any)X +3440(number)X +3763(of)X +3872(pro-)X +576 2391(cessors)N +879(\(potentially)X +1349(nonhomogeneous)X +2052(machines)X +2441(in)X +2541(a)X +2609(network\))X +2981(dynamically.)X +3531(Each)X +3749(proces-)X +576 2499(sor)N +723(maintains)X +1128(a)X +1201(table)X +1419(of)X +1530(explicit)X +1851(work,)X +2103(recording)X +2503(all)X +2631(the)X +2780(problems)X +3169(that)X +3345(have)X +3558(been)X +3771(sent)X +3957(to)X +576 2607(the)N +721(processor,)X +1140(have)X +1349(been)X +1558(generated)X +1960(by)X +2083(the)X +2227(processor)X +2621(itself,)X +2864(and/or)X +3136(have)X +3344(been)X +3552(sent)X +3733(to)X +3834(other)X +576 2715(processors.)N +1062(Each)X +1288(processor)X +1689(is)X +1786(responsible)X +2257(for)X +2402(the)X +2553(work)X +2784(in)X +2893(its)X +3018(table.)X +3288(Each)X +3515(item)X +3721(of)X +3835(work)X +576 2823(\(represented)N +1079(by)X +1202(a)X +1272(node)X +1486(in)X +1588(the)X +1733(backtrack)X +2135(tree,)X +2331(which)X +2593(stands)X +2859(as)X +2965(well)X +3157(for)X +3295(all)X +3418(its)X +3535(descendents\))X +576 2931(is)N +664(labeled)X +967(by)X +1087(which)X +1346(processor,)X +1762(if)X +1845(any,)X +2032(has)X +2184(been)X +2390(assigned)X +2745(that)X +2914(work.)X +776 3072(When)N +1030(a)X +1097(processor)X +2 f +1489(A)X +1 f +1588(is)X +1676(\256nished)X +2004(with)X +2199(a)X +2266(problem)X +2611(and)X +2775(has)X +2928(reported)X +3274(its)X +3390(result)X +3629(to)X +3729(the)X +3872(pro-)X +576 3180(cessor)N +848(that)X +1025(gave)X +1239(it)X +1324(that)X +1500(problem,)X +1876(it)X +1961(will)X +2142(take)X +2334(the)X +2483(\256rst)X +2663(\(in)X +2801(an)X +2923(inorder)X +3232(traversal)X +3595(of)X +3706(the)X +3855(tree\))X +576 3288(unassigned)N +1042(problem)X +1402(from)X +1629(its)X +1760(table.)X +2036(If)X +2140(no)X +2276(unassigned)X +2743(problem)X +3104(is)X +3208(available,)X +2 f +3621(A)X +1 f +3736(sends)X +3989(a)X +3 f +576 3396(work)N +815(request)X +1 f +1145(message)X +1496(to)X +1596(another)X +1910(processor)X +2303(\(or)X +2440(processors\),)X +2926(selected)X +3262(at)X +3357(random)X +3676(from)X +2 f +3888(A)X +1 f +3963('s)X +576 3504(peers,)N +827(repeatedly)X +1253(\(with)X +1480(some)X +1707(delay\))X +1972(until)X +2173(new)X +2357(work)X +2578(arrives.)X +776 3645(A)N +878(processor)X +2 f +1279(B)X +1 f +1387(that)X +1565(receives)X +1914(a)X +1990(work)X +2220(request)X +2531(message)X +2890(interrupts)X +3292(its)X +3416(own)X +3614(search)X +3893(and)X +576 3753(trys)N +754(to)X +863(respond)X +1201(by)X +1331(sending)X +1664(some)X +1901(work)X +2132(to)X +2240(the)X +2391(requesting)X +2825(processor)X +3226(from)X +3446(its)X +3570(table.)X +3839(If)X +3936(no)X +576 3861(unassigned)N +1031(problem)X +1380(is)X +1472(available)X +1849(in)X +1952(the)X +2098(table,)X +2338(then)X +2532(the)X +2678(problem)X +2 f +3028(B)X +1 f +3132(is)X +3225(working)X +3574(on)X +3699(is)X +3792(subdi-)X +576 3969(vided)N +815(and)X +979(its)X +1095(children)X +1436(are)X +1579(put)X +1727(in)X +1827(the)X +1970(table.)X +2231(Until)X +2454(work)X +2676(is)X +2765(subdivided,)X +3236(DIB)X +3426(maintains)X +3826(a)X +3893(fast)X +576 4077(representation)N +1163(of)X +1284(the)X +1443(current)X +1758(search)X +2046(\(just)X +2259(a)X +2344(recursion)X +2744(stack;)X +3011(we)X +3165(call)X +3347(it)X +3443(the)X +3603(``implicit'')X +576 4185(representation\);)N +1206(subdivided)X +1653(work)X +1875(is)X +1964(explicit)X +2278(in)X +2377(the)X +2519(table.)X +2779(After)X +3006(subdivision,)X +2 f +3497(B)X +1 f +3596(can)X +3754(usually)X +576 4293(send)N +791(some)X +1033(unassigned)X +1499(work)X +1735(to)X +1849(the)X +2006(requesting)X +2446(processor.)X +2901(Subdivision)X +3399(may)X +3604(have)X +3826(to)X +3941(be)X +576 4401(repeated)N +944(several)X +1258(times)X +1508(before)X +1795(an)X +1927(unassigned)X +2395(problem)X +2757(is)X +2862(generated,)X +3302(but)X +3466(if)X +3566(it)X +3660(reaches)X +3989(a)X +576 4509(trivial)N +844(problem)X +1202(\(not)X +1394(worth)X +1655(subdividing\),)X +2202(or)X +2319(if)X +2416(it)X +2508(reaches)X +2835(the)X +2991(depth)X +3243(at)X +3351(which)X +2 f +3624(B)X +1 f +3737(itself)X +3968(is)X +576 4617(searching,)N +998(the)X +1144(request)X +1450(is)X +1542(not)X +1693(granted.)X +2 f +2058(B)X +1 f +2161(resumes)X +2504(its)X +2623(search)X +2897(after)X +3102(dealing)X +3414(with)X +3613(the)X +3759(incom-)X +576 4725(ing)N +723(request.)X +776 4866(DIB)N +972(is)X +1067(fault)X +1275(tolerant,)X +1625(in)X +1731(that)X +1907(work)X +2135(that)X +2 f +2311(B)X +1 f +2417(has)X +2576(given)X +2822(to)X +2 f +2929(A)X +1 f +3036(can)X +3202(still)X +3379(be)X +3502(accomplished)X +576 4974(by)N +2 f +702(B)X +1 f +807(if)X +896(there)X +1119(is)X +1213(nothing)X +1537(else)X +1717(worth)X +1971(doing)X +2220(and)X +2389(if)X +2 f +2478(A)X +1 f +2582(has)X +2739(not)X +2891(yet)X +3038(reported)X +3388(the)X +3535(result)X +3778(of)X +3887(that)X +576 5082(work.)N +845(This)X +1040(mechanism)X +1503(does)X +1703(not)X +1850(need)X +2056(timeouts)X +2412(or)X +2516(``heartbeats'')X +3059(to)X +3158(detect)X +3413(failure.)X +776 5223(We)N +938(have)X +1148(enhanced)X +1540(the)X +1686(DIB)X +1879(package)X +2223(so)X +2336(that)X +2509(it)X +2591(can)X +2753(achieve)X +3076(high)X +3275(ef\256ciency)X +3683(for)X +3823(game)X +576 5331(tree)N +748(search.)X +1069(The)X +1246(principal)X +1616(enhancement)X +2152(is)X +2243(added)X +2500(\257exibility)X +2902(given)X +3143(to)X +3245(the)X +3389(application)X +3844(level)X +576 5439(for)N +719(delaying)X +1082(evaluation)X +1515(of)X +1626(a)X +1700(game-tree)X +2117(node.)X +2383(That)X +2591(is,)X +2710(the)X +2860(application)X +3321(can)X +3487(refuse)X +3754(to)X +3861(gen-)X +576 5547(erate)N +792(additional)X +1206(children)X +1549(for)X +1688(a)X +1758(node)X +1972(but)X +2122(indicate)X +2455(that)X +2627(in)X +2729(the)X +2874(future)X +3131(it)X +3212(may)X +3405(again)X +3641(be)X +3759(willing)X +576 5655(to)N +688(do)X +821(so.)X +991(DIB)X +1194(does)X +1408(not)X +1569(attempt)X +1897(to)X +2010(generate)X +2375(children)X +2729(of)X +2847(such)X +3061(a)X +3142(node)X +3367(again)X +3614(until)X +3829(some)X +576 5763(other)N +798(child)X +1015(of)X +1119(that)X +1288(node)X +1499(has)X +1651(completed)X +2077(or)X +2181(a)X +2248(data)X +2433(update)X +2714(message)X +3064(has)X +3216(arrived)X +3513(at)X +3607(that)X +3776(node.)X + +3 p +%%Page: 3 3 +12 s 0 xH 0 xS 1 f +10 s +3 f +576 474(Game-tree)N +963(search)X +3992(3)X +1 f +12 s +776 780(To)N +913(experiment)X +1377(with)X +1578(game)X +1817(playing,)X +2160(we)X +2302(have)X +2514(designed)X +2886(a)X +2959(two-level)X +3353(application)X +3813(struc-)X +576 888(ture.)N +817(The)X +3 f +1010(game)X +1 f +1272(level)X +1503(is)X +1610(game-speci\256c,)X +2212(knowing)X +2591(the)X +2752(rules)X +2982(for)X +3137(tic-tac-toe,)X +3596(Othello,)X +3952(or)X +576 996(checkers.)N +989(The)X +3 f +1167(control)X +1 f +1489(level)X +1705(communicates)X +2290(both)X +2489(with)X +2688(DIB)X +2881(and)X +3048(the)X +3194(game)X +3431(level.)X +3695(It)X +3782(knows)X +576 1104(the)N +734(pattern)X +1042(of)X +1162(evaluation)X +1604(for)X +1756(one)X +1935(of)X +2055(the)X +2213(algorithms)X +2665(we)X +2816(compared,)X +3259(namely,)X +3606(alpha-beta,)X +576 1212(mandatory)N +1023(work)X +1255(\256rst,)X +1463 0.1979(principal-variation)AX +2216(splitting,)X +2591(tree)X +2772(splitting,)X +3148(ER,)X +3331(or)X +3447(delay)X +3692(splitting.)X +576 1320(Any)N +769(of)X +877(the)X +1022(game)X +1258(modules)X +1611(we)X +1750(implemented)X +2281(can)X +2442(be)X +2560(used)X +2763(with)X +2961(any)X +3127(of)X +3234(the)X +3379(control)X +3679(modules;)X +576 1428(any)N +739(such)X +939(combination)X +1445(can)X +1603(be)X +1718(used)X +1918(with)X +2113(our)X +2265(enhanced)X +2653(DIB.)X +776 1569(Since)N +1043(DIB)X +1261(distributes)X +1715(work,)X +1989(collects)X +2337(and)X +2529(reports)X +2849(results,)X +3177(and)X +3370(passes)X +3669(messages)X +576 1677(between)N +929(processors)X +1365(in)X +1471(a)X +1545(similar)X +1844(way)X +2035(for)X +2178(all)X +2306(the)X +2455(combinations,)X +3029(we)X +3172(can)X +3337(compare)X +3700(different)X +576 1785(control)N +882(modules)X +1241(in)X +1349(a)X +1425(fairly)X +1668 0.2050(implementation-independent)AX +2811(fashion.)X +3176(Previous)X +3546(comparisons)X +576 1893(are)N +719(questionable)X +1231(because)X +1561(each)X +1763(algorithm)X +2163(was)X +2337(implemented)X +2866(in)X +2966(a)X +3034(different)X +3391(parallel)X +3706(environ-)X +576 2001(ment.)N +8 f +14 s +576 2205(3.)N +844(Parallel)X +1447(tree)X +1782(search)X +2251(algorithms)X +1 f +12 s +776 2346(The)N +953(best)X +1135(way)X +1323(to)X +1426(evaluate)X +1776(a)X +1847(parallel)X +2165(algorithm)X +2568(for)X +2708(a)X +2779(given)X +3021(problem)X +3370(is)X +3462(to)X +3565(measure)X +3914(the)X +576 2454(extent)N +844(in)X +951(which)X +1217(it)X +1302(takes)X +1531(advantage)X +1953(of)X +2064(available)X +2444(processors.)X +2928(This)X +3130(idea)X +3322(can)X +3487(be)X +3609(formulated)X +576 2562(as)N +680(follows:)X +2 f +1161 2754(speedup)N +1516(S)X +9 f +1604(=)X +2 f +1848 2823(time)N +2054(required)X +2425(by)X +2556(parallel)X +2901(algorithm)X +1705 2700(time)N +1911(required)X +2282(by)X +2413(best)X +2608(sequential)X +3044(algorithm)X +10 f +1690 2727(h)N +1709(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)X +2 f +1442 3045(ef\256ciency)N +1847(E)X +9 f +1946(=)X +2 f +2047 3114(number)N +2380(of)X +2511(processors)X +2966(used)X +2571 2991(S)N +10 f +2033 3018(h)N +2053(hhhhhhhhhhhhhhhhhhhhhhh)X +1 f +776 3285(It)N +866(is)X +961(not)X +1115(easy)X +1317(to)X +1423(achieve)X +1749(a)X +1823(``perfect'')X +2250(ef\256ciency)X +2661(of)X +2772(1.0.)X +2971(For)X +3136(a)X +3211(given)X +3457(sized)X +3687(problem,)X +576 3393(ef\256ciency)N +990(tends)X +1227(to)X +1335(decrease)X +1700(as)X +1813(the)X +1964(number)X +2291(of)X +2404(processors)X +2842(increases.)X +3276(This)X +3480(relationship)X +3968(is)X +576 3501(explained)N +975(by)X +1095(Kumar)X +1386(and)X +1549(Rao)X +1728([2])X +1864(as)X +1968(resulting)X +2329(from)X +2540(an)X +2655(increase)X +2995(in)X +3094(the)X +3236(communication)X +3860(time)X +576 3609(\(sum)N +798(of)X +908(the)X +1056(time)X +1258(spent)X +1491(by)X +1616(all)X +1742(processors)X +2176(in)X +2280(communicating)X +2909(with)X +3109(neighboring)X +3603(processors,)X +576 3717(waiting)N +894(for)X +1035(messages,)X +1451(time)X +1652(in)X +1756(starvation,)X +2189(and)X +2357(so)X +2471(forth\),)X +2743(while)X +2986(there)X +3208(is)X +3301(no)X +3426(change)X +3729(in)X +3834(com-)X +576 3825(putation)N +926(time)X +1132(\(sum)X +1358(of)X +1471(the)X +1622(time)X +1827(spent)X +2063(by)X +2192(all)X +2322(the)X +2473(processors)X +2911(in)X +3019(useful)X +3287(computation\).)X +3882(The)X +576 3933(relationship)N +1060(between)X +1411(communication)X +2041(time)X +2243(\()X +2 f +2275(T)X +9 s +2328 3957(cm)N +1 f +12 s +2428 3933(\),)N +2514(computation)X +3026(time)X +3228(\()X +2 f +3260(T)X +9 s +3313 3957(cp)N +1 f +12 s +3397 3933(\),)N +3483(and)X +3652(ef\256ciency)X +576 4047(\(E\))N +723(is)X +811(described)X +1204(as)X +1308(follows:)X +2 f +2045 4263(E)N +9 f +2120(=)X +2 f +2197 4332(T)N +9 s +2250 4356(cp)N +12 s +9 f +2334 4332(+)N +2 f +2387(T)X +9 s +2440 4356(cm)N +12 s +2300 4185(T)N +9 s +2353 4209(cp)N +12 s +10 f +2182 4236(h)N +2218(hhhhhhh)X +1 f +776 4527(Kumar)N +1080(and)X +1256(Rao)X +1435([2])X +1584(de\256ne)X +1856(an)X +3 f +1984(isoef\256ciency)X +2518(function)X +1 f +2896(that)X +3078(shows)X +3354(how)X +3556(the)X +3711(problem)X +576 4635(must)N +790(grow)X +1013(with)X +1210(number)X +1530(of)X +1636(processors)X +2067(to)X +2168(achieve)X +2489(the)X +2633(same)X +2857(ef\256ciency.)X +3311(They)X +3535(also)X +3716(mention)X +576 4743(that)N +759(since)X +995(most)X +1220(problems)X +1616(have)X +1836(a)X +1917(sequential)X +2346(component)X +2812(\(in)X +2957(depth-\256rst)X +3390(search,)X +3698(it)X +3790(is)X +3893(one)X +576 4851(node)N +813(expansion\),)X +1309(problem)X +1680(size)X +1880(must)X +2117(grow)X +2364(at)X +2484(least)X +2711(linearly)X +3056(to)X +3181(maintain)X +3569(a)X +3662(particular)X +576 4959(ef\256ciency.)N +776 5100(Steinberg)N +1177(and)X +1348(Solomon)X +1719([3])X +1863(blame)X +2131(the)X +2281(failure)X +2565(to)X +2672(achieve)X +2999(perfect)X +3299(ef\256ciency)X +3711(on)X +3839(three)X +576 5208(types)N +803(of)X +907(``loss''.)X +10 f +624 5349(g)N +3 f +706(Starvation)X +1162(loss)X +1 f +1311(:)X +1362(processors)X +1791(sitting)X +2056(idle)X +2225(while)X +2463(awaiting)X +2819(work)X +3040(to)X +3139(be)X +3254(given)X +3492(to)X +3591(them.)X +10 f +624 5457(g)N +3 f +706(Interference)X +1240(loss)X +1 f +1389(:)X +1442(time)X +1640(spent)X +1869(waiting)X +2184(for)X +2322(access)X +2594(to)X +2695(shared)X +2973(resources)X +3363(such)X +3566(as)X +3673(the)X +3818(set)X +3952(of)X +706 5565(un\256nished)N +1130(subproblems.)X +10 f +624 5673(g)N +3 f +706(Speculative)X +1201(loss)X +1 f +1350(:)X +1402(time)X +1599(spent)X +1828(performing)X +2287(unnecessary)X +2783(work,)X +3030(such)X +3232(as)X +3338(that)X +3509(performed)X +3936(by)X +706 5781(a)N +792(parallel)X +1125(algorithm)X +1543(before)X +1832(it)X +1929(is)X +2036(possible)X +2394(to)X +2512(determine)X +2941(that)X +3129(the)X +3289(work)X +3528(is)X +3634(necessary.)X + +4 p +%%Page: 4 4 +12 s 0 xH 0 xS 1 f +10 s +3 f +576 474(Game-tree)N +963(search)X +3992(4)X +1 f +12 s +706 780(Because)N +1059(a)X +1134(parallel)X +1456(algorithm)X +1863(must)X +2082(evaluate)X +2436(different)X +2800(nodes)X +3056(simultaneously,)X +3695(informa-)X +706 888(tion)N +893(gained)X +1187(by)X +1319(evaluation)X +1757(of)X +1873(one)X +2048(node)X +2271(could)X +2521(come)X +2766(too)X +2925(late)X +3101(to)X +3212(cut)X +3366(off)X +3514(evaluation)X +3952(of)X +706 996(other)N +928(nodes.)X +8 f +14 s +576 1200(3.1.)N +978(Alpha-beta)X +1 f +12 s +776 1341(The)N +966(alpha-beta)X +1408(algorithm)X +1823(is)X +1927(a)X +2010(sequential)X +2441(technique)X +2857(used)X +3074(to)X +3190(evaluate)X +3553(a)X +3637(game)X +3887(tree)X +576 1449(ef\256ciently.)N +1050(The)X +1235(nodes)X +1494(corresponding)X +2079(to)X +2189(the)X +2342(\256rst)X +2526(player's)X +2871(moves)X +3157(are)X +3309(called)X +3 f +3574(max)X +1 f +3784(nodes,)X +576 1557(and)N +744(the)X +891(other)X +1119(nodes)X +1373(are)X +1521(called)X +3 f +1782(min)X +1 f +1972(nodes.)X +2274(The)X +2454(value)X +2693(of)X +2803(a)X +2876(max)X +3072(node)X +3289(is)X +3383(the)X +3531(maximum)X +3952(of)X +576 1665(the)N +719(value)X +953(of)X +1058(its)X +1174(children,)X +1539(where)X +1799(as)X +1904(the)X +2047(value)X +2281(of)X +2386(a)X +2454(min)X +2629(node)X +2841(is)X +2930(the)X +3073(minimum)X +3473(of)X +3577(the)X +3719(value)X +3952(of)X +576 1773(its)N +714(children.)X +1125(The)X +1322(value)X +1578(of)X +1705(a)X +1795(leaf)X +1987(is)X +2098(determined)X +2579(by)X +2723(a)X +2814(game-speci\256c)X +3397(static)X +3649(evaluator.)X +576 1881(Alpha-beta)N +1034(ignores)X +1347(branches)X +1719(that)X +1894(are)X +2042(certain)X +2335(not)X +2488(to)X +2593(contribute)X +3014(to)X +3118(the)X +3265(value)X +3503(of)X +3612(the)X +3759(current)X +576 1989(node.)N +835(Figure)X +1110(1)X +1183(shows)X +1447(a)X +1515(sample)X +1813(game)X +2047(tree)X +2217(with)X +2413(a)X +2481(cutoff.)X +2784(In)X +2889(this)X +3053(\256gure,)X +3326(node)X +2 f +3538(z)X +1 f +3591(,)X +3640(which)X +3900(is)X +3989(a)X +576 2097(max)N +766(node,)X +1001(has)X +1153(two)X +1321(children,)X +1685(and)X +1848(its)X +1963(\256rst)X +2136(child)X +2353(is)X +2441(evaluated)X +2835(to)X +2934(9.)X +3054(Therefore,)X +1184 2238(value\()N +2 f +1425(z)X +1 f +1478(\))X +1534(=)X +1612(max{9,)X +1920(value\()X +2 f +2161(y)X +1 f +2220(\)})X +576 2379(where)N +2 f +845(y)X +1 f +939(is)X +1038(the)X +1191(other)X +1424(child)X +1652(of)X +2 f +1767(z)X +1 f +1820(.)X +1903(Now)X +2124(if)X +2218(the)X +2371(\256rst)X +2555(child)X +2783(\(we)X +2962(will)X +3147(often)X +3380(call)X +3555(it)X +3644(the)X +3 f +3797(eldest)X +1 f +576 2487(child\))N +825(of)X +2 f +929(y)X +1 f +1012(is)X +1100(evaluated)X +1494(to)X +1593(7)X +1665(then)X +1184 2628(value\()N +2 f +1425(y)X +1 f +1484(\))X +1540(=)X +1618(min{7,)X +1910(...})X +576 2769(so)N +688(the)X +833(value)X +1069(of)X +2 f +1176(z)X +1 f +1256(is)X +1347(9)X +1423(regardless)X +1841(of)X +1949(the)X +2095(value)X +2332(of)X +2 f +2440(y)X +1 f +2499(.)X +2575(It)X +2662(follows)X +2978(that)X +3151(the)X +3297(remaining)X +3716(children)X +576 2877(of)N +680(the)X +822(node)X +2 f +1033(y)X +1 f +1116(need)X +1322(not)X +1469(be)X +1584(evaluated.)X +2026(Ignoring)X +2381(those)X +2608(children)X +2948(is)X +3036(called)X +3 f +3291(shallow)X +3624(cutoff)X +1 f +3864(.)X +776 3018(Figure)N +1073(2)X +1167(illustrates)X +1588(another)X +1923(type)X +2135(of)X +2261(cutoff.)X +2585(After)X +2834(the)X +2998(eldest)X +3269(child)X +3508(of)X +3634(node)X +2 f +3868(z)X +1 f +3968(is)X +576 3126(evaluated,)N +1009(we)X +1160(see)X +1322(that)X +2 f +1506(z)X +1 f +1559('s)X +1667(value)X +1915(will)X +2104(be)X +2234(greater)X +2540(than)X +2744(or)X +2862(equal)X +3109(to)X +3222(9.)X +3356(This)X +3565(value)X +3812(is)X +3914(the)X +576 3234(current)N +876(lower)X +1122(bound)X +1389(in)X +1491(the)X +1636(alpha-beta)X +2065(algorithm.)X +2515(The)X +2692(value)X +2928(of)X +3035(a)X +3 f +3105(min)X +1 f +3292(node)X +3506(in)X +3608(the)X +3754(subtree)X +576 3342(rooted)N +853(at)X +954(node)X +2 f +1172(y)X +1 f +1262(must)X +1479(be)X +1600(greater)X +1898(than)X +2094(9)X +2172(in)X +2277(order)X +2510(for)X +2652(the)X +2800(lower)X +3049(bound)X +3319(to)X +3424(change.)X +3775(There-)X +576 3450(fore,)N +779(when)X +1011(the)X +1154(algorithm)X +1554(reaches)X +1868(node)X +2 f +2080(w)X +1 f +2185(\(a)X +2285(min)X +2460(node\))X +2704(and)X +2868(its)X +2984(\256rst)X +3158(child)X +3376(is)X +3465(evaluated)X +3860(to)X +3960(7,)X +576 3558(the)N +719(evaluation)X +1146(of)X +1250(the)X +1392(remaining)X +1807(children)X +2147(can)X +2305(be)X +2420(avoided.)X +2797(This)X +2992(cutoff)X +3246(is)X +3334(called)X +3589(a)X +3 f +3656(deep)X +3872(cut-)X +576 3666(off)N +1 f +712(because)X +1041(the)X +1183(node)X +2 f +1394(w)X +1 f +1498(is)X +1586(more)X +1808(than)X +1998(one)X +2161(ply)X +2308(below)X +2567(the)X +2709(node)X +2 f +2920(z)X +1 f +2973(.)X +776 3807(Following)N +1198(Fishburn)X +1563([4],)X +1726(we)X +1865(present)X +2170(the)X +2315(following)X +2716(Pascal-like)X +3166(code)X +3376(of)X +3484(the)X +3630(alpha-beta)X +576 3915(algorithm,)N +999(as)X +1103(adapted)X +1427(from)X +1638(Knuth)X +1902(and)X +2065(Moore)X +2345([5]:)X +1584 4399 MXY +1 setlinewidth +2023 4462 MXY +125 Dc +1584 4775 MXY +125 Dc +2524 MX +125 Dc +2023 5150 MXY +125 Dc +2899 MX +125 Dc +1695 4735 MXY +346 -229 Dl +2140 4491 MXY +396 246 Dl +2540 4817 MXY +-415 285 Dl +1584 4817 MXY +[64 32] 0 setdash +2635 4813 MXY +296 283 Dl +5 f +2061 4502(z)N +2562 4815(y)N +1621 4940(9)N +2059 5316(7)N +1584 5276 MXY +3 setlinewidth +[] 0 setdash +3 f +1821 5448(Figure)N +1 f +2118(1:)X +2217(Shallow)X +2556(cutoff)X + +5 p +%%Page: 5 5 +12 s 0 xH 0 xS 1 f +10 s +3 f +576 474(Game-tree)N +963(search)X +3992(5)X +1 f +12 s +1440 876 MXY +1 setlinewidth +1951 955 MXY +157 Dc +1519 1269 MXY +157 Dc +2540 MX +157 Dc +2147 1740 MXY +157 Dc +3011 MX +157 Dc +1794 2094 MXY +157 Dc +2501 MX +157 Dc +1440 2604 MXY +157 Dc +2147 MX +157 Dc +1636 1201 MXY +336 -193 Dl +2092 1002 MXY +458 229 Dl +2661 1335 MXY +369 355 Dl +2572 1333 MXY +-311 337 Dl +2281 1796 MXY +233 254 Dl +2179 1803 MXY +-266 223 Dl +1440 1803 MXY +[64 32] 0 setdash +1904 2166 MXY +273 377 Dl +1440 2166 MXY +[] 0 setdash +1833 2162 MXY +-291 367 Dl +5 f +2006 995(z)N +2595 1309(y)N +2202 1780(x)N +1838 2134(w)N +1572 1466(9)N +1493 2801(7)N +1440 2761 MXY +3 setlinewidth +3 f +1877 2933(Figure)N +1 f +2174(2:)X +2273(Deep)X +2500(cutoff)X +3 f +10 s +576 3119(function)N +7 f +908(alphabeta\(z)X +1484(:)X +1580(position;)X +2 f +12 s +9 f +2060(a)X +7 f +10 s +2120(,)X +2 f +12 s +9 f +2216(b)X +7 f +10 s +2317(:)X +2413(integer\):integer;)X +3 f +864 3209(var)N +7 f +1152 3299(Answer,)N +1536(Child,)X +1872(t,)X +2016(d)X +2112(:)X +2208(integer;)X +3 f +864 3389(begin)N +7 f +1152 3479(determine)N +1632(the)X +1824(child)X +2112(positions)X +2 f +12 s +2592(z)X +1 f +9 s +2641 3503(1)N +7 f +10 s +3479(,...,)Y +2 f +12 s +2965(z)X +9 s +3002 3503(d)N +3 f +10 s +1152 3575(if)N +7 f +1249(d)X +1345(=)X +1441(0)X +3 f +1537(then)X +1440 3665(return)N +7 f +1663(\(StaticValue\(z\)\))X +3 f +1152 3755(else)N +1440 3845(begin)N +7 f +1440 3935(Answer)N +1776(:=)X +2 f +12 s +9 f +1920(a)X +7 f +10 s +2028(;)X +3 f +1440 4025(for)N +7 f +1591(Child)X +1879(:=)X +2023(1)X +3 f +2119(to)X +7 f +2234(d)X +3 f +2330(do)X +1728 4115(begin)N +7 f +1728 4205(t)N +1824(:=)X +1968(-alphabeta\()X +2 f +12 s +(z)S +9 s +2533 4229(Child)N +7 f +10 s +2709 4205(,)N +2805(-)X +2 f +12 s +9 f +(b)S +7 f +10 s +2906(,)X +3002(-Answer\);)X +3 f +1728 4301(if)N +7 f +1825(t)X +1921(>)X +2017(Answer)X +3 f +2353(then)X +7 f +2016 4391(Answer)N +2352(:=)X +2496(t;)X +3 f +1728 4481(if)N +7 f +1825(Answer)X +2 f +12 s +9 f +2161(\263)X +2238(b)X +3 f +10 s +2339(then)X +2016 4571(return)N +7 f +2239(\(Answer\);)X +2719({cutoff})X +3 f +1728 4661(end)N +7 f +1852(;)X +3 f +1440 4751(return)N +7 f +1663(\(Answer\);)X +3 f +1440 4841(end)N +7 f +1564(;)X +3 f +864 4931(end)N +7 f +988(.)X +1 f +12 s +576 5105(The)N +750(alpha-beta)X +1176(algorithm)X +1575(satis\256es)X +1903(the)X +2045(following)X +2443(conditions)X +2868([5]:)X +896 5246(if)N +979(negamax\()X +2 f +1359(z)X +1 f +1412(\))X +2 f +9 f +1468(\243)X +1545(a)X +1 f +2048(then)X +2238(alphabeta\()X +2 f +2640(z)X +1 f +2693(,)X +2 f +9 f +2741(a)X +1 f +2801(,)X +2 f +9 f +2849(b)X +1 f +2902(\))X +2 f +9 f +2958(\243)X +3035(a)X +1 f +3095(,)X +896 5354(if)N +2 f +9 f +979(a)X +1 f +1063(<)X +1141(negamax\()X +2 f +1521(z)X +1 f +1574(\))X +1630(<)X +2 f +9 f +1708(b)X +1 f +2048(then)X +2238(alphabeta\()X +2 f +2640(z)X +1 f +2693(,)X +2 f +9 f +2741(a)X +1 f +2801(,)X +2 f +9 f +2849(b)X +1 f +2902(\))X +2958(=)X +3036(negamax\()X +2 f +3416(z)X +1 f +3469(\),)X +896 5462(if)N +979(negamax\()X +2 f +1359(z)X +1 f +1412(\))X +2 f +9 f +1468(\263)X +1545(b)X +1 f +2048(then)X +2238(alphabeta\()X +2 f +2640(z)X +1 f +2693(,)X +2 f +9 f +2741(a)X +1 f +2825(,)X +2 f +9 f +2873(b)X +1 f +2926(\))X +2 f +9 f +2982(\263)X +3059(b)X +1 f +3112(.)X +576 5603(These)N +830(conditions)X +1255(imply)X +1504(that)X + +6 p +%%Page: 6 6 +12 s 0 xH 0 xS 1 f +10 s +3 f +576 474(Game-tree)N +963(search)X +3992(6)X +1 f +12 s +896 780(alphabeta\()N +2 f +1298(z)X +1 f +1351(,)X +2 f +9 f +1399(-\245)X +1 f +1521(,)X +2 f +9 f +1569(\245)X +1 f +1638(\))X +1694(=)X +1772(negamax\()X +2 f +2152(z)X +1 f +2205(\))X +2261(,)X +576 921(which)N +839(means)X +1113(that)X +1287(if)X +1375(the)X +1522(initial)X +1777(window)X +2115([alpha,)X +2409(beta])X +2631(is)X +2724(\()X +2 f +9 f +2756(-\245)X +1 f +2878(,)X +2 f +9 f +2931(\245)X +1 f +3000(\))X +3061(then)X +3256(the)X +3403(alpha-beta)X +3834(algo-)X +576 1029(rithm)N +818(returns)X +1118(the)X +1269(same)X +1500(value)X +1742(as)X +1855(the)X +2006(negamax)X +2387(algorithm)X +2795(\(straightforward)X +3453 0.2321(tree-evaluation)AX +576 1137(algorithm)N +975(that)X +1144(never)X +1382(cuts)X +1561(work)X +1782(off\))X +1950([5].)X +776 1278(The)N +959(performance)X +1479(of)X +1593(the)X +1745(alpha-beta)X +2181(algorithm)X +2590(depends)X +2939(a)X +3016(great)X +3243(deal)X +3438(on)X +3568(the)X +3720(order)X +3957(in)X +576 1386(which)N +838(children)X +1181(of)X +1288(a)X +1358(node)X +1572(are)X +1717(expanded.)X +2161(If)X +2252(the)X +2397(children)X +2740(of)X +2847(each)X +3050(node)X +3263(in)X +3364(the)X +3508(game)X +3743(tree)X +3914(are)X +576 1494(expanded)N +972(in)X +1074(increasing)X +1497(order)X +1727(of)X +1834(their)X +2038(negamax)X +2413(values,)X +2710(then)X +2904(the)X +3050(largest)X +3335(number)X +3657(of)X +3765(cutoffs)X +576 1602(will)N +750(occur.)X +776 1743(Knuth)N +1049(and)X +1221(Moore)X +1501([5])X +1646(introduced)X +2091(the)X +2242(idea)X +2436(of)X +3 f +2549(critical)X +2872(nodes)X +1 f +3139(in)X +3247(their)X +3457(analysis)X +3800(of)X +3914(the)X +576 1851(best)N +764(case)X +963(of)X +1075(the)X +1225(alpha-beta)X +1659(algorithm,)X +2090(and)X +2261(Steinberg)X +2662(and)X +2833(Solomon)X +3204([3])X +3348(use)X +3508(the)X +3658(following)X +576 1959(rules)N +787(to)X +886(determine)X +1296(the)X +1438(critical)X +1731(nodes:)X +10 f +624 2100(g)N +1 f +706(The)X +880(root)X +1059(of)X +1163(the)X +1305(game)X +1538(tree)X +1707(is)X +1795(a)X +1862(type-1)X +2132(node.)X +10 f +624 2208(g)N +1 f +706(The)X +880(eldest)X +1129(child)X +1346(of)X +1450(a)X +1517(type-1)X +1787(node)X +1998(is)X +2086(also)X +2265(type-1.)X +2583(The)X +2757(remaining)X +3172(children)X +3512(are)X +3654(type-2.)X +10 f +624 2316(g)N +1 f +706(The)X +880(eldest)X +1129(child)X +1346(of)X +1450(a)X +1517(type-2)X +1787(node)X +1998(is)X +2086(a)X +2153(type-3)X +2423(node.)X +10 f +624 2424(g)N +1 f +706(All)X +853(children)X +1193(of)X +1297(a)X +1364(type-3)X +1634(node)X +1845(are)X +1987(type-2.)X +10 f +624 2532(g)N +1 f +706(A)X +799(node)X +1010(is)X +1098(critical)X +1391(iff)X +1506(it)X +1584(is)X +1672(assigned)X +2027(a)X +2094(number)X +2412(by)X +2532(the)X +2674(above)X +2928(rules.)X +776 2673(The)N +954(critical)X +1251(nodes)X +1503(form)X +1718(a)X +1789(minimal)X +2139(subtree)X +2441([3])X +2581(of)X +2689(the)X +2835(game)X +3072(tree)X +3245(which,)X +3533(regardless)X +3952(of)X +576 2781(the)N +743(values)X +1038(of)X +1167(the)X +1333(terminal)X +1703(nodes,)X +1999(will)X +2197(always)X +2512(be)X +2651(examined)X +3074(by)X +3218(the)X +3384(alpha-beta)X +3834(algo-)X +576 2889(rithm)N +809([5].)X +995(The)X +1171(number)X +1491(of)X +1598(terminal)X +1947(nodes)X +2198(in)X +2300(the)X +2445(minimal)X +2794(subtree)X +3099(of)X +3206(a)X +3276(complete)X +2 f +3657(d)X +1 f +(-ary)S +3887(tree)X +576 2997(of)N +680(height)X +2 f +945(h)X +1 f +1017(is)X +2 f +2147 3153(d)N +9 s +10 f +2219 3114(R)N +2 f +(h)S +2285(/)X +1 f +(2)S +2 f +10 f +2353(H)X +12 s +9 f +3153(+)Y +2 f +2424(d)X +9 s +10 f +2496 3114(Q)N +2 f +(h)S +2562(/)X +1 f +(2)S +2 f +10 f +2630(P)X +12 s +9 f +3153(-)Y +1 f +2701(1)X +576 3309(If)N +673(the)X +824(tree)X +1002(is)X +1099(examined)X +1507(in)X +1615(increasing)X +2044(order)X +2280(of)X +2394(value,)X +2661(the)X +2813(alpha-beta)X +3249(procedure)X +3668(examines)X +576 3417(precisely)N +949(the)X +1092(minimal)X +1438(subtree)X +1740(of)X +1844(the)X +1986(game)X +2219(tree.)X +2436(In)X +2540(short,)X +2780(alpha-beta)X +3206(examines)X +3594(about)X +3832(2)X +2 f +(n)S +1 f +9 s +3940 3378(1)N +2 f +(/)S +1 f +(2)S +12 s +576 3525(nodes,)N +848(where)X +1107(negamax)X +1479(would)X +1743(examine)X +2 f +2094(n)X +1 f +2182(nodes.)X +8 f +14 s +576 3729(3.2.)N +978(Mandatory)X +1648(work)X +1983(first)X +2385(\(MWF\))X +1 f +12 s +776 3870(This)N +974(algorithm)X +1376(was)X +1552(proposed)X +1931(by)X +2054(Akl,)X +2250(Barnard,)X +2612(and)X +2779(Doran)X +3047(as)X +3155(a)X +3226(parallel)X +3544(implementa-)X +576 3978(tion)N +762(of)X +878(alpha-beta)X +1316(without)X +1646(deep)X +1864(cutoffs.)X +2215(The)X +2401(name)X +2646(MWF)X +2910(was)X +3094(coined)X +3386(by)X +3517(Fishburn)X +3893(and)X +576 4086(Finkel.)N +908(MWF)X +1175(evaluates)X +1573(critical)X +1881(nodes)X +2144(concurrently)X +2670(and)X +2848(then)X +3053(returns)X +3359(to)X +3473(evaluate)X +3834(other)X +576 4194(nodes)N +838(if)X +935(needed)X +1232([6,)X +1352(7].)X +1518(When)X +1786(deep)X +2006(cutoffs)X +2311(are)X +2467(not)X +2628(considered)X +3083(in)X +3195(the)X +3350(search)X +3633(algorithm,)X +576 4302(only)N +771(type-1)X +1041(and)X +1204(type-2)X +1474(nodes)X +1722(are)X +1864(critical,)X +2181(as)X +2285(shown)X +2559(in)X +2658(Figure)X +2933(3.)X +776 4443(MWF)N +1032(evaluates)X +1418(type-1)X +1691(nodes)X +1942(completely,)X +2423(but)X +2574(only)X +2773(evaluates)X +3160(type-2)X +3434(nodes)X +3686(partially.)X +576 4551(After)N +814(the)X +967(eldest)X +1227(child)X +1455(of)X +1570(a)X +1648(type-1)X +1929(node)X +2150(\(also)X +2371(type-1\))X +2683(has)X +2845(been)X +3061(evaluated,)X +3489(the)X +3641(remaining)X +576 4659(children)N +916(\(all)X +1069(type-2\))X +1371(are)X +1513(completely)X +1966(evaluated)X +2360(only)X +2555(if)X +2639(the)X +2782(result)X +3021(of)X +3126(the)X +3269(partial)X +3541(evaluation)X +3968(is)X +576 4767(not)N +727(suf\256cient)X +1113(to)X +1216(cut)X +1361(them)X +1581(off.)X +1768(All)X +1918(evaluations)X +2384(currently)X +2759(allowed)X +3091(by)X +3214(MWF)X +3470(may)X +3663(be)X +3781(under-)X +576 4875(taken)N +809(simultaneously.)X +776 5016(Akl,)N +971(Barnard,)X +1332(and)X +1498(Doran)X +1762([6])X +1901(tested)X +2153(MWF)X +2409(with)X +2607(game)X +2844(trees)X +3054(of)X +3162(depth)X +3404(4)X +3480(and)X +3647(branching)X +576 5124(factors)N +875(of)X +992(5,)X +1101(10,)X +1258(15)X +1391(and)X +1567(20.)X +1748(They)X +1983(noticed)X +2304(that)X +2486(MWF)X +2752(has)X +2917(a)X +2997(better)X +3254(ef\256ciency)X +3670(when)X +3914(the)X +576 5232(game)N +818(tree)X +996(has)X +1157(a)X +1233(larger)X +1491(fanout,)X +1794(but)X +1950(found)X +2207(that)X +2385(the)X +2536(speedup)X +2884(reaches)X +3206(a)X +3282(plateau)X +3595(around)X +3896(six.)X +576 5340(The)N +765(total)X +976(number)X +1309(of)X +1428(nodes)X +1691(visited)X +1987(as)X +2106(well)X +2311(as)X +2429(the)X +2585(number)X +2917(of)X +3035(terminal)X +3395(nodes)X +3657(examined)X +576 5448(showed)N +903(an)X +1028(increase)X +1378(with)X +1584(increasing)X +2015(number)X +2344(of)X +2459(processors,)X +2923(but)X +3081(the)X +3234(plateau)X +3548(was)X +3732(reached)X +576 5556(much)N +814(faster.)X +776 5697(Fishburn)N +1141([4])X +1282(analyzed)X +1654(MWF)X +1912(for)X +2053(best-\256rst)X +2418(and)X +2586(worst-\256rst)X +3010(ordering)X +3366(of)X +3476(the)X +3624(game)X +3863(tree.)X +576 5805(In)N +688(the)X +838(best-\256rst)X +1206(ordering,)X +1588(MWF)X +1849(is)X +1945(almost)X +2234(optimal,)X +2585(since)X +2815(its)X +2938(ef\256ciency)X +3350(is)X +3446(very)X +3649(close)X +3878(to)X +3984(1)X + +7 p +%%Page: 7 7 +12 s 0 xH 0 xS 1 f +10 s +3 f +576 474(Game-tree)N +963(search)X +3992(7)X +1 f +12 s +577 876 MXY +1 setlinewidth +2284 MY +127 Dc +831 MX +127 Dc +703 MX +127 Dc +703 1836 MXY +127 Dc +959 2284 MXY +127 Dc +1215 MX +127 Dc +1087 MX +127 Dc +1343 MX +127 Dc +1599 MX +127 Dc +1471 MX +127 Dc +1727 MX +127 Dc +1983 MX +127 Dc +1855 MX +127 Dc +1855 1836 MXY +127 Dc +2111 2284 MXY +127 Dc +2367 MX +127 Dc +2239 MX +127 Dc +2495 MX +127 Dc +2751 MX +127 Dc +2623 MX +127 Dc +2623 1836 MXY +127 Dc +2239 MX +127 Dc +2879 2284 MXY +127 Dc +3135 MX +127 Dc +3007 MX +127 Dc +3007 1836 MXY +127 Dc +3263 2284 MXY +127 Dc +3519 MX +127 Dc +3391 MX +127 Dc +3647 MX +127 Dc +3903 MX +127 Dc +3775 MX +127 Dc +3775 1836 MXY +127 Dc +3391 MX +127 Dc +2239 940 MXY +127 Dc +3400 1357 MXY +-1046 -377 Dl +1207 1357 MXY +1046 -377 Dl +1087 1388 MXY +127 Dc +1119 1443 MXY +-325 335 Dl +1151 1452 MXY +0 320 Dl +1184 1443 MXY +325 335 Dl +2271 1443 MXY +-325 335 Dl +577 1443 MXY +[16] 0 setdash +2303 1452 MXY +0 320 Dl +2336 1443 MXY +325 335 Dl +577 1443 MXY +[] 0 setdash +3423 MX +-325 335 Dl +577 1443 MXY +[16] 0 setdash +3455 1452 MXY +0 320 Dl +3488 1443 MXY +325 335 Dl +577 1443 MXY +[] 0 setdash +2303 1324 MXY +0 -320 Dl +767 1900 MXY +0 320 Dl +753 1899 MXY +-101 323 Dl +782 1899 MXY +101 323 Dl +1137 1899 MXY +-101 323 Dl +577 1899 MXY +[16] 0 setdash +1166 MX +101 323 Dl +577 1899 MXY +[] 0 setdash +1521 MX +-101 323 Dl +577 1899 MXY +[16] 0 setdash +1550 MX +101 323 Dl +577 1899 MXY +[] 0 setdash +1905 MX +-101 323 Dl +1934 1899 MXY +101 323 Dl +577 1899 MXY +[16] 0 setdash +2289 MX +-101 323 Dl +2318 1899 MXY +101 323 Dl +2673 1899 MXY +-101 323 Dl +2702 1899 MXY +101 323 Dl +577 1899 MXY +[] 0 setdash +3057 MX +-101 323 Dl +3086 1899 MXY +101 323 Dl +577 1899 MXY +[16] 0 setdash +3441 MX +-101 323 Dl +3470 1899 MXY +101 323 Dl +3825 1899 MXY +-101 323 Dl +3854 1899 MXY +101 323 Dl +577 1899 MXY +[] 0 setdash +1471 1836 MXY +127 Dc +1087 MX +127 Dc +577 MX +[16] 0 setdash +1151 1900 MXY +0 320 Dl +1535 1900 MXY +0 320 Dl +2303 1900 MXY +0 320 Dl +2687 1900 MXY +0 320 Dl +3455 1900 MXY +0 320 Dl +3839 1900 MXY +0 320 Dl +577 1900 MXY +[] 0 setdash +2239 1388 MXY +127 Dc +3391 MX +127 Dc +1919 1900 MXY +0 320 Dl +5 f +2277 980(1)N +1125 1428(1)N +741 1876(1)N +614 2324(1)N +997(1)X +1765(1)X +1893 1876(1)N +3045(1)X +2917 2324(1)N +2277 1428(2)N +3429(2)X +1125 1876(2)N +1509(2)X +741 2324(2)N +869(2)X +1893(2)X +2021(2)X +3045(2)X +3173(2)X +1381(1)X +3071 1900 MXY +0 320 Dl +577 2348 MXY +3 setlinewidth +3 f +1059 2520(Figure)N +1 f +1356(3:)X +1455(Minimal)X +1811(subtree)X +2113(when)X +2345(deep)X +2551(cutoffs)X +2842(are)X +2984(not)X +3131(considered)X +576 2724(when)N +808(a)X +875(large)X +1092(number)X +1410(of)X +1514(processors)X +1943(is)X +2031(used.)X +2279(For)X +2437(the)X +2580(worst-\256rst)X +2999(ordering,)X +3374(Fishburn)X +3740(used)X +3941(an)X +576 2832(example)N +929(game)X +1163(tree)X +1333(of)X +1438(degree)X +1720(38)X +1841(and)X +2005(processor)X +2398(tree)X +2568(of)X +2673(fanout)X +2944(2)X +3017(to)X +3117(predict)X +3410(that)X +3580(speedup)X +3920(for)X +576 2940(MWF)N +829(will)X +1003(satisfy)X +2 f +1985 3096(p)N +1 f +9 s +2045 3057(0.93)N +2 f +12 s +9 f +2195 3096(\243)N +2 f +2272(S)X +9 f +2360(\243)X +2 f +2437(p)X +1 f +9 s +2497 3057(0.96)N +12 s +576 3252(where)N +2 f +835(p)X +1 f +923(is)X +1011(the)X +1153(number)X +1471(of)X +1575(processors.)X +2052(This)X +2247(result)X +2485(is)X +2573(almost)X +2854(as)X +2958(good)X +3174(as)X +3278(tree-splitting.)X +8 f +14 s +576 3456(3.3.)N +978(The)X +1246(tree-splitting)X +2251(algorithm)X +1 f +12 s +776 3597(Fishburn)N +1154(proposed)X +1543(this)X +1719(method)X +2045(as)X +2162(a)X +2242(natural)X +2547(parallel)X +2874(way)X +3071(to)X +3184(implement)X +3635(the)X +3791(alpha-)X +576 3705(beta)N +771(algorithm.)X +1228(The)X +1412(tree-splitting)X +1939(algorithm)X +2348(splits)X +2585(the)X +2736(game)X +2978(tree)X +3156(into)X +3339(its)X +3463(subtrees)X +3811(at)X +3914(the)X +576 3813(root)N +765(node,)X +1010(and)X +1183(each)X +1394(subtree)X +1706(is)X +1804(assigned)X +2169(to)X +2278(a)X +2355(pool)X +2560(of)X +2674(processors)X +3114(for)X +3261(evaluation)X +3687([4].)X +3882(The)X +576 3921(pool)N +788(will)X +979(evaluate)X +1342(the)X +1501(subtree)X +1820(in)X +1936(parallel)X +2267(if)X +2367(it)X +2462(has)X +2631(more)X +2870(than)X +3077(one)X +3257(processor.)X +3714(In)X +3834(other)X +576 4029(words,)N +860(the)X +1004(game)X +1239(tree)X +1410(is)X +1500(mapped)X +1831(to)X +1932(a)X +2001(processor)X +2395(tree.)X +2614(as)X +2720(shown)X +2996(in)X +3097(Figure)X +3374(4.)X +3497(Here)X +3711(we)X +3850(have)X +576 4137(a)N +646(binary)X +919(tree)X +1090(of)X +1196(processors)X +1627(with)X +1824(height)X +2091(two)X +2261(\(connected)X +2710(by)X +2832(heavy)X +3088(arcs\))X +3301(mapped)X +3632(onto)X +3829(a)X +3898(ter-)X +576 4245(nary)N +772(game)X +1006(tree.)X +1224(When)X +1479(there)X +1697(are)X +1840(more)X +2063(branches)X +2430(in)X +2530(the)X +2673(game)X +2907(tree)X +3077(than)X +3268(there)X +3486(are)X +3629(in)X +3729(the)X +3872(pro-)X +576 4353(cessor)N +851(tree,)X +1055(the)X +1208(extra)X +1436(game)X +1679(tree)X +1858(branches)X +2234(are)X +2386(queued)X +2698(and)X +2871(assigned)X +3236(to)X +3345(a)X +3422(processor)X +3824(when)X +576 4461(one)N +739(becomes)X +1100(available.)X +776 4602(All)N +930(interior)X +1245(processors)X +1681(in)X +1787(the)X +1937(tree)X +2114(of)X +2226(processors)X +2663(are)X +2813(both)X +3016(masters)X +3342(and)X +3513(slaves)X +3780(except)X +576 4710(the)N +728(root)X +917(processor,)X +1343(which)X +1612(is)X +1710(only)X +1915(a)X +1992(master.)X +2331(All)X +2488(the)X +2640(leaf)X +2819(processors)X +3258(are)X +3410(slaves.)X +3726(When)X +3989(a)X +576 4818(slave)N +804(processor)X +1202(\256nishes)X +1526(the)X +1675(search)X +1952(of)X +2063(its)X +2185(assigned)X +2547(subtree,)X +2880(it)X +2965(reports)X +3263(the)X +3412(value)X +3652(computed)X +576 4926(to)N +690(its)X +820(master.)X +1164(When)X +1433(a)X +1515(master)X +1811(processor)X +2218(receives)X +2573(a)X +2655(response)X +3030(from)X +3256(one)X +3434(of)X +3552(its)X +3681(slaves,)X +3978(it)X +576 5034(updates)N +896(its)X +1013(alpha-beta)X +1441(window)X +1776(and)X +1941(informs)X +2266(the)X +2410(other)X +2634(working)X +2980(slaves)X +3241(of)X +3347(this)X +3512(new)X +3699(window.)X +576 5142(The)N +752(new)X +938(window)X +1273(may)X +1465(allow)X +1705(the)X +1849(remaining)X +2266(work)X +2489(under)X +2734(the)X +2878(master)X +3161(to)X +3261(be)X +3377(cutoff.)X +3680(When)X +3935(all)X +576 5250(the)N +723(slaves)X +987(have)X +1198(\256nished,)X +1555(either)X +1804(by)X +1929(cutoff)X +2188(or)X +2298(by)X +2424(reporting)X +2807(their)X +3014(values,)X +3314(the)X +3462(master)X +3749(proces-)X +576 5358(sor)N +717(can)X +875(compute)X +1231(the)X +1373(value)X +1606(of)X +1710(its)X +1825(own)X +2014(position.)X +776 5499(Fishburn)N +1141([4])X +1280(calculates)X +1689(the)X +1835(speedup)X +2178(for)X +2318(the)X +2464(tree-splitting)X +2985(algorithm)X +3388(for)X +3528(two)X +3700(different)X +576 5607(orderings)N +978(of)X +1097(the)X +1254(game)X +1502(tree.)X +1734(Worst-\256rst)X +2189(ordering)X +2554(produces)X +2940(no)X +3075(alpha-beta)X +3516(cutoffs.)X +3870(It)X +3968(is)X +576 5715(achieved)N +947(by)X +1071(sorting)X +1366(all)X +1491(children)X +1835(of)X +1943(all)X +2068(nodes)X +2320(so)X +2433(that)X +2607(whenever)X +3010(the)X +3157(call)X +3326(alphabeta\()X +2 f +3728(z)X +1 f +3781(,)X +2 f +9 f +3834(a)X +1 f +3894(,)X +2 f +9 f +3947(b)X +1 f +4000(\))X + +8 p +%%Page: 8 8 +12 s 0 xH 0 xS 1 f +10 s +3 f +576 474(Game-tree)N +963(search)X +3992(8)X +1 f +12 s +577 876 MXY +1 setlinewidth +1215 2284 MXY +127 Dc +1087 MX +127 Dc +1343 MX +127 Dc +1599 MX +127 Dc +1471 MX +127 Dc +2111 MX +127 Dc +2367 MX +127 Dc +2239 MX +127 Dc +2495 MX +127 Dc +2751 MX +127 Dc +2623 MX +127 Dc +2623 1836 MXY +127 Dc +2239 MX +127 Dc +3263 2284 MXY +127 Dc +3519 MX +127 Dc +3391 MX +127 Dc +3647 MX +127 Dc +3903 MX +127 Dc +3775 MX +127 Dc +3775 1836 MXY +127 Dc +3391 MX +127 Dc +3400 1357 MXY +-1046 -377 Dl +577 1357 MXY +10 setlinewidth +1207 MX +1046 -377 Dl +1119 1443 MXY +-325 335 Dl +1151 1452 MXY +0 320 Dl +577 1452 MXY +1 setlinewidth +1184 1443 MXY +325 335 Dl +577 1443 MXY +10 setlinewidth +2271 MX +-325 335 Dl +2303 1452 MXY +0 320 Dl +577 1452 MXY +1 setlinewidth +2336 1443 MXY +325 335 Dl +3423 1443 MXY +-325 335 Dl +3455 1452 MXY +0 320 Dl +3488 1443 MXY +325 335 Dl +577 1443 MXY +10 setlinewidth +2303 1324 MXY +0 -320 Dl +577 1324 MXY +1 setlinewidth +767 1900 MXY +0 320 Dl +753 1899 MXY +-101 323 Dl +782 1899 MXY +101 323 Dl +1137 1899 MXY +-101 323 Dl +1166 1899 MXY +101 323 Dl +1521 1899 MXY +-101 323 Dl +1550 1899 MXY +101 323 Dl +1905 1899 MXY +-101 323 Dl +1934 1899 MXY +101 323 Dl +2289 1899 MXY +-101 323 Dl +2318 1899 MXY +101 323 Dl +2673 1899 MXY +-101 323 Dl +2702 1899 MXY +101 323 Dl +3057 1899 MXY +-101 323 Dl +3086 1899 MXY +101 323 Dl +3441 1899 MXY +-101 323 Dl +3470 1899 MXY +101 323 Dl +3825 1899 MXY +-101 323 Dl +3854 1899 MXY +101 323 Dl +1151 1900 MXY +0 320 Dl +1535 1900 MXY +0 320 Dl +2303 1900 MXY +0 320 Dl +2687 1900 MXY +0 320 Dl +3455 1900 MXY +0 320 Dl +3839 1900 MXY +0 320 Dl +1919 1900 MXY +0 320 Dl +1087 1388 MXY +127 Dc +2239 940 MXY +127 Dc +2239 1388 MXY +127 Dc +703 1836 MXY +127 Dc +1087 MX +127 Dc +1471 MX +127 Dc +1855 MX +127 Dc +1855 2284 MXY +127 Dc +1983 MX +127 Dc +1727 MX +127 Dc +959 MX +127 Dc +831 MX +127 Dc +703 MX +127 Dc +577 MX +127 Dc +3007 MX +127 Dc +3135 MX +127 Dc +3007 1836 MXY +127 Dc +3391 1388 MXY +127 Dc +2879 2284 MXY +127 Dc +577 2348 MXY +3 setlinewidth +3 f +1372 2520(Figure)N +1 f +1669(4:)X +1768(Processor)X +2165(tree)X +2334(mapped)X +2663(onto)X +2858(game)X +3091(tree)X +576 2724(is)N +664(made,)X +921(the)X +1063(following)X +1461(relation)X +1780(holds)X +2012(among)X +2298(the)X +2440(children)X +2 f +2780(z)X +1 f +9 s +2829 2748(1)N +12 s +2889 2724(,...,)N +2 f +3033(z)X +9 s +3070 2748(d)N +1 f +12 s +3122 2724(:)N +2 f +9 f +1445 2886(a)N +2 f +1529(<)X +9 f +1618(-)X +1 f +1671(negamax\()X +2 f +2051(z)X +1 f +9 s +2100 2910(1)N +12 s +2886(\))Y +2 f +2192(<)X +1 f +2257(...)X +2 f +2353(<)X +9 f +2442(-)X +1 f +2495(negamax\()X +2 f +2875(z)X +9 s +2912 2910(d)N +1 f +12 s +2964 2886(\))N +2 f +3020(<)X +9 f +3109(b)X +1 f +576 3048(Since)N +822(there)X +1047(are)X +1197(no)X +1325(cutoffs,)X +1648(there)X +1873(is)X +1969(no)X +2097(speculative)X +2564(loss,)X +2770(so)X +2888(tree)X +3066(splitting)X +3415(achieves)X +3780(practi-)X +576 3156(cally)N +788(perfect)X +1080(speedup.)X +776 3297(Best-\256rst)N +1178(ordering)X +1554(produces)X +1952(the)X +2121(maximum)X +2563(number)X +2908(of)X +3039(alpha-beta)X +3492(cutoffs.)X +3858(It)X +3968(is)X +576 3405(achieved)N +943(by)X +1063(sorting)X +1354(all)X +1475(children)X +1815(of)X +1919(all)X +2040(nodes)X +2288(so)X +2397(that:)X +1121 3561(negamax\()N +2 f +1501(z)X +1 f +1554(\))X +2 f +9 f +1610(=)X +1687(-)X +1 f +1740(negamax\()X +2 f +2120(z)X +1 f +9 s +2169 3585(1)N +12 s +3561(\))Y +2261(for)X +2397(all)X +2518(nodes)X +2 f +2766(z)X +1 f +2843(in)X +2942(the)X +3084(game)X +3317(tree.)X +576 3723(Using)N +829(this)X +992(ordering,)X +1366(the)X +1508(tree-splitting)X +2025(algorithm)X +2424(gives)X +2 f +2651(S)X +9 f +2739(=)X +1 f +2816(O\()X +2 f +2917(p)X +1 f +9 s +2977 3684(1)N +2 f +(/)S +1 f +(2)S +12 s +3723(\))Y +3125(with)X +2 f +3320(p)X +1 f +3408(processors.)X +776 3864(The)N +950(tree-splitting)X +1467(algorithm)X +1866(gives)X +2 f +2093(S)X +9 f +2181(=)X +1 f +2258(O\()X +2 f +2359(p)X +1 f +9 s +2419 3825(1)N +2 f +(/)S +1 f +(2)S +12 s +3864(\))Y +2567(with)X +2 f +2762(p)X +1 f +2850(processors)X +3279(when)X +3511(best-\256rst)X +3872(ord-)X +576 3972(ering)N +798([4])X +934(of)X +1038(the)X +1180(game)X +1413(tree)X +1582(is)X +1670(used.)X +8 f +14 s +576 4176(3.4.)N +978 -0.1979(Principal-variation)AX +2318(\(PV\))X +2653(splitting)X +1 f +12 s +776 4317(PV)N +931(splitting)X +1281(is)X +1379(a)X +1456(re\256nement)X +1902(of)X +2016(the)X +2168(tree-splitting)X +2695(algorithm)X +3094([8].)X +3288(It)X +3381(assumes)X +3735(that)X +3914(the)X +576 4425(search)N +860(tree)X +1043(is)X +1145(mapped)X +1488(onto)X +1697(an)X +1826(underlying)X +2281(tree)X +2464(of)X +2582(processors)X +3025(and)X +3202(that)X +3385(the)X +3540(game)X +3786(tree)X +3968(is)X +576 4533(strongly)N +921(ordered,)X +1269(that)X +1444(is,)X +1562(the)X +1710(\256rst)X +1889(branch)X +2181(of)X +2292(each)X +2500(node)X +2718(is)X +2813(the)X +2962(best)X +3148(branch)X +3441(at)X +3542(least)X +3750(70)X +3877(per-)X +576 4641(cent)N +780(of)X +903(the)X +1064(time)X +1279(and)X +1461(that)X +1649(the)X +1810(best)X +2007(move)X +2263(is)X +2369(in)X +2486(the)X +2646(\256rst)X +2837(quarter)X +3152(of)X +3274(the)X +3434(branches)X +3818(being)X +576 4749(searched)N +937(90)X +1057(percent)X +1365(of)X +1469(the)X +1611(time.)X +776 4890(The)N +962(type-1)X +1244(nodes)X +1504(are)X +1658(recursively)X +2122(evaluated)X +2528(until)X +2741(a)X +2820(given)X +3070(ply)X +3229(is)X +3329(reached,)X +3690(at)X +3797(which)X +576 4998(point)N +813(tree)X +997(splitting)X +1351(is)X +1453(used.)X +1715(After)X +1956(the)X +2112(value)X +2359(of)X +2477(the)X +2633(principal)X +3014(variation)X +3395(\(type-1\))X +3743(node)X +3968(is)X +576 5106(backed)N +874(up)X +995(the)X +1138(tree,)X +1332(tree)X +1503(splitting)X +1845(is)X +1935(used)X +2137(to)X +2238(evaluate)X +2586(the)X +2730(remaining)X +3147(siblings)X +3472(if)X +3557(they)X +3749(can)X +3909(not)X +576 5214(be)N +691(cut)X +833(off.)X +776 5355(There)N +1049(are)X +1215(two)X +1407(differences)X +1883(between)X +2252(PV)X +2422(splitting)X +2786(and)X +2973(MWF.)X +3298(First,)X +3546(PV)X +3716(splitting)X +576 5463(requires)N +918(a)X +993(particular)X +1395(underlying)X +1844(processor)X +2244(structure,)X +2637(in)X +2744(contrast)X +3081(with)X +3284(the)X +3434(pool)X +3637(of)X +3749(proces-)X +576 5571(sors)N +757(used)X +960(in)X +1062(MWF.)X +1366(Second,)X +1700(it)X +1781(waits)X +2011(for)X +2150(the)X +2295(search)X +2569(of)X +2677(type-1)X +2951(nodes)X +3203(to)X +3306(end)X +3473(before)X +3747(it)X +3829(starts)X +576 5679(evaluating)N +1015(the)X +1170(other)X +1405(nodes.)X +1714(This)X +1922(aspect)X +2200(of)X +2317(PV)X +2476(splitting)X +2829(ensures)X +3154(that)X +3336(the)X +3491(best)X +3683(available)X +576 5787(value)N +809(of)X +2 f +9 f +913(a)X +1 f +997(is)X +1085(passed)X +1365(to)X +1464(the)X +1606(other)X +1828(nodes)X +2076(of)X +2180(the)X +2322(tree.)X + +9 p +%%Page: 9 9 +12 s 0 xH 0 xS 1 f +10 s +3 f +576 474(Game-tree)N +963(search)X +3992(9)X +1 f +12 s +776 780(PV)N +935(splitting)X +1288(was)X +1474(compared)X +1892 0.2404(experimentally)AX +2509(with)X +2718(the)X +2874(tree)X +3057(splitting)X +3411(algorithm)X +3824(using)X +576 888(trees)N +790(of)X +901(depth)X +1146(4)X +1225(and)X +1395(width)X +1645(24.)X +1820(Experimental)X +2371(results)X +2653(show)X +2886(that)X +3062(PV)X +3215(splitting)X +3562(outperforms)X +576 996(tree)N +755(splitting,)X +1129(especially)X +1549(when)X +1791(a)X +1868(wider)X +2121(processor)X +2523(tree)X +2702(is)X +2800(used)X +3000([8].)X +3194(For)X +3361(example,)X +3746(when)X +3989(a)X +576 1104(processor)N +986(tree)X +1173(with)X +1386(both)X +1599(depth)X +1855(and)X +2036(width)X +2297(of)X +2418(2)X +2507(was)X +2697(used,)X +2938(tree-splitting)X +3472(examined)X +3888(912)X +576 1212(nodes,)N +855(and)X +1025(PV)X +1178(splitting)X +1526(examined)X +1933(648)X +2109(nodes.)X +2413(But)X +2584(when)X +2824(the)X +2974(width)X +3225(of)X +3337(the)X +3487(processor)X +3887(tree)X +576 1320(was)N +761(changed)X +1118(to)X +1229(8,)X +1337(tree-splitting)X +1866(and)X +2041(PV)X +2199(splitting)X +2551(examined)X +2962(772)X +3142(and)X +3316(277)X +3495(nodes)X +3754(respec-)X +576 1428(tively.)N +8 f +14 s +576 1632(3.5.)N +978(The)X +1246(ER)X +1447(algorithm)X +1 f +12 s +776 1773(This)N +977(algorithm)X +1382(was)X +1561(developed)X +1987(by)X +2113(Steinberg)X +2512(and)X +2681(Solomon)X +3058(for)X +3200(parallel)X +3520(evaluation)X +3952(of)X +576 1881(game)N +812(trees.)X +1069(It)X +1155(is)X +1246(a)X +1315(sequential)X +1732(algorithm)X +2133(with)X +2330(a)X +2399(parallel)X +2715 0.2548(implementation)AX +3345([3].)X +3531(The)X +3707(nodes)X +3957(in)X +576 1989(the)N +728(game)X +971(tree)X +1150(are)X +1302(divided)X +1626(into)X +1811(two)X +1990(groups,)X +2310(e-nodes)X +2644(and)X +2818(r-nodes.)X +3189(E-nodes)X +3539(will)X +3724(be)X +3850(fully)X +576 2097(evaluated,)N +997(and)X +1163(r-nodes)X +1478(will)X +1655(be)X +1773(refuted,)X +2097(that)X +2269(is,)X +2384(will)X +2561(have)X +2770(an)X +2888(estimated)X +3284(value.)X +3567(All)X +3716(children)X +576 2205(of)N +688(an)X +811(e-node)X +1105(are)X +1255(evaluated,)X +1681(but)X +1836(as)X +1948(few)X +2124(as)X +2236(one)X +2407(child)X +2632(of)X +2744(an)X +2867(r-node)X +3150(needs)X +3401(to)X +3509(be)X +3633(examined.)X +576 2313(Therefore)N +985(e-nodes)X +1313(are)X +1460(more)X +1687(``costly'')X +2074(than)X +2269(r-nodes.)X +2634(Every)X +2892(internal)X +3215(node)X +3430(has)X +3586(exactly)X +3893(one)X +576 2421(e-node)N +862(child)X +1079(\(e-child\).)X +776 2562(Any)N +980(child)X +1212(of)X +1331(a)X +1413(node)X +1639(can)X +1812(be)X +1942(chosen)X +2248(as)X +2368(the)X +2526(e-child,)X +2858(but)X +3021(the)X +3179(child)X +3412(with)X +3623(the)X +3781(lowest)X +576 2670(negamax)N +948(value)X +1181(is)X +1269(the)X +1411(best)X +1590(choice)X +1866([3].)X +776 2811(To)N +907(choose)X +1198(the)X +1340(e-child)X +1633(of)X +1738(a)X +1806(node)X +2 f +2018(z)X +1 f +2071(,)X +2120(ER)X +2268(evaluates)X +2652(the)X +2795(elder)X +3013(grandchildren)X +3573(\(eldest)X +3855(chil-)X +576 2919(dren)N +778(of)X +2 f +889(z)X +1 f +942('s)X +1042(children\))X +1421(in)X +1527(parallel,)X +1872(and)X +2042(chooses)X +2377(the)X +2525(child)X +2748(whose)X +3023(elder)X +3246(child)X +3469(has)X +3627(the)X +3775(largest)X +576 3027(value.)N +874(The)X +1066(e-child)X +1376(is)X +1482(then)X +1690(evaluated)X +2102(while)X +2358(avoiding)X +2737(re-evaluation)X +3288(of)X +3410(its)X +3543(oldest)X +3815(child,)X +576 3135(since)N +798(we)X +934(just)X +1097(got)X +1244(its)X +1359(value.)X +1640(The)X +1814(remaining)X +2229(children)X +2569(are)X +2711(refuted)X +3008(in)X +3107(order.)X +776 3276(In)N +890(the)X +1043(parallel)X +1368 0.2548(implementation)AX +2009(of)X +2124(ER,)X +2306(the)X +2459(elder)X +2687(grandchildren)X +3257(can)X +3426(be)X +3552(evaluated)X +3957(in)X +576 3384(parallel)N +906(because)X +1251(they)X +1457(represent)X +1850(mandatory)X +2302(work.)X +2586(Since)X +2839(these)X +3076(grandchildren)X +3650(are)X +3807(them-)X +576 3492(selves)N +849(e-nodes,)X +1210(their)X +1425(elder)X +1657(grandchildren)X +2231(can)X +2404(also)X +2598(be)X +2728(recursively)X +3195(evaluated)X +3604(in)X +3718(parallel.)X +576 3600(These)N +836(parallel)X +1156(evaluations)X +1625(are)X +1773(mandatory)X +2215(work,)X +2466(but)X +2619(if)X +2708(ER)X +2860(is)X +2953(to)X +3057(perform)X +3396(only)X +3596(the)X +3743(manda-)X +576 3708(tory)N +758(work,)X +1006(the)X +1151(remaining)X +1569(siblings)X +1895(of)X +2002(an)X +2120(e-node)X +2409(must)X +2623(be)X +2741(examined)X +3143(sequentially.)X +3684(To)X +3818(avoid)X +576 3816(these)N +798(sequential)X +1213(evaluations)X +1676(and)X +1839(thus)X +2023(starvation)X +2427(loss,)X +2624(ER)X +2771(uses)X +2960(the)X +3102(following)X +3500(two)X +3668(methods:)X +10 f +624 3957(g)N +1 f +706(Parallel)X +1030(refutation:)X +1461(After)X +1693(an)X +1813(e-child)X +2 f +2110(y)X +1 f +2198(of)X +2307(an)X +2427(e-node)X +2 f +2719(z)X +1 f +2802(is)X +2896(evaluated,)X +3320(refute)X +2 f +3575(y)X +1 f +3634('s)X +3733(siblings)X +706 4065(in)N +822(parallel.)X +1201(This)X +1413(parallel)X +1744(evaluation)X +2187(is)X +2291(likely)X +2551(to)X +2666(encounter)X +3086(lots)X +3265(of)X +3385(speculative)X +3859(loss.)X +706 4173(This)N +915(work)X +1150(is)X +1252(similar)X +1558(to)X +1671(the)X +1827(speculative)X +2299(work)X +2534(performed)X +2974(by)X +3109(MWF)X +3377(and)X +3555(PV)X +3716(splitting)X +706 4281(algorithms.)N +10 f +624 4389(g)N +1 f +706(Multiple)X +1064(e-children:)X +1508(After)X +1737(an)X +1854(e-child)X +2148(of)X +2254(an)X +2371(e-node)X +2 f +2659(z)X +1 f +2738(is)X +2828(evaluated,)X +3248(choose)X +3541(the)X +3685(next)X +3877(best)X +706 4497(child)N +933(of)X +2 f +1047(z)X +1 f +1134(as)X +1248(a)X +1325(second)X +1626(e-child.)X +1976(If)X +2074(it)X +2162(happens)X +2510(that)X +2688(the)X +2839(\256rst)X +3021(e-child)X +3322(is)X +3419(not)X +3575(actually)X +3914(the)X +706 4605(best)N +892(child)X +1116(of)X +2 f +1227(z)X +1 f +1311(\(other)X +1572(children)X +1919(cannot)X +2207(be)X +2329(immediately)X +2843(refuted\),)X +3203(we)X +3347(will)X +3529(have)X +3743(another)X +706 4713(e-child)N +1001(that)X +1173(will)X +1350(hopefully)X +1746(help)X +1939(us)X +2051(cut)X +2196(off)X +2 f +2334(z)X +1 f +2387('s)X +2482(other)X +2706(children.)X +3096(In)X +3202(general,)X +3536(after)X +3739(the)X +3883(\256rst)X +706 4821(e-child)N +998(has)X +1150(been)X +1356(evaluated,)X +1774(ensure)X +2049(that)X +2 f +2218(z)X +1 f +2295(always)X +2586(has)X +2738(one)X +2901(active)X +3156(e-child.)X +776 4962(Steinberg)N +1189(and)X +1372(Solomon)X +1764(compared)X +2189(ER)X +2357(to)X +2477(PV)X +2644(splitting.)X +3053(Sequential)X +3505(ER)X +3673(evaluates)X +576 5070(more)N +811(nodes)X +1072(than)X +1275(alpha-beta,)X +1737(but)X +1896(sequential)X +2323(PV)X +2481(splitting)X +2833(is)X +2933(identical)X +3302(to)X +3413(alpha-beta.)X +3899(For)X +576 5178(this)N +751(reason)X +1038(Steinberg)X +1444(and)X +1620(Solomon)X +1991([3])X +2140(used)X +2353(relative)X +2680(ef\256ciency)X +3097(and)X +3273(relative)X +3600(speedup)X +3952(as)X +576 5286(shown)N +850(below)X +1109(to)X +1208(compare)X +1564(the)X +1706(two)X +1874(algorithms.)X +2 f +1435 5478(relative)N +1770(ef\256ciency)X +9 f +2151(=)X +2 f +2228 5547(no.)N +2388(of)X +2519(processors)X +2974(used)X +2364 5424(relative)N +2699(speedup)X +10 f +2213 5451(h)N +2252(hhhhhhhhhhhhhhhhhhh)X + +10 p +%%Page: 10 10 +12 s 0 xH 0 xS 10 f +10 s +3 f +576 474(Game-tree)N +963(search)X +3952(10)X +2 f +12 s +857 816(relative)N +1192(speedup)X +9 f +1523(=)X +2 f +1948 885(time)N +2154(required)X +2525(by)X +2656(parallel)X +3001(algorithm)X +1600 762(time)N +1806(required)X +2177(by)X +2308(parallel)X +2653(algorithm)X +3072(with)X +1 f +3278(1)X +2 f +3350(processor)X +10 f +1585 789(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)N +1 f +576 1023(Experiments)N +1091(show)X +1321(that)X +1494(ER)X +1645(achieves)X +2005(twice)X +2242(the)X +2388(ef\256ciency)X +2797(and)X +2965(speedup)X +3309(of)X +3418(the)X +3565(PV)X +3716(splitting)X +576 1131(algorithm)N +983(when)X +1223(used)X +1431(on)X +1559(suf\256ciently)X +2024(deep)X +2238(trees)X +2444([3].)X +2636(The)X +2818(average)X +3150(ef\256ciency)X +3562(achieved)X +3936(by)X +576 1239(ER)N +725(using)X +959(16)X +1082(processors)X +1514(for)X +1653(7,)X +1752(8,)X +1851(9,)X +1950(and)X +2116(10)X +2239(ply)X +2389(trees)X +2598(are)X +2743(respectively)X +3236(0.44,)X +3455(0.52,)X +3674(0.68,)X +3893(and)X +576 1347(0.58.)N +820(The)X +997(corresponding)X +1574(ef\256ciencies)X +2040(for)X +2179(PV)X +2328(splitting)X +2671(are)X +2816(0.28,)X +3035(0.31,)X +3254(0.31,)X +3473(and)X +3639(0.31.)X +3882(The)X +576 1455(range)N +817(of)X +924(speedup)X +1266(for)X +1405(7)X +1480(to)X +1582(9)X +1657(ply)X +1807(trees)X +2016(using)X +2251(16)X +2374(processors)X +2806(are)X +2951(7.1)X +3098(to)X +3201(10.9)X +3397(for)X +3537(the)X +3683(ER)X +3834(algo-)X +576 1563(rithm)N +821(and)X +995(4.5)X +1150(to)X +1260(5.0)X +1415(for)X +1562(the)X +1715(PV)X +1872(splitting)X +2223(algorithm.)X +2681(Steinberg)X +3085(and)X +3259(Solomon)X +3641(contribute)X +576 1671(ER's)N +792(higher)X +1062(ef\256ciency)X +1466(to)X +1565(low)X +1733(starvation)X +2137(loss.)X +8 f +14 s +576 1875(3.6.)N +978(Delay)X +1380(splitting)X +1 f +12 s +776 2016(This)N +984(algorithm)X +1396(delays)X +1679(the)X +1834(evaluation)X +2273(of)X +2390(each)X +2604(node)X +2828(until)X +3042(its)X +3170(eldest)X +3432(sibling)X +3732(is)X +3834(com-)X +576 2124(pletely)N +868(evaluated.)X +1315(Starvation)X +1740(loss)X +1918(is)X +2011(accepted)X +2378(in)X +2482(order)X +2714(to)X +2818(increase)X +3163(the)X +3310(number)X +3633(of)X +3741(cutoffs.)X +576 2232(Evaluation)N +1031(delay)X +1278(occurs)X +1567(at)X +1675(every)X +1927(level)X +2153(for)X +2303(each)X +2518(node,)X +2767(thus)X +2965(making)X +3292(delay)X +3539(splitting)X +3893(dif-)X +576 2340(ferent)N +839(from)X +1064(PV)X +1224(splitting,)X +1601(in)X +1713(which)X +1985(delay)X +2231(of)X +2348(evaluation)X +2787(occurs)X +3075(only)X +3283(along)X +3534(the)X +3689(principle)X +576 2448(variation)N +943(route.)X +776 2589(The)N +950(following)X +1348(is)X +1436(Pascal-like)X +1883(code)X +2089(for)X +2225(delay)X +2458(splitting:)X +3 f +10 s +896 2712(function)N +7 f +1228(DelaySplit\(z)X +1852(:)X +1948(position;)X +2 f +12 s +9 f +2428(a)X +7 f +10 s +2488(,)X +2 f +12 s +9 f +2584(b)X +7 f +10 s +2637(\):)X +2781(integer;)X +3 f +1184 2802(var)N +7 f +1348(d,)X +1492(i)X +1588(:)X +1684(integer;)X +1472 2892(value)N +1760(:)X +3 f +1856(array)X +7 f +2048([1..MAXWIDTH])X +2720(of)X +2864(integer;)X +3 f +1184 2982(begin)N +1472 3072(if)N +7 f +1569(\(I)X +1713(am)X +1857(a)X +1953(leaf)X +2193(processor\))X +3 f +2721(then)X +1760 3162(return)N +7 f +1983(\(alphabeta\(z,)X +2 f +12 s +9 f +2655(a)X +7 f +10 s +2715(,)X +2 f +12 s +9 f +2811(b)X +7 f +10 s +2864(\)\);)X +1472 3252(determine)N +1952(the)X +2144(child)X +2432(positions)X +2 f +12 s +2912(z)X +1 f +9 s +2961 3276(1)N +7 f +10 s +3252(,)Y +3093(...,)X +2 f +12 s +3333(z)X +9 s +3370 3276(d)N +12 s +9 f +1472 3348(a)N +7 f +10 s +1580(=)X +1676(-DelaySplit\()X +2 f +12 s +(z)S +1 f +9 s +2301 3372(1)N +7 f +10 s +3348(,)Y +2 f +12 s +9 f +2433(-b)X +7 f +10 s +2539(,)X +2 f +12 s +9 f +2635(-a)X +7 f +10 s +2748(\);)X +3 f +1472 3444(if)N +2 f +12 s +9 f +1569(a)X +1653(\263)X +1730(b)X +3 f +10 s +1831(then)X +1760 3534(return)N +7 f +1983(\()X +2 f +12 s +9 f +(a)S +7 f +10 s +2091(\);)X +3 f +1472 3624(for)N +7 f +1623(i)X +1719(:=)X +1863(2)X +3 f +1959(to)X +7 f +2074(d)X +3 f +2170(do)X +2274(in)X +2360(parallel)X +1760 3714(begin)N +7 f +1760 3804(value[i])N +2192(:=)X +2336(-DelaySplit\()X +2 f +12 s +(z)S +9 s +2949 3828(i)N +7 f +10 s +2985 3804(,)N +2 f +12 s +9 f +3081(-b)X +7 f +10 s +3187(,)X +2 f +12 s +9 f +3283(-a)X +7 f +10 s +3396(\);)X +3 f +1760 3900(begincrit)N +7 f +2115({critical)X +2595(region)X +2931(})X +3 f +2048 3990(if)N +7 f +2145(value[i])X +2577(>)X +2 f +12 s +9 f +2673(a)X +3 f +10 s +2781(then)X +2 f +12 s +9 f +2336 4080(a)N +7 f +10 s +2444(:=)X +2588(value[i];)X +3 f +1760 4170(endcrit)N +7 f +2005(;)X +3 f +1760 4260(if)N +2 f +12 s +9 f +1857(a)X +1941(\263)X +2018(b)X +3 f +10 s +2119(then)X +2048 4350(return)N +7 f +2271(\()X +2 f +12 s +9 f +(a)S +7 f +10 s +2379(\);)X +2523({)X +2619(cutoff)X +2955(})X +3 f +1760 4440(end)N +7 f +1884(;)X +3 f +1184 4530(end)N +7 f +1308(.)X +1404({)X +1500(DelaySplit)X +2028(})X +8 f +14 s +576 4767(4.)N +844(Experimental)X +1715(results)X +1 f +12 s +776 4908(We)N +935(have)X +1143(tested)X +1394(the)X +1538(above)X +1794(algorithms)X +2232(on)X +2354(a)X +2423(Sequent)X +2759(Symmetry)X +3186(with)X +3383(26)X +3505(cpus)X +3707(using)X +3941(an)X +576 5016(unsorted)N +941(tree)X +1120(of)X +1234(depth)X +1482(9)X +1564(and)X +1737(fanout)X +2017(of)X +2131(at)X +2235(most)X +2456(15)X +2586(\(the)X +2770(fanout)X +3049(decreases)X +3451(by)X +3580(one)X +3752(at)X +3855(each)X +576 5124(level\))N +825(generated)X +1229(by)X +1354(the)X +1501(game)X +1739(tic-tac-toe.)X +2208(The)X +2387(algorithms)X +2828(tend)X +3023(to)X +3127(have)X +3338(more)X +3565(cutoffs)X +3861(with)X +576 5232(a)N +647(sorted)X +910(tree,)X +1107(but)X +1258(are)X +1404(likely)X +1652(to)X +1755(have)X +1965(a)X +2036(higher)X +2310(ef\256ciency)X +2717(with)X +2915(a)X +2985(worst-\256rst)X +3406(sorted)X +3668(tree.)X +3888(Not)X +576 5340(sorting)N +871(at)X +969(all)X +1094(gives)X +1325(us)X +1438(a)X +1509(comparison)X +1986(with)X +2185(a)X +2256(reasonable)X +2696(amount)X +3013(of)X +3121(cutoff)X +3380(and)X +3548(a)X +3620(reasonable)X +576 5448(amount)N +914(of)X +1043(parallelism.)X +1569(The)X +1768(relative)X +2107(ef\256ciency)X +2536(comparisons)X +3071(are)X +3238(shown)X +3537(in)X +3661(Figure)X +3960(5.)X +576 5556(\(Relative)N +954(ef\256ciency)X +1358(compares)X +1751(the)X +1893(parallel)X +2207(execution)X +2606(time)X +2802(to)X +2901(the)X +3044(sequential)X +3460(execution)X +3860(time)X +576 5664(of)N +692(the)X +846(same)X +1079(algorithm)X +1489(in)X +1599(the)X +1752(same)X +1985(environment.)X +2555(The)X +2740(sequential)X +3166(execution)X +3576(times)X +3820(of)X +3935(all)X +576 5772(algorithms)N +1031(we)X +1186(tested)X +1455(are)X +1617(quite)X +1854(similar.\))X +2246(For)X +2423(this)X +2606(particular)X +3020(test,)X +3222(the)X +3384(MWF)X +3657(algorithm)X + +11 p +%%Page: 11 11 +12 s 0 xH 0 xS 1 f +10 s +3 f +576 474(Game-tree)N +963(search)X +3952(11)X +1 f +12 s +576 780(achieved)N +961(an)X +1094(almost)X +1393(perfect)X +1703(ef\256ciency,)X +2149(followed)X +2532(by)X +2669(delay)X +2919(splitting)X +3276(and)X +3456(ER)X +3620(algorithms)X +576 888(with)N +772(speedup)X +1112(of)X +1217(over)X +1413(12)X +1534(and)X +1698(9)X +1772(respectively,)X +2288(using)X +2522(20)X +2644(processors.)X +3123(We)X +3283(attribute)X +3631(our)X +3785(ability)X +576 996(to)N +685(exceed)X +987(a)X +1064(speedup)X +1413(of)X +1527(6)X +1609(with)X +1814(MWF)X +2077(to)X +2186(DIB's)X +2454 0.2723(parallelization)AX +3041(environment)X +3562(and)X +3735(the)X +3887(tree)X +576 1104(structure)N +937(used)X +1137(in)X +1236(this)X +1399(experiment.)X +776 1245(Figure)N +1056(6)X +1133(shows)X +1402(the)X +1550(ratio)X +1757(of)X +1867(the)X +2015(number)X +2339(of)X +2449(nodes)X +2703(examined)X +3108(by)X +3234(the)X +3382(algorithms)X +3824(using)X +576 1353(different)N +932(numbers)X +1287(of)X +1391(machines)X +1779(verses)X +2043(using)X +2275(one)X +2438(machine)X +2789(\(sequential)X +3236(algorithm\).)X +977 1537 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1090 1717 MXY +0 29 Dl +0 -14 Dl +15 0 Dl +-29 0 Dl +1316 2412 MXY +0 29 Dl +0 -14 Dl +15 0 Dl +-29 0 Dl +1542 2591 MXY +0 29 Dl +0 -15 Dl +15 0 Dl +-29 0 Dl +1768 2800 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1994 2919 MXY +0 29 Dl +0 -15 Dl +14 0 Dl +-28 0 Dl +2220 2856 MXY +0 29 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +2446 2935 MXY +0 29 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +2672 3097 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +2898 3176 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-29 0 Dl +3124 3238 MXY +0 29 Dl +0 -15 Dl +14 0 Dl +-29 0 Dl +920 3238 MXY +[16] 0 setdash +1 setlinewidth +977 1551 MXY +113 181 Dl +226 695 Dl +226 178 Dl +226 209 Dl +226 119 Dl +226 -62 Dl +226 79 Dl +226 161 Dl +226 79 Dl +226 62 Dl +5 f +3125 3292(alphabeta)N +920 1551 MXY +[] 0 setdash +3 setlinewidth +977 1537 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1090 1560 MXY +0 28 Dl +0 -14 Dl +15 0 Dl +-29 0 Dl +1316 1669 MXY +0 29 Dl +0 -14 Dl +15 0 Dl +-29 0 Dl +1542 1593 MXY +0 29 Dl +0 -14 Dl +15 0 Dl +-29 0 Dl +1768 1653 MXY +0 29 Dl +0 -15 Dl +14 0 Dl +-28 0 Dl +1994 1537 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +2220 1726 MXY +0 29 Dl +0 -15 Dl +14 0 Dl +-28 0 Dl +2446 1605 MXY +0 29 Dl +0 -15 Dl +14 0 Dl +-28 0 Dl +2672 1613 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +2898 1834 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-29 0 Dl +3124 1633 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-29 0 Dl +977 1551 MXY +113 23 Dl +226 110 Dl +226 -76 Dl +226 59 Dl +226 -116 Dl +226 189 Dl +226 -121 Dl +226 8 Dl +226 221 Dl +226 -201 Dl +3163 1737(MWF)N +977 1537 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1090 1596 MXY +0 29 Dl +0 -14 Dl +15 0 Dl +-29 0 Dl +1316 1732 MXY +0 28 Dl +0 -14 Dl +15 0 Dl +-29 0 Dl +1542 1816 MXY +0 29 Dl +0 -14 Dl +15 0 Dl +-29 0 Dl +1768 1870 MXY +0 29 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1994 1984 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +2220 2065 MXY +0 29 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +2446 2209 MXY +0 29 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +2672 2178 MXY +0 29 Dl +0 -15 Dl +14 0 Dl +-28 0 Dl +2898 2376 MXY +0 29 Dl +0 -15 Dl +14 0 Dl +-29 0 Dl +3124 2495 MXY +0 29 Dl +0 -15 Dl +14 0 Dl +-29 0 Dl +920 2495 MXY +1 setlinewidth +977 1551 MXY +113 60 Dl +226 135 Dl +226 85 Dl +226 54 Dl +226 113 Dl +226 82 Dl +226 144 Dl +226 -32 Dl +226 198 Dl +226 119 Dl +3135 2585(delaysplit)N +920 1551 MXY +3 setlinewidth +977 1537 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1090 1895 MXY +0 29 Dl +0 -14 Dl +15 0 Dl +-29 0 Dl +1316 2664 MXY +0 29 Dl +0 -14 Dl +15 0 Dl +-29 0 Dl +1542 2887 MXY +0 29 Dl +0 -14 Dl +15 0 Dl +-29 0 Dl +1768 3037 MXY +0 29 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1994 3151 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +2220 3142 MXY +0 29 Dl +0 -15 Dl +14 0 Dl +-28 0 Dl +2446 3376 MXY +0 29 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +2672 3229 MXY +0 29 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +2898 3439 MXY +0 29 Dl +0 -15 Dl +14 0 Dl +-29 0 Dl +3124 3498 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-29 0 Dl +920 3498 MXY +[64 32 32 32] 0 setdash +1 setlinewidth +977 1551 MXY +113 359 Dl +226 769 Dl +226 223 Dl +226 150 Dl +226 113 Dl +226 -9 Dl +226 235 Dl +226 -147 Dl +226 209 Dl +226 59 Dl +3433(TreeSplit10)Y +920 1551 MXY +[] 0 setdash +3 setlinewidth +977 1537 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1090 1783 MXY +0 28 Dl +0 -14 Dl +15 0 Dl +-29 0 Dl +1316 2159 MXY +0 28 Dl +0 -14 Dl +15 0 Dl +-29 0 Dl +1542 2297 MXY +0 29 Dl +0 -15 Dl +15 0 Dl +-29 0 Dl +1768 2514 MXY +0 29 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1994 2517 MXY +0 29 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +2220 2684 MXY +0 29 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +2446 2783 MXY +0 29 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +2672 2794 MXY +0 29 Dl +0 -15 Dl +14 0 Dl +-28 0 Dl +2898 2882 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-29 0 Dl +3124 2970 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-29 0 Dl +920 2970 MXY +[64 32] 0 setdash +1 setlinewidth +977 1551 MXY +113 246 Dl +226 376 Dl +226 138 Dl +226 218 Dl +226 3 Dl +226 167 Dl +226 99 Dl +226 10 Dl +226 88 Dl +226 88 Dl +3178 3009(ER)N +920 1551 MXY +[] 0 setdash +3 setlinewidth +977 1537 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1090 1876 MXY +0 29 Dl +0 -15 Dl +15 0 Dl +-29 0 Dl +1316 2610 MXY +0 29 Dl +0 -14 Dl +15 0 Dl +-29 0 Dl +1542 2904 MXY +0 29 Dl +0 -14 Dl +15 0 Dl +-29 0 Dl +1768 3097 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1994 3232 MXY +0 29 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +2220 3413 MXY +0 29 Dl +0 -15 Dl +14 0 Dl +-28 0 Dl +2446 3413 MXY +0 29 Dl +0 -15 Dl +14 0 Dl +-28 0 Dl +2672 3422 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +2898 3549 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-29 0 Dl +3124 3546 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-29 0 Dl +977 1551 MXY +113 339 Dl +226 735 Dl +226 294 Dl +226 192 Dl +226 136 Dl +226 180 Dl +226 0 Dl +226 9 Dl +226 127 Dl +226 -3 Dl +3151 3574(PVS10)N +977 4377 MXY +2259 0 Dl +977 MX +0 -2826 Dl +4377 MY +0 29 Dl +951 4530(1)N +1203 4377 MXY +0 29 Dl +1177 4530(3)N +1429 4377 MXY +0 29 Dl +1403 4530(5)N +1655 4377 MXY +0 29 Dl +1629 4530(7)N +1881 4377 MXY +0 29 Dl +1855 4530(9)N +2107 4377 MXY +0 29 Dl +2054 4530(11)N +2333 4377 MXY +0 29 Dl +2280 4530(13)N +2559 4377 MXY +0 29 Dl +2506 4530(15)N +2784 4377 MXY +0 29 Dl +2731 4530(17)N +3010 4377 MXY +0 29 Dl +2957 4530(19)N +3236 4377 MXY +0 29 Dl +3183 4530(21)N +977 4377 MXY +-29 0 Dl +734 4401(0.00)N +977 4094 MXY +-29 0 Dl +734 4118(0.10)N +977 3812 MXY +-29 0 Dl +734 3835(0.20)N +977 3529 MXY +-29 0 Dl +734 3553(0.30)N +977 3247 MXY +-29 0 Dl +734 3270(0.40)N +977 2964 MXY +-29 0 Dl +734 2988(0.50)N +977 2681 MXY +-29 0 Dl +734 2705(0.60)N +977 2399 MXY +-29 0 Dl +734 2422(0.70)N +977 2116 MXY +-29 0 Dl +734 2140(0.80)N +977 1834 MXY +-29 0 Dl +734 1857(0.90)N +977 1551 MXY +-29 0 Dl +734 1575(1.00)N +3 f +1448 4721(Figure)N +1 f +1745(5:)X +1844(Ef\256ciency)X +2264(vs)X +2373(number)X +2691(of)X +2795(machines)X + +12 p +%%Page: 12 12 +12 s 0 xH 0 xS 1 f +10 s +3 f +576 474(Game-tree)N +963(search)X +3952(12)X +1 f +12 s +911 2908 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +1024 2842 MXY +0 31 Dl +0 -16 Dl +16 0 Dl +-31 0 Dl +1252 2474 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +1478 2341 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +1705 2157 MXY +0 31 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +1932 1986 MXY +0 31 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +2158 2093 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-31 0 Dl +2385 2032 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +2612 1784 MXY +0 31 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +2839 1684 MXY +0 31 Dl +0 -15 Dl +16 0 Dl +-32 0 Dl +3065 1753 MXY +0 31 Dl +0 -15 Dl +16 0 Dl +-32 0 Dl +848 1753 MXY +[16] 0 setdash +1 setlinewidth +911 2924 MXY +113 -67 Dl +228 -367 Dl +226 -133 Dl +227 -185 Dl +227 -171 Dl +226 108 Dl +227 -61 Dl +227 -249 Dl +227 -99 Dl +226 69 Dl +5 f +3118 1810(alphabeta)N +848 2924 MXY +[] 0 setdash +3 setlinewidth +911 2908 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +1024 2908 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-31 0 Dl +1252 2903 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +1478 2939 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +1705 2990 MXY +0 31 Dl +0 -15 Dl +16 0 Dl +-32 0 Dl +1932 2970 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +2158 3002 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-31 0 Dl +2385 2991 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +2612 3026 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +2839 3069 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +3065 2988 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +911 2924 MXY +113 0 Dl +228 -5 Dl +226 36 Dl +227 51 Dl +227 -20 Dl +226 32 Dl +227 -11 Dl +227 35 Dl +227 43 Dl +226 -81 Dl +3128 3038(delaysplit)N +911 2908 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +1024 2755 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-31 0 Dl +1252 2268 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +1478 2042 MXY +0 31 Dl +0 -15 Dl +16 0 Dl +-32 0 Dl +1705 1837 MXY +0 31 Dl +0 -15 Dl +16 0 Dl +-32 0 Dl +1932 1685 MXY +0 31 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +2158 1760 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-31 0 Dl +2385 1263 MXY +0 31 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +2612 1663 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +2839 1179 MXY +0 31 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +3065 1090 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +848 1090 MXY +[64 32 32 32] 0 setdash +1 setlinewidth +911 2924 MXY +113 -153 Dl +228 -487 Dl +226 -226 Dl +227 -205 Dl +227 -153 Dl +226 76 Dl +227 -498 Dl +227 401 Dl +227 -485 Dl +226 -88 Dl +3196 1093(TreeSplit10)N +848 2924 MXY +[] 0 setdash +3 setlinewidth +911 2908 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +1024 2766 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-31 0 Dl +1252 2365 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +1478 2093 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +1705 1926 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +1932 1742 MXY +0 31 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +2158 1298 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-31 0 Dl +2385 1404 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +2612 1449 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +2839 1195 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +3065 1143 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +911 2924 MXY +113 -142 Dl +228 -401 Dl +226 -272 Dl +227 -167 Dl +227 -185 Dl +226 -443 Dl +227 106 Dl +227 45 Dl +227 -254 Dl +226 -52 Dl +3121 1197(PVS10)N +911 2908 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +1024 2903 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-31 0 Dl +1252 2880 MXY +0 31 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +1478 2929 MXY +0 31 Dl +0 -15 Dl +16 0 Dl +-32 0 Dl +1705 2917 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +1932 2998 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +2158 2935 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-31 0 Dl +2385 3002 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +2612 3019 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +2839 3006 MXY +0 31 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +3065 3051 MXY +0 31 Dl +0 -15 Dl +16 0 Dl +-32 0 Dl +848 3051 MXY +[16] 0 setdash +1 setlinewidth +911 2924 MXY +113 -5 Dl +228 -24 Dl +226 50 Dl +227 -12 Dl +227 81 Dl +226 -63 Dl +227 67 Dl +227 17 Dl +227 -14 Dl +226 46 Dl +3121 3121(MWF)N +848 2924 MXY +[] 0 setdash +3 setlinewidth +911 2908 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +1024 2823 MXY +0 31 Dl +0 -16 Dl +16 0 Dl +-31 0 Dl +1252 2677 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +1478 2617 MXY +0 31 Dl +0 -15 Dl +16 0 Dl +-32 0 Dl +1705 2501 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +1932 2523 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +2158 2438 MXY +0 31 Dl +0 -15 Dl +16 0 Dl +-31 0 Dl +2385 2317 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +2612 2347 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +2839 2329 MXY +0 32 Dl +0 -16 Dl +16 0 Dl +-32 0 Dl +3065 2210 MXY +0 31 Dl +0 -15 Dl +16 0 Dl +-32 0 Dl +848 2210 MXY +[64 32 32 32] 0 setdash +1 setlinewidth +911 2924 MXY +113 -86 Dl +228 -145 Dl +226 -60 Dl +227 -116 Dl +227 22 Dl +226 -85 Dl +227 -121 Dl +227 30 Dl +227 -18 Dl +226 -119 Dl +3124 2267(ER)N +848 2924 MXY +[] 0 setdash +3 setlinewidth +911 3964 MXY +2495 0 Dl +911 MX +0 -3120 Dl +3964 MY +0 31 Dl +885 4124(1)N +1138 3964 MXY +0 31 Dl +1112 4124(3)N +1365 3964 MXY +0 31 Dl +1339 4124(5)N +1591 3964 MXY +0 31 Dl +1565 4124(7)N +1818 3964 MXY +0 31 Dl +1792 4124(9)N +2045 3964 MXY +0 31 Dl +1992 4124(11)N +2272 3964 MXY +0 31 Dl +2219 4124(13)N +2499 3964 MXY +0 31 Dl +2446 4124(15)N +2726 3964 MXY +0 31 Dl +2673 4124(17)N +2952 3964 MXY +0 31 Dl +2899 4124(19)N +3179 3964 MXY +0 31 Dl +3126 4124(21)N +3406 3964 MXY +0 31 Dl +3353 4124(23)N +911 3964 MXY +-31 0 Dl +662 3981(0.00)N +911 2924 MXY +-31 0 Dl +662 2942(1.00)N +911 1883 MXY +-31 0 Dl +662 1901(2.00)N +911 844 MXY +-31 0 Dl +662 861(3.00)N +3 f +1026 4326(Figure)N +1 f +1323(6:)X +1422(Relative)X +1768(no.)X +1912(of)X +2016(nodes)X +2264(examined)X +2663(vs.)X +2796(number)X +3114(of)X +3218(machines)X +776 4500(We)N +938(have)X +1148(also)X +1331(tested)X +1584(the)X +1730(algorithms)X +2170(using)X +2406(Othello)X +2723(with)X +2922(a)X +2994(6)X +9 f +(\264)S +1 f +3095(6)X +3172(board.)X +3468(All)X +3620(algorithms)X +576 4608(have)N +783(almost)X +1065(the)X +1208(same)X +1431(relative)X +1746(ef\256ciency,)X +2175(with)X +2371(delay)X +2605(splitting)X +2946(leading)X +3255(when)X +3487(fewer)X +3730(than)X +3920(six)X +576 4716(processors)N +1005(are)X +1147(used.)X +1395(In)X +1499(this)X +1662(experiment,)X +2144(the)X +2286(speedup)X +2625(did)X +2772(not)X +2919(exceed)X +3211(7)X +3283(\(Figure)X +3590(7\).)X + +13 p +%%Page: 13 13 +12 s 0 xH 0 xS 1 f +10 s +3 f +576 474(Game-tree)N +963(search)X +3952(13)X +1 f +12 s +977 823 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1089 1360 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1313 1872 MXY +0 29 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1537 2223 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1761 2298 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1985 2446 MXY +0 29 Dl +0 -14 Dl +14 0 Dl +-29 0 Dl +2208 2472 MXY +0 28 Dl +0 -14 Dl +15 0 Dl +-29 0 Dl +2432 2581 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +2656 2699 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +2880 2699 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +3104 2760 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +920 2760 MXY +[16] 0 setdash +1 setlinewidth +977 837 MXY +112 537 Dl +224 513 Dl +224 350 Dl +224 75 Dl +224 149 Dl +223 25 Dl +224 109 Dl +224 118 Dl +224 0 Dl +224 61 Dl +5 f +3159 2702(alphabeta)N +920 837 MXY +[] 0 setdash +3 setlinewidth +977 823 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1089 1229 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1313 1707 MXY +0 29 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1537 1968 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1761 2105 MXY +0 29 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1985 2175 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-29 0 Dl +2208 2396 MXY +0 28 Dl +0 -14 Dl +15 0 Dl +-29 0 Dl +2432 2503 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +2656 2556 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +2880 2724 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +3104 2858 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +977 837 MXY +112 406 Dl +224 479 Dl +224 260 Dl +224 138 Dl +224 69 Dl +223 221 Dl +224 107 Dl +224 53 Dl +224 168 Dl +224 134 Dl +3197 2982(MWF)N +977 823 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1089 1069 MXY +0 29 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1313 1643 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1537 2044 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1761 2262 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1985 2536 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-29 0 Dl +2208 2547 MXY +0 29 Dl +0 -14 Dl +15 0 Dl +-29 0 Dl +2432 2693 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +2656 2741 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +2880 2539 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +3104 2908 MXY +0 29 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +920 2908 MXY +[64 32 32 32] 0 setdash +1 setlinewidth +977 837 MXY +112 247 Dl +224 573 Dl +224 401 Dl +224 218 Dl +224 274 Dl +223 12 Dl +224 145 Dl +224 48 Dl +224 -202 Dl +224 370 Dl +3169 3122(delaysplit)N +920 837 MXY +[] 0 setdash +3 setlinewidth +977 823 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1089 1445 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1313 1918 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1537 2110 MXY +0 29 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1761 2284 MXY +0 29 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1985 2383 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-29 0 Dl +2208 2461 MXY +0 28 Dl +0 -14 Dl +15 0 Dl +-29 0 Dl +2432 2631 MXY +0 29 Dl +0 -15 Dl +14 0 Dl +-28 0 Dl +2656 2628 MXY +0 29 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +2880 2702 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +3104 2752 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +977 837 MXY +112 622 Dl +224 473 Dl +224 193 Dl +224 174 Dl +224 98 Dl +223 78 Dl +224 170 Dl +224 -2 Dl +224 73 Dl +224 50 Dl +3068 2562(TreeSplit10)N +977 823 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1089 1237 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1313 1713 MXY +0 29 Dl +0 -15 Dl +14 0 Dl +-28 0 Dl +1537 1979 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1761 2110 MXY +0 29 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1985 2259 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-29 0 Dl +2208 2332 MXY +0 28 Dl +0 -14 Dl +15 0 Dl +-29 0 Dl +2432 2475 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +2656 2472 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +2880 2643 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +3104 2628 MXY +0 29 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +920 2628 MXY +[64 32] 0 setdash +1 setlinewidth +977 837 MXY +112 414 Dl +224 476 Dl +224 266 Dl +224 132 Dl +224 148 Dl +223 73 Dl +224 143 Dl +224 -3 Dl +224 171 Dl +224 -14 Dl +3213 2422(ER)N +920 837 MXY +[] 0 setdash +3 setlinewidth +977 823 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1089 1315 MXY +0 29 Dl +0 -15 Dl +14 0 Dl +-28 0 Dl +1313 1892 MXY +0 29 Dl +0 -15 Dl +14 0 Dl +-28 0 Dl +1537 2178 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1761 2444 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +1985 2530 MXY +0 29 Dl +0 -14 Dl +14 0 Dl +-29 0 Dl +2208 2581 MXY +0 28 Dl +0 -14 Dl +15 0 Dl +-29 0 Dl +2432 2685 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +2656 2771 MXY +0 29 Dl +0 -15 Dl +14 0 Dl +-28 0 Dl +2880 2819 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +3104 2914 MXY +0 28 Dl +0 -14 Dl +14 0 Dl +-28 0 Dl +977 837 MXY +112 492 Dl +224 577 Dl +224 286 Dl +224 266 Dl +224 87 Dl +223 50 Dl +224 104 Dl +224 86 Dl +224 48 Dl +224 95 Dl +3219 2842(PVS10)N +977 3637 MXY +2238 0 Dl +977 MX +0 -2800 Dl +3637 MY +0 28 Dl +951 3789(1)N +1201 3637 MXY +0 28 Dl +1175 3789(3)N +1425 3637 MXY +0 28 Dl +1399 3789(5)N +1648 3637 MXY +0 28 Dl +1622 3789(7)N +1872 3637 MXY +0 28 Dl +1846 3789(9)N +2096 3637 MXY +0 28 Dl +2043 3789(11)N +2320 3637 MXY +0 28 Dl +2267 3789(13)N +2544 3637 MXY +0 28 Dl +2491 3789(15)N +2768 3637 MXY +0 28 Dl +2715 3789(17)N +2992 3637 MXY +0 28 Dl +2939 3789(19)N +3215 3637 MXY +0 28 Dl +3162 3789(21)N +977 3637 MXY +-28 0 Dl +734 3661(0.00)N +977 3357 MXY +-28 0 Dl +734 3381(0.10)N +977 3077 MXY +-28 0 Dl +734 3101(0.20)N +977 2797 MXY +-28 0 Dl +734 2821(0.30)N +977 2517 MXY +-28 0 Dl +734 2541(0.40)N +977 2237 MXY +-28 0 Dl +734 2261(0.50)N +977 1957 MXY +-28 0 Dl +734 1981(0.60)N +977 1677 MXY +-28 0 Dl +734 1701(0.70)N +977 1397 MXY +-28 0 Dl +734 1421(0.80)N +977 1117 MXY +-28 0 Dl +734 1141(0.90)N +977 837 MXY +-28 0 Dl +734 861(1.00)N +3 f +1448 3979(Figure)N +1 f +1745(7:)X +1844(Ef\256ciency)X +2264(vs)X +2373(number)X +2691(of)X +2795(machines)X +8 f +14 s +576 4216(5.)N +844(Sorting)X +1380(methods)X +1 f +12 s +776 4357(We)N +934(have)X +1141(compared)X +1546(the)X +1689(effects)X +1971(of)X +2076(four)X +2261(different)X +2618(sorting)X +2910(strategies)X +3299(on)X +3420(the)X +3563(search)X +3834(algo-)X +576 4465(rithms.)N +902(In)X +1014(all)X +1143(the)X +1293(strategies,)X +1712(an)X +3 f +1834(expansion)X +2275(depth)X +2540(parameter)X +1 f +3004(speci\256es)X +3366(how)X +3562(many)X +3807(levels)X +576 4573(below)N +843(a)X +918(node)X +1138(are)X +1289(expanded)X +1691(in)X +1799(order)X +2035(to)X +2143(sort)X +2320(that)X +2498(node's)X +2787(children.)X +3184(We)X +3351(set)X +3491(the)X +3642(expansion)X +576 4681(depth)N +828(parameter)X +1252(to)X +1364(3)X +1449(for)X +1598(the)X +1753(experiments)X +2261(reported)X +2619(here.)X +2870(That)X +3084(is,)X +3209(to)X +3321(sort)X +3502(a)X +3582(node)X +2 f +3806(z)X +1 f +3859(,)X +3920(we)X +576 4789(expand)N +880(the)X +1024(tree)X +1195(to)X +1296(three)X +1515(levels)X +1766(below)X +2 f +2027(z)X +1 f +2080(,)X +2130(evaluate)X +2478(the)X +2622(leaves)X +2889(statically,)X +3288(apply)X +3528(alpha-beta)X +3957(to)X +576 4897(those)N +803(values)X +1073(to)X +1172(back)X +1378(them)X +1595(up)X +1715(to)X +1814(node)X +2 f +2025(z)X +1 f +2078('s)X +2171(children,)X +2535(then)X +2725(sort)X +2893(those)X +3120(children)X +3460(accordingly.)X +776 5038(Another)N +1122(adjustable)X +1545(parameter)X +1963(is)X +2059(the)X +3 f +2209(sorting)X +2529(depth)X +2795(parameter)X +1 f +3228(,)X +3284(which)X +3551(speci\256es)X +3914(the)X +576 5146(maximum)N +996(depth)X +1239(of)X +1348(a)X +1420(node)X +1636(to)X +1740(which)X +2004(sorting)X +2300(may)X +2495(be)X +2615(applied.)X +2976(For)X +3138(some)X +3369(applications,)X +3887(like)X +576 5254(tic-tac-toe)N +998(with)X +1199(a)X +1272(4)X +9 f +(\264)S +1 f +1373(4)X +1451(board,)X +1724(every)X +1968(level)X +2186(of)X +2296(the)X +2444(search)X +2720(tree)X +2895(may)X +3092(be)X +3214(pro\256tably)X +3619(sorted,)X +3909(but)X +576 5362(in)N +688(other)X +923(applications,)X +1450(sorting)X +1754(nodes)X +2015(beyond)X +2335(some)X +2575(level)X +2799(increases)X +3188(the)X +3342(total)X +3550(computation)X +576 5470(time;)N +807(sorting)X +1106(time)X +1310(outweighs)X +1737(cutoff)X +1999(bene\256ts.)X +2378(For)X +2543(example,)X +2926(in)X +3033(Othello)X +3354(with)X +3557(a)X +3632(6)X +9 f +(\264)S +1 f +3733(6)X +3813(board)X +576 5578(and)N +752(a)X +832(search)X +1114(tree)X +1295(of)X +1411(nine)X +1613(levels,)X +1898(the)X +2052(best)X +2243(overall)X +2547(results)X +2834(are)X +2988(achieved)X +3367(when)X +3611(the)X +3765(sorting)X +576 5686(depth)N +814(parameter)X +1224(is)X +1312(set)X +1443(to)X +1542(six)X +1678(levels.)X + +14 p +%%Page: 14 14 +12 s 0 xH 0 xS 1 f +10 s +3 f +576 474(Game-tree)N +963(search)X +3952(14)X +1 f +12 s +776 780(Our)N +967(\256rst)X +1158(attempt)X +1490(at)X +1602(sorting)X +1911(was)X +2102(to)X +2219(sort)X +2405(only)X +2618(the)X +2778(children)X +3136(of)X +3258(the)X +3418(top)X +3583(node.)X +3861(This)X +576 888(regime,)N +899(called)X +1161(``TN)X +1384(\(top-node\))X +1821(sorting'',)X +2207(applies)X +2511(to)X +2617(all)X +2745(the)X +2894(algorithms)X +3337(except)X +3620(ER,)X +3797(which)X +576 996(has)N +734(its)X +855(own)X +1051(internal)X +1377(sorting)X +1675(mechanism.)X +2193(There)X +2449(is)X +2544(no)X +2671(noticeable)X +3099(difference)X +3521(in)X +3627(number)X +3952(of)X +576 1104(nodes,)N +858(total)X +1064(time,)X +1294(or)X +1407(ef\256ciency)X +1820(for)X +1965(any)X +2137(of)X +2250(the)X +2401(algorithms)X +2846(between)X +3200(TN)X +3361(and)X +3533(no)X +3662(sorting)X +3962(at)X +576 1212(all.)N +776 1353(Next)N +995(we)X +1139(extended)X +1519(the)X +1669(sorting)X +1968(to)X +2075(include)X +2391(all)X +2521(nodes)X +2778(on)X +2907(the)X +3058(principal)X +3434(variation)X +3810(route.)X +576 1461(We)N +745(call)X +920(this)X +1094(sorting)X +1395(regime)X +1697(``PVR)X +1981(sorting''.)X +2394(Our)X +2577(tests)X +2782(of)X +2896(PVR)X +3116(sorting)X +3417(for)X +3563(PV)X +3719(spitting,)X +576 1569(MWF,)N +853(and)X +1016(delay)X +1249(splitting)X +1589(show)X +1815(no)X +1935(signi\256cant)X +2360(improvement)X +2898(in)X +2997(total)X +3193(computation)X +3699(time.)X +776 1710(In)N +889(the)X +1040(third)X +1255(sorting)X +1555(regime,)X +1881(we)X +2027(sort)X +2205(at)X +2309(the)X +2461(top)X +2618(node)X +2839(and)X +3012(at)X +3116(every)X +3364(eldest)X +3623(child.)X +3898(We)X +576 1818(call)N +754(this)X +931(sorting)X +1236(regime)X +1542(``EC)X +1767(\(eldest)X +2062(child\))X +2325(sorting''.)X +2741(EC)X +2901(sorting)X +3205(applies)X +3515(to)X +3627(MWF)X +3893(and)X +576 1926(delay)N +812(splitting,)X +1179(since)X +1404(only)X +1603(in)X +1706(these)X +1932(two)X +2104(algorithms)X +2544(do)X +2668(we)X +2808(suspend)X +3145(evaluation)X +3575(of)X +3683(all)X +3808(nodes)X +576 2034(that)N +751(are)X +899(not)X +1052(eldest)X +1307(children)X +1653(until)X +1859(their)X +2065(eldest)X +2319(sibling)X +2610(is)X +2703(fully)X +2914(evaluated.)X +3361(Therefore)X +3770(having)X +576 2142(the)N +718(best)X +897(child)X +1114(evaluated)X +1508(\256rst)X +1681(should)X +1961(result)X +2199(in)X +2298(more)X +2520(cutoffs.)X +776 2283(As)N +916(expected,)X +1317(the)X +1469(results)X +1755(are)X +1908(much)X +2157(better)X +2412(for)X +2559(EC)X +2717(sorting)X +3019(than)X +3220(PRV)X +3441(sorting,)X +3767(as)X +3882(evi-)X +576 2391(denced)N +875(by)X +997(tests)X +1194(with)X +1391(our)X +1545(tic-tac-toe)X +1963(and)X +2128(Othello)X +2442(applications.)X +2981(The)X +3156(total)X +3353(computation)X +3860(time)X +576 2499(is)N +664(almost)X +945(reduced)X +1274(by)X +1394(half)X +1568(when)X +1800(fewer)X +2043(machines)X +2431(are)X +2573(used.)X +2821(The)X +2996(reduction)X +3385(in)X +3485(the)X +3628(ef\256ciency,)X +576 2607(expected)N +948(due)X +1116(to)X +1220(the)X +1367(improvement)X +1910(in)X +2014(the)X +2161(sequential)X +2581(performance)X +3097(of)X +3206(the)X +3353(algorithms,)X +3817(is)X +3909(not)X +576 2715(too)N +725(bad.)X +938(Figures)X +1252(8,)X +1350(9)X +1424(and)X +1589(10)X +1711(show)X +1939(the)X +2083(number)X +2403(of)X +2509(nodes)X +2759(examined)X +3160(\(in)X +3293(multiples)X +3678(of)X +3784(1000\),)X +576 2823(total)N +772(time)X +968(and)X +1131(ef\256ciency)X +1535(comparisons)X +2045(for)X +2181(MWF)X +2434(using)X +2666(the)X +2808(4)X +9 f +(\264)S +1 f +2909(4)X +2981(tic-tac-toe)X +3397(game.)X +1377 4346 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1456 4329 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1614 4313 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1771 4287 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1928 4316 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2085 4235 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2243 4295 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2400 4295 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2557 4278 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2715 4299 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2872 4339 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1337 4339 MXY +[16] 0 setdash +1 setlinewidth +1377 4356 MXY +79 -17 Dl +158 -16 Dl +157 -26 Dl +157 29 Dl +157 -81 Dl +158 60 Dl +157 0 Dl +157 -17 Dl +158 21 Dl +157 40 Dl +5 f +2527 4242(MWF\(EC-sorting\))N +1337 4356 MXY +[] 0 setdash +3 setlinewidth +1377 3093 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1456 3086 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1614 3043 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1771 3130 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1928 3110 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2085 3255 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2243 3143 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2400 3264 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2557 3293 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2715 3269 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2872 3349 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1377 3103 MXY +79 -7 Dl +158 -43 Dl +157 87 Dl +157 -20 Dl +157 145 Dl +158 -112 Dl +157 121 Dl +157 29 Dl +158 -24 Dl +157 80 Dl +2541 3533(MWF\(NoSorting\))N +1377 4971 MXY +1573 0 Dl +1377 MX +0 -1967 Dl +4971 MY +0 20 Dl +1351 5102(1)N +1535 4971 MXY +0 20 Dl +1509 5102(3)N +1692 4971 MXY +0 20 Dl +1666 5102(5)N +1849 4971 MXY +0 20 Dl +1823 5102(7)N +2007 4971 MXY +0 20 Dl +1981 5102(9)N +2164 4971 MXY +0 20 Dl +2111 5102(11)N +2321 4971 MXY +0 20 Dl +2268 5102(13)N +2478 4971 MXY +0 20 Dl +2425 5102(15)N +2636 4971 MXY +0 20 Dl +2583 5102(17)N +2793 4971 MXY +0 20 Dl +2740 5102(19)N +2950 4971 MXY +0 20 Dl +2897 5102(21)N +1377 4971 MXY +-20 0 Dl +1151 5012(0.00)N +1377 4820 MXY +-20 0 Dl +1098 4861(50.00)N +1377 4669 MXY +-20 0 Dl +1045 4710(100.00)N +1377 4518 MXY +-20 0 Dl +1045 4559(150.00)N +1377 4366 MXY +-20 0 Dl +1045 4407(200.00)N +1377 4215 MXY +-20 0 Dl +1045 4256(250.00)N +1377 4064 MXY +-20 0 Dl +1045 4105(300.00)N +1377 3912 MXY +-20 0 Dl +1045 3953(350.00)N +1377 3761 MXY +-20 0 Dl +1045 3802(400.00)N +1377 3609 MXY +-20 0 Dl +1045 3650(450.00)N +1377 3458 MXY +-20 0 Dl +1045 3499(500.00)N +1377 3307 MXY +-20 0 Dl +1045 3348(550.00)N +1377 3155 MXY +-20 0 Dl +1045 3196(600.00)N +1377 3004 MXY +-20 0 Dl +1045 3045(650.00)N +3 f +1312 5263(Figure)N +1 f +1609(8:)X +1708(Nodes)X +1977(examined)X +2376(vs.)X +2509(number)X +2827(of)X +2931(machines)X + +15 p +%%Page: 15 15 +12 s 0 xH 0 xS 1 f +10 s +3 f +576 474(Game-tree)N +963(search)X +3952(15)X +1 f +12 s +1377 1091 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1456 1066 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1614 997 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1771 1057 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1928 1021 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2085 1123 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2243 974 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2400 1054 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2557 1049 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2715 900 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2872 1040 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1377 1101 MXY +79 -25 Dl +158 -69 Dl +157 60 Dl +157 -36 Dl +157 102 Dl +158 -149 Dl +157 80 Dl +157 -5 Dl +158 -149 Dl +157 140 Dl +5 f +2541 861(MWF\(NoSorting\))N +1377 1772 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1456 1689 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1614 1583 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1771 1450 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1928 1403 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2085 1240 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2243 1278 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2400 1299 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2557 1147 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2715 1141 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2872 1145 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1337 1145 MXY +[16] 0 setdash +1 setlinewidth +1377 1782 MXY +79 -83 Dl +158 -106 Dl +157 -133 Dl +157 -47 Dl +157 -163 Dl +158 38 Dl +157 21 Dl +157 -152 Dl +158 -6 Dl +157 4 Dl +2527 1266(MWF\(EC-sorting\))N +1337 1782 MXY +[] 0 setdash +3 setlinewidth +1377 2416 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1456 2379 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1614 2335 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1771 2290 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1928 2275 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2085 2210 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2243 2252 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2400 2279 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2557 2204 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2715 2239 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2872 2239 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1337 2239 MXY +[16] 0 setdash +1 setlinewidth +1377 2426 MXY +79 -37 Dl +158 -44 Dl +157 -45 Dl +157 -15 Dl +157 -65 Dl +158 42 Dl +157 27 Dl +157 -75 Dl +158 35 Dl +157 0 Dl +2370 2164(SortTime\(EC-sorting\))N +1337 2426 MXY +[] 0 setdash +3 setlinewidth +1377 2802 MXY +1573 0 Dl +1377 MX +0 -1967 Dl +2802 MY +0 20 Dl +1351 2933(1)N +1535 2802 MXY +0 20 Dl +1509 2933(3)N +1692 2802 MXY +0 20 Dl +1666 2933(5)N +1849 2802 MXY +0 20 Dl +1823 2933(7)N +2007 2802 MXY +0 20 Dl +1981 2933(9)N +2164 2802 MXY +0 20 Dl +2111 2933(11)N +2321 2802 MXY +0 20 Dl +2268 2933(13)N +2478 2802 MXY +0 20 Dl +2425 2933(15)N +2636 2802 MXY +0 20 Dl +2583 2933(17)N +2793 2802 MXY +0 20 Dl +2740 2933(19)N +2950 2802 MXY +0 20 Dl +2897 2933(21)N +1377 2802 MXY +-20 0 Dl +1151 2843(0.00)N +1377 2606 MXY +-20 0 Dl +1098 2647(40.00)N +1377 2409 MXY +-20 0 Dl +1098 2450(80.00)N +1377 2212 MXY +-20 0 Dl +1045 2253(120.00)N +1377 2015 MXY +-20 0 Dl +1045 2057(160.00)N +1377 1819 MXY +-20 0 Dl +1045 1860(200.00)N +1377 1622 MXY +-20 0 Dl +1045 1663(240.00)N +1377 1425 MXY +-20 0 Dl +1045 1466(280.00)N +1377 1229 MXY +-20 0 Dl +1045 1270(320.00)N +1377 1032 MXY +-20 0 Dl +1045 1073(360.00)N +1377 835 MXY +-20 0 Dl +1045 876(400.00)N +3 f +1532 3094(Figure)N +1 f +1829(9:)X +1928(Time)X +2156(vs.)X +2289(number)X +2607(of)X +2711(machines)X +1377 3298 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1456 3449 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1614 3611 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1771 3772 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1928 3823 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2085 3975 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2243 3943 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2400 3924 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2557 4050 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2715 4054 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2872 4054 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1377 3308 MXY +79 151 Dl +158 162 Dl +157 161 Dl +157 51 Dl +157 152 Dl +158 -32 Dl +157 -19 Dl +157 126 Dl +158 4 Dl +157 0 Dl +5 f +2527 4033(MWF\(EC-sorting\))N +1377 3298 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1456 3314 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1614 3390 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1771 3338 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1928 3379 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2085 3300 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2243 3430 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2400 3346 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2557 3351 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2715 3505 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2872 3365 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1337 3365 MXY +[16] 0 setdash +1 setlinewidth +1377 3308 MXY +79 16 Dl +158 76 Dl +157 -52 Dl +157 41 Dl +157 -79 Dl +158 130 Dl +157 -84 Dl +157 5 Dl +158 154 Dl +157 -140 Dl +2541 3364(MWF\(NoSorting\))N +1337 3308 MXY +[] 0 setdash +3 setlinewidth +1377 5275 MXY +1573 0 Dl +1377 MX +0 -1967 Dl +5275 MY +0 20 Dl +1351 5406(1)N +1535 5275 MXY +0 20 Dl +1509 5406(3)N +1692 5275 MXY +0 20 Dl +1666 5406(5)N +1849 5275 MXY +0 20 Dl +1823 5406(7)N +2007 5275 MXY +0 20 Dl +1981 5406(9)N +2164 5275 MXY +0 20 Dl +2111 5406(11)N +2321 5275 MXY +0 20 Dl +2268 5406(13)N +2478 5275 MXY +0 20 Dl +2425 5406(15)N +2636 5275 MXY +0 20 Dl +2583 5406(17)N +2793 5275 MXY +0 20 Dl +2740 5406(19)N +2950 5275 MXY +0 20 Dl +2897 5406(21)N +1377 5275 MXY +-20 0 Dl +1151 5316(0.00)N +1377 5079 MXY +-20 0 Dl +1151 5120(0.10)N +1377 4882 MXY +-20 0 Dl +1151 4923(0.20)N +1377 4685 MXY +-20 0 Dl +1151 4726(0.30)N +1377 4488 MXY +-20 0 Dl +1151 4530(0.40)N +1377 4292 MXY +-20 0 Dl +1151 4333(0.50)N +1377 4095 MXY +-20 0 Dl +1151 4136(0.60)N +1377 3898 MXY +-20 0 Dl +1151 3939(0.70)N +1377 3702 MXY +-20 0 Dl +1151 3743(0.80)N +1377 3505 MXY +-20 0 Dl +1151 3546(0.90)N +1377 3308 MXY +-20 0 Dl +1151 3349(1.00)N +3 f +1412 5567(Figure)N +1 f +1709(10:)X +1856(Ef\256ciency)X +2276(vs.)X +2409(number)X +2727(of)X +2831(machines)X + +16 p +%%Page: 16 16 +12 s 0 xH 0 xS 1 f +10 s +3 f +576 474(Game-tree)N +963(search)X +3952(16)X +1 f +12 s +776 780(The)N +953(last)X +1114(sorting)X +1408(regime)X +1703(is)X +1794(motivated)X +2207(by)X +2330(considering)X +2806(the)X +2951(type-2)X +3224(nodes)X +3475(in)X +3577(MWF.)X +3882(The)X +576 888(eldest)N +830(child)X +1052(of)X +1161(a)X +1233(type-2)X +1508(node)X +1724(is)X +1817(evaluated)X +2215(before)X +2489(its)X +2608(other)X +2834(children)X +3178(are)X +3324(generated.)X +3775(There-)X +576 996(fore,)N +784(if)X +872(we)X +1013(also)X +1197(sort)X +1370(the)X +1517(children)X +1862(of)X +1971(a)X +2044(type-2)X +2320(node)X +2537(there)X +2760(should)X +3046(be)X +3167(even)X +3379(more)X +3607(cutoffs.)X +3952(In)X +576 1104(this)N +748(sorting)X +1048(regime,)X +1373(in)X +1481(addition)X +1830(to)X +1938(sorting)X +2238(children)X +2587(of)X +2700(every)X +2947(eldest)X +3205(child,)X +3455(we)X +3599(also)X +3786(sort)X +3962(at)X +576 1212(every)N +814(type-2)X +1084(node.)X +1343(We)X +1501(call)X +1665(this)X +1828(regime)X +2120(``TT)X +2326(\(type-two\))X +2756(sorting''.)X +776 1353(TT)N +919(sorting)X +1211(resulted)X +1541(in)X +1641(a)X +1709(vast)X +1889(improvement)X +2428(in)X +2528(total)X +2725(computation)X +3232(time)X +3429(and)X +3594(the)X +3738(number)X +576 1461(of)N +688(nodes)X +944(generated.)X +3 f +1398(Unfortunately,)X +2034(a)X +2113(subtle)X +2389(bug)X +2574(in)X +2685(our)X +2860(implementation)X +3537(\(since)X +3803(\256xed\))X +576 1569(renders)N +920(all)X +1051(our)X +1224(conclusions)X +1722(about)X +1985(this)X +2163(sorting)X +2480(method)X +2819(inaccurate;)X +3314(previous)X +3696(versions)X +576 1677(of)N +681(this)X +855(report)X +1142(should)X +1438(not)X +1596(be)X +1717(trusted)X +2035(in)X +2139(this)X +2312(regard.)X +2662(In)X +2776(fact,)X +2979(what)X +3205(we)X +3341(implemented)X +3899(did)X +576 1785(not)N +760(evaluate)X +1153(type-2)X +1460(nodes)X +1745(as)X +1881(deeply)X +2199(as)X +2336(type-1)X +2644(nodes,)X +2954(so)X +3091(far)X +3266(fewer)X +3548(nodes)X +3834(were)X +576 1893(evaluated.)N +1053(So)X +1188(TT)X +1349(sorting)X +1670(\(in)X +1815(this)X +1997(report\))X +2324(implies)X +2651(a)X +2732(different)X +3123(evaluation)X +3583(strategy)X +3947(as)X +576 2001(well.)N +1 f +824(The)X +1008(computation)X +1524(time)X +1731(is)X +1830(almost)X +2122(30)X +2253(times)X +2497(faster)X +2746(than)X +2947(the)X +3100(computation)X +3617(time)X +3824(using)X +576 2109(EC)N +735(sorting)X +1038(for)X +1186(a)X +1265(4)X +9 f +(\264)S +1 f +1366(4)X +1450(tic-tac-toe)X +1877(game,)X +2145(even)X +2362(though)X +2664(about)X +2913(95%)X +3124(of)X +3239(the)X +3392(time)X +3599(is)X +3698(spent)X +3936(on)X +576 2217(sorting)N +868(in)X +968(the)X +1111(1-machine)X +1543(\(sequential\))X +2023(case.)X +2262(These)X +2517(results)X +2793(are)X +2936(shown)X +3211(in)X +3311(Figures)X +3625(11)X +3747(and)X +3912(12.)X +576 2325(The)N +771(ef\256ciency)X +1196(is)X +1305(drastically)X +1752(reduced)X +2102(because)X +2452(the)X +2615(work)X +2857(does)X +3078(not)X +3246(seem)X +3489(to)X +3608(be)X +3743(divided)X +576 2433(evenly)N +857(between)X +1202(the)X +1344(machines.)X +1780(Our)X +1953(assumption)X +2415(is)X +2503(that)X +2673(a)X +2741(better)X +2986(distribution)X +3455(of)X +3560(work)X +3782(can)X +3941(be)X +576 2541(achieved)N +948(by)X +1073(some)X +1305(adjustments)X +1794(to)X +1898(DIB)X +2092(itself)X +2314(so)X +2428(that)X +2602(this)X +2770(great)X +2992(speed)X +3240(can)X +3403(be)X +3523(accompanied)X +576 2649(by)N +696(a)X +763(better)X +1007(ef\256ciency.)X +1377 4770 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1456 4752 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1614 4667 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1771 4618 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1928 4590 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2085 4541 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2243 4493 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2400 4446 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2557 4431 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2715 4314 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2872 4395 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1377 4780 MXY +79 -18 Dl +158 -85 Dl +157 -49 Dl +157 -28 Dl +157 -49 Dl +158 -48 Dl +157 -47 Dl +157 -15 Dl +158 -77 Dl +157 41 Dl +5 f +2457 4358(MWF\(TT-sorting\))N +1377 3612 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1456 3514 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1614 3389 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1771 3233 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1928 3178 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2085 2985 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2243 3031 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2400 3055 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2557 2876 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2715 2870 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2872 2874 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1337 2874 MXY +[16] 0 setdash +1 setlinewidth +1377 3622 MXY +79 -98 Dl +158 -125 Dl +157 -156 Dl +157 -55 Dl +157 -193 Dl +158 46 Dl +157 24 Dl +157 -179 Dl +158 -6 Dl +157 4 Dl +2449 2871(MWF\(EC-sorting\))N +1337 3622 MXY +[] 0 setdash +3 setlinewidth +1377 4370 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1456 4326 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1614 4274 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1771 4221 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1928 4204 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2085 4128 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2243 4176 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2400 4208 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2557 4120 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2715 4162 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2872 4161 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1337 4161 MXY +[16] 0 setdash +1 setlinewidth +1377 4380 MXY +79 -44 Dl +158 -52 Dl +157 -53 Dl +157 -17 Dl +157 -76 Dl +158 48 Dl +157 32 Dl +157 -88 Dl +158 42 Dl +157 -1 Dl +2206 4115(SortTime\(EC-sorting\))N +3137(........)X +1337 4380 MXY +[] 0 setdash +3 setlinewidth +1377 4777 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1456 4777 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1614 4773 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1771 4772 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1928 4771 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2085 4770 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2243 4770 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2400 4771 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2557 4771 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2715 4768 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2872 4771 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1377 4787 MXY +79 0 Dl +158 -4 Dl +157 -1 Dl +157 -1 Dl +157 -1 Dl +158 0 Dl +157 1 Dl +157 0 Dl +158 -3 Dl +157 3 Dl +2337 4712(SortTime\(TT-sorting\))N +1377 4822 MXY +1573 0 Dl +1377 MX +0 -1967 Dl +4822 MY +0 20 Dl +1351 4953(1)N +1535 4822 MXY +0 20 Dl +1509 4953(3)N +1692 4822 MXY +0 20 Dl +1666 4953(5)N +1849 4822 MXY +0 20 Dl +1823 4953(7)N +2007 4822 MXY +0 20 Dl +1981 4953(9)N +2164 4822 MXY +0 20 Dl +2111 4953(11)N +2321 4822 MXY +0 20 Dl +2268 4953(13)N +2478 4822 MXY +0 20 Dl +2425 4953(15)N +2636 4822 MXY +0 20 Dl +2583 4953(17)N +2793 4822 MXY +0 20 Dl +2740 4953(19)N +2950 4822 MXY +0 20 Dl +2897 4953(21)N +1377 4822 MXY +-20 0 Dl +1151 4863(0.00)N +1377 4707 MXY +-20 0 Dl +1098 4748(20.00)N +1377 4591 MXY +-20 0 Dl +1098 4632(40.00)N +1377 4475 MXY +-20 0 Dl +1098 4516(60.00)N +1377 4360 MXY +-20 0 Dl +1098 4401(80.00)N +1377 4244 MXY +-20 0 Dl +1045 4285(100.00)N +1377 4128 MXY +-20 0 Dl +1045 4169(120.00)N +1377 4013 MXY +-20 0 Dl +1045 4054(140.00)N +1377 3897 MXY +-20 0 Dl +1045 3938(160.00)N +1377 3781 MXY +-20 0 Dl +1045 3822(180.00)N +1377 3665 MXY +-20 0 Dl +1045 3706(200.00)N +1377 3550 MXY +-20 0 Dl +1045 3591(220.00)N +1377 3434 MXY +-20 0 Dl +1045 3475(240.00)N +1377 3318 MXY +-20 0 Dl +1045 3359(260.00)N +1377 3202 MXY +-20 0 Dl +1045 3243(280.00)N +1377 3087 MXY +-20 0 Dl +1045 3128(300.00)N +1377 2971 MXY +-20 0 Dl +1045 3012(320.00)N +1377 2855 MXY +-20 0 Dl +1045 2896(340.00)N +3 f +1508 5114(Figure)N +1 f +1805(11:)X +1952(Time)X +2180(vs.)X +2313(number)X +2631(of)X +2735(machines)X + +17 p +%%Page: 17 17 +12 s 0 xH 0 xS 1 f +10 s +3 f +576 474(Game-tree)N +963(search)X +3952(17)X +1 f +12 s +1377 1179 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1456 1133 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1614 1092 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1771 1023 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1928 1099 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2085 888 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2243 1044 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2400 1044 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2557 1000 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2715 1055 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2872 1158 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1337 1158 MXY +[16] 0 setdash +1 setlinewidth +1377 1189 MXY +79 -46 Dl +158 -41 Dl +157 -69 Dl +157 76 Dl +157 -211 Dl +158 156 Dl +157 0 Dl +157 -44 Dl +158 55 Dl +157 103 Dl +5 f +2449 1348(MWF\(EC-sorting\))N +1337 1189 MXY +[] 0 setdash +3 setlinewidth +1377 2739 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1456 2741 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1614 2732 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1771 2729 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1928 2728 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2085 2722 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2243 2721 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2400 2725 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2557 2724 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2715 2718 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2872 2720 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1377 2749 MXY +79 2 Dl +158 -9 Dl +157 -3 Dl +157 -1 Dl +157 -6 Dl +158 -1 Dl +157 4 Dl +157 -1 Dl +158 -6 Dl +157 2 Dl +2457 2669(MWF\(TT-sorting\))N +1377 2787 MXY +1573 0 Dl +1377 MX +0 -1967 Dl +2787 MY +0 20 Dl +1351 2918(1)N +1535 2787 MXY +0 20 Dl +1509 2918(3)N +1692 2787 MXY +0 20 Dl +1666 2918(5)N +1849 2787 MXY +0 20 Dl +1823 2918(7)N +2007 2787 MXY +0 20 Dl +1981 2918(9)N +2164 2787 MXY +0 20 Dl +2111 2918(11)N +2321 2787 MXY +0 20 Dl +2268 2918(13)N +2478 2787 MXY +0 20 Dl +2425 2918(15)N +2636 2787 MXY +0 20 Dl +2583 2918(17)N +2793 2787 MXY +0 20 Dl +2740 2918(19)N +2950 2787 MXY +0 20 Dl +2897 2918(21)N +1377 2787 MXY +-20 0 Dl +1151 2828(0.00)N +1377 2591 MXY +-20 0 Dl +1098 2632(25.00)N +1377 2394 MXY +-20 0 Dl +1098 2435(50.00)N +1377 2197 MXY +-20 0 Dl +1098 2238(75.00)N +1377 2000 MXY +-20 0 Dl +1045 2042(100.00)N +1377 1804 MXY +-20 0 Dl +1045 1845(125.00)N +1377 1607 MXY +-20 0 Dl +1045 1648(150.00)N +1377 1410 MXY +-20 0 Dl +1045 1451(175.00)N +1377 1214 MXY +-20 0 Dl +1045 1255(200.00)N +1377 1017 MXY +-20 0 Dl +1045 1058(225.00)N +1377 820 MXY +-20 0 Dl +1045 861(250.00)N +3 f +1288 3079(Figure)N +1 f +1585(12:)X +1732(Nodes)X +2001(examined)X +2400(vs.)X +2533(number)X +2851(of)X +2955(machines)X +776 3253(We)N +958(also)X +1161(used)X +1385(three-level)X +1846(sort)X +2038(for)X +2198(TT)X +2364(sorting.)X +2727(The)X +2925(great)X +3166(speed)X +3433(in)X +3556(this)X +3743(method)X +576 3361(allowed)N +912(us)X +1028(to)X +1134(build)X +1363(a)X +1437(complete)X +1822(game)X +2062(tree)X +2238(for)X +2381(our)X +2540(experiments.)X +3090(In)X +3200(previous)X +3561(experiments)X +576 3469(with)N +771(tic-tac-toe,)X +1211(we)X +1347(built)X +1548(a)X +1615(search)X +1885(tree)X +2054(with)X +2249(nine)X +2439(levels;)X +2715(the)X +2858(complete)X +3237(search)X +3508(tree)X +3678(for)X +3815(a)X +3883(4)X +9 f +(\264)S +1 f +3984(4)X +576 3577(board)N +819(has)X +971(16)X +1091(levels.)X +8 f +14 s +576 3781(6.)N +844(New)X +1112(results)X +1 f +12 s +776 3922(We)N +939(have)X +1150(new)X +1339(results)X +1619(based)X +1867(on)X +1992(adjustments)X +2481(made)X +2719(to)X +2824(MWF)X +3083(concerning)X +3541(the)X +3689(selection)X +576 4030(of)N +682(type-1)X +954(nodes.)X +1252(In)X +1358(dynamic)X +1716(MWF)X +1971(\(DMWF\),)X +2383(we)X +2521(decide)X +2799(which)X +3060(children)X +3401(of)X +3506(a)X +3574(type-1)X +3845(node)X +576 4138(to)N +687(fully)X +905(investigate)X +1359(not)X +1518(by)X +1650(taking)X +1927(the)X +2081(\256rst)X +2266(\(as)X +2414(in)X +2525(MWF\),)X +2846(but)X +3005(by)X +3137(taking)X +3414(all)X +3547(those)X +3787(whose)X +576 4246(static)N +815(value)X +1059(is)X +1158(above)X +1423(the)X +1576(90th)X +1782(percentile)X +2198(of)X +2312(its)X +2437(siblings.)X +2818(To)X +2959(our)X +3121(knowledge,)X +3601(no)X +3731(one)X +3904(has)X +576 4354(tried)N +781(algorithms)X +1221(that)X +1394(dynamically)X +1900(adjust)X +2159(their)X +2365(width)X +2613(of)X +2722(full)X +2885(evaluation)X +3316(based)X +3564(on)X +3689(evidence)X +576 4462(provided)N +955(in)X +1067(the)X +1221(tree.)X +1450(This)X +1657(adjustment)X +2116(can)X +2286(also)X +2477(be)X +2604(made)X +2849(to)X +2960(other)X +3194(algorithms)X +3642(like)X +3823(delay)X +576 4570(splitting)N +916(and)X +1079(ER.)X +776 4711(We)N +939(compared)X +1348(MWF)X +1606(and)X +1774(DMWF)X +2101(under)X +2349(EC)X +2501(sorting)X +2797(for)X +2939(a)X +3012(tic-tac-toe)X +3434(tree)X +3609(with)X +3810(a)X +3883(4)X +9 f +(\264)S +1 f +3984(4)X +576 4819(board.)N +873(Figure)X +1154(13)X +1280(shows)X +1549(the)X +1697(comparison)X +2176(of)X +2286(the)X +2434(total)X +2636(time)X +2838(\(including)X +3264(communication)X +3893(and)X +576 4927(idle)N +745(time\))X +973(between)X +1318(MWF)X +1571(and)X +1734(DMWF.)X +2104(DMWF)X +2426(is)X +2514(about)X +2752(one-third)X +3129(faster)X +3368(than)X +3559(MWF.)X +3861(This)X +576 5035(speed)N +843(is)X +955(achieved)X +1346(with)X +1565(even)X +1795(less)X +1987(sorting)X +2302(time)X +2522(because)X +2875(it)X +2977(generates)X +3389(fewer)X +3656(nodes,)X +3952(as)X +576 5143(demonstrated)N +1124(in)X +1228(Figure)X +1508(14)X +1633(\(number)X +1989(of)X +2099(nodes)X +2353(are)X +2501(in)X +2606(multiples)X +2995(of)X +3105(1000\).)X +3407(There)X +3662(is)X +3756(also)X +3941(an)X +576 5251(improvement)N +1114(in)X +1213(the)X +1355(ef\256ciency)X +1759(\(Figure)X +2066(15\).)X + +18 p +%%Page: 18 18 +12 s 0 xH 0 xS 1 f +10 s +3 f +576 474(Game-tree)N +963(search)X +3952(18)X +1 f +12 s +1377 1867 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1456 1852 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1614 1809 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1771 1762 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1928 1708 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2085 1607 MXY +0 19 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2243 1618 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2400 1533 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2557 1494 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2715 1393 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2872 1305 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1337 1305 MXY +[16] 0 setdash +1 setlinewidth +1377 1877 MXY +79 -15 Dl +158 -43 Dl +157 -47 Dl +157 -54 Dl +157 -102 Dl +158 12 Dl +157 -85 Dl +157 -39 Dl +158 -101 Dl +157 -88 Dl +5 f +2428 1286(TotalTime\(DMWF\))N +1337 1877 MXY +[] 0 setdash +3 setlinewidth +1377 2296 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1456 2296 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1614 2303 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1771 2306 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1928 2303 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2085 2296 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2243 2304 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2400 2280 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2557 2293 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2715 2284 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2872 2260 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1337 2260 MXY +[16] 0 setdash +1 setlinewidth +1377 2306 MXY +79 0 Dl +158 7 Dl +157 3 Dl +157 -3 Dl +157 -7 Dl +158 8 Dl +157 -24 Dl +157 13 Dl +158 -9 Dl +157 -24 Dl +2446 2458(SortTime\(DMWF\))N +1337 2306 MXY +[] 0 setdash +3 setlinewidth +1377 1611 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1456 1517 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1614 1395 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1771 1244 MXY +0 19 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1928 1190 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2085 1002 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2243 1047 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2400 1071 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2557 896 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2715 890 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2872 894 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1377 1621 MXY +79 -94 Dl +158 -122 Dl +157 -152 Dl +157 -53 Dl +157 -188 Dl +158 45 Dl +157 24 Dl +157 -175 Dl +158 -6 Dl +157 4 Dl +2383 893(TotalTime\(MWF\))N +1377 2348 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1456 2305 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1614 2254 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1771 2203 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1928 2186 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2085 2112 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2243 2159 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2400 2190 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2557 2105 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2715 2145 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2872 2145 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1377 2358 MXY +79 -43 Dl +158 -51 Dl +157 -51 Dl +157 -17 Dl +157 -74 Dl +158 47 Dl +157 31 Dl +157 -85 Dl +158 40 Dl +157 0 Dl +2481 2089(SortTime\(MWF\))N +1377 2787 MXY +1573 0 Dl +1377 MX +0 -1967 Dl +2787 MY +0 20 Dl +1351 2918(1)N +1535 2787 MXY +0 20 Dl +1509 2918(3)N +1692 2787 MXY +0 20 Dl +1666 2918(5)N +1849 2787 MXY +0 20 Dl +1823 2918(7)N +2007 2787 MXY +0 20 Dl +1981 2918(9)N +2164 2787 MXY +0 20 Dl +2111 2918(11)N +2321 2787 MXY +0 20 Dl +2268 2918(13)N +2478 2787 MXY +0 20 Dl +2425 2918(15)N +2636 2787 MXY +0 20 Dl +2583 2918(17)N +2793 2787 MXY +0 20 Dl +2740 2918(19)N +2950 2787 MXY +0 20 Dl +2897 2918(21)N +1377 2787 MXY +-20 0 Dl +1151 2828(0.00)N +1377 2506 MXY +-20 0 Dl +1098 2547(50.00)N +1377 2225 MXY +-20 0 Dl +1045 2266(100.00)N +1377 1944 MXY +-20 0 Dl +1045 1985(150.00)N +1377 1663 MXY +-20 0 Dl +1045 1704(200.00)N +1377 1382 MXY +-20 0 Dl +1045 1423(250.00)N +1377 1101 MXY +-20 0 Dl +1045 1142(300.00)N +1377 820 MXY +-20 0 Dl +1045 861(350.00)N +3 f +1508 3079(Figure)N +1 f +1805(13:)X +1952(Time)X +2180(vs.)X +2313(number)X +2631(of)X +2735(machines)X +1377 3652 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1456 3606 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1614 3565 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1771 3496 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1928 3572 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2085 3361 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2243 3517 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2400 3517 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2557 3473 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2715 3528 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2872 3631 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1337 3631 MXY +[16] 0 setdash +1 setlinewidth +1377 3662 MXY +79 -46 Dl +158 -41 Dl +157 -69 Dl +157 76 Dl +157 -211 Dl +158 156 Dl +157 0 Dl +157 -44 Dl +158 55 Dl +157 103 Dl +5 f +2785 3821(MWF)N +1337 3662 MXY +[] 0 setdash +3 setlinewidth +1377 4212 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1456 4211 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1614 4218 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1771 4249 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1928 4232 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2085 4248 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2243 4282 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2400 4262 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2557 4281 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2715 4306 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2872 4258 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1377 4222 MXY +79 -1 Dl +158 7 Dl +157 31 Dl +157 -17 Dl +157 16 Dl +158 34 Dl +157 -20 Dl +157 19 Dl +158 25 Dl +157 -48 Dl +2751 4293(DMWF)N +1377 5260 MXY +1573 0 Dl +1377 MX +0 -1967 Dl +5260 MY +0 20 Dl +1351 5391(1)N +1535 5260 MXY +0 20 Dl +1509 5391(3)N +1692 5260 MXY +0 20 Dl +1666 5391(5)N +1849 5260 MXY +0 20 Dl +1823 5391(7)N +2007 5260 MXY +0 20 Dl +1981 5391(9)N +2164 5260 MXY +0 20 Dl +2111 5391(11)N +2321 5260 MXY +0 20 Dl +2268 5391(13)N +2478 5260 MXY +0 20 Dl +2425 5391(15)N +2636 5260 MXY +0 20 Dl +2583 5391(17)N +2793 5260 MXY +0 20 Dl +2740 5391(19)N +2950 5260 MXY +0 20 Dl +2897 5391(21)N +1377 5260 MXY +-20 0 Dl +1151 5301(0.00)N +1377 5064 MXY +-20 0 Dl +1098 5105(25.00)N +1377 4867 MXY +-20 0 Dl +1098 4908(50.00)N +1377 4670 MXY +-20 0 Dl +1098 4711(75.00)N +1377 4473 MXY +-20 0 Dl +1045 4515(100.00)N +1377 4277 MXY +-20 0 Dl +1045 4318(125.00)N +1377 4080 MXY +-20 0 Dl +1045 4121(150.00)N +1377 3883 MXY +-20 0 Dl +1045 3924(175.00)N +1377 3687 MXY +-20 0 Dl +1045 3728(200.00)N +1377 3490 MXY +-20 0 Dl +1045 3531(225.00)N +1377 3293 MXY +-20 0 Dl +1045 3334(250.00)N +3 f +1288 5552(Figure)N +1 f +1585(14:)X +1732(Nodes)X +2001(examined)X +2400(vs.)X +2533(number)X +2851(of)X +2955(machines)X + +19 p +%%Page: 19 19 +12 s 0 xH 0 xS 1 f +10 s +3 f +576 474(Game-tree)N +963(search)X +3952(19)X +1 f +12 s +1377 810 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1456 961 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1614 1123 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1771 1284 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1928 1335 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2085 1487 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2243 1455 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2400 1436 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2557 1562 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2715 1566 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2872 1566 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1377 820 MXY +79 151 Dl +158 162 Dl +157 161 Dl +157 51 Dl +157 152 Dl +158 -32 Dl +157 -19 Dl +157 126 Dl +158 4 Dl +157 0 Dl +5 f +2785 1712(MWF)N +1377 810 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1456 832 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1614 928 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1771 1024 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1928 1115 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2085 1239 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2243 1251 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2400 1349 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2557 1369 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2715 1550 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2872 1497 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1337 1497 MXY +[16] 0 setdash +1 setlinewidth +1377 820 MXY +79 22 Dl +158 96 Dl +157 96 Dl +157 91 Dl +157 124 Dl +158 12 Dl +157 98 Dl +157 20 Dl +158 181 Dl +157 -53 Dl +2751 1506(DMWF)N +1337 820 MXY +[] 0 setdash +3 setlinewidth +1377 2787 MXY +1573 0 Dl +1377 MX +0 -1967 Dl +2787 MY +0 20 Dl +1351 2918(1)N +1535 2787 MXY +0 20 Dl +1509 2918(3)N +1692 2787 MXY +0 20 Dl +1666 2918(5)N +1849 2787 MXY +0 20 Dl +1823 2918(7)N +2007 2787 MXY +0 20 Dl +1981 2918(9)N +2164 2787 MXY +0 20 Dl +2111 2918(11)N +2321 2787 MXY +0 20 Dl +2268 2918(13)N +2478 2787 MXY +0 20 Dl +2425 2918(15)N +2636 2787 MXY +0 20 Dl +2583 2918(17)N +2793 2787 MXY +0 20 Dl +2740 2918(19)N +2950 2787 MXY +0 20 Dl +2897 2918(21)N +1377 2787 MXY +-20 0 Dl +1151 2828(0.00)N +1377 2591 MXY +-20 0 Dl +1151 2632(0.10)N +1377 2394 MXY +-20 0 Dl +1151 2435(0.20)N +1377 2197 MXY +-20 0 Dl +1151 2238(0.30)N +1377 2000 MXY +-20 0 Dl +1151 2042(0.40)N +1377 1804 MXY +-20 0 Dl +1151 1845(0.50)N +1377 1607 MXY +-20 0 Dl +1151 1648(0.60)N +1377 1410 MXY +-20 0 Dl +1151 1451(0.70)N +1377 1214 MXY +-20 0 Dl +1151 1255(0.80)N +1377 1017 MXY +-20 0 Dl +1151 1058(0.90)N +1377 820 MXY +-20 0 Dl +1151 861(1.00)N +3 f +1424 3079(Figure)N +1 f +1721(15:)X +1868(Ef\256ciency)X +2288(vs)X +2397(number)X +2715(of)X +2819(machines)X +776 3253(We)N +952(also)X +1149(compared)X +1571(MWF)X +1842(and)X +2023(DMWF)X +2363(under)X +2624(EC)X +2789(sorting)X +3098(for)X +3252(Othello)X +3583(with)X +3797(a)X +3883(6)X +9 f +(\264)S +1 f +3984(6)X +576 3361(board.)N +887(Since)X +1145(Othello)X +1478(is)X +1585(a)X +1671(more)X +1912(complicated)X +2427(game)X +2679(than)X +2888(tic-tac-toe,)X +3347(the)X +3508(sorting)X +3818(depth)X +576 3469(parameter)N +986(was)X +1160(set)X +1292(to)X +1392(6)X +1465(levels,)X +1739(as)X +1844(mentioned)X +2276(above.)X +2579(The)X +2754(results)X +3030(of)X +3135(this)X +3299(experiment,)X +3782(shown)X +576 3577(in)N +675(Figures)X +987(16,)X +1131(17)X +1251(and)X +1414(18,)X +1558(are)X +1700(similar)X +1992(to)X +2091(the)X +2233(results)X +2508(from)X +2719(tic-tac-toe.)X + +20 p +%%Page: 20 20 +12 s 0 xH 0 xS 1 f +10 s +3 f +576 474(Game-tree)N +963(search)X +3952(20)X +1 f +12 s +1377 2410 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1456 2337 MXY +0 19 Dl +0 -9 Dl +10 0 Dl +-20 0 Dl +1614 2219 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1771 2139 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1928 2043 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2085 1982 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2243 1901 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2400 1792 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2557 1764 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2715 1617 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2872 1568 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1337 1568 MXY +[16] 0 setdash +1 setlinewidth +1377 2420 MXY +79 -73 Dl +158 -118 Dl +157 -80 Dl +157 -96 Dl +157 -61 Dl +158 -81 Dl +157 -109 Dl +157 -28 Dl +158 -147 Dl +157 -49 Dl +5 f +2349 1624(TotalTime\(DMWF\))N +1337 2420 MXY +[] 0 setdash +3 setlinewidth +1377 2732 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1456 2721 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1614 2722 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1771 2718 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1928 2711 MXY +0 19 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2085 2712 MXY +0 19 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2243 2709 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2400 2701 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2557 2699 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2715 2704 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2872 2687 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1337 2687 MXY +[16] 0 setdash +1 setlinewidth +1377 2742 MXY +79 -11 Dl +158 1 Dl +157 -4 Dl +157 -8 Dl +157 1 Dl +158 -2 Dl +157 -8 Dl +157 -2 Dl +158 5 Dl +157 -17 Dl +2367 2652(SortTime\(DMWF\))N +1337 2742 MXY +[] 0 setdash +3 setlinewidth +1377 2167 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1456 2087 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1614 1968 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1771 1859 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1928 1825 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2085 1738 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2243 1648 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2400 1511 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2557 1361 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2715 1145 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2872 827 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1377 2177 MXY +79 -80 Dl +158 -119 Dl +157 -109 Dl +157 -34 Dl +157 -87 Dl +158 -90 Dl +157 -137 Dl +157 -150 Dl +158 -216 Dl +157 -318 Dl +2383 883(TotalTime\(MWF\))N +1377 2719 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1456 2714 MXY +0 19 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1614 2703 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1771 2706 MXY +0 19 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1928 2707 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2085 2702 MXY +0 19 Dl +0 -9 Dl +10 0 Dl +-20 0 Dl +2243 2696 MXY +0 19 Dl +0 -9 Dl +10 0 Dl +-20 0 Dl +2400 2698 MXY +0 19 Dl +0 -9 Dl +10 0 Dl +-20 0 Dl +2557 2692 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2715 2679 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2872 2670 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1377 2729 MXY +79 -6 Dl +158 -10 Dl +157 2 Dl +157 2 Dl +157 -5 Dl +158 -6 Dl +157 2 Dl +157 -6 Dl +158 -13 Dl +157 -9 Dl +2402 2559(SortTime\(MWF\))N +1377 2787 MXY +1573 0 Dl +1377 MX +0 -1967 Dl +2787 MY +0 20 Dl +1351 2918(1)N +1535 2787 MXY +0 20 Dl +1509 2918(3)N +1692 2787 MXY +0 20 Dl +1666 2918(5)N +1849 2787 MXY +0 20 Dl +1823 2918(7)N +2007 2787 MXY +0 20 Dl +1981 2918(9)N +2164 2787 MXY +0 20 Dl +2111 2918(11)N +2321 2787 MXY +0 20 Dl +2268 2918(13)N +2478 2787 MXY +0 20 Dl +2425 2918(15)N +2636 2787 MXY +0 20 Dl +2583 2918(17)N +2793 2787 MXY +0 20 Dl +2740 2918(19)N +2950 2787 MXY +0 20 Dl +2897 2918(21)N +1377 2787 MXY +-20 0 Dl +1151 2828(0.00)N +1377 2656 MXY +-20 0 Dl +1045 2697(100.00)N +1377 2525 MXY +-20 0 Dl +1045 2566(200.00)N +1377 2394 MXY +-20 0 Dl +1045 2435(300.00)N +1377 2263 MXY +-20 0 Dl +1045 2304(400.00)N +1377 2132 MXY +-20 0 Dl +1045 2173(500.00)N +1377 2000 MXY +-20 0 Dl +1045 2042(600.00)N +1377 1869 MXY +-20 0 Dl +1045 1910(700.00)N +1377 1738 MXY +-20 0 Dl +1045 1779(800.00)N +1377 1607 MXY +-20 0 Dl +1045 1648(900.00)N +1377 1476 MXY +-20 0 Dl +992 1517(1000.00)N +1377 1345 MXY +-20 0 Dl +992 1386(1100.00)N +1377 1214 MXY +-20 0 Dl +992 1255(1200.00)N +1377 1082 MXY +-20 0 Dl +992 1123(1300.00)N +1377 951 MXY +-20 0 Dl +992 992(1400.00)N +1377 820 MXY +-20 0 Dl +992 861(1500.00)N +3 f +1508 3079(Figure)N +1 f +1805(16:)X +1952(Time)X +2180(vs.)X +2313(number)X +2631(of)X +2735(machines)X +1377 4199 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1456 4080 MXY +0 19 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1614 3953 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1771 3825 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1928 3803 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2085 3756 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2243 3631 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2400 3510 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2557 3430 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2715 3413 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2872 3349 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1337 3349 MXY +[16] 0 setdash +1 setlinewidth +1377 4209 MXY +79 -120 Dl +158 -126 Dl +157 -128 Dl +157 -22 Dl +157 -47 Dl +158 -125 Dl +157 -121 Dl +157 -80 Dl +158 -17 Dl +157 -64 Dl +5 f +2785 3389(MWF)N +1337 4209 MXY +[] 0 setdash +3 setlinewidth +1377 4662 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1456 4559 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1614 4419 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1771 4366 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1928 4258 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2085 4262 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2243 4186 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2400 4112 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2557 4133 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2715 4068 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +2872 4003 MXY +0 20 Dl +0 -10 Dl +10 0 Dl +-20 0 Dl +1377 4672 MXY +79 -103 Dl +158 -140 Dl +157 -53 Dl +157 -108 Dl +157 4 Dl +158 -76 Dl +157 -74 Dl +157 21 Dl +158 -65 Dl +157 -65 Dl +2751 4018(DMWF)N +1377 5260 MXY +1573 0 Dl +1377 MX +0 -1967 Dl +5260 MY +0 20 Dl +1351 5391(1)N +1535 5260 MXY +0 20 Dl +1509 5391(3)N +1692 5260 MXY +0 20 Dl +1666 5391(5)N +1849 5260 MXY +0 20 Dl +1823 5391(7)N +2007 5260 MXY +0 20 Dl +1981 5391(9)N +2164 5260 MXY +0 20 Dl +2111 5391(11)N +2321 5260 MXY +0 20 Dl +2268 5391(13)N +2478 5260 MXY +0 20 Dl +2425 5391(15)N +2636 5260 MXY +0 20 Dl +2583 5391(17)N +2793 5260 MXY +0 20 Dl +2740 5391(19)N +2950 5260 MXY +0 20 Dl +2897 5391(21)N +1377 5260 MXY +-20 0 Dl +1151 5301(0.00)N +1377 5064 MXY +-20 0 Dl +1098 5105(50.00)N +1377 4867 MXY +-20 0 Dl +1045 4908(100.00)N +1377 4670 MXY +-20 0 Dl +1045 4711(150.00)N +1377 4473 MXY +-20 0 Dl +1045 4515(200.00)N +1377 4277 MXY +-20 0 Dl +1045 4318(250.00)N +1377 4080 MXY +-20 0 Dl +1045 4121(300.00)N +1377 3883 MXY +-20 0 Dl +1045 3924(350.00)N +1377 3687 MXY +-20 0 Dl +1045 3728(400.00)N +1377 3490 MXY +-20 0 Dl +1045 3531(450.00)N +1377 3293 MXY +-20 0 Dl +1045 3334(500.00)N +3 f +1288 5552(Figure)N +1 f +1585(17:)X +1732(Nodes)X +2001(examined)X +2400(vs.)X +2533(number)X +2851(of)X +2955(machines)X + +21 p +%%Page: 21 21 +12 s 0 xH 0 xS 1 f +10 s +3 f +576 474(Game-tree)N +963(search)X +3952(21)X +1 f +12 s +981 826 MXY +0 30 Dl +0 -15 Dl +15 0 Dl +-30 0 Dl +1101 1169 MXY +0 30 Dl +0 -15 Dl +15 0 Dl +-30 0 Dl +1340 1560 MXY +0 30 Dl +0 -15 Dl +15 0 Dl +-31 0 Dl +1578 1826 MXY +0 30 Dl +0 -15 Dl +15 0 Dl +-30 0 Dl +1817 1897 MXY +0 31 Dl +0 -16 Dl +15 0 Dl +-30 0 Dl +2056 2059 MXY +0 30 Dl +0 -15 Dl +15 0 Dl +-30 0 Dl +2294 2199 MXY +0 30 Dl +0 -15 Dl +16 0 Dl +-31 0 Dl +2533 2373 MXY +0 30 Dl +0 -15 Dl +15 0 Dl +-30 0 Dl +2772 2513 MXY +0 30 Dl +0 -15 Dl +15 0 Dl +-30 0 Dl +3011 2698 MXY +0 30 Dl +0 -15 Dl +15 0 Dl +-30 0 Dl +3249 2880 MXY +0 31 Dl +0 -16 Dl +16 0 Dl +-31 0 Dl +981 841 MXY +120 343 Dl +239 391 Dl +238 266 Dl +239 71 Dl +239 162 Dl +238 140 Dl +239 174 Dl +239 140 Dl +239 185 Dl +238 182 Dl +5 f +3178 2885(MWF)N +981 826 MXY +0 30 Dl +0 -15 Dl +15 0 Dl +-30 0 Dl +1101 1318 MXY +0 31 Dl +0 -16 Dl +15 0 Dl +-30 0 Dl +1340 1844 MXY +0 31 Dl +0 -16 Dl +15 0 Dl +-31 0 Dl +1578 2092 MXY +0 30 Dl +0 -15 Dl +15 0 Dl +-30 0 Dl +1817 2319 MXY +0 30 Dl +0 -15 Dl +15 0 Dl +-30 0 Dl +2056 2432 MXY +0 31 Dl +0 -15 Dl +15 0 Dl +-30 0 Dl +2294 2560 MXY +0 31 Dl +0 -15 Dl +16 0 Dl +-31 0 Dl +2533 2701 MXY +0 30 Dl +0 -15 Dl +15 0 Dl +-30 0 Dl +2772 2731 MXY +0 30 Dl +0 -15 Dl +15 0 Dl +-30 0 Dl +3011 2868 MXY +0 31 Dl +0 -16 Dl +15 0 Dl +-30 0 Dl +3249 2907 MXY +0 30 Dl +0 -15 Dl +16 0 Dl +-31 0 Dl +920 2907 MXY +[16] 0 setdash +1 setlinewidth +981 841 MXY +120 492 Dl +239 526 Dl +238 248 Dl +239 227 Dl +239 114 Dl +238 128 Dl +239 140 Dl +239 30 Dl +239 137 Dl +238 39 Dl +3144 3034(DMWF)N +920 841 MXY +[] 0 setdash +3 setlinewidth +981 3827 MXY +2387 0 Dl +981 MX +0 -2986 Dl +3827 MY +0 30 Dl +955 3984(1)N +1220 3827 MXY +0 30 Dl +1194 3984(3)N +1459 3827 MXY +0 30 Dl +1433 3984(5)N +1697 3827 MXY +0 30 Dl +1671 3984(7)N +1936 3827 MXY +0 30 Dl +1910 3984(9)N +2175 3827 MXY +0 30 Dl +2122 3984(11)N +2413 3827 MXY +0 30 Dl +2360 3984(13)N +2652 3827 MXY +0 30 Dl +2599 3984(15)N +2891 3827 MXY +0 30 Dl +2838 3984(17)N +3130 3827 MXY +0 30 Dl +3077 3984(19)N +3368 3827 MXY +0 30 Dl +3315 3984(21)N +981 3827 MXY +-30 0 Dl +734 3847(0.00)N +981 3528 MXY +-30 0 Dl +734 3549(0.10)N +981 3230 MXY +-30 0 Dl +734 3250(0.20)N +981 2931 MXY +-30 0 Dl +734 2951(0.30)N +981 2632 MXY +-30 0 Dl +734 2653(0.40)N +981 2334 MXY +-30 0 Dl +734 2354(0.50)N +981 2035 MXY +-30 0 Dl +734 2056(0.60)N +981 1737 MXY +-30 0 Dl +734 1757(0.70)N +981 1438 MXY +-30 0 Dl +734 1458(0.80)N +981 1139 MXY +-30 0 Dl +734 1160(0.90)N +981 841 MXY +-30 0 Dl +734 861(1.00)N +3 f +1424 4181(Figure)N +1 f +1721(18:)X +1868(Ef\256ciency)X +2288(vs)X +2397(number)X +2715(of)X +2819(machines)X +8 f +14 s +576 4418(7.)N +844(Future)X +1313(work)X +1 f +12 s +776 4559(With)N +996(enhancements)X +1569(made)X +1805(to)X +1907(DIB)X +2099(for)X +2239(achieving)X +2642(high)X +2841(ef\256ciency)X +3249(in)X +3352(game)X +3589(tree)X +3762(search,)X +576 4667(we)N +722(have)X +938(developed)X +1368(an)X +1492(environment)X +2012(in)X +2120(which)X +2388(we)X +2533(can)X +2700(test)X +2867(different)X +3232(algorithms)X +3677(in)X +3785(a)X +3861(con-)X +576 4775(sistent)N +853(way.)X +1092(These)X +1353(algorithms)X +1796(have)X +2009(been)X +2222(examined)X +2628(using)X +2867(a)X +2941(test)X +3107(suite)X +3321(of)X +3433(problems)X +3823(taken)X +576 4883(from)N +793(game)X +1032(trees)X +1244(for)X +1386(checkers,)X +1776(tic-tac-toe,)X +2221(and)X +2389(Othello.)X +2755(These)X +3014(games)X +3289(are)X +3436(coded)X +3695(indepen-)X +576 4991(dently)N +841(from)X +1052(the)X +1194(search)X +1464(algorithms,)X +1924(thus)X +2108(contributing)X +2603(to)X +2702(the)X +2844(consistency)X +3317(of)X +3421(the)X +3563(experiment.)X +776 5132(We)N +954(are)X +1116(currently)X +1508(testing)X +1809(these)X +2051(algorithms)X +2507(on)X +2647(a)X +2735(26-processor)X +3276(Sequent)X +3631(Symmetry)X +576 5240(machine.)N +992(Our)X +1182(future)X +1453(plans)X +1697(include)X +2022(the)X +2181(use)X +2350(of)X +2471(a)X +2555(KSR)X +2782(multicomputer)X +3391(with)X +3603(64)X +3740(cpus)X +3957(to)X +576 5348(examine)N +927(the)X +1069(search)X +1339(algorithms)X +1775(with)X +1970(a)X +2037(larger)X +2286(number)X +2604(of)X +2708(processors.)X +776 5489(We)N +944(will)X +1128(also)X +1317(experiment)X +1785(with)X +1990(worst-case)X +2435(sorting,)X +2760(not)X +2917(because)X +3256(it)X +3345(would)X +3620(be)X +3746(used)X +3957(in)X +576 5597(practice,)N +930(but)X +1077(to)X +1176(see)X +1323(how)X +1512(each)X +1713(algorithm)X +2112(is)X +2200(sensitive)X +2561(to)X +2660(sorting.)X + +22 p +%%Page: 22 22 +12 s 0 xH 0 xS 1 f +10 s +3 f +576 474(Game-tree)N +963(search)X +3952(22)X +8 f +14 s +576 780(References)N +1 f +12 s +576 921(1.)N +776(Raphael)X +1122(Finkel)X +1399(and)X +1569(Udi)X +1744(Manber,)X +2098(``DIB)X +2358(\320)X +2485(A)X +2585(Distributed)X +3049 0.2356(Implementation)AX +3691(of)X +3802(Back-)X +776 1029(tracking,'')N +2 f +1223(ACM)X +1469(Transactions)X +2013(on)X +2152(Programming)X +2733(Languages)X +3196(and)X +3382(Systems)X +3 f +3728(9)X +1 f +(\(2\))S +3912(pp.)X +776 1137(235-256)N +1120(\(April)X +1379(1987\).)X +576 1278(2.)N +776(Vipin)X +1024(Kumar)X +1320(and)X +1488(V.)X +1610(Nageshwara)X +2115(Rao,)X +2 f +2324(Scalable)X +2686(Parallel)X +3032(Formation)X +3473(of)X +3578(Depth-First)X +776 1386(Search)N +1 f +1043(.)X +576 1527(3.)N +776(Igor)X +960(Steinberg)X +1353(and)X +1516(Marvin)X +1823(Solomon,)X +2 f +2218(Searching)X +2632(Game)X +2885(tree)X +3059(in)X +3158(Parallel)X +1 f +3474(.)X +576 1668(4.)N +776(John)X +1000(Philip)X +1273(Fishburn,)X +1681(``Analysis)X +2124(of)X +2247(speed)X +2509(up)X +2648(in)X +2767(Distributed)X +3244(Algorithms,'')X +3814(Ph.D.)X +776 1776(Thesis,)N +1140(Department)X +1660(of)X +1805(Computer)X +2255(Science,)X +2644(University)X +3114(of)X +3258(Wisconsin-Madison)X +776 1884(\(1981\).)N +576 2025(5.)N +776(D.)X +907(V.)X +1038(Knuth)X +1316(and)X +1493(R.)X +1619(W.)X +1772(Moore,)X +2090(``An)X +2309(analysis)X +2657(of)X +2775(alpha-beta)X +3215(prunning,'')X +2 f +3689(Arti\256cial)X +776 2133(Intelligence)N +3 f +1256(6)X +1 f +1328(pp.)X +1472(293-326)X +1816(\(1975\).)X +576 2274(6.)N +776(Selim)X +1048(G.)X +1188(Akl,)X +1403(David)X +1685(T.)X +1815(Barnard,)X +2196(and)X +2382(Ralph)X +2659(J.)X +2767(Doran,)X +3078(``Desing,)X +3485(Analysis,)X +3893(and)X +776 2382 0.2356(Implementation)AN +1432(of)X +1557(a)X +1645(Parallel)X +1985(Tree)X +2207(Search)X +2514(Algorithm,'')X +2 f +3048(IEEE)X +3 f +3301(PAMI-4)X +1 f +3637(\(2\)\(March)X +776 2490(1982\).)N +576 2631(7.)N +776(R.)X +891(A.)X +1011(Finkel)X +1284(and)X +1450(J.)X +1538(P.)X +1642(Fishburn,)X +2034(``Parallelism)X +2559(in)X +2661(alpha-beta)X +3090(search,'')X +2 f +3452(Arti\256cial)X +3823(Intel-)X +776 2739(ligence)N +3 f +1079(19)X +1 f +1199(pp.)X +1343(89-106)X +1639(\(1982\).)X +576 2880(8.)N +776(T.)X +903(A.)X +1040(Marsland)X +1448(and)X +1632(M.)X +1786(Campbell,)X +2230(``Parallel)X +2634(Search)X +2941(of)X +3066(Strongly)X +3442(Ordered)X +3802(Game)X +776 2988(Trees,'')N +2 f +1102(Computing)X +1553(Surveys)X +3 f +1876(14)X +1 f +(\(4\))S +2108(pp.)X +2252(533-551)X +2596(\(December)X +3048(1982\).)X + +22 p +%%Trailer +xt + +xs |