%!PS-Adobe-2.0%%Creator: dvipsk 5.58f Copyright 1986, 1994 Radical Eye Software%%Title: aphidcut.dvi%%Pages: 5%%PageOrder: Ascend%%BoundingBox: 0 0 612 792%%DocumentFonts: Times-Bold Times-Roman Times-Italic Helvetica-Bold%%+ Courier%%EndComments%DVIPSCommandLine: dvips aphidcut%DVIPSParameters: dpi=300, compressed, comments removed%DVIPSSource:  TeX output 1996.07.17:1230%%BeginProcSet: texc.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 72mul 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 scaleisls{landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 divhsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mulTR[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 Nstring /base X array /BitMaps X /BuildChar{CharBuilder}N /Encoding IE Nend 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 duplength 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 subget 127 sub}B /ch-dx{ch-data dup length 1 sub get}B /ch-image{ch-datadup 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-dx0 ch-xoff ch-yoff ch-height sub ch-xoff ch-width add ch-yoffsetcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-yoff.1 sub]/id ch-image N /rw ch-width 7 add 8 idiv string N /rc 0 N /gp 0 N/cp 0 N{rc 0 ne{rc 1 sub /rc X rw}{G}ifelse}imagemask restore}B /G{{idgp get /gp gp 1 add N dup 18 mod S 18 idiv pl S get exec}loop}B /adv{cpadd /cp X}B /chg{rw cp id gp 4 index getinterval putinterval dup gp add/gp X adv}B /nd{/cp 0 N rw exit}B /lsh{rw cp 2 copy get dup 0 eq{pop 1}{dup 255 eq{pop 254}{dup dup add 255 and S 1 and or}ifelse}ifelse put 1adv}B /rsh{rw cp 2 copy get dup 0 eq{pop 128}{dup 255 eq{pop 127}{dup 2idiv S 128 and or}ifelse}ifelse put 1 adv}B /clr{rw cp 2 index stringputinterval adv}B /set{rw cp fillstr 0 4 index getinterval putintervaladv}B /fillstr 18 string 0 1 17{2 copy 255 put pop}for N /pl[{adv 1 chg}{adv 1 chg nd}{1 add chg}{1 add chg nd}{adv lsh}{adv lsh nd}{adv rsh}{adv rsh nd}{1 add adv}{/rc X nd}{1 add set}{1 add clr}{adv 2 chg}{adv 2chg nd}{pop nd}]dup{bind pop}forall N /D{/cc X dup type /stringtype ne{]}if nn /base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{dup duplength 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 @rigin0 0 moveto /V matrix currentmatrix dup 1 get dup mul exch 0 get dup muladd .99 lt{/QV}{/RV}ifelse load def pop pop}N /eop{SI restore userdict/eop-hook known{eop-hook}if showpage}N /@start{userdict /start-hookknown{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}for65781.76 div /vsize X 65781.76 div /hsize X}N /p{show}N /RMat[1 0 0 -1 00]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 7getinterval 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 falseRMat{BDot}imagemask grestore}}{{gsave TR -.1 .1 TR rulex ruley scale 1 1false RMat{BDot}imagemask grestore}}ifelse B /QV{gsave newpath transformround exch round exch itransform moveto rulex 0 rlineto 0 ruley negrlineto 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 pa}B /bos{/SS save N}B /eos{SS restore}B end%%EndProcSet%%BeginProcSet: texps.proTeXDict begin /rf{findfont dup length 1 add dict begin{1 index /FID ne 2index /UniqueID ne and{def}{pop pop}ifelse}forall[1 index 0 6 -1 rollexec 0 exch 5 -1 roll VResolution Resolution div mul neg 0 0]/Metricsexch def dict begin Encoding{exch dup type /integertype ne{pop pop 1 subdup 0 le{pop}{[}ifelse}{FontMatrix 0 get div Metrics 0 get div def}ifelse}forall Metrics /Metrics currentdict end def[2 index currentdictend definefont 3 -1 roll makefont /setfont load]cvx def}def/ObliqueSlant{dup sin S cos div neg}B /SlantFont{4 index mul add}def/ExtendFont{3 -1 roll mul exch}def /ReEncodeFont{/Encoding exch def}defend%%EndProcSet%%BeginProcSet: special.proTeXDict begin /SDict 200 dict N SDict begin /@SpecialDefaults{/hs 612 N/vs 792 N /ho 0 N /vo 0 N /hsc 1 N /vsc 1 N /ang 0 N /CLIP 0 N /rwiSeenfalse N /rhiSeen false N /letter{}N /note{}N /a4{}N /legal{}N}B/@scaleunit 100 N /@hscale{@scaleunit div /hsc X}B /@vscale{@scaleunitdiv /vsc X}B /@hsize{/hs X /CLIP 1 N}B /@vsize{/vs X /CLIP 1 N}B /@clip{/CLIP 2 N}B /@hoffset{/ho X}B /@voffset{/vo X}B /@angle{/ang X}B /@rwi{10 div /rwi X /rwiSeen true N}B /@rhi{10 div /rhi X /rhiSeen true N}B/@llx{/llx X}B /@lly{/lly X}B /@urx{/urx X}B /@ury{/ury X}B /magscaletrue def end /@MacSetUp{userdict /md known{userdict /md get type/dicttype eq{userdict begin md length 10 add md maxlength ge{/md md duplength 20 add dict copy def}if end md begin /letter{}N /note{}N /legal{}N /od{txpose 1 0 mtx defaultmatrix dtransform S atan/pa X newpathclippath mark{transform{itransform moveto}}{transform{itransform lineto}}{6 -2 roll transform 6 -2 roll transform 6 -2 roll transform{itransform 6 2 roll itransform 6 2 roll itransform 6 2 roll curveto}}{{closepath}}pathforall newpath counttomark array astore /gc xdf pop ct 390 put 10 fz 0 fs 2 F/|______Courier fnt invertflag{PaintBlack}if}N/txpose{pxs pys scale ppr aload pop por{noflips{pop S neg S TR pop 1 -1scale}if xflip yflip and{pop S neg S TR 180 rotate 1 -1 scale ppr 3 getppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg TR}if xflip yflipnot and{pop S neg S TR pop 180 rotate ppr 3 get ppr 1 get neg sub neg 0TR}if yflip xflip not and{ppr 1 get neg ppr 0 get neg TR}if}{noflips{TRpop pop 270 rotate 1 -1 scale}if xflip yflip and{TR pop pop 90 rotate 1-1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub negTR}if xflip yflip not and{TR pop pop 90 rotate ppr 3 get ppr 1 get negsub neg 0 TR}if yflip xflip not and{TR pop pop 270 rotate ppr 2 get ppr0 get neg sub neg 0 S TR}if}ifelse scaleby96{ppr aload pop 4 -1 roll add2 div 3 1 roll add 2 div 2 copy TR .96 dup scale neg S neg S TR}if}N /cp{pop pop showpage pm restore}N end}if}if}N /normalscale{Resolution 72div VResolution 72 div neg scale magscale{DVImag dup scale}if 0 setgray}N /psfts{S 65781.76 div N}N /startTexFig{/psf$SavedState save N userdictmaxlength dict begin /magscale true def normalscale currentpoint TR/psf$ury psfts /psf$urx psfts /psf$lly psfts /psf$llx psfts /psf$y psfts/psf$x psfts currentpoint /psf$cy X /psf$cx X /psf$sx psf$x psf$urxpsf$llx sub div N /psf$sy psf$y psf$ury psf$lly sub div N psf$sx psf$syscale psf$cx psf$sx div psf$llx sub psf$cy psf$sy div psf$ury sub TR/showpage{}N /erasepage{}N /copypage{}N /p 3 def @MacSetUp}N /doclip{psf$llx psf$lly psf$urx psf$ury currentpoint 6 2 roll newpath 4 copy 4 2roll moveto 6 -1 roll S lineto S lineto S lineto closepath clip newpathmoveto}N /endTexFig{end psf$SavedState restore}N /@beginspecial{SDictbegin /SpecialSave save N gsave normalscale currentpoint TR@SpecialDefaults count /ocount X /dcount countdictstack N}N /@setspecial{CLIP 1 eq{newpath 0 0 moveto hs 0 rlineto 0 vs rlineto hs neg 0 rlinetoclosepath clip}if ho vo TR hsc vsc scale ang rotate rwiSeen{rwi urx llxsub div rhiSeen{rhi ury lly sub div}{dup}ifelse scale llx neg lly neg TR}{rhiSeen{rhi ury lly sub div dup scale llx neg lly neg TR}if}ifelseCLIP 2 eq{newpath llx lly moveto urx lly lineto urx ury lineto llx urylineto closepath clip}if /showpage{}N /erasepage{}N /copypage{}N newpath}N /@endspecial{count ocount sub{pop}repeat countdictstack dcount sub{end}repeat grestore SpecialSave restore end}N /@defspecial{SDict begin}N /@fedspecial{end}B /li{lineto}B /rl{rlineto}B /rc{rcurveto}B /np{/SaveX currentpoint /SaveY X N 1 setlinecap newpath}N /st{stroke SaveXSaveY moveto}N /fil{fill SaveX SaveY moveto}N /ellipse{/endangle X/startangle X /yrad X /xrad X /savematrix matrix currentmatrix N TR xradyrad scale 0 0 1 startangle endangle arc savematrix setmatrix}N end%%EndProcSetTeXDict begin 40258431 52099146 1000 300 300 (aphidcut.dvi)@start /Fa 2 13 df<EA01F038070C08380C0E10EA1807123000701320126000E01340A214801400A3EA601B383063A0380F81C015107F8F19>11 D<EB03C0EB0C301310EB203813401380EA0100A2000213701460EB1FC0131138041F60EB0070A35AA31460001813E014C0EB018038140300EA230EEA20F890C7FCA25AA45A1521809916>IE /Fb 61[12 12 70[15 17 17 1[17 19 10 15 15 1[19 19 1927 10 2[10 19 19 10 17 19 17 19 19 13[19 2[23 2[31 2[1712 3[23 27 25 1[23 6[12 5[19 6[12 9 4[12 39[{}38 37.500000/Times-Italic rf /Fc 55[12 5[12 16[19 54[17 19 19 2719 19 10 15 12 1[19 19 19 29 10 19 1[10 19 19 12 17 1917 19 17 3[12 1[12 3[35 27 27 23 21 25 1[21 27 1[33 1[2715 12 27 27 21 23 27 25 25 27 6[10 19 19 19 19 19 1919 19 19 19 1[9 12 9 2[12 12 40[{}65 37.500000 /Times-Romanrf /Fd 1 111 df<EA30F8EA590C124E129C12981218A2EA301813191331A2EA6032131C100D7F8C15>110 D E /Fe 23 119 df<1380EA0100120212065AA25AA25AA35AA412E0AC1260A47EA37EA27EA27E12027EEA0080092A7C9E10>40 D<7E12407E12307EA27EA27EA37EA41380AC1300A41206A35AA25AA25A12205A5A092A7E9E10>I<1306ADB612E0A2D80006C7FCAD1B1C7E9720>43 D<5A1207123F12C71207B3A5EAFFF80D1C7C9B15>49D<EA07C0EA1830EA201CEA400C130EEAF00F12F81307A21270EA000F130EA2131CA213381370136013C0EA0180EA0300EA0601120C1218EA1002EA3FFE127F12FF101C7E9B15>I<130CA2131C133CA2135C13DC139CEA011C120312021204120C1208121012301220124012C0B512C038001C00A73801FFC0121C7F9B15>52 D<007FB512C0B612E0C9FCA8B612E06C14C01B0C7E8F20>61 D<EA1FC0EA3070EA78387F12301200A2EA01FCEA0F1C12381270126000E01340A3EA603C38304E80381F870012127E9115>97 D<EB1F801303AAEA03F3EA0E0BEA1807EA30031270126012E0A6126012701230EA1807EA0E1B3803E3F0141D7F9C17>100 D<EA07E0EA0C30EA1818EA300CEA700EEA600612E0EAFFFEEAE000A41260EA70021230EA1804EA0C18EA03E00F127F9112>I<12FC121CAA137C1387EA1D03001E1380121CAD38FF9FF0141D7F9C17>104 D<1218123CA21218C7FCA712FC121CB0EAFF80091D7F9C0C>I<12FC121CB3A9EAFF80091D7F9C0C>108 D<39FC7E07E0391C838838391D019018001EEBE01C001C13C0AD3AFF8FF8FF8021127F9124>I<EAFC7CEA1C87EA1D03001E1380121CAD38FF9FF014127F9117>I<EA03F0EA0E1CEA1806487E00701380EA600100E013C0A600601380EA700300301300EA1806EA0E1CEA03F012127F9115>I<EAFC7CEA1D87381E0180001C13C0EB00E0A21470A614E0A2EB01C0001E1380381D0700EA1CFC90C7FCA7B47E141A7F9117>I<3803E080EA0E19EA1805EA3807EA7003A212E0A61270A2EA38071218EA0E1BEA03E3EA0003A7EB1FF0141A7F9116>I<EAFCE0EA1D38EA1E78A2EA1C301300ACEAFFC00D127F9110>I<EA1F90EA2070EA4030EAC010A212E0EAF800EA7F80EA3FE0EA0FF0EA00F8EA8038131812C0A2EAE010EAD060EA8FC00D127F9110>I<1204A4120CA2121C123CEAFFE0EA1C00A91310A5120CEA0E20EA03C00C1A7F9910>I<38FC1F80EA1C03AD1307120CEA0E1B3803E3F014127F9117>I<38FF07E0383C0380381C0100A2EA0E02A2EA0F06EA0704A2EA0388A213C8EA01D0A2EA00E0A3134013127F9116>I E /Ff173[25 82[{}1 41.666668 /Courier rf /Fg 134[23 2[23 2514 23 16 1[25 25 25 1[12 2[12 25 25 14 23 25 23 1[2313[28 2[28 32 3[30 1[12 30 1[25 1[30 2[30 13[23 23 232[12 46[{}31 41.666668 /Helvetica-Bold rf /Fh 137[231[15 18 20 1[25 23 25 38 13 2[13 25 1[15 20 2[25 23 12[3025 2[28 36 1[43 3[18 36 3[33 2[33 12[23 23 23 23 2[1146[{}29 45.833332 /Times-Bold rf /Fi 134[17 1[24 2[913 11 1[17 17 17 26 9 2[9 17 17 11 15 17 2[15 12[20 35[171[8 11 8 44[{}22 33.333332 /Times-Roman rf /Fj 1 50 df<1218127812981218AC12FF08107D8F0F>49 D E /Fk 2 4 df<B61280A219027D8A20>0D<1203A4EAC30CEAE31CEA7338EA1FE0EA0780A2EA1FE0EA7338EAE31CEAC30CEA0300A40E127D9215>3 D E /Fl 1 49 df<1204120EA2121CA31238A212301270A21260A212C0A2070F7F8F0A>48 D E /Fm 1 50 df<120C121C12EC120CAFEAFFC00A137D9211>49D E /Fn 69[18 8[21 1[23 23 3[18 47[18 21 21 30 21 2112 16 14 21 21 21 21 32 12 21 12 12 21 21 14 18 21 1821 18 3[14 1[14 1[30 1[39 30 30 25 23 28 1[23 30 30 3725 30 16 14 30 30 23 25 30 28 28 30 5[12 12 21 21 2121 21 21 21 21 21 21 12 10 14 10 2[14 14 14 1[35 37[{}7641.666668 /Times-Roman rf /Fo 10 123 df<13F8EA030C380E0604EA1C07383803080030138800701390A200E013A0A214C01480A3EA6007EB0B8838307190380F80E016127E911B>11 D<EB01F0EB0618EB080C1310EB200E13401380141CEA01001418143838020FF0EB10C0EB0FE0EB00305AA21438A2481370A314E01218EB01C000141380EB0300EA230EEA20F890C7FCA25AA45AA217257F9C17>I<90B512E09038F001C03901C003809038800700EB000E141E0002131C5C5CC75A495A495A49C7FC5B131E131C5BEB7002495AEA01C0EA038048485A5A000E1318485B48137048485AB5FC1B1C7E9B1C>90 D<EA01E3EA0717EA0C0F1218EA380E12301270A2485AA4EB3880A3EA607838319900EA1E0E11127E9116>97D<EB07E01300A2EB01C0A4EB0380A43801E700EA0717EA0C0F1218EA380E12301270A2485AA4EB3880A3EA607838319900EA1E0E131D7E9C16>100 D<EB38C013C5EA0183EA0303000713801206120EA2381C0700A4130EA3EA0C1EEA047CEA039CEA001CA25B1260EAF0301370EAE0C0007FC7FC121A809114>103 D<EA3C1F384E6180384681C0EA4701128F128E120EA2381C0380A3EB070000381310A2130E1420387006403830038014127E9119>110D<001C13C0EA27011247A238870380A2120EA2381C0700A438180E20A3EA1C1E380C26403807C38013127E9118>117 D<001CEBC080392701C1C0124714C03987038040A2120EA2391C070080A3EC0100EA1806A2381C0E02EB0F04380E13083803E1F01A127E911E>119D<EA0381EA07C1EA0FF6EA081CEA1008EA0010132013401380EA010012025AEA08041210EA3C18EA67F8EA43F0EA81E010127E9113>122 D E /Fp 133[1618 1[28 18 21 12 16 16 1[21 21 21 30 12 18 1[12 21 2112 18 21 18 21 21 7[23 1[35 2[23 1[25 1[25 30 5[14 303[30 1[25 25 18[10 14 10 2[14 14 40[{}39 41.666668 /Times-Italicrf /Fq 135[25 36 1[28 17 19 22 1[28 25 28 41 14 28 1[1428 25 17 22 28 22 28 25 9[50 2[33 1[36 1[30 6[19 39 1[3033 36 36 1[36 11[25 25 25 25 25 2[12 46[{}38 50.000000/Times-Bold rf /Fr 2 104 df<EB03C0EB1E0013385B5BB1485A485A000FC7FC12F8120FEA03806C7E6C7EB113707F131EEB03C012317DA419>102 D<12F8120FEA03806C7E6C7EB113707F131EEB03C0EB1E0013385B5BB1485A485A000FC7FC12F812317DA419>IE /Fs 134[25 2[25 25 14 19 17 1[25 25 25 39 14 25 1414 25 25 17 22 25 22 25 22 11[36 30 28 5[44 2[19 1[3636 1[30 36 33 33 36 46 9[25 3[25 25 2[12 1[12 44[{}4050.000000 /Times-Roman rf /Ft 2 13 df<EB0FC0EB70709038C038013803801C3907001E02000E130E001E130F001C1404123C00381408127815105A15201540A21580481400A3127014170030EB67043918018788380C0E033903F000F0201A7D9925>11D<EC03F0EC0C1CEC300EEC4006EC8007EB010013025B150F5BA249130E151E49131C153815309038403F60EC41C0EC3F60EC0070491338A3153C48C7FCA400021478A31570000614F015E0140115C00009EB0380EC07003808800EEB401C38103070EB0FC090C8FCA25AA45AA45AA220367FA921>I E /Fu 139[20 1[27 2[30 1[50 17 2[1733 30 1[27 1[27 1[30 12[40 33 2[37 6[23 47 3[43 2[4365[{}18 59.999973 /Times-Bold rf end%%EndProlog%%BeginSetup%%Feature: *Resolution 300dpiTeXDict begin%%EndSetup%%Page: 1 11 0 bop 400 187 a Fu(The)14 b(APHID)h(Parallel)d Ft(\013\014)19b Fu(Sear)o(ch)14 b(Algorithm)487 345 y Fs(Mark)e(G.)h(Brockington)e(and)i(Jonathan)f(Schaef)o(fer)368 403 y(Department)g(of)g(Computing)f(Science,)i(University)f(of)g(Alberta)567 461 y(Edmonton,)h(Alberta)f(T6G)g(2H1)h(Canada)602 519 y Fr(f)p Fs(brock,)f(jonathan)pFr(g)p Fs(@cs.ualberta.ca)308 694 y Fq(Abstract)-41 794y Fp(This)j(paper)g(intr)n(oduces)h(the)f(APHID)i(\(Asynchr)n(onous)f(Par)o(-)-91 844 y(allel)g(Hierar)n(chical)i(Iterative)f(Deepening\))g(game-tr)n(ee)h(sear)n(ch)-91 894 y(algorithm.)36 b(APHID)19b(r)n(epr)n(esents)i(a)d(departur)n(e)h(fr)n(om)g(the)f(ap-)-91944 y(pr)n(oaches)12 b(used)f(in)g(practice.)17 b(Instead)11b(of)g(parallelism)e(based)j(on)-91 993 y(the)k(minimal)f(sear)n(ch)j(tr)n(ee,)i(APHID)d(uses)g(a)g(truncated)e(game-)-911043 y(tr)n(ee)f(and)f(all)g(of)g(the)g(leaves)h(of)f(that)g(tr)n(ee)h(ar)n(e)h(sear)n(ched)g(in)e(par)o(-)-91 1093 y(allel.)24b(APHID)14 b(has)g(been)g(pr)n(ogrammed)g(as)g(an)f(easy)i(to)e(imple-)-91 1143 y(ment,)c(game-independent)f Fo(\013\014)k Fp(library)n(,)d(and)f(has)h(been)h(tested)f(on)-91 1193 y(several)g(game-playing)d(pr)n(ograms.)13 b(Results)8 b(for)g(an)g(Othello)e(pr)n(o-)-911242 y(gram)h(ar)n(e)h(pr)n(esented)g(her)n(e.)14 b(The)8b(algorithm)t(yields)f(good)g(parallel)-91 1292 y(performance)k(on)f(a)g(network)h(of)f(workstations,)f(without)g(using)g(a)-911342 y(shar)n(ed)i(transposition)c(table.)-91 1485 yFq(1.)13 b(Intr)o(oduction)-41 1567 y Fn(The)f(alpha-beta)g(\()pFo(\013\014)r Fn(\))g(minimax)g(tree)g(search)h(algorithm)e(has)-911612 y(proven)h(to)h(be)g(a)h(dif)o(\256cult)e(algorithm)f(to)i(parallelize.)22 b(Although)-91 1658 y(simulations)8b(predict)g(excellent)h(parallel)g(performance,)i(most)e(re-)-911704 y(sults)k(are)h(based)g(on)f(an)h(unreasonable)g(set)f(of)g(assumptions.)24 b(In)-91 1749 y(practice,)12 b(knowing)d(where)j(to)e(initiate)g(parallel)g(activity)g(is)h(dif)o(\256-)-911795 y(cult)g(since)g(the)h(result)e(of)i(searching)f(one)h(node)f(at)g(a)h(branch)g(may)-91 1841 y(obviate)d(the)h(parallel)g(work)g(of)g(the)g(other)g(branches.)-41 1886 y(In)d(real-world)f(implementations,)h(such)h(as)g(high)e(performance)-91 1932 y(chess,)20b(checkers)f(and)e(Othello)f(game-playing)h(programs,)i(the)-911978 y(programs)13 b(suf)o(fer)h(from)f(three)h(major)f(sources)h(of)g(parallel)f(inef-)-91 2023 y(\256ciency)e(\(a)f(similar)g(model)g(is)g(presented)h(in)e([6]\).)-41 2069 y(The)15 b(\256rst)f(is)gFp(synchr)n(onization)f(over)o(head)p Fn(.)27 b(The)15b(search)g(typ-)-91 2115 y(ically)g(has)g(many)h(synchronization)e(points)g(where)i(there)f(is)h(no)-91 2160 y(work)d(available,)i(which)f(results)g(in)f(a)h(high)f(percentage)i(of)f(idle)-912206 y(time.)-41 2252 y(The)c(second)f(is)g Fp(parallelization)d(over)o(head)p Fn(.)15 b(This)9 b(is)g(the)g(over)o(-)-91 2297y(head)g(of)f(incorporating)e(the)j(parallel)f(algorithm,)g(which)g(includes)-91 2343 y(the)i(handling)g(of)g(communication,)h(and)g(maintaining)e(structures)-91 2389 y(to)g(allow)h(for)g(allocation)f(of)h(work.)-41 2434 y(The)i(third)d(is)i Fp(sear)n(ch)i(over)o(head)pFn(.)18 b(Search)12 b(trees)g(are)g(really)f(di-)-912480 y(rected)k(graphs.)26 b(W)m(ork)13 b(performed)h(on)g(one)h(processor)f(may)h(be)-91 2526 y(useful)c(to)h(the)g(computations)f(of)g(another)h(processor)n(.)19 b(If)12 b(this)f(in-)-912571 y(formation)c(is)h(not)g(available,)h(unnecessary)h(search)f(may)g(be)g(done.)-41 2617 y(These)j(overheads)g(are)h(not)d(independent)h(of)g(each)i(other)n(.)k(For)-91 2662 y(example,)24 b(increased)e(communication)e(can)i(help)e(reduce)h(the)987 694 y(search)13b(overhead.)20 b(Reducing)11 b(the)h(number)f(of)h(synchronization)987740 y(points)i(can)j(increase)g(the)e(search)i(overhead.)31b(In)16 b(practice,)i(the)987 786 y(right)7 b(balance)i(between)g(these)g(sources)h(of)e(program)g(inef)o(\256ciency)987831 y(is)13 b(dif)o(\256cult)f(to)g(\256nd,)i(and)f(one)g(usually)f(performs)h(many)h(experi-)987 877 y(ments)c(to)g(\256nd)g(the)g(right)f(trade-of)o(fs)h(to)f(maximize)i(performance.)1037 924y(Many)g(parallel)g Fo(\013\014)j Fn(algorithms)c(have)i(appeared)g(in)f(the)g(liter)o(-)987 970 y(ature)g(\(a)g(more)g(complete)f(list)g(is)g(available)h(elsewhere)g([1]\).)k(The)987 1015 y(PV)l(-Split)10b(algorithm)g(recognized)h(that)g(some)h(nodes)f(exist)g(in)g(the)9871061 y(search)h(tree)f(where,)h(having)e(searched)j(the)e(\256rst)f(branch)h(sequen-)987 1107 y(tially)m(,)c(the)g(remaining)g(branches)h(can)g(be)f(searched)i(in)e(parallel)g([5)o(].)987 1152y(Initiating)h(parallelism)i(along)h(the)f(best)h(line)f(of)h(play)m(,)g(the)f Fp(princi-)987 1198 y(pal)i(variation)p Fn(,)h(was)g(ef)o(fective)h(for)f(a)g(small)g(number)g(of)g(proces-)9871244 y(sors,)g(although)d(variations)h(on)h(this)f(scheme)j(seemed)f(limited)e(to)987 1289 y(speedups)f(of)g(less)h(than)f(8)g([7].)10371336 y(The)15 b(idea)f(can)h(be)f(generalized)h(to)e(other)h(nodes)g(in)g(the)g(tree.)987 1382 y(At)f(nodes)g(where)h(the)g(\256rst)f(branch)h(has)f(been)h(searched)h(and)f(no)987 1427 y(cut-of)o(f)h(occurred,)i(the)e(rest)g(can)h(likely)e(be)i(searched)h(in)d(paral-)987 1473 y(lel.)32 b(It)16 b(is)g(a)g(trade-of)o(f)g(\261)g(increased)i(parallelism)e(versus)g(addi-)987 1519 y(tional)h(search)i(overhead,)i(since)e(one)f(of)g(these)g(parallel)g(tasks)987 1564y(could)10 b(cause)h(a)g(cut-of)o(f.)j(This)c(idea)h(has)g(been)g(tried)f(by)g(a)g(number)987 1610 y(of)h(researchers,)j(such)d(as)h(Jamboree)g(search)h([4)o(])e(and)h(ABDADA)987 1656 y([9].)26b(The)15 b(best-known)e(instance)h(of)g(this)g(type)g(of)g(algorithm)f(is)987 1701 y(called)8 b Fp(Y)l(oung)g(Br)n(others)h(W)l(ait)eFn(\(YBW\))h(and)g(was)h(implemented)f(in)987 1747 y(the)kFo(Z)s(ug)q(z)r(w)q(ang)i Fn(chess)g(program)e([3].)21b(YBW)12 b(achieved)h(a)g(344-)987 1793 y(fold)c(speedup)i(using)e(a)i(network)e(of)h(1024)f(T)o(ransputers.)1037 1839 y(This)h(class)h(of)e(algorithms)g(cannot)h(achieve)h(a)g(linear)e(speedup)9871885 y(primarily)i(due)i(to)f(synchronization)f(overhead;)i(the)f(search)i(tree)987 1931 y(may)k(have)g(thousands)f(of)g(synchronization)f(points)h(and)g(there)987 1976 y(are)10b(numerous)g(occasions)g(where)g(the)g(processes)h(are)f(starved)g(for)987 2022 y(work.)21 b(The)14 b(algorithms)d(have)j(low)e(search)i(overhead,)g(with)e(the)987 2068 y(absolute)c(performance)i(being)e(strongly)f(linked)h(to)g(the)g(quality)g(of)987 2113y(the)i(move)h(ordering)e(within)f(the)i(game-tree.)10372160 y(This)f(paper)h(introduces)f(the)h(Asynchronous)f(Parallel)g(Hierar)o(-)987 2206 y(chical)g(Iterative)g(Deepening)g(\(APHID\))g(game-tree)h(search)g(algo-)987 2252 y(rithm.)26 b(The)15b(algorithm)f(represents)h(a)g(departure)f(from)h(the)f(ap-)9872297 y(proaches)j(used)g(in)g(practice.)34 b(In)16 b(contrast)h(to)f(other)g(schemes,)987 2343 y(APHID)e(de\256nes)g(a)g(frontier)f(\(a)h(\256xed)f(number)h(of)g(moves)g(away)987 2389 y(from)e(the)g(root)f(of)g(the)h(search)i(tree\),)f(and)f(all)f(nodes)h(at)g(the)g(fron-)9872434 y(tier)c(are)i(done)f(in)f(parallel.)14 b(Each)c(worker)f(process)g(is)g(assigned)g(an)987 2480 y(equal)h(number)f(of)g(frontier)f(nodes)i(to)f(search.)15 b(The)10 b(workers)g(con-)987 2526y(tinually)d(search)j(these)g(nodes)f(deeper)h(and)f(deeper)n(,)i(never)e(having)987 2571 y(to)h(synchronize)g(with)f(a)h(controlling)e(master)j(process.)k(The)c(mas-)987 2617 y(ter)c(process)h(repeatedly)f(searches)i(to)e(the)g(frontier)f(to)g(get)i(the)f(latest)9872663 y(search)12 b(results.)i(In)d(this)e(way)m(,)j(there)f(is)f(ef)o(fectively)h(no)f(idle)g(time;)p eop%%Page: 2 22 1 bop -91 42 a Fn(search)14 b(inef)o(\256ciencies)g(are)f(primarily)f(due)h(to)g(search)h(overhead.)-91 87 y(APHID')n(s)c(performance)h(does)g(not)e(rely)h(on)g(the)h(implementation)-91 133y(of)h(a)i(distributed)c(transposition)h(table,)j(which)e(makes)i(the)f(algo-)-91 178 y(rithm)g(suitable)g(for)g(loosely-coupled)f(architectures)i(\(such)f(as)i(a)-91 224 y(network)c(of)h(workstations\),)f(as)i(well)f(as)g(tightly-coupled)d(archi-)-91270 y(tectures.)-41 323 y(Unlike)f(some)i(parallel)fFo(\013\014)j Fn(algorithms,)d(APHID)g(is)h(designed)-91369 y(to)e(\256t)g(into)f(a)i(sequential)e Fo(\013\014)kFn(structure.)i(APHID)8 b(has)h(been)g(imple-)-91 415y(mented)k(as)h(a)g(game-independent)f(library)g(of)g(routines.)22b(These,)-91 460 y(combined)10 b(with)f(application-dependent)f(routines)h(that)h(the)g(user)-91 506 y(supplies,)k(allow)f(a)h(sequential)f Fo(\013\014)j Fn(program)d(to)g(be)h(easily)f(con-)-91551 y(verted)7 b(to)f(a)i(parallel)f(program.)13 b(Although)5b(most)i(parallel)f Fo(\013\014)k Fn(pro-)-91 597 y(grams)d(take)g(months)g(to)f(develop,)h(the)g(game-independent)g(library)-91643 y(allows)14 b(users)h(to)f(integrate)g(parallelism)g(into)g(their)g(application)-91 688 y(with)9 b(only)g(a)i(few)g(hours)e(of)h(work.)-91807 y Fq(2.)j(The)f(APHID)h(Algorithm)-41 913 y Fn(Y)l(oung)g(Brothers)h(W)m(ait)g(and)g(other)g(similar)g(algorithms)g(suf-)-91959 y(fer)f(from)h(three)f(serious)h(problems.)23 b(First,)14b(the)f(numerous)h(syn-)-91 1004 y(chronization)8 b(points)h(and)h(occasions)g(where)g(there)g(is)g(little)e(or)i(no)-911050 y(work)e(to)h(be)g(done)g(in)f(parallel)h(result)f(in)h(idle)f(time.)14 b(This)8 b(suggests)-91 1096 y(that)h(a)h(new)g(algorithm)e(must)h(strive)g(to)g(reduce)h(or)g(eliminate)f(syn-)-911141 y(chronization)i(and)h(small)h(work)e(lists.)20b(Second,)14 b(the)e(chaotic)g(na-)-91 1187 y(ture)h(of)f(a)i(work-stealing)d(scheduler)i(requires)g(algorithms)f(such)-911233 y(as)i(YBW)g(and)g(Jamboree)h(to)e(use)h(a)g(shared)g(transposition)d(table)-91 1278 y(to)c(achieve)h(good)e(move)i(ordering)e(and)h(reasonable)h(performance.)-91 1324y(ABDADA)j(requires)g(a)h(shared)g(transposition)d(table)i(to)g(function)-91 1370 y(correctly)m(.)33 b(Third,)17 b(the)g(program)f(may)h(initiate)e(parallelism)h(at)-91 1415 y(nodes)8b(which)f(are)i(better)e(done)h(sequentially)m(.)k(For)c(example,)h(hav-)-91 1461 y(ing)d(searched)i(the)f(\256rst)g(branch)g(at)g(a)g(node)g(and)g(not)f(achieved)i(a)g(cut-)-91 1507 y(of)o(f,)g(Y)l(oung)f(Brothers)f(W)m(ait)i(\(in)f(its)g(simplest)g(form\))g(permits)g(all)h(of)-91 1552 y(the)g(remaining)g(branches)h(to)f(be)h(searched)g(in)f(parallel.)13 b(However)n(,)-91 1598 y(if)d(the)g(second)h(branch,)h(for)e(example,)i(causes)g(a)f(cut-of)o(f,)f(then)h(all)-911644 y(the)c(parallel)g(work)g(has)h(been)g(wasted.)13b(This)8 b(suggests)f(parallelism)-91 1689 y(should)i(only)h(be)h(initiated)e(at)i(nodes)g(where)g(there)g(is)f(a)i(very)e(high)-911735 y(probability)d(that)j(all)g(branches)h(must)f(be)g(considered.)-41 1788 y(This)g(section)h(introduces)f(the)h(Asynchronous)f(Parallel)g(Hier)o(-)-91 1834 y(archical)h(Iterative)g(Deepening)g(\(APHID\))f(game-tree)i(searching)-91 1880 y(algorithm.)k(APHID)11b(has)h(been)g(designed)f(to)g(address)h(the)f(above)-911925 y(three)f(issues.)k(The)c(algorithm)f(is)g(asynchronous)h(in)f(nature;)g(it)g(re-)-91 1971 y(moves)15 b(all)f(synchronization)f(points)g(from)i(the)f Fo(\013\014)j Fn(search)f(and)-912017 y(from)11 b(iterative)g(deepening.)18 b(Also,)12b(parallelism)g(is)f(only)g(applied)-91 2062 y(at)e(nodes)g(that)f(have)i(a)f(high)f(probability)e(of)j(needing)f(parallelism.)-912108 y(The)g(top)f Fp(plies)128 2093 y Fm(1)154 2108y Fn(of)h(a)g(game-tree)h(near)f(the)f(root)g(vary)g(infrequently)-912154 y(between)13 b(steps)h(of)f(iterative)f(deepening.)23b(This)13 b(relative)g(invari-)-91 2199 y(ance)f(of)f(the)g(top)f(portion)g(of)h(the)g(game-tree)h(is)f(exploited)f(by)g(the)-912245 y(APHID)g(algorithm.)-41 2298 y(In)k(its)h(simplest)g(form,)h(APHID)f(can)h(be)g(viewed)f(as)h(a)f(mas-)-91 2344 y(ter/slave)8b(program)g(although,)g(as)h(discussed)g(later)n(,)g(it)f(can)h(be)f(gen-)-91 2390 y(eralized)19 b(to)e(a)i(hierarchical)f(processor)h(tree.)38 b(For)18 b(a)h(depth)f Fo(d)-91 2435 y Fn(search,)9b(the)f(master)g(is)g(responsible)f(for)g(the)g(top)gFo(d)640 2420 y Fl(0)659 2435 y Fn(ply)g(of)g(the)h(tree,)-912481 y(and)i(the)g(remaining)g Fo(d)e Fk(\000)h Fo(d)3122466 y Fl(0)334 2481 y Fn(ply)g(are)i(searched)g(in)f(parallel)g(by)f(the)-91 2527 y(slaves.)p -91 2585 394 2 v -49 2611 aFj(1)-31 2623 y Fi(The)e(ply)h(of)f(a)h(node)f(is)h(its)g(depth)f(within)h(the)f(game-tree,)g(starting)h(with)g(ply)g(0)-912662 y(at)g(the)g(root)g(of)g(the)g(game-tree.)987 42y Fh(2.1.)k(Operation)g(of)f(the)h(Master)g(in)g(APHID)1037123 y Fn(The)f(master)h(is)f(responsible)f(for)g(searching)h(the)g(top)f Fo(d)1850 107 y Fl(0)1873 123 y Fn(ply)g(of)987 168y(the)15 b(tree.)29 b(It)15 b(repeatedly)g(traverses)h(this)e(tree)i(until)d(the)i(correct)987 214 y(minimax)10 b(value)h(has)g(been)g(determined.)16 b(The)11 b(master)h(is)e(execut-)987259 y(ing)f(a)h(normal)g Fo(\013\014)i Fn(search,)f(with)e(the)g(exception)h(that)f(APHID)g(en-)987 305 y(forces)15 b(an)g(arti\256cial)f(search)i(horizon)e(at)g Fo(d)1639 290y Fl(0)1665 305 y Fn(ply)g(from)h(the)f(root.)987 351y(Each)j(leaf)g(node)f(in)f(the)i(master)r(')n(s)f Fo(d)1556336 y Fl(0)1583 351 y Fn(ply)g(game-tree)h(is)f(being)987396 y(asynchronously)c(searched)i(by)f(the)g(slaves.)23b(Before)13 b(describing)987 442 y(the)d(master)r(')n(s)g(stopping)e(condition,)g(we)i(must)g(\256rst)g(describe)g(how)987488 y(the)g(master)h(searches)h(the)e Fo(d)1403 473 yFl(0)1425 488 y Fn(ply)f(tree.)1037 534 y(When)f(the)h(master)g(reaches)h(a)f(leaf)g(of)f(the)g Fo(d)1678 519 y Fl(0)1698534 y Fn(ply)g(tree,)h(it)f(uses)h(a)987 580 y(reliable)h(or)f(approximate)h(value)g(for)f(the)h(leaf,)h(depending)e(on)h(the)987626 y(information)f(available.)15 b(If)c(a)g Fo(d)e Fk(\000)hFo(d)1532 610 y Fl(0)1554 626 y Fn(ply)g(search)i(result)e(is)h(avail-)987 671 y(able)e(from)f(the)h(slave,)h(that)e(will)f(be)i(used.)14b(However)n(,)c(if)e(the)g Fo(d)d Fk(\000)g Fo(d)1960656 y Fl(0)987 717 y Fn(ply)k(result)g(is)h(not)f(available,)h(then)g(the)f(algorithm)g(uses)h(the)g(deep-)987 762 y(est)e(search)i(result)d(that)h(has)g(been)h(returned)e(by)h(the)g(slave)h(to)e(gener)o(-)987808 y(ate)h(a)g(guessed)f(minimax)g(value.)14 b(Any)6b(node)i(where)f(we)h(are)g(forced)987 854 y(to)i(guess)g(are)h(marked)g(as)g Fp(uncertain)p Fn(.)1037 900 y(As)g(values)f(get)h(backed)g(up)g(the)f(tree,)i(the)e(master)i(maintains)e(a)987 946 y(count)i(of)g(how)g(many)g(uncertain)g(nodes)g(have)h(been)g(visited)e(in)h(a)987992 y(pass)f(over)g(the)f(tree.)16 b(As)11 b(long)e(as)i(the)g(score)g(at)g(any)g(of)f(the)h(leaves)987 1037 y(is)g(uncertain,)h(the)f(master)h(must)f(do)g(another)g(pass)h(over)f(the)h(tree.)9871083 y(Once)c(the)f(master)i(has)e(a)h(reliable)f(value)h(for)f(all)g(the)g(leaves)h(in)f(its)g Fo(d)1960 1068 y Fl(0)9871129 y Fn(ply)f(tree,)j(the)e(search)h(of)f(the)g Fo(d)gFn(ply)f(tree)i(is)f(complete.)13 b(The)8 b(control-)9871174 y(ling)g(program)h(would)f(then)g(proceed)i(to)e(the)h(next)g(iteration)e(by)i(in-)987 1220 y(crementing)g Fo(d)gFn(and)h(asking)f(the)g(master)h(to)f(search)h(the)f(tree)h(again.)10371266 y(The)15 b(slaves)g(are)g(responsible)f(for)f(setting)h(their)f(own)h(search)987 1312 y(windows,)j(based)g(on)g(information)d(from)i(the)h(master)n(.)33 b(Some-)987 1358 y(times,)9 b(the)g(information)e(returned)h(by)g(the)h(slave)g(may)g(not)f(be)h(use-)9871403 y(ful)j(to)g(the)h(master)n(.)22 b(For)13 b(example,)i(a)e(slave)g(can)h(tell)e(the)h(master)987 1449 y(that)e(the)h(score)h(of)f(a)h(given)e(node)h(is)g(less)h(than)f(30,)g(but)g(the)g(mas-)9871495 y(ter)e(may)g(want)f(to)h(know)f(if)g(the)g(score)i(is)e(in)h(between)g(-5)f(and)h(5.)k(In)987 1540 y(this)9 b(case,)j(a)f(\252bad)f(bound\272)f(search)j(is)d(generated,)i(and)f(the)g(search)9871586 y(window)e(parameters,)k Fo(\013)d Fn(and)h Fo(\014)rFn(,)h(must)e(be)h(communicated)h(to)e(the)987 1631 y(slave)j(processor)n(.)18 b(Any)11 b(nodes)h(where)g(we)g(are)h(waiting)d(for)h(\252bad)987 1677 y(bound\272)d(information)g(are)h(considered)g(as)h(uncertain)f(by)g(the)g(mas-)987 1723 y(ter)n(,)k(even)g(though)e(we)i(have)g(a)g(score)g(bound)e(for)h(the)g Fo(d)g Fk(\000)gFo(d)1894 1708 y Fl(0)1918 1723 y Fn(ply)987 1768 y(search.)24b(Eventually)m(,)14 b(the)f(slave)h(will)e(return)g(updated)h(informa-)987 1814 y(tion)7 b(that)i(is)f(consistent)g(with)g(both)g(the)g(original)f(information)g(and)987 1860 y(the)j(search)h(window)f(requested.)987 1941 y Fh(2.2.)i(The)g(APHID)f(T)l(able)10372022 y Fn(If)h(a)i(node)e(is)h(visited)e(by)i(the)f(master)i(for)e(the)h(\256rst)f(time,)i(it)e(is)987 2067 y(statically)d(allocated)h(to)f(a)i(slave)f(processor)n(.)k(This)c(information)e(is)9872113 y(recorded)13 b(in)g(a)h(table,)g(the)f Fp(APHID)h(table)pFn(,)f(that)f(is)h(shared)h(by)f(all)987 2159 y(processors.)j(Figure)10b(1)h(shows)f(an)i(example)f(of)g(how)f(the)g(APHID)9872204 y(table)g(would)f(be)i(or)o(ganized)f(at)g(a)h(given)f(point)f(in)g(time.)1037 2251 y(The)f(APHID)g(table)f(is)g(partitioned)f(into)g(two)h(parts:)12 b(one)c(which)987 2296 y(only)j(the)g(master)i(can)g(write)e(to,)h(and)g(one)g(which)f(only)g(the)h(slave)9872342 y(that)e(has)g(been)h(assigned)g(that)e(piece)i(of)f(work)g(can)h(write)f(to.)k(Any)987 2388 y(attempt)e(to)f(write)h(into)e(the)i(table)g(generates)h(a)g(message)h(that)d(in-)987 2433y(forms)e(the)f(slave)h(or)g(the)f(master)i(process)f(of)f(the)h(update)g(to)f(the)g(in-)987 2479 y(formation.)k(The)d(master)h(and)e(slave)h(only)e(read)i(their)f(local)g(copies)987 2525y(of)k(the)h(information;)e(there)i(are)g(no)f(explicit)f(messages)k(sent)d(be-)987 2570 y(tween)e(the)h(master)g(and)f(the)g(slave)h(asking)e(for)h(information.)1037 2617 y(The)18 b(master)r(')n(s)f(half)g(of)g(the)g(table)g(is)g(illustrated)e(above)j(the)9872662 y(dashed)12 b(line)e(in)h(Figure)g(1.)18 b(For)11b(each)h(leaf)g(that)f(has)h(been)g(visited)p eop%%Page: 3 33 2 bop -85 0 a 15345564 14208860 8420065 17234821 28417720 35653713 startTexFig -85 0 a%%BeginDocument: draw2.ps/arrowHeight 10 def/arrowWidth 5 def/IdrawDict 51 dict defIdrawDict begin/reencodeISO {dup dup findfont dup length dict begin{ 1 index /FID ne { def }{ pop pop } ifelse } forall