path: root/parallel/search.ps

%!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