%!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(\(jrezaie@ms.uky.edu\))X 14 s 1482 1329(Raphael)N 1877(Finkel)X 12 s 2247(\(raphael@ms.uky.edu\))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