%!PS-Adobe-2.0 %%Creator: dvips 5.55 Copyright 1986, 1994 Radical Eye Software %%Title: taxonomy.dvi %%CreationDate: Wed Jun 12 00:05:43 1996 %%Pages: 14 %%PageOrder: Ascend %%BoundingBox: 0 0 612 792 %%EndComments %DVIPSCommandLine: dvips taxonomy %DVIPSParameters: dpi=300, comments removed %DVIPSSource: TeX output 1996.06.12:0003 %%BeginProcSet: tex.pro /TeXDict 250 dict def TeXDict begin /N{def}def /B{bind def}N /S{exch}N /X{S N}B /TR{translate}N /isls false N /vsize 11 72 mul N /hsize 8.5 72 mul N /landplus90{false}def /@rigin{isls{[0 landplus90{1 -1}{-1 1} ifelse 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale isls{landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div hsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul TR[matrix currentmatrix{dup dup round sub abs 0.00001 lt{round}if} forall round exch round exch]setmatrix}N /@landscape{/isls true N}B /@manualfeed{statusdict /manualfeed true put}B /@copies{/#copies X}B /FMat[1 0 0 -1 0 0]N /FBB[0 0 0 0]N /nn 0 N /IE 0 N /ctr 0 N /df-tail{ /nn 8 dict N nn begin /FontType 3 N /FontMatrix fntrx N /FontBBox FBB N string /base X array /BitMaps X /BuildChar{CharBuilder}N /Encoding IE N end dup{/foo setfont}2 array copy cvx N load 0 nn put /ctr 0 N[}B /df{ /sf 1 N /fntrx FMat N df-tail}B /dfs{div /sf X /fntrx[sf 0 0 sf neg 0 0] N df-tail}B /E{pop nn dup definefont setfont}B /ch-width{ch-data dup length 5 sub get}B /ch-height{ch-data dup length 4 sub get}B /ch-xoff{ 128 ch-data dup length 3 sub get sub}B /ch-yoff{ch-data dup length 2 sub get 127 sub}B /ch-dx{ch-data dup length 1 sub get}B /ch-image{ch-data dup type /stringtype ne{ctr get /ctr ctr 1 add N}if}B /id 0 N /rw 0 N /rc 0 N /gp 0 N /cp 0 N /G 0 N /sf 0 N /CharBuilder{save 3 1 roll S dup /base get 2 index get S /BitMaps get S get /ch-data X pop /ctr 0 N ch-dx 0 ch-xoff ch-yoff ch-height sub ch-xoff ch-width add ch-yoff setcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-yoff .1 sub]{ch-image}imagemask restore}B /D{/cc X dup type /stringtype ne{]} if nn /base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{dup dup length 1 sub dup 2 index S get sf div put}if put /ctr ctr 1 add N}B /I{ cc 1 add D}B /bop{userdict /bop-hook known{bop-hook}if /SI save N @rigin 0 0 moveto /V matrix currentmatrix dup 1 get dup mul exch 0 get dup mul add .99 lt{/QV}{/RV}ifelse load def pop pop}N /eop{SI restore showpage userdict /eop-hook known{eop-hook}if}N /@start{userdict /start-hook known{start-hook}if pop /VResolution X /Resolution X 1000 div /DVImag X /IE 256 array N 0 1 255{IE S 1 string dup 0 3 index put cvn put}for 65781.76 div /vsize X 65781.76 div /hsize X}N /p{show}N /RMat[1 0 0 -1 0 0]N /BDot 260 string N /rulex 0 N /ruley 0 N /v{/ruley X /rulex X V}B /V {}B /RV statusdict begin /product where{pop product dup length 7 ge{0 7 getinterval dup(Display)eq exch 0 4 getinterval(NeXT)eq or}{pop false} ifelse}{false}ifelse end{{gsave TR -.1 .1 TR 1 1 scale rulex ruley false RMat{BDot}imagemask grestore}}{{gsave TR -.1 .1 TR rulex ruley scale 1 1 false RMat{BDot}imagemask grestore}}ifelse B /QV{gsave newpath transform round exch round exch itransform moveto rulex 0 rlineto 0 ruley neg rlineto rulex neg 0 rlineto fill grestore}B /a{moveto}B /delta 0 N /tail {dup /delta X 0 rmoveto}B /M{S p delta add tail}B /b{S p tail}B /c{-4 M} B /d{-3 M}B /e{-2 M}B /f{-1 M}B /g{0 M}B /h{1 M}B /i{2 M}B /j{3 M}B /k{ 4 M}B /w{0 rmoveto}B /l{p -4 w}B /m{p -3 w}B /n{p -2 w}B /o{p -1 w}B /q{ p 1 w}B /r{p 2 w}B /s{p 3 w}B /t{p 4 w}B /x{0 S rmoveto}B /y{3 2 roll p a}B /bos{/SS save N}B /eos{SS restore}B end %%EndProcSet TeXDict begin 40258431 52099146 1000 300 300 (/usr/maligne2/grad/brock/Writing/taxonomy/taxonomy.dvi) @start /Fa 2 101 df<00200060006000C000C000C00180018001800300030003000600 06000C000C000C00180018001800300030003000600060006000C000C000C0000B1D7E95 11>61 D<007C000C0018001800180018003007B00C7010703060606060606060C0C0C0C8 C0C841C862D03C700E147E9311>100 D E /Fb 4 81 df<7FFFC0FFFFC07FFFC01C01C0 1C01C01C01C01C01C01C00001C00001C1C001C1C001FFC001FFC001FFC001C1C001C1C00 1C00001C00E01C00E01C00E01C00E01C00E07FFFE0FFFFE07FFFE013197F9816>69 D<7E1FC0FF3FE07F1FC01D07001D87001D87001D87001DC7001DC7001CC7001CC7001CE7 001CE7001CE7001C67001C67001C77001C77001C37001C37001C37001C17007F1F00FF9F 007F0F0013197F9816>78 D<1FFC003FFE007FFF00780F00F00780E00380E00380E00380 E00380E00380E00380E00380E00380E00380E00380E00380E00380E00380E00380F00780 F00780780F007FFF003FFE001FFC0011197E9816>I<7FF800FFFE007FFF001C0F801C03 801C03C01C01C01C01C01C01C01C03C01C03801C0F801FFF001FFE001FF8001C00001C00 001C00001C00001C00001C00001C00007F0000FF80007F000012197F9816>I E /Fc 21 123 df<000FE0200070186001C00460030003E0060001E00E0000E01C000060 38000060380000207800002070000020F0000000F0000000F0000000F0000000F0000000 F0000000F0000000F0000000700000207800002038000020380000201C0000400E000040 060000800300010001C0060000701800000FE0001B1E7D9C21>67 D75 D80 D<7FFFFFC0700F01C0600F00 C0400F0040400F0040C00F0020800F0020800F0020800F0020000F0000000F0000000F00 00000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F00 00000F0000000F0000000F0000000F0000000F0000001F800003FFFC001B1C7D9B21>84 D87 D<7FFFFC7C00787000786000F06001E04001E04003C0400780400780000F00001E00 001E00003C0000780000780000F00001E00001E00403C0040780040780040F000C1E0008 1E00083C00187800387800F8FFFFF8161C7D9B1C>90 D<00200000700000700000700000 B80000B80000B800011C00011C00011C00020E00020E0004070004070007FF0008038008 03800803801801C03803C0FE0FF815157F9419>97 D101 D<00FC200782600E01E01C00E03800 60780020700020F00020F00000F00000F00000F00FF8F000E0F000E07000E07800E03800 E01C00E00E00E007836000FC2015157E941B>103 DII107 DI110 D<01F800070E000C03001C03803801C07801E07000E0F000F0F000F0F000F0F000F0F000 F0F000F0F000F07000E07801E03801C01C03801E0780070E0001F80014157E941A>I114 D117 D119 DIII E /Fd 2 26 df<0000300000F00001C0000700001E0000780001E0000380000E00003C00 00F00000F000003800000E000007800001E000007800001C000007000003C00000F00000 300000000000000000000000000000000000007FFFE0FFFFF0141E7D951B>20 D<0F00043FC0047FE004F0F00CC03C3C801FF8800FF08003C00000000F00043FC0047FE0 04F0F00CC03C3C801FF8800FF08003C016117E901B>25 D E /Fe 22 122 df<7FF0FFE00C027F890E>45 D<000020000000300000007000000070000000F0 000000F0000001F00000037800000278000006780000047800000C780000087C0000183C 0000103C0000203C0000203C0000403C0000403E0000FFFE0000801E0001001E0001001E 0002001E0002000F0004000F0004000F001E001F00FF80FFF01C1D7F9C1F>65 D<0007F010001C0C300070026000C001E0038000E0070000E00E0000600E0000601C0000 403C00004038000040780000007800000078000000F0000000F0000000F0000000F000FF F0F0000F80F0000780F0000F0070000F0070000F0038000F0038000F001C001F000C001E 000600660003818200007E00001C1E7C9C21>71 D<0FFFFC0000F80F0000F0038000F003 C000F001C000F001C000F001C001E003C001E003C001E003C001E0038001E0070001E00E 0003C03C0003FFE00003C0000003C0000003C0000003C000000780000007800000078000 000780000007800000078000000F0000000F800000FFF000001A1C7E9B1C>80 D<003F0400C0CC0180380300380600180E00180E00180E00181E00101E00001F00000F80 000FF80007FF0003FF8001FFC0003FE00003E00001E00000E00000E04000E04000E04000 E04000C06001C0E00180F00300CC0E0083F800161E7E9C17>83 D<1FFFFFF03C07C0F030 07803020078020600780204007802040078020400F0020800F0020000F0000000F000000 0F0000000F0000001E0000001E0000001E0000001E0000001E0000001E0000003C000000 3C0000003C0000003C0000003C0000003C000000780000007C00001FFFE0001C1C7C9B1E >I<07F0001C18001E0C001C0E00180E00000E00000E0001FE000F0E001C1C00301C0070 1C00E01C40E01C40E03C40E05C80709D803F0E0012127D9115>97 D<01F8071C0C1E181C38183000700070007000E000E000E000600060047008301018200F C00F127D9112>99 D<01F8070C0C061C073803300370037FFF7000E000E000E000600060 02300430081C3007C010127E9112>101 D<000F800039C00061C000E3C001C18001C000 01C00001C0000380000380000380003FF800038000038000070000070000070000070000 0700000700000E00000E00000E00000E00000E00000E00001C00001E0000FFC000121D7F 9C0D>I<000038003CCC00C69C0183080383800703800703800703800703800707000306 00038C0004F0000400000C00000C00000FFE0007FF800FFFC01801C02000C06000E0C000 C0C000C0600180200300180E0007F000161C809215>I<07E00001E00001C00001C00001 C00001C00001C00001C000038000038000038000038F8003B0C003C0E00780E00780E007 00E00700E00700E00700E00E01C00E01C00E01C00E01C00E01C00E01C01C03801E03C0FF 9FF0141D7F9C17>I<00C001C001C0018000000000000000000000000000001F80078003 800700070007000700070007000E000E000E000E000E000E001C001E00FF800A1D7F9C0C >I<07E001E001C001C001C001C001C001C0038003800380038003800380070007000700 0700070007000E000E000E000E000E000E001C001E00FF800B1D7F9C0C>108 D<1F8FC0FC00079061060003E07607000780780700078078070007007007000700700700 070070070007007007000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E000E 00E00E001C01C01C001E01E01E00FF8FF8FF8021127F9124>I<1F8F8007B0C003C0E007 80E00780E00700E00700E00700E00700E00E01C00E01C00E01C00E01C00E01C00E01C01C 03801E03C0FF9FF014127F9117>I<00FC000307000E01801C01C03800C03000C07000E0 7000E07000E0E001C0E001C0E001C0600180600380700700380E001C180007E00013127E 9115>I<1F9C07EE03CF078E078C07000700070007000E000E000E000E000E000E001C00 1E00FFC010127F9110>114 D<03F20C0E18061004300438043E001FE00FF007F8003C40 1C400C400C6018E010D0608FC00F127F9110>I<020002000200060006000C001C003C00 FFE01C001C00380038003800380038003800700070407040704070407080708031001E00 0B1A7C9910>I<1FE3FC07C1E003818001C10001C20000E40000EC000078000070000038 00007800009C00011E00020E000407000C07003C0780FE1FF016127F9116>120 D<0FF0FE03C03801C03001C02001C06001C04001E08000E08000E10000E10000E2000072 00007400007C00007800007000003000002000002000004000004000708000F10000F100 00E60000780000171A809116>I E /Ff 2 13 df<07C0000C3040101040201880601880 C00C80C00D00C00E00800E00800C00C01C00C02C0060C4803F0300120E7E8D17>11 D<000F0000308000C0C00080400100600200C00400C0040080040180083F00083E000801 00080180100180100180100180100180300300300300300600280C0044180043E0004000 00400000800000800000800000800000131D7F9614>I E /Fg 13 118 df<60F0F0600404798312>46 D<03E007F01E18381C30FC71FE739EE30EE70EE70E E70EE70EE30C739C71F830F038001E0E07FE03F80F147F9312>64 D<3F807FC070E0207000700FF03FF07870E070E070E07070F03FFE1F3E0F0E7E8D12>97 DI<07F01FF8383870106000E000E000E000E000600070383838 1FF007E00D0E7E8D12>I<07801FE0387070706038E038FFF8FFF8E0006000703838381F F007C00D0E7E8D12>101 D107 DI< 0F803FE038E07070E038E038E038E038E038F078707038E03FE00F800D0E7E8D12>111 D 114 D<1FF03FF06070C070E0007F003FE00FF000786018E018F030FFE0DFC00D0E7E8D12 >I<06000E000E000E007FF8FFF80E000E000E000E000E000E000E000E380E380E3807F0 03C00D127F9112>II E /Fh 73 123 df<00FCF807839C0E079C1C07081C07001C07001C07 001C07001C0700FFFFE01C07001C07001C07001C07001C07001C07001C07001C07001C07 001C07001C07001C0700FF1FE01617809615>11 D<00FC000782000E07001C07001C0200 1C00001C00001C00001C0000FFFF001C07001C07001C07001C07001C07001C07001C0700 1C07001C07001C07001C07001C0700FF1FE01317809614>I<60C0F1E0F1E070E0102010 2020402040408040800B0A7F9612>34 D<01C0000320000610000E10000E10000E10000E 20000E40000E80000780FE0700380700200B802013804031C04061E08060E100E07100E0 3A00E01C02700E0238370C0FC1F817177F961B>38 D<0102040C1818303070606060E0E0 E0E0E0E0E0E0E0E060606070303018180C04020108227D980E>40 D<8040203018180C0C0E060606070707070707070707070606060E0C0C18183020408008 227E980E>I<020002000200C218F2783AE00F800F803AE0F278C2180200020002000D0E 7E9812>I<00300000300000300000300000300000300000300000300000300000300000 3000FFFFFCFFFFFC00300000300000300000300000300000300000300000300000300000 300000300016187E931B>I<60F0F070101020204040040A7D830A>II<60F0F06004047D830A>I<0008001800300030003000600060006000C000C000C001 8001800180030003000600060006000C000C000C00180018001800300030003000600060 006000C000C0000D217E9812>I<07C018303018701C600C600CE00EE00EE00EE00EE00E E00EE00EE00EE00E600C600C701C30181C7007C00F157F9412>I<03000700FF00070007 000700070007000700070007000700070007000700070007000700070007007FF00C157E 9412>I<0F8030E040708030C038E0384038003800700070006000C00180030006000C08 080810183FF07FF0FFF00D157E9412>I<0FE030306018701C701C001C00180038006007 E000300018000C000E000EE00EE00EC00C401830300FE00F157F9412>I<003000300070 00F001F001700270047008701870107020704070C070FFFE0070007000700070007003FE 0F157F9412>I<20303FE03FC0240020002000200020002F8030E0207000300038003840 38E038E0388030406020C01F000D157E9412>I<01F00608080C181C301C70006000E000 E3E0EC30F018F00CE00EE00EE00E600E600E300C3018183007C00F157F9412>I<40007F FE7FFC7FF8C008801080200040008000800100010003000200060006000E000E000E000E 000E0004000F167E9512>I<07E018302018600C600C700C78183E101F600FC00FF018F8 607C601EC00EC006C006C004600C38300FE00F157F9412>I<07C0183030186018E00CE0 0CE00EE00EE00E601E301E186E0F8E000E000C001C70187018603020C01F800F157F9412 >I<60F0F06000000000000060F0F060040E7D8D0A>I61 D<001000003800003800003800 005C00005C00005C00008E00008E00008E0001070001070003078002038002038007FFC0 0401C00401C00800E00800E01800E03800F0FE03FE17177F961A>65 DI<00FC100383300E00B01C0070380030300030700010600010E00010E00000E0 0000E00000E00000E00000E000106000107000103000203800201C00400E008003830000 FC0014177E9619>IIII<007E080381980600580C0038180018 300018700008700008E00008E00000E00000E00000E00000E003FEE00038700038700038 3000381800380C00380600380380D8007F0817177E961C>III<0FFC00E000E000E000E000E000E000E000E000E000E000E000E0 00E000E000E000E000E0E0E0E0E0C1C061801F000E177E9612>IIIII<00FC00030300 0E01C01C00E0380070300030700038600018E0001CE0001CE0001CE0001CE0001CE0001C E0001C7000387000383000303800701C00E00E01C003030000FC0016177E961B>II82 D<0FC4302C601C400CC004C004C004E00070007F003FE00FF801FC001C00 0E0006800680068006C004E008D81087E00F177E9614>I<7FFFF8603818403808403808 803804803804803804003800003800003800003800003800003800003800003800003800 00380000380000380000380000380000380007FFC016177F9619>III< FF07FC3F803C01E00E001C00E004001C00E004001C017004000E017008000E017008000E 023808000702381000070238100007041C100003841C200003841C200003880E200001C8 0E400001C80E400001D80F400000F007800000F007800000F00780000060030000006003 0000006003000021177F9624>I89 D<204020404080408081008100E1C0F1E0F1E060C00B0A7B9612>92 D<1FC0386038301038003803F81E3830387038E039E039E07970FF1F1E100E7F8D12>97 DI<07F01838303870106000E000E000E000E000600070083008183007C00D0E7F 8D10>I<007E00000E00000E00000E00000E00000E00000E00000E00000E0007CE001C3E 00300E00700E00600E00E00E00E00E00E00E00E00E00600E00700E00301E00182E0007CF C012177F9614>I<0FC0186030307038E018FFF8E000E000E000600070083010183007C0 0D0E7F8D10>I<03E006700E701C201C001C001C001C001C00FF801C001C001C001C001C 001C001C001C001C001C001C001C00FF800C1780960B>I<0F9E18E33060707070707070 306018C02F80200060003FE03FF83FFC600EC006C006C006600C38380FE010157F8D12> II<183C3C1800000000007C1C1C1C1C1C1C1C1C1C1C1C1CFF081780960A>I107 DIII<07C018303018600C600CE0 0EE00EE00EE00EE00E701C3018183007C00F0E7F8D12>II<07C2001C2600381E00700E00600E00E00E 00E00E00E00E00E00E00600E00700E00301E001C2E0007CE00000E00000E00000E00000E 00000E00007FC012147F8D13>II<1F4060C0C040C040E000FF007F801FC001E080608060C0 60E0C09F000B0E7F8D0E>I<080008000800180018003800FF8038003800380038003800 3800380038403840384038401C800F000A147F930E>II< FE1F3C0E3C0C1C081C080E100E100720072003C003C003C001800180100E7F8D13>IIIII E /Fi 1 50 df<0C003C00CC000C00 0C000C000C000C000C000C000C000C000C000C000C00FF8009107E8F0F>49 D E /Fj 1 4 df<01800180018001804182F18F399C0FF003C003C00FF0399CF18F4182 018001800180018010127E9215>3 D E /Fk 12 113 df<00F000030C000E06041C0704 380708300708700790700790E003A0E003A0E003C0E00380E00380E00380600780601B88 3061900F80E016127E911B>11 D<0001F000061800080C00100C00200E00400E00800E00 801C01001C010018010038020FF00210C0020FE002003004003004003004003804003808 00700800700800700800E01800E01800C0140180140300230E0020F80020000020000040 000040000040000040000080000080000017257F9C17>I<01FFFF80003C01E000380070 003800380038001C0038001C0070001C0070001E0070001E0070001E00E0001E00E0001E 00E0001E00E0001E01C0003C01C0003C01C0003C01C000380380007803800070038000F0 038000E0070001C0070003800700070007001C000E007800FFFFC0001F1C7E9B22>68 D<01FFFFF8003C0078003800180038001000380010003800100070001000700010007010 100070100000E0200000E0200000E0600000FFE00001C0400001C0400001C0400001C040 0003808040038000400380008003800080070001000700010007000300070006000E003E 00FFFFFC001D1C7E9B1F>I<01FC00FF80001C001C00002E001800002E001000002E0010 00002700100000470020000043002000004380200000438020000081C040000081C04000 0081C040000080E040000100E08000010070800001007080000100708000020039000002 00390000020039000002001D000004001E000004000E000004000E00000C000E00001C00 040000FF80040000211C7E9B21>78 D<0003F800000E0E000038038000E001C001C001C0 038000E0070000E00F0000F01E0000F01C0000F03C0000F03C0000F0780000F0780000F0 780000F0F00001E0F00001E0F00001E0F00003C0F00003C0F0000780F0000780F0000F00 70000E0070001C00380038003C0070001C01C0000707800001FC00001C1E7E9C20>I<01 FFFE00003C03C0003800E0003800F00038007000380070007000F0007000F0007000F000 7001E000E001C000E0078000E01E0000FFF00001C0300001C0180001C01C0001C01C0003 801C0003801C0003801C0003801C0007003C0007003C0807003C0807003C100F001E10FF E00E20000007C01D1D7E9B20>82 D<000FC100303300400F008006018006030006030006 06000406000407000007000007800003F00001FF0000FFC0003FE00003E00000F0000070 0000300000302000302000306000606000606000C0600080F00300CC060083F800181E7E 9C19>I<3F00070007000E000E000E000E001C001C001C001C0039E03A303C1838187018 701C701C701CE038E038E038E030E070E060E0C061C023001E000E1D7E9C12>98 D<0007E00000E00000E00001C00001C00001C00001C000038000038000038000038001E7 000717000C0F00180F00380E00300E00700E00700E00E01C00E01C00E01C00E01C00E038 80E03880E038806078803199001E0E00131D7E9C16>100 D<0FC00001C00001C0000380 000380000380000380000700000700000700000700000E07000E18800E21C00E23C01C47 801C83001D00001E00003F800039C00038E00038E00070E10070E10070E10070E200E062 00603C00121D7E9C16>107 D<07078009C86008D03008E03011C03011C03801C03801C0 380380700380700380700380600700E00700C00701800783000E86000E78000E00000E00 001C00001C00001C00001C00003C0000FF8000151A819115>112 D E /Fl 53 122 df<0020004001800380030006000E001C001C003C0038003800780078 007800F800F000F000F000F000F000F000F000F000F000F800780078007800380038003C 001C001C000E000600030003800180004000200B297C9E13>40 D<800040003000380018 000C000E000700070007800380038003C003C003C003E001E001E001E001E001E001E001 E001E001E003E003C003C003C0038003800780070007000E000C00180038003000400080 000B297D9E13>I45 D<78FCFCFCFC7806067D850D>I< 00600001E0000FE000FFE000F3E00003E00003E00003E00003E00003E00003E00003E000 03E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E000 03E0007FFF807FFF80111B7D9A18>49 D<07F8001FFE00383F80780FC0FC07C0FC07E0FC 03E0FC03E07803E00007E00007C00007C0000F80001F00001E0000380000700000E00001 80600300600600600800E01FFFC03FFFC07FFFC0FFFFC0FFFFC0131B7E9A18>I<03F800 1FFE003C1F003C0F807C07C07E07C07C07C03807C0000F80000F80001E00003C0003F800 001E00000F800007C00007C00007E03007E07807E0FC07E0FC07E0FC07C0780F80781F00 1FFE0007F800131B7E9A18>I<000180000380000780000F80001F80003F80006F8000CF 80008F80018F80030F80060F800C0F80180F80300F80600F80C00F80FFFFF8FFFFF8000F 80000F80000F80000F80000F80000F8001FFF801FFF8151B7F9A18>I<1801801FFF001F FE001FFC001FF8001FC00018000018000018000018000019F8001E0E00180F8010078000 07C00007E00007E00007E07807E0F807E0F807E0F807C0F007C0600F80381F001FFE0007 F000131B7E9A18>I<6000007FFFE07FFFE07FFFC07FFF807FFF80E00300C00600C00C00 C0180000300000300000600000E00000E00001E00001C00003C00003C00003C00003C000 07C00007C00007C00007C00007C00007C000038000131C7D9B18>55 D<03F8000FFE001E0F803807803803C07803C07803C07E03C07F83807FC7003FFE001FFC 000FFE0007FF801DFF80387FC0781FE0F007E0F003E0F001E0F001E0F001E07801C07803 803E07801FFE0003F800131B7E9A18>I<03F8000FFE001E0F003C07807807807803C0F8 03C0F803C0F803E0F803E0F803E0F803E07807E03807E03C0BE00E1BE003E3E00003E000 03C00003C03807C07C07807C0700780F00383C001FF8000FE000131B7E9A18>I<000380 00000380000007C0000007C0000007C000000FE000000FE000001FF000001BF000001BF0 000031F8000031F8000061FC000060FC0000E0FE0000C07E0000C07E0001803F0001FFFF 0003FFFF8003001F8003001F8006000FC006000FC00E000FE00C0007E0FFC07FFEFFC07F FE1F1C7E9B24>65 DI<001FE02000FFF8E003F80FE007C003E0 0F8001E01F0000E03E0000E03E0000607E0000607C000060FC000000FC000000FC000000 FC000000FC000000FC000000FC000000FC0000007C0000607E0000603E0000603E0000C0 1F0000C00F80018007C0030003F80E0000FFFC00001FE0001B1C7D9B22>IIII<000FF008007FFE38 01FC07F807E001F80F8000781F0000783F0000383E0000387E0000187C000018FC000000 FC000000FC000000FC000000FC000000FC000000FC007FFFFC007FFF7C0001F87E0001F8 3E0001F83F0001F81F0001F80F8001F807E001F801FC07F8007FFE78000FF818201C7D9B 26>III<07FFF007FFF0001F80001F80001F80001F80001F80001F80001F80001F8000 1F80001F80001F80001F80001F80001F80001F80001F80001F80001F80301F80781F80FC 1F80FC1F80FC1F00783E00387C000FF000141C7F9B19>IIIII<003FE000 01F07C0003C01E000F800F801F0007C01E0003C03E0003E07E0003F07C0001F07C0001F0 FC0001F8FC0001F8FC0001F8FC0001F8FC0001F8FC0001F8FC0001F8FC0001F87C0001F0 7E0003F07E0003F03E0003E03F0007E01F0007C00F800F8003C01E0001F07C00003FE000 1D1C7D9B24>II82 D<07F8201FFEE03C07E07801E07000 E0F000E0F00060F00060F80000FE0000FFE0007FFE003FFF003FFF800FFFC007FFE0007F E00003F00001F00000F0C000F0C000F0C000E0E000E0F001C0FC03C0EFFF0083FC00141C 7D9B1B>I<7FFFFFE07FFFFFE0781F81E0701F80E0601F8060E01F8070C01F8030C01F80 30C01F8030C01F8030001F8000001F8000001F8000001F8000001F8000001F8000001F80 00001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F80 0007FFFE0007FFFE001C1C7E9B21>II87 D<0FF8001C1E003E0F803E07803E 07C01C07C00007C0007FC007E7C01F07C03C07C07C07C0F807C0F807C0F807C0780BC03E 13F80FE1F815127F9117>97 DI<03 FC000E0E001C1F003C1F00781F00780E00F80000F80000F80000F80000F80000F8000078 00007801803C01801C03000E0E0003F80011127E9115>I<000FF0000FF00001F00001F0 0001F00001F00001F00001F00001F00001F00001F001F9F00F07F01C03F03C01F07801F0 7801F0F801F0F801F0F801F0F801F0F801F0F801F07801F07801F03C01F01C03F00F0FFE 03F9FE171D7E9C1B>I<01FC000F07001C03803C01C07801C07801E0F801E0F801E0FFFF E0F80000F80000F800007800007C00603C00601E00C00F038001FC0013127F9116>I<00 7F0001E38003C7C00787C00F87C00F83800F80000F80000F80000F80000F8000FFF800FF F8000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F 80000F80000F80007FF8007FF800121D809C0F>I<03F8F00E0F381E0F381C07303C0780 3C07803C07803C07801C07001E0F000E0E001BF8001000001800001800001FFF001FFFC0 0FFFE01FFFF07801F8F00078F00078F000787000707800F01E03C007FF00151B7F9118> II<1E003F003F003F003F001E0000 0000000000000000000000FF00FF001F001F001F001F001F001F001F001F001F001F001F 001F001F001F00FFE0FFE00B1E7F9D0E>I108 DII<01FC000F07801C01C0 3C01E07800F07800F0F800F8F800F8F800F8F800F8F800F8F800F87800F07800F03C01E0 1E03C00F078001FC0015127F9118>II114 D<1FD830786018E018E018F000FF807FE0 7FF01FF807FC007CC01CC01CE01CE018F830CFC00E127E9113>I<030003000300030007 0007000F000F003FFCFFFC1F001F001F001F001F001F001F001F001F001F0C1F0C1F0C1F 0C0F08079803F00E1A7F9913>III121 D E /Fm 2 51 df<0C001C00EC000C000C000C000C000C000C000C000C00 0C000C000C000C000C000C000C00FFC00A137D9211>49 D<1F0060C06060F070F0306030 00700070006000C001C00180020004000810101020207FE0FFE00C137E9211>I E /Fn 68 123 df<0001FC000703000C03001C07001C0300180000380000380000380000 380000700007FFFC00701C00701C00701C00E03800E03800E03800E03800E07001C07001 C07001C07001C0E201C0E201C0E20380E4038064038038038000030000070000060000C6 0000E40000CC00007000001825819C17>12 D18 D<03070E1C3860C0800808729C15>I<183C3C3C0404080810204080060C779C0D>39 D<00030006000800180030006000C000C0018003000300060006000C000C001C00180018 00380030003000700070006000600060006000E000E000E000E000E00060006000600060 00600020003000100008000800102A7B9E11>I<001000100008000C0004000600060006 00060006000700070007000700070006000600060006000E000E000C000C001C00180018 0038003000300060006000C000C001800300030006000C00180010006000C000102A809E 11>I<0030000060000060000060001841803C47000ECE0007B80001E00003C0000EF000 39B800711E00C10C000300000300000300000600001112799E15>I<1838783808081010 20404080050C7D830D>44 DI<3078F06005047C830D>I<00 3C0000C6000183000303000603000603800E03800C03801C03801C030038070038070038 0700380700700E00700E00700E00700E00E01C00E01C00E01C00E03800E03800E03000C0 6000E0600060C0007180001E0000111D7B9B15>48 D<00020006000C001C007C039C0038 003800380038007000700070007000E000E000E000E001C001C001C001C0038003800380 03800780FFF00F1C7C9B15>I<003C0000C3000101800201800201C00441C00441C00841 C00841C00841C01083801083801107000E0600000C0000180000300000C0000100000600 000800001001001002002002004006007E0C00C7F80083F80080E000121D7C9B15>I<00 3E0000C1800101800200C00400C00440C00841C00841C00841C008838007038000070000 0E0001F800003800000C00000C00000E00000E00000E00000E00700E00E01C00801C0080 380080300040600021C0001F0000121D7C9B15>I<0001800001C0000380000380000380 000300000700000700000600000E00000C00001C00001800001800003000003000006000 00400000C600018E00010E00020E00061C000C1C00181C003F1C0040F800803F00003800 00380000700000700000700000700000E00000600012247E9B15>I<00C06000FFC001FF 8001FE00010000010000020000020000020000020000047800058C000606000406000806 00000700000700000600000E00000E00700E00700C00E01C008018008038004030004060 0021C0001F0000131D7C9B15>I<001E000061000081800180800300C00300C006018006 018006018007030007860003CC0003F00001F000037800063C00081E00180E00300E0060 0600600600600600C00C00C00C00C0180060100060200030C0000F0000121D7C9B15>56 D<003C0000C6000183000303000603000E03000C03801C03801C03001C03003807003807 00380700380F00380E00181E00181E000C6C00079C00001C000018000038000030000060 00E0C000E0C0008180008600007C0000111D7B9B15>I<060F0F06000000000000000000 003078F06008127C910D>I<000018000000180000003800000038000000780000007800 0000B8000001B800000138000002380000023C0000041C0000041C0000081C0000181C00 00101C0000201C0000201C00007FFC0000401C0000801C0001801C0001001C0002001C00 02001C0004000E000C000E001C001E00FF00FFC01A1D7E9C1F>65 D<01FFFE00003C0780003803C0003801C0003801C0003801C0007001C0007003C0007003 C00070078000E0070000E00E0000E03C0000FFF80001C01C0001C00E0001C00F0001C00F 0003800F0003800F0003800F0003800F0007001E0007001C0007003C00070078000E01E0 00FFFF80001A1C7D9B1D>I<0003F020001E0C60003002E000E003C001C001C0038001C0 070000C00E0000801E0000801C0000803C0000803C000000780000007800000078000000 F0000000F0000000F0000000F0000000F0000400F0000400F0000400F000080070000800 7000100038002000180040000C0180000706000001F800001B1E7A9C1E>I<01FFFE0000 3C0780003801C0003801C0003800E0003800E0007000F00070007000700070007000F000 E000F000E000F000E000F000E000F001C001E001C001E001C001E001C001C0038003C003 800380038007800380070007000E0007001C0007003800070070000E01C000FFFF00001C 1C7D9B1F>I<01FFFFE0003C00E000380060003800400038004000380040007000400070 0040007020400070200000E0400000E0400000E0C00000FFC00001C0800001C0800001C0 800001C0800003810100038001000380020003800200070004000700040007000C000700 18000E007800FFFFF0001B1C7D9B1C>I<01FFFFC0003C01C0003800C000380080003800 80003800800070008000700080007020800070200000E0400000E0400000E0C00000FFC0 0001C0800001C0800001C0800001C0800003810000038000000380000003800000070000 000700000007000000070000000F000000FFF000001A1C7D9B1B>I<0003F020001E0C60 003002E000E003C001C001C0038001C0070000C00E0000801E0000801C0000803C000080 3C000000780000007800000078000000F0000000F0000000F001FFC0F0001E00F0001C00 F0001C00F0001C00F0001C00700038007000380038003800180078000C00900007071000 01F800001B1E7A9C20>I<01FFCFFE003C01E0003801C0003801C0003801C0003801C000 70038000700380007003800070038000E0070000E0070000E0070000FFFF0001C00E0001 C00E0001C00E0001C00E0003801C0003801C0003801C0003801C00070038000700380007 003800070038000F007800FFE7FF001F1C7D9B1F>I<01FFC0003C000038000038000038 0000380000700000700000700000700000E00000E00000E00000E00001C00001C00001C0 0001C0000380000380000380000380000700000700000700000700000F0000FFE000121C 7E9B10>I<007FF0000780000700000700000700000700000E00000E00000E00000E0000 1C00001C00001C00001C0000380000380000380000380000700000700000700000700060 E000E0E000C0C00081C0008380004700003C0000141D7B9B16>I<01FFC0FF003C003C00 3800300038004000380080003801000070020000700400007010000070200000E0400000 E0C00000E1C00000E5C00001C8E00001D0E00001E0E00001C07000038070000380700003 803800038038000700380007001C0007001C0007001C000F001E00FFE0FF80201C7D9B20 >I<01FFE0003C0000380000380000380000380000700000700000700000700000E00000 E00000E00000E00001C00001C00001C00001C00003800803800803800803801007001007 00300700600700E00E03C0FFFFC0151C7D9B1A>I<01FE0007F8003E000780002E000F00 002E001700002E001700002E002700004E002E00004E004E00004E004E00004E008E0000 8E011C00008E011C00008E021C00008E021C000107043800010704380001070838000107 1038000207107000020720700002072070000207407000040740E000040780E000040700 E0000C0700E0001C0601E000FF861FFC00251C7D9B25>I<01FC03FE001C0070003C0060 002E0040002E0040002E0040004700800047008000470080004380800083810000838100 008181000081C1000101C2000101C2000100E2000100E2000200E4000200740002007400 020074000400380004003800040038000C0018001C001000FF8010001F1C7D9B1F>I<01 FFFC00003C070000380380003801C0003801C0003801C0007003C0007003C0007003C000 70038000E0078000E0070000E00E0000E0380001FFE00001C0000001C0000001C0000003 800000038000000380000003800000070000000700000007000000070000000F000000FF E000001A1C7D9B1C>80 D<01FFF800003C0E000038070000380380003803800038038000 700780007007800070078000700F0000E00E0000E01C0000E0700000FFC00001C0C00001 C0600001C0700001C07000038070000380700003807000038070000700F0000700F04007 00F0400700F0800F007880FFE0790000001E001A1D7D9B1E>82 D<000F8400304C00403C 00801801001803001803001806001006001006000007000007000003E00003FC0001FF00 007F800007C00001C00001C00000C00000C02000C02000C0600180600180600300600200 F00400CC180083E000161E7D9C17>I<1FFFFFC01C0701C0300E00C0200E0080600E0080 400E0080401C0080801C0080801C0080001C000000380000003800000038000000380000 0070000000700000007000000070000000E0000000E0000000E0000000E0000001C00000 01C0000001C0000001C0000003C000007FFE00001A1C799B1E>I<7FF0FF800F001C000E 0018000E0010000E0010000E0010001C0020001C0020001C0020001C0020003800400038 004000380040003800400070008000700080007000800070008000E0010000E0010000E0 010000E0020000E0020000E0040000E00400006008000030300000104000000F80000019 1D779B1F>III89 D<00FFFF8000F0070001C00E0001801E0001001C0001003800020070000200E0 000201C0000001C0000003800000070000000E0000001C0000001C000000380000007000 0000E0080001C0100001C0100003801000070020000E0020001C0060003C00C0003801C0 0070078000FFFF8000191C7D9B19>I<020006001B0031006080C0800906759C15>94 D<03CC063C0C3C181C3838303870387038E070E070E070E070E0E2C0E2C0E261E462643C 380F127B9115>97 D<3F00070007000E000E000E000E001C001C001C001C0039C03E6038 3038307038703870387038E070E070E070E060E0E0C0C0C1C0618063003C000D1D7B9C13 >I<01F007080C08181C3838300070007000E000E000E000E000E000E008E010602030C0 1F000E127B9113>I<001F80000380000380000700000700000700000700000E00000E00 000E00000E0003DC00063C000C3C00181C00383800303800703800703800E07000E07000 E07000E07000E0E200C0E200C0E20061E4006264003C3800111D7B9C15>I<01E007100C 1018083810701070607F80E000E000E000E000E000E0086010602030C01F000D127B9113 >I<0003C0000670000C70001C60001C00001C0000380000380000380000380000380003 FF8000700000700000700000700000700000E00000E00000E00000E00000E00001C00001 C00001C00001C00001C000038000038000038000030000030000070000C60000E60000CC 00007800001425819C0D>I<00F3018F030F06070E0E0C0E1C0E1C0E381C381C381C381C 383830383038187818F00F700070007000E000E0C0C0E1C0C3007E00101A7D9113>I<0F C00001C00001C0000380000380000380000380000700000700000700000700000E78000E 8C000F0E000E0E001C0E001C0E001C0E001C0E00381C00381C00381C0038380070388070 3880707080707100E03200601C00111D7D9C15>I<018003800100000000000000000000 00000000001C002600470047008E008E000E001C001C001C003800380071007100710072 0072003C00091C7C9B0D>I<0FC00001C00001C000038000038000038000038000070000 0700000700000700000E0F000E11000E23800E43801C83001C80001D00001E00003F8000 39C00038E00038E00070E20070E20070E20070E400E06400603800111D7D9C13>107 D<1F800380038007000700070007000E000E000E000E001C001C001C001C003800380038 0038007000700070007000E400E400E400E40068003800091D7C9C0B>I<3C1E07802663 18C04683A0E04703C0E08E0380E08E0380E00E0380E00E0380E01C0701C01C0701C01C07 01C01C070380380E0388380E0388380E0708380E0710701C0320300C01C01D127C9122> I<3C3C002646004687004707008E07008E07000E07000E07001C0E001C0E001C0E001C1C 00381C40381C40383840383880701900300E0012127C9117>I<01E007180C0C180C380C 300E700E700EE01CE01CE01CE018E038E030E06060C031801E000F127B9115>I<078700 04D98008E0C008E0C011C0E011C0E001C0E001C0E00381C00381C00381C0038180070380 0703000707000706000E8C000E70000E00000E00001C00001C00001C00001C00003C0000 FF8000131A7F9115>I<03C4062C0C3C181C3838303870387038E070E070E070E070E0E0 C0E0C0E061E063C03DC001C001C0038003800380038007803FF00E1A7B9113>I<3C3C26 C2468747078E068E000E000E001C001C001C001C0038003800380038007000300010127C 9112>I<01F006080C080C1C18181C001F001FC00FF007F0007800386030E030C0308060 60C01F000E127D9111>I<00C001C001C001C00380038003800380FFE00700070007000E 000E000E000E001C001C001C001C00384038403840388019000E000B1A7D990E>I<1E03 00270700470700470700870E00870E000E0E000E0E001C1C001C1C001C1C001C1C003838 803838801838801839001C5900078E0011127C9116>I<1E06270E470E4706870287020E 020E021C041C041C041C0818083808181018200C4007800F127C9113>I<1E0183270387 4703874703838707018707010E07010E07011C0E021C0E021C0E021C0E04180C04181C04 181C081C1C100C263007C3C018127C911C>I<070E0019910010E38020E38041C30041C0 0001C00001C000038000038000038000038000070200670200E70400CB04008B080070F0 0011127D9113>I<1E03270747074707870E870E0E0E0E0E1C1C1C1C1C1C1C1C38383838 183818381C7007F00070007000E0E0C0E1C0818047003C00101A7C9114>I<038207C20F EC08381008001000200040008001000200040008081008383067F043E081C00F127D9111 >I E /Fo 18 90 df45 D<0000700000000070000000 00F800000000F800000000F800000001FC00000001FC00000003FE00000003FE00000003 FE00000006FF000000067F0000000E7F8000000C3F8000000C3F800000183FC00000181F C00000381FE00000300FE00000300FE00000600FF000006007F00000E007F80000FFFFF8 0000FFFFF800018001FC00018001FC00038001FE00030000FE00030000FE000600007F00 0600007F00FFE00FFFF8FFE00FFFF825227EA12A>65 D<0003FE0080001FFF818000FF01 E38001F8003F8003E0001F8007C0000F800F800007801F800007803F000003803F000003 807F000001807E000001807E00000180FE00000000FE00000000FE00000000FE00000000 FE00000000FE00000000FE00000000FE000000007E000000007E000001807F000001803F 000001803F000003801F800003000F8000030007C000060003F0000C0001F800380000FF 00F000001FFFC0000003FE000021227DA128>67 D69 DI<0003FE0040001FFFC0C0007F00F1C001 F8003FC003F0000FC007C00007C00FC00003C01F800003C03F000001C03F000001C07F00 0000C07E000000C07E000000C0FE00000000FE00000000FE00000000FE00000000FE0000 0000FE00000000FE00000000FE000FFFFC7E000FFFFC7F00001FC07F00001FC03F00001F C03F00001FC01F80001FC00FC0001FC007E0001FC003F0001FC001FC003FC0007F80E7C0 001FFFC3C00003FF00C026227DA12C>III76 DII<0007FC0000003FFF800000FC07E00003F001F80007E000FC000FC0007E 001F80003F001F80003F003F00001F803F00001F807F00001FC07E00000FC07E00000FC0 FE00000FE0FE00000FE0FE00000FE0FE00000FE0FE00000FE0FE00000FE0FE00000FE0FE 00000FE0FE00000FE07E00000FC07F00001FC07F00001FC03F00001F803F80003F801F80 003F000FC0007E0007E000FC0003F001F80000FC07E000003FFF80000007FC000023227D A12A>II82 D<01FC0407FF8C1F03FC3C007C7C003C78001C78001CF8000CF8000CFC000CFC0000FF00 00FFE0007FFF007FFFC03FFFF01FFFF80FFFFC03FFFE003FFE0003FF00007F00003F0000 3FC0001FC0001FC0001FE0001EE0001EF0003CFC003CFF00F8C7FFE080FF8018227DA11F >I<7FFFFFFF807FFFFFFF807E03F80F807803F807807003F803806003F80180E003F801 C0E003F801C0C003F800C0C003F800C0C003F800C0C003F800C00003F800000003F80000 0003F800000003F800000003F800000003F800000003F800000003F800000003F8000000 03F800000003F800000003F800000003F800000003F800000003F800000003F800000003 F800000003F800000003F800000003F8000003FFFFF80003FFFFF80022227EA127>I<7F FFC1FFF07FFFC1FFF003FC000C0001FE00180000FE00380000FF007000007F806000003F 80C000003FC1C000001FE38000000FE30000000FF700000007FE00000003FC00000003FC 00000001FE00000000FE00000000FF00000000FF80000001FFC0000001BFC00000031FE0 0000070FF000000E0FF000000C07F800001803FC00003803FC00003001FE00006000FF00 00E000FF0001C0007F800180003FC0FFFC03FFFEFFFC03FFFE27227FA12A>88 DI E /Fp 83 128 df<007E1F0001C1B1800303E3C00703C3C00E03C1800E01C0000E01C000 0E01C0000E01C0000E01C0000E01C000FFFFFC000E01C0000E01C0000E01C0000E01C000 0E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C000 0E01C0000E01C0000E01C0007F87FC001A1D809C18>11 D<007E0001C1800301800703C0 0E03C00E01800E00000E00000E00000E00000E0000FFFFC00E01C00E01C00E01C00E01C0 0E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C0 7F87F8151D809C17>I<007FC001C1C00303C00703C00E01C00E01C00E01C00E01C00E01 C00E01C00E01C0FFFFC00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01 C00E01C00E01C00E01C00E01C00E01C00E01C00E01C07FCFF8151D809C17>I<003F07E0 0001C09C18000380F018000701F03C000E01E03C000E00E018000E00E000000E00E00000 0E00E000000E00E000000E00E00000FFFFFFFC000E00E01C000E00E01C000E00E01C000E 00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00 E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C007FC7FCFF80211D80 9C23>I18 D<1C1C3C3870C0800607779C15>I<6060F0F0 F8F86868080808080808101010102020404080800D0C7F9C15>34 D<60F0F8680808081010204080050C7C9C0C>39 D<004000800100020006000C000C0018 001800300030007000600060006000E000E000E000E000E000E000E000E000E000E000E0 00E000600060006000700030003000180018000C000C00060002000100008000400A2A7D 9E10>I<800040002000100018000C000C000600060003000300038001800180018001C0 01C001C001C001C001C001C001C001C001C001C001C00180018001800380030003000600 06000C000C00180010002000400080000A2A7E9E10>I<01800180018001804182F18F39 9C0FF003C003C00FF0399CF18F4182018001800180018010127E9E15>I<60F0F0701010 101020204080040C7C830C>44 DI<60F0F06004047C830C>I<00 010003000600060006000C000C000C0018001800180030003000300060006000C000C000 C0018001800180030003000300060006000C000C000C0018001800180030003000300060 0060006000C000C00010297E9E15>I<03C00C301818300C300C700E60066006E007E007 E007E007E007E007E007E007E007E007E007E007E00760066006700E300C300C18180C30 07E0101D7E9B15>I<030007003F00C70007000700070007000700070007000700070007 000700070007000700070007000700070007000700070007000F80FFF80D1C7C9B15>I< 07C01830201C400C400EF00FF80FF807F8077007000F000E000E001C001C003800700060 00C00180030006010C01180110023FFE7FFEFFFE101C7E9B15>I<07E01830201C201C78 1E780E781E381E001C001C00180030006007E00030001C001C000E000F000F700FF80FF8 0FF80FF00E401C201C183007E0101D7E9B15>I<000C00000C00001C00003C00003C0000 5C0000DC00009C00011C00031C00021C00041C000C1C00081C00101C00301C00201C0040 1C00C01C00FFFFC0001C00001C00001C00001C00001C00001C00001C0001FFC0121C7F9B 15>I<300C3FF83FF03FC020002000200020002000200023E024302818301C200E000E00 0F000F000F600FF00FF00FF00F800E401E401C2038187007C0101D7E9B15>I<00F0030C 06040C0E181E301E300C700070006000E3E0E430E818F00CF00EE006E007E007E007E007 E007600760077006300E300C18180C3003E0101D7E9B15>I<4000007FFF807FFF007FFF 0040020080040080040080080000100000100000200000600000400000C00000C00001C0 000180000180000380000380000380000380000780000780000780000780000780000780 00030000111D7E9B15>I<03E00C301008200C20066006600660067006780C3E083FB01F E007F007F818FC307E601E600FC007C003C003C003C00360026004300C1C1007E0101D7E 9B15>I<03C00C301818300C700C600EE006E006E007E007E007E007E0076007700F300F 18170C2707C700060006000E300C780C78187010203030C00F80101D7E9B15>I<60F0F0 600000000000000000000060F0F06004127C910C>I<60F0F06000000000000000000000 60F0F0701010101020204080041A7C910C>I<7FFFFFC0FFFFFFE0000000000000000000 0000000000000000000000000000000000000000000000FFFFFFE07FFFFFC01B0C7E8F20 >61 D<0FE03038401CE00EF00EF00EF00E000C001C0030006000C0008001800100010001 000100010001000000000000000000000003000780078003000F1D7E9C14>63 D<000600000006000000060000000F0000000F0000000F00000017800000178000001780 000023C0000023C0000023C0000041E0000041E0000041E0000080F0000080F0000180F8 000100780001FFF80003007C0002003C0002003C0006003E0004001E0004001E000C001F 001E001F00FF80FFF01C1D7F9C1F>65 DI< 001F808000E0618001801980070007800E0003801C0003801C0001803800018078000080 7800008070000080F0000000F0000000F0000000F0000000F0000000F0000000F0000000 F0000000700000807800008078000080380000801C0001001C0001000E00020007000400 0180080000E03000001FC000191E7E9C1E>IIII<001F8080 00E0618001801980070007800E0003801C0003801C000180380001807800008078000080 70000080F0000000F0000000F0000000F0000000F0000000F0000000F000FFF0F0000F80 700007807800078078000780380007801C0007801C0007800E00078007000B8001801180 00E06080001F80001C1E7E9C21>III<1FFF00F8007800780078007800780078007800 78007800780078007800780078007800780078007800787078F878F878F878F0F040E021 C01F00101D7F9B15>IIIII<003F800000E0E0000380380007001C000E00 0E001C0007003C00078038000380780003C0780003C0700001C0F00001E0F00001E0F000 01E0F00001E0F00001E0F00001E0F00001E0F00001E0700001C0780003C0780003C03800 03803C0007801C0007000E000E0007001C000380380000E0E000003F80001B1E7E9C20> II<003F800000E0E0000380380007001C00 0E000E001C0007003C00078038000380780003C0780003C0700001C0F00001E0F00001E0 F00001E0F00001E0F00001E0F00001E0F00001E0F00001E0700001C0780003C0780003C0 380003803C0E07801C1107000E208E0007205C0003A0780000F0E020003FE02000006020 00003060000038E000003FC000003FC000001F8000000F001B257E9C20>II<07E0801C1980300580700380600180E00180E00080E00080E000 80F00000F800007C00007FC0003FF8001FFE0007FF0000FF80000F800007C00003C00001 C08001C08001C08001C0C00180C00180E00300D00200CC0C0083F800121E7E9C17>I<7F FFFFC0700F01C0600F00C0400F0040400F0040C00F0020800F0020800F0020800F002000 0F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F000000 0F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000001F800003 FFFC001B1C7F9B1E>IIII89 D<7FFFF07C01F07001E06003C0 6003C0400780400F80400F00401E00001E00003C00007C0000780000F00000F00001E000 03E00003C0100780100780100F00101F00301E00203C00203C00607800E0F803E0FFFFE0 141C7E9B19>I<08081010202040404040808080808080B0B0F8F8787830300D0C7A9C15> 92 D<1FC000307000783800781C00301C00001C00001C0001FC000F1C00381C00701C00 601C00E01C40E01C40E01C40603C40304E801F870012127E9115>97 DI<07E00C301878307870306000E0 00E000E000E000E000E00060007004300418080C3007C00E127E9112>I<003F00000700 00070000070000070000070000070000070000070000070000070003E7000C1700180F00 300700700700600700E00700E00700E00700E00700E00700E00700600700700700300700 180F000C370007C7E0131D7E9C17>I<03E00C301818300C700E6006E006FFFEE000E000 E000E00060007002300218040C1803E00F127F9112>I<00F8018C071E061E0E0C0E000E 000E000E000E000E00FFE00E000E000E000E000E000E000E000E000E000E000E000E000E 000E000E000E007FE00F1D809C0D>I<00038003C4C00C38C01C3880181800381C00381C 00381C00381C001818001C38000C300013C0001000003000001800001FF8001FFF001FFF 803003806001C0C000C0C000C0C000C06001803003001C0E0007F800121C7F9215>II<18003C003C00180000000000000000 00000000000000FC001C001C001C001C001C001C001C001C001C001C001C001C001C001C 001C001C00FF80091D7F9C0C>I<00C001E001E000C00000000000000000000000000000 0FE000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E0 00E000E000E060E0F0C0F1C061803E000B25839C0D>IIIII<03F0000E1C00180600300300700380600180E001 C0E001C0E001C0E001C0E001C0E001C06001807003803003001806000E1C0003F0001212 7F9115>II<03C1000C3300180B00300F00700700700700 E00700E00700E00700E00700E00700E00700600700700700300F00180F000C370007C700 000700000700000700000700000700000700000700003FE0131A7E9116>II<1F9030704030C010C010E010F8007F803FE00FF000F880388018C018C018E010D060 8FC00D127F9110>I<04000400040004000C000C001C003C00FFE01C001C001C001C001C 001C001C001C001C001C101C101C101C101C100C100E2003C00C1A7F9910>IIII<7F8FF00F03800F030007020003840001C80001 D80000F00000700000780000F800009C00010E00020E000607000403801E07C0FF0FF815 12809116>II<7FFC70386038407040F040E041C003C003 8007000F040E041C043C0C380870087038FFF80E127F9112>II<60 60F0F0F0F060600C047C9C15>127 D E end %%EndProlog %%BeginSetup %%Feature: *Resolution 300dpi TeXDict begin %%EndSetup %%Page: 1 1 1 0 bop 1929 50 a Fp(1)52 195 y Fo(A)19 b(T)-5 b(AX)n(ONOMY)20 b(OF)f(P)-5 b(ARALLEL)19 b(GAME-TREE)f(SEAR)n(CH)h(ALGORITHMS)766 274 y Fn(Mark)c(G.)g(Br)n(o)n(ckington)1165 259 y Fm(1)799 353 y Fp(Edmon)o(ton,)d(Alb)q(erta)0 496 y Fl(1)48 b(INTR)o(ODUCTION)0 617 y Fp(In)14 b(the)h(last)f(t)o(w)o(en)o(t)o(y)h(y)o(ears,)f(a)g(n)o (um)o(b)q(er)g(of)g(articles)g(and)h(theses)h(ha)o(v)o(e)e(b)q(een)h (written)g(that)f(con)o(tain)g(inno)o(v)n(ativ)o(e)f(parallel)0 666 y(game-tree)i(searc)o(h)i(algorithms.)k(The)c(authors)f(of)f(the)h (parallel)f(algorithms)e(ha)o(v)o(e)j(sho)o(wn)f(ho)o(w)h(their)g(w)o (ork)f(is)h(unique)0 716 y(and)11 b(in)o(teresting.)18 b(In)11 b(some)f(cases,)j(this)e(has)h(b)q(een)g(sho)o(wn)f(b)o(y)g (classifying)g(other)g(algorithms)e(b)o(y)i(listing)f(implemen)o (tation)0 766 y(details)h(\(Bal)g(and)g(v)n(an)f(Renesse,)j(1986;)d (Ciancarini,)g(1994\).)17 b(T)m(o)10 b(the)i(author's)f(kno)o(wledge,)g (no)f(attempt)h(has)g(b)q(een)h(made)0 816 y(to)j(classify)g(the)h (algorithms)d(based)j(solely)e(on)h(their)h(algorithmic)d(prop)q (erties.)23 b(A)15 b(taxonom)o(y)e(w)o(ould)i(mak)o(e)f(it)g(easy)i(to) 0 866 y(ascertain)i(what)e(has)h(and)g(has)g(not)g(b)q(een)g (accomplished)f(in)h(parallel)e(game-tree)i(searc)o(h.)28 b(The)17 b(presen)o(tation)h(of)e(this)0 916 y(t)o(yp)q(e)e(of)g (taxonom)o(y)d(is)j(the)g(main)e(con)o(tribution)i(of)f(this)h(pap)q (er.)0 994 y(The)19 b(taxonom)o(y)c(will)i(b)q(e)i(brok)o(en)f(in)o(to) g(t)o(w)o(o)f(ma)r(jor)g(categories:)27 b Fk(\013\014)r Fp(-based)19 b(algorithms,)e(and)h(algorithms)d(based)k(on)0 1044 y(other)c(searc)o(h)h(paradigms)d(\()p Fk(S)r(S)r(S)r Fj(\003)p Fp(,)j Fk(E)r(R)p Fp(,)e(and)h(theoretical)g(metho)q(ds\).)20 b(F)m(or)14 b(the)h(former)f(category)m(,)g(a)g(table)h(is)f(giv)o(en)g (to)0 1094 y(isolate)i(the)h(fundamen)o(tal)e(di\013erences)j(b)q(et)o (w)o(een)g(the)g(algorithms.)23 b(The)17 b(table)g(is)f(divided)g(in)o (to)g(t)o(w)o(o)g(parts:)24 b(the)17 b(\014rst)0 1144 y(part)g(con)o(tains)g(c)o(haracteristics)i(of)e(the)h Fk(\013\014)r Fp(-based)g(algorithms,)d(while)i(the)g(second)i(part)e (con)o(tains)g(details)g(ab)q(out)g(an)0 1194 y(implemen)o(tatio)o(n)9 b(of)i(eac)o(h)i(algorithm.)h(Section)f(2)e(describ)q(es)j(the)f(v)n (arious)e(columns)f(giv)o(en)i(in)f(the)h(table,)g(and)g(then)g(giv)o (es)0 1243 y(some)h(brief)h(details)g(on)f(the)i(algorithms)c(con)o (tained)j(therein.)0 1322 y(The)j(algorithms)e(based)i(on)g(other)g (searc)o(h)h(paradigms)d(are)j(giv)o(en)e(in)g(Section)h(3.)27 b(Due)17 b(to)g(the)g(v)n(aried)g(nature)g(of)f(the)0 1372 y(metho)q(ds,)c(a)h(brief)g(description)h(is)f(giv)o(en)f(for)h (eac)o(h)h(of)e(the)i(algorithms)d(and)i(no)f(attempt)h(has)g(b)q(een)h (made)e(to)h(categorize)0 1422 y(them)h(to)g(the)h(same)f(exten)o(t)h (as)g(the)g Fk(\013\014)r Fp(-based)h(algorithms.)h(The)e(implemen)o (tation)c(details)j(ha)o(v)o(e)h(not)f(b)q(een)i(organized)0 1472 y(in)o(to)e(a)g(table,)g(since)h(some)e(of)h(the)h(algorithms)d (giv)o(en)i(are)h(of)f(a)g(theoretical)h(nature)g(and)f(ha)o(v)o(e)g (not)h(b)q(een)g(implemen)o(ted)0 1522 y(or)f(sim)o(ulated.)0 1600 y(The)g(\014nal)g(section)g(deals)g(with)g(some)f(conclusions)h (that)g(can)g(b)q(e)h(dra)o(wn)e(from)f(the)j(taxonom)o(y)m(.)0 1744 y Fl(2)48 b Fk(\013\014)r Fl(-BASED)15 b(P)l(ARALLEL)g(GAME-TREE)i (SEAR)o(CH)0 1864 y Fp(This)e(section)h(discusses)h(algorithms)c(based) i(on)g Fk(\013\014)j Fp(and)d(will)e(b)q(e)j(split)f(in)o(to)f(four)h (subsections.)23 b(Sections)16 b(2.1)e(and)h(2.2)0 1914 y(will)e(b)q(e)i(used)h(to)e(describ)q(e)j(the)e(columns)e(in)h(T)m (ables)g(1)h(and)f(2,)g(resp)q(ectiv)o(ely)m(.)21 b(The)15 b(description)g(of)f(the)i(algorithms)c(has)0 1964 y(b)q(een)i(divided) e(in)o(to)g(t)o(w)o(o)g(eras.)18 b(Section)13 b(2.3)f(co)o(v)o(ers)h(w) o(ork)f(\014rst)i(submitted)e(up)g(to)h(June,)g(1987.)j(Most)d(of)f (the)h(w)o(ork)g(from)0 2014 y(this)k(era)g(describ)q(es)i(algorithms)c (to)h(b)q(e)i(used)f(on)g(a)g(limited)d(n)o(um)o(b)q(er)i(of)h(pro)q (cessors.)29 b(Section)17 b(2.4)f(co)o(v)o(ers)h(w)o(ork)g(that)0 2064 y(w)o(as)f(\014rst)i(submitted)e(on)g(or)g(after)h(July)m(,)f (1987.)25 b(The)17 b(ma)r(jorit)o(y)d(of)i(the)i(algorithms)c(from)h (this)h(era)h(are)g(designed)g(for)0 2113 y(implemen)o(tatio)o(n)12 b(on)j(massiv)o(ely-parallel)c(hardw)o(are)k(systems,)g(whic)o(h)f(w)o (ere)i(una)o(v)n(ailable)d(to)h(most)g(researc)o(hers)j(b)q(efore)0 2163 y(1987.)0 2302 y Fl(2.1)48 b(Comparison)14 b(of)h(the)g Fk(\013\014)j Fl(Algorithms)0 2408 y Fp(T)m(able)13 b(1)h(summarizes)e (and)i(classi\014es)g(the)h(v)n(arious)e Fk(\013\014)r Fp(-based)i(algorithms,)c(and)j(is)f(divided)h(in)o(to)f(\014v)o(e)h (columns.)0 2487 y(The)j(\014rst)g(column)d(giv)o(es)j(the)f(name)g(of) f(the)i(algorithm,)d(and)i(the)h(reference)h(that)f(con)o(tains)f(the)h (most)e(details)h(ab)q(out)0 2537 y(the)f(algorithm.)k(F)m(or)14 b(example,)g(the)h(Y)m(oung)f(Brothers)j(W)m(ait)c(concept)j(has)f(b)q (een)h(describ)q(ed)h(in)d(man)o(y)f(pap)q(ers,)j(but)f(all)0 2587 y(of)e(the)i(algorithm's)c(details)j(are)g(lo)q(cated)g(in)f(F)m (eldmann's)f(thesis)j(\(1993\).)p 0 2626 780 2 v 46 2652 a Fi(1)64 2664 y Fh(Departmen)o(t)8 b(of)j(Computing)e(Science,)h(Univ) o(ersit)o(y)g(of)h(Alb)q(erta,)f(Edmon)o(ton,)f(Alb)q(erta,)h(Canada,)g (T6G)i(2H1.)0 2704 y(Email:)i Fg(brock@cs.ua)o(lb)o(ert)o(a.c)o(a)p eop %%Page: 2 2 2 1 bop 0 50 a Fp(2)603 b(ICCA)14 b(Journal)f(Submission)601 b(June)15 b(12,)e(1996)p 56 488 1827 2 v 56 498 V 55 538 2 40 v 317 526 a Fh(Algorithm)p 735 538 V 283 w(Date)e(First)p 944 538 V 70 w(Pro)q(cessor)p 1182 538 V 1182 538 V 133 w(P)o(arallelism)p 1532 538 V 1532 538 V 138 w(Sync)o(hroniza)o(tion)p 1882 538 V 55 577 V 308 565 a(\(Reference\))p 735 577 V 278 w(Describ)q(ed)p 944 577 V 62 w(Hierarc)o(h)o(y/)p 1182 577 V 1182 577 V 121 w(P)o(ossible)f(A)o(t)p 1532 577 V 1532 577 V 146 w(Done)h(A)o(t)h(These)p 1882 577 V 55 616 V 735 616 V 944 616 V 1006 605 a(Con)o(trol)p 1182 616 V 1182 616 V 136 w(These)f(No)q(des)p 1532 616 V 1532 616 V 204 w(No)q(des)p 1882 616 V 55 656 V 735 656 V 944 656 V 970 644 a(Distribution)p 1182 656 V 1532 656 V 1882 656 V 56 658 1827 2 v 56 668 V 55 707 2 40 v 81 695 a(P)o(arallel)e(Aspiration)h(Searc)o(h)p 735 707 V 319 w(1978)p 944 707 V 133 w(Static/)p 1182 707 V 88 w(Ro)q(ot)h(\()p Ff(\013\014)h Fh(windo)o(w\))p 1532 707 V 62 w(Ro)q(ot)p 1882 707 V 55 746 V 81 735 a(\(Baudet,)d(1978\))p 735 746 V 944 746 V 663 w(Cen)o(tralized)p 1182 746 V 1532 746 V 1882 746 V 56 748 1827 2 v 55 787 2 40 v 81 776 a(Mandatory)g(W)m(ork)i(First)p 735 787 V 372 w(1979)p 944 787 V 133 w(Static/)p 1182 787 V 88 w(T)o(yp)q(e)g(1+3+Left-)p 1532 787 V 94 w(Bad)g(T)o(yp)q(e)g(2)p 1882 787 V 55 827 V 81 815 a(\(Akl,)g(Barnard)e(and)i(Doran,)f(1982\))p 735 827 V 944 827 V 395 w(Cen)o(tralized)p 1182 827 V 54 w(most)g(c)o(hild)h(of)g(3)p 1532 827 V 1882 827 V 56 829 1827 2 v 55 868 2 40 v 81 856 a(T)m(ree)g(Splitting)p 735 868 V 509 w(1980)p 944 868 V 133 w(Static/)p 1182 868 V 88 w(T)m(op)g(k-ply)p 1532 868 V 199 w(Ro)q(ot)p 1882 868 V 55 907 V 81 896 a(\(Fink)o(el)f(and)g(Fish)o(burn,)g(1982\)) p 735 907 V 944 907 V 460 w(Cen)o(tralized)p 1182 907 V 1532 907 V 1882 907 V 56 909 1827 2 v 55 949 2 40 v 81 937 a(PV-Split)p 735 949 V 588 w(1981)p 944 949 V 133 w(Static/)p 1182 949 V 88 w(T)o(yp)q(e)h(1)p 1532 949 V 241 w(T)o(yp)q(e)g(1)p 1882 949 V 55 988 V 81 976 a(\(Marsland)e(and)i(Campb)q(ell,)e(1982\))p 735 988 V 944 988 V 402 w(Cen)o(tralized)p 1182 988 V 1532 988 V 1882 988 V 56 990 1827 2 v 55 1029 2 40 v 81 1017 a(Key)i(No)q(de)p 735 1029 V 570 w(1983)p 944 1029 V 133 w(Static/)p 1182 1029 V 88 w(T)o(yp)q(e)g(1+3+Left-)p 1532 1029 V 94 w(Bad)g(T)o(yp)q(e) g(2)p 1882 1029 V 55 1069 V 81 1057 a(\(Lindstrom,)d(1983\))p 735 1069 V 944 1069 V 615 w(Cen)o(tralized)p 1182 1069 V 54 w(most)i(c)o(hild)h(of)g(3)p 1532 1069 V 1882 1069 V 56 1070 1827 2 v 55 1110 2 40 v 81 1098 a(UIDP)m(ABS)p 735 1110 V 566 w(1986)p 944 1110 V 133 w(Static/)p 1182 1110 V 88 w(Ro)q(ot)p 1532 1110 V 273 w(None)p 1882 1110 V 55 1149 V 81 1137 a(\(Newb)q(orn,)f(1988\))p 735 1149 V 944 1149 V 635 w(Cen)o(tralized)p 1182 1149 V 1532 1149 V 1882 1149 V 56 1151 1827 2 v 55 1190 2 40 v 81 1178 a(DPVS)p 735 1190 V 601 w(01/1987)p 944 1190 V 81 w(Dynamic/)p 1182 1190 V 64 w(T)o(yp)q(e)h(1+3+2)p 1532 1190 V 151 w(T)o(yp)q(e)g(1+3+Bad)g(2)p 1882 1190 V 55 1230 V 81 1218 a(\(Sc)o(hae\013er,)d(1989\))p 735 1230 V 944 1230 V 637 w(Cen)o(tralized)p 1182 1230 V 1532 1230 V 1882 1230 V 56 1231 1827 2 v 55 1271 2 40 v 81 1259 a(EPVS)p 735 1271 V 604 w(06/1987)p 944 1271 V 81 w(Dynamic/)p 1182 1271 V 64 w(T)o(yp)q(e)j(1+3)p 1532 1271 V 196 w(T)o(yp)q(e)g(1+3)p 1882 1271 V 55 1310 V 81 1298 a(\(Hy)o(att,)f(Suter)g(and)h(Nelson,)f(1989\))p 735 1310 V 944 1310 V 398 w(Cen)o(tralized)p 1182 1310 V 1532 1310 V 1882 1310 V 56 1312 1827 2 v 55 1351 2 40 v 81 1339 a(W)m(a)o(yco)q(ol)p 735 1351 V 592 w(1987)p 944 1351 V 109 w(Dynamic/)p 1182 1351 V 64 w(All,)h(except)f(T)o(yp)q (e)h(2)p 1532 1351 V 63 w(No)q(des)g(with)g(TT)p 1882 1351 V 55 1391 V 81 1379 a(\(F)m(elten)f(and)g(Otto,)h(1988\))p 735 1391 V 944 1391 V 527 w(Distributed)p 1182 1391 V 53 w(with)g(no)g(TT)i(en)o(try)p 1532 1391 V 76 w(&)f(no)f(cuto\013)p 1882 1391 V 56 1392 1827 2 v 55 1432 2 40 v 81 1420 a(Y)m(oung)f (Brothers)g(W)m(ait)p 735 1432 V 369 w(10/1987)p 944 1432 V 81 w(Dynamic/)p 1182 1432 V 64 w(T)o(yp)q(e)h(1+3+Bad)g(2)p 1532 1432 V 77 w(T)o(yp)q(e)g(1+Bad)g(2)p 1882 1432 V 55 1471 V 81 1459 a(\(F)m(eldmann,)d(1993\))p 735 1471 V 944 1471 V 623 w(Distributed)p 1182 1471 V 1532 1471 V 1882 1471 V 56 1473 1827 2 v 55 1512 2 40 v 81 1500 a(Dynamic)h(T)m(ree)i(Splitting)p 735 1512 V 360 w(1988)p 944 1512 V 109 w(Dynamic/)p 1182 1512 V 64 w(T)o(yp)q(e)g(1+3+Bad)g(2)p 1532 1512 V 77 w(T)o(yp)q(e)g(1+Bad)g(2)p 1882 1512 V 55 1552 V 81 1540 a(\(Hy)o(att,)f(1988\))p 735 1552 V 944 1552 V 685 w(Distributed)p 1182 1552 V 1532 1552 V 1882 1552 V 56 1553 1827 2 v 55 1593 2 40 v 81 1581 a(Bound-and-)o(Bran)o(c)o(h)p 735 1593 V 403 w(08/1988)p 944 1593 V 81 w(Dynamic/)p 1182 1593 V 64 w(T)o(yp)q(e)h(1+3+Bad)g(2)p 1532 1593 V 77 w(T)o(yp)q(e)g(1+Bad)g(2)p 1882 1593 V 55 1632 V 81 1620 a(\(F)m(erguson)e(and)i(Korf,)g(1988\))p 735 1632 V 944 1632 V 486 w(Distributed)p 1182 1632 V 1532 1632 V 1882 1632 V 56 1634 1827 2 v 55 1673 2 40 v 81 1661 a(Dela)o(y)o(ed)e(Branc)o(h)h(T)m(ree)i(Expansion)p 735 1673 V 226 w(1990)p 944 1673 V 133 w(Static/)p 1182 1673 V 88 w(T)o(yp)q(e)f(1+3)p 1532 1673 V 196 w(Bad)g(T)o(yp)q(e)g(2)p 1882 1673 V 55 1713 V 81 1701 a(\(Hsu,)g(1990\))p 735 1713 V 944 1713 V 714 w(Cen)o(tralized)p 1182 1713 V 1532 1713 V 1882 1713 V 56 1714 1827 2 v 55 1754 2 40 v 81 1742 a(F)m(ron)o(tier)e(Splitting)p 735 1754 V 454 w(1993)p 944 1754 V 109 w(Dynamic/)p 1182 1754 V 64 w(All)p 1532 1754 V 304 w(Ro)q(ot)p 1882 1754 V 55 1793 V 81 1781 a(\(Lu,)h(1993\))p 735 1793 V 944 1793 V 733 w(Distributed)p 1182 1793 V 1532 1793 V 1882 1793 V 56 1795 1827 2 v 55 1834 2 40 v 81 1823 a Ff(\013\014)r Fh(*)p 735 1834 V 661 w(1993)p 944 1834 V 109 w(Dynamic/)p 1182 1834 V 64 w(T)o(yp)q(e)h(1+3)p 1532 1834 V 196 w(T)o(yp)q(e)g(1+3+Bad)g(2)p 1882 1834 V 55 1874 V 81 1862 a(\(Da)o(vid,)e(1993\))p 735 1874 V 944 1874 V 683 w(Distributed)p 1182 1874 V 1532 1874 V 1882 1874 V 56 1875 1827 2 v 55 1915 2 40 v 81 1903 a(CABP)p 735 1915 V 624 w(1994)p 944 1915 V 133 w(Static/)p 1182 1915 V 88 w(T)o(yp)q(e)i(1+3)p 1532 1915 V 196 w(Bad)g(T)o(yp)q(e)g(2)p 1882 1915 V 55 1954 V 81 1943 a(\(Cung,)f(1994\))p 735 1954 V 944 1954 V 692 w(Cen)o(tralized)p 1182 1954 V 1532 1954 V 1882 1954 V 56 1956 1827 2 v 55 1995 2 40 v 81 1984 a(Jam)o(b)q(oree)p 735 1995 V 574 w(1994)p 944 1995 V 109 w(Dynamic/)p 1182 1995 V 64 w(T)o(yp)q(e)h(1+3+Bad)g(2)p 1532 1995 V 77 w(T)o(yp)q(e)g(1+Bad)g(2)p 1882 1995 V 55 2035 V 81 2023 a(\(Kuszmaul,)e(1994\))p 735 2035 V 944 2035 V 621 w(Distributed)p 1182 2035 V 1532 2035 V 1882 2035 V 56 2037 1827 2 v 55 2076 2 40 v 81 2064 a(ABD)o(AD)o(A)p 735 2076 V 569 w(1995)p 944 2076 V 109 w(Dynamic/)p 1182 2076 V 64 w(T)o(yp)q(e)i (1+3+Bad)g(2)p 1532 2076 V 77 w(T)o(yp)q(e)g(1+Bad)g(2)p 1882 2076 V 55 2115 V 81 2104 a(\(W)m(eill,)f(1995\))p 735 2115 V 944 2115 V 696 w(Distributed)p 1182 2115 V 1532 2115 V 1882 2115 V 56 2117 1827 2 v 55 2157 2 40 v 81 2145 a(Dynamic)f(Multiple)h(PV-Split)p 735 2157 V 297 w(1995)p 944 2157 V 109 w(Dynamic/)p 1182 2157 V 64 w(No)q(des)h(within)p 1532 2157 V 145 w(No)q(des)g(within)p 1882 2157 V 55 2196 V 81 2184 a(\(Marsland)e(and)i(Gao,)f(1995\))p 735 2196 V 944 2196 V 487 w(Distributed)p 1182 2196 V 53 w(PV)i(set)p 1532 2196 V 244 w(PV)g(set)p 1882 2196 V 56 2198 1827 2 v 55 2237 2 40 v 81 2225 a(APHID)p 735 2237 V 608 w(1996)p 944 2237 V 133 w(Static/)p 1182 2237 V 88 w(T)m(op)f(k-ply)p 1532 2237 V 199 w(None)p 1882 2237 V 55 2276 V 81 2265 a(\(Bro)q(c)o(kingto)o(n)e(and)h(Sc)o (hae\013er,)f(1996\))p 735 2276 V 944 2276 V 368 w(Cen)o(tralized)p 1182 2276 V 1532 2276 V 1882 2276 V 56 2278 1827 2 v 56 2288 V 312 2363 a Fp(T)m(able)14 b(1:)j(Comparison)12 b(of)i(P)o(arallel)e Fk(\013\014)r Fp(-based)j(Game-T)m(ree)e(Searc)o (h)h(Algorithms)p eop %%Page: 3 3 3 2 bop 467 50 a Fe(A)14 b(T)m(axonom)o(y)d(of)i(P)o(arallel)g(Game-T)m (ree)g(Searc)o(h)h(Algorithms)465 b Fp(3)0 195 y(The)18 b(second)h(column)e(giv)o(es)g(the)i(date)f(that)g(the)g(algorithm)d(w) o(as)j(\014rst)h(published)f(or)g(receiv)o(ed)h(b)o(y)e(a)h(journal.)29 b(This)0 245 y(information)11 b(has)j(b)q(een)h(used)g(to)f(order)g (the)h(algorithms)c(in)o(to)i(c)o(hronological)g(order.)0 324 y(The)20 b(third)g(column)f(con)o(tains)h(information)d(on)j(b)q (oth)g(the)h(pro)q(cessor)g(hierarc)o(h)o(y)g(and)f(the)g(distribution) g(of)f(con)o(trol)0 374 y(within)12 b(the)h(algorithm.)i Fn(Pr)n(o)n(c)n(essor)e(Hier)n(ar)n(chy)e Fp(categorizes)j(algorithms)c (based)j(on)g(the)g(rigidit)o(y)e(of)h(the)h(pro)q(cessor)h(tree.)0 423 y(If)g(the)g(pro)q(cessor)i(tree)f(is)f Fn(static)p Fp(,)f(one)h(or)g(more)f(pro)q(cessors)j(are)f(designated)f(as)g (masters,)g(and)f(con)o(trol)h(the)h(other)f(sla)o(v)o(e)0 473 y(pro)q(cessors.)20 b(This)14 b(hierarc)o(h)o(y)g(is)g(\014xed)g (throughout)g(a)f(searc)o(h)i(of)e(the)i(game-tree.)i(A)d Fn(dynamic)h Fp(pro)q(cessor)g(tree)g(c)o(hanges)0 523 y(based)f(on)g(the)g(distribution)f(of)h(busy)g(and)f(idle)g(pro)q (cessors.)21 b Fn(Contr)n(ol)14 b(Distribution)f Fp(describ)q(es)j (whether)f(the)f(con)o(trol)g(of)0 573 y(the)i(algorithm)c(is)j Fn(c)n(entr)n(alize)n(d)g Fp(on)g(a)g(small)e(n)o(um)o(b)q(er)h(of)h (masters)g(\(e.g.)21 b(PV-Split\),)15 b(or)g(could)g(b)q(e)h Fn(distribute)n(d)f Fp(amongst)0 623 y(all)e(pro)q(cessors)j(\(e.g.)i (Y)m(oung)13 b(Brothers)i(W)m(ait\).)0 702 y(The)e(fourth)g(column)f (describ)q(es)j(the)e(t)o(ypical)f(no)q(des)i(of)e(the)i(game-tree)f (where)h(parallelism)c(could)j(o)q(ccur.)19 b(The)13 b(descrip-)0 751 y(tion)f(is)h(based)g(on)g(the)g(classi\014cation)f (of)g(the)i(minim)o(al)9 b(game-tree)j(b)o(y)h(Kn)o(uth)g(and)f(Mo)q (ore)h(\(1975\).)k(Note)c(that)g(the)g(t)o(yp)q(e)0 801 y(2)h(\(cut)h(no)q(des\))g(ha)o(v)o(e)f(b)q(een)h(di\013eren)o(tiated)g (in)o(to)f(t)o(w)o(o)f(sub-classes.)21 b(When)14 b(a)g(t)o(yp)q(e)h(2)e (no)q(de)i(has)f(not)g(b)q(een)i(pruned)f(after)0 851 y(searc)o(hing)f(the)h(\014rst)g(mo)o(v)o(e,)d(this)i(no)q(de)g(is)g (called)g(a)g Fn(b)n(ad)h(typ)n(e)g(2)f Fp(no)q(de)h(due)f(to)g(its)g (incorrect)h(mo)o(v)o(e)e(ordering.)18 b(Similarly)l(,)0 901 y Fn(go)n(o)n(d)e(typ)n(e)f(2)g Fp(no)q(des)g(are)g(considered)h (to)e(b)q(e)h(t)o(yp)q(e)g(2)f(no)q(des)h(that)g(cause)g(a)f(cuto\013)h (after)g(examining)d(the)j(\014rst)g(mo)o(v)o(e)e(\(i.e.)0 951 y(the)h(mo)o(v)o(e)f(ordering)h(is)f(correct\).)0 1029 y(F)m(or)i(example,)g(PV-Split)g(only)g(implem)o(en)o(ts)f (parallelism)f(at)i(t)o(yp)q(e)h(1)g(\(principal)f(v)n(ariation\))f(no) q(des,)i(while)f(the)i(Y)m(oung)0 1079 y(Brothers)e(W)m(ait)e (algorithms)e(allo)o(w)h(for)h(parallelism)e(at)j(t)o(yp)q(e)g(1,)f(t)o (yp)q(e)h(3)g(\(all)e(no)q(des\))j(and)f(bad)f(t)o(yp)q(e)h(2)g(no)q (des.)19 b(A)o(t)13 b(go)q(o)q(d)0 1129 y(t)o(yp)q(e)j(2)f(no)q(des,)i (the)f(Y)m(oung)f(Brothers)i(W)m(ait)d(algorithm)f(will)h(searc)o(h)j (the)f(\014rst)g(mo)o(v)o(e,)e(ac)o(hiev)o(e)i(a)f(cuto\013,)h(and)g (none)g(of)0 1179 y(the)e(other)h(c)o(hildren)f(will)e(b)q(e)j(ev)n (aluated.)0 1258 y(The)g(\014fth)g(column)e(indicates)i(whic)o(h)f(no)q (des)i(of)e(the)h(game-tree)f(migh)o(t)f(ha)o(v)o(e)h(parallelism)e (constrained)k(b)o(y)e(w)o(aiting)f(for)0 1308 y(the)f(\014rst)h Fk(k)f Fp(c)o(hildren)g(to)g(b)q(e)g(ev)n(aluated.)17 b(F)m(or)12 b(example,)e(bad)i(t)o(yp)q(e)g(2)f(no)q(des)i(are)f(sync)o (hronization)g(p)q(oin)o(ts)f(for)h(Akl)f Fn(et.)h(al)p Fp('s)0 1357 y(Mandatory)f(W)m(ork)g(First)g(algorithm,)e(while)i(t)o (yp)q(e)h(1)f(and)g(bad)h(t)o(yp)q(e)g(2)f(no)q(des)h(are)g(sync)o (hronization)f(p)q(oin)o(ts)h(for)f(F)m(erguson)0 1407 y(and)j(Korf)s('s)g(Bound-and-Branc)o(h)g(algorithm.)0 1554 y Fl(2.2)48 b(Comparison)14 b(of)h(the)g Fk(\013\014)j Fl(Implemen)o(tati)o(ons)0 1662 y Fp(T)m(able)13 b(2)h(summarizes)e(an) i(implem)o(en)o(tation)d(of)i(eac)o(h)i(algorithm)c(giv)o(en)i(in)h(T)m (able)f(1.)0 1741 y(The)j(\014rst)g(column)d(giv)o(es)i(the)h(name)e (of)g(the)i(algorithm,)c(and)j(the)h(reference)i(to)d(the)g(pap)q(er)h (that)f(con)o(tains)g(the)h(details)0 1790 y(ab)q(out)e(the)i(implem)o (en)o(tation.)h(In)e(some)e(cases,)j(this)e(pap)q(er)i(ma)o(y)c(b)q(e)j (di\013eren)o(t)h(than)e(the)i(pap)q(er)f(whic)o(h)f(b)q(est)i(describ) q(es)0 1840 y(the)e(algorithm.)0 1919 y(The)f(second)g(column)e (describ)q(es)k(the)e(underlying)f(hardw)o(are)h(used)g(to)f(host)h (the)g(selected)h(implemen)o(tation.)g(A)f(soft)o(w)o(are)0 1969 y Fn(simulation)h Fp(of)f(hardw)o(are)h(is)g(denoted)h(in)e(this)h (column.)0 2048 y(The)k(third)g(column)e(describ)q(es)j(the)f(t)o(yp)q (e)h(of)e(game-trees)g(explored)h(b)o(y)f(the)i(algorithm.)26 b(If)17 b(the)h(game-trees)g(are)g(not)0 2098 y(generated)12 b(b)o(y)f(game-pla)o(ying)d(programs,)i(they)i(are)f(considered)h(to)f (b)q(e)h Fn(arti\014cial)g(tr)n(e)n(es)p Fp(.)k(In)11 b(terms)g(of)f(a)o(v)o(erage)h(branc)o(hing)0 2147 y(factor,)i(c)o (hess)j(trees)f(are)g(wider)f(than)g(Othello)f(trees,)i(and)f(b)q(oth)g (are)g(wider)g(than)g(c)o(hec)o(k)o(ers)i(trees.)0 2226 y(The)j(fourth)g(column)e(denotes)i(whic)o(h)g(of)f(the)h(sequen)o (tial)g(game-tree)f(searc)o(hing)h(algorithms)d(w)o(as)j(parallelized:) 27 b Fk(\013\014)0 2276 y Fp(\(Brudno,)21 b(1963;)g(Kn)o(uth)f(and)f (Mo)q(ore,)i(1975\),)e(PVS)h(\(Marsland,)g(1983\))f(or)g(NegaScout)h (\(Reinfeld,)g(1983\).)34 b(Some)0 2326 y(programs)17 b(are)i(more)e(e\016cien)o(t)h(when)h(using)f(a)g(di\013eren)o(t)h (sequen)o(tial)f(algorithm,)e(dep)q(ending)j(on)f(the)h(nature)g(of)e (the)0 2376 y(ev)n(aluation)g(function)i(and)g(the)g(strength)h(of)e (the)i(mo)o(v)o(e)d(ordering)i(tec)o(hniques)h(in)e(the)i(sequen)o (tial)f(program.)31 b(Th)o(us,)0 2425 y(the)18 b(c)o(hoice)g(of)e (sequen)o(tial)i(algorithm)c(to)j(compare)g(the)h(parallel)e(algorithm) e(against)j(is)g(a)g(factor)g(to)g(consider)h(when)0 2475 y(ev)n(aluating)12 b(a)i(parallel)f(algorithm's)e(results.)0 2554 y(The)k(\014fth)g(column)f(describ)q(es)j(what)e(t)o(yp)q(e)h(of)e (transp)q(osition)h(table)g(has)g(b)q(een)h(implemen)o(ted)d(for)i(the) g(algorithm.)k(E\016-)0 2604 y(cien)o(t)c(sharing)f(of)g(transp)q (osition)g(table)h(information)c(is)j(crucial)h(to)f(the)h(p)q (erformance)f(of)g(a)g(parallel)g(game-tree)g(searc)o(h)0 2654 y(algorithm.)g(The)d(t)o(w)o(o)f(main)e(metho)q(ds)h(are)i(a)f Fn(distribute)n(d)f Fp(message-passing)h(transp)q(osition)g(table)g (and)g(a)g Fn(shar)n(e)n(d-memory)0 2704 y Fp(transp)q(osition)k (table.)k(Sp)q(ecial)c(hardw)o(are)g(is)g(required)g(to)g(implemen)o(t) d(a)j(shared-memory)e(transp)q(osition)i(table,)f(but)h(is)p eop %%Page: 4 4 4 3 bop 0 50 a Fp(4)603 b(ICCA)14 b(Journal)f(Submission)601 b(June)15 b(12,)e(1996)p 9 508 1921 2 v 9 518 V 8 557 2 40 v 270 545 a Fh(Algorithm)p 688 557 V 321 w(Hardw)o(are)p 961 557 V 143 w(T)m(est)p 1192 557 V 110 w(Sequen)o(tial)p 1405 557 V 84 w(T)m(rans-)p 1624 557 V 1624 557 V 146 w(Sp)q(eedup)p 1928 557 V 8 597 V 261 585 a(\(Reference\))p 688 597 V 348 w(Used)p 961 597 V 153 w(Domain)p 1192 597 V 80 w(Algorithm)p 1405 597 V 73 w(P)o(osition)p 1624 597 V 1624 597 V 125 w(Obtained)p 1928 597 V 8 636 V 688 636 V 961 636 V 1192 636 V 1405 636 V 1473 624 a(T)m(able)p 1624 636 V 1928 636 V 9 638 1921 2 v 9 648 V 8 687 2 40 v 34 675 a(P)o(arallel)d(Aspiration)f(Searc)o(h)p 688 687 V 304 w(Sim)o(ulation)p 961 687 V 97 w(Arti\014cial)p 1192 687 V 130 w Ff(\013\014)p 1405 687 V 159 w Fh(none)p 1624 687 V 96 w Fd(\024)i Fh(6)g(for)g(large)f(n)p 1928 687 V 8 727 V 34 715 a(\(Baudet,)f(1978\))p 688 727 V 961 727 V 771 w(T)m(rees)p 1192 727 V 1405 727 V 1624 727 V 530 w(\(sim)o(ulated\))p 1928 727 V 9 728 1921 2 v 8 768 2 40 v 34 756 a(Mandatory)g(W)m(ork)i(First)p 688 768 V 357 w(Sim)o(ulation)p 961 768 V 97 w(Arti\014cial)p 1192 768 V 130 w Ff(\013\014)p 1405 768 V 148 w Fh(\\score)p 1624 768 V 85 w Fd(\024)g Fh(6)g(for)g(large)f(n)p 1928 768 V 8 807 V 34 795 a(\(Akl,)h(Barnard)f(and)g(Doran,)g(1982\))p 688 807 V 961 807 V 503 w(T)m(rees)p 1192 807 V 1405 807 V 349 w(table")p 1624 807 V 85 w(\(sim)o(ulated\))p 1928 807 V 9 809 1921 2 v 8 848 2 40 v 34 836 a(T)m(ree)h(Splitting)p 688 848 V 506 w(LSI-11)f(&)p 961 848 V 114 w(Chec)o(k)o(ers)p 1192 848 V 130 w Ff(\013\014)p 1405 848 V 159 w Fh(none)p 1624 848 V 96 w(2.34)h(\(n=3\))p 1928 848 V 8 888 V 34 876 a(\(Fink)o(el)f(and)g(Fish)o(burn,)g(1982\))p 688 888 V 274 w(Sim)o(ulation)p 961 888 V 1192 888 V 1405 888 V 1624 888 V 737 w(5.12)h(\(n=27,sim\))p 1928 888 V 9 889 1921 2 v 8 929 2 40 v 34 917 a(PV-Split)p 688 929 V 611 w(Sun)g(3)p 961 929 V 163 w(Chess)p 1192 929 V 142 w(PVS)p 1405 929 V 145 w(lo)q(cal)p 1624 929 V 97 w(3.75)g(\(n=5\))p 1928 929 V 8 968 V 34 956 a(\(Marsland,)e (Olafsson)g(and)h(Sc)o(hae\013er,)e(1985\))p 688 968 V 95 w(Net)o(w)o(ork)p 961 968 V 1192 968 V 1405 968 V 1624 968 V 1928 968 V 9 970 1921 2 v 8 1009 2 40 v 34 998 a(Key)j(No)q(de)p 688 1009 V 555 w(Sim)o(ulation)p 961 1009 V 97 w(Arti\014cial)p 1192 1009 V 130 w Ff(\013\014)p 1405 1009 V 159 w Fh(none)p 1624 1009 V 96 w(12.57)g(\(n=20\))p 1928 1009 V 8 1049 V 34 1037 a(\(Lindstrom,)e(1983\))p 688 1049 V 961 1049 V 722 w(T)m(rees)p 1192 1049 V 1405 1049 V 1624 1049 V 1928 1049 V 9 1050 1921 2 v 8 1090 2 40 v 34 1078 a(UIDP)m(ABS)p 688 1090 V 530 w(Data)h(General)p 961 1090 V 102 w(Chess)p 1192 1090 V 155 w Ff(\013\014)p 1405 1090 V 159 w Fh(lo)q(cal)p 1624 1090 V 97 w(3.94)h(\(n=8\))p 1928 1090 V 8 1129 V 34 1117 a(\(Newb)q(orn,)f(1988\))p 688 1129 V 420 w(\(mixed)f(pro)q(cs.\))p 961 1129 V 1192 1129 V 1405 1129 V 1624 1129 V 1928 1129 V 9 1131 1921 2 v 8 1170 2 40 v 34 1159 a(DPVS)p 688 1170 V 650 w(Sun)i(3)p 961 1170 V 163 w(Chess)p 1192 1170 V 95 w(NegaScout)p 1405 1170 V 52 w(TT.)i(Mgr)e(-)p 1624 1170 V 54 w(7.64)g(\(n=19\))p 1928 1170 V 8 1210 V 34 1198 a(\(Sc)o(hae\013er,)d(1989\))p 688 1210 V 469 w(Net)o(w)o(ork)p 961 1210 V 1192 1210 V 1405 1210 V 555 w(messages)p 1624 1210 V 1928 1210 V 9 1212 1921 2 v 8 1251 2 40 v 34 1239 a(EPVS)p 688 1251 V 637 w(Sequen)o(t)p 961 1251 V 144 w(Chess)p 1192 1251 V 155 w Ff(\013\014)p 1405 1251 V 145 w Fh(shared)p 1624 1251 V 82 w(5.93)j(\(n=16\))p 1928 1251 V 8 1290 V 34 1279 a(\(Hy)o(att,)f(Suter)g(and)h(Nelson,)g(1989\))p 688 1290 V 233 w(Balance)p 961 1290 V 1192 1290 V 1405 1290 V 565 w(memory)p 1624 1290 V 1928 1290 V 9 1292 1921 2 v 8 1331 2 40 v 34 1320 a(W)m(a)o(yco)q(ol)p 688 1331 V 576 w(Hyp)q(ercub)q(e)p 961 1331 V 122 w(Chess)p 1192 1331 V 155 w Ff(\013\014)p 1405 1331 V 111 w Fh(distributed)p 1624 1331 V 46 w(101)g(\(n=256\))p 1928 1331 V 8 1371 V 34 1359 a(\(F)m(elten)f(and)g(Otto,)i(1988\))p 688 1371 V 961 1371 V 1192 1371 V 1405 1371 V 1043 w(messages)p 1624 1371 V 1928 1371 V 9 1373 1921 2 v 8 1412 2 40 v 34 1400 a(Y)m(oung)f(Brothers)e(W)m(ait)p 688 1412 V 371 w(T)m(ransputers)p 961 1412 V 113 w(Chess)p 1192 1412 V 95 w(NegaScout)p 1405 1412 V 48 w(distributed)p 1624 1412 V 46 w(142)i(\(n=256\))p 1928 1412 V 8 1451 V 34 1440 a(\(F)m(eldmann,)e(1993\))p 688 1451 V 961 1451 V 1192 1451 V 1405 1451 V 1139 w(messages)p 1624 1451 V 63 w(344)i(\(n=1024\))p 1928 1451 V 9 1453 1921 2 v 8 1493 2 40 v 34 1481 a(Dynamic)e(T)m(ree)j(Splitting)p 688 1493 V 366 w(Sequen)o(t)p 961 1493 V 144 w(Chess)p 1192 1493 V 155 w Ff(\013\014)p 1405 1493 V 145 w Fh(shared)p 1624 1493 V 82 w(8.81)f(\(n=16\))p 1928 1493 V 8 1532 V 34 1520 a(\(Hy)o(att,)f(1988\))p 688 1532 V 521 w(Balance)p 961 1532 V 1192 1532 V 1405 1532 V 565 w(memory)p 1624 1532 V 1928 1532 V 9 1534 1921 2 v 8 1573 2 40 v 34 1561 a(Bound-and-Br)o(anc)n(h)p 688 1573 V 413 w(Hyp)q(ercub)q(e)p 961 1573 V 109 w(Othello)p 1192 1573 V 142 w Ff(\013\014)p 1405 1573 V 111 w Fh(distributed)p 1624 1573 V 46 w(12)h(\(n=32\))p 1928 1573 V 8 1613 V 34 1601 a(\(F)m(erguson)e(and)i(Korf,)g(1988\))p 688 1613 V 961 1613 V 1192 1613 V 1405 1613 V 1003 w(messages)p 1624 1613 V 1928 1613 V 9 1614 1921 2 v 8 1654 2 40 v 34 1642 a(Dela)o(y)o(ed)f(Branc)o(h)g(T)m(ree)h(Expansion)p 688 1654 V 211 w(Sim)o(ulation)p 961 1654 V 121 w(Chess)p 1192 1654 V 155 w Ff(\013\014)p 1405 1654 V 159 w Fh(none)p 1624 1654 V 96 w(350)g(\(n=1000,)p 1928 1654 V 8 1693 V 34 1681 a(\(Hsu,)g(1990\))p 688 1693 V 961 1693 V 1192 1693 V 1405 1693 V 1624 1693 V 1434 w(sim)o(ulated\))p 1928 1693 V 9 1695 1921 2 v 8 1734 2 40 v 34 1722 a(F)m(ron)o(tier)f (Splitting)p 688 1734 V 482 w(BBN)p 961 1734 V 146 w(Chec)o(k)o(ers)p 1192 1734 V 70 w(NegaScout)p 1405 1734 V 82 w(shared)p 1624 1734 V 82 w(3.32)h(\(n=16\))p 1928 1734 V 8 1774 V 34 1762 a(\(Lu,)g(1993\))p 688 1774 V 568 w(TC2000)p 961 1774 V 1192 1774 V 1405 1774 V 566 w(memory)p 1624 1774 V 1928 1774 V 9 1775 1921 2 v 8 1815 2 40 v 34 1803 a Ff(\013\014)r Fh(*)p 688 1815 V 637 w(T)m(ransputers)p 961 1815 V 113 w(Chess)p 1192 1815 V 95 w(NegaScout)p 1405 1815 V 48 w(distributed)p 1624 1815 V 46 w(6.5)g(\(n=8+8TT\))p 1928 1815 V 8 1854 V 34 1842 a(\(Da)o(vid,)f(1993\))p 688 1854 V 961 1854 V 1192 1854 V 1405 1854 V 1199 w(messages)p 1624 1854 V 1928 1854 V 9 1856 1921 2 v 8 1895 2 40 v 34 1883 a(CABP)p 688 1895 V 631 w(Sequen)o(t)p 961 1895 V 120 w(Arti\014cial)p 1192 1895 V 130 w Ff(\013\014)p 1405 1895 V 145 w Fh(shared)p 1624 1895 V 82 w(4.6)h(\(n=9\))p 1928 1895 V 8 1935 V 34 1923 a(\(Cung,)f(1994\))p 688 1935 V 528 w(Balance)p 961 1935 V 149 w(T)m(rees)p 1192 1935 V 1405 1935 V 334 w(memory)p 1624 1935 V 1928 1935 V 9 1936 1921 2 v 8 1976 2 40 v 34 1964 a(Jam)o(b)q(oree)p 688 1976 V 598 w(CM-5)p 961 1976 V 164 w(Chess)p 1192 1976 V 95 w(NegaScout)p 1405 1976 V 48 w(distributed)p 1624 1976 V 46 w Fd(\031)p Fh(50)i(\(n=512\))p 1928 1976 V 8 2015 V 34 2003 a(\(Kuszmaul,)d(1994\))p 688 2015 V 961 2015 V 1192 2015 V 1405 2015 V 1138 w(messages)p 1624 2015 V 1928 2015 V 9 2017 1921 2 v 8 2056 2 40 v 34 2044 a(ABD)o(AD)o(A)p 688 2056 V 593 w(CM-5)p 961 2056 V 164 w(Chess)p 1192 2056 V 95 w(NegaScout)p 1405 2056 V 48 w(distributed)p 1624 2056 V 46 w(15.85)i(\(n=32\))p 1928 2056 V 8 2096 V 34 2084 a(\(W)m(eill,)f(1996\))p 688 2096 V 961 2096 V 754 w(\(&)i(Othello\))p 1192 2096 V 1405 2096 V 277 w(messages)p 1624 2096 V 1928 2096 V 9 2097 1921 2 v 8 2137 2 40 v 34 2125 a(Dynamic)d(Multiple)h (PV-Split)p 688 2137 V 298 w(AP-1000)p 961 2137 V 116 w(Arti\014cial)p 1192 2137 V 117 w(PVS)p 1405 2137 V 145 w(none)p 1624 2137 V 96 w Fd(\031)p Fh(32)i(\(n=64\))p 1928 2137 V 8 2176 V 34 2164 a(\(Marsland)e(and)g(Gao,)h(1995\))p 688 2176 V 961 2176 V 594 w(T)m(rees)p 1192 2176 V 1405 2176 V 1624 2176 V 1928 2176 V 9 2178 1921 2 v 8 2217 2 40 v 34 2205 a(APHID)p 688 2217 V 618 w(Sparc)f(2)p 961 2217 V 149 w(Chess)p 1192 2217 V 95 w(NegaScout)p 1405 2217 V 96 w(lo)q(cal)p 1624 2217 V 97 w(6.04)h(\(n=16\))p 1928 2217 V 8 2257 V 34 2245 a(\(Bro)q(c)o(kington)d(and)j(Sc)o (hae\013er,)d(1995\))p 688 2257 V 200 w(Net)o(w)o(ork)p 961 2257 V 1192 2257 V 1405 2257 V 1624 2257 V 1928 2257 V 9 2258 1921 2 v 9 2268 V 262 2343 a Fp(T)m(able)13 b(2:)18 b(Comparison)12 b(of)h(P)o(arallel)g Fk(\013\014)r Fp(-based)i(Game-T)m(ree)e(Searc)o(h)h(Implemen)o(tations)p eop %%Page: 5 5 5 4 bop 467 50 a Fe(A)14 b(T)m(axonom)o(y)d(of)i(P)o(arallel)g(Game-T)m (ree)g(Searc)o(h)h(Algorithms)465 b Fp(5)0 195 y(generally)15 b(faster)g(than)g(distributed)h(transp)q(osition)e(tables)i(based)f(on) g(message)f(passing.)21 b(Lo)q(cal)15 b(transp)q(osition)g(tables)0 245 y(are)h(main)o(tained)d(separately)i(on)g(eac)o(h)h(pro)q(cessor,)h (but)e(no)g(transp)q(osition)g(table)g(information)e(is)i(shared)h(b)q (et)o(w)o(een)g(the)0 295 y(pro)q(cessors.)0 374 y(The)h(\014nal)e (column)g(giv)o(es)h(the)g Fn(sp)n(e)n(e)n(dup)h Fp(of)f(the)g (implemen)o(tation)d(on)j(a)g(large)f(n)o(um)o(b)q(er)h(of)f(pro)q (cessors.)27 b(There)18 b(will)c(b)q(e)0 423 y(a)19 b(tendency)h(to)f (read)g(do)o(wn)f(this)h(column)f(and)g(use)i(the)f(absolute)g(sp)q (eedup)i(or)e(relativ)o(e)f(e\016ciencies)i(to)f(determine)0 473 y(something)d(ab)q(out)h(a)g(pair)g(of)g(algorithms.)26 b(It)18 b(is)f(v)o(ery)h(hard)f(and)g(misleading)e(to)i(compare)g(t)o (w)o(o)g(algorithms)e(in)i(this)0 523 y(manner.)g(There)e(are)f(\014v)o (e)h(ma)r(jor)d(concerns)j(when)g(comparing)d(sp)q(eedup)j(n)o(um)o(b)q (ers.)0 602 y(The)i(\014rst)g(concern)h(deals)e(with)g(sim)o(ulation)e (results.)27 b(It)16 b(is)g(often)h(di\016cult)f(to)g(determine)g(ho)o (w)g(a)g(parallel)g(algorithm)0 652 y(will)c(b)q(eha)o(v)o(e)j(on)e(a)h (large)g(n)o(um)o(b)q(er)f(of)g(mac)o(hines,)g(due)h(to)g(o)o(v)o (er-simpli\014cation)d(of)i(the)i(sim)o(ulation)c(mo)q(del)h(b)q(eing)i (used.)0 731 y(The)j(second)g(ma)r(jor)d(concern)k(deals)e(with)g(the)g (test)h(domain.)23 b(Arti\014cial)15 b(trees)j(rarely)e(re\015ect)i (the)e(unique)h(prop)q(erties)0 780 y(of)12 b(searc)o(hing)i(a)f(real)g (c)o(hess/c)o(hec)o(k)o(ers/Othe)q(llo)h(tree,)g(and)f(migh)o(t)e(b)q (e)j(geared)f(to)o(w)o(ards)g(illustrating)f(the)i(strength)g(of)e(the) 0 830 y(parallel)h(algorithm)e(\(Plaat)i Fn(et.)19 b(al)p Fp(,)13 b(1996\).)0 909 y(The)19 b(third)g(ma)r(jor)f(concern)i(is)f (that)g(w)o(e)g(cannot)g(tak)o(e)g(the)g(real)g(trees)i(at)e(face)g(v)n (alue)f(either,)j(since)e(the)h(sequen)o(tial)0 959 y(algorithm)11 b(used)j(to)f(generate)i(the)f(tree)g(ma)o(y)e(not)h(b)q(e)h(an)f (e\016cien)o(t)h(searc)o(her)h(\(with)e(resp)q(ect)j(to)d(the)h(minim)o (al)c(tree)15 b(size\).)0 1009 y(This)f(could)f(b)q(e)h(caused)h(b)o(y) e(lea)o(ving)g(out)g(k)o(ey)h(mo)o(v)o(e)e(ordering)h(tec)o(hniques,)i (suc)o(h)f(as)g(a)f(su\016cien)o(tly)h(large)f(transp)q(osition)0 1059 y(table,)g(iterativ)o(e)g(deep)q(ening)h(or)f(killer)f(mo)o(v)o (es.)k(A)d(p)q(o)q(or)g(searc)o(her)i(will)d(yield)g(more)g(opp)q (ortunities)h(for)g(parallelism,)d(and)0 1108 y(ma)o(y)i(increase)j (the)g(sp)q(eedup)g(ac)o(hiev)o(ed)f(b)o(y)g(the)g(algorithm.)0 1187 y(The)h(fourth)f(concern)i(deals)f(with)f(the)h(v)n(aried)f(branc) o(hing)g(factor)h(of)e(the)i(game-trees)g(in)f(di\013eren)o(t)h(test)h (domains.)i(The)0 1237 y(a)o(v)o(erage)f(branc)o(hing)f(factor)g(in)h (c)o(hess)h(\(38\))e(is)g(higher)h(than)f(the)i(a)o(v)o(erage)e(branc)o (hing)h(factor)f(in)g(c)o(hec)o(k)o(ers)j(\(8)d(for)g(non-)0 1287 y(capture)h(p)q(ositions\).)25 b(T)m(aking)14 b(capture)j(p)q (ositions)f(in)o(to)g(accoun)o(t,)g(the)h(a)o(v)o(erage)f(branc)o(hing) g(factor)g(of)f(c)o(hec)o(k)o(ers)j(is)e(less)0 1337 y(than)f(3)g(\(Lu,)g(1993\).)21 b(The)15 b(breadth)h(of)e(c)o(hec)o(k)o (ers)j(trees)g(yield)e(sp)q(eedups)i(that)e(are)g(m)o(uc)o(h)f(smaller) g(in)h(magnitude)e(than)0 1386 y(the)h(same)f(algorithm)f(implem)o(en)o (ted)g(on)i(a)g(c)o(hess)h(program.)0 1465 y(The)h(\014nal)g(concern)h (deals)f(with)g(the)h(sp)q(eed)g(of)f(the)g(pro)q(cessor)i(v)o(ersus)f (the)g(sp)q(eed)h(of)d(the)i(net)o(w)o(ork.)24 b(If)16 b(the)h(algorithm)0 1515 y(w)o(as)i(tested)i(on)e(slo)o(w)g(pro)q (cessors)i(with)e(a)g(fast)g(net)o(w)o(ork)h(linking)d(them,)i(the)h (algorithm)d(ma)o(y)g(not)i(yield)g(the)h(same)0 1565 y(p)q(erformance)14 b(when)g(using)g(faster)g(pro)q(cessors)i(and/or)e (a)f(slo)o(w)o(er)h(net)o(w)o(ork.)0 1644 y(In)f(short,)g(it)g(is)g (nearly)g(imp)q(ossible)e(to)i(ob)r(jectiv)o(ely)g(compare)f(sp)q (eedups)j(or)e(e\016ciencies)i(for)d(the)i(di\013eren)o(t)g(implemen)o (ta-)0 1694 y(tions)g(giv)o(en)f(in)h(T)m(able)f(2.)0 1882 y Fl(2.3)48 b(Descriptio)o(ns)13 b(of)i(Earlier)f(Algorithms)f (\(1979-June)g(1987\))0 1998 y Fp(Baudet's)20 b(w)o(ork)f(\(1978\))g (describ)q(ed)i(a)e(metho)q(d)g(of)g(doing)f Fn(p)n(ar)n(al)r(lel)h (aspir)n(ation)h(se)n(ar)n(ch)p Fp(.)34 b(Aspiration)19 b(searc)o(h)i(can)e(b)q(e)0 2048 y(describ)q(ed)e(as)f(the)g(shrinking) f(of)g(the)h(initial)d Fk(\013\014)18 b Fp(windo)o(w)d(to)g(a)g(small)e (range.)23 b(If)15 b(the)h(minima)o(x)d(v)n(alue)h(lies)i(within)e(the) 0 2098 y(smaller)g(range,)i(the)h(correct)g(minima)o(x)c(v)n(alue)i (could)h(b)q(e)g(returned)i(while)d(visiting)g(less)h(leaf)g(no)q(des)g (than)g(w)o(ould)f(ha)o(v)o(e)0 2147 y(b)q(een)g(visited)f(b)o(y)g (using)f(the)i(larger)e(range.)0 2226 y(In)k(Baudet's)g(w)o(ork,)g(the) g(initial)e Fk(\013\014)k Fp(windo)o(w)d(is)h(sub)q(divided)g(in)o(to)f Fk(p)h Fp(disjoin)o(t)e(windo)o(ws,)i(where)h Fk(p)e Fp(is)h(the)g(n)o(um)o(b)q(er)g(of)0 2276 y(pro)q(cessors)h(used.)25 b(Eac)o(h)16 b(pro)q(cessor)i(searc)o(hes)g(the)f(game-tree)e(with)h (those)g(smaller)f(windo)o(ws.)24 b(When)16 b(a)f(pro)q(cessor)j(is)0 2326 y(\014nished,)e(it)f(can)h(use)g(the)h(result)f(of)f(the)h(searc)o (h)h(\(if)e(it)g(is)g(a)h(fail)e(lo)o(w)g(or)i(fail)e(high\))h(to)g (further)i(reduce)g(the)f(size)g(of)f(the)0 2376 y(windo)o(ws)c (examined.)16 b(Once)d(a)f(pro)q(cessor)i(determines)e(the)g(minim)o (ax)d(v)n(alue,)i(all)f(pro)q(cessors)k(are)f(stopp)q(ed)f(immediately) l(.)0 2455 y(Akl,)f(Barnard)g(and)g(Doran)f(\(1982\))g(w)o(ere)i(the)f (\014rst)h(to)f(prop)q(ose)g(and)g(sim)o(ulate)e(a)i Fn(mandatory)h(work)g(\014rst)e Fp(algorithm.)15 b(The)0 2504 y(idea)f(of)g(the)h(algorithm)d(is)i(to)g(explore)h(in)f(parallel) f(those)i(lea)o(v)o(es)g(that)f(w)o(ould)g(b)q(e)h(examined)e(if)h(the) h(tree)h(w)o(as)e(p)q(erfectly)0 2554 y(ordered.)19 b(There)c(are)f(t)o (w)o(o)g(categories)g(of)f(no)q(des)i(that)f(corresp)q(ond)h(to)f(the)g (cut)h(and)e(all)g(no)q(des)h(from)e(the)j(minim)o(al)10 b(tree.)0 2604 y(Left-hand)15 b(no)q(des)h(are)f(similar)d(to)j(all)f (no)q(des,)i(and)e(all)g(of)g(their)i(successors)h(are)f(ev)n(aluated)f (at)f(di\013eren)o(t)i(pro)q(cessors)h(in)0 2654 y(parallel.)23 b(Righ)o(t-hand)15 b(no)q(des)i(are)f(similar)e(to)i(cut)g(no)q(des,)h (and)f(only)g(one)g(successor)i(pro)q(cess)g(can)e(b)q(e)h(spa)o(wned)g (from)0 2704 y(them)c(at)h(a)f(time.)p eop %%Page: 6 6 6 5 bop 0 50 a Fp(6)603 b(ICCA)14 b(Journal)f(Submission)601 b(June)15 b(12,)e(1996)0 195 y(The)h(\014rst)h(branc)o(h)f(to)g(b)q(e)g (ev)n(aluated)g(from)e(a)i(righ)o(t-hand)f(no)q(de)h(migh)o(t)e (establish)i(a)f(score)j(that)d(signi\014es)h(a)g(cuto\013.)19 b(The)0 245 y(pro)q(cess)d(con)o(trolling)e(a)g(righ)o(t-hand)g(no)q (de)h(is)f(forced)h(to)g(stall)f(and)g(\014nd)h(out)f(the)h(v)n(alue)f (of)g(the)i(sibling)d(left-hand)h(no)q(de.)0 295 y(Once)20 b(this)f(sibling)f(left-hand)g(no)q(de)h(has)g(a)g(v)n(alue,)g(the)g(t) o(w)o(o)f(v)n(alues)h(are)g(compared)f(and)h(the)g(program)f (determines)0 345 y(whether)g(or)f(not)g(the)h(righ)o(t-hand)e(no)q(de) h(can)h(b)q(e)f(pruned)h(based)g(on)e(the)i(\014rst)g(branc)o(h)f(that) g(w)o(as)g(searc)o(hed.)29 b(If)17 b(there)0 394 y(is)e(no)f(cuto\013)i (y)o(et)f(for)f(the)i(righ)o(t-hand)e(no)q(de,)h(the)g(subsequen)o(t)i (branc)o(hes)f(in)e(the)i(righ)o(t-hand)e(no)q(de)h(are)g(examined)f (one)0 444 y(after)i(the)g(other)h(sequen)o(tially)m(.)22 b(This)16 b(will)e(stop)i(when)g(the)g(righ)o(t-hand)f(no)q(de)i(gets)f (pruned,)h(or)e(the)h(righ)o(t-hand)g(no)q(de)0 494 y(establishes)c(a)f (v)n(alue)f(higher)h(than)g(the)h(sibling)d(left-hand)i(no)q(de)g (after)g(exploring)g(all)e(branc)o(hes.)19 b(This)11 b(allo)o(ws)e(the)j(sc)o(heme)0 544 y(to)g(determine)f(most)g(of)g(the) i(direct)f(shallo)o(w)f(cuto\013s)h(that)g(w)o(ould)f(o)q(ccur)i(in)e (the)i(sequen)o(tial)f Fk(\013\014)i Fp(algorithm,)9 b(but)j(neglects)0 594 y(some)h(of)g(the)i(deep)g(cuto\013s)f(p)q (ossible.)0 672 y(Fink)o(el)k(and)h(Fish)o(burn)g(\(1982\))f(in)o(tro)q (duced)h(the)h(concept)g(of)e Fn(tr)n(e)n(e)g(splitting)p Fp(.)32 b(In)19 b(their)g(algorithm,)e(a)h(static)i(tree)g(of)0 722 y(pro)q(cessors)c(is)e(o)o(v)o(erlaid)f(on)g(top)h(of)g(a)f (game-tree.)18 b(The)c(ro)q(ot)g(of)g(the)g(game-tree)g(is)g(giv)o(en)f (to)h(the)g(ro)q(ot)g(of)g(the)g(pro)q(cessor)0 772 y(tree.)19 b(The)14 b(pro)q(cessor)h(ro)q(ot)f(generates)h(all)d(the)i(mo)o(v)o (es)e(at)i(ply)f(1)g(of)g(the)h(game-tree,)f(and)g(hands)h(them)e(o)o (v)o(er)i(to)f(the)h(\014rst)0 822 y(ply)h(of)f(the)i(pro)q(cessor)h (tree.)23 b(This)15 b(pro)q(cess)i(con)o(tin)o(ues)f(un)o(til)e(w)o(e)h (reac)o(h)h(the)g(lea)o(v)o(es)f(of)g(the)h(pro)q(cessor)h(tree,)f (where)g(the)0 872 y(pro)q(cessors)g(execute)f(the)g(sequen)o(tial)e Fk(\013\014)j Fp(algorithm)11 b(to)j(the)g(required)h(searc)o(h)f (depth.)19 b(The)14 b(no)q(des)h(in)e(the)h(\014rst)g Fk(k)h Fp(lev)o(els)0 922 y(of)c(the)i(tree,)g(where)g Fk(k)f Fp(is)g(the)g(depth)h(of)e(the)i(pro)q(cessor)g(tree,)g(can)f(b) q(e)h(ev)n(aluated)e(in)h(parallel.)k(The)c(only)f(sync)o(hronization)0 971 y(p)q(oin)o(t)i(o)q(ccurs)j(at)d(the)i(ro)q(ot)f(of)f(the)i(tree)g (b)q(et)o(w)o(een)g(searc)o(hes)h(at)e(di\013eren)o(t)g(depths.)0 1050 y(The)20 b Fn(PV-Split)f Fp(algorithm)e(\(Campb)q(ell,)h(1981;)j (Marsland)e(and)g(Campb)q(ell,)g(1982\))f(is)i(a)f(natural)g(extension) h(of)f(tree)0 1100 y(splitting,)12 b(based)i(on)g(the)g(regular)g (structure)h(of)e(the)h(minima)o(l)c(game-tree)k(as)f(w)o(e)h(tra)o(v)o (el)f(along)g(the)h(principal)f(v)n(ariation)0 1150 y(\(PV\).)19 b(The)g(\014rst)h(stage)f(of)g(the)g(algorithm)e(in)o(v)o(olv)o(es)h(a) g(recursiv)o(e)j(call)d(to)h(itself)f(as)h(it)g(tra)o(v)o(els)g(do)o (wn)f(the)i(principal)0 1200 y(v)n(ariation.)g(Once)c(the)g(left)f (subtree)i(of)d(a)h(PV)g(no)q(de)h(has)f(b)q(een)h(examined,)e(all)g (of)g(the)i(other)f(subtrees)j(b)q(elo)o(w)c(that)i(PV)0 1249 y(no)q(de)d(are)g(searc)o(hed)h(in)e(parallel)f(using)h(tree)i (splitting.)j(After)c(all)e(of)h(the)h(subtrees)i(ha)o(v)o(e)d(b)q(een) h(explored,)g(that)g(PV)g(no)q(de)0 1299 y(can)h(return)i(a)e(score)h (to)f(the)h(PV)f(no)q(de)h(ab)q(o)o(v)o(e)f(it.)k(A)o(t)c(an)o(y)g(one) h(time,)d(only)h(one)i(no)q(de's)f(subtrees)i(are)f(b)q(eing)f (examined)0 1349 y(in)f(parallel)g(b)o(y)h(the)g(PV-Split)g(algorithm.) 0 1428 y(In)e(the)h(original)e(implem)o(en)o(tation)e(\(Marsland)j(and) h(Campb)q(ell,)d(1982\),)h(the)i(PV-Split)f(algorithm)d(did)j(not)g (use)h(minima)o(l)0 1478 y(windo)o(ws)g(or)g(other)h(searc)o(h)h (enhancemen)o(t)e(tec)o(hniques)i(common)c(in)h(game-pla)o(ying)f (programs.)16 b(T)m(o)d(sim)o(ulate)e(these)k(or-)0 1528 y(dering)f(tec)o(hniques,)g(strongly-ordered)g(game-trees)g(w)o(ere)g (arti\014cially)e(created.)20 b(The)14 b(PV-Split)f(algorithm)e(w)o(as) i(sho)o(wn)0 1577 y(to)i(ha)o(v)o(e)h(a)f(b)q(etter)i(sp)q(eedup)g (than)f(tree)g(splitting)f(for)g(the)h(sim)o(ulated)e(strongly-ordered) i(trees.)25 b(There)17 b(are)f(n)o(umerous)0 1627 y(published)f(exp)q (erimen)o(ts)g(with)f(the)i(PV-Split)e(algorithm)e(\(Marsland)j(and)g (P)o(op)q(o)o(wic)o(h,)f(1985;)g(Newb)q(orn,)h(1985;)f(Mars-)0 1677 y(land,)h(Olafsson)h(and)g(Sc)o(hae\013er,)h(1985\).)23 b(The)16 b(b)q(est)h(rep)q(orted)h(e\016ciency)f(in)e(these)i(implemen) o(tations)c(w)o(as)j(a)f(sp)q(eedup)0 1727 y(of)f(3.75)g(on)h(5)g(pro)q (cessors)i(for)d(Marsland,)h(Olafsson)g(and)f(Sc)o(hae\013er)j (\(1985\).)j(The)c(ma)r(jor)d(problem)h(in)g(the)i(implemen-)0 1777 y(tation)g(of)g(PV-Split)g(is)h(a)f(large)g(sync)o(hronization)h (o)o(v)o(erhead,)g(since)g(man)o(y)e(pro)q(cessors)k(are)e(often)g (forced)g(to)f(w)o(ait)g(for)0 1826 y(long)d(p)q(erio)q(ds)i(of)f(time) e(while)i(the)h(last)f(unev)n(aluated)g(branc)o(h)g(of)g(a)g(PV)g(no)q (de)h(is)f(ev)n(aluated.)k(Newb)q(orn)d(suggested)h(that)0 1876 y(idle)f(pro)q(cessors)j(should)d(assist)h(those)g(pro)q(cessors)i (that)e(are)g(still)e(busy)i(b)o(y)g(creating)f(a)h(new)g(split)f(no)q (de)h(that)f(the)h(idle)0 1926 y(pro)q(cessors)g(can)e(w)o(ork)g(on)f (\(Newb)q(orn,)i(1985\).)0 2005 y(The)c Fn(Key)h(No)n(de)g Fp(metho)q(d)e(\(Lindstrom,)f(1983\))h(attempts)h(a)f(di\013eren)o(t)i (metho)q(d)e(for)h(attac)o(king)f(the)h(tree.)18 b(The)12 b(mandatory)0 2055 y(w)o(ork)g(\014rst)h(tree)g(is)f(dynamically)d(ev)o (olv)o(ed)j(and)g(stored)h(within)e(a)h(cen)o(tralized)h(message)f (queue.)18 b(Eac)o(h)13 b(pro)q(cessor)h(tak)o(es)e(a)0 2105 y(message)h(from)e(the)j(queue,)g(creates)h(new)f(messages)f (based)h(on)f(the)h(t)o(yp)q(e)g(of)e(message,)h(and)g(adds)g(the)h (information)d(in)o(to)0 2154 y(the)j(tree,)g(as)g(required.)k(F)m(or) 13 b(example,)f(if)h(a)g(message)g(is)g(sen)o(t)h(to)f(a)g(leaf)g(no)q (de)h(within)e(the)i(tree,)h(the)f(no)q(de)f(is)h(ev)n(aluated,)0 2204 y(and)h(the)h(v)n(alue)f(is)h(sen)o(t)g(to)g(the)g(paren)o(t.)23 b(A)o(t)16 b(t)o(yp)q(e)g(1)f(and)g(t)o(yp)q(e)h(3)g(no)q(des,)g (messages)g(for)f(eac)o(h)h(of)f(the)h(c)o(hildren)g(can)f(b)q(e)0 2254 y(sen)o(t)h(out)f(at)g(the)h(same)e(time)g(\(yielding)g(nearly)h (ideal)f(parallelism\).)20 b(Sync)o(hronization)15 b(o)q(ccurs)h(at)f (bad)g(t)o(yp)q(e)h(2)f(no)q(des,)0 2304 y(where)g(eac)o(h)f(mo)o(v)o (e)f(is)g(tried)i(in)e(turn)h(in)g(an)g(attempt)f(to)g(\014nd)h(the)h (cuto\013.)0 2383 y(The)j(Key)h(No)q(de)f(metho)q(d)f(w)o(as)h(sim)o (ulated)e(using)i(arti\014cial)f(trees,)j(where)f(the)f(score)i(of)d (the)h(paren)o(t)h(w)o(as)f(similar)d(to)0 2433 y(the)g(score)g(of)f (the)h(c)o(hildren.)k(The)c(metho)q(d)e(w)o(as)h(compared)g(against)f (the)i(classical)f Fk(\013\014)j Fp(algorithm.)f(In)e(the)h(sim)o (ulation,)0 2482 y(eac)o(h)f(message)f(w)o(as)h(assumed)f(to)g(b)q(e)h (pro)q(cessed)i(in)d(unit)g(time,)f(and)h(some)g(e\013orts)h(w)o(ere)h (made)d(to)h(sim)o(ulate)f(con)o(ten)o(tion)0 2532 y(for)j(the)g(no)q (des)h(within)e(the)h(tree.)22 b(Ov)o(er)16 b(10)e(test)i(runs,)g(the)f (Key)h(No)q(de)f(metho)q(d)f(ac)o(hiev)o(ed)h(a)g(sp)q(eedup)h(of)e (12.57)g(on)g(20)0 2582 y(pro)q(cessors,)i(using)d(a)h(tree)h(depth)g (of)e(5)g(and)h(a)g(breadth)g(of)g(4.)0 2661 y(Newb)q(orn's)f(\(1988\)) f(algorithm,)d Fn(Unsynchr)n(onize)n(d)15 b(Iter)n(atively)d(De)n(ep)n (ening)j(Par)n(al)r(lel)e(A)o(lpha-Beta)g(Se)n(ar)n(ch)p Fp(,)g(w)o(as)f(the)h(\014rst)p eop %%Page: 7 7 7 6 bop 467 50 a Fe(A)14 b(T)m(axonom)o(y)d(of)i(P)o(arallel)g(Game-T)m (ree)g(Searc)o(h)h(Algorithms)465 b Fp(7)0 195 y(attempt)13 b(to)g(async)o(hronously)h(start)g(the)g(next)g(lev)o(el)f(of)g(an)g (iterativ)o(ely)g(deep)q(ened)i(searc)o(h)g(instead)f(of)f(sync)o (hronizing)g(at)0 245 y(the)i(ro)q(ot)e(of)h(the)g(game-tree.)k(The)c (mo)o(v)o(es)f(from)f(the)j(ro)q(ot)f(p)q(osition)f(are)h(partitioned)g (among)d(the)k(pro)q(cessors,)h(and)d(the)0 295 y(pro)q(cessors)j (searc)o(h)g(their)e(o)o(wn)g(subset)h(of)f(the)h(mo)o(v)o(es)d(with)i (iterativ)o(e)g(deep)q(ening.)20 b(Eac)o(h)15 b(pro)q(cessor)g(is)f (giv)o(en)g(the)h(same)0 345 y(initial)e(windo)o(w,)g(but)h(some)g(of)g (the)h(pro)q(cessors)i(ma)o(y)12 b(ha)o(v)o(e)j(c)o(hanged)f(their)h (windo)o(ws,)f(based)h(on)f(the)h(searc)o(h)h(results)g(of)0 394 y(their)e(mo)o(v)o(es.)k(The)c(UIDP)m(ABS)h(algorithm)c(then)k(com) o(bines)e(the)i(results)g(once)g(a)f(predetermined)g(time)f(limit)f (has)i(b)q(een)0 444 y(reac)o(hed.)19 b(Some)11 b(of)g(the)i(mo)o(v)o (es)e(ma)o(y)f(ha)o(v)o(e)i(b)q(een)h(ev)n(aluated)f(to)g(larger)g (depths)h(than)f(those)h(on)f(other)h(pro)q(cessors,)h(whic)o(h)0 494 y(ma)o(y)e(yield)h(a)h(b)q(etter)h(qualit)o(y)e(mo)o(v)o(e)f(c)o (hoice.)0 573 y(Sc)o(hae\013er's)h Fn(Dynamic)h(PV-Split)e Fp(algorithm)d(\(1989\))i(is)h(an)f(enhancemen)o(t)i(that)f(allo)o(ws)e (for)i(dynamic)e(pro)q(cessor)k(trees)f(in)0 623 y(the)f(PV-Split)e (framew)o(ork.)16 b(Instead)c(of)e(the)i(\014xed)f(pro)q(cessor)i(tree) g(mec)o(hanism)8 b(that)j(w)o(as)g(used)h(in)f(PV-Split,)g(pro)q (cessors)0 672 y(in)h(Dynamic)f(PV-Split)h(\(DPVS\))h(are)h(allo)o(w)o (ed)d(to)i(dynamically)c(attac)o(h)k(themselv)o(es)g(to)g(other)g(busy) g(pro)q(cessors,)i(whic)o(h)0 722 y(eac)o(h)21 b(run)g(the)g(PV-Split)e (algorithm.)35 b(This)20 b(allo)o(ws)g(for)g(parallelism)d(along)i(the) i(pseudo-principal)f(v)n(ariation)f(\(the)0 772 y(leftmost)g(branc)o (h\))i(b)q(eing)f(searc)o(hed)h(b)o(y)f(an)o(y)g(pro)q(cessor,)j(and)d (allo)o(ws)f(for)h(m)o(ultiple)e(split)h(no)q(des.)38 b(The)21 b(pro)q(cess)h(of)0 822 y(c)o(ho)q(osing)11 b(the)i(new)f(split)f(no)q(de)h(started)h(b)o(y)e(allo)q(cating)f (branc)o(hes)j(at)f(t)o(yp)q(e)g(1)f(or)h(t)o(yp)q(e)g(3)f(no)q(des,)i (and)e(allo)o(w)o(ed)g(parallelism)0 872 y(at)k(t)o(yp)q(e)h(2)f(no)q (des)h(once)g(the)g(branc)o(hes)h(from)d(all)g(t)o(yp)q(e)i(1)f(and)g (3)g(no)q(des)h(w)o(ere)h(allo)q(cated.)22 b(All)14 b(requests)k(for)d (w)o(ork)g(w)o(en)o(t)0 922 y(through)e(a)g(Con)o(troller)f(pro)q (cess,)i(whic)o(h)f(w)o(as)g(used)h(to)e(balance)h(the)h(dynamic)d(pro) q(cessor)k(tree)f(amongst)d(the)j(pro)q(cessors)0 971 y(that)g(had)g(the)g(most)f(w)o(ork)g(to)h(do,)f(as)h(w)o(ell)f(as)h (assign)g(w)o(ork)g(from)e(the)i(curren)o(t)i(no)q(de)e(on)g(the)g (principal)f(v)n(ariation.)0 1050 y(Unfortunately)m(,)j(the)h(increase) h(in)d(searc)o(h)j(o)o(v)o(erhead)f(comp)q(ensated)f(for)g(the)h (decrease)i(in)d(sync)o(hronization)g(o)o(v)o(erhead.)0 1100 y(The)e(searc)o(h)h(o)o(v)o(erhead)g(arose)f(from)e(additional)g (pro)q(cessors,)k(once)e(they)h(had)e(b)q(een)i(reassigned,)g (attempting)d(to)i(searc)o(h)0 1150 y(some)c(subtrees)i(without)f(the)g (b)q(ene\014t)h(of)d(the)j(ordering)e(information)e(from)h(the)i(searc) o(hed)h(sibling)d(subtrees.)19 b(By)11 b(allo)o(wing)0 1200 y(a)f(shared)h(T)m(able)f(Manager)g(to)g(handle)g(all)f(transp)q (osition)h(table)g(requests,)j(along)c(with)h(a)g(mec)o(hanism)d(for)j (rebroadcasting)0 1249 y(history)19 b(table)h(information,)d(the)j(sp)q (eedup)h(for)e Fc(P)l(araPhoenix)j Fp(w)o(as)d(impro)o(v)o(ed)f(to)h (7.64)g(on)g(19)g(pro)q(cessors.)37 b(The)0 1299 y(mec)o(hanism)12 b(describ)q(ed)k(in)e(the)h(pap)q(er)g(tap)q(ered)h(o\013)e(once)h (more)f(than)g(10)g(pro)q(cessors)j(w)o(ere)e(in)o(v)o(olv)o(ed;)e(the) i(o)o(v)o(erhead)g(of)0 1349 y(going)e(through)h(a)f(single)h(T)m(able) f(Manager)h(increased)h(linearly)e(as)h(more)f(pro)q(cessors)j(w)o(ere) f(added.)0 1428 y(The)c Fn(Enhanc)n(e)n(d)i(PV-Split)d Fp(algorithm)e(\(Hy)o(att,)i(1988;)g(Hy)o(att,)h(Suter)g(and)g(Nelson,) g(1989\))e(is)h(a)g(di\013eren)o(t)i(t)o(yp)q(e)f(of)f(dynamic)0 1478 y(allo)q(cation)f(to)h(the)h(PV-Split)f(algorithm.)k(In)d(the)g (Enhanced)g(PV-Split)f(\(EPVS\))i(algorithm,)c(when)j(a)f(pro)q(cessor) i(b)q(ecame)0 1528 y(idle,)j(all)e(of)i(the)h(other)g(pro)q(cessors)h (w)o(ere)f(stopp)q(ed)g(and)f(a)g(new)h(split)f(no)q(de)g(w)o(ould)f(b) q(e)i(created)h(t)o(w)o(o)e(ply)f(further)i(do)o(wn)0 1577 y(the)f(tree)g(of)e(one)h(of)g(the)g(busy)g(pro)q(cessors.)21 b(All)13 b(pro)q(cessors)j(w)o(ould)d(then)i(start)f(to)g(w)o(ork)g(on) g(the)g(smaller)f(subtree.)20 b(The)0 1627 y(transp)q(osition)14 b(table)g(ensured)h(that)f(the)h(smaller)d(subtree)k(had)d(not)h(b)q (een)h(explored)f(y)o(et.)0 1706 y(Using)i(a)g(Sequen)o(t)h(Balance)f (21000)f(computer,)h(the)h(sp)q(eedup)g(of)f(EPVS)h(w)o(as)f(5.93)e(on) i(16)g(pro)q(cessors.)27 b(On)16 b(the)h(same)0 1756 y(mac)o(hine)d(and)h(test)h(set,)g(PV-Split)f(ac)o(hiev)o(ed)g(a)g(sp)q (eedup)i(of)e(4.57)f(on)h(16)f(pro)q(cessors.)24 b(The)16 b(authors)g(p)q(oin)o(t)e(out)h(at)g(the)0 1806 y(end)e(of)f(their)h (pap)q(er)g(that)f(the)h(a)o(v)o(erage)g(branc)o(hing)f(factor)h(of)e (a)i(c)o(hess)h(tree)f(is)g(38;)e(their)i(algorithm)d(could)i(not)h (use)g(64)f(or)0 1856 y(more)g(pro)q(cessors)j(e\013ectiv)o(ely)f (since)g(all)e(pro)q(cessors)j(co-ordinate)e(at)g(one)h(split)e(no)q (de)i(at)f(an)o(y)f(giv)o(en)h(time.)j(Th)o(us,)d(to)g(use)0 1905 y(massiv)o(ely)e(parallel)h(arc)o(hitectures)k(\(with)d(h)o (undreds)h(or)f(thousands)h(of)f(pro)q(cessors\),)i(a)e(greater)h(n)o (um)o(b)q(er)f(of)f(split)h(no)q(des)0 1955 y(m)o(ust)g(b)q(e)h(a)o(v)n (ailable)e(for)i(parallel)e(w)o(ork.)0 2116 y Fl(2.4)48 b(The)15 b(Adv)o(en)o(t)f(Of)i(Massiv)o(e)f(P)o(aralleli)o(sm)e(\(July) h(1987-presen)o(t\))0 2226 y Fp(F)m(elten)19 b(and)g(Otto)h(\(1988\))e (implemen)o(ted)f(the)j(\014rst)g(parallel)e Fk(\013\014)j Fp(algorithm)c(that)i(pla)o(y)o(ed)g(c)o(hess)h(on)f(more)f(than)h(32)0 2276 y(pro)q(cessors.)k(Their)15 b Fc(W)-5 b(a)m(yCool)17 b Fp(program)c(decided)j(on)f(the)h(t)o(yp)q(e)f(of)f(parallelism)e(to) j(b)q(e)h(applied)e(at)h(a)f(no)q(de)i(based)f(on)0 2326 y(whether)f(there)f(w)o(as)f(a)h(transp)q(osition)f(table)g(en)o(try)h (in)f(the)h(system.)k(If)12 b(a)g(transp)q(osition)g(table)g(en)o(try)h (w)o(as)f(a)o(v)n(ailable,)e(the)0 2376 y(mo)o(v)o(e)j(stored)i(w)o (ould)e(lik)o(ely)g(b)q(e)i(the)g(b)q(est)g(mo)o(v)o(e,)e(and)h(it)g(w) o(as)g(w)o(orth)g(w)o(aiting)f(for)h(a)g(b)q(ound)g(to)h(b)q(e)f (returned)i(from)d(that)0 2425 y(transp)q(osition)h(table)g(mo)o(v)o (e.)j(Once)f(that)e(b)q(ound)g(had)g(b)q(een)h(returned)h(\(assuming)d (that)h(the)h(no)q(de)f(is)g(not)g(immediately)0 2475 y(pruned\),)d(all)d(of)h(the)i(other)f(successors)i(could)e(b)q(e)g (explored)g(in)f(parallel.)15 b(If)10 b(there)h(is)e(no)g(transp)q (osition)h(table)f(information,)0 2525 y(all)k(subtrees)j(could)d(b)q (e)i(computed)e(in)h(parallel.)0 2604 y(The)f(pro)q(cessors)h(are)f (hierarc)o(hically)e(organized)h(in)o(to)g(a)g(tree)h(structure)h(at)e (the)h(start)g(of)f(the)g(searc)o(h,)h(but)g(this)f(pro)q(cessor)0 2654 y(tree)19 b(w)o(ould)e(b)q(e)h(restructured)j(as)c(necessary)m(.) 31 b(The)18 b(sc)o(heme)g(relied)g(on)g(a)f(globally)e(shared)k(transp) q(osition)f(table)f(and)0 2704 y(a)f(load)f(balancing)g(sc)o(heme)i (that)f(is)g(similar)e(to)i(the)g(one)h(used)g(in)f(EPVS.)g(The)h(load) e(balancing)g(sc)o(heme)h(reorganized)p eop %%Page: 8 8 8 7 bop 0 50 a Fp(8)603 b(ICCA)14 b(Journal)f(Submission)601 b(June)15 b(12,)e(1996)0 195 y(searc)o(hers)j(in)o(to)d(new)i(teams)e (that)h(searc)o(h)h(a)e(\\hot)h(sp)q(ot")g(in)f(parallel.)0 274 y(F)m(eldmann)8 b Fn(et.)17 b(al)k Fp(implem)o(en)o(ted)8 b(a)h(parallel)g Fk(\013\014)j Fp(algorithm)7 b(on)i(a)h(large)f(net)o (w)o(ork)h(of)f(T)m(ransputers)i(for)e(the)h(c)o(hess)i(program)0 324 y Fc(Zugzw)l(ang)g Fp(\(V)m(orn)o(b)q(erger)g(and)g(Monien,)f (1987;)g(F)m(eldmann)e Fn(et.)18 b(al)p Fp(,)11 b(1989;)g(F)m(eldmann,) f(1993\).)16 b(The)c(algorithm)d(in)o(v)o(olv)o(es)0 374 y(the)j(use)g(of)e(the)i Fn(Y)m(oung)h(Br)n(others)e(Wait)i(Conc)n (ept)e Fp(\(YBW)o(C\))h(to)f(determine)g(when)g(no)q(des)h(can)f(b)q(e) h(giv)o(en)f(out)g(in)f(a)h(parallel)0 423 y(manner.)0 502 y(In)19 b(a)g(game-tree)g(that)g(has)h(near)f(p)q(erfect)i (ordering,)f(there)h(is)e(a)g(high)g(probabilit)o(y)e(that)i(a)g(no)q (de)h(is)f(an)g(all)f(no)q(de)i(if)0 552 y(w)o(e)e(ev)n(aluate)g(the)h (leftmost)d(branc)o(h)j(and)f(w)o(e)g(ha)o(v)o(e)g(not)g(pruned)h(the)f (searc)o(h)h(b)q(elo)o(w)f(that)g(no)q(de.)31 b(The)19 b(basic)f(Y)m(oung)0 602 y(Brothers)g(W)m(ait)c(Concept)j(states)h (that)e(the)h(leftmost)d(branc)o(h)j(\(the)g(eldest)g(brother\))g(m)o (ust)e(b)q(e)i(ev)n(aluated)f(b)q(efore)g(an)o(y)0 652 y(other)c(branc)o(hes)h(\(the)g(y)o(oung)e(brothers\))i(can)f(b)q(e)g (distributed)g(to)g(other)g(pro)q(cessors.)19 b(This)12 b(is)f(not)h(necessarily)h(limited)c(to)0 702 y(the)15 b(principal)f(v)n(ariation)f(\(i.e.)20 b(PV-Split\))14 b(or)h(a)f(pseudo-principal)h(v)n(ariation)e(\(i.e.)20 b(DPVS)15 b(or)f(EPVS\);)h(it)g(can)f(happ)q(en)0 751 y(at)h(an)o(y)g(no)q(de)g(within)g(the)g(game-tree.)22 b(The)15 b(algorithm)e(giv)o(en)h(in)h(T)m(ables)g(1)g(and)f(2)h(is)g (YBW)o(C*.)22 b(This)15 b(v)n(ariation)e(do)q(es)0 801 y(not)j(w)o(ait)f(for)h(y)o(oung)g(brothers)h(at)f(t)o(yp)q(e)h(3)f(no) q(des)h(and)f(forces)h(sequen)o(tial)f(ev)n(aluation)f(of)g(all)g (\\reasonable")h(mo)o(v)o(es)f(at)0 851 y(t)o(yp)q(e)f(2)g(no)q(des,)g (as)g(describ)q(ed)i(in)d(F)m(eldmann's)f(Ph.D.)h(thesis)i(\(1993\).)0 930 y(Hy)o(att)f(in)o(tro)q(duced)g Fn(Dynamic)i(T)m(r)n(e)n(e)e (Splitting)f Fp(\(DTS\))h(in)f(his)h(Ph.D.)f(thesis)h(\(1988\).)j(One)e (pro)q(cessor)h(is)d(giv)o(en)h(the)g(ro)q(ot)0 980 y(p)q(osition)h (and)g(the)h(others)g(m)o(ust)f(try)h(to)f(\014nd)g(a)h(pro)q(cessor)h (that)e(has)h(w)o(ork)f(to)g(steal.)23 b(If)15 b(a)g(pro)q(cessor)j (has)d(w)o(ork,)g(DTS)0 1029 y(hands)k(out)f(a)h(branc)o(h)g(from)d (the)k(lo)o(w)o(est)e(t)o(yp)q(e)h(3)f(no)q(de.)33 b(T)o(yp)q(e)19 b(1)f(no)q(des)h(that)g(ha)o(v)o(e)f(b)q(ound)h(information)d(\(i.e.)31 b(the)0 1079 y(leftmost)13 b(c)o(hild)h(has)g(b)q(een)h(ev)n(aluated\)) f(are)h(considered)h(as)e(t)o(yp)q(e)h(3)f(no)q(des.)19 b(F)m(ailing)12 b(this,)i(the)h(pro)q(cessor)h(will)d(hand)h(out)0 1129 y(an)o(y)f(no)q(de)h(from)e(a)i(t)o(yp)q(e)g(1)f(no)q(de)h(that)g (do)q(es)g(not)g(ha)o(v)o(e)f(an)o(y)h(b)q(ound)f(information.)i (Finally)m(,)c(the)k(pro)q(cessor)g(w)o(ould)e(hand)0 1179 y(out)e(branc)o(hes)h(from)d(t)o(yp)q(e)i(2)f(no)q(des)i(that)f (ha)o(v)o(e)f(not)h(b)q(een)h(pruned)f(after)g(the)h(\014rst)f(c)o (hild)f(has)h(b)q(een)h(completely)e(ev)n(aluated.)0 1229 y(This)17 b(mak)o(es)f(the)i(algorithm)d(similar)g(\(in)h (parallelization)g(and)h(sync)o(hronization)g(c)o(haracteristics\))i (to)e(YBW)o(C*,)h(but)0 1279 y(allo)q(cates)c(the)g(w)o(ork)g(in)f(a)h (di\013eren)o(t)h(order)f(than)g(YBW)o(C*)g(w)o(ould.)0 1357 y(In)c(the)g(implemen)o(tation,)d(split)i(p)q(oin)o(ts)h(w)o(ere)g (placed)g(in)f(shared)i(memory)c(so)j(that)g(other)g(pro)q(cessors)i (had)e(an)f(opp)q(ortunit)o(y)0 1407 y(to)16 b(tak)o(e)g(branc)o(hes)h (without)f(a)g(pro)q(cessor)h(con)o(tin)o(ually)e(lo)q(oking)f(for)i(w) o(ork)g(to)g(do.)24 b(Using)16 b(a)f(Sequen)o(t)i(Balance)g(21000,)0 1457 y(DTS)d(generated)h(an)e(a)o(v)o(erage)h(sp)q(eed-up)i(of)d(8.81)g (o)o(v)o(er)g(16)h(pro)q(cessors.)0 1536 y Fn(Bound-and-Br)n(anch)f Fp(\(F)m(erguson)e(and)g(Korf,)g(1988\))e(is)i(a)f(pro)q(cessor)j(allo) q(cation)c(sc)o(heme)i(in)f(the)i(Distributed)f(T)m(ree)g(Searc)o(h)0 1586 y(framew)o(ork)d({)i(a)g(general)g(framew)o(ork)e(for)i (distributed)h(searc)o(h)g({)f(to)f(searc)o(h)j Fk(\013\014)g Fp(trees)f(generated)h(b)o(y)e(an)f(Othello)h(program.)0 1636 y(If)k(no)h(cuto\013)g(b)q(ound)g(exists)g(at)f(a)h(no)q(de,)g (all)e(pro)q(cessors)k(are)e(assigned)g(to)f(the)h(\014rst)h(c)o(hild)e (to)g(generate)i(a)f(cuto\013)g(b)q(ound)0 1685 y(as)j(quic)o(kly)f(as) h(p)q(ossible.)29 b(If)18 b(a)f(cuto\013)i(b)q(ound)e(exists,)i(or)f (has)g(b)q(een)h(established)f(b)o(y)g(completing)e(the)i(searc)o(h)h (of)e(the)0 1735 y(\014rst)e(c)o(hild,)f(the)h(pro)q(cessors)h(are)f (allo)q(cated)f(in)g(a)g(breadth-\014rst)i(manner)d(to)h(all)g (remaining)e(c)o(hildren.)20 b(E\013ectiv)o(ely)m(,)14 b(this)0 1785 y(sc)o(heme)f(giv)o(es)g(the)g(same)f(parallelism)e(and)j (sync)o(hronization)g(pattern)h(describ)q(ed)g(in)f(the)g(YBW)o(C*)g (algorithm.)i(F)m(or)d(the)0 1835 y(Bound-and-Branc)o(h)f(pro)q(cessor) h(allo)q(cation)d(sc)o(heme,)h(F)m(erguson)h(and)f(Korf)g(get)h(sp)q (eedups)h(of)e(12)f(while)h(studying)g(Othello)0 1885 y(trees)16 b(using)e(a)h(32-pro)q(cessor)g(h)o(yp)q(ercub)q(e.)22 b(The)15 b(searc)o(h)h(is)e(facilitated)g(b)o(y)g(a)h(distributed)g (\\game-tree)f(represen)o(tation")0 1934 y(whic)o(h)g(is)g(similar)d (to)j(a)f(transp)q(osition)h(table,)f(and)h(iterativ)o(e)g(deep)q (ening.)0 2013 y(Hsu)i(describ)q(ed)h(a)e Fn(queue)n(d)i(pr)n(o)n(c)n (essor)f(arr)n(ay)g(mo)n(del)f Fp(for)g(implemen)o(ting)d(a)j(parallel) g Fk(\013\014)i Fp(algorithm)c(within)i(the)h(second)0 2063 y(v)o(ersion)g(of)f(Deep)h(Though)o(t)f(\(1990\).)23 b(The)16 b(host)g(w)o(orkstation)f(tra)o(v)o(erses)i(the)g(tree)f (according)g(to)g(the)g(algorithm)d(un)o(til)0 2113 y(the)h (parallelization)e(horizon)i(is)f(reac)o(hed.)20 b(The)14 b(subproblems)f(are)i(then)f(placed)g(on)g(to)f(a)h(queue)g(that)g(can) g(b)q(e)h(accessed)0 2163 y(b)o(y)g(a)h(large)f(n)o(um)o(b)q(er)g(of)g (sp)q(ecialized)h(VLSI)g(pro)q(cessors.)25 b(All)15 b(of)g(the)h(pro)q (cessors)i(are)e(connected)h(b)o(y)e(the)h(same)f(bus)h(to)0 2213 y(this)i(queue.)31 b(The)18 b(pro)q(cessors)i(tak)o(e)e(a)o(w)o(a) o(y)f(the)i(subproblems)e(placed)h(on)g(the)g(queue,)i(run)e(the)g (silicon-enco)q(ded)h Fk(\013\014)0 2262 y Fp(routine)c(on)f(the)i(c)o (hip,)e(and)h(return)h(the)f(results)h(to)f(another)g(queue)g(on)g(the) g(bus)g(that)g(go)q(es)g(in)g(to)f(the)i(host)f(pro)q(cessor.)0 2312 y(The)f(results)h(are)g(then)f(added)g(to)g(the)h(tree)g(represen) o(tation)g(in)f(the)g(host)g(computer.)0 2391 y(Hsu)i(also)f(in)o(tro)q (duced)h(the)g Fn(delaye)n(d)h(br)n(anch)g(tr)n(e)n(e)e(exp)n(ansion)i Fp(\(DBTE\))f(algorithms)d(in)i(his)h(thesis.)23 b(These)17 b(algorithms)0 2441 y(generate)f(t)o(w)o(o)e(queues)i(of)e(no)q(des.)20 b(The)15 b(\014rst)h(queue)f(is)g(a)f(set)h(of)f(no)q(des)i(that)e (corresp)q(ond)i(to)f(the)g Fk(\013\014)i Fp(minim)o(al)11 b(tree,)k(in)0 2491 y(a)e(left-to-righ)o(t)f(order.)19 b(The)14 b(second)g(queue)g(con)o(tains)f(no)q(des)h(that)g(are)g(not)f (in)g(the)g Fk(\013\014)j Fp(minim)o(al)10 b(tree,)k(b)q(ecause)h(of)e (p)q(o)q(or)0 2540 y(mo)o(v)o(e)g(ordering)h(at)g(t)o(yp)q(e)h(2)f(no)q (des.)21 b(The)15 b(minim)o(al)c(tree)k(queue)g(is)g(used)g(only)f (when)g(the)h(queue)h(of)d(additional)g(w)o(ork)h(at)0 2590 y(failed)f(t)o(yp)q(e)h(2)g(no)q(des)h(is)e(empt)o(y)m(.)k(This)d (setup)h(allo)o(ws)d(for)i(parallelism)d(at)j(t)o(yp)q(e)g(1)g(and)f(3) h(no)q(des.)0 2669 y(There)d(is)g(a)f(family)d(of)j(DBTE)g(algorithms)e (based)j(on)f(the)h(c)o(hoice)g(of)f(CUT)g(no)q(des)h(to)f(re-expand.) 18 b(One)11 b(of)f(the)h(algorithms,)p eop %%Page: 9 9 9 8 bop 467 50 a Fe(A)14 b(T)m(axonom)o(y)d(of)i(P)o(arallel)g(Game-T)m (ree)g(Searc)o(h)h(Algorithms)465 b Fp(9)0 195 y(the)13 b(Leftmost)e(First)h(algorithm,)e(is)i(sho)o(wn)g(to)g(b)q(e)g (asymptotically)e(optimal)f(on)j(b)q(est-\014rst)i(trees)g(as)e(w)o (ell)g(as)g(dominating)0 245 y(w)o(eak)f Fk(\013\014)i Fp(\(a)e(v)o(ersion)h(of)e(the)i Fk(\013\014)h Fp(algorithm)c(whic)o(h) h(only)h(has)g(shallo)o(w)f(cuto\013s\).)18 b(The)12 b(Leftmost)e(First)h(algorithm)e(causes)0 295 y(sync)o(hronization)j (to)f(o)q(ccur)i(at)e(bad)g(t)o(yp)q(e)h(2)g(no)q(des.)18 b(Sim)o(ulations)9 b(rep)q(ort)j(that)g(a)f(sp)q(eedup)i(of)e(350)g (with)g(1000)g(pro)q(cessors)0 345 y(is)j(p)q(ossible,)f(once)i(the)f (mac)o(hine)f(is)h(completely)e(constructed.)0 423 y(Lu)19 b(\(1993\))g(implemen)o(ted)e(a)i(pair)g(of)g(impro)o(v)o(emen)o(ts)e (to)i(the)i(basic)e(PV-Split)g(algorithm)e(for)i(use)h(in)f(the)h(c)o (hec)o(k)o(ers)0 473 y(program)13 b Fc(Chinook)p Fp(.)21 b(T)m(o)14 b(prev)o(en)o(t)i(starv)n(ation)e(when)h(exploring)f(c)o (hec)o(k)o(ers)i(trees,)g(whic)o(h)f(ha)o(v)o(e)f(an)h(a)o(v)o(erage)f (branc)o(hing)0 523 y(factor)d(of)g(3)g(instead)h(of)f(the)h(38)e (found)h(in)g(c)o(hess)i(trees,)g Fn(fr)n(ontier)f(splitting)e Fp(w)o(as)h(prop)q(osed)i(and)e(tested.)19 b(F)m(ron)o(tier)11 b(splitting)0 573 y(creates)18 b(m)o(ultiple)d(split)h(no)q(des)h (further)h(up)f(the)g(v)n(ariation)e(b)q(eing)h(explored)h(b)o(y)g(the) g(Con)o(troller)f(pro)q(cess)j(as)d(they)i(are)0 623 y(required.)33 b(This)18 b(is)h(di\013eren)o(t)g(than)f(algorithms)f (lik)o(e)g(YBW)o(C*,)i(whic)o(h)g(concen)o(trate)h(on)e(creating)h(new) g(split)f(no)q(des)0 672 y(underneath)g(the)g(curren)o(t)g(split)e(no)q (de.)28 b(Split)16 b(no)q(des)i(are)f(created)h(\014rst)g(at)f(all)e (no)q(des)j(and)f(only)f(at)g(cut)i(no)q(des)f(when)0 722 y(there)e(is)g(no)e(parallelism)f(left)i(at)g(an)o(y)g(all)f(no)q (des.)19 b(The)c(dra)o(wbac)o(k)f(is)g(that)g(the)h(searc)o(h)g(migh)o (t)d(b)q(e)j(started)h(without)d(an)o(y)0 772 y(b)q(ound)j (information.)23 b(Essen)o(tially)m(,)15 b(this)i(remo)o(v)o(es)f(the)g (sync)o(hronization)h(for)f(a)g(giv)o(en)g(depth)h(searc)o(h,)g(and)f (allo)o(ws)f(for)0 822 y(parallelism)c(at)j(an)o(y)f(no)q(de)i(within)e (the)h(tree.)0 901 y(An)h(implemen)o(tati)o(on)d(of)i(dynamic)f(load)h (balancing,)f(similar)f(to)j(the)g(EPVS)g(metho)q(d,)f(w)o(as)g(also)g (presen)o(ted.)23 b Fn(Str)n(aggler)0 951 y(pr)n(e)n(emption)13 b Fp(gathers)g(a)f(group)h(of)f(idle)g(pro)q(cessors)j(and)e(assigns)f (them)g(to)h(a)f(subtree)j(that)d(has)h(b)q(een)h(w)o(ork)o(ed)f(on)f (b)o(y)h(one)0 1000 y(pro)q(cessor)j(for)f(a)f(long)f(p)q(erio)q(d)i (of)f(time.)19 b(Both)c(of)f(the)h(impro)o(v)o(em)o(en)o(ts)e(w)o(ere)i (tested)h(and)f(the)g(sp)q(eedup)h(on)e(the)h(test)h(set)0 1050 y(impro)o(v)o(ed)11 b(from)g(1.92)h(on)h(16)f(pro)q(cessors)k(for) c(the)i(basic)f(PV-Split)f(algorithm)f(to)i(3.31)e(on)i(16)g(pro)q (cessors.)20 b(The)13 b(a)o(v)o(erage)0 1100 y(branc)o(hing)f(factor)h (of)f(the)h(trees)h(b)q(eing)f(explored)g(w)o(as)f(2.78;)g(although)f (the)j(magnitude)d(of)h(the)h(increase)h(w)o(as)e(small,)e(the)0 1150 y(fact)k(that)g(the)g(sp)q(eedup)i(is)e(larger)f(than)h(the)h (branc)o(hing)e(factor)h(is)g(signi\014can)o(t.)0 1229 y(Da)o(vid's)d Fk(\013\014)r Fp(*)i(\(1993\))f(is)g(a)h(new)g(t)o(yp)q (e)g(of)f(arc)o(hitecture)i(for)f(dealing)e(whic)o(h)i(requires)h(a)e (shared)i(transp)q(osition)e(table.)18 b(All)0 1279 y(pro)q(cessors)f (start)e(at)g(the)g(ro)q(ot)g(of)f(the)i(tree)g(and)e(start)h(tra)o(v)o (elling)f(do)o(wn)g(the)i(tree.)21 b(Ho)o(w)o(ev)o(er,)15 b(the)h(pro)q(cessors)h(explore)0 1328 y(di\013eren)o(t)12 b(parts)g(of)f(the)g(tree)i(based)f(on)f(results)h(from)d(the)j(shared) g(transp)q(osition)g(table.)17 b(Eac)o(h)11 b(en)o(try)h(con)o(tains)f (a)g(coun)o(ter)0 1378 y(of)17 b(ho)o(w)f(man)o(y)g(pro)q(cessors)j (are)e(exploring)g(the)h(subtree)h(ro)q(oted)e(at)g(that)g(no)q(de.)29 b(Th)o(us,)17 b(the)h(pro)q(cessor)h(can)f(disco)o(v)o(er)0 1428 y(whic)o(h)c(no)q(des)g(ha)o(v)o(e)g(b)q(een)h(ev)n(aluated.)0 1507 y(A)h(depth-limited)f(searc)o(h)i(is)f(executed)i(at)d(non-PV)i (no)q(des)f(to)g(determine)g(whether)i(the)e(no)q(de)h(is)f(a)f(t)o(yp) q(e)i(2)f(or)g(a)f(t)o(yp)q(e)0 1557 y(3)i(no)q(de.)27 b(T)o(yp)q(e)17 b(2)g(no)q(des)g(are)g(searc)o(hed)i(sequen)o(tially)m (,)d(as)h(in)f(other)i(algorithms.)24 b(A)o(t)17 b(t)o(yp)q(e)h(3)e(no) q(des,)i(the)f(n)o(um)o(b)q(er)g(of)0 1606 y(pro)q(cessors)g(allo)o(w)o (ed)c(to)h(explore)g(a)g(subtree)i(is)f(limited)d(b)o(y)i(a)g(constan)o (t)h(factor)f(of)g(the)g(n)o(um)o(b)q(er)g(of)g(pro)q(cessors)i(that)f (are)0 1656 y(curren)o(tly)i(at)f(the)g(t)o(yp)q(e)g(3)g(no)q(de.)24 b(F)m(or)16 b(the)g(purp)q(oses)i(of)d Fk(\013\014)r Fp(*,)h(once)g(the)h(leftmost)d(c)o(hild)i(of)f(a)h(t)o(yp)q(e)g(1)g (no)q(de)g(has)g(b)q(een)0 1706 y(ev)n(aluated,)e(the)i(t)o(yp)q(e)f(1) g(no)q(de)g(e\013ectiv)o(ely)h(b)q(ecomes)f(a)g(t)o(yp)q(e)g(3)g(no)q (de.)21 b(Once)16 b(a)f(pro)q(cessor)i(has)e(visited)g(a)f(no)q(de,)h (it)g(ma)o(y)0 1756 y(not)h(go)g(bac)o(k)h(ab)q(o)o(v)o(e)f(that)h(no)q (de)f(un)o(til)g(the)h(no)q(de)g(is)f(ev)n(aluated)h(\(i.e.)25 b(the)17 b(correct)h Fk(\013\014)h Fp(information)14 b(is)i(kno)o(wn)g(ab)q(out)0 1806 y(the)g(v)n(alue)f(at)g(that)g(no)q (de\).)24 b(This)15 b(means)f(that)i(as)f(so)q(on)h(as)f(one)h(pro)q (cessor)h(has)f(\\ev)n(aluated")e(the)i(ro)q(ot,)g(the)g(searc)o(h)g (is)0 1856 y(completed.)h(One)c(adv)n(an)o(tage)e(of)h(the)g Fk(\013\014)r Fp(*)h(algorithm)c(is)j(the)h(parallel)e(co)q(de)i(in)o (v)o(olv)o(es)e(only)g(a)h(small)e(n)o(um)o(b)q(er)i(of)f(c)o(hanges)0 1905 y(to)16 b(the)h(sequen)o(tial)f(co)q(de)h(\(W)m(eill,)e(1995\).)24 b(In)16 b(his)h(thesis,)g(Da)o(vid)e(ac)o(hiev)o(ed)h(a)g(sp)q(eedup)i (of)e(6.5)f(on)h(16)g(T)m(ransputers.)26 b(8)0 1955 y(of)14 b(the)i(T)m(ransputers)g(w)o(ere)f(used)h(to)f(con)o(trol)f(the)i (shared)g(transp)q(osition)e(table,)h(while)f(the)h(other)h(8)e(w)o (ere)i(used)g(as)f(tree)0 2005 y(searc)o(hers.)0 2084 y Fn(CABP)g Fp(is)h(an)f(algorithm)d(b)o(y)k(Cung)f(\(1994\),)f(based)i (on)g(the)g(Deep)g(Though)o(t)f(design)g(presen)o(ted)j(b)o(y)d(Hsu)h (\(1990\).)22 b(The)0 2134 y(algorithm)8 b(w)o(as)j(designed)g(for)f(a) h(shared)g(memory)e(system,)h(and)h(main)o(tains)d(a)j(shared)g (\\score)h(tree")g(for)e(the)h(en)o(tire)h(game-)0 2183 y(tree)18 b(and)f(the)h(t)o(w)o(o)e(lists)h(of)g(w)o(ork:)24 b(critical)17 b(no)q(des)g(one)h(ply)e(ab)q(o)o(v)o(e)h(the)h(lea)o(v)o (es,)f(and)g(non-critical)f(c)o(hildren)i(of)e(failed)0 2233 y(cut-no)q(des.)j(A)o(t)13 b(failed)f(cut-no)q(des,)h(the)h (non-critical)e(c)o(hildren)h(are)g(added)g(to)g(the)g(list)f Fk(k)i Fp(at)f(a)f(time.)17 b(\(In)12 b(the)i(sim)o(ulation)0 2283 y(results)e(giv)o(en)e(in)g(the)h(thesis,)g Fk(k)i Fp(=)f(1.\))k(In)11 b(his)f(Ph.D.)g(thesis,)h(Cung)g(sho)o(ws)f(the)h (CABP)h(algorithm)7 b(generating)k(a)f(sp)q(eedup)0 2333 y(of)i(4.6)g(on)h(strongly-ordered)h(trees)g(with)f(a)g(branc)o(hing)g (factor)f(of)h(40)f(using)h(9)g(pro)q(cessors)i(on)e(a)f(Sequen)o(t)i (Balance)f(8000.)0 2412 y(Kuszmaul)f(\(1994\))h(presen)o(ts)i Fn(Jamb)n(or)n(e)n(e)e(se)n(ar)n(ch)g Fp(in)g(his)g(Ph.D.)f(thesis)i (as)f(an)g(algorithm)e(for)h(testing)i(MIMD)f(sc)o(heduling)0 2462 y(algorithms)e(on)j(the)g(CM-5.)k(Jam)o(b)q(oree)13 b(searc)o(h)i(is)f(a)f(parallelization)f(of)h(NegaScout)h(searc)o(h)h (whic)o(h)f(b)q(eha)o(v)o(es)g(with)g(only)0 2511 y(a)f(few)g(minor)f (di\013erences)j(to)f(the)g(w)o(ork)f(done)g(b)o(y)g(F)m(eldmann)f Fn(et.)18 b(al)13 b Fp(on)g(the)h(Y)m(oung)f(Brothers)i(W)m(ait)d (algorithm.)j(In)e(the)0 2561 y(Y)m(oung)h(Brothers)i(W)m(ait)e (algorithm,)d(when)16 b(a)e(subtree)j(is)d(giv)o(en)g(to)h(a)f(pro)q (cessor)j(and)d(the)i(searc)o(h)g(fails)d(high,)h(the)h(sla)o(v)o(e)0 2611 y(pro)q(cessor)j(immediately)c(pro)q(ceeds)k(to)f(w)o(ork)f(out)h (the)g(v)n(alue)f(with)g(the)h(full)f(searc)o(h)h(windo)o(w)f(without)h (informing)c(the)0 2661 y(master)h(pro)q(cessor.)23 b(In)15 b(Jam)o(b)q(oree)g(searc)o(h,)h(a)f(fail)e(high)h(v)n(alue)g(is)h (returned)i(to)e(the)g(master)g(pro)q(cessor.)23 b(This)15 b(prev)o(en)o(ts)p eop %%Page: 10 10 10 9 bop 0 50 a Fp(10)592 b(ICCA)14 b(Journal)f(Submission)591 b(June)15 b(12,)e(1996)0 195 y(an)o(y)i(y)o(ounger)i(subtrees)h(from)c (executing)j(a)e(full)g(windo)o(w)g(searc)o(h)i(un)o(til)e(the)i(new)f (b)q(ound)g Fk(\013)g Fp(can)g(b)q(e)h(established)g(b)o(y)e(a)0 245 y(full)e(windo)o(w)g(searc)o(h.)0 324 y(W)m(eill)c(in)o(tro)q (duced)j(an)e(impro)o(v)o(emen)o(t)f(to)h(the)i Fk(\013\014)r Fp(*)f(algorithm)d(in)i(his)h(Ph.D.)f(thesis)i(\(1995\).)k(W)m(eill)9 b(suggested)k(and)d(tested)0 374 y(a)g(decision)h(metho)q(d)f(based)i (on)e(the)i(Y)m(oung)e(Brothers)i(W)m(ait,)d(instead)j(of)e(the)h (depth-limited)e(searc)o(h)j(and)f(constan)o(t)g(factor)0 423 y(at)i(t)o(yp)q(e)h(3)f(no)q(des)h(tested)g(b)o(y)f(Da)o(vid.)k(A)o (t)c(an)o(y)g(no)q(de)g(in)g(the)h Fk(\013\014)r Fp(*)f(algorithm,)d (if)j(the)g(leftmost)f(c)o(hild)h(isn't)g(ev)n(aluated,)f(all)0 473 y(pro)q(cessors)18 b(m)o(ust)d(ev)n(aluate)g(the)i(leftmost)d(c)o (hild.)23 b(Once)17 b(the)f(leftmost)f(c)o(hild)g(is)h(ev)n(aluated,)f (pro)q(cessors)j(are)e(allo)q(cated)0 523 y(to)i(non-ev)n(aluated)f (idle)g(c)o(hildren)h(\014rst,)h(and)e(then)i(allo)q(cated)e(in)g(a)h (balanced)f(manner)g(to)h(the)g(other)g(non-ev)n(aluated)0 573 y(c)o(hildren)13 b(in)g(the)g(tree.)19 b(Although)12 b(b)q(oth)h Fk(\013\014)r Fp(*)g(and)g(YBW)o(C*)g(use)h(the)f(same)f (decision)h(metho)q(d)f(for)h(allo)o(wing)d(or)j(den)o(ying)0 623 y(parallelism,)g Fk(\013\014)r Fp(*)j(uses)g(a)g(shared)g(transp)q (osition)g(table)f(to)g(k)o(eep)i(the)f(pro)q(cessors)i(w)o(orking)c (on)i(di\013eren)o(t)g(parts)g(of)f(the)0 672 y(tree,)g(while)e(YBW)o (C*)h(uses)h(master-sla)o(v)o(e)e(relationships.)0 751 y(In)g(a)g(later)g(pap)q(er)h(\(W)m(eill,)d(1996\),)h(the)i(com)o (bined)e(metho)q(d)g(w)o(as)h(called)g Fn(A)o(lpha-B)o(^)-20 b(eta)15 b(Distribut)o(\023)-20 b(e)13 b(ave)n(c)i(Dr)n(oit)e(d'A)1828 742 y(^)1830 751 y(inesse)p Fp(,)0 801 y(or)k(ABD)o(AD)o(A.)f(He)i(sho) o(w)o(ed)f(that)g(ABD)o(AD)o(A)g(yields)f(greater)i(sp)q(eedups)h(than) e(YBW)o(C)g(on)g(a)f(CM-5)h(when)g(studying)0 851 y(c)o(hess)j(trees.) 35 b(ABD)o(AD)o(A)19 b(also)g(yields)f(similar)f(sp)q(eedups)k(to)e (YBW)o(C)g(when)g(studying)g Fk(\013\014)i Fp(trees)g(generated)f(b)o (y)f(an)0 901 y(Othello)14 b(program.)0 980 y Fn(Dynamic)i(Multiple)e (Princip)n(al)g(V)m(ariation)g(Splitting)g Fp(\(DM-PVSplit\))f(is)h(a)g (v)n(ariation)e(of)h(the)h(PV-Split)g(algorithm)d(that)0 1029 y(allo)o(ws)18 b(for)h(greater)h(parallelism)c(near)k(the)f(start) h(of)f(a)g(searc)o(h)h(\(Marsland)f(and)g(Gao,)g(1995\).)33 b(T)m(o)18 b(understand)i(the)0 1079 y(algorithm,)12 b(it)i(is)h(necessary)i(to)d(de\014ne)i(the)g Fn(PV)f(set)p Fp(.)21 b(The)15 b(ro)q(ot)g(is)g(a)f(mem)o(b)q(er)f(of)i(the)g(PV)g (set.)22 b(A)o(t)15 b(subsequen)o(t)h(lev)o(els,)0 1129 y(no)q(des)f(are)f(part)g(of)g(the)g(PV)h(set)g(if)e(the)h(paren)o(t)h (is)f(a)g(mem)o(b)q(er)e(of)h(the)i(PV)f(set,)h(and)f(they)g(are)h (generated)g(b)o(y)f(the)g(\014rst)h Fk(k)0 1179 y Fp(candidate)g(mo)o (v)o(es)f(in)h(the)g(mo)o(v)o(e)f(list)h(of)f(the)i(paren)o(t.)22 b(The)16 b(determination)d(of)i Fk(k)h Fp(is)f(giv)o(en)f(b)o(y)h(a)g (function,)g(not)g(a)g(\014xed)0 1229 y(n)o(um)o(b)q(er.)i(Th)o(us,)c (the)g(PV)g(set)h(is)e(a)h(righ)o(t-pruned)g(v)o(ersion)g(of)f(the)h (game-tree.)18 b(An)13 b(appropriate)f(c)o(hoice)i(of)e(the)h (heuristic)0 1279 y(guess)h(allo)o(ws)d(for)i(greater)g(parallelism)d (without)j(adv)o(ersely)g(increasing)g(the)g(searc)o(h)h(o)o(v)o (erhead,)f(since)h(the)f(correct)i(mo)o(v)o(e)0 1328 y(at)g(a)g(PV)h(set)g(no)q(de)g(is)g(highly)e(lik)o(ely)g(to)h(app)q (ear)h(in)f(its)g(PV)h(set)g(c)o(hildren.)23 b(By)16 b(alw)o(a)o(ys)e(selecting)i(only)f(one)h(candidate)0 1378 y(mo)o(v)o(e,)10 b(DM-PVSplit)h(generalizes)h(in)o(to)f(PV-Split.) 17 b(Since)12 b(the)g(PV)g(set)h(do)q(es)f(not)f(resp)q(ect)j(the)f (structure)g(of)e(the)h(minima)o(l)0 1428 y(tree,)18 b(the)f(last)g(t)o(w)o(o)f(columns)f(in)i(T)m(able)e(2)i(re\015ect)h (this)f(b)o(y)f(referring)i(to)e(the)h(PV)g(set,)h(and)f(not)f(Kn)o (uth)h(and)g(Mo)q(ore's)0 1478 y(classi\014cation)d(of)f(minim)o(al)d (tree)15 b(no)q(des.)0 1557 y(The)c(algorithm)e(is)h(designed)i(for)f (use)g(on)g(strongly)g(ordered)h(trees.)19 b(In)11 b(the)g(pap)q(er,)h (Marsland)f(and)f(Gao)g(sho)o(w)h(the)h(results)0 1606 y(of)i(an)g(exp)q(erimen)o(t)g(where)i(DM-PVSplit)d(generates)j(a)e(sp) q(eedup)i(of)e(appro)o(ximately)e(32)i(o)o(v)o(er)g(64)g(pro)q (cessors,)i(using)e(an)0 1656 y(arti\014cially)e(generated)k(tree)f(of) e(width)h(32)f(and)h(depth)g(8.)0 1735 y Fn(Asynchr)n(onous)21 b(Par)n(al)r(lel)f(Hier)n(ar)n(chic)n(al)f(Iter)n(ative)g(De)n(ep)n (ening)i Fp(is)f(an)g(attempt)f(to)h(extend)g(the)h(ideas)f(of)f(Newb)q (orn's)0 1785 y(UIDP)m(ABS)c(algorithm)e(for)i(use)h(on)f(a)g(net)o(w)o (ork)h(of)f(w)o(orkstations,)g(where)h(the)g(cost)g(of)f(comm)o (unicatio)o(n)e(is)i(prohibitiv)o(e)0 1835 y(\(Bro)q(c)o(kington)j(and) f(Sc)o(hae\013er,)i(1996\).)28 b(Instead)19 b(of)e(using)g(a)g(single)g (ply)g(of)g(the)h(game-tree)f(to)h(generate)g(w)o(ork)g(lists,)0 1885 y(APHID)h(uses)h(a)f(truncated)h(game-tree)e(of)h(user-de\014ned)i (depth,)f(and)f(all)e(lea)o(v)o(es)i(of)f(the)i(truncated)g(game-tree)f (are)0 1934 y(allo)q(cated)c(to)g(sla)o(v)o(e)g(pro)q(cessors.)24 b(The)16 b(master)e(pro)q(cessors)k(within)c(the)i(hierarc)o(h)o(y)g (con)o(tin)o(ually)d(searc)o(h)k(the)f(truncated)0 1984 y(game-tree)g(to)g(add,)f(delete)j(and)d(up)q(date)i(the)g(priorit)o(y) e(of)g(w)o(ork)h(for)g(the)g(sla)o(v)o(es.)25 b(The)16 b(sla)o(v)o(e)g(pro)q(cessors)i(searc)o(h)g(their)0 2034 y(w)o(ork)12 b(lists)f(with)h(minim)o(al)c(sync)o(hronization)k(from)e (the)j(master.)k(The)12 b(sla)o(v)o(es)g(determine)g(their)g(o)o(wn)f (w)o(ork)h(sc)o(hedule)h(and)0 2084 y(inform)e(the)k(master)e(pro)q (cessors)j(of)d(the)h(searc)o(h)h(results.)k(Sla)o(v)o(e)13 b(pro)q(cessors)j(can)e(con)o(tin)o(ue)g(searc)o(hing)g(the)g(next)g (lev)o(el)g(of)0 2134 y(the)g(iterativ)o(e)g(deep)q(ening)h(searc)o(h)g (sp)q(eculativ)o(ely)f(if)f(they)i(ha)o(v)o(e)e(no)h(w)o(ork)g(left)f (to)h(do)g(at)f(the)i(curren)o(t)g(lev)o(el.)0 2213 y(The)e(APHID)f (algorithm)e(has)j(b)q(een)g(implemen)o(ted)d(as)j(a)f(game-indep)q (enden)o(t)g(library)g(that)g(can)h(b)q(e)g(easily)f(inserted)i(in)o (to)0 2262 y(a)e(sequen)o(tial)g(game-pla)o(ying)c(program.)16 b(The)d(library)e(has)h(b)q(een)h(tested)g(on)f(b)q(oth)g Fc(Key)m(ano)i Fp(\(an)e(Othello)g(program\))e(and)0 2312 y Fc(TheTurk)k Fp(\(a)g(c)o(hess)h(program\).)h(A)o(t)e(time)e(of) h(writing,)g(the)h(APHID)g(algorithm)d(ac)o(hiev)o(es)j(sp)q(eedups)h (of)e(8.41)g(and)g(6.02)0 2362 y(for)h Fc(Key)m(ano)i Fp(and)d Fc(TheTurk)i Fp(\(resp)q(ectiv)o(ely\))g(on)f(a)g(net)o(w)o (ork)g(of)f(16)g(Sparc-2)h(w)o(orkstations.)0 2529 y Fl(3)48 b(OTHER)16 b(SEAR)o(CH)g(P)l(ARADIGMS)f(F)o(OR)g(P)l(ARALLEL)g (GAME-TREE)i(SEAR)o(CH)0 2654 y Fp(Although)e(the)h(emphasis)f(has)h(b) q(een)h(on)e Fk(\013\014)r Fp(-based)h(metho)q(ds,)g(there)g(are)h (other)f(searc)o(h)h(strategies)f(that)g(can)g(b)q(e)g(used)0 2704 y(to)e(generate)i(the)f(minima)o(x)d(v)n(alue.)19 b(They)c(ha)o(v)o(e)g(b)q(een)g(sub)q(divided)g(in)o(to)f(three)i (subsections.)22 b(The)15 b(\014rst)g(will)e(deal)h(with)p eop %%Page: 11 11 11 10 bop 456 50 a Fe(A)14 b(T)m(axonom)o(y)d(of)j(P)o(arallel)e (Game-T)m(ree)h(Searc)o(h)i(Algorithms)454 b Fp(11)0 195 y(parallel)11 b(algorithms)g(based)i(on)f(the)h(original)e(form)o (ulation)e(of)j Fk(S)r(S)r(S)r Fj(\003)p Fp(.)20 b(The)13 b(second)h(subsection)f(will)f(deal)g(with)g(the)h Fk(E)r(R)0 245 y Fp(metho)q(d,)f(while)g(the)h(\014nal)f(subsection)i(will)d(deal) i(v)o(ery)g(brie\015y)g(with)f(purely)h(theoretical)g(mo)q(dels)f(for)g (game-tree)g(searc)o(h.)0 450 y Fl(3.1)48 b(P)o(arallel)13 b(Searc)o(h)h(based)h(on)g Fk(S)r(S)r(S)r Fj(\003)0 569 y Fp(Sto)q(c)o(kman)g(\(1979\))h(in)o(tro)q(duced)h(the)g Fk(S)r(S)r(S)r Fj(\003)h Fp(algorithm.)23 b(Initially)m(,)14 b(it)i(w)o(as)g(b)q(eliev)o(ed)h(that)f(the)h(algorithm)d(dominated)0 619 y Fk(\013\014)19 b Fp(in)d(the)h(sense)h(that)f Fk(S)r(S)r(S)r Fj(\003)i Fp(will)c(not)h(searc)o(h)i(a)e(no)q(de)h(if)f Fk(\013\014)i Fp(did)f(not)f(searc)o(h)i(it.)25 b(A)17 b(p)q(erceiv)o(ed)h(problem)d(with)h(the)0 669 y(algorithm)e(is)j(that) g(a)g(list)f(structure)k(\(the)d Fb(OPEN)f Fp(list\))h(m)o(ust)f(b)q(e) i(main)o(tained,)d(whic)o(h)i(could)f(gro)o(w)h(to)g Fk(b)1713 654 y Fa(d=)p Fm(2)1783 669 y Fp(elemen)o(ts,)0 719 y(where)f Fk(b)e Fp(is)h(the)g(branc)o(hing)g(factor)g(and)f Fk(d)h Fp(is)f(the)i(depth)f(of)f(the)i(tree)g(to)f(b)q(e)g(searc)o (hed.)22 b(This)15 b(space)h(requiremen)o(t)f(w)o(as,)0 769 y(at)e(the)g(time,)e(considered)j(to)f(b)q(e)g(to)q(o)g(large)f (for)g(a)h(practical)f(c)o(hess-pla)o(ying)h(program.)j(F)m (urthermore,)c(ev)o(en)i(if)e(the)h(space)0 818 y(requiremen)o(t)18 b(w)o(as)f(not)h(a)g(problem,)f(the)h(main)o(tenance)f(of)g(the)i Fb(OPEN)d Fp(list)i(slo)o(w)o(ed)f(do)o(wn)h(the)g(algorithm)d(to)j (mak)o(e)e(it)0 868 y(slo)o(w)o(er)e(than)g Fk(\013\014)i Fp(in)d(practice.)0 947 y(A)f(theoretical)g(parallel)f Fk(S)r(S)r(S)r Fj(\003)j Fp(algorithm)9 b(w)o(as)i(prop)q(osed)i (\(Campb)q(ell,)d(1981;)h(Campb)q(ell)e(and)j(Marsland,)f(1983\),)g (based)0 997 y(on)i(breaking)g(the)g(tree)i(in)o(to)d(stages)i(to)f (reduce)i(the)e(cost)h(of)f(main)o(taini)o(ng)d(the)k Fb(OPEN)e Fp(list.)17 b(A)o(t)d(the)f(end)h(of)e(a)h(stage)h(in)e(the)0 1047 y(searc)o(h,)j(the)f(no)q(de)h(w)o(ould)e(b)q(e)i(handed)f(to)g(a) g(sla)o(v)o(e)g(pro)q(cessor)i(in)d(the)i(tree)g(hierarc)o(h)o(y)m(.)k (This)14 b(limited)e(the)i(depth)h Fk(d)p Fp(,)f(th)o(us)0 1097 y(prev)o(en)o(ting)i(the)h Fb(OPEN)e Fp(list)h(from)e(b)q(ecoming) h(to)q(o)h(large.)25 b(The)16 b(staged)h Fk(S)r(S)r(S)r Fj(\003)h Fp(algorithm)c(is)h(sho)o(wn)i(to)f(b)q(e)g(marginally)0 1146 y(faster)f(than)e(either)i(tree)g(splitting)e(or)h(PV-Split)f(on)h (randomly)e(ordered)j(trees)g(in)f(Campb)q(ell's)e(w)o(ork.)0 1225 y(Leifk)o(er)k(and)g(Kanal)f(\(1985\))g(prop)q(ose)i(the)f(HYBRID) g(algorithm)d(that)j(is)g(based)g(on)g(the)g(problem)f(heap)h(from)e Fk(S)r(S)r(S)r Fj(\003)p Fp(,)0 1275 y(but)20 b(con)o(tains)f(no)g (details)g(p)q(ertaining)g(to)g(an)g(implemen)o(tation.)31 b(V)m(orn)o(b)q(erger)20 b(and)f(Monien)g(presen)o(ted)j(the)e(results) 0 1325 y(of)14 b(a)h(parallel)f Fk(S)r(S)r(S)r Fj(\003)j Fp(algorithm)c(\(1987\),)h(but)h(the)h(results)g(w)o(ere)g(disapp)q (oin)o(ting)d(when)j(compared)e(to)h(the)h(parallel)e Fk(\013\014)0 1375 y Fp(algorithm)9 b(\(later)i(to)g(b)q(e)h(called)f (\\Y)m(oung)f(Brothers)j(W)m(ait"\).)i(Their)d(implemen)o(tatio)o(n)d (of)h(parallel)g Fk(S)r(S)r(S)r Fj(\003)k Fp(on)d(a)f(lo)q(cal)h(area)0 1424 y(net)o(w)o(ork)j(of)f(PCs)i(had)e(a)h(searc)o(h)h(o)o(v)o(erhead) f(of)g(o)o(v)o(er)f(300)h(p)q(ercen)o(t)h(when)g(using)e(16)h(pro)q (cessors.)20 b(Dideric)o(h)14 b(describ)q(ed)h(an)0 1474 y(implemen)o(tatio)o(n)c(of)j(Sync)o(hronized)h(Distributed)f(State)g (Space)h(Searc)o(h)g(\()p Fk(S)r(D)q(S)r(S)r(S)s Fj(\003)p Fp(\))h(\(1992\))e(and)f(ac)o(hiev)o(ed)i(a)e(sp)q(eedup)0 1524 y(of)g(11.40)g(using)g(32)h(pro)q(cessors,)h(searc)o(hing)g(a)e(5) h(ply)f(tree)i(with)f(a)f(branc)o(hing)h(factor)g(of)f(16.)0 1603 y(There)k(are)f(some)e(other)i Fk(S)r(S)r(S)r Fj(\003)i Fp(algorithms)13 b(b)o(y)i(Hiromoto)f Fn(et)i(al.)23 b Fp(\(1987\),)14 b(Kraas)i(\(1990\),)f(and)g(Shinghal)f(and)i(Sh)o(v)o (ed)0 1653 y(\(1991\),)f(and)h(all)f(of)g(the)i(w)o(ork)e(deals)h(with) g(ho)o(w)f(to)h(parallelize)f(w)o(ork)h(based)g(on)g(the)h Fb(OPEN)e Fp(list.)23 b(Although)16 b(the)g(w)o(ork)0 1703 y(has)g(sho)o(wn)f(some)g(promise)f(in)i(eliminating)c(the)k (di\016culties)f(of)g(dealing)g(with)g(an)g(ordered)i(problem)d(heap,)i (all)e(of)h(the)0 1752 y(w)o(ork)i(on)f(handling)g(the)i Fb(OPEN)e Fp(list)g(has)h(b)q(een)h(made)e(obsolete.)28 b(This)17 b(is)g(due)g(to)g(the)g(rev)o(elation)g(that)g Fk(S)r(S)r(S)r Fj(\003)i Fp(can)e(b)q(e)0 1802 y(implemen)o(ted)e(as)i (a)g(series)h(of)f(n)o(ull-windo)o(w)e Fk(\013\014)k Fp(calls,)e(using)g(a)g(transp)q(osition)g(table)g(in)f(the)i(place)f (of)g(the)g Fb(OPEN)f Fp(list)0 1852 y(\(Plaat,)d(1995\).)0 2057 y Fl(3.2)48 b(P)o(arallel)13 b(Searc)o(h)h(based)h(on)g Fk(E)r(R)0 2176 y Fp(Stein)o(b)q(erg)g(and)f(Solomon)d(\(1990\))j (presen)o(ted)i(the)e Fk(E)r(R)g Fp(metho)q(d)g(of)f(searc)o(hing)i (game-trees.)j Fk(E)r(R)c Fp(stands)h(for)f(Ev)n(aluate-)0 2226 y(Refute,)20 b(and)f(it)g(attempts)f(to)h(ev)n(aluate)g(some)f (mandatory)g(w)o(ork)g(b)q(efore)i(attempting)e(to)h(refute)h(the)g (other)f(mo)o(v)o(es)0 2276 y(within)e(the)g(tree.)30 b(A)o(t)17 b(a)g(no)q(de)h(to)f(b)q(e)h(ev)n(aluated)f(\(an)g(e-no)q (de\))h(within)f(the)h(tree,)g(the)g Fk(E)r(R)f Fp(algorithm)e(ev)n (aluates)i(the)0 2326 y(elder)g(grandc)o(hildren)f(\(concurren)o(tly)m (,)h(if)f(p)q(ossible\),)h(and)f(then)g(c)o(ho)q(oses)i(the)f(c)o(hild) e(with)h(largest)h(elder)g(grandc)o(hild)e(to)0 2376 y(b)q(e)f(the)g(e-c)o(hild.)k(This)13 b(e-c)o(hild)g(is)g(ev)n (aluated,)g(and)g(then)i(the)f(other)g(c)o(hildren)f(of)g(the)h(e-no)q (de)g(are)g(refuted.)19 b(The)14 b(metho)q(d)0 2425 y(is)f(less)h (e\016cien)o(t)g(at)g(searc)o(hing)f(trees)i(than)f(the)g Fk(\013\014)i Fp(algorithm)10 b(since)15 b(it)e(misses)g(some)f(deep)j (cuto\013s.)j(F)m(urthermore,)13 b(the)0 2475 y(algorithm)e(w)o(as)j (not)g(tested)h(with)f(iterativ)o(e)g(deep)q(ening)h(or)e(minima)o(l)e (windo)o(ws)i(when)i(refuting)e(e-no)q(des.)0 2554 y(The)21 b Fk(E)r(R)f Fp(metho)q(d)g(and)h(PV-Split)f(w)o(ere)h(implemen)o(ted)e (as)h(problem-heap)g(algorithms)e(on)i(a)h(Sequen)o(t)g(Symmetry)0 2604 y(m)o(ultipro)q(cessor.)k(Stein)o(b)q(erg)17 b(and)f(Solomon)e (found)i(that)h(they)g(ac)o(hiev)o(ed)f(a)h(b)q(etter)h(e\016ciency)f (with)f(the)h(parallel)e Fk(E)r(R)0 2654 y Fp(algorithm)10 b(than)j(with)f(PV-Split.)17 b(The)c Fk(E)r(R)f Fp(metho)q(d)g(ac)o (hiev)o(ed)h(a)f(sp)q(eedup)j(of)d(10)g(with)g(16)g(pro)q(cessors,)j (and)d(a)g(sp)q(eedup)0 2704 y(of)h(14.7)g(with)g(27)h(pro)q(cessors.)p eop %%Page: 12 12 12 11 bop 0 50 a Fp(12)592 b(ICCA)14 b(Journal)f(Submission)591 b(June)15 b(12,)e(1996)0 195 y Fl(3.3)48 b(Theoretical)13 b(P)o(arallel)g(Searc)o(h)i(Metho)q(ds)0 303 y Fp(There)i(are)g(a)f(n)o (um)o(b)q(er)g(of)f(theoretical)i(algorithms)d(that,)i(to)h(the)f (author's)h(kno)o(wledge,)f(ha)o(v)o(en't)g(b)q(een)h(programmed.)0 353 y(Karp)c(and)g(Zhang)h(\(1989\))e(and)h(Alth\177)-21 b(ofer)13 b(\(1993\))f(ha)o(v)o(e)h(prop)q(osed)h(algorithms)d(that)j (will)d(yield)i(linear)g(sp)q(eedups)i(in)d(the)0 402 y(n)o(um)o(b)q(er)17 b(of)f(pro)q(cessors,)k(giv)o(en)d(trees)i(of)e Fk(O)q Fp(\()p Fk(N)12 b Fp(log)6 b Fk(N)f Fp(\))18 b(or)f Fk(O)q Fp(\()p Fk(N)5 b Fp(\))17 b(depth,)i(resp)q(ectiv)o(ely)m(.)29 b(Bro)q(der)19 b Fn(et)f(al.)28 b Fp(\(1990\))17 b(ha)o(v)o(e)0 452 y(sho)o(wn)12 b(that)g(for)g(an)o(y)f(parallel)g(tree)i(searc)o (hing)f(algorithm,)e(there)j(exists)g(a)e(tree)i(instance)g(that)f(do)q (es)h(not)f(run)g(in)g(p)q(olylog)0 502 y(parallel)18 b(run-time.)32 b(Bro)q(der)20 b Fn(et)f(al.)33 b Fp(also)18 b(sho)o(w)h(and)g(pro)o(v)o(e)g(an)g(upp)q(er)h(b)q(ound)f(on)f(the)i (run-time)e(of)g(the)h(P)o(arHop)q(e)0 552 y(algorithm.)0 703 y Fl(4)48 b(CONCLUSIONS)0 825 y Fp(The)19 b(taxonom)o(y)d(giv)o(en) i(in)g(section)h(2)f(sho)o(ws)h(that)f(there)i(are)f(a)f(n)o(um)o(b)q (er)g(of)f(algorithms)f(whic)o(h)j(are)g(similar)c(to)k(one)0 875 y(another.)29 b(There)19 b(are)f(only)e(subtle)i(di\013erences)i(b) q(et)o(w)o(een)f(a)e(large)g(n)o(um)o(b)q(er)g(of)g(the)h Fk(\013\014)r Fp(-based)g(algorithms.)27 b(Most)18 b(of)0 925 y(these)h(di\013erences)g(are)e(due)h(to)f(the)h(di\013eren)o(t)g (arc)o(hitectures)h(and)e(game)f(trees)i(studied.)29 b(This)17 b(comparison)e(is)i(easily)0 974 y(made)c(through)h(the)g (separation)g(of)f(the)i(implemen)o(tatio)o(n)c(and)j(algorithmic)d (details.)0 1053 y(As)17 b(the)h(n)o(um)o(b)q(er)e(of)g(pro)q(cessors)j (a)o(v)n(ailable)c(to)i(the)g(programmers)e(has)i(increased,)h(dynamic) e(algorithms)e(ha)o(v)o(e)j(tak)o(en)0 1103 y(the)i(place)f(of)g(the)h (earlier)f(algorithms)e(whic)o(h)i(o\013ered)i(limited)c(parallelism)f (on)j(a)g(large)g(n)o(um)o(b)q(er)g(of)g(pro)q(cessors.)33 b(It)0 1153 y(is)16 b(the)h(author's)g(b)q(elief)f(that)h(sp)q (eculativ)o(e)g(parallelism)d(is)i(necessary)j(to)d(yield)g (near-linear)g(p)q(erformance)h(on)f(parallel)0 1203 y(arc)o(hitectures,)g(and)d(is)h(the)h(sub)r(ject)g(of)e(on-going)g (researc)o(h)i(at)f(the)h(Univ)o(ersit)o(y)e(of)h(Alb)q(erta.)0 1354 y Fl(5)48 b(A)o(CKNO)o(WLEDGEMENTS)0 1476 y Fp(The)19 b(author)g(w)o(ould)g(lik)o(e)f(to)h(thank)f(Yngvi)h(Bjornsson,)h (Rainer)f(F)m(eldmann,)f(Y)m(ao)q(qing)f(Gao,)i(Andreas)h(Junghanns,)0 1526 y(T)m(on)o(y)14 b(Marsland,)f(Ask)o(e)j(Plaat,)d(Jonathan)h(Sc)o (hae\013er,)i(Jean-Christophe)g(W)m(eill)c(and)j(the)g(editorial)e (sta\013)i(of)f(the)h(ICCA)0 1575 y(Journal)d(for)g(their)h(helpful)f (commen)o(ts)f(on)h(the)i(revisions)e(of)g(this)h(pap)q(er.)18 b(The)13 b(author)g(is)f(b)q(eing)h(funded)g(b)o(y)f(an)g(NSER)o(C)0 1625 y(P)o(ostgraduate)i(Sc)o(holarship,)g(for)f(whic)o(h)h(the)g (author)g(is)g(extremely)g(grateful.)0 1704 y(The)g(author)g(w)o(ould)f (appreciate)i(an)o(y)e(corrections,)i(suggestions)g(and)e(impro)o(v)o (emen)o(ts)f(that)i(y)o(ou)f(ma)o(y)f(ha)o(v)o(e.)0 1847 y Fl(References)21 1953 y Fp(Akl,)j(S.)h(G.,)f(Barnard,)h(D.)f(T.,)h (and)g(Doran,)f(R.)g(J.)h(\(1982\).)23 b(Design,)16 b(Analysis)g(and)f (Implemen)o(tation)e(of)i(a)h(P)o(arallel)21 1994 y(T)m(ree)g(Searc)o (h)h(Algorithm.)k Fn(IEEE)c(T)m(r)n(ansactions)g(on)g(Pattern)g(A)o (nalysis)f(and)h(Machine)h(Intel)r(ligenc)n(e)p Fp(,)e(V)m(ol.)e(P)m (AMI-4,)21 2036 y(No.)f(2,)g(pp.)h(192{203.)21 2119 y(Alth\177)-21 b(ofer,)13 b(I.)f(\(1993\).)17 b(A)c(P)o(arallel)f(Game)g(T)m(ree)i (Searc)o(h)g(Algorithm)d(with)i(a)g(Linear)g(Sp)q(eedup.)18 b Fn(Journal)c(of)h(A)o(lgorithm)p Fp(,)21 2161 y(V)m(ol.)d(15,)h(pp.)g (175{198.)21 2245 y(Bal,)f(H.)h(E.)g(and)f(v)n(an)h(Renesse,)h(R.)e (\(1986\).)k(A)d(Summary)e(of)h(P)o(arallel)g(Alpha-Beta)h(Searc)o(h)h (Results.)j Fn(ICCA)d(Journal)p Fp(,)21 2286 y(V)m(ol.)e(9,)h(No.)g(3,) h(pp.)f(146{149.)21 2370 y(Baudet,)j(G.)f(M.)g(\(1978\).)22 b Fn(The)16 b(Design)h(and)g(Analysis)f(of)h(Algorithms)e(for)h (Asynchr)n(onous)h(Multipr)n(o)n(c)n(essors)p Fp(.)22 b(Ph.D.)21 2412 y(thesis,)14 b(Carnegie)g(Mellon)f(Univ)o(ersit)o(y)m (,)g(Pittsburgh,)h(P)m(A.)k(Av)n(ailable)12 b(as)i(T)m(ec)o(h.)g(Rept.) g(CMU-CS-78-116.)21 2495 y(Bro)q(c)o(kington,)g(M.)g(G.)f(and)i(Sc)o (hae\013er,)g(J.)f(\(1996\).)19 b(APHID)c(Game-Tree)e(Searc)o(h.)21 b(Presen)o(ted)c(at)d Fn(A)n(dvanc)n(es)i(in)f(Com-)21 2537 y(puter)f(Chess)h(8)p Fp(,)f(Maastric)o(h)o(t.)21 2621 y(Bro)q(der,)19 b(A.,)f(Karlin,)g(A.,)g(Ragha)o(v)n(an,)e(P)m(.,)i (and)g(Upfal,)f(E.)h(\(1990\).)29 b(On)18 b(the)g(Parallel)f(Complexit) o(y)e(of)j(Ev)n(aluating)21 2662 y(Game-Trees.)g(T)m(ec)o(hnical)c(Rep) q(ort)h(RR)e(RJ)h(7729,)f(IBM)h(T.)g(J.)g(W)m(atson)g(Researc)o(h)h (Cen)o(ter,)g(Y)m(orkto)o(wn)e(Heigh)o(ts,)h(New)21 2704 y(Y)m(ork.)p eop %%Page: 13 13 13 12 bop 456 50 a Fe(A)14 b(T)m(axonom)o(y)d(of)j(P)o(arallel)e (Game-T)m(ree)h(Searc)o(h)i(Algorithms)454 b Fp(13)21 195 y(Brudno,)17 b(A.)f(L.)g(\(1963\).)26 b(Bounds)17 b(and)f(V)m(aluations)g(for)g(Abridging)g(the)h(Searc)o(h)g(for)g (Estimates.)25 b Fn(Pr)n(oblems)17 b(of)g(Cy-)21 237 y(b)n(ernetics)p Fp(,)d(V)m(ol.)f(10,)h(pp.)g(225{241.)19 b(T)m(ranslation)14 b(of)g(Russian)h(original)d(in)j Fn(Pr)n(oblemy)g(Kib)n(ernetiki)p Fp(,)f(10:141{150,)d(Ma)o(y)21 278 y(1963.)21 356 y(Campb)q(ell,)i(M.)j(S.)f(\(1981\).)22 b Fn(A)o(lgorithms)16 b(for)g(the)g(Par)n(al)r(lel)g(Se)n(ar)n(ch)g(of) h(Game)g(Tr)n(e)n(es)p Fp(.)22 b(M.Sc.)15 b(thesis,)h(Departmen)o(t)g (of)21 397 y(Computing)f(Science,)k(Univ)o(ersit)o(y)e(of)f(Alb)q (erta,)i(Edmon)o(ton,)e(Alta.)28 b(Av)n(ailable)15 b(as)j(T)m(ec)o(h.)f (Rep.)f(TR)h(81-8,)g(Dept.)g(of)21 439 y(Computing)12 b(Science.)21 516 y(Campb)q(ell,)e(M.)h(S.)g(and)h(Marsland,)g(T.)f(A.) g(\(1983\).)j(A)e(Comparison)e(of)h(Minimax)e(T)m(ree)k(Searc)o(h)f (Algorithms.)h Fn(A)o(rti\014cial)21 557 y(Intel)r(ligenc)n(e)p Fp(,)g(V)m(ol.)f(20,)h(pp.)h(347{367.)21 635 y(Ciancarini,)g(P)m(.)h (\(1994\).)22 b(Distributed)16 b(Searc)o(hes:)23 b(A)16 b(Basis)g(for)f(Comparison.)21 b Fn(ICCA)16 b(Journal)p Fp(,)f(V)m(ol.)f(17,)h(No.)g(4,)g(pp.)21 676 y(194{206.)21 754 y(Cung,)h(V.-D.)f(\(1994\).)24 b Fn(Contribution)17 b(\022)-21 b(a)18 b(l'A)o(lgorithmique)d(Non)j(Num)o(\023)-20 b(erique)17 b(Par)n(al)r(l)o(\022)-20 b(ele:)22 b(Explor)n(ation)17 b(d'Esp)n(ac)n(es)h(de)21 795 y(R)n(e)n(cher)n(che)p Fp(.)g(Ph.D.)13 b(thesis,)h(Univ)o(ersit)o(\023)-20 b(e)15 b(P)o(aris)f(VI.)21 873 y(Da)o(vid,)f(V.)h(\(1993\).)20 b Fn(A)o(lgorithmique)15 b(p)n(ar)n(al)r(l)o(\022)-20 b(ele)15 b(sur)g(les)g(arbr)n(es)g(de)h(d)o(\023)-20 b(ecision)16 b(et)g(r)n(aisonnement)g(en)g(temps)g(c)n(ontr)n(aint)f(-) 21 914 y(Etude)g(et)g(applic)n(ation)g(au)g(minimax)p Fp(.)j(Ph.D.)13 b(thesis,)i(ENSAE,)f(T)m(oulouse,)f(F)m(rance.)21 992 y(Dideric)o(h,)f(C.)g(G.)g(\(1992\).)j(Ev)n(aluation)c(des)i(P)o (erformances)g(de)g(l'Algorithm)o(e)d(SSS*)j(a)o(v)o(ec)g(Phases)g(de)g (Sync)o(hronisation)21 1033 y(sur)j(une)g(Mac)o(hine)f(P)o(arall)o (\022)-20 b(ele)15 b(\022)-21 b(a)15 b(M)o(\023)-20 b(emoires)14 b(Distribu)o(\023)-20 b(ees.)23 b(T)m(ec)o(hnical)15 b(Rep)q(ort)h(LITH-99,)e(Swiss)i(F)m(ederal)f(Institute)i(of)21 1075 y(T)m(ec)o(hnology)m(,)12 b(Lausanne,)i(Switzerland.)21 1152 y(F)m(eldmann,)26 b(R.)f(\(1993\).)53 b Fn(Spielb)n(aumsuche)27 b(mit)e(massiv)h(p)n(ar)n(al)r(lelen)f(Systemen)p Fp(.)54 b(Ph.D.)25 b(thesis,)k(Univ)o(ersit\177)-21 b(at-)21 1194 y(Gesam)o(tho)q(c)o(hsc)o(h)o(ule)13 b(P)o(aderb)q(orn,)i(P)o (aderb)q(orn,)f(German)o(y)m(.)21 1271 y(F)m(eldmann,)j(R.,)h(Monien,)h (B.,)g(Mysliwietz,)g(P)m(.,)f(and)g(V)m(orn)o(b)q(erger,)i(O.)e (\(1989\).)31 b(Distributed)19 b(Game)e(T)m(ree)i(Searc)o(h.)21 1312 y Fn(ICCA)14 b(Journal)p Fp(,)f(V)m(ol.)g(12,)f(No.)i(2,)f(pp.)g (65{73.)21 1390 y(F)m(elten,)g(E.)g(W.)g(and)h(Otto,)f(S.)g(W.)g (\(1988\).)k(Chess)d(on)g(a)f(Hyp)q(ercub)q(e.)19 b(In)14 b(G.)f(F)m(o)o(x,)f(editor,)h Fn(Pr)n(o)n(c)n(e)n(e)n(dings)i(of)f(The) h(Thir)n(d)21 1431 y(Confer)n(enc)n(e)e(on)i(Hyp)n(er)n(cub)n(e)e (Concurr)n(ent)h(Computers)f(and)i(Applic)n(ations)p Fp(,)d(v)o(olume)f(I)q(I-Applications,)g(pp.)i(1329{1341,)21 1473 y(P)o(assadena,)h(CA.)21 1550 y(F)m(erguson,)g(C.)f(and)h(Korf,)f (R.)h(E.)f(\(1988\).)18 b(Distributed)c(T)m(ree)h(Searc)o(h)g(and)f (its)g(Application)f(to)g(Alpha-Beta)h(Pruning.)21 1592 y(In)g Fn(Pr)n(o)n(c)n(e)n(e)n(dings)g(of)h(AAAI-88)p Fp(,)e(pp.)h(128{132,)e(Sain)o(t)h(P)o(aul,)g(MN.)21 1669 y(Fink)o(el,)f(R.)g(A.)h(and)g(Fish)o(burn,)g(J.)g(P)m(.)g (\(1982\).)j(P)o(arallelism)11 b(in)h(Alpha-Beta)i(Searc)o(h.)k Fn(A)o(rti\014cial)13 b(Intel)r(ligenc)n(e)p Fp(,)f(V)m(ol.)g(19,)21 1711 y(No.)h(1,)g(pp.)h(89{106.)21 1788 y(Hiromoto,)i(U.,)j(Masafumi,)d (Y.,)j(Masaharu,)g(I.,)f(and)g(T)m(oshihide,)g(I.)f(\(1987\).)30 b(P)o(arallel)18 b(Searc)o(hes)h(of)f(Game)e(T)m(rees.)21 1830 y Fn(Systems)f(and)h(Computers)e(in)h(Jap)n(an)p Fp(,)f(V)m(ol.)e(18,)h(No.)g(8,)h(pp.)f(97{109.)21 1907 y(Hsu,)20 b(F.-h.)e(\(1990\).)31 b Fn(L)n(ar)n(ge)19 b(Sc)n(ale)h(Par)n(al)r(lelization)e(of)h(A)o(lpha-Beta)h(Se)n(ar)n (ch:)28 b(A)o(n)19 b(A)o(lgorithmic)g(and)h(A)o(r)n(chite)n(ctur)n(al) 21 1949 y(Study)p Fp(.)28 b(Ph.D.)16 b(thesis,)i(Carnegie)f(Mellon)f (Univ)o(ersit)o(y)m(,)h(Pittsburgh,)h(U.S.A.)26 b(Also)17 b(T)m(ec)o(h.)f(Rept.)h(CMU-CS-90-108,)21 1990 y(Carnegie)d(Mellon)f (Univ)o(ersit)o(y)m(,)g(F)m(eb.)g(1990.)21 2067 y(Hy)o(att,)i(R.)g(M.)g (\(1988\).)22 b Fn(A)16 b(High-Performanc)n(e)g(Par)n(al)r(lel)g(A)o (lgorithm)f(T)m(o)h(Se)n(ar)n(ch)h(Depth-F)m(rist)e(Game)i(T)m(r)n(e)n (es)p Fp(.)22 b(Ph.D.)21 2109 y(thesis,)14 b(Univ)o(ersit)o(y)g(of)f (Alabama,)e(Birmingham,)f(U.S.A.)21 2186 y(Hy)o(att,)15 b(R.)f(M.,)h(Suter,)h(B.)f(W.,)f(and)h(Nelson,)h(H.)f(L.)f(\(1989\).)22 b(A)15 b(P)o(arallel)f(Alpha/Beta)h(T)m(ree)h(Searc)o(hing)g (Algorithm.)21 2228 y Fn(Par)n(al)r(lel)e(Computing)p Fp(,)f(V)m(ol.)g(10,)g(No.)g(3,)g(pp.)g(299{308.)21 2305 y(Karp,)i(R.)f(M.)h(and)g(Zhang,)g(Y.)g(\(1989\).)22 b(On)15 b(Parallel)f(Ev)n(aluation)g(of)h(Game)e(Trees.)24 b(In)15 b Fn(Pr)n(o)n(c)n(e)n(e)n(dings)h(of)g(SP)m(AA)g('89)p Fp(,)21 2347 y(pp.)d(409{420,)f(New)i(Y)m(ork,)f(NY.)h(A)o(CM)g(Press.) 21 2424 y(Kn)o(uth,)f(D.)f(E.)g(and)h(Mo)q(ore,)g(R.)f(W.)f(\(1975\).) 16 b(An)d(Analysis)f(of)g(Alpha-Beta)h(Pruning.)j Fn(A)o(rti\014cial)d (Intel)r(ligenc)n(e)p Fp(,)f(V)m(ol.)g(6,)21 2466 y(No.)h(3,)g(pp.)h (293{326.)21 2543 y(Kraas,)e(H.-J.)f(\(1990\).)j Fn(Zur)f(Par)n(al)r (lelisierung)f(des)h(SSS*-A)o(lgorithmus)p Fp(.)i(Ph.D.)c(thesis,)i(TU) f(of)f(Braunsc)o(h)o(w)o(eig,)i(Braun-)21 2585 y(sc)o(h)o(w)o(eig,)g (German)o(y)m(.)21 2662 y(Kuszmaul,)h(B.)h(C.)f(\(1994\).)21 b Fn(Synchr)n(onize)n(d)c(MIMD)g(Computing)p Fp(.)k(Ph.D.)15 b(thesis,)g(Massac)o(h)o(usetts)i(Institute)f(of)f(T)m(ec)o(h-)21 2704 y(nology)m(,)c(Cam)o(bridge,)h(MA.)p eop %%Page: 14 14 14 13 bop 0 50 a Fp(14)592 b(ICCA)14 b(Journal)f(Submission)591 b(June)15 b(12,)e(1996)21 195 y(Leifk)o(er,)f(D.)g(B.)h(and)f(Kanal,)g (L.)g(N.)h(\(1985\).)i(A)e(Hybrid)f(SSS*/Alpha-Beta)h(Algorithm)d(for)i (P)o(arallel)g(Searc)o(h)i(of)e(Game)21 237 y(T)m(rees.)19 b(In)14 b Fn(Pr)n(o)n(c)n(e)n(e)n(dings)g(of)h(IJCAI-85)p Fp(,)e(pp.)h(1044{1046.)21 311 y(Lindstrom,)d(G.)g(\(1983\).)k(The)e (Key)h(No)q(de)f(Metho)q(d:)18 b(A)12 b(Highly-P)o(arallel)e (Alpha-Beta)j(Algorithm.)g(T)m(ec)o(hnical)g(Rep)q(ort)21 353 y(UUCS)h(83-101,)e(Univ)o(ersit)o(y)i(of)f(Utah,)g(Departmen)o(t)h (of)f(Computer)g(Science,)i(Salt)e(Lak)o(e)h(Cit)o(y)m(,)e(UT.)21 428 y(Lu,)20 b(C.-P)m(.)e(P)m(.)g(\(1993\).)33 b Fn(Par)n(al)r(lel)19 b(Se)n(ar)n(ch)h(of)g(Narr)n(ow)e(Game)i(Tr)n(e)n(es)p Fp(.)33 b(M.Sc.)19 b(thesis,)i(Departmen)o(t)d(of)h(Computing)21 469 y(Science,)c(Univ)o(ersit)o(y)e(of)h(Alb)q(erta,)g(Edmon)o(ton,)d (Canada.)21 544 y(Marsland,)j(T.)h(A.)g(\(1983\).)21 b(Relativ)o(e)14 b(E\016ciency)h(of)g(Alpha-Beta)g(Implemen)o(tations.) k(In)c Fn(Pr)n(o)n(c)n(e)n(e)n(dings)h(of)g(IJCAI-83)p Fp(,)21 585 y(pp.)d(763{766,)f(Karlsruhe,)i(German)o(y)m(.)21 660 y(Marsland,)k(T.)f(A.)h(and)f(Campb)q(ell,)g(M.)g(S.)g(\(1982\).)29 b(Parallel)17 b(Searc)o(h)i(of)e(Strongly)g(Ordered)j(Game)c(Trees.)31 b Fn(A)o(CM)21 702 y(Computing)15 b(Surveys)p Fp(,)f(V)m(ol.)e(14,)h (No.)g(4,)g(pp.)h(533{551.)21 776 y(Marsland,)h(T.)f(A.)h(and)g(Gao,)f (Y.)h(\(1995\).)22 b(Sp)q(eculativ)o(e)15 b(P)o(arallelism)e(Impro)o(v) o(es)h(Searc)o(h?)30 b(T)m(ec)o(hnical)15 b(Rep)q(ort)h(95{05,)21 818 y(Departmen)o(t)d(of)g(Computing)f(Science,)j(Univ)o(ersit)o(y)f (of)f(Alb)q(erta,)h(Edmon)o(ton,)e(Alta.)21 892 y(Marsland,)19 b(T.)g(A.,)g(Olafsson,)h(M.,)g(and)e(Sc)o(hae\013er,)k(J.)d(\(1985\).) 32 b(Multipro)q(cessor)21 b(Tree-Searc)o(h)g(Exp)q(erimen)o(ts.)33 b(In)21 934 y(D.)13 b(Beal,)g(editor,)h Fn(A)n(dvanc)n(es)h(in)g (Computer)g(Chess)g(4)p Fp(,)e(pp.)h(37{51.)e(P)o(ermagon)h(Press,)i (Oxford.)21 1009 y(Marsland,)j(T.)f(A.)h(and)f(P)o(op)q(o)o(wic)o(h,)h (F.)f(\(1985\).)29 b(Parallel)17 b(Game-Tree)g(Searc)o(h.)31 b Fn(IEEE)19 b(T)m(r)n(ansactions)f(on)h(Pattern)21 1050 y(A)o(nalysis)14 b(and)i(Machine)g(Intel)r(ligenc)n(e)p Fp(,)d(V)m(ol.)f(P)m(AMI-7,)h(No.)h(4,)f(pp.)g(442{452.)21 1125 y(Newb)q(orn,)g(M.)e(M.)h(\(1985\).)i(A)f(P)o(arallel)e(Searc)o(h) i(Chess)g(Program.)h(In)e Fn(Pr)n(o)n(c)n(e)n(e)n(dings)h(of)g(the)h(A) o(CM)f(A)o(nnual)h(Confer)n(enc)n(e)p Fp(,)21 1166 y(pp.)f(272{277.)21 1241 y(Newb)q(orn,)h(M.)f(M.)h(\(1988\).)j(Unsync)o(hronized)e (Iterativ)o(e)f(Deep)q(ening)h(P)o(arallel)d(Alpha-Beta)i(Searc)o(h.)19 b Fn(IEEE)c(T)m(r)n(ansac-)21 1283 y(tions)g(on)g(Pattern)g(A)o (nalysis)f(and)i(Machine)g(Intel)r(ligenc)n(e)p Fp(,)d(V)m(ol.)f(P)m (AMI-10,)h(No.)g(5,)g(pp.)h(687{694.)21 1357 y(Plaat,)g(A.,)h(Sc)o (hae\013er,)h(J.,)f(Pijls,)f(W.,)g(and)h(de)h(Bruin,)f(A.)g(\(1995\).) 20 b(Best-First)d(Fixed-Depth)f(Game-T)m(ree)d(Searc)o(h)j(in)21 1399 y(Practice.)j(In)14 b Fn(Pr)n(o)n(c)n(e)n(e)n(dings)h(of)f (IJCAI-95)p Fp(,)f(v)o(olume)f(1,)i(pp.)f(273{279,)f(Mon)o(treal,)h (Queb)q(ec.)21 1474 y(Plaat,)h(A.,)g(Sc)o(hae\013er,)i(J.,)e(Pijls,)g (W.,)f(and)i(de)g(Bruin,)g(A.)f(\(1996\).)20 b(Best-First)c (Fixed-Depth)f(Minimax)d(Algorithms.)21 1515 y(T)m(o)h(app)q(ear)h(in)g Fn(A)o(rti\014cial)f(Intel)r(ligenc)n(e)p Fp(.)21 1590 y(Reinefeld,)g(A.)h(\(1983\).)k(An)c(Impro)o(v)o(emen)o(t)e(to)i(the)h (Scout)g(Tree-Searc)o(h)h(Algorithm.)g Fn(ICCA)e(Journal)p Fp(,)g(V)m(ol.)f(6,)g(No.)h(4,)21 1631 y(pp.)f(4{14.)21 1706 y(Sc)o(hae\013er,)19 b(J.)e(\(1989\).)28 b(Distributed)18 b(Game-T)m(ree)e(Searc)o(hing.)29 b Fn(Journal)18 b(of)g(Par)n(al)r (lel)g(and)h(Distribute)n(d)e(Computing)p Fp(,)21 1748 y(V)m(ol.)12 b(6,)h(No.)g(2,)h(pp.)f(90{114.)21 1822 y(Shinghal,)f(R.)i(and)g(Sh)o(v)o(ed,)g(S.)g(\(1991\).)k(Prop)q(osed)e (Mo)q(di\014cations)e(to)g(P)o(arallel)f(State)i(Space)g(Searc)o(h)g (of)f(Game)e(T)m(rees.)21 1864 y Fn(International)j(Journal)g(of)f (Pattern)h(R)n(e)n(c)n(o)n(gnition)g(and)h(A)o(rti\014cial)e(Intel)r (ligenc)n(e)p Fp(,)f(V)m(ol.)f(5,)h(No.)h(5,)f(pp.)g(809{833.)21 1939 y(Stein)o(b)q(erg,)e(I.)e(R.)h(and)g(Solomon,)d(M.)j(\(1990\).)h (Searc)o(hing)g(Game)d(Trees)k(in)d(P)o(arallel.)i(In)f Fn(Pr)n(o)n(c)n(c)n(e)n(dings)h(of)h(the)f(1990)h(Inter-)21 1980 y(national)j(Confer)n(enc)n(e)f(on)h(Par)n(al)r(lel)e(Pr)n(o)n(c)n (essing)h(\(vol.)g(3\))p Fp(,)g(pp.)f(9{17,)f(Univ)o(ersit)o(y)h(P)o (ark,)g(P)m(A.)g(P)o(enn.)g(State)h(Univ)o(ersit)o(y)21 2022 y(Press.)21 2096 y(Sto)q(c)o(kman,)f(G.)i(C.)f(\(1979\).)21 b(A)16 b(Minimax)c(Algorithm)h(Better)k(than)e(Alpha-Beta?)30 b Fn(A)o(rti\014cial)14 b(Intel)r(ligenc)n(e)p Fp(,)h(V)m(ol.)f(12,)21 2138 y(pp.)f(179{196.)21 2213 y(V)m(orn)o(b)q(erger,)18 b(O.)f(and)f(Monien,)i(B.)e(\(1987\).)27 b(P)o(arallel)16 b(Alpha-Beta)h(v)o(ersus)h(Parallel)e(SSS*.)27 b(In)17 b Fn(Pr)n(o)n(c)n(e)n(e)n(dings)g(of)h(the)21 2254 y(IFIP)d(Confer)n (enc)n(e)g(on)g(Distribute)n(d)f(Pr)n(o)n(c)n(essing)p Fp(,)g(pp.)f(613{625.)f(North)i(Holland.)21 2329 y(W)m(eill,)k(J.-C.)g (\(1995\).)32 b Fn(Pr)n(o)n(gr)n(ammes)18 b(d')o(\023)-20 b(eche)n(cs)20 b(de)g(championnat:)29 b(ar)n(chite)n(ctur)n(e)19 b(lo)n(giciel)r(le)f(synth)o(\022)-20 b(ese)20 b(de)g(fonctions)21 2370 y(d')o(\023)-20 b(evaluations,)15 b(p)n(ar)n(al)r(l)o(\023)-20 b(elisme)13 b(de)j(r)n(e)n(cher)n(che)p Fp(.)h(Ph.D.)c(thesis,)h(Univ)o (ersit)o(\023)-20 b(e)15 b(P)o(aris)f(8.)21 2445 y(W)m(eill,)d(J.-C.)h (\(1996\).)k(The)e(ABD)o(AD)o(A)f(Distributed)g(Minimax-Searc)o(h)f (Algorithm.)i Fn(ICCA)g(Journal)p Fp(,)e(V)m(ol.)g(19,)g(No.)h(1,)21 2487 y(pp.)g(3{16.)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF