1 files changed, 2298 insertions, 0 deletions

diff --git a/parallel/search.ps b/parallel/search.ps
new file mode 100644
index 0000000..3b5be1c
--- /dev/null
+++ b/parallel/search.ps
@@ -0,0 +1,2298 @@
+%!PS-Adobe-3.0
+%%Creator: groff version 1.17.2
+%%CreationDate: Wed Sep  4 21:51:42 2002
+%%DocumentNeededResources: font Times-Roman
+%%DocumentSuppliedResources: procset grops 1.17 2
+%%Pages: 27
+%%PageOrder: Ascend
+%%Orientation: Portrait
+%%EndComments
+%%BeginProlog
+%%BeginResource: procset grops 1.17 2
+/setpacking where{
+pop
+currentpacking
+true setpacking
+}if
+/grops 120 dict dup begin
+/SC 32 def
+/A/show load def
+/B{0 SC 3 -1 roll widthshow}bind def
+/C{0 exch ashow}bind def
+/D{0 exch 0 SC 5 2 roll awidthshow}bind def
+/E{0 rmoveto show}bind def
+/F{0 rmoveto 0 SC 3 -1 roll widthshow}bind def
+/G{0 rmoveto 0 exch ashow}bind def
+/H{0 rmoveto 0 exch 0 SC 5 2 roll awidthshow}bind def
+/I{0 exch rmoveto show}bind def
+/J{0 exch rmoveto 0 SC 3 -1 roll widthshow}bind def
+/K{0 exch rmoveto 0 exch ashow}bind def
+/L{0 exch rmoveto 0 exch 0 SC 5 2 roll awidthshow}bind def
+/M{rmoveto show}bind def
+/N{rmoveto 0 SC 3 -1 roll widthshow}bind def
+/O{rmoveto 0 exch ashow}bind def
+/P{rmoveto 0 exch 0 SC 5 2 roll awidthshow}bind def
+/Q{moveto show}bind def
+/R{moveto 0 SC 3 -1 roll widthshow}bind def
+/S{moveto 0 exch ashow}bind def
+/T{moveto 0 exch 0 SC 5 2 roll awidthshow}bind def
+/SF{
+findfont exch
+[exch dup 0 exch 0 exch neg 0 0]makefont
+dup setfont
+[exch/setfont cvx]cvx bind def
+}bind def
+/MF{
+findfont
+[5 2 roll
+0 3 1 roll
+neg 0 0]makefont
+dup setfont
+[exch/setfont cvx]cvx bind def
+}bind def
+/level0 0 def
+/RES 0 def
+/PL 0 def
+/LS 0 def
+/MANUAL{
+statusdict begin/manualfeed true store end
+}bind def
+/PLG{
+gsave newpath clippath pathbbox grestore
+exch pop add exch pop
+}bind def
+/BP{
+/level0 save def
+1 setlinecap
+1 setlinejoin
+72 RES div dup scale
+LS{
+90 rotate
+}{
+0 PL translate
+}ifelse
+1 -1 scale
+}bind def
+/EP{
+level0 restore
+showpage
+}bind def
+/DA{
+newpath arcn stroke
+}bind def
+/SN{
+transform
+.25 sub exch .25 sub exch
+round .25 add exch round .25 add exch
+itransform
+}bind def
+/DL{
+SN
+moveto
+SN
+lineto stroke
+}bind def
+/DC{
+newpath 0 360 arc closepath
+}bind def
+/TM matrix def
+/DE{
+TM currentmatrix pop
+translate scale newpath 0 0 .5 0 360 arc closepath
+TM setmatrix
+}bind def
+/RC/rcurveto load def
+/RL/rlineto load def
+/ST/stroke load def
+/MT/moveto load def
+/CL/closepath load def
+/FL{
+currentgray exch setgray fill setgray
+}bind def
+/BL/fill load def
+/LW/setlinewidth load def
+/RE{
+findfont
+dup maxlength 1 index/FontName known not{1 add}if dict begin
+{
+1 index/FID ne{def}{pop pop}ifelse
+}forall
+/Encoding exch def
+dup/FontName exch def
+currentdict end definefont pop
+}bind def
+/DEFS 0 def
+/EBEGIN{
+moveto
+DEFS begin
+}bind def
+/EEND/end load def
+/CNT 0 def
+/level1 0 def
+/PBEGIN{
+/level1 save def
+translate
+div 3 1 roll div exch scale
+neg exch neg exch translate
+0 setgray
+0 setlinecap
+1 setlinewidth
+0 setlinejoin
+10 setmiterlimit
+[]0 setdash
+/setstrokeadjust where{
+pop
+false setstrokeadjust
+}if
+/setoverprint where{
+pop
+false setoverprint
+}if
+newpath
+/CNT countdictstack def
+userdict begin
+/showpage{}def
+}bind def
+/PEND{
+clear
+countdictstack CNT sub{end}repeat
+level1 restore
+}bind def
+end def
+/setpacking where{
+pop
+setpacking
+}if
+%%EndResource
+%%IncludeResource: font Times-Roman
+grops begin/DEFS 1 dict def DEFS begin/u{.001 mul}bind def end/RES 72
+def/PL 792 def/LS false def/ENC0[/asciicircum/asciitilde/Scaron/Zcaron
+/scaron/zcaron/Ydieresis/trademark/quotesingle/.notdef/.notdef/.notdef
+/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef
+/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef
+/.notdef/.notdef/space/exclam/quotedbl/numbersign/dollar/percent
+/ampersand/quoteright/parenleft/parenright/asterisk/plus/comma/hyphen
+/period/slash/zero/one/two/three/four/five/six/seven/eight/nine/colon
+/semicolon/less/equal/greater/question/at/A/B/C/D/E/F/G/H/I/J/K/L/M/N/O
+/P/Q/R/S/T/U/V/W/X/Y/Z/bracketleft/backslash/bracketright/circumflex
+/underscore/quoteleft/a/b/c/d/e/f/g/h/i/j/k/l/m/n/o/p/q/r/s/t/u/v/w/x/y
+/z/braceleft/bar/braceright/tilde/.notdef/quotesinglbase/guillemotleft
+/guillemotright/bullet/florin/fraction/perthousand/dagger/daggerdbl
+/endash/emdash/ff/fi/fl/ffi/ffl/dotlessi/dotlessj/grave/hungarumlaut
+/dotaccent/breve/caron/ring/ogonek/quotedblleft/quotedblright/oe/lslash
+/quotedblbase/OE/Lslash/.notdef/exclamdown/cent/sterling/currency/yen
+/brokenbar/section/dieresis/copyright/ordfeminine/guilsinglleft
+/logicalnot/minus/registered/macron/degree/plusminus/twosuperior
+/threesuperior/acute/mu/paragraph/periodcentered/cedilla/onesuperior
+/ordmasculine/guilsinglright/onequarter/onehalf/threequarters
+/questiondown/Agrave/Aacute/Acircumflex/Atilde/Adieresis/Aring/AE
+/Ccedilla/Egrave/Eacute/Ecircumflex/Edieresis/Igrave/Iacute/Icircumflex
+/Idieresis/Eth/Ntilde/Ograve/Oacute/Ocircumflex/Otilde/Odieresis
+/multiply/Oslash/Ugrave/Uacute/Ucircumflex/Udieresis/Yacute/Thorn
+/germandbls/agrave/aacute/acircumflex/atilde/adieresis/aring/ae/ccedilla
+/egrave/eacute/ecircumflex/edieresis/igrave/iacute/icircumflex/idieresis
+/eth/ntilde/ograve/oacute/ocircumflex/otilde/odieresis/divide/oslash
+/ugrave/uacute/ucircumflex/udieresis/yacute/thorn/ydieresis]def
+/Times-Roman@0 ENC0/Times-Roman RE
+%%EndProlog
+%%Page: 1 1
+%%BeginPageSetup
+BP
+%%EndPageSetup
+/F0 11/Times-Roman@0 SF(Abstract)72 96 Q .758(This paper describes a hi\
+gh-performance parallel tree search algorithm that uses Dynamic T)72 120
+R .757(ree Splitting)-.385 F .412
+(\(DTS\) to search alpha/beta minimax g)72 132 R .412
+(ame trees, speci\214cally those for the g)-.055 F .413(ame of chess.)
+-.055 F .413(This algorithm)5.913 F(di)72 144 Q .843
+(vides the search tree among se)-.275 F -.165(ve)-.275 G .842
+(ral processors on a shared memory parallel machine.).165 F .842
+(This paper dis-)6.342 F .997(cusses the follo)72 156 R .997
+(wing topics:)-.275 F .997(\(1\) the DTS algorithm, \(2\) ho)6.497 F
+3.747(wt)-.275 G .998(he tree is di)-3.747 F .998
+(vided into parallel pieces that)-.275 F .509(can be searched in parall\
+el; \(3\) performance results of the algorithm and \(4\) analysis of th\
+e results to see)72 168 R(where further impro)72 180 Q -.165(ve)-.165 G
+(ments might occur).165 E(..)-.605 E 2.75(1. Introduction.)72 204 R(Ov)
+72 228 Q 1.11(er the past ten years, high performance computer architec\
+tural designers ha)-.165 F 1.44 -.165(ve t)-.22 H 1.11
+(urned to parallel pro-).165 F .027(cessing to push the performance en)
+72 240 R -.165(ve)-.44 G .026(lope to higher and higher le).165 F -.165
+(ve)-.275 G 2.776(ls. Unfortunately).165 F 2.776(,f)-.715 G .026(or man)
+-2.776 F 2.776(ya)-.165 G(lgorithms)-2.776 E 1.533
+(in general, and the alpha/beta algorithm in particular)72 252 R 4.283
+(,p)-.44 G 1.533(arallel processing of)-4.283 F 1.534
+(fers a substantial hurdle to)-.275 F -.165(ex)72 264 S
+(tracting maximum performance from parallel machines.).165 E 1.81(The a\
+lpha/beta algorithm is based on a highly sequential property of searchi\
+ng that depends on prior)72 288 R(kno)72 300 Q 3.431(wledge to pre)-.275
+F -.165(ve)-.275 G 3.431(nt searching parts of the g).165 F 3.432
+(ame tree that ha)-.055 F 3.762 -.165(ve n)-.22 H 6.182(ob).165 G 3.432
+(earing on the \214nal results)-6.182 F 4.909([Knuth75,Hyatt89]. Since)
+72 312 R 4.908(ap)4.908 G 2.158(arallel search tra)-4.908 F -.165(ve)
+-.22 G 2.158(rses parts of the tree "simultaneously" such a priori).165
+F(kno)72 324 Q 6.478(wledge is not al)-.275 F -.11(wa)-.11 G 6.478(ys a)
+.11 F -.275(va)-.22 G 6.478
+(ilable [Campbell81,Hyatt88,Hyatt89,Hsu90,Lindstrom83,Marsland85,).275 F
+(Popo)72 336 Q(wich83,Schaef)-.275 E(fer89,man)-.275 E 2.75(yo)-.165 G
+(thers].)-2.75 E 1.814(The best-kno)72 360 R 1.814
+(wn early attempt at searching such trees in parallel w)-.275 F 1.813
+(as the Principal V)-.11 F 1.813(ariation Splitting)-1.221 F 4.248(\(PV\
+S\) algorithm [Hyatt86,Marsland80,Marsland81, Marsland82,Marsland86,Ne)
+72 372 R(wborn85,Schaef)-.275 E(fer89].)-.275 E .062(This w)72 384 R
+.062(as both simple to understand and easy to implement.)-.11 F .061
+(When starting an N-ply search, one processor)5.561 F .553
+(generates the mo)72 396 R -.165(ve)-.165 G 3.303(sa).165 G 3.303(tt)
+-3.303 G .553(he root position, mak)-3.303 F .553(es the \214rst mo)-.11
+F .883 -.165(ve \()-.165 H .553
+(leading to what is often referred to as the).165 F .086
+(left-most descendent position\), then generates the mo)72 408 R -.165
+(ve)-.165 G 2.836(sa).165 G 2.836(tp)-2.836 G .086(ly=2, mak)-2.836 F
+.086(es the \214rst mo)-.11 F .416 -.165(ve a)-.165 H -.055(ga).165 G
+.086(in, and contin-).055 F .115(ues this until reaching ply=N.)72 420 R
+.115(At this point, the processor pool searches all of the mo)5.615 F
+-.165(ve)-.165 G 2.865(sa).165 G 2.866(tt)-2.865 G .116
+(his ply \(N\) in)-2.866 F .42(parallel, and the best v)72 432 R .42
+(alue is back)-.275 F .419(ed up to ply N-1.)-.11 F(No)5.919 E 3.169(wt)
+-.275 G .419(hat the lo)-3.169 F .419(wer bound for ply N-1 is kno)-.275
+F .419(wn, the)-.275 F .328(rest of the mo)72 444 R -.165(ve)-.165 G
+3.078(sa).165 G 3.078(tN)-3.078 G .329
+(-1 are searched in parallel, and the best v)-3.078 F .329(alue ag)-.275
+F .329(ain back)-.055 F .329(ed up to N-2.)-.11 F .329(This contin-)
+5.829 F .464(ues until the \214rst root mo)72 456 R .794 -.165(ve h)
+-.165 H .464(as been searched and the v).165 F .464(alue is kno)-.275 F
+3.214(wn. The)-.275 F .464(remainder of the root mo)3.214 F -.165(ve)
+-.165 G(s).165 E .4(are searched in parallel, until none are left.)72
+468 R .4(The ne)5.9 F .4
+(xt iteration is started and the process repeats for depth)-.165 F(N+1.)
+72 480 Q .048
+(Performance analysis with this algorithm \(PVS\) produced speedups gi)
+72 504 R -.165(ve)-.275 G 2.797(nb).165 G(elo)-2.797 E 2.797(wi)-.275 G
+2.797(nt)-2.797 G .047(able 1 [Hyatt88] \(oth-)-2.797 F 1.112(ers ha)72
+516 R 1.442 -.165(ve p)-.22 H 1.112(roduced results v).165 F 1.113
+(ery similar to this\).)-.165 F 1.113(Clearly the performance curv)6.613
+F 3.863(ei)-.165 G 3.863<738d>-3.863 G 1.113(attened badly on the)-3.863
+F .23(upper end, and the C90 with 16 processors and the T90 with 32 are\
+ not going to perform as well as might)72 528 R 1.231(be e)72 540 R
+1.231(xpected, although the)-.165 F 3.981(ya)-.165 G 1.231
+(re certainly v)-3.981 F 1.231(ery f)-.165 F 3.981(ast. An)-.11 F 1.231
+(upper bound of 5X \(maybe\) does not look v)3.981 F(ery)-.165 E
+(attracti)72 552 Q -.165(ve)-.275 G 2.75(,h).165 G -.275(ow)-2.75 G
+-2.365 -.275(ev e).275 H 2.75(r[).275 G(Hyatt88].)-2.75 E EP
+%%Page: 2 2
+%%BeginPageSetup
+BP
+%%EndPageSetup
+.44 LW 414.465 88.75 197.534 88.75 DL/F0 11/Times-Roman@0 SF 2.75(#p)
+203.034 98 S 17.875(rocessors 1)-2.75 F 24.75(248)24.75 G(16)-2.75 E
+414.465 102.75 197.534 102.75 DL 32.384(speedup 1.0)203.034 112 R 13.75
+(1.9 3.4 5.4 6.0)16.5 F 414.465 116.75 197.534 116.75 DL 386.965 102.75
+386.965 116.75 DL 356.715 102.75 356.715 116.75 DL 326.465 102.75
+326.465 116.75 DL 296.215 102.75 296.215 116.75 DL 265.965 102.75
+265.965 116.75 DL 414.465 88.75 414.465 116.75 DL 197.534 88.75 197.534
+116.75 DL 386.965 88.75 386.965 116.75 DL 356.715 88.75 356.715 116.75
+DL 326.465 88.75 326.465 116.75 DL 296.215 88.75 296.215 116.75 DL
+265.965 88.75 265.965 116.75 DL -.88(Ta)233.427 140.2 S
+(ble 1 PVS performance results).88 E 1.656
+(This approach has a couple of f)72 164.2 R 1.656(airly ob)-.11 F 1.656
+(vious dra)-.165 F 4.406(wbacks. First,)-.165 F 1.656
+(notice that all of the processors w)4.406 F(ork)-.11 E .724
+(together at a single node, searching descendent positions in parallel.)
+72 176.2 R .725(If the number of possible mo)6.224 F -.165(ve)-.165 G
+3.475(si).165 G(s)-3.475 E .368
+(small, or the number of processors is lar)72 188.2 R .368(ge, some ha)
+-.198 F .698 -.165(ve n)-.22 H .368(othing to do.).165 F .368(Second, e)
+5.868 F -.165(ve)-.275 G .368(ry branch from a gi).165 F -.165(ve)-.275
+G(n).165 E .492(position does not produce a tree of equal size, since s\
+ome branches may gro)72 200.2 R 3.242(wi)-.275 G .492
+(nto complicated positions)-3.242 F .988
+(with lots of checks and search e)72 212.2 R .988(xtensions that mak)
+-.165 F 3.738(et)-.11 G .988(he tree v)-3.738 F .988(ery lar)-.165 F
+.987(ge, while other branches gro)-.198 F 3.737(wi)-.275 G(nto)-3.737 E
+.84(simple positions that are searched quickly)72 224.2 R 6.34(.T)-.715
+G .84(his leads to a load balancing problem where one processor)-6.34 F
+(be)72 236.2 Q .312(gins searching a v)-.165 F .312(ery lar)-.165 F .312
+(ge tree and the others \214nish the easy mo)-.198 F -.165(ve)-.165 G
+3.062(sa).165 G .312(nd ha)-3.062 F .641 -.165(ve t)-.22 H 3.061(ow).165
+G .311(ait for the remaining)-3.171 F(processor to slo)72 248.2 Q
+(wly tra)-.275 E -.165(ve)-.22 G(rse the tree.).165 E .235
+(This second problem is a serious dra)72 272.2 R .235
+(wback, because with a reasonable number of processors, the speedup)
+-.165 F .092(can look v)72 284.2 R .092(ery bad if most of the time man)
+-.165 F 2.842(yo)-.165 G 2.842(ft)-2.842 G .092(he processors are w)
+-2.842 F .092(aiting on one last node to be completed)-.11 F(before the)
+72 296.2 Q 2.75(yc)-.165 G(an back up to ply N-1 and start to w)-2.75 E
+(ork there.)-.11 E .271(Because of this, when we \214rst mo)72 320.2 R
+-.165(ve)-.165 G 3.021(dC).165 G .272
+(ray Blitz to the eight processor Cray YMP)-3.021 F 3.022(,w)-1.221 G
+3.022(ed)-3.022 G(isco)-3.022 E -.165(ve)-.165 G .272(red that the).165
+F 2.067(performance w)72 332.2 R 2.067(as only mar)-.11 F 2.067
+(ginally better than it w)-.198 F 2.067(as on the four processor XMP)
+-.11 F 4.817(,i)-1.221 G 4.817(fy)-4.817 G 2.067(ou discount the)-4.817
+F(impro)72 344.2 Q -.165(ve)-.165 G 4.166(dc).165 G 1.416
+(lock speed of each YMP processor)-4.166 F 6.916(.T)-.605 G 1.416
+(he \214rst approach we de)-6.916 F -.165(ve)-.275 G 1.417(loped w).165
+F 1.417(as called Enhanced)-.11 F 6.409(Principal V)72 356.2 R 6.409(ar\
+iation Splitting \(EPVS\) and is also pretty easy to understand and imp\
+lement)-1.221 F 3.843([Hyatt88,Hyatt89]. EPVS)72 368.2 R 1.093
+(simply notices whene)3.843 F -.165(ve)-.275 G 3.843(rap).165 G 1.093
+(rocessor at a node runs out of w)-3.843 F 3.843(ork. When)-.11 F(this)
+3.843 E 1.711(happens, assuming there are M processors w)72 380.2 R
+1.711(orking, we kno)-.11 F 4.461(wt)-.275 G 1.711(hat there are no)
+-4.461 F 4.461(wM)-.275 G 1.71(-1 \(or less\) acti)-4.461 F -.165(ve)
+-.275 G 1.684(branches remaining.)72 392.2 R 1.685
+(EPVS immediately stops all processors \(which are w)7.185 F 1.685
+(orking at ply P)-.11 F 4.435(,t)-1.221 G 1.685(he current)-4.435 F .419
+(position\) and follo)72 404.2 R .419
+(ws the \214rst remaining ply=P branch tw)-.275 F 3.168(op)-.11 G .418
+(lies and then splits the tree at that point with)-3.168 F 2.751(ap)72
+416.2 S .001(arallel search e)-2.751 F .001(xactly lik)-.165 F 2.751(et)
+-.11 G .001(he old PVS idea.)-2.751 F .002(The bene\214t is that no)
+5.501 F 2.752(wa)-.275 G .002(ll processors are w)-2.752 F .002
+(orking together)-.11 F .187
+(on a single branch at a node where there is little w)72 428.2 R .187
+(ork, and ha)-.11 F .517 -.165(ve s)-.22 H .187(tepped do).165 F .186
+(wn into the tree to a node with)-.275 F .633(more mo)72 440.2 R -.165
+(ve)-.165 G 3.383(st).165 G 3.383(os)-3.383 G .633(earch, and also a no\
+de where the descendent trees will be smaller since this node is tw)
+-3.383 F(o)-.11 E .581(plies deeper in the tree.)72 452.2 R .581
+(It should be noted that this is ef)6.081 F(fecti)-.275 E .911 -.165
+(ve b)-.275 H .58(ecause the transposition table stores the).165 F .231
+(partial results from the searches that are stopped, so that when these\
+ branches are searched later)72 464.2 R 2.982(,t)-.44 G .232(he w)-2.982
+F(ork)-.11 E .789
+(is not repeated because the information is found in the table.)72 476.2
+R .788(In case you might w)6.289 F .788(onder wh)-.11 F 3.538(yt)-.055 G
+.788(he search)-3.538 F .165(steps further into the tree tw)72 488.2 R
+2.915(op)-.11 G .165(lies, rather than one, recall that with alpha/beta\
+, if one ply \(P\) requires that)-2.915 F .2(all mo)72 500.2 R -.165(ve)
+-.165 G 2.95(sb).165 G 2.95(es)-2.95 G .2(earched, then the ne)-2.95 F
+.199(xt ply \(P+1\) only requires that one mo)-.165 F .529 -.165(ve b)
+-.165 H 2.949(es).165 G .199(earched to produce a refu-)-2.949 F 1.168
+(tation \(e)72 512.2 R 1.168(xcept for the case of PV nodes where no mo)
+-.165 F -.165(ve)-.165 G 3.918(sh).165 G -2.475 -.22(av e)-3.918 H 1.168
+(yet been searched.\))4.138 F 1.169(Therefore, since we)6.669 F(kno)72
+524.2 Q 3.385(wt)-.275 G .634(hat we are going to e)-3.385 F .634
+(xamine all nodes at P \(since we just back)-.165 F .634
+(ed up the PVS algorithm to ply P\),)-.11 F .847(we kno)72 536.2 R 3.597
+(wt)-.275 G .847(hat all nodes at ply P+2 will most lik)-3.597 F .848
+(ely ha)-.11 F 1.178 -.165(ve t)-.22 H 3.598(ob).165 G 3.598(es)-3.598 G
+.848(earched as well, so long as we choose a)-3.598 F(reasonable mo)72
+548.2 Q .33 -.165(ve a)-.165 H 2.75(tp).165 G(ly=P+1.)-2.75 E EP
+%%Page: 3 3
+%%BeginPageSetup
+BP
+%%EndPageSetup
+/F0 11/Times-Roman@0 SF 1.83(Performance analysis with this algorithm \
+\(EPVS\) produced speedups that were modest impro)72 96 R -.165(ve)-.165
+G(ments).165 E -.165(ove)72 108 S 3.435(rP).165 G .685(VS, as gi)-3.435
+F -.165(ve)-.275 G 3.435(ni).165 G 3.435(nt)-3.435 G .685(able 2 belo)
+-3.435 F 4.865 -.715(w. T)-.275 H .685(his is roughly 20% f).715 F .685
+(aster than PVS on lar)-.11 F .686(ger numbers of proces-)-.198 F .285
+(sors, from the results belo)72 120 R 1.715 -.715(w, b)-.275 H .284(ut \
+the 8 and 16 processor times still are disappointing, and the 32 proces\
+sor).495 F 1.229(results w)72 132 R 1.23(ould be abysmal.)-.11 F
+(Clearly)6.73 E 3.98(,ab)-.715 G 1.23
+(etter algorithm had to be found, or we were going to see a v)-3.98 F
+(ast)-.275 E(amount of unused processing po)72 144 Q
+(wer on future Cray computers [Hyatt88].)-.275 E .44 LW 414.465 164.95
+197.534 164.95 DL 2.75(#p)203.034 174.2 S 17.875(rocessors 1)-2.75 F
+24.75(248)24.75 G(16)-2.75 E 414.465 178.95 197.534 178.95 DL 32.384
+(speedup 1.0)203.034 188.2 R 13.75(1.9 3.4 5.4 6.0)16.5 F 414.465 192.95
+197.534 192.95 DL 386.965 178.95 386.965 192.95 DL 356.715 178.95
+356.715 192.95 DL 326.465 178.95 326.465 192.95 DL 296.215 178.95
+296.215 192.95 DL 265.965 178.95 265.965 192.95 DL 414.465 164.95
+414.465 192.95 DL 197.534 164.95 197.534 192.95 DL 386.965 164.95
+386.965 192.95 DL 356.715 164.95 356.715 192.95 DL 326.465 164.95
+326.465 192.95 DL 296.215 164.95 296.215 192.95 DL 265.965 164.95
+265.965 192.95 DL -.88(Ta)230.067 216.4 S
+(ble 2 EPVS performance results).88 E 2.75(2. Dynamic)72 240.4 R -.385
+(Tr)2.75 G(ee Splitting algorithm \(DTS\)).385 E .595(Before describing\
+ the DTS algorithm in detail, one important point needs e)72 264.4 R
+3.345(xplanation. This)-.165 F .595(algorithm is)3.345 F .457(speci\214\
+cally designed for a shared memory multiprocessor architecture.)72 276.4
+R .457(As a result, issues that other pro-)5.957 F 1.152
+(grams and programmers ha)72 288.4 R 1.482 -.165(ve t)-.22 H 3.902(of)
+.165 G 1.152(ace \(distrib)-4.012 F 1.152
+(uted transposition tables, killer mo)-.22 F -.165(ve)-.165 G 1.151
+(s, history information).165 F .099
+(and such\) are not an issue here at all.)72 300.4 R .1
+(Some of the decisions in the DTS design w)5.6 F .1(ould lik)-.11 F .1
+(ely cause signi\214-)-.11 F 1.014
+(cant problems on a message-passing architecture, no matter ho)72 312.4
+R 3.764(wf)-.275 G 1.014(ast the communication channel might)-3.874 F
+3.479(be. On)72 324.4 R .729(the Cray)3.479 F 3.479(,w)-.715 G .73
+(hich has an absolutely astounding cpu-to-memory bandwidth, mo)-3.479 F
+.73(ving a me)-.165 F -.055(ga)-.165 G .73(byte of).055 F 1.693
+(data tak)72 336.4 R 1.693(es v)-.11 F 1.692(ery little time at all, wh\
+ich simply means that in this algorithm, communication costs are)-.165 F
+(al)72 348.4 Q -.11(wa)-.11 G .037(ys assumed to be zero.).11 F .037
+(An assumption that w)5.537 F .037(ould f)-.11 F .037
+(ail on other architectures of course, b)-.11 F .038(ut one which)-.22 F
+.664(certainly af)72 360.4 R .663
+(fected decisions made while designing the DTS algorithm as well.)-.275
+F .663(It turns out that loading a)6.163 F .649("\215ag w)72 372.4 R
+.649(ord" \(which indicates that there is some parallel-processing rela\
+ted task to perform\) and testing it)-.11 F(can be b)72 384.4 Q
+(uried in the instruction stream so that the)-.22 E 2.75(yc)-.165 G
+(ause no delays at all.j)-2.75 E(2.1 The DTS approach)72 408.4 Q .446
+(In analyzing the pre)72 432.4 R .446(vious tw)-.275 F 3.196(oa)-.11 G
+.446(lgorithms, the)-3.196 F 3.196(yb)-.165 G .445(oth suf)-3.196 F .445
+(fer from tw)-.275 F 3.195(od)-.11 G .445(istinct problems:)-3.195 F
+.445(\(1\) all processors)5.945 F -.11(wo)72 444.4 S .152
+(rk together at a single node, which is acceptable for middle-g).11 F
+.152(ames with 35+ le)-.055 F -.055(ga)-.165 G 2.903(lm).055 G -.165
+(ove)-2.903 G 2.903(s\().165 G -2.475 -.22(av e)-2.903 H .153(rage\), b)
+.22 F(ut)-.22 E .175(which does not look attracti)72 456.4 R .505 -.165
+(ve i)-.275 H 2.925(ne).165 G(nd-g)-2.925 E .175
+(ames where the number of le)-.055 F -.055(ga)-.165 G 2.925(lm).055 G
+-.165(ove)-2.925 G 2.925(si).165 G 2.925(sm)-2.925 G .175(uch smaller;)
+-2.925 F .175(\(2\) if one)5.675 F .366(processor selects a mo)72 468.4
+R .696 -.165(ve t)-.165 H .367(hat leads to a v).165 F .367(ery b)-.165
+F(ush)-.22 E 3.117(yt)-.055 G .367
+(ree, the other processors might end up w)-3.117 F .367(aiting for an)
+-.11 F -.165(ex)72 480.4 S .324(tended period before that tree is compl\
+eted, producing long periods where most processors are w).165 F(aiting,)
+-.11 E .251(and greatly de)72 492.4 R .251
+(grading parallel performance.)-.165 F .252(The DTS algorithm w)5.752 F
+.252(as speci\214cally de)-.11 F -.165(ve)-.275 G .252(loped to a).165 F
+-.22(vo)-.22 G .252(id both).22 F(of these problems.)72 504.4 Q .192
+(The \214rst design goal in de)72 528.4 R -.165(ve)-.275 G .191
+(loping the DTS algorithm w).165 F .191
+(as to completely eliminate the cases where a pro-)-.11 F .365(cessor w)
+72 540.4 R .366(as idle, with no mo)-.11 F -.165(ve)-.165 G 3.116(sl)
+.165 G .366(eft to search, while other processors were b)-3.116 F(usy)
+-.22 E 5.866(.I)-.715 G 3.116(na)-5.866 G .366(ccomplishing this, it)
+-3.116 F .848(became ob)72 552.4 R .848(vious that the \214rst step w)
+-.165 F .847(as to disassociate all of the processors, so there w)-.11 F
+.847(as no requirement)-.11 F(that the)72 564.4 Q 2.75(ya)-.165 G
+(ll congre)-2.75 E -.055(ga)-.165 G(te at a single node and w).055 E
+(ork together searching mo)-.11 E -.165(ve)-.165 G 2.75(su).165 G
+(ntil all were completed.)-2.75 E EP
+%%Page: 4 4
+%%BeginPageSetup
+BP
+%%EndPageSetup
+/F0 11/Times-Roman@0 SF 2.554(Note that there are alternati)72 96 R
+2.884 -.165(ve w)-.275 H 2.554(ays to k).055 F 2.554(eep processors b)
+-.11 F(usy)-.22 E 5.304(,b)-.715 G 2.555(esides trying to ha)-5.304 F
+2.885 -.165(ve t)-.22 H 2.555(hem all w).165 F(ork)-.11 E(together)72
+108 Q 6.366(.O)-.605 G .866(ne such approach w)-6.366 F .866
+(as used in Phoenix [Schaef)-.11 F .865(fer89], and used tw)-.275 F
+3.615(os)-.11 G .865(eparate search engines,)-3.615 F 1.058
+(one a full chess program, the other \(called Minix\) w)72 120 R 1.059
+(as a material-only searcher that searched deeper to)-.11 F .424
+(con\214rm/reject mo)72 132 R -.165(ve)-.165 G 3.174(sp).165 G .424
+(roposed by the full chess program.)-3.174 F(Ob)5.923 E .423
+(viously there is duplicate w)-.165 F .423(ork done in this)-.11 F .88
+(approach, as well as other problems related to choosing a mo)72 144 R
+1.21 -.165(ve t)-.165 H 3.63(op).165 G .881
+(lay when the positional search says)-3.63 F .604(play X, b)72 156 R
+.604(ut the tactical search says "no.")-.22 F .603
+(This sort of speculati)6.103 F .933 -.165(ve c)-.275 H .603
+(omputing, which is an admission that).165 F .541
+(additional processors w)72 168 R(on')-.11 E 3.291(ts)-.198 G .541
+(peed up the basic search, w)-3.291 F .542(as deemed too inef)-.11 F
+.542(\214cient and inef)-.275 F(fecti)-.275 E .872 -.165(ve t)-.275 H
+3.292(oc).165 G(on-)-3.292 E(sider)72 180 Q 2.75(,a)-.44 G
+(nd something better w)-2.75 E(as desired.)-.11 E 2.554
+(The second design goal w)72 204 R 2.553(as to a)-.11 F -.22(vo)-.22 G
+2.553(id completely ripping Cray Blitz apart, ef).22 F(fecti)-.275 E
+-.165(ve)-.275 G 2.553(ly starting from).165 F .994(scratch; rather)72
+216 R 3.744(,w)-.44 G 3.744(ew)-3.744 G .994(anted to use the same mo)
+-3.854 F 1.324 -.165(ve g)-.165 H .995
+(enerator code, tree search code, mo).165 F 1.325 -.165(ve o)-.165 H
+.995(rdering code,).165 F(and so forth for both a one-processor sequent\
+ial program and the multi-processing v)72 228 Q(ersion.)-.165 E 3.071
+(As)72 252 S .321(imple e)-3.071 F .321(xplanation of DTS is f)-.165 F
+.321(airly easy to understand, b)-.11 F .321
+(ut it also hides a great deal of comple)-.22 F .321(xity that)-.165 F
+1.565(has to be o)72 264 R -.165(ve)-.165 G 1.565
+(rcome when writing and deb).165 F 1.565(ugging the code.)-.22 F 1.566
+(At the be)7.066 F 1.566(ginning of a ne)-.165 F 4.316(wi)-.275 G 1.566
+(teration, DTS)-4.316 F(beha)72 276 Q -.165(ve)-.22 G 3.594(sj).165 G
+.844(ust lik)-3.594 F 3.594(eP)-.11 G .844(VS, searching do)-3.594 F
+.843
+(wn the left-hand side of the tree from ply=1 up to ply=N, with only)
+-.275 F .789(one processor)72 288 R 6.289(.A)-.605 G 3.539(tp)-6.289 G
+.789(ly=N, all processors "join the party" and search the ply=N mo)
+-3.539 F 1.119 -.165(ve l)-.165 H .789(ist in parallel, just).165 F(lik)
+72 300 Q 3.346(eP)-.11 G 3.345(VS/EPVS. Ho)-3.346 F(we)-.275 E -.165(ve)
+-.275 G 1.475 -.44(r, w).165 H .595(hen a processor completes the mo).44
+F .925 -.165(ve i)-.165 H 3.345(ti).165 G 3.345(ss)-3.345 G .595
+(earching, and disco)-3.345 F -.165(ve)-.165 G .595(rs there are).165 F
+(no more to be searched, DTS reacts to this.)72 312 Q .802(This idle pr\
+ocessor broadcasts \(using shared memory\) that it is idle, and is a)72
+336 R -.275(va)-.22 G .802(ilable to "help" an).275 F 3.552(yo)-.165 G
+(ther)-3.552 E .514(processor \214nish searching its tree.)72 348 R .514
+(The b)6.014 F .513
+(usy processors collect the "state of the tree" data, and store it in)
+-.22 F 1.558(shared memory for the idle processor to e)72 360 R 4.308
+(xamine. This)-.165 F 1.558
+(idle processor analyzes this data, and decides)4.308 F .057
+(which \(if an)72 372 R .057(y\) of the b)-.165 F .057
+(usy processors seems to ha)-.22 F .386 -.165(ve a t)-.22 H .056
+(ree that is complicated enough that it w).165 F .056(ould be ef)-.11 F
+<8c2d>-.275 E .591(cient to help with the search.)72 384 R .592(If such\
+ a position is found, the idle processor informs the processor which)
+6.092 F -.275(ow)72 396 S(ns that node of this and the).275 E 2.75(y")
+-.165 G(join" forces.)-2.75 E 2.07 -.88(To a)72 420 T .31(ccomplish thi\
+s, the idle processor speci\214cally chooses a ply=S position and tells\
+ the o).88 F .309(wner that S has)-.275 F .767
+(been chosen as the split-point ply)72 432 R 6.267(.T)-.715 G .768
+(he processor with that subtree in progress then copies the complete)
+-6.267 F .008(tree state to a shared memory area called a "split block"\
+ \(this tree state includes the v)72 444 R .008(arious search bounds,)
+-.275 F(mo)72 456 Q 1.498 -.165(ve l)-.165 H 1.169(ists for each ply un\
+der analysis, current board position and other related search data such\
+ as the).165 F .745(repetition list and so forth\).)72 468 R .745
+(Both processors can no)6.245 F 3.494(we)-.275 G .744(xtract mo)-3.659 F
+-.165(ve)-.165 G 3.494(sf).165 G .744
+(rom this shared data and search in)-3.494 F 2.92(parallel. Whene)72 480
+R -.165(ve)-.275 G 2.92(ro).165 G .17(ne runs out of w)-2.92 F .171
+(ork, it simply repeats this process.)-.11 F .171
+(In some cases, we might see tw)5.671 F(o)-.11 E .794
+(processors split the tree at ply=8, then one runs out of w)72 492 R
+.793(ork, and decides that the other one has the best)-.11 F .401
+(split candidate, and the)72 504 R 3.151(yt)-.165 G .401
+(hen split at ply=10.)-3.151 F .401(The \214rst might run out of w)5.901
+F .402(ork at that split point, and help)-.11 F .586(the other at a ne)
+72 516 R 3.336(ws)-.275 G .586(plit point at ply=12.)-3.336 F .586
+(Or it might bail out completely and choose to help another pro-)6.086 F
+(cessor)72 528 Q 3.713(,s)-.44 G .964(ince going deeper and deeper spli\
+tting the tree means that each subtree searched is smaller and)-3.713 F
+(smaller)72 540 Q 4.25(,a)-.44 G 1.5(nd e)-4.25 F -.165(ve)-.275 G 1.5
+(ntually the tw).165 F 4.25(op)-.11 G 1.5
+(rocessors might spend as much time splitting and sharing as the)-4.25 F
+4.249(yd)-.165 G(o)-4.249 E
+(searching \(more about this possible condition later)72 552 Q(.\))-.605
+E .893(The o)72 576 R -.165(ve)-.165 G .893(rall ef).165 F .893(fect of\
+ this is that the processors start together on a single node, searching\
+ in parallel, b)-.275 F(ut)-.22 E EP
+%%Page: 5 5
+%%BeginPageSetup
+BP
+%%EndPageSetup
+/F0 11/Times-Roman@0 SF(the)72 96 Q 2.75(yq)-.165 G
+(uickly spread out in groups o)-2.75 E -.165(ve)-.165 G 2.75(rt).165 G
+(he acti)-2.75 E .33 -.165(ve t)-.275 H
+(ree, helping at points where there is w).165 E(ork to be done.)-.11 E
+(No)72 120 Q 3.518(wt)-.275 G .768(he ne)-3.518 F .768(xt issue.)-.165 F
+.767(Notice that as a processor becomes idle, it can re-split the same \
+tree it w)6.268 F .767(as sharing)-.11 F .561(with another processor)72
+132 R 3.311(,b)-.44 G .561(ut so f)-3.531 F(ar)-.11 E 3.311(,o)-.44 G
+.561(nly at deeper plies.)-3.311 F(Wh)6.061 E 3.311(yi)-.055 G 3.311(st)
+-3.311 G 3.311(his? Because)-3.311 F .562(it is inef)3.311 F .562
+(\214cient to back up)-.275 F 1.604(to ply N-1 and search branches ther\
+e before ply=N has been completely searched \(remember the \214rst)72
+144 R .033(ply=N split node is a PV node just lik)72 156 R 2.783(eP)-.11
+G .033(VS, and we don')-2.783 F 2.783(tw)-.198 G .033(ant to start w)
+-2.893 F .034(orking on ply N-1, until we ha)-.11 F -.165(ve)-.22 G
+2.388(the actual score for ply=N\).)72 168 R(Ho)7.888 E(we)-.275 E -.165
+(ve)-.275 G 3.267 -.44(r, e).165 H -.165(ve).165 G(ntually).165 E 5.137
+(,t)-.715 G 2.387(he trees can')-5.137 F 5.137(tb)-.198 G 5.137(ef)
+-5.137 G 2.387(urther sub-di)-5.137 F 2.387(vided an)-.275 F 5.137(yf)
+-.165 G(urther)-5.137 E .003(because the cost of doing so w)72 180 R
+.003(ould be more than the cost of searching the subtree.)-.11 F(No)
+5.503 E 2.754(wac)-.275 G .004(ritical decision)-2.754 F
+(has to be made, "what to do ne)72 192 Q(xt?")-.165 E .389
+(Since we are using the best-kno)72 216 R .389(wn mo)-.275 F .719 -.165
+(ve o)-.165 H .389
+(rdering heuristics in the alpha/ beta tree, it is lik).165 F .388
+(ely that by the)-.11 F .641(time the \214rst fe)72 228 R 3.391(wm)-.275
+G -.165(ove)-3.391 G 3.391(sa).165 G 3.391(tp)-3.391 G .641(ly=N ha)
+-3.391 F .971 -.165(ve b)-.22 H .641(een searched, we kno).165 F 3.391
+(wt)-.275 G .641(he actual score for this node, as mo)-3.391 F -.165(ve)
+-.165 G(s).165 E .092(further do)72 240 R .092(wn the list should be w)
+-.275 F .092(orse and not impro)-.11 F .421 -.165(ve t)-.165 H .091
+(he score further).165 F 5.591(.T)-.605 G .091(hen, allo)-5.591 F .091
+(wing idle processors to)-.275 F .276(back up to ply=N-1 and start sear\
+ching there before ply=N is completed is probably safe, and this is wha\
+t)72 252 R .129(DTS does.)72 264 R .128(On the rare occasions when the \
+ply=N search completes, and the last branch produces an e)5.629 F -.165
+(ve)-.275 G(n).165 E 1.475(better score, the processors that ha)72 276 R
+1.805 -.165(ve b)-.22 H(ack).165 E 1.475
+(ed up to ply=N-1 already are searching with a less ef)-.11 F(\214cient)
+-.275 E 3.062(bound. DTS)72 288 R .312
+(notices this and each processor already searching at N-1 is gi)3.062 F
+-.165(ve)-.275 G 3.061(nt).165 G .311(he ne)-3.061 F 3.061(w\()-.275 G
+.311(correct\) bound as)-3.061 F .261(soon as it is kno)72 300 R 3.012
+(wn. This)-.275 F .262(sounds easy and clean, b)3.012 F .262
+(ut it can cause some interesting problems, because this)-.22 F(ne)72
+312 Q 3.124(wb)-.275 G .374
+(ound might mean most of what a processor has been b)-3.124 F .374
+(usy doing can be thro)-.22 F .373(wn a)-.275 F -.11(wa)-.165 G 3.123
+(ys).11 G .373(ince the ne)-3.123 F(w)-.275 E(bound w)72 324 Q(ould ha)
+-.11 E .33 -.165(ve c)-.22 H(aused a cutof).165 E 2.75(fm)-.275 G
+(uch sooner than the original bound used.)-2.75 E .813(The best metapho\
+r for describing this might be "ants at a picnic" where the chess tree \
+is the picnic, and)72 348 R .01
+(the ants are the search engines \(processors\).)72 360 R .01
+(The ants start eating on a lar)5.51 F .009(ge crumb, b)-.198 F .009
+(ut as it is eaten a)-.22 F -.11(wa)-.165 G -.715(y,).11 G 1.623
+(it becomes too small and the ants that are displaced mo)72 372 R 1.953
+-.165(ve t)-.165 H 4.373(oa).165 G 1.623(nother crumb and start w)-4.373
+F 1.624(orking there..)-.11 F(Ev)72 384 Q .551
+(entually lots of ants are congre)-.165 F -.055(ga)-.165 G .551
+(ted around a steadily diminishing supply of crumbs, which brings up)
+.055 F(the \214nal phase of the DTS algorithm de)72 396 Q -.165(ve)-.275
+G(lopment.).165 E .137
+(In testing this code, we found, on occasion, a position that w)72 420 R
+.137(ould blo)-.11 F 2.887(wu)-.275 G 2.887(pa)-2.887 G .138
+(nd produce search times much)-2.887 F .884(longer than e)72 432 R -.165
+(ve)-.275 G 3.634(nt).165 G .884(he single-processor search.)-3.634 F
+-.165(Fo)6.384 G 3.634(re).165 G .884(xample, 1 processor w)-3.799 F
+.883(ould tak)-.11 F 3.633(e1m)-.11 G .883(inute to do a 10)-3.633 F
+.135(ply search, b)72 444 R .135
+(ut with DTS, out of 5,000 test runs, one run w)-.22 F .136(ould tak)
+-.11 F 2.886(e1m)-.11 G .136(inute to do a 5 ply search with 16)-2.886 F
+3.074(processors. What)72 456 R .324(we found w)3.074 F .323(as a condi\
+tion we later termed a "feeding frenzy" to maintain the ants anal-)-.11
+F(ogy)72 468 Q 6.533(.W)-.715 G 1.033(hat w)-6.533 F 1.033
+(as happening w)-.11 F 1.033(as that as the tree w)-.11 F 1.033
+(as nearly completed, the search reached a point where)-.11 F .597
+(there were no good "split points".)72 480 R .597(DTS w)6.097 F .597
+(as quite good at recognizing when it w)-.11 F .596
+(as appropriate to split a)-.11 F .084
+(tree into parallel slices and when it w)72 492 R .084(as not.)-.11 F
+(Unfortunately)5.584 E 2.834(,i)-.715 G 2.834(tw)-2.834 G .084
+(as not so good at determining when it w)-2.944 F(as)-.11 E
+(time to quit checking to see if there were an)72 504 Q 2.75(yg)-.165 G
+(ood split points.)-2.75 E .187
+(Imagine a case with 16 processors, with 15 idle, and one w)72 528 R
+.186(orking trying to search the last 15 nodes left in)-.11 F .836
+(the entire tree.)72 540 R .836(This one processor k)6.336 F .836
+(eeps getting interrupted with "may I help you?", "can I help you?",)
+-.11 F .299("could you use some help there?" and so forth, so that rath\
+er than searching, it stays b)72 552 R .298(usy cop)-.22 F .298
+(ying its tree)-.11 F 1.201(state to shared memory so that the idle pro\
+cessors can attempt to \214nd a split point.)72 564 R(The)6.701 E 3.951
+(yf)-.165 G 1.201(ail, and ask)-4.061 F(ag)72 576 Q 2.159(ain, and ag)
+-.055 F 4.909(ain. And)-.055 F 2.158(in a v)4.909 F 2.158(ery fe)-.165 F
+4.908(wp)-.275 G 2.158(athological cases, this almost hung the search.)
+-4.908 F 3.918 -.88(To s)7.658 H(olv).88 E 4.908(et)-.165 G(his)-4.908 E
+EP
+%%Page: 6 6
+%%BeginPageSetup
+BP
+%%EndPageSetup
+/F0 11/Times-Roman@0 SF 1.617(problem, which only occurred right at the\
+ end of an iteration, we chose to add a "thrashing" counter)72 96 R(,)
+-.44 E .202(which w)72 108 R .202(as nothing more than a counter that w)
+-.11 F .202(as set to some v)-.11 F .201
+(alue when a processor handled one of those)-.275 F .692
+("may I help you?")72 120 R 3.442(queries. Until)6.192 F .693
+(that processor searched N nodes \(N w)3.442 F .693(as the v)-.11 F .693
+(alue set in the thrashing)-.275 F .754(counter\) it w)72 132 R .753
+(ould refuse to answer an)-.11 F 3.503(ym)-.165 G .753
+(ore "may I help you?")-3.503 F .753
+(queries, which eliminated the thrashing)6.253 F
+(right at the end of an iteration.)72 144 Q .818(That is a basic e)72
+168 R .819(xplanation of DTS.)-.165 F(Ho)6.319 E(we)-.275 E -.165(ve)
+-.275 G 1.699 -.44(r, t).165 H 3.569(oa).44 G .819(ppreciate e)-3.569 F
+.819(xactly ho)-.165 F 3.569(wc)-.275 G(omple)-3.569 E 3.569(xa)-.165 G
+.819(nd sophisticated this)-3.569 F -2.365 -.275(ev e)72 180 T .252
+(ntually became, the ne).275 F .252(xt step is to look at some of the s\
+peci\214c components and data structures need to)-.165 F(mak)72 192 Q
+3.733(et)-.11 G .983(his algorithm perform.)-3.733 F .983
+(First, we need a couple of de\214nitions to mak)6.483 F 3.734(es)-.11 G
+.984(ure terminology does not)-3.734 F(obscure the algorithm.)72 204 Q
+2.75(2.2 De\214nitions)72 228 R 1.162(Split-point is a node within the \
+tree where it appears that the search must e)72 252 R 1.161
+(xamine all of the successor)-.165 F 2.791(nodes. The)72 264 R .041(qua\
+lity of a split point is related both to its depth \(nodes closer to th\
+e root of the tree represent)2.791 F(lar)72 276 Q 2.328(ger subtrees an\
+d thus are better split points\) and the con\214dence that all of the b\
+ranches must be)-.198 F 2.091(searched must be high.)72 288 R 2.091(Thi\
+s con\214dence is described in section three which discusses choosing s\
+plit)7.591 F(points.)72 300 Q .48(Branching f)72 324 R .48
+(actor is a measure of the comple)-.11 F .48
+(xity of a position reached in the tree search which character)-.165 F
+(-)-.22 E .754(izes this comple)72 336 R .754(xity in terms of the a)
+-.165 F -.165(ve)-.22 G .755(rage number of successor branches \(le).165
+F -.055(ga)-.165 G 3.505(lm).055 G -.165(ove)-3.505 G .755
+(s\) from this posi-).165 F 3.902(tion. Chess)72 348 R 1.152(seems to a)
+3.902 F -.165(ve)-.22 G 1.152(rage around 38 according to man).165 F
+3.902(yp)-.165 G 1.152(ublished papers, b)-3.902 F 1.152
+(ut the number can v)-.22 F(ary)-.275 E
+(from zero \(mate or stalemate or dra)72 360 Q
+(w\) to around 200 \(with man)-.165 E 2.75(yq)-.165 G
+(ueens and an open board.\))-2.75 E 2.75(2.3 The)72 384 R(HELP command)
+2.75 E .765
+(The HELP command is the primary signaling mechanism within DTS.)72 408
+R(Whene)6.265 E -.165(ve)-.275 G 3.515(rap).165 G .766
+(rocessor is "out of)-3.515 F -.11(wo)72 420 S
+(rk" it sends the HELP command to what is ef).11 E(fecti)-.275 E -.165
+(ve)-.275 G(ly the entire group of acti).165 E .33 -.165(ve p)-.275 H
+(rocessors.).165 E .444(The HELP command simply requests that an)72 444
+R 3.194(yp)-.165 G .444(rocessors that are acti)-3.194 F -.165(ve)-.275
+G .443(ly searching subtrees temporarily).165 F(stop, cop)72 456 Q 2.75
+(yt)-.11 G(he "tree state" to shared memory)-2.75 E 2.75(,a)-.715 G
+(nd then continue searching.)-2.75 E 1.553
+(As these "tree states" become a)72 480 R -.275(va)-.22 G 1.553
+(ilable, the idle processor that initiated the HELP command analyzes)
+.275 F 1.005(each state to determine if it can \214nd a satisf)72 492 R
+1.004(actory split point.)-.11 F 1.004
+(If not, it simply re-broadcasts the HELP)6.504 F(command.)72 504 Q .07
+(As will be sho)72 528 R .07(wn later)-.275 F 2.82<2c8c>-.44 G .07
+(nding a split point is non-tri)-2.82 F .071(vial, because it is a k)
+-.275 F .401 -.165(ey s)-.11 H .071(tep in the DTS algorithm.).165 F(If)
+5.571 E 1.209(an incorrect split point is chosen, then it is lik)72 540
+R 1.208(ely that the processors that start to help at that point are)
+-.11 F .175(going to search nodes that are not necessary)72 552 R 2.925
+(,w)-.715 G .175(hich does nothing b)-2.925 F .175
+(ut increase the parallel search o)-.22 F -.165(ve)-.165 G(rhead).165 E
+(without making the search progress an)72 564 Q 2.75(yf)-.165 G
+(aster through the tree.)-2.86 E EP
+%%Page: 7 7
+%%BeginPageSetup
+BP
+%%EndPageSetup
+/F0 11/Times-Roman@0 SF .59(An interesting feature here, is that once a\
+ processor \214nds a viable split-point, and the Split\(\) operation is)
+72 96 R 1.058(performed, whene)72 108 R -.165(ve)-.275 G 3.808(ra).165 G
+1.388 -.165(ny o)-3.808 H 1.058(ther processor becomes idle, the).165 F
+3.808(yc)-.165 G 1.058(heck for acti)-3.808 F 1.388 -.165(ve s)-.275 H
+1.058(plit-points before broad-).165 F 1.037(casting a HELP command.)72
+120 R 1.036(If a processor locates an)6.537 F 3.786(yv)-.165 G 1.036
+(alid split points, and there is w)-4.061 F 1.036(ork remaining at)-.11
+F(an)72 132 Q 3.258(yo)-.165 G 3.258(ft)-3.258 G .508
+(hem, it simply attaches to the split point with the most w)-3.258 F
+.509(ork remaining, and does not broadcast a)-.11 F 1.445(help command.)
+72 144 R 1.444(This tends to k)6.944 F 1.444(eep the processors w)-.11 F
+1.444(orking together in related parts of the tree, which)-.11 F(mak)72
+156 Q .521(es the transposition table and scoring hash tables more ef)
+-.11 F(fecti)-.275 E .851 -.165(ve s)-.275 H .521
+(ince the information is more useful).165 F .101
+(among closely related positions.)72 168 R(Ho)5.601 E(we)-.275 E -.165
+(ve)-.275 G .981 -.44(r, i).165 H 2.851(fap).44 G .101
+(rocessor becomes idle, and \214nds no split-point with w)-2.851 F(ork)
+-.11 E .665(remaining, it does initiate a HELP command and goes about \
+\214nding a ne)72 180 R 3.416(ws)-.275 G 3.416(plit-point. Other)-3.416
+F(processors)3.416 E .956(will lik)72 192 R .956
+(ely join it at that split point as the)-.11 F 3.706(yb)-.165 G .956
+(ecome idle.)-3.706 F .955
+(Another reason for doing this is that \214nding a)6.456 F .34
+(split point tak)72 204 R .34
+(es time, and once a good one has been located, there')-.11 F 3.09(sn)
+-.605 G 3.09(op)-3.09 G .34(oint in locating another until the)-3.09 F
+1.863
+(\214rst one has been completed, or at least until there are no more mo)
+72 216 R -.165(ve)-.165 G 4.613(sl).165 G 1.863
+(eft at that point that can be)-4.613 F 1.086
+(searched by idle processors.)72 228 R 1.086(In the v)6.586 F 1.087
+(ery w)-.165 F 1.087
+(orst case, with N processors each split point could ha)-.11 F 1.417
+-.165(ve t)-.22 H -.11(wo).165 G .177(processors w)72 240 R .177
+(orking, if the tree is v)-.11 F .176(ery narro)-.165 F 4.356 -.715
+(w. I)-.275 H 2.926(nt).715 G .176(he optimal case, which is f)-2.926 F
+.176(airly common in the middle-)-.11 F -.055(ga)72 252 S 1.416
+(me, there are rarely more than one or tw).055 F 4.166(os)-.11 G 1.416
+(plit points, the \214rst is nearly completed, and the second)-4.166 F
+(\(ne)72 264 Q
+(w\) split point is where each processor goes when it runs out of w)
+-.275 E(ork at the original split point.)-.11 E 2.078 -.88(To p)72 288 T
+.318(rocess the HELP command, a simple test w).88 F .317
+(as added to the sequential search code.)-.11 F .317(After an)5.817 F
+3.067(yn)-.165 G .317(ode is)-3.067 F .91(processed, HELP\(i\) is check)
+72 300 R .911(ed, and if set, the tree state is copied to shared memory)
+-.11 F 3.661(,t)-.715 G .911(he \215ag is cleared,)-3.661 F .888
+(and the search continues normally)72 312 R 6.388(.T)-.715 G .887
+(his reduces the idle time for a processor to the time required for a)
+-6.388 F .712(processor to search one node and return to the top of Sea\
+rch\(\) and then store the "tree state" for the idle)72 324 R .982
+(processor to e)72 336 R 3.732(xamine. \(About)-.165 F .981
+(30 microseconds on a Cray C90.\))3.732 F .981
+(After this time, an idle processor will)6.481 F(ha)72 348 Q .33 -.165
+(ve a)-.22 H 2.75(tl).165 G(east one tree state to e)-2.75 E
+(xamine for split points, making this reasonably ef)-.165 E(\214cient.)
+-.275 E 1.001(While it sounds lik)72 372 R 3.751(eal)-.11 G 1.001
+(ot of w)-3.751 F 1.001(ait time could accumulate, man)-.11 F 3.751(yt)
+-.165 G 1.001(ests on a C90 ha)-3.751 F 1.332 -.165(ve c)-.22 H 1.002
+(on\214rmed that this).165 F -.11(wa)72 384 S .232(it time is ne).11 F
+2.982(gligible. In)-.165 F .231(searching for 5-6 minutes of w)2.982 F
+.231(all-clock time, typical idle times \(per processor\))-.11 F -2.475
+-.22(av e)72 396 T .566(rage between .01 seconds and .1 seconds.).22 F
+.566(On rare occasions \(notably v)6.066 F .566(ery simple endg)-.165 F
+.567(ame positions)-.055 F .666(where the branching f)72 408 R .666
+(actor is quite lo)-.11 F .665
+(w\) this has reached one second per processor)-.275 F 3.415(,s)-.44 G
+.665(till k)-3.415 F .665(eeping the idle)-.11 F .882
+(time per processor do)72 420 R .882
+(wn to less than .3% of the total search time.)-.275 F .883
+(One major reason for this is that the)6.383 F .279
+(code which selects split points is v)72 432 R .279(ery careful, and f)
+-.165 F -.22(avo)-.11 G .279
+(rs nodes near the root of the tree, because the sub-).22 F 1.307
+(trees belo)72 444 R 4.057(wt)-.275 G 1.307
+(hose nodes represent a signi\214cant amount of w)-4.057 F 1.307
+(ork that must be completed before another)-.11 F .703
+(split point must be found.)72 456 R .703
+(The only time that processors are idle is while the)6.203 F 3.452(ya)
+-.165 G .702(re w)-3.452 F .702(aiting on other pro-)-.11 F .573
+(cessors to pro)72 468 R .573
+(vide tree state information to one idle processor)-.165 F 3.324(,o)-.44
+G 3.324(rw)-3.324 G .574(hile the)-3.324 F 3.324(ya)-.165 G .574(re w)
+-3.324 F .574(aiting on one idle pro-)-.11 F .071
+(cessor to select a split point.)72 480 R .071(If this e)5.571 F -.165
+(ve)-.275 G .071(nt is relati).165 F -.165(ve)-.275 G .07
+(ly rare, as it typically is in DTS, then the opportunities).165 F
+(for accumulating e)72 492 Q(xcessi)-.165 E .33 -.165(ve i)-.275 H
+(dle time are fe).165 E 2.75(wa)-.275 G(nd f)-2.75 E(ar between.)-.11 E
+2.75(2.4 The)72 516 R(Split\(\) operation.)2.75 E .315
+(Split\(\) is called whene)72 540 R -.165(ve)-.275 G 3.065(ra).165 G
+3.065(ni)-3.065 G .315
+(dle processor has one or more "tree state" blocks to e)-3.065 F .316
+(xamine when attempt-)-.165 F .267(ing to \214nd a split-point.)72 552 R
+.266(Split\(\) \214rst attempts to \214nd a good split point \(section \
+three\) and then sets things)5.767 F(up so that the Select\(\) operatio\
+n described later can function correctly)72 564 Q(.)-.715 E EP
+%%Page: 8 8
+%%BeginPageSetup
+BP
+%%EndPageSetup
+/F0 11/Times-Roman@0 SF .557(The \214rst operation performed after a go\
+od split-point is located is to allocate a data structure kno)72 96 R
+.557(wn as a)-.275 F 1.231(SPLIT BLOCK.)72 108 R 1.23
+(This data structure is simply an e)6.731 F 1.23
+(xact duplicate of the tree search data structures that)-.165 F .028
+(already e)72 120 R .029(xist in each processor')-.165 F 2.779(sl)-.605
+G .029(ocal memory area.)-2.779 F .029(It contains the v)5.529 F .029
+(arious mo)-.275 F .359 -.165(ve l)-.165 H .029
+(ists, board information,).165 F(scoring information, etc.)72 132 Q .265
+(The Split\(\) operation then copies ALL of the current processor')72
+156 R 3.015(sl)-.605 G .265(ocal tree state information to the SPLIT)
+-3.015 F 3.208(BLOCK. \(ALL)72 168 R .458
+(here means that if the current ply is \214v)3.208 F 3.208(e\()-.165 G
+.458(5\), then all of the data for plies 1-5 are copied,)-3.208 F -.22
+(bu)72 180 S 4.901(tn).22 G 2.151(ot all of the useless data belo)-4.901
+F 4.901(wp)-.275 G 2.151(ly 5.)-4.901 F 2.151(Note that EVER)7.651 F
+2.15(YTHING is copied, so that this global)-.715 F .806
+(\(shared\) memory area has an e)72 192 R .807(xact cop)-.165 F 3.557
+(yo)-.11 G 3.557(ft)-3.557 G .807(he current processor')-3.557 F 3.557
+(ss)-.605 G .807(earch data structures.)-3.557 F .807(It w)6.307 F .807
+(ould no)-.11 F(w)-.275 E .026(be possible for this processor to e)72
+204 R .026(xit, and another processor could cop)-.165 F 2.776(yt)-.11 G
+.026(his global data to its pri)-2.776 F -.275(va)-.275 G .025(te mem-)
+.275 F .497(ory area and resume the search just as if it were the origi\
+nal processor since it no)72 216 R 3.247(ww)-.275 G .497(ould ha)-3.357
+F .827 -.165(ve a)-.22 H .497(ccess to).165 F -2.365 -.275(ev e)72 228 T
+.406(rything the original processor had.).275 F 3.156(\(Note: Cray)5.906
+F .406(Blitz w)3.156 F .405(as written before F)-.11 F .405
+(ortran supported recursion,)-.165 F 1.075
+(and as a result, it did not use the no)72 240 R 3.825(wi)-.275 G 3.825
+(nv)-3.825 G 1.075(ogue "ne)-4.045 F -.055(ga)-.165 G 1.075
+(max" recursi).055 F 1.405 -.165(ve a)-.275 H 1.075
+(lpha/beta search implementation.).165 F .118(As a result, there w)72
+252 R .118(as no problem in implementing the parallel search as e)-.11 F
+2.868(xplained. Ne)-.165 F -.055(ga)-.165 G .117(max w).055 F .117
+(ould ha)-.11 F -.165(ve)-.22 G 1.058(made it much more dif)72 264 R
+1.058(\214cult, since the call stack is inaccessible to the search code\
+ and mo)-.275 F 1.059(ving the tree)-.165 F(state around w)72 276 Q
+(ould ha)-.11 E .33 -.165(ve b)-.22 H(een much more dif).165 E
+(\214cult [Pearl80].\))-.275 E .733(The Split\(\) operation then passes\
+ the address of this SPLIT BLOCK to an)72 300 R 3.483(yp)-.165 G .733
+(rocessors that are currently)-3.483 F .224(idle, so that the)72 312 R
+2.974(ym)-.165 G .224(ay be)-2.974 F .224(gin w)-.165 F .224
+(orking at this point immediately)-.11 F 5.725(.T)-.715 G .225
+(he idle processors drop out of their b)-5.725 F(usy)-.22 E -.11(wa)72
+324 S 1.109(it loop since the).11 F 3.859(yn)-.165 G 1.659 -.275(ow h)
+-3.859 H -2.475 -.22(av e).275 H 3.859(ap)4.079 G 1.108(ointer to a v)
+-3.859 F 1.108(alid SPLIT BLOCK rather than a v)-.275 F 1.108
+(alue of "zero".)-.275 F(The)6.608 E(y)-.165 E(must \214rst cop)72 336 Q
+2.75(yt)-.11 G(he global data to their pri)-2.75 E -.275(va)-.275 G
+(te memory area, and then be).275 E(gin searching at that point.)-.165 E
+.258(The primary reason for cop)72 360 R .258
+(ying ALL of the "splitting" processor')-.11 F 3.009(sd)-.605 G .259
+(ata to the shared memory re)-3.009 F .259(gion is to)-.165 F -.22(avo)
+72 372 S 1.046(id an).22 F 3.796(yt)-.165 G 1.045(ype of synchronizatio\
+n delays after searching all branches from the split-point.)-3.796 F
+1.045(The speci\214c)6.545 F .607(problem addressed is that the "contro\
+lling" processor \(the one splitting w)72 384 R .608
+(ork for other processors to help)-.11 F .548
+(with\) might choose a branch that is v)72 396 R .548
+(ery simple with a minimum number of nodes and \214nish this branch)
+-.165 F .902(quite quickly)72 408 R 6.402(.A)-.715 G .902
+(nother processor might choose a branch that has man)-6.402 F 3.653(yc)
+-.165 G .903(hecks and/or search e)-3.653 F(xtensions)-.165 E 1.666
+(and requires an e)72 420 R 1.666(xtended amount of time to search.)
+-.165 F 1.666(The controlling processor w)7.166 F 1.665
+(ould often \214nd itself)-.11 F -.11(wa)72 432 S .673
+(iting on other processors to complete their searches and return the v)
+.11 F .674(alues for their subtrees before the)-.275 F
+(controlling processor could back up the proper v)72 444 Q(alue.)-.275 E
+-.44(Wi)72 468 S .375(th the current implementation, this ne).44 F -.165
+(ve)-.275 G 3.125(rh).165 G 3.125(appens. Since)-3.125 F .375
+(ALL processors ha)3.125 F .705 -.165(ve a c)-.22 H .375(omplete cop)
+.165 F 3.125(yo)-.11 G 3.125(ft)-3.125 G(he)-3.125 E .694
+(search data, an)72 480 R 3.444(yo)-.165 G 3.444(ft)-3.444 G .694(hem i\
+s capable of \214nishing the search of the nodes in the tree after the \
+split-point is)-3.444 F 2.751(completed. F)72 492 R .001(or e)-.165 F
+.001(xample, processor 1 can search from plies 1 through 5 and then ano\
+ther processor selects)-.165 F 1.294(ply=5 as a split-point.)72 504 R
+1.295(Processor 2 joins the search at this split-point and selects a br\
+anch to e)6.794 F(xamine.)-.165 E .455(Processor 1 completes the remain\
+der of the branches at this split-point and then sends a HELP command)72
+516 R 1.552
+(to processor 2 so that it can help with the remainder of the comple)72
+528 R 4.303(xb)-.165 G 1.553(ranch processor 2 is searching.)-4.303 F
+1.018(When the search \214nally backs up to ply=1, EITHER processor \(b)
+72 540 R 1.018(ut not both\) could be in char)-.22 F 1.017(ge of the)
+-.198 F .019
+(search at that point; it depends on which one \214nishes \214rst.)72
+552 R .019(In simple terms, this is a "peer)5.519 F .02
+(-to-peer" design,)-.22 F(rather than a "master)72 564 Q(-sla)-.22 E
+-.165(ve)-.22 G 2.75("d).165 G(esign, so that all processors are equal.)
+-2.75 E EP
+%%Page: 9 9
+%%BeginPageSetup
+BP
+%%EndPageSetup
+/F0 11/Times-Roman@0 SF .093
+(The nice feature of this approach is that whene)72 96 R -.165(ve)-.275
+G 2.842(rA).165 G .092(NY processor runs out of w)-2.842 F .092
+(ork at a split-point, it then)-.11 F .49(assists one of the b)72 108 R
+.49(usy processors by \214rst sending a HELP command to force the creat\
+ion of a ne)-.22 F 3.241(ws)-.275 G(plit-)-3.241 E .663
+(point where this idle processor can "join in.")72 120 R .663
+(This feature is implemented by a simple rule that pre)6.163 F -.165(ve)
+-.275 G(nts).165 E(an)72 132 Q 3.464(yp)-.165 G .714(rocessor from back\
+ing the search up past a split point, unless \(if and only if\) only on\
+e processor is)-3.464 F -.11(wo)72 144 S .181
+(rking on that split point.).11 F .18(The best visual analogy is the g)
+5.68 F .18(ame of "leap-frog" where one processor starts)-.055 F .685(o\
+n a position, another helps it, the \214rst \214nishes and "leap-frogs"\
+ the second to a position further into the)72 156 R(tree and helps the \
+second processor search at that point, and so forth.)72 168 Q 2.75
+(2.5 The)72 192 R(Select\(\) operation.)2.75 E 1.079(one of the tw)72
+216 R 3.829(og)-.11 G 1.078
+(oals mentioned when designing the DTS algorithm w)-3.829 F 1.078
+(as to a)-.11 F -.22(vo)-.22 G 1.078(id completely re-writing).22 F .307
+(the search code for Cray Blitz.)72 228 R .308
+(This code \(approximately 10,000 lines of FOR)5.807 F .308
+(TRAN, which are replaced)-.66 F .35(by about 20,000 lines of Cray Asse\
+mbly Language [CAL] when running on the C90\) has been de)72 240 R -.165
+(ve)-.275 G(loped).165 E 1.21(and deb)72 252 R 1.21(ugged o)-.22 F -.165
+(ve)-.165 G 3.96(rap).165 G 1.21
+(eriod of years, and altering it signi\214cantly w)-3.96 F 1.211
+(as something the authors w)-.11 F 1.211(anted to)-.11 F -.22(avo)72 264
+S(id if possible since deb).22 E
+(ugging the parallel processing code already loomed as a lar)-.22 E
+(ge obstacle.)-.198 E -.165(Fo)72 288 S 3.376(rs).165 G(implicity)-3.376
+E 3.376(,t)-.715 G .626(he design retained the original programming met\
+hodology that a processor maintains the)-3.376 F 1.152
+(tree \(subtree, actually\) it is searching by k)72 300 R 1.152
+(eeping all of the related data in local \(pri)-.11 F -.275(va)-.275 G
+1.152(te, task common,).275 F(etc.\) memory so that other processors ca\
+n not "change" this information directly)72 312 Q(.)-.715 E(Ho)72 336 Q
+(we)-.275 E -.165(ve)-.275 G 1.079 -.44(r, s).165 H .199
+(ince a group of processors must w).44 F .198
+(ork together at some point within the tree, shared memory is)-.11 F
+.022(also required to allo)72 348 R 2.772(wt)-.275 G .022
+(his communication.)-2.772 F .022
+(The simple implementation mechanism we chose w)5.522 F .023(as to mod-)
+-.11 F(ify the procedure Select\(\) so that it could w)72 360 Q
+(ork in this en)-.11 E(vironment.)-.44 E .716
+(Select\(\) is a procedure called to select the ne)72 384 R .715(xt mo)
+-.165 F 1.045 -.165(ve a)-.165 H 3.465(tt).165 G .715
+(he current node in the tree.)-3.465 F(Normally)6.215 E 3.465(,i)-.715 G
+3.465(te)-3.465 G(xam-)-3.63 E 1.611(ines the mo)72 396 R 1.941 -.165
+(ve l)-.165 H 1.612(ist in the pri).165 F -.275(va)-.275 G 1.612
+(te memory for the current processor and remo).275 F -.165(ve)-.165 G
+4.362(so).165 G 1.612(ne of the mo)-4.362 F -.165(ve)-.165 G 4.362(sf)
+.165 G(or)-4.362 E -.165(ex)72 408 S 3.946(amination. At).165 F 3.946
+(as)3.946 G 1.196(plit-point, this is slightly more complicated since m\
+ultiple processors are "sharing")-3.946 F(this mo)72 420 Q .33 -.165
+(ve l)-.165 H(ist.).165 E 1.29
+(Select\(\) is unchanged, the only code that w)72 444 R 1.291
+(as modi\214ed w)-.11 F 1.291
+(as the code that actually calls Select\(\) within)-.11 F 2.909
+(Search\(\). Search\(\))72 456 R .159(simply tests to see if the curren\
+t ply is a split point, and if so it copies the shared mo)2.909 F -.165
+(ve)-.165 G .917(list to the local mo)72 468 R 1.248 -.165(ve l)-.165 H
+.918(ist, calls Select\(\) to choose one for searching and then remo)
+.165 F -.165(ve)-.165 G 3.668(si).165 G 3.668(tf)-3.668 G .918
+(rom the mo)-3.668 F -.165(ve)-.165 G .531
+(list. Search\(\) then copies the local mo)72 480 R .861 -.165(ve l)
+-.165 H .53
+(ist back to the shared one \(all protected by a semaphore so that).165
+F .131(no race conditions arise\).)72 492 R .131(If the current ply is \
+not a split point, Select\(\) is simply called normally)5.631 F 5.632
+(.t)-.715 G .132(he fol-)-5.632 F(lo)72 504 Q 1.494(wing code sho)-.275
+F 1.494(ws ho)-.275 F 4.244(wt)-.275 G 1.494(his w)-4.244 F 1.494
+(as implemented.)-.11 F 1.494
+(The major bene\214t here is that Select\(\) is a v)6.994 F 1.493
+(ery lar)-.165 F(ge)-.198 E .6(block of code, that generates mo)72 516 R
+-.165(ve)-.165 G .6(s, orders the list, selects mo).165 F -.165(ve)-.165
+G 3.35(sf).165 G .601(rom the list based on things lik)-3.35 F 3.351(ec)
+-.11 G(ap-)-3.351 E 1.49(tures and the e)72 528 R 1.49(xpected g)-.165 F
+1.49(ain, killer mo)-.055 F -.165(ve)-.165 G 1.49(s, and so forth.).165
+F 1.49(It w)6.99 F 1.49(as considered v)-.11 F 1.489
+(ery desirable to lea)-.165 F 1.819 -.165(ve t)-.22 H(his).165 E
+(completely alone, since the assembly v)72 540 Q
+(ersion of this module is se)-.165 E -.165(ve)-.275 G
+(ral thousand lines long.).165 E(call Select\(\))99.5 564 Q EP
+%%Page: 10 10
+%%BeginPageSetup
+BP
+%%EndPageSetup
+/F0 11/Times-Roman@0 SF -.11(wa)72 96 S 2.75(sr).11 G
+(eplaced by the follo)-2.75 E(wing lines of code:)-.275 E
+(if\(ply .eq. splitl\(taskid\)\) then)99.5 120 Q(call Selget\(\))110.5
+132 Q(call Select\(\))110.5 144 Q(call Selput\(\))110.5 156 Q(else)99.5
+168 Q(call Select\(\))110.5 180 Q(endif)99.5 192 Q .425(In the abo)72
+216 R .755 -.165(ve c)-.165 H .425
+(ode, Selget\(\) sets a semaphore to lock this mo).165 F .755 -.165
+(ve l)-.165 H .425(ist \(there are multiple semaphores so that).165 F
+.191(multiple mo)72 228 R .52 -.165(ve l)-.165 H .19(ists can be shared\
+ without unnecessary interaction\) and then copies the global mo).165 F
+.52 -.165(ve l)-.165 H .19(ist to).165 F .568(the local memory)72 240 R
+3.318(.S)-.715 G .568(elect\(\) then operates normally)-3.318 F 6.068
+(.S)-.715 G .568(elput\(\) then copies the mo)-6.068 F .898 -.165(ve l)
+-.165 H .569(ist back \(after a mo).165 F -.165(ve)-.165 G
+(has been remo)72 252 Q -.165(ve)-.165 G 2.75(df).165 G
+(or searching\) and \214nally clears the semaphore.)-2.75 E .752(The v)
+72 276 R .751(ector splitl\(taskid\) is set up by the split operation a\
+nd identi\214es the current split point for this pro-)-.165 F .736
+(cessor \(taskid\).)72 288 R .737(It should be noted that this implemen\
+tation is quite good in terms of ef)6.236 F(\214cienc)-.275 E 2.167
+-.715(y, b)-.165 H(ecause).715 E .353(the Selget\(\) \(cop)72 300 R
+3.103(ys)-.11 G .352(hared memory to local memory\) and the Selput\(\) \
+\(back to shared memory\) operations)-3.103 F 1.311
+(are rarely used, and on a Cray the)72 312 R 4.061(yv)-.165 G 1.312
+(ectorize quite well and cost v)-4.226 F 1.312(ery little.)-.165 F 1.312
+(Note that this same code)6.812 F -.11(wo)72 324 S .911(rks well withou\
+t parallel processing since Selget\(\) and Selput\(\) are ne).11 F -.165
+(ve)-.275 G 3.661(rc).165 G .911(alled if a Split\(\) operation)-3.661 F
+(has not been performed.)72 336 Q 2.75(2.6 The)72 360 R(Mer)2.75 E
+(ge\(\) operation.)-.198 E(Whene)72 384 Q -.165(ve)-.275 G 2.897(rap)
+.165 G .147(rocessor calls Select\(\) and is told that the mo)-2.897 F
+-.165(ve)-.165 G 2.898(sl).165 G .148(ist is empty)-2.898 F 2.898(,t)
+-.715 G .148(he \214rst test made by the DTS)-2.898 F .702
+(search algorithm is "is this a split-point?")72 396 R .702
+(If the answer is yes, this processor has computed a v)6.202 F .701
+(alue that)-.275 F .225
+(represents only a subset of the branches from this node.)72 408 R .226
+(The DTS Search no)5.726 F 2.976(wc)-.275 G .226(alls procedure Mer)
+-2.976 F .226(ge\(\) to)-.198 F .397(process this partial v)72 420 R
+3.147(alue. Mer)-.275 F .396(ge\(\) simply compares the search v)-.198 F
+.396(alue from the current partial search with)-.275 F .983
+(the best search v)72 432 R .984(alue for this node yet back)-.275 F
+.984(ed up, and remembers the best result.)-.11 F .984
+(It also notes that one)6.484 F 1.367(less processor is w)72 444 R 1.366
+(orking at this split point by decrementing the processor count.)-.11 F
+1.366(If this count is no)6.866 F(w)-.275 E -.165(ex)72 456 S .252
+(actly one, the split-point is no longer needed; in this case, Mer).165
+F .252(ge\(\) sends an UNSPLIT command to the)-.198 F
+(remaining processor \(described belo)72 468 Q -.715(w.)-.275 G(\)).715
+E .333(After the cleanup is completed via Mer)72 492 R .332
+(ge\(\), the DTS algorithm then returns this processor to its idle loop)
+-.198 F .501(where it immediately checks for another split-point to joi\
+n, or else it generates a HELP command to cre-)72 504 R
+(ate a split-point.)72 516 Q 2.75(2.7 The)72 540 R
+(Unsplit\(\) operation.)2.75 E .076(The ne)72 564 R .076
+(xt-to-last processor w)-.165 F .076(orking on a split point sends an U\
+NSPLIT command to the remaining proces-)-.11 F(sor)72 576 Q 2.818(,w)
+-.44 G(hene)-2.818 E -.165(ve)-.275 G 2.818(ri).165 G 2.818<748c>-2.818
+G .068(nds no more w)-2.818 F .068(ork to do at this split point.)-.11 F
+.068(The split-point has been completely searched)5.568 F EP
+%%Page: 11 11
+%%BeginPageSetup
+BP
+%%EndPageSetup
+/F0 11/Times-Roman@0 SF -.165(ex)72 96 S
+(cept for the branch being analyzed by the remaining processor).165 E(.)
+-.605 E 2.147(When a processor recei)72 120 R -.165(ve)-.275 G 4.897(sa)
+.165 G 4.897(nU)-4.897 G 2.147
+(NSPLIT command, it calls procedure Unsplit\(\) to cleanup the split-)
+-4.897 F .221(point\(S\) that ha)72 132 R .551 -.165(ve b)-.22 H .221(e\
+en "almost completed" \(recall that the current processor is STILL sear\
+ching a branch).165 F(at one or more of these e)72 144 Q
+(xhausted split-points.\))-.165 E .028(Unsplit\(\) performs tw)72 168 R
+2.778(oa)-.11 G 2.778(ctions. The)-2.778 F .028(\214rst action it tak)
+2.778 F .027(es is to compare the partial score from the split-point)
+-.11 F .42(with its o)72 180 R .42
+(wn partial score for that ply and remember the best one.)-.275 F .42
+(It then deallocates the SPLIT BLOCK)5.92 F .982
+(so that this block can be used whene)72 192 R -.165(ve)-.275 G 3.731
+(ra).165 G .981(nother Split\(\) operation is required.)-3.731 F .981
+(After an Unsplit\(\) opera-)6.481 F(tion, all signs of the pre)72 204 Q
+(vious Split\(\) operation are gone.)-.275 E 2.75(2.8 The)72 228 R
+(Share\(\) operation.)2.75 E 1.051(Since the ef)72 252 R(\214cienc)-.275
+E 3.801(yo)-.165 G 3.801(ft)-3.801 G 1.051
+(he alpha/beta algorithm directly depends on kno)-3.801 F 1.051
+(wing the best scores back)-.275 F 1.052(ed up)-.11 F 1.525
+(through the tree, whene)72 264 R -.165(ve)-.275 G 4.275(rb).165 G 1.525
+(acking up a ne)-4.275 F 4.274(wb)-.275 G 1.524
+(est score to a split-point ply \(by an)-4.274 F 4.274(yo)-.165 G 4.274
+(ft)-4.274 G 1.524(he processors)-4.274 F -.11(wo)72 276 S
+(rking at that split-point\), special action is required.).11 E .971
+(The re)72 300 R .971(gular search procedure Backup\(\) w)-.165 F .972
+(as modi\214ed to check for this condition in the same manner as)-.11 F
+1.06(Select\(\) described pre)72 312 R(viously)-.275 E 3.81(,i)-.715 G
+3.81(tc)-3.81 G 1.06
+(hecks the SPLITL\(i\) \215ag to determine if it is "w)-3.81 F 1.06
+(orking together" with)-.11 F .182(another processor)72 324 R 5.682(.I)
+-.605 G 2.932(fs)-5.682 G .182
+(o, it sends a SHARE command to all processors w)-2.932 F .182
+(orking at this split- point.)-.11 F(These)5.683 E .193
+(processors then call Share\(\) to determine if this ne)72 336 R .193
+(wly back)-.275 F .192(ed up v)-.11 F .192(alue is better than the v)
+-.275 F .192(alue in this pro-)-.275 F(cessor')72 348 Q 3.565(ss)-.605 G
+3.565(earch. If)-3.565 F .815(so, some quick tests for alpha/beta cutof)
+3.565 F .816(fs are made to determine if this ne)-.275 F .816(wly a)
+-.275 F -.275(va)-.22 G(il-).275 E(able v)72 360 Q(alue w)-.275 E
+(ould prune a)-.11 E -.11(wa)-.165 G 2.75(yp).11 G
+(art of the tree currently being searched by this processor)-2.75 E(.)
+-.605 E .161(This procedure w)72 384 R .161(as added to address tw)-.11
+F 2.911(op)-.11 G 2.91(roblems. \(1\))-2.911 F .16(When a better v)2.91
+F .16(alue is found at a split-point, ef)-.275 F<8c2d>-.275 E(cienc)72
+396 Q 4.368(yd)-.165 G 1.618(emands that all processors be made a)-4.368
+F -.11(wa)-.165 G 1.619
+(re of it as soon as possible in order to maximize the).11 F .109
+(alpha/beta ef)72 408 R(\214cienc)-.275 E 4.289 -.715(y. \()-.165 H
+2.859(2\) W).715 F 2.859(ea)-.88 G .109(nticipated the case where the s\
+earch might create a split-point at a location)-2.859 F .717
+(within the tree where either alpha or beta might be unkno)72 420 R .717
+(wn \(this is the idea of speculati)-.275 F 1.048 -.165(ve s)-.275 H
+.718(earching to).165 F -.11(ke)72 432 S .59(ep processors b).11 F .59
+(usy described earlier)-.22 F 3.339(.\) Share\(\))-.605 F .589
+(determines these v)3.339 F .589(alues for the current processor when-)
+-.275 F -2.365 -.275(ev e)72 444 T 2.75(rt).275 G(he)-2.75 E 2.75(yb)
+-.165 G(ecome a)-2.75 E -.275(va)-.22 G(ilable.).275 E 2.75(3. Choosing)
+72 468 R(where to split the tree.)2.75 E 1.027(The most important decis\
+ion that the DTS algorithm frequently addresses is where to split the t\
+ree into)72 492 R 1.083(parallel subtrees.)72 504 R 1.083(If it chooses\
+ a good split point, performance is good; if it chooses a poor split po\
+int,)6.583 F(performance suf)72 516 Q(fers.)-.275 E(3.1 Node types PV)72
+540 Q 2.75(,C)-1.419 G(UT and ALL.)-2.75 E 3.097(Knuth and Moore clearl\
+y de\214ned three node classes of nodes within the alpha/beta minimax t\
+ree)72 564 R 4.378([Knut75]. While)72 576 R 1.628(their analysis w)4.378
+F 1.628(as centered on a minimal g)-.11 F 1.627
+(ame-tree with perfect mo)-.055 F 1.957 -.165(ve o)-.165 H 1.627
+(rdering, the).165 F EP
+%%Page: 12 12
+%%BeginPageSetup
+BP
+%%EndPageSetup
+/F0 11/Times-Roman@0 SF .386(concepts the)72 96 R 3.136(yp)-.165 G .386
+(resented also apply to "real" alpha/beta trees, e)-3.136 F -.165(ve)
+-.275 G 3.136(nt).165 G .386(hough it is impossible to produce per)
+-3.136 F(-)-.22 E .611(fect mo)72 108 R .94 -.165(ve o)-.165 H .61
+(rdering [Hyatt89].).165 F .61(In this conte)6.11 F .61
+(xt we use the terminology de)-.165 F -.165(ve)-.275 G .61
+(loped in [Marsland85], which).165 F(uses the terms PV)72 120 Q 2.75(,C)
+-1.419 G(UT and ALL instead of type one, tw)-2.75 E 2.75(oa)-.11 G
+(nd three.)-2.75 E -.88(Ty)108 144 S .768(pe one \(PV\) nodes.).88 F
+.769(The root position is a type one node.)6.268 F .769
+(The \214rst successor)6.269 F .346(of a PV node is also a PV node whil\
+e all other successors of a PV node are CUT)108 156 R 3.17(nodes. PV)108
+168 R .42(nodes require e)3.17 F .421
+(xamination of all their successors.)-.165 F 3.171(AP)5.921 G 3.171(Vn)
+-3.171 G .421(ode is easy)-3.171 F .643
+(to recognize, because both alpha and beta are at their original v)108
+180 R .643(alues since noth-)-.275 F(ing has yet been searched.)108 192
+Q -.88(Ty)108 216 S .02(pe tw).88 F 2.77(o\()-.11 G .02(CUT\) nodes.)
+-2.77 F 2.771(AC)5.521 G .021
+(UT node is a successor of either a PV node \(as gi)-2.771 F -.165(ve)
+-.275 G(n).165 E(abo)108 228 Q -.165(ve)-.165 G 3.434(\)o).165 G 3.433
+(ra)-3.434 G 3.433(nA)-3.433 G .683(LL node.)-3.433 F 3.433(AC)6.183 G
+.683(UT node only requires e)-3.433 F .683(xamination of one succes-)
+-.165 F .407(sor \(for perfectly ordered g)108 240 R .407(ame trees.\))
+-.055 F .407(This is the node type that we must recog-)5.907 F .99
+(nize and a)108 252 R -.22(vo)-.22 G .989
+(id selecting as a split-point, because with best mo).22 F 1.319 -.165
+(ve o)-.165 H .989(rdering, only).165 F .206
+(one branch needs to be searched, which lea)108 264 R -.165(ve)-.22 G
+2.957(sn).165 G 2.957(ow)-2.957 G .207(ork for additional processors,)
+-3.067 F(other than w)108 276 Q(ork that is completely unnecessary)-.11
+E(.)-.715 E -.88(Ty)108 300 S 2.43(pe three \(ALL\) nodes.).88 F 2.43
+(An ALL node is a successor of a CUT node and)7.93 F .719(requires e)108
+312 R .72(xamination of all its successor branches.)-.165 F(Ev)6.22 E
+.72(en more interesting, mo)-.165 F -.165(ve)-.165 G .335(ordering with\
+in a type three node is completely unimportant and has no ef)108 324 R
+.335(fect on)-.275 F 2.053(the total nodes searched.)108 336 R 2.054
+(This is an important node type in a parallel search)7.554 F .806
+(because e)108 348 R -.165(ve)-.275 G .806(ry mo).165 F 1.136 -.165
+(ve m)-.165 H .806(ust be searched, of).165 F .806(fering plenty of w)
+-.275 F .805(ork that can be done)-.11 F(in parallel.)108 360 Q 1.164
+(From these de\214nitions, se)72 384 R -.165(ve)-.275 G 1.164
+(ral things become apparent.).165 F 1.164(\(1\) T)6.664 F 1.164
+(ype three \(ALL\) nodes are perfect candi-)-.88 F .276(dates for paral\
+lel searching since all successors must be searched, and the order of t\
+ra)72 396 R -.165(ve)-.22 G .276(rsal for these suc-).165 F .152
+(cessors is unimportant.)72 408 R 2.902(\(2\) T)5.652 F .152(ype tw)-.88
+F 2.902(o\()-.11 G .152(CUT\) nodes must be a)-2.902 F -.22(vo)-.22 G
+.153(ided as split points since only one succes-).22 F .225
+(sor must be e)72 420 R 2.975(xamined. If)-.165 F .225
+(such a node is chosen as a split point, e)2.975 F .225
+(xtra branches will be searched, resulting)-.165 F .91(in w)72 432 R .91
+(asted w)-.11 F 3.66(ork. \(3\))-.11 F -.88(Ty)3.66 G .91(pe one \(PV\)\
+ nodes appear to be good candidates for parallel search until careful)
+.88 F 1.023(study unco)72 444 R -.165(ve)-.165 G 1.023(rs the f).165 F
+1.023
+(act that the \214rst successor of a type one node must be completely e)
+-.11 F 1.022(xamined before)-.165 F(an)72 456 Q 4.358(yo)-.165 G 4.358
+(ft)-4.358 G 1.608(he other successors.)-4.358 F 1.608(This is required\
+ since the \214rst branch establishes a search bound for the)7.108 F
+1.174(remainder of the successors, and if the)72 468 R 3.924(ya)-.165 G
+1.174(re searched before this bound is kno)-3.924 F 1.174(wn, e)-.275 F
+1.174(xtra w)-.165 F 1.174(ork might be)-.11 F(done.)72 480 Q 2.75
+(3.2 Classifying)72 504 R(node types.)2.75 E .563(When a processor gene\
+rates a HELP command, and obtains tree-state data from b)72 528 R .564
+(usy processors, it must)-.22 F .408(\(if possible\) establish a split \
+point so that it \(and other idle processors\) can "join in" and help.)
+72 540 R .408(From sec-)5.908 F .39(tion 3.1, it becomes ob)72 552 R .39
+(vious that type ALL nodes mak)-.165 F 3.141(ed)-.11 G .391
+(esirable split points, type PV nodes mak)-3.141 F 3.141(ed)-.11 G(esir)
+-3.141 E(-)-.22 E 1.62(able split points AFTER the \214rst successor of\
+ the node has been completely searched, and type CUT)72 564 R
+(nodes must be a)72 576 Q -.22(vo)-.22 G(ided at all costs.).22 E EP
+%%Page: 13 13
+%%BeginPageSetup
+BP
+%%EndPageSetup
+/F0 11/Times-Roman@0 SF 1.52(Cray Blitz contains a function T)72 96 R
+1.52(ypeNode\(\), that types an)-.88 F 4.27(yn)-.165 G 1.52
+(ode from ply one to the current ply)-4.27 F 9.771(.t)-.715 G(his)-9.771
+E .574(function is called by function Split\(\) to mak)72 108 R 3.323
+(ea)-.11 G 3.323(ni)-3.323 G .573
+(nitial "guess" of the node types for each ply in the cur)-3.323 F(-)
+-.22 E(rent processor')72 120 Q 2.75(ss)-.605 G(earch space.)-2.75 E
+.239(It mak)72 144 R .239(es the follo)-.11 F .239(wing assumptions.)
+-.275 F .239(If, for the current node being tested, the v)5.739 F .24
+(alues of alpha and beta are)-.275 F .06
+(equal to the initial search windo)72 156 R 1.49 -.715(w, t)-.275 H .06
+(hen this node is a PV node.).715 F .059
+(Otherwise, if the current node is at an odd)5.559 F .683
+(ply and alpha is equal to the lo)72 168 R .684
+(wer initial search bound, or the current node is at an e)-.275 F -.165
+(ve)-.275 G 3.434(np).165 G .684(ly and beta is)-3.434 F
+(equal to the upper initial search bound, then the node type is CUT)72
+180 Q 5.5(.F)-.814 G(or all other cases, it is type ALL.)-5.665 E .642
+(Split\(\) uses the abo)72 204 R .971 -.165(ve a)-.165 H .641(lgorithm \
+to set its initial guess for each node type from ply 1 through the curr\
+ent).165 F(ply)72 216 Q 5.915(.N)-.715 G -.165(ex)-5.915 G 3.165(ti).165
+G 3.165(te)-3.165 G .416(nters an "o)-3.165 F -.165(ve)-.165 G .416
+(rride" phase.).165 F .416
+(Split\(\) starts at ply=2 and checks the number of mo)5.916 F -.165(ve)
+-.165 G 3.166(st).165 G .416(hat ha)-3.166 F -.165(ve)-.22 G 1.132
+(been zeroed by the search \(the number of mo)72 228 R -.165(ve)-.165 G
+3.881(st).165 G 1.131(hat ha)-3.881 F 1.461 -.165(ve a)-.22 H 1.131
+(ctually been searched.\)).165 F -.165(Fo)6.631 G 3.881(ra).165 G 3.881
+(nA)-3.881 G 1.131(LL node,)-3.881 F(man)72 240 Q 3.087(ym)-.165 G -.165
+(ove)-3.087 G 3.087(sa).165 G .338(lready searched increases the "con\
+\214dence" that this is truly an ALL node.)-3.087 F -.165(Fo)5.838 G
+3.088(rC).165 G .338(UT nodes,)-3.088 F 1.527(if more than one mo)72 252
+R 1.856 -.165(ve h)-.165 H 1.526
+(as been searched, then the con\214dence for this CUT node is lo).165 F
+1.526(wered, since it)-.275 F 1.014
+(should not be necessary to search more than one mo)72 264 R 1.344 -.165
+(ve a)-.165 H -6.513 3.764(ta r).165 H 1.015(eal CUT node.)-3.764 F
+1.015(In f)6.515 F 1.015(act, if more than some)-.11 F .361(limit of mo)
+72 276 R -.165(ve)-.165 G 3.111(sh).165 G .361(as been e)-3.111 F .361
+(xamined \(currently=3\) then the type for this node is o)-.165 F -.165
+(ve)-.165 G .36(rridden and set to ALL,).165 F .161
+(since it appears that mo)72 288 R .491 -.165(ve o)-.165 H .161
+(rdering has someho).165 F 2.912(wf)-.275 G .162
+(ailed to search the best mo)-3.022 F .492 -.165(ve \214)-.165 H .162
+(rst at some pre).165 F .162(vious ply)-.275 F(.)-.715 E .252
+(After this o)72 312 R -.165(ve)-.165 G .251
+(rride phase, a \214nal simple check is made since it is no).165 F 3.001
+(wp)-.275 G .251(ossible to ha)-3.001 F .581 -.165(ve t)-.22 H .471 -.11
+(wo A).165 H .251(LL nodes on).11 F(successi)72 324 Q .784 -.165(ve p)
+-.275 H 3.204(lies. If).165 F .455(this happens, the second ALL node pr\
+obably means that the successor to this node is)3.204 F .306
+(really a CUT node and we are resetting the upper/lo)72 336 R .305
+(wer search bounds after searching a wrong \214rst mo)-.275 F -.165(ve)
+-.165 G(some)72 348 Q 3(where. The)-.275 F .25(\214nal o)3 F -.165(ve)
+-.165 G .251(rride phase will note the second ALL node, and then force \
+the successor of this).165 F .042
+(node to be type CUT since yet another ALL node can')72 360 R 2.792(tf)
+-.198 G(ollo)-2.792 E 2.792(wt)-.275 G .042(his one unless mo)-2.792 F
+.371 -.165(ve o)-.165 H .041(rdering is hopelessly).165 F 3.847
+(bad. This)72 372 R 1.097(phase of the o)3.847 F -.165(ve)-.165 G 1.097
+(rride code simply allo).165 F 1.097(ws only tw)-.275 F 3.847(oA)-.11 G
+1.097(LL nodes to be consecuti)-3.847 F 1.428 -.165(ve i)-.275 H 3.848
+(nt).165 G 1.098(he tree.)-3.848 F .218
+(After the second ALL node, the ne)72 384 R .218(xt node must be CUT)
+-.165 F 2.968(,t)-.814 G .218(he ne)-2.968 F .218(xt ALL, etc.)-.165 F
+-.165(Fo)5.718 G 2.968(ra).165 G .218(ll of these o)-2.968 F -.165(ve)
+-.165 G .218(rrides the).165 F 1.125(con\214dence is v)72 396 R 1.125
+(ery "lo)-.165 F 1.125(w" and, ag)-.275 F 1.125(ain, the number of mo)
+-.055 F -.165(ve)-.165 G 3.875(ss).165 G 1.126
+(earched at each ply is used to impro)-3.875 F 1.456 -.165(ve t)-.165 H
+(his).165 E(con\214dence.)72 408 Q .116(This has pro)72 432 R -.165(ve)
+-.165 G 2.866(nt).165 G 2.865(ob)-2.866 G 2.865(eac)-2.865 G .115
+(ritical step in the DTS algorithm.)-2.865 F 2.865(Am)5.615 G(istak)
+-2.865 E 2.865(eh)-.11 G .115(ere produces se)-2.865 F -.165(ve)-.275 G
+.115(re problems later).165 F .657(because the search space is going to\
+ increase due to searching branches that the sequential search w)72 444
+R(ould)-.11 E .154(be able to a)72 456 R -.22(vo)-.22 G 2.904(id. The)
+.22 F .154(initial estimate w)2.904 F .154(as quite good, b)-.11 F .154
+(ut the o)-.22 F -.165(ve)-.165 G .153(rride phase further impro).165 F
+-.165(ve)-.165 G 2.903(dt).165 G .153(he reliabil-)-2.903 F .729
+(ity of choosing a good node for a Split\(\) operation.)72 468 R .73
+(This has been modi\214ed more than an)6.23 F 3.48(yo)-.165 G .73
+(ther part of)-3.48 F .838(the DTS code, because Cray Blitz still \(on \
+occasion\) searches trees in parallel that are much lar)72 480 R .838
+(ger than)-.198 F .15(the same tree searched by only one processor)72
+492 R 5.65(.I)-.605 G 2.9(ft)-5.65 G .151
+(his were 100% accurate, then Cray Blitz w)-2.9 F .151(ould produce)-.11
+F(almost linear speedup as additional processors are added to the searc\
+h.)72 504 Q .599(Others ha)72 528 R .929 -.165(ve t)-.22 H .599
+(ackled this "where to split the tree" in dif).165 F .598(ferent w)-.275
+F .598(ays, and ha)-.11 F .928 -.165(ve p)-.22 H .598
+(roduced interesting results).165 F([Akl82,A)72 540 Q(werb)-1.012 E .569
+(uch85,Baudet78,Feldman90, Feldman93,and others].)-.22 F .57
+(Most all were designed for message-)6.07 F .683
+(passing systems, which made choosing split-points more comple)72 552 R
+3.433(xs)-.165 G .683(ince it becomes a serious issue when)-3.433 F 2.09
+(communication costs become a major design consideration.)72 564 R 2.091
+(It should be noted that the only serious)7.59 F .877
+(attempts to control tree search o)72 576 R -.165(ve)-.165 G .877
+(rhead all do so at the e).165 F .877(xpense of synchronization/w)-.165
+F .877(ait penalties.)-.11 F .876(In a)6.376 F EP
+%%Page: 14 14
+%%BeginPageSetup
+BP
+%%EndPageSetup
+/F0 11/Times-Roman@0 SF(distrib)72 96 Q .904(uted en)-.22 F .904
+(vironment, this mak)-.44 F .904
+(es a great deal of sense, since the cost of di)-.11 F .904
+(viding a tree into pieces is)-.275 F -.165(ve)72 108 S(ry high.).165 E
+(On the Cray architecture, the opposite is true.)5.5 E
+(3.3 Choosing a SPLIT ply)72 132 Q .547(The \214rst goal of the Split\(\
+\) procedure is to select an ALL node for splitting since this is the o\
+nly reason-)72 156 R .958(able type of node that w)72 168 R(on')-.11 E
+3.708(ta)-.198 G .958(dd an)-3.708 F 3.708(ys)-.165 G .958(earch o)
+-3.708 F -.165(ve)-.165 G .958(rhead \(e).165 F .958(xtra nodes.\))-.165
+F .958(Since the o)6.458 F -.165(ve)-.165 G .958(rhead for choosing a)
+.165 F .708(SPLIT point is costly)72 180 R 3.457(,am)-.715 G .707(ajor \
+consideration for selecting a split point is to choose a split point th\
+at will)-3.457 F(tak)72 192 Q 3.938(ear)-.11 G 1.188
+(easonable amount of time to search in parallel so Split\(\) w)-3.938 F
+(on')-.11 E 3.938(tb)-.198 G 3.939(ei)-3.938 G -2.09 -.44(nv o)-3.939 H
+-.11(ke).44 G 3.939(da).11 G -.055(ga)-3.939 G 3.939(in. As).055 F 3.939
+(ag)3.939 G(eneral)-3.939 E .512(rule, nodes at shallo)72 204 R 3.261
+(wd)-.275 G .511(epths represent more w)-3.261 F .511
+(ork than nodes at deep plies, making shallo)-.11 F 3.261(wn)-.275 G
+.511(odes desir)-3.261 F(-)-.22 E .486(able split points.)72 216 R .486
+(This can be complicated by at least tw)5.986 F 3.237(of)-.11 G .487
+(eatures of the nodes;)-3.237 F .487(\(1\) the con\214dence of an)5.987
+F .71(ALL node is lo)72 228 R 2.14 -.715(w, m)-.275 H .71(aking it risk)
+.715 F 3.46(yt)-.165 G 3.46(os)-3.46 G .709
+(earch it in parallel and possibly introduce e)-3.46 F .709
+(xtra nodes into the tree)-.165 F 1.169
+(search, and \(2\) the node has v)72 240 R 1.169(ery fe)-.165 F 3.919
+(wb)-.275 G 1.169(ranches remaining, so that it will only supply w)
+-3.919 F 1.17(ork for a small)-.11 F(number of processors which will fo\
+rce yet another Split\(\) when the remaining processors become idle.)72
+252 Q .461(As can be seen, this is a some)72 276 R .461(what subjecti)
+-.275 F .79 -.165(ve d)-.275 H .46
+(ecision, and tuning this code will continue for some time.).165 F .25
+(Other recent modi\214cations to this include questions lik)72 288 R 3
+(e")-.11 G .25(is the king in check at this node?" since this can)-3 F
+.26(result in a misleading "w)72 300 R .26(ork estimate.")-.11 F .26
+(Cray Blitz generates pseudo-le)5.76 F -.055(ga)-.165 G 3.009(lm).055 G
+-.165(ove)-3.009 G .259(s, and when the king is in).165 F .109
+(check, most of these mo)72 312 R -.165(ve)-.165 G 2.859(sa).165 G .109
+(re, in f)-2.859 F .11(act, ille)-.11 F -.055(ga)-.165 G 2.86(l. If).055
+F .11(these mo)2.86 F -.165(ve)-.165 G 2.86(sa).165 G .11
+(re used to estimate the w)-2.86 F .11(ork to be done at)-.11 F .171
+(this ply)72 324 R 2.921(,ap)-.715 G .17
+(oor SPLIT point will be chosen since man)-2.921 F 2.92(ym)-.165 G -.165
+(ove)-2.92 G 2.92(sa).165 G .17(re a)-2.92 F -.275(va)-.22 G .17
+(ilable, b).275 F .17(ut most will be immediately)-.22 F .332
+(recognized as ille)72 336 R -.055(ga)-.165 G 3.082(lw).055 G .332
+(ith almost no w)-3.082 F .332(ork required to determine this.)-.11 F
+(Se)5.833 E -.165(ve)-.275 G .333(ral such features can af).165 F .333
+(fect the)-.275 F 1.625("estimated w)72 348 R 1.625
+(orkload" of a potential split point to mak)-.11 F 4.375(ei)-.11 G 4.375
+(tl)-4.375 G 1.625(ess attracti)-4.375 F -.165(ve)-.275 G 7.125(.A).165
+G 1.625(nother e)-7.125 F 1.624(xample is that the)-.165 F .315
+(search e)72 360 R .316(xtensions used by Cray Blitz at ply=N are af)
+-.165 F .316(fected by the e)-.275 F .316
+(xtensions at plies before N in the tree.)-.165 F 1.713
+(The idea is that if something is causing e)72 372 R 1.712
+(xtensions at shallo)-.165 F 4.462(wp)-.275 G 1.712
+(lies, the search should be careful and)-4.462 F -.165(ex)72 384 S .523
+(tend at deeper plies too, to \214nd out what is going on.).165 F .524
+(Therefore, if there are man)6.024 F 3.274(ye)-.165 G .524
+(xtensions before a)-3.439 F .958
+(potential split-point, the subtrees belo)72 396 R 3.708(wt)-.275 G .957
+(hat possible split-point will lik)-3.708 F .957(ely be lar)-.11 F .957
+(ger than normal, a f)-.198 F(act)-.11 E
+(that should be considered when choosing from se)72 408 Q -.165(ve)-.275
+G(ral candidate nodes for a split-point.).165 E .309
+(Split\(\) is the single most important function in the DTS algorithm.)
+72 432 R .31(When it inadv)5.81 F .31(ertently chooses a CUT)-.165 F
+.831(node as a split-point, search o)72 444 R -.165(ve)-.165 G .831
+(rhead increases dramatically).165 F 6.33(.C)-.715 G .83
+(hoosing a PV node potentially increases)-6.33 F 1.145(the search o)72
+456 R -.165(ve)-.165 G 1.146(rhead until the \214rst branch is e).165 F
+1.146(xamined and Share\(\) correctly establishes the upper/lo)-.165 F
+(wer)-.275 E(search bounds.)72 468 Q 2.75(3.4 Splitting)72 492 R
+(at the root)2.75 E .832
+(Splitting the search at the root \(or not\) unco)72 516 R -.165(ve)
+-.165 G .832(rs some interesting problems.).165 F .832
+(First, most computer chess)6.332 F .186(programs use the so-called ite\
+rated search where a one ply search is done, then that information is u\
+sed to)72 528 R .137(order the mo)72 540 R -.165(ve)-.165 G 2.887(sf)
+.165 G .137(or a tw)-2.887 F 2.887(op)-.11 G .137(ly search, and the in\
+formation from that is used to order a three ply search and)-2.887 F
+(so forth.)72 552 Q
+(This process is continued until the time allotted for this mo)5.5 E .33
+-.165(ve r)-.165 H(uns out.).165 E 1.096(It should be ob)72 576 R 1.096
+(vious that the reason for doing a "depth+1" search is to \214nd a bett\
+er mo)-.165 F 1.427 -.165(ve t)-.165 H 1.097(han the one).165 F EP
+%%Page: 15 15
+%%BeginPageSetup
+BP
+%%EndPageSetup
+/F0 11/Times-Roman@0 SF .85(found from the "depth" search.)72 96 R .849
+(Often, the program does not change its mind from iteration to iteratio\
+n,)6.35 F .347
+(and, in such circumstances, splitting the tree at the root is an e)72
+108 R .347(xcellent idea.)-.165 F .347(After searching the \214rst root)
+5.847 F .314(branch completely)72 120 R 3.064(,s)-.715 G .314
+(earching the remainder in parallel introduces almost no o)-3.064 F
+-.165(ve)-.165 G .314(rhead \(some arises due to).165 F .768
+(transposition table interaction.\))72 132 R(Ho)6.269 E(we)-.275 E -.165
+(ve)-.275 G 1.649 -.44(r, w).165 H .769(hen the \214rst mo).44 F 1.099
+-.165(ve s)-.165 H .769(earched is not the best, and the program).165 F
+.705(ultimately chooses a dif)72 144 R .705(ferent root mo)-.275 F 1.035
+-.165(ve a)-.165 H 3.455(sb).165 G .705
+(est, searching root branches in parallel causes a problem in)-3.455 F
+(timed tournament chess g)72 156 Q(ames.)-.055 E .938(From prior analys\
+is [Knuth75,Hyatt88,Hyatt89,Hsu90] the \214rst branch from the root pro\
+duces a subtree)72 180 R .52(much lar)72 192 R .52(ger than the remaind\
+er of the branches \(when the \214rst branch is best.\))-.198 F .519
+(If the program then must)6.019 F .632
+("change its mind" and select a dif)72 204 R .632(ferent mo)-.275 F .962
+-.165(ve a)-.165 H 3.382(sb).165 G .632(est, this mo)-3.382 F .962 -.165
+(ve w)-.165 H .632(ill also produce a much lar).165 F .633(ger subtree)
+-.198 F(than the other mo)72 216 Q -.165(ve)-.165 G 2.75(s. This).165 F
+("much lar)2.75 E(ger subtree" causes an interesting problem in timed e)
+-.198 E -.165(ve)-.275 G(nts.).165 E .148(Consider a case where the sec\
+ond branch is really the one that the "depth+1" search will ultimately \
+select.)72 240 R .816(After searching the \214rst branch \(using parall\
+el processing\) one processor selects the second mo)72 252 R 1.146 -.165
+(ve i)-.165 H 3.566(nt).165 G(he)-3.566 E .346
+(list \(that is really the best mo)72 264 R -.165(ve)-.165 G 3.095(\)a)
+.165 G .345(nd starts searching the v)-3.095 F .345(ery lar)-.165 F .345
+(ge subtree it produces.)-.198 F .345(Other processors)5.845 F -.165(ex)
+72 276 S .009(amine other root branches that are unimportant.).165 F
+.009(If time runs out before the second branch is completely)5.509 F
+-.165(ex)72 288 S .389(amined, the \214rst mo).165 F .719 -.165(ve w)
+-.165 H .388(ill be chosen, resulting in the program making a w).165 F
+.388(orse mo)-.11 F .718 -.165(ve t)-.165 H .388(han it really has).165
+F 2.948(to. An)72 300 R(alternati)2.948 E .528 -.165(ve i)-.275 H 2.949
+(st).165 G 2.949(oh)-2.949 G -2.475 -.22(av e)-2.949 H .199
+(all processors w)3.169 F .199(ork on the \214rst mo)-.11 F -.165(ve)
+-.165 G 2.949(,t).165 G .199(hen all processors w)-2.949 F .199
+(ork on the second)-.11 F(mo)72 312 Q -.165(ve)-.165 G 3.6(,a).165 G .85
+(nd so forth.)-3.6 F .849(Then, when a ne)6.349 F 3.599(wb)-.275 G .849
+(est mo)-3.599 F 1.179 -.165(ve i)-.165 H 3.599(ss).165 G .849
+(earched, all processors search it and complete the)-3.599 F
+(search before time runs out.)72 324 Q .883(Some might be quick to sugg\
+est that "the search should notice that the un\214nished mo)72 348 R
+1.214 -.165(ve h)-.165 H .884(as produced a).165 F(lar)72 360 Q .429
+(ge tree, and is lik)-.198 F .429(ely about to become a ne)-.11 F 3.179
+(wb)-.275 G .429(est, so don')-3.179 F 3.179(tg)-.198 G -2.365 -.275
+(iv e)-3.179 H .428(up until it has been completed.")3.454 F(Ho)5.928 E
+(w-)-.275 E -2.365 -.275(ev e)72 372 T 1.181 -.44(r, t).275 H .301
+(here are tw).44 F 3.052(oi)-.11 G .302(ssues with this:)-3.052 F .302
+(\(1\) just because a root mo)5.802 F .632 -.165(ve p)-.165 H .302
+(roduces a tree se).165 F -.165(ve)-.275 G .302(ral orders of magni-)
+.165 F .811(tude lar)72 384 R .811(ger than an)-.198 F 3.561(yo)-.165 G
+.811(ther \(than the \214rst\) root mo)-3.561 F 1.141 -.165(ve d)-.165 H
+.811(oes not imply that this mo).165 F 1.141 -.165(ve i)-.165 H 3.561
+(sb).165 G(etter)-3.561 E 6.311(.I)-.605 G 3.561(tm)-6.311 G .81
+(ight be)-3.561 F(better)72 396 Q 4.048(,o)-.44 G 4.048(ri)-4.048 G
+4.048(tm)-4.048 G 1.298(ight simply be a complicated mo)-4.048 F 1.628
+-.165(ve t)-.165 H 1.299
+(hat leads to positions which stimulate lots of search).165 F -.165(ex)
+72 408 S .148(tensions and mak).165 F 2.898(et)-.11 G .148
+(he tree quite lar)-2.898 F 2.898(ge. Therefore,)-.198 F .148
+(it is not safe to simply say the tree so f)2.898 F .148(ar is big, w)
+-.11 F(ait,)-.11 E .884(because that might tak)72 420 R 3.634(eas)-.11 G
+.884(igni\214cant amount of time to \214nish.)-3.634 F .885
+(And note the major problem here is that)6.385 F .068
+(only one processor is searching that branch should we choose to w)72
+432 R .067(ait for a result.)-.11 F .067(\(2\) "Just w)5.567 F .067
+(aiting" is not)-.11 F 3.879(ap)72 444 S 1.129
+(articularly good plan in a timed e)-3.879 F -.165(ve)-.275 G 3.879
+(nt. Since).165 F 1.129(time is a f)3.879 F(actor)-.11 E 3.879(,u)-.44 G
+1.129(sing it wisely is a major part of an)-3.879 F(y)-.165 E 1.055
+(chess program, and ha)72 456 R 1.055(ving to b)-.22 F 1.054(urn man)
+-.22 F 3.804(ym)-.165 G 1.054(inutes just because the search can')-3.804
+F 3.804(tr)-.198 G(esolv)-3.804 E 3.804(ew)-.165 G 1.054(hether a mo)
+-3.804 F -.165(ve)-.165 G(further do)72 468 Q(wn the ply=1 mo)-.275 E
+.33 -.165(ve l)-.165 H(ist is better or not can lead to timing dif).165
+E(\214culties.)-.275 E .252(The dra)72 492 R .252
+(wback to solving this is that we "kno)-.165 F .252
+(w" that all branches at the root should be searched \(time per)-.275 F
+(-)-.22 E 1.002(mitting\) and that searching them will cause no e)72 504
+R 1.002(xtra o)-.165 F -.165(ve)-.165 G 1.002
+(rhead \(after the \214rst branch establishes a lo).165 F(wer)-.275 E
+.621(search bound, assuming that the \214rst mo)72 516 R .951 -.165
+(ve i)-.165 H 3.371(sa).165 G .621(ctually the best mo)-3.371 F -.165
+(ve)-.165 G 6.121(.T).165 G .621(his is true for a lar)-6.121 F .621
+(ge majority of)-.198 F 1.614(positions, \).)72 528 R 1.614
+(The root is therefore a highly f)7.114 F -.22(avo)-.11 G 1.613
+(rable \(from a search o).22 F -.165(ve)-.165 G 1.613
+(rhead point of vie).165 F 1.613(w\) place to)-.275 F 1.085
+(search in parallel.)72 540 R 1.085(If the entire ply=1 mo)6.585 F 1.415
+-.165(ve l)-.165 H 1.085(ist w).165 F 1.086
+(as searched, then splitting at ply=1 w)-.11 F 1.086(ould w)-.11 F 1.086
+(ork well.)-.11 F(Ho)72 552 Q(we)-.275 E -.165(ve)-.275 G 1.257 -.44
+(r, s).165 H .377(ince time can run out and stop the search, e).44 F
+.377(xamining the \214rst fe)-.165 F 3.126(wm)-.275 G -.165(ove)-3.126 G
+3.126(so).165 G 3.126(nt)-3.126 G .376(he list \(searching)-3.126 F .942
+(each in succession with all processors w)72 564 R .942
+(orking together on each mo)-.11 F -.165(ve)-.165 G 3.692(\)e).165 G
+.942(nsures that the \214rst fe)-3.692 F 3.693(wm)-.275 G -.165(ove)
+-3.693 G(s).165 E 1.19(are COMPLETEL)72 576 R 3.94(Ye)-1.1 G 1.19
+(xamined before time runs out. \(Note: in Cray Blitz and Crafty)-4.105 F
+3.939(,a)-.715 G 3.939(ni)-3.939 G 1.189(teration is not)-3.939 F EP
+%%Page: 16 16
+%%BeginPageSetup
+BP
+%%EndPageSetup
+/F0 11/Times-Roman@0 SF .398(completed after time has run out.)72 96 R
+(Rather)5.898 E 3.148(,t)-.44 G .398(he search stops, the mo)-3.148 F
+.728 -.165(ve i)-.165 H 3.148(sm).165 G .398
+(ade, and then the ponder search)-3.148 F .731
+(picks up and continues searching.\))72 108 R 2.491 -.88(We c)6.231 H
+.731(hose to accept this inef).88 F(\214cienc)-.275 E 3.481(y\()-.165 G
+.73(searching e)-3.481 F .73(xtra nodes\) in order)-.165 F(to let the p\
+rogram change its mind on the last iteration, if the \214rst mo)72 120 Q
+.33 -.165(ve i)-.165 H 2.75(sn).165 G(ot best.)-2.75 E .063
+(This often leads to a li)72 144 R -.165(ve)-.275 G .064(ly debate abou\
+t \(a\) whether or not a parallel search should split at the root and \
+\(b\)).165 F .591
+(whether or not the program should completely search the root mo)72 156
+R .921 -.165(ve l)-.165 H .591(ist before stopping for a time limit.)
+.165 F 1.76 -.88(We h)72 168 T -2.475 -.22(av e).88 H -.165(ex)2.97 G
+(perimented with possible alternati).165 E .33 -.165(ve a)-.275 H
+(lgorithms, b).165 E(ut none ha)-.22 E .33 -.165(ve p)-.22 H(ro).165 E
+-.165(ve)-.165 G 2.75(nb).165 G(etter to date.)-2.75 E 2.75(4. DTS)72
+192 R(performance results)2.75 E .117(The DTS algorithm w)72 216 R .117
+(as tested using a Cray C916/1024 computer)-.11 F 5.617(.T)-.605 G .117
+(his machine has 16 processors with a)-5.617 F -.165(cy)72 228 S
+(cle time of 4.166 nanoseconds, and also has 1024 million w).165 E
+(ords of memory \(eight gig)-.11 E(abytes.\))-.055 E(4.1 T)72 252 Q
+(esting methodology)-.77 E .829(In producing these results, all testing\
+ used the machine in a dedicated mode so that all of the machine')72 276
+R(s)-.605 E .241(memory w)72 288 R .241(as used, re)-.11 F -.055(ga)
+-.165 G .242
+(rdless of the number of processors utilized in each test \(e).055 F
+.242(xcept for the one-proces-)-.165 F 1.227(sor test, which is e)72 300
+R 1.227(xplained later\).)-.165 F 1.227
+(Often, particularly when using distrib)6.727 F 1.227(uted machines lik)
+-.22 F 3.976(et)-.11 G 1.226(he Hyper)-3.976 F(-)-.22 E 4.252(cubes, ad\
+ding additional processors also adds additional memory [Feldmann90,Feld\
+mann93,K)72 312 R(usz-)-.165 E(maul94,Schaef)72 324 Q(fer89,Y)-.275 E
+1.535(ang93], ef)-1.1 F(fecti)-.275 E -.165(ve)-.275 G 1.535
+(ly changing tw).165 F 4.285(os)-.11 G 1.534
+(earch parameters at the same time \(number of)-4.285 F .166
+(processors or total computation po)72 336 R .166
+(wer and total memory a)-.275 F -.275(va)-.22 G 2.916(ilable.\) It).275
+F .166(is then dif)2.916 F .166(\214cult to attrib)-.275 F .166
+(ute the per)-.22 F(-)-.22 E .379(formance impro)72 348 R -.165(ve)-.165
+G .379(ment to additional processor po).165 F .378
+(wer alone as the transposition table is e)-.275 F .378(xtremely impor)
+-.165 F(-)-.22 E(tant to search performance and making it lar)72 360 Q
+(ger often dramatically speeds up search times.)-.198 E .434
+(The testing done to produce the results gi)72 384 R -.165(ve)-.275 G
+3.184(nh).165 G .434(erein dif)-3.184 F .434
+(fers from the testing used in pre)-.275 F .434(vious parallel tree)
+-.275 F .378(search algorithms [Hyatt88, Hyatt89, Schaef)72 396 R .378
+(fer89, Feldmann90,others].)-.275 F .378
+(Rather than use a group of unre-)5.878 F 1.856
+(lated chess problems, we elected to tak)72 408 R 4.606(eas)-.11 G -.165
+(eg)-4.606 G 1.856(ment of a real chess g).165 F 1.856(ame and ha)-.055
+F 2.187 -.165(ve t)-.22 H 1.857(he program play).165 F .175
+(through it with v)72 420 R .175(arying numbers of processors.)-.275 F
+.175(There are tw)5.675 F 2.925(or)-.11 G .175
+(easons for choosing this approach: \(1\) this)-2.925 F .124
+(is what a chess program is designed to do, "play a complete g)72 432 R
+.124(ame", not "search random positions" and \(2\))-.055 F 1.346
+(it is well-kno)72 444 R 1.345(wn that parallel algorithms perform bett\
+er when searching deeper trees [Hyatt88,Hyatt89,)-.275 F(Schaef)72 456 Q
+4.903(fer89,others]. When)-.275 F 2.153(searching unrelated problems, t\
+here is no "continuity" between problems.)4.903 F .974
+(When searching a series of mo)72 468 R -.165(ve)-.165 G 3.724(sf).165 G
+.974(rom the same g)-3.724 F .974
+(ame, the transposition table, the killer mo)-.055 F 1.304 -.165(ve l)
+-.165 H .974(ist, the).165 F .105
+(dynamic scoring parameters, all "tie things together" and allo)72 480 R
+2.855(wd)-.275 G .105(eeper searches.)-2.855 F .105
+(Note also, that if you are)5.605 F
+(iterested in results on a traditional test lik)72 492 Q 2.75(et)-.11 G
+(he K)-2.75 E(opek/Bratk)-.385 E 2.75(op)-.11 G(ositions, the)-2.75 E
+2.75(ya)-.165 G(re a)-2.75 E -.275(va)-.22 G(ilable in [Hyatt88].).275 E
+1.564(The testing methodology w)72 516 R 1.564(as to tak)-.11 F 4.314
+(et)-.11 G 1.564(he 16-processor log produced during the actual g)-4.314
+F 1.563(ame, and then)-.055 F("contri)72 528 Q -.165(ve)-.275 G 4.302
+("t).165 G 1.552(hings so that the "lesser" con\214gurations w)-4.302 F
+1.552(ould do the same amount of w)-.11 F 1.552(ork \(roughly\).)-.11 F
+(In)7.053 E 1.257(these tests, if the 16 processor search reached 11 pl\
+ies and searched the \214rst 10 root mo)72 540 R -.165(ve)-.165 G 4.007
+(sb).165 G 1.257(efore the)-4.007 F .21
+(search timed out, then all lessor con\214gurations had to also do e)72
+552 R .21(xactly this same search, which led to some)-.165 F .406
+(embarrassingly long search times for one processor as will be seen.)72
+564 R .405(One other minor note is that the sin-)5.905 F 1.222
+(gle processor times appear to search slightly slo)72 576 R 1.222
+(wer than the equi)-.275 F -.275(va)-.275 G 1.222
+(lent parallel searches, which w).275 F(ould)-.11 E EP
+%%Page: 17 17
+%%BeginPageSetup
+BP
+%%EndPageSetup
+/F0 11/Times-Roman@0 SF .019(seem to be counter)72 96 R(-intuiti)-.22 E
+-.165(ve)-.275 G 5.518(.H).165 G -.275(ow)-5.518 G -2.365 -.275(ev e)
+.275 H .898 -.44(r, d).275 H .018
+(ue to the enormous time required to play through this g).44 F .018
+(ame with-)-.055 F .33(out stopping \(which w)72 108 R .331(ould ha)-.11
+F .661 -.165(ve c)-.22 H .331(leared the transposition table and so for\
+th\) we ran this test on a produc-).165 F .263
+(tion machine, and competed with other processes.)72 120 R .263
+(As a result, memory con\215icts were much higher \(bank)5.763 F 1.866
+(con\215icts to those that are Cray-sa)72 132 R 1.866
+(vvy\) as well as sw)-.22 F 1.866(apping o)-.11 F -.165(ve)-.165 G 1.866
+(rhead which gets char).165 F 1.867(ged to the user)-.198 F(.)-.605 E
+(While this is well belo)72 144 Q 2.75(wt)-.275 G(he .1% le)-2.75 E
+-.165(ve)-.275 G 2.75(lo).165 G 2.75(fn)-2.75 G
+(oise, it is noticeable, and should be remembered.)-2.75 E .978
+(The test positions came from the g)72 168 R .977
+(ame Mchess Pro vs Cray Blitz at the 1993 A)-.055 F .977
+(CM International Com-)-.44 F .112(puter Chess Championship.)72 180 R
+.112(\(This g)5.612 F .112(ame is included as Appendix A.\))-.055 F .113
+(This g)5.613 F .113(ame w)-.055 F .113(as chosen after looking)-.11 F
+.84(at analysis produced by Cray Blitz during the tournament.)72 192 R
+.839(The opening w)6.339 F .839(as a King')-.11 F 3.589(sG)-.605 G .839
+(ambit Accepted)-3.589 F .428
+(where white sacri\214ced a piece for some pa)72 204 R .429
+(wns and a strong attack.)-.165 F .429(C-B sa)5.929 F 3.179(wt)-.165 G
+.429(he e)-3.179 F -.275(va)-.275 G .429(luation steadily drop).275 F
+.553(as it disco)72 216 R -.165(ve)-.165 G .553(red just ho).165 F 3.303
+(ws)-.275 G .553(trong the attack w)-3.303 F .553(as, then it le)-.11 F
+-.165(ve)-.275 G .553(led of).165 F 3.303(fa)-.275 G .552(nd follo)
+-3.303 F .552(wed a "tight-rope" for se)-.275 F -.165(ve)-.275 G(ral)
+.165 E(mo)72 228 Q -.165(ve)-.165 G 1.286
+(s, making the only possible mo).165 F 1.616 -.165(ve t)-.165 H 1.287
+(hat w).165 F 1.287(ould not lose, then it started f)-.11 F 1.287
+(ailing high repeatedly as it)-.11 F(\214nally survi)72 240 Q -.165(ve)
+-.275 G 2.75(dt).165 G(he attack and started a counter)-2.75 E
+(-attack that ultimately w)-.22 E(on the g)-.11 E(ame.)-.055 E .275
+(The \214rst position occurs after the sequence of mo)72 264 R -.165(ve)
+-.165 G 3.024(s1).165 G 3.024(.e)-3.024 G 3.024(4e)-3.024 G 3.024(52)
+-3.024 G 3.024(.N)-3.024 G .274(c3 Nc6 3. f4 e)-3.024 F .274
+(xf4 4. Nf3 g5 5. d4 g4 6.)-.165 F .557(Bc4 gxf3 7. o-o d5)72 276 R .557
+(8. e)6.057 F .557(xd5 Bg4 9. Qd2 ...)-.165 F .558(At this point, C-B w)
+6.058 F .558(as "out of book" and quickly disco)-.11 F -.165(ve)-.165 G
+(red).165 E .021(that its king w)72 288 R .021(as e)-.11 F .021
+(xposed in the center although it w)-.165 F .021
+(as a piece up and a couple of pa)-.11 F .02(wns do)-.165 F 2.77
+(wn. The)-.275 F -.275(eva)2.77 G(lu-).275 E .972
+(ation steadily dropped for the ne)72 300 R .973(xt fe)-.165 F 3.723(wm)
+-.275 G -.165(ove)-3.723 G 3.723(sa).165 G 3.723(sC)-3.723 G .973
+(-B "sa)-3.723 F .973(w" ho)-.165 F 3.723(we)-.275 G .973
+(xposed its king w)-3.888 F 3.723(as. The)-.11 F -.275(eva)3.723 G
+(luation).275 E .598(dropped to a point where C-B w)72 312 R .598
+(as about 1/4 pa)-.11 F .597(wn "do)-.165 F .597(wn" at the lo)-.275 F
+3.347(wp)-.275 G .597(oint in the g)-3.347 F 3.347(ame. It)-.055 F .597
+(then be)3.347 F -.055(ga)-.165 G 3.347(na).055 G 1.491
+(climb to roughly 1/3 of a pa)72 324 R 1.491(wn "ahead" before disco)
+-.165 F -.165(ve)-.165 G 1.492
+(ring that Mchess could force a perpetual dra).165 F -.715(w.)-.165 G
+.248(\(This occurred at position 17 where C-B took a long time trying t\
+o \214nd an)72 336 R 2.997(yw)-.165 G .247(ay out of the v)-3.107 F .247
+(ery deep per)-.165 F(-)-.22 E .274(petual check.)72 348 R .274
+(The perpetual w)5.774 F .274(as some 19 plies deep.\))-.11 F -.165(Fo)
+5.774 G 3.024(rt).165 G .274(he ne)-3.024 F .274(xt tw)-.165 F 3.024(om)
+-.11 G -.165(ove)-3.024 G .274(s, it w).165 F .274(as resigned to a dra)
+-.11 F -.715(w,)-.165 G -.22(bu)72 360 S 4.917(tM).22 G 2.167(chess app\
+arently did not search deeply enough to detect the repetition and v)
+-4.917 F 2.166(aried, gi)-.275 F 2.166(ving C-B)-.275 F(another chance.)
+72 372 Q(From this point on the e)5.5 E -.275(va)-.275 G
+(luation climbed steadily).275 E(.)-.715 E .256
+(This particular series of positions of)72 396 R .256
+(fered both "good," "bad" and "normal" positions that C-B searched in)
+-.275 F(parallel.)72 408 Q 2.784(A")72 432 S .033
+(good" position is one where the program \214nds the correct mo)-2.784 F
+.363 -.165(ve a)-.165 H 2.783(tas).165 G(hallo)-2.783 E 2.783(ws)-.275 G
+.033(earch and "sticks with it")-2.783 F .327
+(through later searches and ultimately mak)72 444 R .328(es that mo)-.11
+F -.165(ve)-.165 G 5.828(.T).165 G .328
+(his means that ordering at the root of the tree is)-5.828 F .531
+(perfect, and often means that ordering f)72 456 R .531(arther do)-.11 F
+.531(wn in the tree is also quite good, making the search rea-)-.275 F
+1.069(sonably ef)72 468 R 3.82(\214cient. These)-.275 F 1.07
+(positions produce good speedups re)3.82 F -.055(ga)-.165 G 1.07
+(rdless of the number of processors used.).055 F
+(Positions 20 and 21 are e)72 480 Q(xamples of such positions.)-.165 E
+3.761(A")72 504 S 1.01(normal" position is one where the program occasi\
+onally changes its mind at the root, b)-3.761 F 1.01(ut that mo)-.22 F
+-.165(ve)-.165 G .143(ordering is still good.)72 516 R .144
+(This lets C-B \214nd the ne)5.643 F 2.894(wb)-.275 G .144(est mo)-2.894
+F .474 -.165(ve a)-.165 H 2.894(tt).165 G .144(he root f)-2.894 F .144
+(aster than it w)-.11 F .144(ould if it could split)-.11 F(the w)72 528
+Q(ork at the root \(pre)-.11 E(vious discussion.\))-.275 E 3.443(A")72
+552 S .692(bad" position is one where e)-3.443 F -.165(ve)-.275 G .692
+(ry iteration un).165 F -.165(ve)-.44 G .692(ils some ne).165 F 3.442
+(wt)-.275 G .692(hreat that the program must then \214nd a)-3.442 F -.11
+(wa)72 564 S 3.25(yt).11 G 3.25(od)-3.25 G .5(efend ag)-3.25 F 3.25
+(ainst. At)-.055 F .5(the be)3.25 F .5(ginning of each ne)-.165 F 3.251
+(wi)-.275 G .501(teration, the best mo)-3.251 F .831 -.165(ve f)-.165 H
+.501(rom the pre).165 F .501(vious iteration)-.275 F .707(often f)72 576
+R .707(ails lo)-.11 F 2.137 -.715(w, a)-.275 H .707
+(nd with little help in ordering mo).715 F -.165(ve)-.165 G .707
+(s, the parallel v).165 F .706(ersion of the search be)-.165 F .706
+(gins to search)-.165 F EP
+%%Page: 18 18
+%%BeginPageSetup
+BP
+%%EndPageSetup
+/F0 11/Times-Roman@0 SF .389
+(signi\214cantly more nodes than the sequential v)72 96 R 3.14
+(ersion. These)-.165 F .39(positions typically ha)3.14 F .72 -.165(ve p)
+-.22 H .39(oor speedup results).165 F .07
+(when compared with a sequential search.)72 108 R .07(An e)5.57 F .07
+(xcellent e)-.165 F .069(xample of this is position 17.)-.165 F .069
+(This is the position)5.569 F 1.575(where C-B disco)72 120 R -.165(ve)
+-.165 G 1.575(rs that it can').165 F 4.325(ta)-.198 G -.22(vo)-4.545 G
+1.575(id a dra).22 F 4.325(wb)-.165 G 4.325(yr)-4.325 G 1.575
+(epetition \(with best play by the opponent.\))-4.325 F(Mo)7.076 E -.165
+(ve)-.165 G .923(ordering is poor since prior kno)72 132 R .923
+(wledge of good mo)-.275 F -.165(ve)-.165 G 3.673(si).165 G 3.673(sq)
+-3.673 G .923(uickly refuted by the dra)-3.673 F .923
+(wing lines found by)-.165 F(the constantly increasing search depth.)72
+144 Q .276(The results include tw)72 168 R 3.026(os)-.11 G .276
+(ets of numbers for each test, where a test used either one, tw)-3.026 F
+.277(o, four)-.11 F 3.027(,e)-.44 G .277(ight or six-)-3.027 F .133
+(teen processors.)72 180 R .133
+(The numbers are the clock time required for the search \(w)5.633 F .133
+(all clock time\) and the number)-.11 F(of nodes searched \(which sho)72
+192 Q(ws ho)-.275 E 2.75(wm)-.275 G(uch e)-2.75 E(xtra w)-.165 E
+(ork is added by using additional processors.)-.11 E .256
+(These results are summarized belo)72 216 R 3.006(wi)-.275 G 3.006(nt)
+-3.006 G .256(able 3, which can be compared to the results for the tw)
+-3.006 F 3.007(op)-.11 G(re)-3.007 E(vious)-.275 E(algorithms.)72 228 Q
+.44 LW 417.215 248.95 194.784 248.95 DL 2.75(#p)200.284 258.2 S 17.875
+(rocessors 1)-2.75 F 24.75(2481)24.75 G(6)-24.75 E 417.215 262.95
+194.784 262.95 DL 32.384(speedup 1.0)200.284 272.2 R 13.75
+(2.0 3.7 6.6 11.1)16.5 F 417.215 276.95 194.784 276.95 DL 384.215 262.95
+384.215 276.95 DL 353.965 262.95 353.965 276.95 DL 323.715 262.95
+323.715 276.95 DL 293.465 262.95 293.465 276.95 DL 263.215 262.95
+263.215 276.95 DL 417.215 248.95 417.215 276.95 DL 194.784 248.95
+194.784 276.95 DL 384.215 248.95 384.215 276.95 DL 353.965 248.95
+353.965 276.95 DL 323.715 248.95 323.715 276.95 DL 293.465 248.95
+293.465 276.95 DL 263.215 248.95 263.215 276.95 DL -.88(Ta)233.125 300.4
+S(ble 3 DTS performance results).88 E 2.75(5. Performance)72 324.4 R
+(analysis)2.75 E .292(The performance results for DTS are presented in \
+table 4 \(search time for each test position in the g)72 348.4 R(ame\),)
+-.055 E 1.243(table 5 \(nodes searched for each test position\) and tab\
+le 6 \(the performance impro)72 360.4 R -.165(ve)-.165 G 1.244
+(ment for each test).165 F(position\).)72 372.4 Q 1.37(The simplest w)72
+396.4 R 1.37(ay to analyze the performance is to e)-.11 F 1.369
+(xamine T)-.165 F 1.369(able 3 which gi)-.88 F -.165(ve)-.275 G 4.119
+(st).165 G 1.369(he speedup for each)-4.119 F 4.238(position. This)72
+408.4 R 1.488(table presents the a)4.238 F -.165(ve)-.22 G 1.489
+(rage speedup for tw).165 F 1.489(o, four)-.11 F 4.239(,e)-.44 G 1.489
+(ight and sixteen processors, and is a)-4.239 F .379
+(summary of the timing results from table 6, gi)72 420.4 R .378
+(ving each position a weight of one and di)-.275 F .378
+(viding the sum of)-.275 F .505(the column by 24.)72 432.4 R .506
+(It is interesting to note that there is an in)6.005 F -.165(ve)-.44 G
+.506(rse relationship between speedup and total).165 F 1.163
+(nodes searched, which is e)72 444.4 R 1.162(xactly as e)-.165 F 1.162
+(xpected with DTS.)-.165 F 1.162(Recall that DTS does not allo)6.662 F
+3.912(wp)-.275 G 1.162(rocessors to)-3.912 F .328(remain idle for an)72
+456.4 R 3.078(ys)-.165 G .328(igni\214cant amount of time, so that poor\
+ speedup results has to be the result of search-)-3.078 F
+(ing nodes that are unnecessary)72 468.4 Q 2.75(,e)-.715 G
+(xactly as the ra)-2.915 E 2.75(wd)-.165 G(ata gi)-2.75 E -.165(ve)-.275
+G 2.75(ns).165 G(ho)-2.75 E(ws.)-.275 E -.165(Fo)72 492.4 S 3.441(rt)
+.165 G .691
+(he older Cray XMP machines with a maximum of four processors, an a)
+-3.441 F -.165(ve)-.22 G .69(rage speedup of tw).165 F 3.44(o\()-.11 G
+(tw)-3.44 E(o)-.11 E .194
+(processors\) and 3.7 \(four processors\) looks e)72 504.4 R .194
+(xtremely ef)-.165 F 2.944(\214cient. Mo)-.275 F .195
+(ving up to an eight processor machine)-.165 F 1.013
+(\(the old YMP line is an e)72 516.4 R 1.013
+(xample\) produces a speedup of 6.6 which, ag)-.165 F 1.013
+(ain, is a reasonable result.)-.055 F(Here)6.512 E .334(doubling the nu\
+mber of processors from four to eight produces a performance impro)72
+528.4 R -.165(ve)-.165 G .334(ment f).165 F .334(actor of 1.8.)-.11 F
+(Ho)72 540.4 Q(we)-.275 E -.165(ve)-.275 G 2.493 -.44(r, p).165 H 1.613
+(ushing this further be).44 F 1.613(gins to sho)-.165 F 4.363(wj)-.275 G
+1.613(ust ho)-4.363 F 4.363(wd)-.275 G(if)-4.363 E 1.612
+(\214cult parallelizing an alpha/beta tree search)-.275 F 1.164
+(really is.)72 552.4 R 1.164
+(The speedup of 11.1 for 16 processors means that o)6.664 F -.165(ve)
+-.165 G 3.915(ro).165 G 1.165(ne quarter of the C90')-3.915 F 3.915(sc)
+-.605 G 1.165(ycles were)-4.08 F -.11(wa)72 564.4 S 2.903(sted. F).11 F
+.153(or these tests, processor idle time a)-.165 F -.165(ve)-.22 G .153
+(raged under tw).165 F 2.903(os)-.11 G .153
+(econds for each position \(per processor\),)-2.903 F EP
+%%Page: 19 19
+%%BeginPageSetup
+BP
+%%EndPageSetup
+/F0 11/Times-Roman@0 SF(sho)72 96 Q .549
+(wing that the parallel search e)-.275 F .55(xamined a signi\214cant nu\
+mber of nodes that the sequential search didn')-.165 F(t)-.198 E(\(e)72
+108 Q 1.019(xamine T)-.165 F 1.018
+(able 2 and compare the 1cpu node counts column to an)-.88 F 3.768(yo)
+-.165 G 3.768(ft)-3.768 G 1.018(he others.)-3.768 F -.165(Fo)6.518 G
+3.768(rp).165 G 1.018(osition 17 it is)-3.768 F(ob)72 120 Q 1.22
+(vious that the program searched almost three times as man)-.165 F 3.97
+(yn)-.165 G 1.22(odes with 16 processors as it did with)-3.97 F .087
+(one, so that, e)72 132 R -.165(ve)-.275 G 2.837(nt).165 G .086
+(hough the entire machine \(16 processors\) w)-2.837 F .086(as b)-.11 F
+(usy)-.22 E 2.836(,t)-.715 G .086(he majority of the processors were)
+-2.836 F(doing unnecessary w)72 144 Q(ork.)-.11 E .297(Cray Blitz count\
+s the number of split operations that it attempts, as part of its b)72
+168 R .297(uilt-in performance analy-)-.22 F 3.562(sis. This)72 180 R
+.812(count is af)3.562 F .811(fected by tw)-.275 F 3.561(op)-.11 G 3.561
+(arameters; \(1\))-3.561 F .811(the e)3.561 F .811
+(xtra nodes searched by the program, and \(2\) the)-.165 F 1.872
+(total search time.)72 192 R 1.873(In ef)7.373 F 1.873
+(fect, the number of splits per unit of time \(in)-.275 F -.165(ve)-.44
+G 1.873(rsely\) follo).165 F 1.873(ws the e)-.275 F 1.873(xtra nodes)
+-.165 F .218(searched by the program.)72 204 R -.165(Fo)5.718 G 2.968
+(rt).165 G .218(hese test positions, the SPLIT count ranged from a lo)
+-2.968 F 2.968(wo)-.275 G 2.968(f3)-2.968 G .218(07 to a high of)-2.968
+F -.165(ove)72 216 S 3.225(r1).165 G 3.225(20,000! As)-3.225 F 3.225(ar)
+3.225 G .476(esult, this data has not been presented since the speedup \
+table and time tables accu-)-3.225 F 1.63
+(rately predict the split counts obtained from the tests.)72 228 R 1.629
+(The best speedup \(and the fe)7.13 F 1.629(west e)-.275 F 1.629
+(xtra nodes\))-.165 F .716(occurs on positions where fe)72 240 R 3.467
+(ws)-.275 G .717(plit operations are attempted.)-3.467 F 2.477 -.88
+(To a)6.217 H -.22(vo).66 G .717(id a situation of "information o).22 F
+-.165(ve)-.165 G -.22(r-).165 G<8d6f>72 252 Q .095
+(w" additional statistics g)-.275 F .095(athered by C-B ha)-.055 F .425
+-.165(ve b)-.22 H .094(een omitted since statistical analysis sho).165 F
+.094(ws strong corre-)-.275 F .407(lation among all of the metrics.)72
+264 R .408(One e)5.908 F .408
+(xample is that C-B counts the number of times a processor starts a)
+-.165 F .648(parallel task only to be stopped by another because mo)72
+276 R .978 -.165(ve o)-.165 H .648(rdering w).165 F .648
+(as not optimal.)-.11 F .648(These "early stops")6.148 F
+(correspond with the "split operations attempted" and with the "e)72 288
+Q(xtra nodes" quite well.)-.165 E 1.25(The most immediate problem in th\
+e current algorithm is that the parallel search e)72 312 R 1.25
+(xamines a signi\214cant)-.165 F .413(number of e)72 324 R .413
+(xtra nodes that the sequential algorithm does not.)-.165 F .413(Much w)
+5.913 F .412(ork remains to determine just ho)-.11 F(w)-.275 E -.11(fa)
+72 336 S 2.773(rt).11 G .024(his can be reduced.)-2.773 F(Intuiti)5.524
+E -.165(ve)-.275 G(ly).165 E 2.774(,i)-.715 G 2.774(ti)-2.774 G 2.774
+(sn)-2.774 G .024(ot possible to reduce the number of e)-2.774 F .024
+(xtra nodes to zero since this)-.165 F -.11(wo)72 348 S 1.702
+(uld require nearly perfect mo).11 F 2.032 -.165(ve o)-.165 H 4.452
+(rdering. The).165 F(rele)4.452 E -.275(va)-.275 G 1.702
+(nt question is whether or not it is possible to).275 F .418
+(choose a split point more accurately than the present algorithm does.)
+72 360 R .419(If some information were a)5.919 F -.275(va)-.22 G(ilable)
+.275 E .446(that might be used to predict ho)72 372 R 3.196(wg)-.275 G
+.446(ood mo)-3.196 F .776 -.165(ve o)-.165 H .446
+(rdering is at a particular node, better split points might be).165 F
+(chosen.)72 384 Q -.165(Fo)72 408 S 3.053(rc).165 G .303
+(urrent machines with sixteen processors \(and e)-3.053 F -.165(ve)-.275
+G 3.053(nf).165 G .303(or future potential supercomputers with up to 64)
+-3.053 F .279(processors\) the processor idle time in the current algor\
+ithm does not pose a signi\214cant problem.)72 420 R .278(The cur)5.778
+F(-)-.22 E 1.43(rent idle times of tw)72 432 R 4.181(ot)-.11 G 4.181(ot)
+-4.181 G 1.431(hree seconds o)-4.181 F -.165(ve)-.165 G 4.181(ram).165 G
+1.761 -.165(ove t)-4.181 H 1.431(hat tak).165 F 1.431
+(es 200 to 500 seconds does not af)-.11 F 1.431(fect the)-.275 F .475(s\
+earch times signi\214cantly for small numbers of processors \(2-16\), b)
+72 444 R .475(ut for really lar)-.22 F .474(ge numbers of proces-)-.198
+F(sors, something must be done to a)72 456 Q -.22(vo)-.22 G
+(id running into Amdahl').22 E 2.75(sL)-.605 G -.165(aw)-2.75 G(.)-.55 E
+.143(This result compares f)72 480 R -.22(avo)-.11 G .143
+(rably with the DPVS \(Dynamic PVS\) algorithm de).22 F -.165(ve)-.275 G
+.144(loped for Phoenix \(Schaef-).165 F 3.365(fer89]. The)72 492 R -.165
+(ove)3.365 G .615(rall algorithms seem quite similar).165 F 3.365(,b)
+-.44 G .615(ut ag)-3.585 F .615(ain, DTS is designed for a much dif)
+-.055 F .614(ferent com-)-.275 F 2.718
+(munication mechanism \(shared memory\) and can o)72 504 R -.165(ve)
+-.165 G 2.719(rlook some things that Phoenix [Schaef).165 F(fer89],)
+-.275 E(Zugzw)72 516 Q .746(ang [Feldman93], *Socrates [K)-.11 F .746
+(uszmaul], and others ha)-.165 F 1.076 -.165(ve t)-.22 H 3.496(ob).165 G
+3.496(ev)-3.496 G .746(ery concerned about because the)-3.661 F .725(co\
+mmunication costs are so signi\214cant in those message passing archite\
+ctures used.)72 528 R .726(In f)6.226 F .726(act, perhaps the)-.11 F
+1.313(Deep Thought/Deep Blue hardw)72 540 R 1.312
+(are comes closest to the architecture used by Cray Blitz, b)-.11 F
+1.312(ut e)-.22 F -.165(ve)-.275 G 4.062(nt).165 G(his)-4.062 E 1.102
+(chess-speci\214c architecture still does not ha)72 552 R 1.432 -.165
+(ve a u)-.22 H 1.103
+(niform shared memory system that is global across all).165 F
+(processors and chess processors [Hsu90].)72 564 Q EP
+%%Page: 20 20
+%%BeginPageSetup
+BP
+%%EndPageSetup
+/F0 11/Times-Roman@0 SF(It')72 96 Q 3.367(su)-.605 G .616(nfortunate th\
+at shared memory is an architectural design feature that doesn')-3.367 F
+3.366(ts)-.198 G .616(cale to lar)-3.366 F .616(ge numbers)-.198 F .39(\
+of processors, because CB might produce some interesting performance re\
+sults with really lar)72 108 R .39(ge numbers)-.198 F 1.413
+(of processors.)72 120 R(Ho)6.913 E(we)-.275 E -.165(ve)-.275 G 2.293
+-.44(r, t).165 H 1.413(his is not the case, and it is doubtful that a C\
+ray-class machine will support).44 F .474(shared memory on more than 64\
+ processors, using a high-speed interconnect lik)72 132 R 3.224(et)-.11
+G .474(he Cray machines use.)-3.224 F .032
+(As a result, this algorithm really will only scale as f)72 144 R .031
+(ar as a shared memory architecture scales.)-.11 F(An)5.531 E 2.781(yd)
+-.165 G(elays)-2.781 E 1.782(\(such as those in some architectures that\
+ use a hierarchical memory or)72 156 R -.055(ga)-.198 G 1.783
+(nization with v).055 F 1.783(arying delays)-.275 F .496
+(depending on ho)72 168 R 3.246(wf)-.275 G .496
+(ar the memory is from the requesting processor\) will certainly ha)
+-3.356 F .826 -.165(ve a)-.22 H 3.246(na).165 G(dv)-3.246 E .496
+(erse ef)-.165 F(fect)-.275 E(on DTS.)72 180 Q EP
+%%Page: 21 21
+%%BeginPageSetup
+BP
+%%EndPageSetup
+.44 LW 418.139 88.75 193.86 88.75 DL/F0 11/Times-Roman@0 SF(processors)
+298.673 98 Q 418.139 102.75 193.86 102.75 DL 23.375(pos 1)199.36 112 R
+35.75(248)35.75 G(16)-6.875 E 418.139 116.75 193.86 116.75 DL 16.5(12)
+209.139 126 S 13.75(,830 1,415)-16.5 F 22(832 435)24.75 F(311)16.5 E
+418.139 130.75 193.86 130.75 DL 16.5(22)209.139 140 S 13.75(,849 1,424)
+-16.5 F 22(791 438)24.75 F(274)16.5 E 418.139 144.75 193.86 144.75 DL
+16.5(33)209.139 154 S 13.75(,274 1,637)-16.5 F 22(884 467)24.75 F(239)
+16.5 E 418.139 158.75 193.86 158.75 DL 16.5(42)209.139 168 S 13.75
+(,308 1,154)-16.5 F 22(591 349)24.75 F(208)16.5 E 418.139 172.75 193.86
+172.75 DL 16.5(51)209.139 182 S 22(,584 792 440 243)-16.5 F(178)16.5 E
+418.139 186.75 193.86 186.75 DL 16.5(64)209.139 196 S 13.75
+(,294 2,147 1,160)-16.5 F 13.75(670 452)24.75 F 418.139 200.75 193.86
+200.75 DL 16.5(71)209.139 210 S 22(,888 993 524 273)-16.5 F(187)16.5 E
+418.139 214.75 193.86 214.75 DL 16.5(87)209.139 224 S 13.75
+(,275 3,637 1,966 1,039 680)-16.5 F 418.139 228.75 193.86 228.75 DL 16.5
+(93)209.139 238 S 13.75(,940 1,970 1,094)-16.5 F 13.75(635 398)24.75 F
+418.139 242.75 193.86 242.75 DL 13.75(10 2,431 1,215)203.639 252 R 22
+(639 333)24.75 F(187)16.5 E 418.139 256.75 193.86 256.75 DL 13.75
+(11 3,062 1,531)203.639 266 R 22(827 425)24.75 F(247)16.5 E 418.139
+270.75 193.86 270.75 DL 13.75(12 2,518 1,325)203.639 280 R 22(662 364)
+24.75 F(219)16.5 E 418.139 284.75 193.86 284.75 DL 13.75(13 2,131 1,121)
+203.639 294 R 22(560 313)24.75 F(192)16.5 E 418.139 298.75 193.86 298.75
+DL 13.75(14 1,871)203.639 308 R 22(935 534 296)24.75 F(191)16.5 E
+418.139 312.75 193.86 312.75 DL 13.75(15 2,648 1,324)203.639 322 R 22
+(715 378)24.75 F(243)16.5 E 418.139 326.75 193.86 326.75 DL 13.75
+(16 2,347 1,235)203.639 336 R 22(601 321)24.75 F(182)16.5 E 418.139
+340.75 193.86 340.75 DL 13.75(17 4,884 2,872 1,878 1,085 814)203.639 350
+R 418.139 354.75 193.86 354.75 DL 22(18 646 358 222 124)203.639 364 R
+(84)22 E 418.139 368.75 193.86 368.75 DL 13.75(19 2,983 1,491)203.639
+378 R 22(785 426)24.75 F(226)16.5 E 418.139 382.75 193.86 382.75 DL
+13.75(20 7,473 3,736 1,916 1,083 530)203.639 392 R 418.139 396.75 193.86
+396.75 DL 13.75(21 3,626 1,813)203.639 406 R 22(906 489)24.75 F(237)16.5
+E 418.139 410.75 193.86 410.75 DL 13.75(22 2,560 1,347)203.639 420 R 22
+(691 412)24.75 F(264)16.5 E 418.139 424.75 193.86 424.75 DL 13.75
+(23 2,039 1,019)203.639 434 R 22(536 323)24.75 F(206)16.5 E 418.139
+438.75 193.86 438.75 DL 13.75(24 2,563 1,281)203.639 448 R 22(657 337)
+24.75 F(178)16.5 E 418.139 452.75 193.86 452.75 DL 387.889 116.75
+387.889 452.75 DL 346.639 116.75 346.639 452.75 DL 305.389 116.75
+305.389 452.75 DL 264.139 116.75 264.139 452.75 DL 222.889 116.75
+222.889 452.75 DL 418.139 88.75 418.139 452.75 DL 193.86 88.75 193.86
+452.75 DL 387.889 102.75 387.889 452.75 DL 346.639 102.75 346.639 452.75
+DL 305.389 102.75 305.389 452.75 DL 264.139 102.75 264.139 452.75 DL
+222.889 88.75 222.889 452.75 DL -.88(Ta)235.297 476.2 S(ble 4 Search T)
+.88 E(ime in Seconds)-.385 E EP
+%%Page: 22 22
+%%BeginPageSetup
+BP
+%%EndPageSetup
+.44 LW 497.889 88.75 114.11 88.75 DL/F0 11/Times-Roman@0 SF(processors)
+298.673 98 Q 497.889 102.75 114.11 102.75 DL 38.5(pos 1)119.61 112 R 66
+(248)66 G(16)-2.75 E 497.889 116.75 114.11 116.75 DL 22(18)129.389 126 S
+19.25(7,735,974 89,052,012)-22 F 13.75
+(105,025,123 109,467,495 155,514,410)16.5 F 497.889 130.75 114.11 130.75
+DL 22(28)129.389 140 S 19.25(8,954,757 90,289,077)-22 F 13.75
+(100,568,301 110,988,161 137,965,406)16.5 F 497.889 144.75 114.11 144.75
+DL 16.5(31)129.389 154 S 13.75
+(01,302,792 102,822,332 111,433,074 117,366,515 119,271,093)-16.5 F
+497.889 158.75 114.11 158.75 DL 22(47)129.389 168 S 19.25
+(1,726,853 72,802,754 74,853,409 88,137,085)-22 F(104,230,094)16.5 E
+497.889 172.75 114.11 172.75 DL 22(54)129.389 182 S 19.25
+(9,386,616 50,127,414 55,834,316 61,619,298 89,506,306)-22 F 497.889
+186.75 114.11 186.75 DL 16.5(61)129.389 196 S 13.75
+(33,238,718 135,237,296 146,562,594 168,838,428 226,225,307)-16.5 F
+497.889 200.75 114.11 200.75 DL 22(75)129.389 210 S 19.25
+(8,593,747 62,602,792 66,243,490 68,868,878 93,575,946)-22 F 497.889
+214.75 114.11 214.75 DL 16.5(82)129.389 224 S 13.75
+(25,906,282 229,294,872 248,496,917 261,728,552 340,548,431)-16.5 F
+497.889 228.75 114.11 228.75 DL 16.5(91)129.389 238 S 13.75
+(22,264,617 124,098,584 138,226,951 159,930,005 199,204,874)-16.5 F
+497.889 242.75 114.11 242.75 DL 19.25
+(10 75,301,353 76,430,872 80,651,716 83,656,702 93,431,597)123.889 252 R
+497.889 256.75 114.11 256.75 DL 19.25(11 95,321,494 96,751,315)123.889
+266 R 13.75(104,853,646 107,369,070 123,994,812)16.5 F 497.889 270.75
+114.11 270.75 DL 19.25(12 79,975,416 85,447,418 85,657,884 94,000,085)
+123.889 280 R(112,174,209)16.5 E 497.889 284.75 114.11 284.75 DL 19.25
+(13 66,100,160 70,622,802 70,796,754 78,834,155 96,053,649)123.889 294 R
+497.889 298.75 114.11 298.75 DL 19.25
+(14 58,099,574 58,971,066 67,561,507 74,791,668 95,627,150)123.889 308 R
+497.889 312.75 114.11 312.75 DL 19.25
+(15 84,143,340 85,405,488 92,557,676 97,486,065)123.889 322 R
+(124,516,703)16.5 E 497.889 326.75 114.11 326.75 DL 19.25
+(16 75,738,094 80,920,173 79,039,499 84,141,904 94,701,972)123.889 336 R
+497.889 340.75 114.11 340.75 DL 13.75
+(17 154,901,225 184,970,278 242,480,013 279,166,418 416,426,105)123.889
+350 R 497.889 354.75 114.11 354.75 DL 19.25
+(18 20,266,629 22,856,254 28,443,165 31,608,146 42,454,639)123.889 364 R
+497.889 368.75 114.11 368.75 DL 19.25(19 93,858,903 95,266,785)123.889
+378 R 13.75(100,527,830 108,742,238 114,692,731)16.5 F 497.889 382.75
+114.11 382.75 DL 13.75
+(20 231,206,390 234,674,482 241,284,621 271,751,263 264,493,531)123.889
+392 R 497.889 396.75 114.11 396.75 DL 13.75
+(21 112,457,464 114,144,324 114,425,474 123,247,294 118,558,091)123.889
+406 R 497.889 410.75 114.11 410.75 DL 19.25
+(22 81,302,340 86,865,131 89,432,576)123.889 420 R 13.75
+(106,348,704 135,196,568)16.5 F 497.889 424.75 114.11 424.75 DL 19.25
+(23 63,598,940 64,552,923 68,117,815 81,871,010)123.889 434 R
+(103,621,303)16.5 E 497.889 438.75 114.11 438.75 DL 19.25
+(24 80,413,971 81,620,179 83,919,196 85,810,169 90,074,814)123.889 448 R
+497.889 452.75 114.11 452.75 DL 429.139 116.75 429.139 452.75 DL 357.639
+116.75 357.639 452.75 DL 286.139 116.75 286.139 452.75 DL 214.639 116.75
+214.639 452.75 DL 143.139 116.75 143.139 452.75 DL 497.889 88.75 497.889
+452.75 DL 114.11 88.75 114.11 452.75 DL 429.139 102.75 429.139 452.75 DL
+357.639 102.75 357.639 452.75 DL 286.139 102.75 286.139 452.75 DL
+214.639 102.75 214.639 452.75 DL 143.139 88.75 143.139 452.75 DL -.88
+(Ta)238.911 476.2 S(ble 5).88 E -.88(To)5.5 G(tal Nodes Searched).88 E
+EP
+%%Page: 23 23
+%%BeginPageSetup
+BP
+%%EndPageSetup
+.44 LW 393.582 88.75 218.418 88.75 DL/F0 11/Times-Roman@0 SF(processors)
+298.866 98 Q 393.582 102.75 218.418 102.75 DL 13.943(pos 1)224.11 112 R
+24.75(2481)20.625 G(6)-24.75 E 393.582 116.75 218.418 116.75 DL 16.5
+(112)234.082 126 S 13.75(.0 3.4 6.5)-16.5 F(9.1)22 E 393.582 130.75
+218.418 130.75 DL 16.5(212)234.082 140 S 13.75(.0 3.6 6.5 10.4)-16.5 F
+393.582 144.75 218.418 144.75 DL 16.5(312)234.082 154 S 13.75
+(.0 3.7 7.0 13.7)-16.5 F 393.582 158.75 218.418 158.75 DL 16.5(412)
+234.082 168 S 13.75(.0 3.9 6.6 11.1)-16.5 F 393.582 172.75 218.418
+172.75 DL 16.5(512)234.082 182 S 13.75(.0 3.6 6.5)-16.5 F(8.9)22 E
+393.582 186.75 218.418 186.75 DL 16.5(612)234.082 196 S 13.75
+(.0 3.7 6.4)-16.5 F(9.5)22 E 393.582 200.75 218.418 200.75 DL 16.5(711)
+234.082 210 S 13.75(.9 3.6 6.9 10.1)-16.5 F 393.582 214.75 218.418
+214.75 DL 16.5(812)234.082 224 S 13.75(.0 3.7 7.0 10.7)-16.5 F 393.582
+228.75 218.418 228.75 DL 16.5(912)234.082 238 S 13.75(.0 3.6 6.2)-16.5 F
+(9.9)22 E 393.582 242.75 218.418 242.75 DL 13.75(10 1 2.0 3.8 7.3 13.0)
+228.582 252 R 393.582 256.75 218.418 256.75 DL 13.75
+(11 1 2.0 3.7 7.2 12.4)228.582 266 R 393.582 270.75 218.418 270.75 DL
+13.75(12 1 1.9 3.8 6.9 11.5)228.582 280 R 393.582 284.75 218.418 284.75
+DL 13.75(13 1 1.9 3.8 6.8 11.1)228.582 294 R 393.582 298.75 218.418
+298.75 DL 13.75(14 1 2.0 3.5 6.3)228.582 308 R(9.8)22 E 393.582 312.75
+218.418 312.75 DL 13.75(15 1 2.0 3.7 7.0 10.9)228.582 322 R 393.582
+326.75 218.418 326.75 DL 13.75(16 1 1.9 3.9 7.3 12.9)228.582 336 R
+393.582 340.75 218.418 340.75 DL 13.75(17 1 1.7 2.6 4.5)228.582 350 R
+(6.0)22 E 393.582 354.75 218.418 354.75 DL 13.75(18 1 1.8 2.9 5.2)
+228.582 364 R(7.7)22 E 393.582 368.75 218.418 368.75 DL 13.75
+(19 1 2.0 3.8 7.0 13.2)228.582 378 R 393.582 382.75 218.418 382.75 DL
+13.75(20 1 2.0 3.9 6.9 14.1)228.582 392 R 393.582 396.75 218.418 396.75
+DL 13.75(21 1 2.0 4.0 7.4 15.3)228.582 406 R 393.582 410.75 218.418
+410.75 DL 13.75(22 1 1.9 3.7 6.2)228.582 420 R(9.7)22 E 393.582 424.75
+218.418 424.75 DL 13.75(23 1 2.0 3.8 6.3)228.582 434 R(9.9)22 E 393.582
+438.75 218.418 438.75 DL 13.75(24 1 2.0 3.9 7.6 14.4)228.582 448 R
+393.582 452.75 218.418 452.75 DL -.22(av)223.918 462 S 16.5(g12).22 G
+13.75(.0 3.7 6.6 11.1)-16.5 F 393.582 466.75 218.418 466.75 DL 360.582
+116.75 360.582 466.75 DL 330.332 116.75 330.332 466.75 DL 300.082 116.75
+300.082 466.75 DL 269.832 116.75 269.832 466.75 DL 247.832 116.75
+247.832 466.75 DL 393.582 88.75 393.582 466.75 DL 218.418 88.75 218.418
+466.75 DL 360.582 102.75 360.582 466.75 DL 330.332 102.75 330.332 466.75
+DL 300.082 102.75 300.082 466.75 DL 269.832 102.75 269.832 466.75 DL
+247.832 88.75 247.832 466.75 DL -.88(Ta)224.798 490.2 S(ble 6).88 E
+-.165(Pa)5.5 G(rallel Processing Speedup).165 E 2.75(6. Future)72 514.2
+R -.11(wo)2.75 G(rk).11 E .824(Perhaps the most signi\214cant future w)
+72 538.2 R .824
+(ork for this algorithm lies in selecting split points more accurately)
+-.11 F(.)-.715 E -.165(Fo)72 550.2 S 4.713(rs).165 G 1.963
+(ome positions, the current Split\(\) algorithm performs admirably)
+-4.713 F 7.462(.F)-.715 G 1.962(or others, it performs poorly)-7.627 F
+(.)-.715 E(An)72 562.2 Q(ything that impro)-.165 E -.165(ve)-.165 G 2.75
+(st).165 G(he "poor" cases has a positi)-2.75 E .33 -.165(ve e)-.275 H
+-.275(ff).165 G(ect on o).275 E -.165(ve)-.165 G(rall performance.).165
+E EP
+%%Page: 24 24
+%%BeginPageSetup
+BP
+%%EndPageSetup
+/F0 11/Times-Roman@0 SF .071(There are at least tw)72 96 R 2.822(oa)-.11
+G .072(pproaches to this problem.)-2.822 F .072
+(One is to more accurately \214nd good split points \(some-)5.572 F .721
+(thing that might be impossible in a signi\214cant number of positions\
+\).)72 108 R .72(Another is to de)6.22 F -.165(ve)-.275 G .72
+(lop some sort of).165 F .501
+(con\214dence in a list of split points, someho)72 120 R 3.251(we)-.275
+G .501(liminating those that are potentially bad.)-3.251 F .502
+(After eliminating)6.002 F .511(such split points, the o)72 132 R -.165
+(ve)-.165 G .511(rhead should drop signi\214cantly).165 F 6.011(.U)-.715
+G(nfortunately)-6.011 E 3.261(,d)-.715 G .511
+(etecting such split points is not)-3.261 F(easy)72 144 Q 5.882(.T)-.715
+G .382(he \214rst step will lik)-5.882 F .383
+(ely be more detailed analysis of the trees searched by C-B.)-.11 F .383
+(The problem with)5.883 F .434(this is that these trees re)72 156 R .434
+(gularly e)-.165 F .433(xceed one billion nodes on a T90, making the v)
+-.165 F .433(olume of data some)-.22 F(what)-.275 E(lar)72 168 Q 3.063
+(ge! Such)-.198 F(lar)3.063 E .313(ge trees require recognizing a speci\
+\214c performance feature and then adding instructions to)-.198 F .156
+(the code to measure the feature "in situ" since analyzing such a lar)72
+180 R .156(ge tree by visual inspection is impracti-)-.198 F(cal.)72 192
+Q .913(The current algorithm depends on rapid information sharing and u\
+ses shared memory to implement this)72 216 R 4.45(sharing. The)72 228 R
+(ne)4.449 E 1.699(xt logical step in algorithm de)-.165 F -.165(ve)-.275
+G 1.699(lopment is to mo).165 F 2.029 -.165(ve t)-.165 H -2.31 -.275
+(ow a).165 H 1.699(rd a distrib).275 F 1.699(uted architecture.)-.22 F
+-.44(Wi)72 240 S .091(th HIPPI and/or other high-performance processor \
+interconnects, a distrib).44 F .091(uted v)-.22 F .092
+(ersion of this algorithm)-.165 F 1.738(should deli)72 252 R -.165(ve)
+-.275 G 4.488(rh).165 G 1.738(igh performance if care is tak)-4.488 F
+1.737(en to control task granularity \(which is not an issue on)-.11 F
+(machines lik)72 264 Q 2.75(et)-.11 G(he C90/T90 with shared memory)
+-2.75 E(.\))-.715 E(7. Bibliograph)72 288 Q(y)-.055 E 1.053(S. Akl, D. \
+Barnard, and R. Doran, "The Design, Analysis and Implementation of a P)
+72 312 R 1.054(arallel Alpha-Beta)-.165 F 2.925(Algorithm", IEEE T)72
+324 R 2.925(ransactions on P)-.385 F 2.924
+(attern Analysis and Machine Intelligence, P)-.165 F 2.924
+(AMI-4, \(2\) \(1982\),)-1.012 F(\(192-203\).)72 336 Q 1.392(B. A)72 360
+R(werb)-1.012 E 1.392(uch, "A Ne)-.22 F 4.142(wD)-.275 G(istrib)-4.142 E
+1.393(uted Depth-First Search Algorithm", Information Processing Letter\
+s \(20\))-.22 F(\(1985\) 147-150.)72 372 Q .363(G. Baudet, "The Design \
+and Analysis of Algorithms for Asynchronous Multiprocessors", Ph. D Dis\
+serta-)72 396 R(tion, Carne)72 408 Q(gie-Mellon Uni)-.165 E -.165(ve)
+-.275 G(rsity).165 E 2.75(,P)-.715 G(ittsb)-2.75 E(ur)-.22 E(gh, P)-.198
+E 2.75(a. \(1978\).)-.165 F .892(M. Campbell, "Algorithms for the P)72
+432 R .892(arallel Search of Game T)-.165 F .892
+(rees", M. Sc. Thesis, T)-.385 F .892(echnical Report TR)-.77 F
+(81-8, Computer Science Department, Uni)72 444 Q -.165(ve)-.275 G
+(rsity of Alberta, Edmonton \(1981\).).165 E 4.095(RF)72 468 S 1.345
+(eldmann, B. Monieni, P)-4.095 F 4.095(.M)-1.221 G 1.345
+(ysliwietz and O. V)-4.095 F(ornber)-1.419 E(ger)-.198 E 4.095(,")-.44 G
+(Distrib)-4.095 E 1.345(uted g)-.22 F 1.344(ame tree search," in P)-.055
+F(arallel)-.165 E
+(algorithms for machine intelligence and pattern recognition \(1990\).)
+72 480 Q 3(RF)72 504 S .25(eldmann, "Game T)-3 F .251
+(ree Search on Massi)-.385 F -.165(ve)-.275 G .251(ly P).165 F .251
+(arallel Systems," Ph.D. Theses, Uni)-.165 F -.165(ve)-.275 G .251
+(rsity of P).165 F(aderborn,)-.165 E(August, 1993.)72 516 Q(R. Fink)72
+540 Q(el and J. Fishb)-.11 E(urn, "P)-.22 E(arallelism in Alpha-Beta Se\
+arch", Arti\214cial Intelligence \(1982\) 89-106.)-.165 E 1.706
+(F-h Hsu, "Lar)72 564 R 1.705(ge scale parallelism of alpha-beta search\
+: an algorithmic and architectural study)-.198 F 1.705(," Ph.D.)-.715 F
+(Thesis, Carne)72 576 Q(gie-Mellon Uni)-.165 E -.165(ve)-.275 G
+(rsity \(1990\).).165 E EP
+%%Page: 25 25
+%%BeginPageSetup
+BP
+%%EndPageSetup
+/F0 11/Times-Roman@0 SF .025(R. Hyatt, B. Suter)72 96 R 2.775(,a)-.44 G
+.025(nd H. Nelson, "A P)-2.775 F .026(arallel Alpha/Beta T)-.165 F .026
+(ree Searching Algorithm," P)-.385 F .026(arallel Computing)-.165 F
+(10 \(1989\) 299-308.)72 108 Q 1.052(R. Hyatt, "A High-Performance P)72
+132 R 1.052(arallel Algorithm to Search Depth-First Game T)-.165 F 1.051
+(rees," Ph.D. Disserta-)-.385 F(tion, Uni)72 144 Q -.165(ve)-.275 G
+(rsity of Alabama at Birmingham, 1988.).165 E 1.7(R. Hyatt, A. Go)72 168
+R(wer)-.275 E 4.45(,a)-.44 G 1.7(nd H. Nelson, "Cray Blitz", Adv)-4.45 F
+1.7(ances in Computer Chess 4, Per)-.275 F -.055(ga)-.198 G 1.701
+(mmon Press).055 F(\(1986\) \(8-18\).)72 180 Q .293
+(R. Hyatt, H. Nelson, A. Go)72 204 R(wer)-.275 E 3.043(,")-.44 G .292
+(Cray Blitz - 1984 Chess Champion", T)-3.043 F .292
+(elematics and Informatics \(2\) \(4\),)-.77 F(Per)72 216 Q -.055(ga)
+-.198 G(mmon Press Ltd. \(1986\) \(299-305\).).055 E .119(D. Knuth and \
+R. Moore, "An Analysis of Alpha-Beta Pruning", Arti\214cial Intelligenc\
+e 6 \(1975\) \(293-326\).)72 240 R(B. K)72 264 Q
+(uszmaul, "Synchronized MIMD Computing," Ph.D. Thesis, MIT)-.165 E 2.75
+(,1)-.814 G(994.)-2.75 E 2.239(G. Lindstrom, "The K)72 288 R 2.569 -.165
+(ey N)-.275 H 2.239(ode Method: A Highly P).165 F 2.239
+(arallel Alpha-Beta Algorithm", T)-.165 F 2.238(echnical Report)-.77 F
+(UUCS 83-101, Department of Computer Science, Uni)72 300 Q -.165(ve)
+-.275 G(rsity of Utah, 1983.).165 E 1.628 -.814(T. M)72 324 T
+(arsland and J. Schaef).814 E(fer)-.275 E 2.75(,C)-.44 G
+(omputers, Chess and Cognition, Springer)-2.75 E(-V)-.22 E(erlag, 1990.)
+-1.221 E 1.913 -.814(T. M)72 348 T .285(arsland and M. Campbell, "P).814
+F .286(arallel Search of Strongly Ordered Game T)-.165 F .286(rees", A)
+-.385 F .286(CM Computing Sur)-.44 F(-)-.22 E -.165(vey)72 360 S 2.75
+(s\().165 G(4\) \(1982\) \(533-551\).)-2.75 E 2.905 -.814(T. A)72 384 T
+4.027(.M).814 G 1.277(arsland and F)-4.027 F 4.027(.P)-.88 G(opo)-4.027
+E 4.026(wich, "P)-.275 F 1.276(arallel Game-tree Search", IEEE T)-.165 F
+1.276(ransactions on P)-.385 F 1.276(attern Analysis)-.165 F
+(and Machine Intelligence, P)72 396 Q(AMI-7, \(1985\) \(442-452\).)
+-1.012 E 2.523 -.814(T. M)72 420 T .895(arsland, M. Campbell, and A. Ri)
+.814 F -.165(ve)-.275 G .896(ra, "P).165 F .896
+(arallel Search of Game T)-.165 F .896(rees", T)-.385 F .896
+(echnical Report TR 80-7,)-.77 F(Computing Science Department, Uni)72
+432 Q -.165(ve)-.275 G(rsity of Alberta, Edmonton \(1980\).).165 E 2.851
+-.814(T. M)72 456 T 1.222(arsland and M. Campbell, "Methods for P).814 F
+1.222(arallel Search of Game T)-.165 F 1.222
+(rees", Proceedings of the 1981)-.385 F
+(International Joint Conference on Arti\214cial Intelligence.)72 468 Q
+3.843 -.814(T. M)72 492 T 2.215(arsland, M. Olafsson, and J. Schaef).814
+F(fer)-.275 E 4.966(,")-.44 G 2.216(Multiprocessor T)-4.966 F 2.216
+(ree-Search Experiments", Adv)-.385 F 2.216(ances in)-.275 F
+(Computer Chess 4, Per)72 504 Q -.055(ga)-.198 G
+(mmon Press \(1986\) \(37-51\).).055 E 3.234(M. Ne)72 528 R 3.234
+(wborn, "A P)-.275 F 3.233
+(arallel Search Chess Program", Proceedings, A)-.165 F 3.233
+(CM Annual Conference, \(1985\),)-.44 F(\(272-277\).)72 540 Q .826
+(J. Pearl, "Scout: A Simple Game-Searching Algorithm with Pro)72 564 R
+-.165(ve)-.165 G 3.577(nO).165 G .827
+(ptimal Properties", Proceedings of)-3.577 F(the First Annual National \
+Conference on Arti\214cial Intelligence, Stanford, \(1980\).)72 576 Q EP
+%%Page: 26 26
+%%BeginPageSetup
+BP
+%%EndPageSetup
+/F0 11/Times-Roman@0 SF 2.219 -.88(F. P)72 96 T(opo).88 E .459
+(wich and T)-.275 F 3.208(.M)-.814 G .458(arsland, "P)-3.208 F .458
+(arabelle: Experiments with a P)-.165 F .458(arallel Chess Program", T)
+-.165 F .458(echnical Report)-.77 F
+(TR 83-7, Computing Science Department, Uni)72 108 Q -.165(ve)-.275 G
+(rsity of Alberta, Edmonton \(1983\).).165 E .612(J. Schaef)72 132 R
+(fer)-.275 E 3.362(,")-.44 G(Distrib)-3.362 E .612(uted g)-.22 F .612
+(ame-tree search," Journal of P)-.055 F .612(arallel and Distrib)-.165 F
+.612(uted Computing 6 \(2\) \(1989\),)-.22 F(90-114.)72 144 Q .133
+(I. Steinber)72 168 R 2.883(ga)-.198 G .133(nd M. Solomon, "Searching g)
+-2.883 F .132
+(ame trees in parallel," Proceedings of the International Confer)-.055 F
+(-)-.22 E(ence on P)72 180 Q(arallel Processing \(V)-.165 E
+(ol 3\) \(1990\), 9-17.)-1.419 E 1.89(Z. Y)72 204 R 1.89(ang and T)-1.1
+F 4.64(.M)-.814 G 1.89(arsland, "Global States and T)-4.64 F 1.89
+(ime in Distrib)-.385 F 1.89(uted Systems," IEEE Computer Society)-.22 F
+(Press, No)72 216 Q -.165(ve)-.165 G(mber 1993.).165 E EP
+%%Page: 27 27
+%%BeginPageSetup
+BP
+%%EndPageSetup
+/F0 11/Times-Roman@0 SF(Appendix A)72 96 Q([Ev)72 120 Q(ent "23rd A)
+-.165 E(CM International Computer Chess Championship"])-.44 E
+([Site "Indianapolis, MD"])72 132 Q([Date "02.14.1993"])72 144 Q
+([Round "?"])72 156 Q([White "Mchess Pro"])72 168 Q
+([Black "Cray Blitz"])72 180 Q([Result "0-1"])72 192 Q .78(1. e4)72 204
+R .78(e5 2. Nc3 Nc6 3. f4)6.28 F -.165(ex)6.28 G .78(f4 4. Nf3 g5 5. d4)
+.165 F .78(g4 6. Bc4 gxf3 7. o-o d5 8. e)6.28 F .78
+(xd5 Bg4 9. Qd2 Na5 10.)-.165 F .744
+(Bb5+ c6 11. Qxf4 Nf6 12. Re1+ Kd7 13. dxc6+ bxc6 14. Ne4 Nx)72 216 R
+.744(e4 15. Qxg4+ Kc7 16. Rx)-.165 F .744(e4 cxb5 17.)-.165 F 1.054
+(Qxf3 Qd7 18. Rf4 Be7 19. Rxf7 Raf8 20. Bf4+ Kb6 21. Be5 Rhg8 22. c3)72
+228 R 1.054(Nc6 23. Re1 Qe8 24. Rxf8)6.554 F .718
+(Qxf8 25. Qd5 Rg5 26. a4)72 240 R .718(bxa4 27. c4)6.218 F(Nx)6.218 E
+.718(e5 28. Rx)-.165 F .718(e5 Rx)-.165 F .718(e5 29. Qx)-.165 F .719
+(e5 Qd8 30. c5+ Kb5 31. Qe2+ Kb4)-.165 F .585(32. Qd3 Bf6 33. Qc3+ Kb5 \
+34. Qd3+ Kc6 35. Qf3+ Kd7 36. Qe4 Qe7 37. Qb7+ K)72 252 R .585
+(e8 38. Qa8+ Qd8 39.)-.275 F .911(Qc6+ Kf7 40. Qb7+ Kf8 41. d5)72 264 R
+.911(Qe7 42. Qb8+ Kf7 43. Kf1 Bxb2 44. g4)6.411 F .912
+(Bc3 45. Kf2 Qxc5+ 46. Kf1)6.411 F(Qc4+ 47. Kf2 Qd4+ 48. Kf3 Qd1+ 49. K)
+72 276 Q(e3 Bd2+ 50. Kf2 Qe1+ 51. Kg2 Qe2+)-.275 E EP
+%%Trailer
+end
+%%EOF