From 10acef9e6f2d1f56a39c7f4b9ccf4b4be6f8bed7 Mon Sep 17 00:00:00 2001 From: Scott Gasch Date: Wed, 1 Jun 2016 19:04:57 -0700 Subject: A bunch of chess-related papers. --- parallel/pami.ps | 3771 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 3771 insertions(+) create mode 100755 parallel/pami.ps (limited to 'parallel/pami.ps') diff --git a/parallel/pami.ps b/parallel/pami.ps new file mode 100755 index 0000000..bf1dafa --- /dev/null +++ b/parallel/pami.ps @@ -0,0 +1,3771 @@ +%!PS +%%Version: 3.3 +%%DocumentFonts: (atend) +%%Pages: (atend) +%%EndComments +% +% Version 3.3 prologue for troff files. +% + +/#copies 1 store +/aspectratio 1 def +/formsperpage 1 def +/landscape false def +/linewidth .3 def +/magnification 1 def +/margin 0 def +/orientation 0 def +/resolution 720 def +/rotation 1 def +/xoffset 0 def +/yoffset 0 def + +/roundpage true def +/useclippath true def +/pagebbox [0 0 612 792] def + +/R /Times-Roman def +/I /Times-Italic def +/B /Times-Bold def +/BI /Times-BoldItalic def +/H /Helvetica def +/HI /Helvetica-Oblique def +/HB /Helvetica-Bold def +/HX /Helvetica-BoldOblique def +/CW /Courier def +/CO /Courier def +/CI /Courier-Oblique def +/CB /Courier-Bold def +/CX /Courier-BoldOblique def +/PA /Palatino-Roman def +/PI /Palatino-Italic def +/PB /Palatino-Bold def +/PX /Palatino-BoldItalic def +/Hr /Helvetica-Narrow def +/Hi /Helvetica-Narrow-Oblique def +/Hb /Helvetica-Narrow-Bold def +/Hx /Helvetica-Narrow-BoldOblique def +/KR /Bookman-Light def +/KI /Bookman-LightItalic def +/KB /Bookman-Demi def +/KX /Bookman-DemiItalic def +/AR /AvantGarde-Book def +/AI /AvantGarde-BookOblique def +/AB /AvantGarde-Demi def +/AX /AvantGarde-DemiOblique def +/NR /NewCenturySchlbk-Roman def +/NI /NewCenturySchlbk-Italic def +/NB /NewCenturySchlbk-Bold def +/NX /NewCenturySchlbk-BoldItalic def +/ZD /ZapfDingbats def +/ZI /ZapfChancery-MediumItalic def +/S /S def +/S1 /S1 def +/GR /Symbol def + +/inch {72 mul} bind def +/min {2 copy gt {exch} if pop} bind def + +/setup { + counttomark 2 idiv {def} repeat pop + + landscape {/orientation 90 orientation add def} if + /scaling 72 resolution div def + linewidth setlinewidth + 1 setlinecap + + pagedimensions + xcenter ycenter translate + orientation rotation mul rotate + width 2 div neg height 2 div translate + xoffset inch yoffset inch neg translate + margin 2 div dup neg translate + magnification dup aspectratio mul scale + scaling scaling scale + + /Symbol /S Sdefs cf + /Times-Roman /S1 S1defs cf + 0 0 moveto +} def + +/pagedimensions { + useclippath userdict /gotpagebbox known not and { + /pagebbox [clippath pathbbox newpath] def + roundpage currentdict /roundpagebbox known and {roundpagebbox} if + } if + pagebbox aload pop + 4 -1 roll exch 4 1 roll 4 copy + landscape {4 2 roll} if + sub /width exch def + sub /height exch def + add 2 div /xcenter exch def + add 2 div /ycenter exch def + userdict /gotpagebbox true put +} def + +/pagesetup { + /page exch def + currentdict /pagedict known currentdict page known and { + page load pagedict exch get cvx exec + } if +} def + +/decodingdefs [ + {counttomark 2 idiv {y moveto show} repeat} + {neg /y exch def counttomark 2 idiv {y moveto show} repeat} + {neg moveto {2 index stringwidth pop sub exch div 0 32 4 -1 roll widthshow} repeat} + {neg moveto {spacewidth sub 0.0 32 4 -1 roll widthshow} repeat} + {counttomark 2 idiv {y moveto show} repeat} + {neg setfunnytext} +] def + +/setdecoding {/t decodingdefs 3 -1 roll get bind def} bind def + +/w {neg moveto show} bind def +/m {neg dup /y exch def moveto} bind def +/done {/lastpage where {pop lastpage} if} def + +/f { + dup /font exch def findfont exch + dup /ptsize exch def scaling div dup /size exch def scalefont setfont + linewidth ptsize mul scaling 10 mul div setlinewidth + /spacewidth ( ) stringwidth pop def +} bind def + +/changefont { + /fontheight exch def + /fontslant exch def + currentfont [ + 1 0 + fontheight ptsize div fontslant sin mul fontslant cos div + fontheight ptsize div + 0 0 + ] makefont setfont +} bind def + +/sf {f} bind def + +/cf { + dup length 2 idiv + /entries exch def + /chtab exch def + /newfont exch def + + findfont dup length 1 add dict + /newdict exch def + {1 index /FID ne {newdict 3 1 roll put} {pop pop} ifelse} forall + + newdict /Metrics entries dict put + newdict /Metrics get + begin + chtab aload pop + 1 1 entries {pop def} for + newfont newdict definefont pop + end +} bind def + +% +% A few arrays used to adjust reference points and character widths in some +% of the printer resident fonts. If square roots are too high try changing +% the lines describing /radical and /radicalex to, +% +% /radical [0 -75 550 0] +% /radicalex [-50 -75 500 0] +% +% Move braceleftbt a bit - default PostScript character is off a bit. +% + +/Sdefs [ + /bracketlefttp [201 500] + /bracketleftbt [201 500] + /bracketrighttp [-81 380] + /bracketrightbt [-83 380] + /braceleftbt [203 490] + /bracketrightex [220 -125 500 0] + /radical [0 0 550 0] + /radicalex [-50 0 500 0] + /parenleftex [-20 -170 0 0] + /integral [100 -50 500 0] + /infinity [10 -75 730 0] +] def + +/S1defs [ + /underscore [0 80 500 0] + /endash [7 90 650 0] +] def +%%EndProlog +%%BeginSetup +mark +/resolution 720 def +setup +2 setdecoding +%%EndSetup +%%Page: 1 1 +/saveobj save def +mark +1 pagesetup +10 B f +(The History Heuristic and)3 1120 1 2320 840 t +(Alpha-Beta Search Enhancements in Practice)4 1943 1 1908 1200 t +10 R f +(Jonathan Schaeffer)1 761 1 2499 1680 t +10 I f +(Abstract -)1 397 1 720 2160 t +10 R f +( have been proposed to help reduce the size of)9 1923(Many enhancements to the alpha-beta algorithm)5 1967 2 1150 2160 t +( recent enhancement, the history heuristic, is described that improves the order in which)13 3591( A)1 128(minimax trees.)1 601 3 720 2400 t +( comprehensive set of experiments is reported which tries all)9 2498( A)1 130( nodes.)1 291(branches are considered at interior)4 1401 4 720 2640 t +( work on)2 387( Previous)1 416( one yields the best performance.)5 1399(combinations of enhancements to determine which)5 2118 4 720 2880 t +( concentrated on the benefits of individual enhancements or a few combina-)11 3051(assessing their performance has)3 1269 2 720 3120 t +( each enhancement should not be taken in isolation; one would like to find the combination)15 3659(tions. However,)1 661 2 720 3360 t +( indicate that the history heuristic and transposition)7 2067( Results)1 348( the greatest reduction in tree size.)6 1384(that provides)1 521 4 720 3600 t +( For)1 202(tables significantly out-perform other alpha-beta enhancements in application generated game trees.)10 4118 2 720 3840 t +( 99% of the possible reductions in tree size,)8 1779(trees up to depth 8, when taken together, they account for over)11 2541 2 720 4080 t +(with the other enhancements yielding insignificant gains.)6 2284 1 720 4320 t +10 I f +( -)1 58(Index Terms)1 524 2 720 4800 t +10 R f +(Alpha-beta search, minimax search, game trees, history heuristic, transposition tables,)9 3685 1 1355 4800 t +(minimal window search, killer heuristic.)4 1615 1 720 5040 t +cleartomark +showpage +saveobj restore +%%EndPage: 1 1 +%%Page: 2 2 +/saveobj save def +mark +2 pagesetup +11 R f +(- 2 -)2 183 1 2788 490 t +11 B f +(1. Introduction)1 739 1 720 840 t +11 R f +(Many modifications and enhancements to the alpha-beta \()7 2546 1 970 1116 t +11 S f +(ab)3516 1116 w +11 R f +(\) algorithm have been proposed)4 1394 1 3646 1116 t +( in)1 119( of the more prominent ones)5 1273( Some)1 313(to increase the efficiency of minimax game tree searching.)8 2615 4 720 1356 t +( tables [2], refutation tables [3],)5 1563(the literature include iterative deepening [1], transposition)6 2757 2 720 1596 t +( of these)2 412( Some)1 327( aspiration search [5] and the killer heuristic [3].)8 2279(minimal window search [4],)3 1302 4 720 1836 t +( each)1 232( However,)1 489( others appear to have questionable merit.)6 1863(search aids seem to be beneficial while)6 1736 4 720 2076 t +( find the combination of features)5 1457(enhancement should not be taken in isolation; one would like to)10 2863 2 720 2316 t +( merits)1 307( experiments assessing the relative)4 1531( Several)1 387(that provides the greatest reduction in tree size.)7 2095 4 720 2556 t +( these features have been reported in the literature, using both artificially constructed)12 3830(of some of)2 490 2 720 2796 t +( trees.)1 262( 7, 8])2 210([6] and application generated [1,)4 1428 3 720 3036 t +(The size of the search tree built by a depth-first)9 2148 1 970 3312 t +11 S f +(ab)3154 3312 w +11 R f +( the order in)3 561(search largely depends on)3 1159 2 3320 3312 t +( minimal)1 398( The)1 228(which branches are considered at interior nodes.)6 2128 3 720 3552 t +11 S f +(ab)3503 3552 w +11 R f +(tree arises if the branch leading)5 1378 1 3662 3552 t +( them in worst to)4 796( Examining)1 551( at all interior nodes.)4 956(to the best minimax score is considered first)7 2017 4 720 3792 t +( it)1 95( the difference between the two extremes is large,)8 2225( Since)1 306(best order results in the maximal tree.)6 1694 4 720 4032 t +( application)1 538( Typically,)1 527( a good ordering of branches at interior nodes.)8 2204(is imperative to obtain)3 1051 4 720 4272 t +(dependent knowledge is applied to make a "best guess" decision on an order to consider them in.)16 4258 1 720 4512 t +( to the)2 294(In this paper, a recent enhancement)5 1592 2 970 4788 t +11 S f +(ab)2893 4788 w +11 R f +(algorithm, the history heuristic, is described)5 1980 1 3060 4788 t +( order in which branches are con-)6 1466( heuristic achieves its performance by improving the)7 2316( The)1 227([9, 10].)1 311 4 720 5028 t +( game trees, the same branch, or)6 1450( In)1 153(sidered at interior nodes.)3 1104 3 720 5268 t +10 I f +(move)3458 5268 w +11 R f +(, will occur many times at dif-)6 1372 1 3668 5268 t +(ferent nodes, or)2 703 1 720 5508 t +10 I f +(positions)1457 5508 w +11 R f +( move is in leading to)5 993( history is maintained of how successful each)7 2056(. A)1 172 3 1819 5508 t +( every different)2 684( information is maintained for)4 1336( This)1 256(the highest minimax score at an interior node.)7 2044 4 720 5748 t +( in)1 115( interior nodes of the tree, moves are examined)8 2080( At)1 168(move, regardless of the originating position.)5 1957 4 720 5988 t +( information is accumulated)3 1233( this manner, previous search)4 1284( In)1 147(order of their prior history of success.)6 1656 4 720 6228 t +(and distributed throughout the tree.)4 1549 1 720 6468 t +( heuristic and)2 608(A series of experiments is reported that assess the performance of the history)12 3462 2 970 6744 t +(the prominent)1 620 1 720 6984 t +11 S f +(ab)1374 6984 w +11 R f +( experiments consisted of trying all possible combi-)7 2312( The)1 231(search enhancements.)1 959 3 1538 6984 t +( The)1 243(nations of enhancements in a chess program to find out which provides the best results.)14 4077 2 720 7224 t +cleartomark +showpage +saveobj restore +%%EndPage: 2 2 +%%Page: 3 3 +/saveobj save def +mark +3 pagesetup +11 R f +(- 3 -)2 183 1 2788 490 t +( each of these enhancements is quantified, providing evidence)8 2722(reductions in tree size achievable by)5 1598 2 720 840 t +( is the first comprehensive test performed in this area; previous)10 2951( This)1 270(of their \(in\)significance.)2 1099 3 720 1080 t +( into account)2 568( this work takes)3 697( Further,)1 408( 7, 8].)2 238(work has been limited to a few select combinations [1,)9 2409 5 720 1320 t +( nodes, something not addressed by previous)6 1983(the effect on tree size of ordering branches at interior)9 2337 2 720 1560 t +(work.)720 1800 w +( with transposition tables provides more)5 1769(The results show that the history heuristic combined)7 2301 2 970 2076 t +(than 99% of the possible reductions in tree size; the others combining for an insignificant)14 4320 1 720 2316 t +( a simple, mechanical way to order branches at interior)9 2570( history heuristic is)3 893(improvement. The)1 857 3 720 2556 t +( time and space overheads of the)6 1456( has none of the implementation, debugging, execution)7 2452(nodes. It)1 412 3 720 2796 t +( of using explicit knowledge, the heuristic uses the implicit)9 2618( Instead)1 374(knowledge-based alternatives.)1 1328 3 720 3036 t +( gives rise)2 456( This)1 257( the tree.)2 391(knowledge of the "experience" it has gained from visiting other parts of)11 3216 4 720 3276 t +( knowledge is better in that an application dependent knowledge-)9 2892(to the apparent paradox that less)5 1428 2 720 3516 t +(based ordering method can be approximated by the history heuristic.)9 3015 1 720 3756 t +11 B f +(2.)720 4116 w +11 S f +(ab)859 4116 w +11 B f +(and its Enhancements)2 1036 1 1017 4116 t +11 R f +(An)970 4392 w +10 I f +(adversary)1135 4392 w +11 R f +(or)1569 4392 w +10 I f +(game)1692 4392 w +11 R f +( types)1 267( Two)1 264(tree is one in which two players alternate making moves.)9 2566 3 1943 4392 t +( at the bottom of the tree are called)8 1555( Nodes)1 339(of nodes in the tree are distinguished.)6 1670 3 720 4632 t +10 I f +(lea f)1 166 1 4312 4632 t +11 R f +(nodes while)1 531 1 4509 4632 t +(those with successors are)3 1118 1 720 4872 t +10 I f +(interior)1867 4872 w +11 R f +( may be referred to as a)6 1058( interior or leaf node)4 918(nodes. An)1 478 3 2205 4872 t +10 I f +(position)4689 4872 w +11 R f +(.)5012 4872 w +(An)720 5112 w +10 I f +(evaluator)882 5112 w +11 R f +( A)1 137( leaf nodes to assign a score measuring the merit of the position.)12 2850(is used at)2 416 3 1296 5112 t +10 I f +(move)4726 5112 w +11 R f +(is)4966 5112 w +(the operation by which a position is transformed into a successor position.)11 3264 1 720 5352 t +( subtree,)1 384(For each)1 391 2 970 5628 t +11 S f +(ab)1785 5628 w +11 R f +(maintains lower \()2 793 1 1955 5628 t +11 S f +(a)2748 5628 w +11 R f +(\) and upper \()3 599 1 2817 5628 t +11 S f +(b)3416 5628 w +11 R f +(\) bounds on the range of minimax)6 1563 1 3477 5628 t +( can be)2 322(values that)1 480 2 720 5868 t +11 I f +(backed-up)1556 5868 w +11 R f +( benefits of the algo-)4 933( The)1 232(to affect the value at the root of the root.)9 1830 3 2045 5868 t +( proven their value must lie)5 1222(rithm come from the elimination of sub-trees without search once it is)11 3098 2 720 6108 t +(outside the)1 481 1 720 6348 t +11 S f +(ab)1230 6348 w +11 R f +( eliminated in this manner are said to be)8 1768( Sub-trees)1 471(search window.)1 689 3 1389 6348 t +11 I f +(cutoff.)4346 6348 w +11 S f +(ab)4681 6348 w +11 R f +(does)4839 6348 w +( the optimal case, for)4 957( In)1 155( growth of the trees; it merely dampens it.)8 1907(not eliminate the exponential)3 1301 4 720 6588 t +(uniform trees of depth)3 994 1 720 6839 t +10 I f +(d)1744 6839 w +11 R f +(\(or)1827 6839 w +10 I f +(d ply)1 202 1 1984 6839 t +11 R f +( branching factor)2 756(\) and)1 227 2 2186 6839 t +10 I f +(w)3198 6839 w +11 R f +(,)3265 6839 w +10 I f +(w)3322 6839 w +7 S f +(\351)3405 6791 w +7 I f +(d /)1 60 1 3440 6782 t +7 R f +(2)3505 6782 w +7 S f +(\371)3540 6791 w +10 S f +(+)3624 6839 w +10 I f +(w)3728 6839 w +7 S f +(\353)3811 6791 w +7 I f +(d /)1 60 1 3846 6782 t +7 R f +(2)3911 6782 w +7 S f +(\373)3946 6791 w +10 S f +(-)4030 6839 w +10 R f +(1)4134 6839 w +11 R f +(leaf nodes need be)3 824 1 4216 6839 t +( the worst case,)3 689( In)1 151(considered [11].)1 716 3 720 7079 t +11 S f +(ab)2309 7079 w +11 R f +(becomes a full minimax search, evaluating)5 1904 1 2472 7079 t +10 I f +(w)4406 7079 w +7 I f +(d)4484 7039 w +11 R f +(leaf nodes.)1 480 1 4560 7079 t +( moves are examined at interior nodes.)6 1855(The size of the tree depends on the order in which)10 2465 2 720 7319 t +cleartomark +showpage +saveobj restore +%%EndPage: 3 3 +%%Page: 4 4 +/saveobj save def +mark +4 pagesetup +11 R f +(- 4 -)2 183 1 2788 490 t +( interior node in the tree pro-)6 1281(Considering the move producing the best minimax score first at each)10 3039 2 720 840 t +(duces the)1 411 1 720 1080 t +10 I f +(minimal)1156 1080 w +11 R f +(or)1512 1080 w +10 I f +(optimally)1628 1080 w +11 R f +(-)2006 1080 w +10 I f +(ordered)2042 1080 w +11 S f +(ab)2386 1080 w +11 R f +(tree.)2544 1080 w +(Many enhancements to)2 1022 1 970 1356 t +11 S f +(ab)2022 1356 w +11 R f +( are usually based on)4 933( They)1 284( in the literature.)3 736(have been suggested)2 905 4 2182 1356 t +(one or more of the following principals:)6 1759 1 720 1596 t +(1\))720 1872 w +11 I f +(ordering)839 1872 w +11 R f +(, improving the order in which moves are examined at interior nodes ,)12 3072 1 1224 1872 t +(2\))720 2148 w +11 I f +(window size)1 540 1 842 2148 t +11 R f +( window \(absolute difference between)4 1689(, the smaller the search)4 1021 2 1382 2148 t +11 S f +(a)4124 2148 w +11 R f +(and)4225 2148 w +11 S f +(b)4415 2148 w +11 R f +(\), the greater)2 564 1 4476 2148 t +(the chance for a cutoff to occur, and)7 1582 1 720 2388 t +(3\))720 2664 w +11 I f +(re-using information)1 927 1 851 2664 t +11 R f +(, saving the results of sub-trees examined in the event that this sub-tree)12 3262 1 1778 2664 t +(re-appears at a later time.)4 1110 1 720 2904 t +(Following is a brief discussion of the major)7 1918 1 720 3180 t +11 S f +(ab)2666 3180 w +11 R f +(enhancements used in practice.)3 1364 1 2824 3180 t +11 B f +(A\) Iterative deepening)2 1079 1 720 3576 t +11 R f +( used to increase the probability that the best)8 2089( technique is)2 586( This)1 267([1, 8].)1 256 4 1842 3576 t +( series of staged searches are carried out to succes-)9 2232( A)1 136(move is searched first at the root of the tree.)9 1952 3 720 3816 t +(sively larger search depths, using the best move found for a)10 2655 1 720 4056 t +10 I f +(d)3404 4056 w +10 S f +(-)3478 4056 w +10 R f +(1)3549 4056 w +11 R f +( first examined)2 669(ply search as the)3 740 2 3631 4056 t +(in a)1 174 1 720 4296 t +10 I f +(d)931 4296 w +11 R f +( gained in the)3 629( the search progresses deeper, more and more confidence is)9 2713( As)1 190(ply search.)1 487 4 1021 4296 t +( cost of an iteration is strongly influenced by the branching factor)11 2977( The)1 235(best move.)1 486 3 720 4536 t +10 I f +(w)4452 4536 w +11 R f +( chess)1 275(. For)1 246 2 4519 4536 t +(programs \(with)1 675 1 720 4776 t +10 I f +(w)1421 4776 w +11 R f +( odd depth is about 8)5 922(typically around 35\), the cost of iterating an extra ply to an)11 2601 2 1517 4776 t +( 3 times \(a consequence of)5 1197(times the cost of the previous search, whereas to an even depth, about)12 3123 2 720 5016 t +(the)720 5256 w +10 S f +(\353 \373)1 113 1 893 5269 t +11 R f +(and)1040 5256 w +10 S f +(\351 \371)1 113 1 1237 5269 t +11 R f +( the cost of performing iterations)5 1474( Thus)1 282(operators in the minimal tree formula\) [1].)6 1900 3 1384 5256 t +(to)720 5501 w +10 R f +( ,)1 33( 2)1 91(1 ,)1 83 3 834 5501 t +(. . .)2 125 1 1107 5476 t +(,)1298 5501 w +10 I f +(d)1364 5501 w +10 S f +(-)1438 5501 w +10 R f +(1)1509 5501 w +11 R f +( that the best move)4 848(ply is only a small price to pay for having high confidence)11 2602 2 1590 5501 t +(is being searched first for the larger)6 1559 1 720 5741 t +10 I f +(d)2304 5741 w +11 R f +(ply search.)1 475 1 2382 5741 t +( in a tourna-)3 546(Iterative deepening is useful when the search is constrained by time \(as, for example,)13 3774 2 720 6017 t +( any point, the search can be terminated with the best move \(to that point\) known.)15 3596( At)1 166(ment game\).)1 549 3 720 6257 t +11 B f +(B\) Transposition tables)2 1106 1 720 6533 t +11 R f +( trees are not necessarily distinct; it may)7 1803( nodes of game)3 680( Interior)1 388([2, 12].)1 311 4 1858 6533 t +( tables take advantage of this)5 1277( These)1 318( more than one path.)4 905(be possible to reach the same position by)7 1820 4 720 6773 t +( searched in the event that the identical position)8 2247(by recording information about each sub-tree)5 2073 2 720 7013 t +( move that leads)3 724( information saved would include the value of the sub-tree, the)10 2786( The)1 229(occurs again.)1 581 4 720 7253 t +cleartomark +showpage +saveobj restore +%%EndPage: 4 4 +%%Page: 5 5 +/saveobj save def +mark +5 pagesetup +11 R f +(- 5 -)2 183 1 2788 490 t +( searching a new sub-tree, the)5 1328( Before)1 358( which the tree was searched.)5 1309(to this value, and the depth to)6 1325 4 720 840 t +( so, depending on)3 777( If)1 128( the current node.)3 768(table is interrogated to see if there is information relevant to)10 2647 4 720 1080 t +(the quality of the information found, the entire sub-tree may not need to be searched.)14 3729 1 720 1320 t +( and it was previously)4 1046( the position is found in the table)7 1582( If)1 147(The tables are used in two ways.)6 1545 4 720 1596 t +( for the sub-tree can be retrieved from the)8 1922(searched to at least the desired depth, then the value)9 2398 2 720 1836 t +( trees)1 245( that this has the potential for building)7 1751(table. Note)1 520 3 720 2076 t +11 I f +(smaller)3275 2076 w +11 R f +(than the minimal game tree by)5 1396 1 3644 2076 t +( the information is not as reliable as)7 1728( If)1 150( without performing any search.)4 1494(eliminating sub-trees)1 948 4 720 2316 t +(desired \(was not previously searched deep enough\) the best move from the previous search can be)15 4320 1 720 2556 t +( a shallower search\) there is a high pro-)8 1754( this move was previously best \(albeit for)7 1846(retrieved. Since)1 720 3 720 2796 t +( transposition tables)2 907( Thus)1 289( tried first.)2 488(bability it is also best for the current depth and should be)11 2636 4 720 3036 t +(allow for the reuse of information and help improve ordering.)9 2709 1 720 3276 t +( the)1 170( As)1 186( are typically implemented as a hash table.)7 1924(To minimize access time, transposition tables)5 2040 4 720 3552 t +( reducing their effectiveness.)3 1278(table becomes full, collisions occur and information lost, potentially)8 3042 2 720 3792 t +(As a consequence, the tables are usually as large as possible.)10 2665 1 720 4032 t +11 B f +(C\) Refutation tables)2 946 1 720 4308 t +11 R f +( Refutation)1 521( is their size.)3 560( major disadvantage of transposition tables)5 1884([3]. The)1 381 4 1694 4308 t +( the advantages of transposition tables, when used with iterative)9 2935(tables attempt to retain one of)5 1385 2 720 4548 t +( each iteration, the search yields a path for)8 1864( For)1 210( memory requirements.)2 1024(deepening, but with smaller)3 1222 4 720 4788 t +( to a leaf node that results in either the correct minimax score or an upper)15 3233(each move from the root)4 1087 2 720 5028 t +( path from the)3 623( This)1 253(bound on its value.)3 842 3 720 5268 t +10 I f +(d)2464 5268 w +10 S f +(-)2538 5268 w +10 R f +(1)2609 5268 w +11 R f +(ply search can be used as the basis for the search to)11 2274 1 2689 5268 t +10 I f +(d)4990 5268 w +11 R f +( iteration's path or)3 857( searching the previous)3 1066(ply. Often,)1 519 3 720 5508 t +11 I f +(refutation)3206 5508 w +11 R f +(for a move as the initial path)6 1355 1 3685 5508 t +(examined for the current iteration will prove sufficient to refute the move one ply deeper.)14 3924 1 720 5748 t +11 B f +(D\) Minimal window)2 987 1 720 6024 t +11 R f +( window searching is a variant of)6 1590( Minimal)1 458([4, 8, 13].)2 412 3 1757 6024 t +11 S f +(ab)4267 6024 w +11 R f +(based on the)2 593 1 4447 6024 t +( remaining moves are inferior until pro-)6 1775(assumption that the first move considered is best and the)9 2545 2 720 6264 t +( that the first branch has been searched with a full win-)11 2467( an interior node, given)4 1039( At)1 170(ven otherwise.)1 644 4 720 6504 t +(dow \()1 256 1 720 6744 t +11 S f +(a)976 6744 w +11 R f +(,)1045 6744 w +11 S f +(b)1104 6744 w +11 R f +(\) and produced a value)4 1010 1 1165 6744 t +10 I f +(v)2203 6744 w +11 R f +( moves are searched with the)5 1280(inside the window, the remaining)4 1482 2 2278 6744 t +(minimal window \()2 830 1 720 6984 t +10 I f +(v)1550 6984 w +10 R f +(,)1602 6984 w +10 I f +(v)1635 6984 w +10 S f +(+)1703 6984 w +10 R f +(1)1774 6984 w +11 R f +( win-)1 238( motivation for minimal window searching is that a smaller)9 2680(\). The)1 298 3 1824 6984 t +( minimal window searching is a probabilistic gamble)7 2416( Essentially,)1 579( smaller tree.)2 594(dow generates a)2 731 4 720 7224 t +cleartomark +showpage +saveobj restore +%%EndPage: 5 5 +%%Page: 6 6 +/saveobj save def +mark +6 pagesetup +11 R f +(- 6 -)2 183 1 2788 490 t +( the gamble proves incorrect,)4 1333( If)1 142(that most moves can be shown to be inferior with little effort.)11 2845 3 720 840 t +( a re-search \(to encompass the range of values \()9 2156(then additional work is required to do)6 1710 2 720 1080 t +10 I f +(v)4586 1080 w +10 S f +(+)4654 1080 w +10 R f +(1 ,)1 83 1 4725 1080 t +10 S f +(b)4849 1080 w +11 R f +(\) \).)1 136 1 4904 1080 t +(At a node with)3 654 1 720 1320 t +10 I f +(w)1400 1320 w +11 R f +(successors,)1496 1320 w +11 S f +(ab)2015 1320 w +11 R f +(only recognizes only one best move, which implies)7 2269 1 2174 1320 t +10 I f +(w)4470 1320 w +10 S f +(-)4561 1320 w +10 R f +(1)4632 1320 w +11 R f +(inferior)4712 1320 w +(ones.)720 1560 w +11 B f +(E\) Aspiration search)2 972 1 720 1836 t +11 R f +( The)1 226([5, 14].)1 311 2 1720 1836 t +11 S f +(ab)2285 1836 w +11 R f +(search is usually started with a)5 1346 1 2443 1836 t +10 R f +(\()3814 1836 w +10 S f +(- \245)1 144 1 3863 1836 t +10 R f +(,)4015 1836 w +10 S f +(\245)4081 1836 w +10 R f +(\))4162 1836 w +11 R f +( If)1 129(search window.)1 688 2 4223 1836 t +( of the search will fall is available, then tighter bounds)10 2442(some idea of the range in which the value)8 1878 2 720 2076 t +( involves using a smaller initial search)6 1783( search)1 321( Aspiration)1 535(can be placed on the initial window.)6 1681 4 720 2316 t +( Other-)1 353( value falls within the window, then the original window was adequate.)11 3269( the)1 175(window. If)1 523 4 720 2556 t +(wise, one must re-search with a wider window.)7 2071 1 720 2796 t +11 B f +(F\) Killer Heuristic)2 915 1 720 3072 t +11 R f +( quickly)1 383( during a search, most moves tried in a position are)10 2486([3]. Often)1 484 3 1687 3072 t +( killer heuristic involves remembering at each depth of)8 2492( The)1 237(refuted, usually by the same move.)5 1591 3 720 3312 t +( next time the same)4 864( The)1 228( most cutoffs \("killers"\).)3 1074(search the move\(s\) which seem to be causing the)8 2154 4 720 3552 t +(depth in the tree is reached, the killer move is retrieved and used, if valid in the current position.)18 4230 1 720 3792 t +( a dramatic effect on tree size, it is)8 1565(Since searching the best move first at interior nodes has)9 2505 2 970 4224 t +( ordering usually)2 761( resources to achieving this)4 1232( Devoting)1 474(important to have a good move ordering.)6 1853 4 720 4464 t +( or refutation table can be used, they help order the)10 2285( positions where the transposition)4 1496( In)1 151(pays off.)1 388 4 720 4704 t +( information acquired from previ-)4 1497(moves by suggesting a likely candidate for best move based on)10 2823 2 720 4944 t +( any information on)3 883( they don't tell how to order the remaining moves, nor give)11 2637( But)1 219(ous searches.)1 581 4 720 5184 t +( method used by most game)5 1273( The)1 234( at nodes where the tables provide no clues.)8 1977(how to order them)3 836 4 720 5424 t +( to apply application dependent heuristic knowledge to each move indicating)10 3436(playing programs is)2 884 2 720 5664 t +( course, any ordering)3 941( Of)1 176( and sort based on these assessments.)6 1664(how good the move is likely to be)7 1539 4 720 5904 t +(is probabilistic guessing since the desirability of a move usually cannot be reliably determined)13 4320 1 720 6144 t +( the knowledge used, this approach)5 1554( on the quality of)4 765( Depending)1 540(without performing some search.)3 1461 4 720 6384 t +(is usually superior to a random ordering.)6 1787 1 720 6624 t +(Several studies have been performed investigating how close)7 2764 1 970 6900 t +11 S f +(ab)3774 6900 w +11 R f +(search with its enhance-)3 1095 1 3945 6900 t +( and Marsland [6] have investigated this)6 1770( Campbell)1 485( tree.)1 220(ments can come to achieving the minimal)6 1845 4 720 7140 t +cleartomark +showpage +saveobj restore +%%EndPage: 6 6 +%%Page: 7 7 +/saveobj save def +mark +7 pagesetup +11 R f +(- 7 -)2 183 1 2788 490 t +( experimented)1 631( 8])1 109(question using artificially-constructed trees, while Gillogly [1] and Marsland [7,)9 3580 3 720 840 t +( experiments considered trees of depths 2 through 6 ply [8].)10 2722( Marsland's)1 559( program.)1 437(using a chess)2 602 4 720 1080 t +(For even depths, the results showed that)6 1775 1 720 1320 t +11 S f +(ab)2526 1320 w +11 R f +(, enhanced with minimal window searching \(the Prin-)7 2384 1 2656 1320 t +( build trees)2 503(cipal Variation Search algorithm\) and refutation and transposition tables, was able to)11 3817 2 720 1560 t +( The)1 227( 1.5.)1 195( odd depths, this was reduced to a factor of)9 1886( For)1 209(within twice the size of the minimal tree.)7 1803 5 720 1800 t +(factor of 2 for even depths is roughly the same as in Campbell and Marsland [6], but these results)18 4320 1 720 2040 t +(were achieved)1 643 1 720 2280 t +11 I f +(without)1408 2280 w +11 R f +( illustrates the danger of)4 1130( This)1 269(using transposition and refutation tables.)4 1856 3 1785 2280 t +( gen-)1 229(using results from artificially-constructed trees as a guideline for how to search application)12 4091 2 720 2520 t +( refutation)1 476( study also showed that for shallow searches, the performance of)10 3048( The)1 247(erated trees.)1 549 4 720 2760 t +( comparable to that of transposition tables, but as the search depth increased, refutation)13 3862(tables was)1 458 2 720 3000 t +(tables out-performed transposition tables \(probably because of transposition table over-loading\).)9 4233 1 720 3240 t +( is usu-)2 321(A variety of studies have been performed demonstrating that minimal window search)11 3749 2 970 3516 t +(ally superior to just)3 866 1 720 3756 t +11 S f +(ab)1618 3756 w +11 R f +( artificially constructed game trees)4 1529( advantage is more pronounced in)5 1505(. The)1 258 3 1748 3756 t +( where the stronger ordering of moves at inte-)8 2044( 8],)1 137( trees [7,)2 389( than in application generated)4 1311([6, 13, 15])2 439 5 720 3996 t +(rior nodes results in smaller trees.)5 1484 1 720 4236 t +( observed no benefits)3 951( Gillogly)1 429( has been questioned.)3 955(The effectiveness of the killer heuristic)5 1735 4 970 4512 t +( is a)2 206( This)1 266( reductions in tree size - as much as 80% [16].)10 2169([1], whereas Hyatt claims significant)4 1679 4 720 4752 t +(popular)720 4992 w +11 S f +(ab)1083 4992 w +11 R f +(enhancement, yet no one really seems to know how effective it is.)11 2896 1 1241 4992 t +11 B f +( History Heuristic)2 843(3. The)1 323 2 720 5352 t +11 R f +(Using the terminology of Newell and Simon [17], a)8 2375 1 970 5628 t +11 I f +(problem space)1 657 1 3387 5628 t +11 R f +(is a set of)3 461 1 4086 5628 t +11 I f +(states)4589 5628 w +11 R f +(and)4882 5628 w +11 I f +(operators)720 5868 w +11 R f +( state of knowledge, one repeatedly)5 1584( from an initial)3 679( Starting)1 412(that map states into states.)4 1182 4 1183 5868 t +( as parameterized)2 793( can be viewed)3 693( Operators)1 500(applies operators to states, looking for a goal state.)8 2334 4 720 6108 t +( In)1 155( operator should do to the state.)6 1433(functions; the parameters providing the specifics of what the)8 2732 3 720 6348 t +( move operation could)3 1013( The)1 235(the context of game trees, states are positions and moves, operators.)10 3072 3 720 6588 t +( function of three parameters: the initial position and the from-square and to-square)12 3672(be viewed as a)3 648 2 720 6828 t +(of the move, producing a new successor position.)7 2171 1 720 7068 t +cleartomark +showpage +saveobj restore +%%EndPage: 7 7 +%%Page: 8 8 +/saveobj save def +mark +8 pagesetup +11 R f +(- 8 -)2 183 1 2788 490 t +( not unique within the tree:)5 1205(For many types of search trees, the parameters of an operator are)11 2865 2 970 840 t +( history heuristic)2 746( The)1 229( states can have the same operator applied yielding new states.)10 2772(two different)1 573 4 720 1080 t +( a correlation between an operator and any success that)9 2459(maintains information on whether there is)5 1861 2 720 1320 t +( an arbitrary state in the problem space, the history heuris-)10 2560( At)1 166( goal.)1 245(the operator has in achieving a)5 1349 4 720 1560 t +(tic prefers to explore operators with a history of success first.)10 2687 1 720 1800 t +( types of game trees, the making of a move from one position yields a successor)15 3638(For many)1 432 2 970 2076 t +( is quite likely that the impor-)6 1335( It)1 127(position that has many of the same properties as its predecessor.)10 2858 3 720 2316 t +( not significantly)2 755(tant features of the position, the ones that dictate what the good moves are, have)14 3565 2 720 2556 t +( the)1 171( Since)1 309( good in the previous position will still be good.)9 2197(changed and that a move considered)5 1643 4 720 2796 t +( analogies to show the)4 1006(two positions are similar, one could take a sophisticated approach and use)11 3314 2 720 3036 t +( this is an expensive proposition.)5 1445( However,)1 484(similarity \(for example [18]\).)3 1287 3 720 3276 t +( move)1 276( A)1 139(As an example, consider the trees built by chess programs.)9 2615 3 970 3552 t +10 I f +(M)4029 3552 w +11 R f +(may be shown to be)4 896 1 4144 3552 t +( similar position may occur, perhaps only differ-)7 2138( on in the search tree a)6 999( Later)1 288(best in one position.)3 895 4 720 3792 t +( difference may not change the position enough to)8 2299( minor)1 302( This)1 263(ing in the location of one piece.)6 1456 4 720 4032 t +(alter move)1 467 1 720 4272 t +10 I f +(M)1213 4272 w +11 R f +( best.)1 233(from still being)2 682 2 1325 4272 t +10 I f +(M)2290 4272 w +11 R f +(, with its prior history of success, may now be the first move)12 2667 1 2373 4272 t +( improves the ordering of moves, increasing the chances of a cut-)11 2877( This)1 253( this position.)2 602(considered in)1 588 4 720 4512 t +(off occurring.)1 602 1 720 4752 t +(In an)1 222 1 970 5028 t +11 S f +(ab)1220 5028 w +11 R f +(framework, a)1 583 1 1378 5028 t +10 I f +( icient)1 230(su ff)1 161 2 1986 5028 t +11 R f +(\(or good\) move at an interior node is defined as one that)11 2469 1 2405 5028 t +( a cutoff, or)3 512(1\) causes)1 535 2 720 5304 t +( no cutoff occurs, the one yielding the best minimax score.)10 2578(2\) if)1 317 2 720 5580 t +(Note that this does not imply that a)7 1547 1 720 5856 t +10 I f +( icient)1 230(su ff)1 161 2 2292 5856 t +11 R f +(move is the)2 508 1 2711 5856 t +10 I f +(best)3244 5856 w +11 R f +( cutoff was)2 489( move causing a)3 711(move. A)1 407 3 3433 5856 t +10 I f +( icient)1 230(su ff)1 161 2 720 6096 t +11 R f +( at that node, but there is no guarantee that had the search con-)13 2745(to cause the search to stop)5 1155 2 1140 6096 t +(tinued, a better \(but irrelevant\) score might have been obtained by a latter move.)13 3529 1 720 6336 t +(Every time a)2 615 1 970 6612 t +10 I f +( icient)1 230(su ff)1 161 2 1637 6612 t +11 R f +( score associated with that move is)6 1695(move is found, the history)4 1262 2 2083 6612 t +( reaching an inte-)3 770( Upon)1 302( scores.)1 331( that are consistently good quickly achieve high)7 2119(increased. Moves)1 798 5 720 6852 t +( a ran-)2 289( than using)2 492( Rather)1 352(rior node, moves are ordered according to their prior history of success.)11 3187 4 720 7092 t +cleartomark +showpage +saveobj restore +%%EndPage: 8 8 +%%Page: 9 9 +/saveobj save def +mark +9 pagesetup +11 R f +(- 9 -)2 183 1 2788 490 t +( in, a move's prior)4 854(dom or knowledge-based approach for deciding the order to consider moves)10 3466 2 720 840 t +( experienced-based, acquir-)2 1209( heuristic is)2 510( The)1 227(history of success can be used as the ordering criteria.)9 2374 4 720 1080 t +( In)1 156( future.)1 326(ing information on what has been seen as an indication of what will be useful in the)16 3838 3 720 1320 t +( This)1 253( tree.)1 220(effect, previous search information is being accumulated and distributed throughout the)10 3847 3 720 1560 t +( is)1 112(implies that the heuristic)3 1119 2 720 1800 t +10 I f +(dynamic)1986 1800 w +11 R f +(; the ordering of branches being adaptive to previous condi-)9 2716 1 2324 1800 t +(tions seen in the search tree.)5 1238 1 720 2040 t +( illustrates the history heuristic in the)6 1658(Figure 1)1 373 2 970 2316 t +11 S f +(ab)3033 2316 w +11 R f +( lines marked with a * are)6 1159(algorithm. The)1 686 2 3195 2316 t +( the sorting operation is not specific to the)8 1861( that)1 195( Note)1 271(those that differ from the standard algorithm.)6 1993 4 720 2556 t +( requires a)2 464(history heuristic; the usual technique of assigning a heuristic-based score to each move)12 3856 2 720 2796 t +( in some)2 384( some applications avoid the sort by generating moves as needed)10 2905( However,)1 490(sort as well.)2 541 4 720 3036 t +( the heuristic is applied at all interior nodes, since one can never)12 2877( note that)2 418( Also)1 268(reasonable order.)1 757 4 720 3276 t +(tell in advance with certainty whether a cutoff will occur or not.)11 2806 1 720 3516 t +( a)1 95( Assuming)1 522( an example of how the heuristic can affect tree searching.)10 2744(Figure 2 shows)2 709 4 970 3792 t +( tree, at interior node)4 950(depth-first, left to right, traversal of the)6 1776 2 720 4032 t +11 I f +(I1)3482 4032 w +11 R f +(, move)1 308 1 3573 4032 t +11 I f +(M)3917 4032 w +11 R f +(was found to be suffi-)4 996 1 4044 4032 t +( the search, at interior node)5 1270( on in)2 280(cient. Later)1 541 3 720 4272 t +11 I f +(I2,)2854 4272 w +11 R f +(move)3016 4272 w +11 I f +(M)3303 4272 w +11 R f +(was one of the successor branches.)5 1603 1 3437 4272 t +(Given no information, the successors of)5 1762 1 720 4512 t +11 I f +(I2)2512 4512 w +11 R f +( the prior)2 407( With)1 278(would be considered in arbitrary order.)5 1722 3 2633 4512 t +(history of success of)3 936 1 720 4752 t +11 I f +(M,)1696 4752 w +11 R f +( of)1 132(the successors)1 636 2 1855 4752 t +11 I f +(I2)2664 4752 w +11 R f +(are re-ordered, allowing)2 1080 1 2796 4752 t +11 I f +(M)3917 4752 w +11 R f +(to be considered first.)3 991 1 4049 4752 t +(Since nodes)1 532 1 720 4992 t +11 I f +(I1)1284 4992 w +11 R f +(and)1407 4992 w +11 I f +(I2)1597 4992 w +11 R f +( a high probability that)4 1016(are not dis-similar, there is)4 1192 2 1720 4992 t +11 I f +(M)3959 4992 w +11 R f +(will also be sufficient)3 959 1 4081 4992 t +(at)720 5232 w +11 I f +(I2,)827 5232 w +11 R f +(thereby reducing the size of tree traversed.)6 1865 1 974 5232 t +( based on two parameters; the)5 1368(The implementation is)2 1013 2 970 5508 t +10 I f +(mapping)3388 5508 w +11 R f +(of moves to history and the)5 1262 1 3778 5508 t +10 I f +(weight)720 5748 w +11 R f +(of a)1 177 1 1025 5748 t +10 I f +( icient)1 230(su ff)1 161 2 1237 5748 t +11 R f +(move. The)1 508 1 1666 5748 t +10 I f +(mapping)2209 5748 w +11 R f +( was to specify a move as a)7 1262(used in the chess program)4 1181 2 2597 5748 t +( the)1 173( Essentially,)1 578(12-bit number \(6-bits from-square, 6-bits to-square\).)5 2364 3 720 5988 t +10 I f +(mapping)3871 5988 w +11 R f +( viewed as)2 487(can be)1 293 2 4260 5988 t +( this simplistic representation hides a lot of the)8 2160( Although)1 485( to the move operator.)4 1020(the parameters)1 655 4 720 6228 t +( it allows for compact)4 963(move details in the operator \(for example, which piece is making the move\),)12 3357 2 720 6468 t +(tables \()1 323 1 720 6708 t +10 R f +(2)1043 6708 w +7 R f +(12)1098 6668 w +11 R f +( more context information \(for example, the)6 1943( Including)1 479( are easily accessed.)3 887(entries\) that)1 524 4 1207 6708 t +( performance \(for a complete discussion, see [9]\).)7 2303(piece moving\) did not significantly increase)5 2017 2 720 6948 t +( to the extreme, the result is a transposition)8 1981(Note that if you carry the idea of including context)9 2339 2 720 7188 t +cleartomark +showpage +saveobj restore +%%EndPage: 9 9 +%%Page: 10 10 +/saveobj save def +mark +10 pagesetup +11 R f +(- 10 -)2 238 1 2761 490 t +(table.)720 840 w +(What should be the history)4 1198 1 970 1116 t +10 I f +(weight)2196 1116 w +11 R f +(of a)1 170 1 2494 1116 t +10 I f +( icient)1 230(su ff)1 161 2 2692 1116 t +11 R f +( are two considerations: First,)4 1321(move? There)1 605 2 3114 1116 t +( sub-tree searched, the more reliable the minimax value \(except in)10 3068(the deeper the)2 650 2 720 1356 t +11 I f +(pathological)4483 1356 w +11 R f +( one idea is to associate higher history scores for)9 2241( Therefore,)1 525(trees, rarely seen in practice [19]\).)5 1554 3 720 1596 t +( deeper the search tree \(and)5 1239( the)1 171( Second,)1 416(moves successful on deep rather than shallow searches.)7 2494 4 720 1836 t +( between two arbitrary positions in the tree and the less)10 2514(hence larger\), the greater the differences)5 1806 2 720 2076 t +( sufficient moves near the root of the tree have more potential)11 2744( Hence,)1 365(they may have in common.)4 1211 3 720 2316 t +( considera-)1 491( These)1 325( than sufficient moves near the leaf nodes.)7 1910(for being useful throughout the tree)5 1594 4 720 2556 t +( the usage of a)4 678(tions led)1 389 2 720 2796 t +10 I f +(weight)1823 2796 w +11 R f +(of)2129 2796 w +10 R f +(2)2256 2796 w +7 I f +(depth)2311 2756 w +11 R f +(, where)1 333 1 2475 2796 t +10 I f +(depth)2844 2796 w +11 R f +( This)1 263(is the depth of the sub-tree searched.)6 1672 2 3105 2796 t +(scheme gives more weight to moves that are)7 1957 1 720 3036 t +10 I f +( icient)1 230(su ff)1 161 2 2703 3036 t +11 R f +( those near)2 479(closer to the root of the tree than)7 1438 2 3123 3036 t +( rather than smaller, sub-trees.)4 1389(the leaves of the tree and favors moves that are roots of larger,)12 2931 2 720 3276 t +(Several other)1 590 1 720 3516 t +10 I f +(weights)1344 3516 w +11 R f +(, such as 1 and)4 681 1 1650 3516 t +10 I f +(depth)2365 3516 w +11 R f +( to be experimentally inferior to)5 1451(, were tried and found)4 1002 2 2587 3516 t +10 R f +(2)720 3756 w +7 I f +(depth)775 3716 w +11 R f +(\(for a complete discussion, see [9]\).)5 1570 1 967 3756 t +( the killer)2 424( Whereas)1 438( the killer heuristic is just a special case of the history heuristic.)12 2802(Note that)1 406 4 970 4032 t +( two successful moves per depth of search, the history heuristic)10 2920(heuristic keeps track of one or)5 1400 2 720 4272 t +( heuristic, "killer" moves would)4 1406( the history)2 496( With)1 276(maintains the success for all moves at all depths.)8 2142 4 720 4512 t +( generality of the history mechanism provides valuable ordering)8 2949( The)1 243(earn high history scores.)3 1128 3 720 4752 t +(information at all nodes; not just those with "killer" moves.)9 2613 1 720 4992 t +( nothing particular to the history heuristic that restricts its usage)10 2846(A final point is that there is)6 1224 2 970 5268 t +(to the)1 259 1 720 5508 t +11 S f +(ab)1018 5508 w +11 R f +( types of search algorithms and applications may be able to use this)12 3083(algorithm. Other)1 771 2 1186 5508 t +( suitable \(operators are not unique to)6 1653( success depends on whether the tree type is)8 1981(technique. The)1 686 3 720 5748 t +( values\) and a suitable)4 984(each node and there is a correlation between using an operator and sub-tree)12 3336 2 720 5988 t +10 I f +(mapping)720 6228 w +11 R f +(and)1098 6228 w +10 I f +(weight)1281 6228 w +11 R f +(can be found.)2 594 1 1576 6228 t +11 B f +( Design)1 346(4. Experiment)1 694 2 720 6588 t +11 R f +( various search features, the chess program)6 2094(To assess the importance of)4 1356 2 970 6864 t +10 I f +(Phoenix)4480 6864 w +11 R f +(was)4870 6864 w +( base program that performs)4 1269( with a)2 318( Starting)1 414(enhanced to turn each one on or off selectively.)8 2153 4 720 7104 t +11 S f +(ab)4910 7104 w +cleartomark +showpage +saveobj restore +%%EndPage: 10 10 +%%Page: 11 11 +/saveobj save def +mark +11 pagesetup +11 R f +(- 11 -)2 238 1 2761 490 t +( combi-)1 342(with iterative deepening, a series of experiments was then performed whereby all possible)12 3978 2 720 840 t +( Bratko-Kopec positions [20])3 1306( The)1 233( search features were tried on a test set of positions.)10 2336(nations of)1 445 4 720 1080 t +( benchmarking of sequential and parallel tree search perfor-)8 2736(have been used extensively for the)5 1584 2 720 1320 t +( deepening is necessary to be able to properly)8 2184( Iterative)1 443( 21, 22].)2 348(mance in chess programs [6,)4 1345 4 720 1560 t +(evaluate refutation tables and hence is not one of the experiment parameters.)11 3364 1 720 1800 t +(The search features used were:)4 1348 1 970 2076 t +( Tables \()2 406(1\) Transposition)1 855 2 720 2352 t +10 I f +(T)1981 2352 w +11 R f +( table contained)2 717(\). The)1 301 2 2037 2352 t +10 R f +(2)3091 2352 w +7 R f +(13)3146 2312 w +10 S f +(=)3273 2352 w +10 R f +(8 , 192)2 241 1 3377 2352 t +11 R f +( through 6,)2 505(entries for depths 2)3 878 2 3657 2352 t +(and)970 2592 w +10 R f +(2)1153 2592 w +7 R f +(16)1208 2552 w +10 S f +(=)1335 2592 w +10 R f +(65 , 536)2 291 1 1439 2592 t +11 R f +(for depths 7 and 8 .)5 850 1 1758 2592 t +( Tables \()2 384(2\) Refutation)1 714 2 720 2868 t +10 I f +(R)1818 2868 w +11 R f +(\).)1879 2868 w +( Window Searching \()3 936(3\) Minimal)1 630 2 720 3144 t +10 I f +(N)2286 3144 w +11 R f +( NegaScout variant [13].)3 1079(\). The)1 290 2 2353 3144 t +( Searching \()2 540(4\) Aspiration)1 714 2 720 3420 t +10 I f +(S)1974 3420 w +11 R f +( result of the previous itera-)5 1247(\), using a one pawn window around the)7 1769 2 2024 3420 t +(tion.)970 3660 w +( using the History Heuristic \()5 1281(5\) Ordering)1 645 2 720 3936 t +10 I f +(H)2646 3936 w +11 R f +(\).)2718 3936 w +(A more detailed description of the implementation of each of these can be found in [9].)15 3832 1 720 4212 t +( some)1 266(To assess the history heuristic as a move ordering mechanism, it is necessary to have)14 3804 2 970 4488 t +( search programs apply application dependent heuristics to try and sug-)10 3130( Most)1 283(basis of comparison.)2 907 3 720 4728 t +( often)1 260( course, the heuristics are only guesses; their validity)8 2372( Of)1 177(gest which moves might be good.)5 1511 4 720 4968 t +( first is)2 317( The)1 231( two undesirable properties.)3 1235( approach has)2 614( This)1 258(cannot be ascertained without search.)4 1665 6 720 5208 t +( the board.)2 487(that the knowledge is \(usually\) static; it is unable to adapt to changing conditions on)14 3833 2 720 5448 t +( problems are)2 615( Both)1 280( the knowledge does not handle exceptions well.)7 2194(The second problem is that)4 1231 4 720 5688 t +( real problem is that there is too)7 1523( The)1 243(symptoms of the same problem: inadequate knowledge.)6 2554 3 720 5928 t +( Most)1 288( the designer must make important cost/benefit decisions.)7 2565(much knowledge to draw on and)5 1467 3 720 6168 t +( effective to implement and so the designer draws on)9 2394(of the knowledge one could use is not cost)8 1926 2 720 6408 t +( inte-)1 231( For)1 211( the time and accepts the resulting consequences.)7 2167(the heuristics that are effective 90% of)6 1711 4 720 6648 t +(rior node move ordering, the consequences can be a poor ordering resulting in a larger search tree.)16 4313 1 720 6888 t +(To have a means of comparison for the history heuristic,)9 2538 1 970 7164 t +10 I f +(Phoenix)3539 7164 w +11 R f +(also has a heuristic-based)3 1139 1 3901 7164 t +cleartomark +showpage +saveobj restore +%%EndPage: 11 11 +%%Page: 12 12 +/saveobj save def +mark +12 pagesetup +11 R f +(- 12 -)2 238 1 2761 490 t +( methods used for ordering the)5 1351( The)1 227( \(developed prior to the history heuristic\).)6 1841(ordering mechanism)1 901 4 720 840 t +( most chess programs, although it is probably more sophisticated than most.)11 3410(moves are similar to)3 910 2 720 1080 t +( move ordering method will)4 1241( This)1 255( 8].)1 137( in fact, superior to the ordering mechanisms used in [7,)10 2486(It is,)1 201 5 720 1320 t +(be referred to as the)4 957 1 720 1560 t +10 I f +(knowledge heuristics)1 857 1 1725 1560 t +11 R f +(since the ordering is based on well-known, human-)7 2407 1 2633 1560 t +( an integral value in the range -25)7 1535( heuristics usually give)3 1039( The)1 235(understandable, chess knowledge.)2 1511 4 720 1800 t +( are combined, but the larger)5 1322( used with the history heuristic, the scores)7 1923( When)1 328(to +25.)1 325 4 720 2040 t +10 I f +(H)4655 2040 w +11 R f +(scores)4767 2040 w +( detailed description of the routine can)6 1720( A)1 140( heuristic scores.)2 745(quickly swamp the smaller knowledge)4 1715 4 720 2280 t +( the experiments have another parameter:)5 1811( Thus,)1 304(be found in [9].)3 684 3 720 2520 t +( using Knowledge Heuristics \(K\).)4 1480(6\) Ordering)1 645 2 720 2796 t +(This implies that a program without)5 1627 1 720 3072 t +10 I f +(K)2381 3072 w +11 R f +(or)2485 3072 w +10 I f +(H)2610 3072 w +11 R f +( just searches the)3 777(has no explicit move ordering and)5 1544 2 2719 3072 t +( not a completely random order, since)6 1705( fact, this is)3 533( In)1 155(moves in the order they were generated in.)7 1927 4 720 3312 t +( the absence of a transposition or refuta-)7 1820( In)1 155( some bias in the order moves are generated.)8 2018(there is)1 327 4 720 3552 t +(tion table move, all program variants consider capture moves before non-capture ones.)11 3801 1 720 3792 t +( the killer)2 452(Finally, for comparison purposes, the experiment has been enhanced to include)10 3618 2 970 4068 t +( considerable doubt as to its effectiveness, a controlled experi-)9 2792( there seems to be)4 815(heuristic. Since)1 713 3 720 4308 t +(ment might provide insight into its effective behavior.)7 2379 1 720 4548 t +( Heuristic \(L\).)2 625(7\) Killer)1 506 2 720 4824 t +(Previous experiments with)2 1181 1 970 5136 t +11 S f +(ab)2183 5136 w +11 R f +(enhancements have neglected the issue of interior move ord-)8 2695 1 2345 5136 t +( using a chess program, it is reasonable to)8 1900( since the experiments were performed)5 1746( 8])1 109( [7,)1 156(ering. In)1 409 5 720 5376 t +( reduce)1 320(assume that some application specific knowledge was used to order the moves and thereby)13 4000 2 720 5616 t +( draw from their experiments, since the order-)7 2045( might question the conclusions they)5 1638( One)1 243(tree size.)1 394 4 720 5856 t +(ing will influence tree size, and tree size may influence the effectiveness of some enhancements.)14 4235 1 720 6096 t +(Excluding the killer heuristic, there are 6 parameters resulting in)9 2930 1 970 6372 t +10 R f +(2)3937 6372 w +7 R f +(6)3992 6332 w +10 S f +(=)4084 6372 w +10 R f +(64)4188 6372 w +11 R f +(different sets of)2 712 1 4328 6372 t +( possible combinations were searched to depths of 2, 3, 4, and)11 2736( All)1 198( be tried.)2 390(enhancements that can)2 996 4 720 6612 t +( killer heuristic is just a special case of the history heuristic, only a few of the)16 3576( the)1 172( Since)1 310(5 ply.)1 262 4 720 6852 t +( just to establish the relationship between)6 1900(combinations with it present were tried)5 1794 2 720 7092 t +10 I f +(L)4453 7092 w +11 R f +(and)4551 7092 w +10 I f +(H)4748 7092 w +11 R f +(. To)1 220 1 4820 7092 t +cleartomark +showpage +saveobj restore +%%EndPage: 12 12 +%%Page: 13 13 +/saveobj save def +mark +13 pagesetup +11 R f +(- 13 -)2 238 1 2761 490 t +( with only those combinations that showed signi-)7 2185(depths of 6, 7, and 8 ply, experiments continued)8 2135 2 720 840 t +( total of 2000 hours of VAX 11/780 equivalent time)9 2290( A)1 136(ficant reductions in tree size through 5 ply.)7 1894 3 720 1080 t +(was required to perform the experiments.)5 1810 1 720 1320 t +11 B f +( Results)1 370(5. Experiment)1 694 2 720 1680 t +11 R f +( the)1 170( From)1 303( search algorithm performance is elapsed CPU time.)7 2350(One measure for comparing)3 1247 4 970 1956 t +( timing)1 337( any)1 207( However,)1 505(implementor's point of view, this is the most important consideration.)9 3271 4 720 2196 t +( bottom)1 356( measure is the number of)5 1208( Another)1 429(results are machine and implementation dependent.)5 2327 4 720 2436 t +( in the literature)3 801(positions \(leaf nodes\) examined \(NBP\), which has been used extensively)9 3519 2 720 2676 t +( NBP is an inadequate measure since it treats all leaf nodes equally and)13 3258( However,)1 494([1, 6, 23, 24].)3 568 3 720 2916 t +( most applications, neither is a reason-)6 1737( fact, for)2 392( In)1 156(assumes interior nodes are of negligible cost.)6 2035 4 720 3156 t +( may be a good theoretical measure, but not a good practical one.)12 2862( NBP)1 271(able assumption.)1 740 3 720 3396 t +( in a manner that is corre-)6 1170(A better measure would be one that measures the size of the tree)12 2900 2 970 3672 t +( The)1 245(lated with program running time.)4 1534 2 720 3912 t +11 I f +(node count \(NC\))2 771 1 2546 3912 t +11 R f +(measure counts all nodes in the tree)6 1676 1 3364 3912 t +( of)1 122( includes interior, leaf, and any nodes in sub-trees built as part)11 2755( This)1 254(where computation occurs.)2 1189 4 720 4152 t +( least for)2 410( At)1 179(leaf node evaluation.)2 943 3 720 4392 t +10 I f +(Phoenix)2290 4392 w +11 R f +( be strongly correlated)3 1020(, this count has been shown to)6 1403 2 2617 4392 t +( execution time overhead of most of the)7 1903( that since the)3 671( Note)1 290(with program running time [9].)4 1456 4 720 4632 t +( dominated by leaf node evaluation\),)5 1696(enhancements is negligible \(the cost being)5 1955 2 720 4872 t +10 I f +(NC)4413 4872 w +11 R f +(accurately)4592 4872 w +( exception is the)3 736( The)1 231(reflects the relative running time of the program variants.)8 2556 3 720 5112 t +10 I f +(K)4274 5112 w +11 R f +(heuristic, since)1 665 1 4375 5112 t +( to it as you want.)5 810(you can add as much or as little knowledge)8 1947 2 720 5352 t +10 I f +(NC)3532 5352 w +11 R f +(has the advantage of factoring)4 1341 1 3699 5352 t +( you view the)3 617( If)1 135(this out of the results.)4 981 3 720 5592 t +10 I f +(NC)2485 5592 w +11 R f +( to note that)3 548(graphs as measuring time, it is important)6 1838 2 2654 5592 t +10 I f +(K)720 5832 w +11 R f +( it added an additional 5% on to the execution)9 2092('s relative time performance is over-stated since)6 2161 2 787 5832 t +( this paper, both the NBP and NC measures will be used.)11 2505(time. In)1 371 2 720 6072 t +( combination of search enhancements would be to)7 2227(The best measure of the performance of a)7 1843 2 970 6348 t +( to know the size)4 754( it is difficult)3 583( Unfortunately,)1 702(compare its tree sizes with that of the minimal tree.)9 2281 4 720 6588 t +( in the tree)3 470(of the minimal tree, due to the variable branching factor and presence of terminal nodes)14 3850 2 720 6828 t +( good method for approximating the minimal tree [25]\).)8 2501(\(although Ebeling has recently devised a)5 1819 2 720 7068 t +( improvement in search efficiency as)5 1712(Instead, performance will be measured as the percentage)7 2608 2 720 7308 t +cleartomark +showpage +saveobj restore +%%EndPage: 13 13 +%%Page: 14 14 +/saveobj save def +mark +14 pagesetup +11 R f +(- 14 -)2 238 1 2761 490 t +( all possi-)2 429( each depth,)2 529( For)1 210(compared to that achievable by the best combination of search features.)10 3152 4 720 840 t +( best result \(using the)4 954(ble combinations of enhancements were tried, with the one giving the)10 3082 2 720 1080 t +10 I f +(NC)4784 1080 w +11 R f +(or)4949 1080 w +10 I f +(NBP)720 1320 w +11 R f +(measure\) being labeled)2 1018 1 938 1320 t +10 I f +(N)1982 1320 w +7 I f +(best)2060 1340 w +11 R f +( program was also run with none of the enhancements \(just)10 2604(. The)1 255 2 2181 1320 t +11 S f +(ab)720 1560 w +11 R f +(with iterative deepening\) yielding)3 1525 1 891 1560 t +10 I f +(N)2454 1560 w +7 I f +(none)2532 1580 w +11 R f +( a given combination of enhancements)5 1758(. For)1 250 2 2676 1560 t +10 I f +(enh)4722 1560 w +11 R f +(, its)1 174 1 4866 1560 t +( of the reduction in tree size from)7 1530(percentage improvements reflects how much)4 2007 2 720 1800 t +10 I f +(N)4291 1800 w +7 I f +(none)4369 1820 w +11 R f +(to)4550 1800 w +10 I f +(N)4670 1800 w +7 I f +(best)4748 1820 w +11 R f +(the)4906 1800 w +(presence of)1 500 1 720 2040 t +10 I f +(enh)1245 2040 w +11 R f +( calculation is done using the formula:)6 1687(achieved. The)1 642 2 1417 2040 t +10 I f +(reduction)2096 2400 w +7 I f +(enh)2490 2420 w +10 S f +(=)2648 2400 w +10 I f +(N)2779 2470 w +7 I f +(none)2857 2490 w +10 S f +(-)3050 2470 w +10 I f +(N)3154 2470 w +7 I f +(best)3232 2490 w +10 I f +(N)2785 2320 w +7 I f +(none)2863 2340 w +10 S f +(-)3056 2320 w +10 I f +(N)3160 2320 w +7 I f +(enh)3238 2340 w +10 S1 f +(_ ____________)1 609 1 2762 2370 t +10 I f +(*)3422 2400 w +10 R f +(100)3513 2400 w +11 R f +( to the addition of a single search)7 1485(Figure 3 shows the percentage reduction in tree size attributable)9 2835 2 720 2686 t +( 4 shows all the combinations)5 1337( Figure)1 349( ply using NBP as a measure.)6 1336( - 8)2 147(enhancement for depths 3)3 1151 5 720 2926 t +(of two enhancements that exceed a 70% reduction.)7 2230 1 720 3166 t +( after)1 235(Figure 3 shows that history heuristic performs well, but its efficiency appears to drop)13 3835 2 970 3442 t +( knowledge heuristic's performance runs almost parallel to)7 2603( The)1 229(depth 7.)1 358 3 720 3682 t +10 I f +(H)3937 3682 w +11 R f +(, albeit with less search)4 1031 1 4009 3682 t +(efficiency. The effectiveness of transposition tables, on the other hand, increases with search)12 4320 1 720 3922 t +( constant performance, regardless of depth, and appear to)8 2509( tables seem to provide)4 1018(depth. Refutation)1 793 3 720 4162 t +( minimal window search provide)4 1531( and)1 206( Aspiration)1 540(be a poor substitute for transposition tables.)6 2043 4 720 4402 t +( 4\), the combination of transposition tables and)7 2150( two enhancements \(Figure)3 1228( With)1 288(small benefits.)1 654 4 720 4642 t +( transposition)1 601( Since)1 304( of the possible reduction in tree size.)7 1671(the history heuristic achieves over 99%)5 1744 4 720 4882 t +( type of search reduction than the history heuristic \(eliminating sub-trees)10 3212(tables provide a different)3 1108 2 720 5122 t +( limited move ordering, versus more comprehensive move ordering\),)8 3035(without search and providing)3 1285 2 720 5362 t +( of these two features indi-)5 1204( performance)1 586( The)1 233(it is not surprising that the two work well together.)9 2297 4 720 5602 t +( Com-)1 311(cates that the other enhancements can provide at most a small percentage of improvement.)13 4009 2 720 5842 t +(bining three or more enhancements does not change this observation \(details can be found in [9]\).)15 4289 1 720 6082 t +(Figures 5 and 6 present the same data using the)9 2116 1 970 6358 t +10 I f +(NC)3115 6358 w +11 R f +(measure and provide a better indication)5 1759 1 3281 6358 t +( and history)2 560( this measure, transposition tables)4 1573( Using)1 340(of how tree size effects execution time.)6 1847 4 720 6598 t +( the search towards)3 873( methods have the advantage of steering)6 1816( Both)1 280(heuristic show up even better.)4 1351 4 720 6838 t +(previously encountered parts of the tree, thereby increasing the computations that can be re-used.)13 4264 1 720 7078 t +cleartomark +showpage +saveobj restore +%%EndPage: 14 14 +%%Page: 15 15 +/saveobj save def +mark +15 pagesetup +11 R f +(- 15 -)2 238 1 2761 490 t +( to oscillate with)3 777(In both Figures 4 and 6, the performance of some enhancements appear)11 3293 2 970 840 t +( mentioned)1 498( As)1 184( to the odd/even depth of the alpha-beta search.)8 2124( is largely attributable)3 983(depth. This)1 531 5 720 1080 t +( to an odd depth is greater)6 1178(in section 2, the incremental cost of growing the tree an additional ply)12 3142 2 720 1320 t +( some combinations of enhancements are tied to search depth, it)10 2941( Since)1 314(than for an even depth.)4 1065 3 720 1560 t +( could)1 278( One)1 244(suggests that a different method for representing the data might be more informative.)12 3798 3 720 1800 t +( depth results, but given the paucity of depths for which results)11 2857(separately plot the odd and even)5 1463 2 720 2040 t +(are available, this was not done.)5 1407 1 720 2280 t +( 8 ply, the percentage improvement attributable to the history heuristic decreases)11 3622(From 7 to)2 448 2 970 2556 t +(\(although significantly less for)3 1356 1 720 2796 t +10 I f +(NC)2104 2796 w +11 R f +(than)2269 2796 w +10 I f +(NBP)2486 2796 w +11 R f +( first is that the)4 670( The)1 228( are two reasons for this.)5 1090(\). There)1 377 4 2675 2796 t +( before, its per-)3 691(trees are getting so large that, although the history heuristic is just as effective as)14 3629 2 720 3036 t +( that the percentage reduction is relative)6 1785( Recall)1 341( seems poorer.)2 647(formance relative to the larger tree)5 1547 4 720 3276 t +( enhancement starts to perform well \(in this case, the tran-)10 2563( an)1 131( If)1 128(to the maximum possible savings.)4 1498 4 720 3516 t +( percentage)1 518(sposition tables\), it can increase the possible savings and as a result, decrease the)13 3802 2 720 3756 t +(improvement attributable to the other enhancements.)5 2319 1 720 3996 t +( the search)2 472( As)1 180( are becoming over-loaded.)3 1205(A second reason is that the history heuristic tables)8 2213 4 970 4272 t +( entries)1 328( Table)1 313( variation in the positions that occur in the tree.)9 2151(becomes deeper, there is a greater)5 1528 4 720 4512 t +( flooded with scores from the lower depths that affect the orderings of moves near the root)16 4035(can be)1 285 2 720 4752 t +( results reported here were constrained to only save history information)10 3255( fact, the)2 407( In)1 160(of the tree.)2 498 4 720 4992 t +(within the first)2 651 1 720 5232 t +10 I f +(depth)1397 5232 w +10 S f +(-)1643 5232 w +10 R f +(1)1714 5232 w +11 R f +( This)1 254( information throughout the entire tree.)5 1726(ply of the tree, but to use the)7 1267 3 1793 5232 t +( can)1 204(constraint provided a small improvement in performance, confirming that history tables)10 4116 2 720 5472 t +(become flooded with information, decreasing their usefulness.)6 2739 1 720 5712 t +( the history heuristic dominates the knowledge heuris-)7 2392(As an interior node ordering heuristic,)5 1678 2 970 5988 t +( be a comment on the quality of the chess)9 1824( this result may)3 680( Again,)1 353(tics approach under all scenarios.)4 1463 4 720 6228 t +( order the moves and that a better routine might be written with)12 3062(specific knowledge used to)3 1258 2 720 6468 t +( interesting feature in the diagrams is that sometimes the combination of both)12 3417( An)1 191(increased effort.)1 712 3 720 6708 t +10 I f +(H)720 6948 w +11 R f +(and)822 6948 w +10 I f +(K degrades)1 461 1 1007 6948 t +11 R f +(the performance compared to)3 1295 1 1499 6948 t +10 I f +(H)2822 6948 w +11 R f +( condition is caused by the two ord-)7 1595(alone. This)1 520 2 2925 6948 t +(ering mechanisms disagreeing over the importance of a move.)8 2833 1 720 7188 t +10 I f +(K)3616 7188 w +11 R f +( highly)1 322(may rate some moves)3 994 2 3724 7188 t +cleartomark +showpage +saveobj restore +%%EndPage: 15 15 +%%Page: 16 16 +/saveobj save def +mark +16 pagesetup +11 R f +(- 16 -)2 238 1 2761 490 t +( the knowledge)2 679( that)1 196( Recall)1 339(that superficially appear to be good but in the current context, are not.)12 3106 4 720 840 t +( history heuristic)2 750( The)1 231(heuristics statically assign scores to moves without performing any search.)9 3339 3 720 1080 t +( his-)1 194( The)1 227( ordering.)1 428(also does not perform search, but makes use of previous search results to do its)14 3471 4 720 1320 t +(tory heuristic is)2 691 1 720 1560 t +10 I f +(adaptive)1439 1560 w +11 R f +( search tree and is)4 793(to the conditions in the)4 1023 2 1814 1560 t +10 I f +(insensitive)3657 1560 w +11 R f +(to application depen-)2 931 1 4109 1560 t +( heuristics fail under conditions of exception, where excep-)8 2632( knowledge)1 512( The)1 229(dent pre-conceptions.)1 947 4 720 1800 t +( inappropriate)1 629( Consequently,)1 706( the heuristics.)2 673(tion is defined as any condition not covered by)8 2203 4 720 2040 t +10 I f +(K)4973 2040 w +11 R f +(scores can decrease the effectiveness of ordering, resulting in larger trees.)10 3231 1 720 2280 t +( the history heuristic.)3 993(Not surprisingly, the killer heuristic shows up as being inferior to)10 3077 2 970 2556 t +( consideration is that there is less overhead in maintaining killer than history informa-)13 3812(However, a)1 508 2 720 2796 t +( high performance machines that implement)5 1957( For)1 213(tion; in particular, no sorting.)4 1308 3 720 3036 t +11 S f +(ab)4230 3036 w +11 R f +(in hardware or)2 648 1 4392 3036 t +(microcode, the simplicity of implementing the killer heuristic may make it preferable \(for exam-)13 4320 1 720 3276 t +(ple, [25]\).)1 436 1 720 3516 t +( the trees)2 440( As)1 200( of transposition tables consistently increases with depth.)7 2660(The performance)1 770 4 970 3792 t +( and therefore more savings to be found.)7 1824(become larger, there are potentially more transpositions)6 2496 2 720 4032 t +( 6 ply, it appears there were)6 1240(However, the savings are limited by the size of the tables used and to)13 3080 2 720 4272 t +( 8, over-loading became a seri-)5 1373( depths 7 and)3 596( For)1 213(few problems with table over-loading problems.)5 2138 4 720 4512 t +( further depths, if performance starts to)6 1848( At)1 188( be increased.)2 643(ous problem and table sizes had to)6 1641 4 720 4752 t +( the size of the tables, reducing the number of collisions that)11 2784(decrease, one can always increase)4 1536 2 720 4992 t +(occur.)720 5232 w +( is)1 114( This)1 264( out-performs the refutation table.)4 1533(In all cases, the transposition table significantly)6 2159 4 970 5508 t +( the refutation tables contain only a small subset of the information available)12 3444(not surprising since)2 876 2 720 5748 t +( refutation and transposi-)3 1116( [8] has published results comparing)5 1617( Marsland)1 474(with transposition tables.)2 1113 4 720 5988 t +( 6 ply searches using transposition tables of size)8 2162( experiments included 2 through)4 1451( His)1 216(tion tables.)1 491 4 720 6228 t +( in perfor-)2 468( all depths examined, refutation tables were found to be roughly comparable)11 3470(8K. For)1 382 3 720 6468 t +( with those reported here, it is)6 1455( comparing these results)3 1140( When)1 342(mance to transposition tables.)3 1383 4 720 6708 t +( program are 3-4 times larger than those)7 1815(important to note that tree sizes obtained by Marsland's)8 2505 2 720 6948 t +(generated by)1 568 1 720 7188 t +10 I f +(Phoenix)1319 7188 w +11 R f +( of)1 124( Because)1 425( \(the 24 Kopec-Bratko positions\).)4 1495(while using the same data set)5 1316 4 1680 7188 t +cleartomark +showpage +saveobj restore +%%EndPage: 16 16 +%%Page: 17 17 +/saveobj save def +mark +17 pagesetup +11 R f +(- 17 -)2 238 1 2761 490 t +( up more quickly and may become over-loaded, reducing its effec-)10 2932(this, the transposition table fills)4 1388 2 720 840 t +( an 8K tran-)3 545( concludes that)2 673( Marsland)1 477(tiveness and making refutation tables look more attractive.)7 2625 4 720 1080 t +( positions. In)2 582(sposition table is too small for 6 ply searches of complex middlegame)11 3111 2 720 1320 t +10 I f +(Phoenix)4442 1320 w +11 R f +(, refu-)1 271 1 4769 1320 t +( examined to 6 ply, again showing little justifi-)8 2091(tation tables and 8K entry transposition have been)7 2229 2 720 1560 t +( to remember an)3 782( main contribution of the refutation table is)7 2039( The)1 247(cation for refutation tables.)3 1252 4 720 1800 t +( is an important enhancement on a)6 1568( This)1 262( information.)1 585(important subset of the transposition table)5 1905 4 720 2040 t +( for machines with)3 854( But)1 227( transposition tables are not possible.)5 1682(memory constrained system where)3 1557 4 720 2280 t +( as the transposition table does not become over-loaded, refutation)9 3097(available memory, as long)3 1223 2 720 2520 t +(tables will always be of minimal benefit.)6 1794 1 720 2760 t +( and minimal window, usually provide a)6 1837(The two search window enhancements, aspiration)5 2233 2 970 3036 t +( with the history heuristic and transposition)6 2065( used)1 256( When)1 344(small improvement in performance.)3 1655 4 720 3276 t +( both)1 225( Since)1 301( and together provide a small reduction in tree size.)9 2261(tables, both enhancements singlely)3 1533 4 720 3516 t +( and cost nothing in additional storage or computation, one might as well)12 3323(are easy to implement)3 997 2 720 3756 t +( benefits, however, are probably going to be)7 1951( The)1 228(include them in any real tree searching program.)7 2141 3 720 3996 t +(small.)720 4236 w +( the his-)2 373( Clearly,)1 416(In conclusion, what is the best combination of alpha-beta enhancements?)9 3281 3 970 4512 t +( loses nothing and gains)4 1087( One)1 245( transposition tables provide most of the savings.)7 2203(tory heuristic and)2 785 4 720 4752 t +(slightly by also including aspiration and minimal window search.)8 2878 1 720 4992 t +( move ordering, it is difficult)5 1278(Since the experiments reported here illustrate the importance of)8 2792 2 970 5268 t +( having addressed the issue of)5 1360( Without)1 426( with those of other researchers.)5 1446(to compare these results)3 1088 4 720 5508 t +( move ordering, some reported results may be heavily biased by a good or poor ord-)15 3753(interior node)1 567 2 720 5748 t +( considering a range of)4 1005( By)1 185( but it is impossible for us to know.)8 1562( 7, 8]\))2 246(ering scheme \(for example [1,)4 1322 5 720 5988 t +( ordering to the knowledge and history heuristics\), the results reported)10 3126(ordering schemes \(from no)3 1194 2 720 6228 t +( used to)2 373(here illustrate the range of efficient versus inefficient alpha-beta searching and can be)12 3947 2 720 6468 t +(assess the effectiveness of interior node ordering methods.)7 2567 1 720 6708 t +( heuristic was added to the chess program)7 1861(The history)1 507 2 970 6984 t +11 I f +(TinkerBelle)3370 6984 w +11 R f +( program used tran-)3 874(. This)1 284 2 3882 6984 t +( the history heuristic)3 986( addition of)2 566( The)1 255(sposition tables and simple move ordering heuristics.)6 2513 4 720 7224 t +cleartomark +showpage +saveobj restore +%%EndPage: 17 17 +%%Page: 18 18 +/saveobj save def +mark +18 pagesetup +11 R f +(- 18 -)2 238 1 2761 490 t +(reduced the size of the average tree by 25%.)8 1938 1 720 840 t +( artificially constructed trees it is easy to calcu-)8 2122( For)1 215( are we to the minimal tree?)6 1262(How close)1 471 4 970 1116 t +( is not necessarily true for application gen-)7 1939( this)1 198( Unfortunately,)1 709(late the size of the minimal tree.)6 1474 4 720 1356 t +( an average branching factor, one can come up with a rough approximation of)13 3465( Using)1 323(erated trees.)1 532 3 720 1596 t +( transposition tables, the)3 1080( Eliminating)1 580(the minimal tree size.)3 956 3 720 1836 t +10 I f +(NBP)3364 1836 w +11 R f +(results show the trees being built)5 1456 1 3584 1836 t +( transposition tables, the trees)4 1357( With)1 289( of the minimal tree.)4 948(to be within a factor of 1.5 times that)8 1726 4 720 2076 t +(become smaller than the minimal tree.)5 1685 1 720 2316 t +11 B f +(6. Conclusions)1 710 1 720 2676 t +11 R f +( inexpensive method for ordering descendants of interior nodes)8 2879(The history heuristic is an)4 1191 2 970 2952 t +( has the advantage of being simple to implement, as)9 2415( It)1 138(that is largely application independent.)4 1767 3 720 3192 t +( algorithm sub-)2 679( The)1 229( consuming, trial-and-error, knowledge-based approach.)4 2475(compared to the time)3 937 4 720 3432 t +( knowledge and, at least in the case of)8 1669(stitutes "experience" for explicit)3 1419 2 720 3672 t +11 S f +(ab)3836 3672 w +11 R f +(searching applied to the)3 1046 1 3994 3672 t +(game of chess, provides a viable alternative.)6 1945 1 720 3912 t +(The heuristic has proven useful for parallel)6 1955 1 970 4188 t +11 S f +(ab)2964 4188 w +11 R f +( network of)2 530( [26] on a)3 457(implementations. In)1 920 3 3133 4188 t +( each processor would maintain its own)6 1776( First,)1 293( tables were used two ways.)5 1256(computers, the history)2 995 4 720 4428 t +( periodically all the local tables would be merged and broadcast to all)12 3088( Second,)1 410(local history table.)2 822 3 720 4668 t +( program per-)2 612( resulted in a noticeable improvement in)6 1807( This)1 258(processors to achieve global sharing.)4 1643 4 720 4908 t +(formance.)720 5148 w +( easy to build trees close to the minimal tree in size, there is noth-)14 2959(Given that it is relatively)4 1111 2 970 5424 t +(ing of interest left to explore in terms of)8 1808 1 720 5664 t +10 I f +( depth)1 263(f ixed)1 202 2 2559 5664 t +11 S f +(ab)3058 5664 w +11 R f +( research efforts are con-)4 1105(searching. New)1 714 2 3221 5664 t +(centrating on)1 609 1 720 5904 t +10 I f +(variable depth)1 596 1 1387 5904 t +11 R f +(searches, so called)2 878 1 2044 5904 t +10 I f +(selective deepening)1 794 1 2980 5904 t +11 R f +( moves)1 349(\(for example, null)2 856 2 3835 5904 t +( singular extensions [29] as enhancements to)6 1995( and)1 192([27, 28])1 338 3 720 6144 t +11 S f +(ab)3278 6144 w +11 R f +( as)1 124( 31])1 164(, and conspiracy numbers [30,)4 1344 3 3408 6144 t +(a new approach to minimax search\).)5 1590 1 720 6384 t +11 B f +(Acknowledgments)720 6744 w +11 R f +( Alexander)1 534( and constructive criticism.)3 1260(Many thanks to Tony Marsland for his guidance)7 2276 3 970 7020 t +(Reinefeld, Murray Campbell, and the anonymous referees provided valuable suggestions.)9 3935 1 720 7260 t +cleartomark +showpage +saveobj restore +%%EndPage: 18 18 +%%Page: 19 19 +/saveobj save def +mark +19 pagesetup +11 R f +(- 19 -)2 238 1 2761 490 t +11 B f +(References)720 840 w +11 R f +( Gillogly,)1 427(1. J.)1 346 2 720 1032 t +11 I f +( of the Technology Chess Program)5 1552(Performance Analysis)1 976 2 1524 1032 t +11 R f +(, Ph.D. thesis, Depart-)3 988 1 4052 1032 t +(ment of Computer Science, Carnegie-Mellon University, 1978.)6 2776 1 995 1152 t +( The Northwestern University Chess Program, in)6 2261( Slate and L.R. Atkin, Chess 4.5 -)7 1606(2. D.J.)1 453 3 720 1308 t +11 I f +(Chess Skill in Man and Machine)5 1479 1 995 1428 t +11 R f +( York, 1977, 82-)3 755(, P.W. Frey \(ed.\), Springer-Verlag, New)5 1811 2 2474 1428 t +(118.)995 1548 w +( and the Killer Heuristic,)4 1142( Akl and M.M. Newborn, The Principle Continuation)7 2433(3. S.G.)1 472 3 720 1704 t +11 I f +(ACM)4808 1704 w +(Annual Conference)1 851 1 995 1824 t +11 R f +(, 1977, 466-473.)2 726 1 1846 1824 t +( Optimal Properties,)2 938( Pearl, Scout: A Simple Game-Searching Algorithm with Proven)8 3036(4. J.)1 346 3 720 1980 t +11 I f +(First Annual National Conference on Artificial Intelligence)6 2619 1 995 2100 t +11 R f +(, Stanford, 1980.)2 738 1 3614 2100 t +( Baudet,)1 390(5. G.)1 382 2 720 2256 t +11 I f +( of Algorithms for Asynchronous Multiprocessors)5 2302(The Design and Analysis)3 1167 2 1543 2256 t +11 R f +(,)5012 2256 w +(Ph.D. thesis, Department of Computer Science, Carnegie-Mellon University, 1978.)8 3660 1 995 2376 t +( and T.A. Marsland, A Comparison of Minimax Tree Search Algorithms,)10 3360( Campbell)1 469(6. M.S.)1 491 3 720 2532 t +11 I f +(Artificial Intelligence 20)2 1082 1 995 2652 t +11 R f +(, \(1983\), 347-367.)2 798 1 2077 2652 t +( Marsland, A Review of Game-Tree Pruning,)6 2060(7. T.A.)1 477 2 720 2808 t +11 I f +(Journal of the International Computer)4 1743 1 3297 2808 t +(Chess Association 9)2 888 1 995 2928 t +11 R f +(, 1 \(1986\), 3-19.)3 716 1 1883 2928 t +( Marsland, Relative Efficiency of Alpha-Beta Implementations,)6 2938(8. T.A.)1 477 2 720 3084 t +11 I f +(International Joint)1 853 1 4187 3084 t +(Conference on Artificial Intelligence)3 1615 1 995 3204 t +11 R f +(, Karlsruhe, 1983, 763-766.)3 1213 1 2610 3204 t +( Schaeffer, Experiments in Search and Knowledge, Ph.D. thesis, Dept. of Computer Sci-)12 3974(9. J.)1 346 2 720 3360 t +(ence, University of Waterloo, 1986.)4 1577 1 995 3480 t +( Schaeffer, The History Heuristic,)4 1511(10. J.)1 346 2 720 3636 t +11 I f +( Associa-)1 413(Journal of the International Computer Chess)5 2016 2 2611 3636 t +(tion 6)1 255 1 995 3756 t +11 R f +(, 3 \(1983\), 16-19.)3 771 1 1250 3756 t +( of Alpha-Beta Pruning,)3 1066( Knuth and R.W. Moore, An Analysis)6 1685(11. D.E.)1 477 3 720 3912 t +11 I f +(Artificial Intelligence 6)2 1033 1 3979 3912 t +11 R f +(,)5012 3912 w +(\(1975\), 293-326.)1 742 1 995 4032 t +( Chess Program,)2 771( Greenblatt, D.E. Eastlake and S.D. Crocker, The Greenblatt)8 2830(12. R.D.)1 484 3 720 4188 t +11 I f +(Fall)4856 4188 w +(Joint Computer Conference 31)3 1359 1 995 4308 t +11 R f +(, \(1967\), 801-810.)2 798 1 2354 4308 t +( Reinefeld, An Improvement of the Scout Tree Search Algorithm,)9 2899(13. A.)1 382 2 720 4464 t +11 I f +( the Interna-)2 553(Journal of)1 457 2 4030 4464 t +(tional Computer Chess Association 6)4 1642 1 995 4584 t +11 R f +(, 4 \(1983\), 4-14.)3 716 1 2637 4584 t +( S.A. Lawless, Parallel Alpha-Beta Search on Arachne,)7 2480( Finkel, J. Fishburn and)4 1071(14. R.A.)1 484 3 720 4740 t +11 I f +(Inter-)4791 4740 w +(national Conference on Parallel Processing)4 1944 1 995 4860 t +11 R f +(, 1980, 235-243.)2 726 1 2939 4860 t +( Marsland, A. Reinefeld and J. Schaeffer, Low Overhead Alternatives to SSS*,)11 3539(15. T.A.)1 477 2 720 5016 t +11 I f +(Artifi-)4770 5016 w +(cial Intelligence 31)2 848 1 995 5136 t +11 R f +(, 1 \(1987\), 185-199.)3 881 1 1843 5136 t +( Hyatt,)1 306(16. R.M.)1 503 2 720 5292 t +11 I f +( A Computer Chess Playing Program)5 1684(Cray Blitz -)2 527 2 1563 5292 t +11 R f +(, M.Sc. thesis, University of)4 1266 1 3774 5292 t +(Southern Mississippi, 1983.)2 1233 1 995 5412 t +( Newell and H.A. Simon, in)5 1231(17. A.)1 382 2 720 5568 t +11 I f +(Human Problem Solving)2 1087 1 2361 5568 t +11 R f +(, Prentice-Hall, 1972.)2 944 1 3448 5568 t +( Adelson-Velskiy, V.L. Arlazarov and M.V. Donskoy, Some Methods of Controlling)10 3812(18. G.M.)1 508 2 720 5724 t +(the Tree Search in Chess Programs,)5 1568 1 995 5844 t +11 I f +(Artificial Intelligence 6)2 1027 1 2591 5844 t +11 R f +(, \(1975\), 361-371.)2 798 1 3618 5844 t +( on Game Trees, Ph.D. thesis, Dept.)6 1611( Nau, Quality of Decision Versus Depth of Search)8 2237(19. D.S.)1 472 3 720 6000 t +(of Computer Science, Duke University, 1979.)5 2016 1 995 6120 t +( Experiment: A Comparison of Human and)6 2026( Kopec and I. Bratko, The Bratko-Kopec)6 1912(20. D.)1 382 3 720 6276 t +(Computer Performance in Chess, in)4 1609 1 995 6396 t +11 I f +( 3)1 91(Advances in Computer Chess)3 1319 2 2641 6396 t +11 R f +(, M.R.B. Clarke \(ed.\),)3 989 1 4051 6396 t +(Pergamon Press, 1982, 57-72.)3 1321 1 995 6516 t +( Program,)1 447( Newborn, A Parallel Search Chess)5 1609(21. M.M.)1 527 3 720 6672 t +11 I f +(ACM Annual Conference)2 1137 1 3344 6672 t +11 R f +(, 1985, 272-)2 559 1 4481 6672 t +(277.)995 6792 w +( Schaeffer, Multiprocessor Tree-Search Experiments, in)5 2486( Marsland, M. Olafsson and J.)5 1357(22. T.A.)1 477 3 720 6948 t +11 I f +(Advances in Computer Chess 4)4 1375 1 995 7068 t +11 R f +(, D. Beal \(ed.\), Pergamon Press, 1985, 37-51.)7 2000 1 2370 7068 t +( and J. Dixon, Experiments with some Programs that Search Game Trees,)11 3292( Slagle)1 307(23. J.)1 346 3 720 7224 t +11 I f +(Journal)4698 7224 w +cleartomark +showpage +saveobj restore +%%EndPage: 19 19 +%%Page: 20 20 +/saveobj save def +mark +20 pagesetup +11 R f +(- 20 -)2 238 1 2761 490 t +11 I f +(of the ACM 2)3 591 1 995 840 t +11 R f +(, \(1969\), 189-207.)2 798 1 1586 840 t +( Strategies in Game)3 903( Muszycka and R. Shinghal, An Empirical Comparison of Pruning)9 3035(24. A.)1 382 3 720 996 t +(Trees,)995 1116 w +11 I f +(IEEE Transactions on Systems, Man, and Cybernetics SMC-15)7 2778 1 1293 1116 t +11 R f +(, 3 \(1985\), 389-399.)3 881 1 4071 1116 t +( A VLSI Architecture for Chess, Ph.D. thesis, Dept. of)9 2465( Ebeling, All the Right Moves:)5 1391(25. Carl)1 464 3 720 1272 t +(Computer Science, Carnegie-Mellon University, 1986.)4 2409 1 995 1392 t +( Schaeffer, Distributed Game-Tree Searching,)4 2050(26. J.)1 346 2 720 1548 t +11 I f +( Distributed Com-)2 822(Journal of Parallel and)3 1065 2 3153 1548 t +(puting)995 1668 w +11 R f +( appear.)1 346( To)1 178(, 1989.)1 304 3 1277 1668 t +( Beal, Null Moves,)3 836(27. D.)1 382 2 720 1824 t +11 I f +(Advances in Computer Chess V)4 1387 1 1966 1824 t +11 R f +(, 1987.)1 304 1 3353 1824 t +( the Null Move in Chess,)5 1108( Goetsch and M. Campbell, Experiments with)6 2018(28. G.)1 382 3 720 1980 t +11 I f +(AAAI Sprint Sym-)2 783 1 4257 1980 t +(posium)995 2100 w +11 R f +(, 1988, 14-18.)2 616 1 1313 2100 t +( Singular Extensions: Adding Selectivity to)5 1954( Anantharaman, M. Campbell and F.H. Hsu,)6 1996(29. T.)1 370 3 720 2256 t +(brute-Force Searching,)1 1004 1 995 2376 t +11 I f +(AAAI Spring Symposium)2 1087 1 2027 2376 t +11 R f +(, 1988, 8-13.)2 561 1 3114 2376 t +( Min-Max Search,)2 832( McAllester, Conspiracy Numbers for)4 1718(30. D.A.)1 489 3 720 2532 t +11 I f +(Artificial Intelligence 35)2 1112 1 3802 2532 t +11 R f +(, 3)1 126 1 4914 2532 t +(\(1988\), 287-310.)1 742 1 995 2652 t +( Schaeffer, Conspiracy Numbers,)3 1459(31. J.)1 346 2 720 2808 t +11 I f +(Artificial Intelligence)1 944 1 2553 2808 t +11 R f +( in)1 115( to appear)2 432( Also)1 264( press.)1 281( In)1 147(, 1989.)1 304 6 3497 2808 t +11 I f +(Advances in Computer Chess V,)4 1415 1 995 2928 t +11 R f +(D. Beal and H. Berliner \(ed.\), Elsevier Press, 1989.)8 2254 1 2438 2928 t +cleartomark +showpage +saveobj restore +%%EndPage: 20 20 +%%Page: 21 21 +/saveobj save def +mark +21 pagesetup +11 R f +(- 21 -)2 238 1 2761 490 t +(Affiliation of author:)2 922 1 995 840 t +( the Department of Computing Science, University of Alberta, Edmon-)9 3214(The author is with)3 831 2 995 1080 t +( work was supported by the National Science and)8 2316( This)1 270(ton, Alberta, Canada T6G 2H1.)4 1459 3 995 1200 t +(Engineering Research Council of Canada.)4 1844 1 995 1320 t +(Footnotes:)995 1680 w +( 1986 World Computer Chess Championship, Cologne, West Ger-)8 3027(1. A competitor in the)4 1018 2 995 1920 t +(many.)995 2040 w +( conducted through to depth 6 and showed minimal signs)9 2571(2. The original experiments were)4 1474 2 995 2280 t +( depths 7 and 8, table conflicts necessitated an increase)9 2460( extended to)2 549( When)1 323(of over-loading.)1 713 4 995 2400 t +(in table size.)2 553 1 995 2520 t +( software predecessor of the chess machine)6 1892(3. A)1 218 2 995 2760 t +11 I f +(Belle.)3133 2760 w +cleartomark +showpage +saveobj restore +%%EndPage: 21 21 +%%Page: 22 22 +/saveobj save def +mark +22 pagesetup +11 R f +(- 22 -)2 238 1 2761 490 t +cleartomark +saveobj restore +%%BeginGlobal +/C /Courier def +%%EndGlobal +/saveobj save def +mark +10 C f +(AlphaBeta\( p : position;)3 1440 1 995 820 t +10 S f +(a)2495 820 w +10 C f +(,)2558 820 w +10 S f +(b)2678 820 w +10 C f +(, depth : integer \) : integer;)6 1800 1 2733 820 t +(var)995 920 w +(bestmove, score, width, m, result : integer;)6 2640 1 1235 1020 t +(rating : array[ 1..MAX_WIDTH ] of integer;)6 2520 1 1235 1120 t +(begin)995 1320 w +( At a leaf node })5 1020( {)1 540(if depth = 0 then)4 1020 3 1235 1420 t +(return\( Evaluate\( p \) \);)4 1440 1 1475 1520 t +(width := GenerateMoves\( moves \);)4 1920 1 1235 1720 t +( No moves in this position })6 1680( {)1 540(if width = 0 then)4 1020 3 1235 1820 t +(return\( Evaluate\( p \) \);)4 1440 1 1475 1920 t +({ Assign history heuristic score to each move })8 2820 1 1235 2120 t +(for m := 1 to width do)6 1320 1 1235 2220 t +( m ] = HistoryTable[ moves[ m ] ];)8 2040(* rating[)1 900 2 995 2320 t +( Put highest rated moves first })6 1920( {)1 240(Sort\( moves, rating \);)3 1320 3 1235 2420 t +(score :=)1 480 1 1235 2620 t +10 S f +(-\245)1775 2620 w +10 R f +(4;)1903 2620 w +(for m := 1 to width do)6 884 1 1095 2720 t +(begin)1170 2820 w +({ Recurse using nega-max variant of)5 1464 1 1220 2920 t +10 S f +(ab)2709 2920 w +10 R f +(})2852 2920 w +(result := -AlphaBeta\( p.moves[m], -)4 1437 1 1220 3020 t +10 S f +(b)2657 3020 w +10 R f +(, -)1 83 1 2712 3020 t +10 S f +(a)2795 3020 w +10 R f +(, depth-1 \);)2 441 1 2858 3020 t +(if result)1 308 1 1220 3120 t +10 S f +(>)1553 3120 w +10 R f +(score then)1 407 1 1633 3120 t +(score := result;)2 594 1 1320 3220 t +({ Check for cut-off })4 838 1 1220 3420 t +(if score)1 296 1 1220 3520 t +10 S f +(>)1541 3520 w +10 R f +(=)1596 3520 w +10 S f +(b)1677 3520 w +10 R f +(then)1757 3520 w +(begin)1270 3620 w +({ Cut-off: no further sub-trees need be examined })8 2019 1 1320 3720 t +(bestmove := moves[ m ];)4 1000 1 1320 3820 t +(goto done;)1 425 1 1320 3920 t +(end;)1270 4020 w +10 S f +(a)1220 4220 w +10 R f +(:= MAX\()1 375 1 1308 4220 t +10 S f +(a)1708 4220 w +10 R f +(, score \);)2 346 1 1771 4220 t +(end;)1170 4320 w +(done:)1045 4520 w +({ Update history score for best move })7 1546 1 1095 4620 t +( bestmove ] = HistoryTable[ bestmove ] + 2)8 1754(* HistoryTable[)1 685 2 995 4720 t +7 I f +(depth)3434 4681 w +10 C f +(;)3606 4720 w +(return\( score \);)2 960 1 1235 4820 t +(end.)995 4920 w +10 B f +(Fig. 1. The History Heuristic and Alpha-Beta.)6 1948 1 2043 5120 t +cleartomark +showpage +saveobj restore +%%EndPage: 22 22 +%%Page: 23 23 +/saveobj save def +mark +23 pagesetup +11 R f +(- 23 -)2 238 1 2761 490 t +cleartomark +saveobj restore +%%BeginGlobal +% +% Version 3.3 drawing procedures for dpost. Automatically pulled in, but only +% when needed. +% + +/inpath false def +/savematrix matrix def + +/Dl { + inpath + {pop pop neg lineto} + {newpath neg moveto neg lineto stroke} + ifelse +} bind def + +/De { + /y1 exch 2 div def + /x1 exch 2 div def + /savematrix savematrix currentmatrix def + neg exch x1 add exch translate + x1 y1 scale + 0 0 1 0 360 + inpath + {1 0 moveto arc savematrix setmatrix} + {newpath arc savematrix setmatrix stroke} + ifelse +} bind def + +/Da { + /dy2 exch def + /dx2 exch def + /dy1 exch def + /dx1 exch def + dy1 add neg exch dx1 add exch + dx1 dx1 mul dy1 dy1 mul add sqrt + dy1 dx1 neg atan + dy2 neg dx2 atan + inpath + {arc} + {newpath arc stroke} + ifelse +} bind def + +/DA { + /dy2 exch def + /dx2 exch def + /dy1 exch def + /dx1 exch def + dy1 add neg exch dx1 add exch + dx1 dx1 mul dy1 dy1 mul add sqrt + dy1 dx1 neg atan + dy2 neg dx2 atan + inpath + {arcn} + {newpath arcn stroke} + ifelse +} bind def + +/Ds { + /y2 exch def + /x2 exch def + /y1 exch def + /x1 exch def + /y0 exch def + /x0 exch def + x0 5 x1 mul add 6 div + y0 5 y1 mul add -6 div + x2 5 x1 mul add 6 div + y2 5 y1 mul add -6 div + x1 x2 add 2 div + y1 y2 add -2 div + inpath + {curveto} + {newpath x0 x1 add 2 div y0 y1 add -2 div moveto curveto stroke} + ifelse +} bind def +%%EndGlobal +/saveobj save def +mark +11 R f +2730 1031 300 300 De +(Root)2773 1053 w +1830 1632 300 300 De +3630 1632 300 300 De +(I2)3735 1654 w +3672 1526 2985 1138 Dl +2087 1526 2774 1138 Dl +1380 2232 300 300 De +1830 2232 300 300 De +2280 2232 300 300 De +1874 1738 1530 2082 Dl +1980 1782 1980 2082 Dl +2086 1738 2430 2082 Dl +2880 2232 300 300 De +(I2.M)2921 2254 w +3330 2232 300 300 De +3929 2232 300 300 De +4379 2232 300 300 De +3672 1738 3029 2082 Dl +(Move M)1 382 1 2882 1909 t +3779 1782 3479 2082 Dl +3780 1782 4080 2082 Dl +3887 1738 4530 2082 Dl +1830 2831 300 300 De +(I1)1935 2853 w +1980 2382 1980 2682 Dl +1380 3432 300 300 De +1830 3432 300 300 De +2280 3432 300 300 De +(I1.M)2322 3454 w +1874 2937 1530 3281 Dl +(Move M)1 382 1 2282 3110 t +1980 2981 1980 3281 Dl +2086 2937 2430 3281 Dl +11 B f +(Fig. 2. History Heuristic Example.)4 1607 1 2214 4325 t +cleartomark +showpage +saveobj restore +%%EndPage: 23 23 +%%Page: 24 24 +/saveobj save def +mark +24 pagesetup +11 R f +(- 24 -)2 238 1 2761 490 t +974 882 974 3422 Dl +5039 882 974 882 Dl +5040 3422 5040 882 Dl +975 3422 5040 3422 Dl +(%)629 2174 w +(depth)2884 3699 w +974 3473 974 3422 Dl +(2)947 3556 w +1482 3473 1482 3422 Dl +(3)1455 3556 w +1990 3473 1990 3422 Dl +(4)1963 3556 w +2499 3473 2499 3422 Dl +(5)2472 3556 w +3006 3473 3006 3422 Dl +(6)2979 3556 w +3515 3473 3515 3422 Dl +(7)3488 3556 w +4023 3473 4023 3422 Dl +(8)3996 3556 w +4531 3473 4531 3422 Dl +(9)4504 3556 w +5040 3473 5040 3422 Dl +(10)4985 3556 w +923 3422 974 3422 Dl +(0)868 3444 w +923 3168 974 3168 Dl +(10)813 3190 w +923 2915 974 2915 Dl +(20)813 2937 w +923 2661 974 2661 Dl +(30)813 2683 w +923 2406 974 2406 Dl +(40)813 2428 w +923 2152 974 2152 Dl +(50)813 2174 w +923 1898 974 1898 Dl +(60)813 1920 w +923 1644 974 1644 Dl +(70)813 1666 w +923 1390 974 1390 Dl +(80)813 1412 w +923 1136 974 1136 Dl +(90)813 1158 w +923 882 974 882 Dl +(100)758 904 w +1990 1262 1482 1161 Dl +2498 1313 1990 1262 Dl +3007 1415 2499 1314 Dl +3514 1126 3006 1415 Dl +4023 1817 3515 1126 Dl +4531 1447 4023 1817 Dl +(H)4582 1442 w +8 R f +(.)1471 1520 w +(.)1496 1525 w +(.)1521 1530 w +(.)1547 1535 w +(.)1573 1540 w +(.)1598 1545 w +(.)1624 1551 w +(.)1649 1556 w +(.)1674 1561 w +(.)1699 1566 w +(.)1725 1571 w +(.)1750 1576 w +(.)1776 1581 w +(.)1801 1586 w +(.)1827 1591 w +(.)1852 1596 w +(.)1878 1601 w +(.)1903 1606 w +(.)1928 1611 w +(.)1953 1616 w +(. .)1 20 1 1979 1622 t +(.)2005 1620 w +(.)2030 1619 w +(.)2056 1617 w +(.)2081 1616 w +(.)2106 1615 w +(.)2131 1614 w +(.)2157 1612 w +(.)2182 1611 w +(.)2208 1610 w +(.)2233 1609 w +(.)2259 1607 w +(.)2284 1606 w +(.)2310 1605 w +(.)2335 1604 w +(.)2360 1602 w +(.)2385 1601 w +(.)2411 1600 w +(.)2437 1599 w +(.)2462 1597 w +(. .)1 20 1 2488 1596 t +(.)2513 1600 w +(.)2538 1604 w +(.)2563 1607 w +(.)2589 1611 w +(.)2614 1615 w +(.)2640 1619 w +(.)2665 1623 w +(.)2691 1627 w +(.)2716 1630 w +(.)2742 1634 w +(.)2767 1638 w +(.)2792 1642 w +(.)2817 1646 w +(.)2843 1649 w +(.)2869 1653 w +(.)2894 1657 w +(.)2920 1661 w +(.)2945 1665 w +(.)2970 1669 w +(. .)1 20 1 2995 1672 t +(.)3015 1655 w +(.)3033 1637 w +(.)3052 1620 w +(.)3071 1602 w +(.)3090 1585 w +(.)3108 1567 w +(.)3127 1550 w +(.)3146 1533 w +(.)3165 1515 w +(.)3184 1497 w +(.)3203 1480 w +(.)3221 1462 w +(.)3240 1445 w +(.)3259 1427 w +(.)3278 1409 w +(.)3297 1392 w +(.)3316 1375 w +(.)3334 1357 w +(.)3353 1340 w +(.)3372 1322 w +(.)3391 1305 w +(.)3410 1287 w +(.)3429 1270 w +(.)3447 1252 w +(.)3466 1234 w +(.)3485 1217 w +(. .)1 20 1 3504 1200 t +(.)3519 1220 w +(.)3535 1241 w +(.)3550 1261 w +(.)3565 1281 w +(.)3581 1302 w +(.)3596 1322 w +(.)3612 1343 w +(.)3627 1363 w +(.)3643 1384 w +(.)3658 1404 w +(.)3673 1425 w +(.)3689 1445 w +(.)3704 1466 w +(.)3720 1486 w +(.)3735 1507 w +(.)3751 1527 w +(.)3766 1548 w +(.)3781 1569 w +(.)3797 1589 w +(.)3812 1610 w +(.)3828 1630 w +(.)3843 1651 w +(.)3858 1671 w +(.)3874 1691 w +(.)3889 1712 w +(.)3905 1732 w +(.)3920 1753 w +(.)3935 1773 w +(.)3951 1794 w +(.)3966 1814 w +(.)3981 1835 w +(.)3997 1855 w +(.)4012 1875 w +11 R f +(K)4074 1894 w +1506 2197 1482 2203 Dl +1554 2185 1530 2191 Dl +1602 2173 1578 2179 Dl +1651 2161 1627 2167 Dl +1699 2148 1675 2154 Dl +1748 2136 1724 2142 Dl +1796 2125 1772 2131 Dl +1844 2112 1820 2118 Dl +1893 2100 1869 2106 Dl +1941 2088 1917 2094 Dl +1989 2076 1965 2082 Dl +2009 2060 1990 2076 Dl +2047 2028 2028 2044 Dl +2084 1996 2065 2012 Dl +2122 1964 2103 1980 Dl +2160 1932 2141 1948 Dl +2197 1900 2178 1916 Dl +2235 1868 2216 1884 Dl +2272 1836 2253 1852 Dl +2310 1804 2291 1820 Dl +2348 1772 2329 1788 Dl +2385 1740 2366 1756 Dl +2423 1708 2404 1724 Dl +2460 1676 2441 1692 Dl +2498 1645 2479 1661 Dl +2522 1636 2499 1644 Dl +2570 1619 2547 1627 Dl +2618 1602 2595 1610 Dl +2666 1585 2643 1593 Dl +2715 1568 2692 1576 Dl +2764 1551 2741 1559 Dl +2812 1534 2789 1542 Dl +2860 1517 2837 1525 Dl +2909 1501 2886 1509 Dl +2957 1483 2934 1491 Dl +3005 1466 2982 1474 Dl +3028 1454 3006 1466 Dl +3073 1428 3051 1440 Dl +3117 1403 3095 1415 Dl +3161 1377 3139 1389 Dl +3205 1351 3183 1363 Dl +3249 1326 3227 1338 Dl +3294 1300 3272 1312 Dl +3338 1274 3316 1286 Dl +3382 1249 3360 1261 Dl +3426 1223 3404 1235 Dl +3470 1198 3448 1210 Dl +3515 1172 3493 1184 Dl +3540 1170 3515 1171 Dl +3588 1168 3563 1169 Dl +3636 1166 3611 1167 Dl +3685 1163 3660 1164 Dl +3733 1161 3708 1162 Dl +3781 1158 3756 1159 Dl +3830 1156 3805 1157 Dl +3878 1153 3853 1154 Dl +3926 1151 3901 1152 Dl +3974 1148 3949 1149 Dl +4023 1146 3998 1147 Dl +4047 1141 4023 1146 Dl +4095 1130 4071 1135 Dl +4144 1120 4120 1125 Dl +4192 1109 4168 1114 Dl +4241 1098 4217 1103 Dl +4289 1087 4265 1092 Dl +4337 1077 4313 1082 Dl +4385 1067 4361 1072 Dl +4434 1056 4410 1061 Dl +4482 1045 4458 1050 Dl +4531 1034 4507 1039 Dl +(T)4582 1081 w +1990 2481 1482 2304 Dl +2498 2382 1990 2483 Dl +3007 2406 2499 2381 Dl +(R)3057 2428 w +1507 3420 1482 3422 Dl +1555 3416 1530 3418 Dl +1603 3411 1578 3413 Dl +1652 3406 1627 3408 Dl +1700 3402 1675 3404 Dl +1748 3397 1723 3399 Dl +1796 3392 1771 3394 Dl +1845 3387 1820 3389 Dl +1893 3382 1868 3384 Dl +1942 3377 1917 3379 Dl +1990 3372 1965 3374 Dl +2015 3369 1990 3372 Dl +2064 3362 2039 3365 Dl +2112 3355 2087 3358 Dl +2160 3347 2135 3350 Dl +2208 3340 2183 3343 Dl +2257 3333 2232 3336 Dl +2305 3325 2280 3328 Dl +2353 3318 2328 3321 Dl +2401 3311 2376 3314 Dl +2450 3303 2425 3306 Dl +2498 3296 2473 3299 Dl +2524 3294 2499 3296 Dl +2572 3289 2547 3291 Dl +2620 3284 2595 3286 Dl +2668 3279 2643 3281 Dl +2717 3274 2692 3276 Dl +2765 3269 2740 3271 Dl +2813 3265 2788 3267 Dl +2861 3260 2836 3262 Dl +2910 3255 2885 3257 Dl +2958 3250 2933 3252 Dl +3006 3245 2981 3247 Dl +(S)3057 3318 w +1990 3397 1482 3422 Dl +2498 3194 1990 3397 Dl +3007 3245 2499 3194 Dl +(N)3057 3216 w +1990 1568 1482 1553 Dl +2498 1639 1990 1568 Dl +3007 1913 2499 1639 Dl +(L)3057 1935 w +11 B f +(Fig. 3. Single Search Enhancement \(NBP\).)5 1984 1 2025 3913 t +cleartomark +showpage +saveobj restore +%%EndPage: 24 24 +%%Page: 25 25 +/saveobj save def +mark +25 pagesetup +11 R f +(- 25 -)2 238 1 2761 490 t +974 882 974 3422 Dl +5039 882 974 882 Dl +5040 3422 5040 882 Dl +975 3422 5040 3422 Dl +(%)629 2174 w +(depth)2884 3699 w +974 3473 974 3422 Dl +(2)947 3556 w +1482 3473 1482 3422 Dl +(3)1455 3556 w +1990 3473 1990 3422 Dl +(4)1963 3556 w +2499 3473 2499 3422 Dl +(5)2472 3556 w +3006 3473 3006 3422 Dl +(6)2979 3556 w +3515 3473 3515 3422 Dl +(7)3488 3556 w +4023 3473 4023 3422 Dl +(8)3996 3556 w +4531 3473 4531 3422 Dl +(9)4504 3556 w +5040 3473 5040 3422 Dl +(10)4985 3556 w +923 3422 974 3422 Dl +(70)813 3444 w +923 2999 974 2999 Dl +(75)813 3021 w +923 2576 974 2576 Dl +(80)813 2598 w +923 2152 974 2152 Dl +(85)813 2174 w +923 1728 974 1728 Dl +(90)813 1750 w +923 1305 974 1305 Dl +(95)813 1327 w +923 882 974 882 Dl +(100)758 904 w +6 R f +1990 1221 1482 1221 Dl +2498 1137 1990 1221 Dl +3007 1052 2499 1136 Dl +3514 907 3006 1051 Dl +4023 907 3515 907 Dl +4531 892 4023 907 Dl +(HT)4612 955 w +4 R f +(.)1476 1645 w +(.)1499 1657 w +(.)1522 1668 w +(.)1545 1680 w +(.)1568 1691 w +(.)1591 1703 w +(.)1614 1714 w +(.)1637 1726 w +(.)1661 1737 w +(.)1684 1749 w +(.)1707 1760 w +(.)1730 1772 w +(.)1753 1783 w +(.)1776 1795 w +(.)1799 1806 w +(.)1822 1818 w +(.)1845 1830 w +(.)1868 1842 w +(.)1891 1853 w +(.)1914 1865 w +(.)1938 1876 w +(.)1961 1888 w +(. .)1 10 1 1984 1899 t +(.)2004 1883 w +(.)2023 1867 w +(.)2043 1850 w +(.)2062 1834 w +(.)2082 1818 w +(.)2102 1801 w +(.)2121 1785 w +(.)2141 1769 w +(.)2160 1752 w +(.)2179 1736 w +(.)2199 1720 w +(.)2218 1703 w +(.)2238 1687 w +(.)2258 1671 w +(.)2277 1654 w +(.)2297 1639 w +(.)2316 1622 w +(.)2336 1606 w +(.)2356 1590 w +(.)2375 1573 w +(.)2395 1557 w +(.)2414 1541 w +(.)2434 1524 w +(.)2453 1508 w +(.)2472 1492 w +(. .)1 10 1 2493 1476 t +(.)2516 1464 w +(.)2539 1452 w +(.)2562 1441 w +(.)2585 1429 w +(.)2608 1417 w +(.)2631 1406 w +(.)2654 1394 w +(.)2677 1383 w +(.)2700 1371 w +(.)2723 1360 w +(.)2747 1348 w +(.)2770 1337 w +(.)2793 1325 w +(.)2816 1314 w +(.)2839 1302 w +(.)2862 1291 w +(.)2885 1279 w +(.)2908 1268 w +(.)2931 1256 w +(.)2954 1245 w +(.)2977 1233 w +(. .)1 10 1 3000 1222 t +(.)3024 1211 w +(.)3047 1200 w +(.)3070 1189 w +(.)3093 1178 w +(.)3116 1168 w +(.)3139 1157 w +(.)3162 1146 w +(.)3185 1135 w +(.)3208 1124 w +(.)3231 1114 w +(.)3254 1103 w +(.)3277 1092 w +(.)3301 1081 w +(.)3324 1070 w +(.)3347 1060 w +(.)3370 1049 w +(.)3393 1038 w +(.)3416 1027 w +(.)3439 1016 w +(.)3462 1006 w +(.)3486 995 w +(. .)1 10 1 3509 984 t +(.)3534 983 w +(.)3560 981 w +(.)3585 980 w +(.)3611 978 w +(.)3636 977 w +(.)3661 975 w +(.)3686 973 w +(.)3712 972 w +(.)3738 970 w +(.)3763 969 w +(.)3789 967 w +(.)3814 966 w +(.)3839 965 w +(.)3864 963 w +(.)3890 961 w +(.)3915 960 w +(.)3941 958 w +(.)3966 957 w +(.)3992 955 w +(.)4017 954 w +6 R f +(KT)4104 965 w +1507 1817 1482 1813 Dl +1555 1825 1530 1821 Dl +1603 1833 1578 1829 Dl +1652 1842 1627 1838 Dl +1700 1850 1675 1846 Dl +1748 1858 1723 1854 Dl +1796 1865 1771 1861 Dl +1845 1873 1820 1869 Dl +1894 1882 1869 1878 Dl +1942 1890 1917 1886 Dl +1990 1898 1965 1894 Dl +2013 1905 1990 1898 Dl +2062 1921 2039 1914 Dl +2110 1938 2087 1931 Dl +2158 1953 2135 1946 Dl +2207 1969 2184 1962 Dl +2255 1986 2232 1979 Dl +2303 2002 2280 1995 Dl +2352 2018 2329 2011 Dl +2401 2034 2378 2027 Dl +2449 2050 2426 2043 Dl +2497 2066 2474 2059 Dl +2522 2078 2499 2067 Dl +2566 2101 2543 2090 Dl +2609 2122 2586 2111 Dl +2653 2145 2630 2134 Dl +2698 2167 2675 2156 Dl +2742 2189 2719 2178 Dl +2786 2211 2763 2200 Dl +2831 2233 2808 2222 Dl +2874 2255 2851 2244 Dl +2918 2277 2895 2266 Dl +2963 2299 2940 2288 Dl +3007 2321 2984 2310 Dl +(HS)3087 2334 w +1990 1983 1482 1475 Dl +2498 2236 1990 1982 Dl +3007 2406 2499 2237 Dl +(HR)3087 2418 w +4 R f +( .)1 0( .)1 26( . . .)3 75( .)1 26( .)1 25( .)1 26( .)1 25( .)1 26( .)1 25( .)1 26( . . .)3 75( .)1 26( .)1 25( . .)2 52(. . .)2 60 15 1476 2153 t +(.)2007 2165 w +(.)2030 2176 w +(.)2053 2188 w +(.)2076 2199 w +(.)2100 2211 w +(.)2123 2222 w +(.)2146 2234 w +(.)2169 2245 w +(.)2192 2257 w +(.)2215 2269 w +(.)2238 2280 w +(.)2262 2292 w +(.)2285 2303 w +(.)2308 2315 w +(.)2331 2326 w +(.)2354 2338 w +(.)2377 2349 w +(.)2400 2361 w +(.)2423 2373 w +(.)2446 2384 w +(.)2470 2396 w +(. .)1 10 1 2493 2407 t +(.)2516 2415 w +(.)2541 2423 w +(.)2565 2431 w +(.)2589 2439 w +(.)2614 2448 w +(.)2637 2456 w +(.)2662 2464 w +(.)2686 2472 w +(.)2710 2479 w +(.)2735 2488 w +(.)2758 2496 w +(.)2783 2504 w +(.)2807 2512 w +(.)2831 2521 w +(.)2856 2528 w +(.)2879 2536 w +(.)2904 2544 w +(.)2928 2552 w +(.)2952 2561 w +(.)2976 2569 w +(.)3000 2577 w +6 R f +(HN)3087 2588 w +2499 3253 2448 3422 Dl +3007 2660 2499 3253 Dl +(NT)3087 2673 w +1990 2659 1482 1982 Dl +2498 2577 1990 2661 Dl +3007 2745 2499 2576 Dl +(KR)3087 2732 w +2460 3401 2448 3422 Dl +2497 3339 2485 3360 Dl +2515 3319 2499 3338 Dl +2547 3281 2531 3300 Dl +2580 3243 2564 3262 Dl +2613 3204 2597 3223 Dl +2646 3166 2630 3185 Dl +2678 3128 2662 3147 Dl +2711 3089 2695 3108 Dl +2744 3051 2728 3070 Dl +2777 3013 2761 3032 Dl +2809 2975 2793 2994 Dl +2842 2937 2826 2956 Dl +2875 2898 2859 2917 Dl +2908 2860 2892 2879 Dl +2940 2822 2924 2841 Dl +2973 2783 2957 2802 Dl +3006 2745 2990 2764 Dl +(ST)3087 2788 w +4 R f +(.)2493 3423 w +(.)2508 3405 w +(.)2525 3385 w +(.)2542 3367 w +(.)2558 3347 w +(.)2574 3328 w +(.)2591 3309 w +(.)2607 3289 w +(.)2624 3271 w +(.)2640 3251 w +(.)2656 3233 w +(.)2673 3213 w +(.)2689 3194 w +(.)2706 3175 w +(.)2722 3156 w +(.)2738 3137 w +(.)2755 3117 w +(.)2771 3099 w +(.)2787 3079 w +(.)2804 3061 w +(.)2820 3041 w +(.)2837 3022 w +(.)2853 3003 w +(.)2869 2983 w +(.)2886 2965 w +(.)2902 2945 w +(.)2919 2927 w +(.)2935 2907 w +(.)2951 2888 w +(.)2968 2869 w +(.)2984 2850 w +(.)3000 2831 w +6 R f +(RT)3087 2842 w +1505 1909 1482 1898 Dl +1549 1931 1526 1920 Dl +1593 1953 1570 1942 Dl +1637 1975 1614 1964 Dl +1681 1997 1658 1986 Dl +1725 2019 1702 2008 Dl +1770 2042 1747 2031 Dl +1814 2063 1791 2052 Dl +1858 2086 1835 2075 Dl +1902 2108 1879 2097 Dl +1946 2129 1923 2118 Dl +1990 2152 1967 2141 Dl +2013 2163 1990 2152 Dl +2057 2185 2034 2174 Dl +2101 2207 2078 2196 Dl +2146 2230 2123 2219 Dl +2190 2251 2167 2240 Dl +2234 2273 2211 2262 Dl +2278 2296 2255 2285 Dl +2322 2317 2299 2306 Dl +2366 2340 2343 2329 Dl +2410 2362 2387 2351 Dl +2455 2384 2432 2373 Dl +2499 2406 2476 2395 Dl +2517 2424 2499 2406 Dl +2551 2459 2533 2441 Dl +2586 2494 2568 2476 Dl +2622 2530 2604 2512 Dl +2656 2564 2638 2546 Dl +2692 2599 2674 2581 Dl +2726 2634 2708 2616 Dl +2761 2669 2743 2651 Dl +2797 2705 2779 2687 Dl +2831 2739 2813 2721 Dl +2867 2774 2849 2756 Dl +2902 2810 2884 2792 Dl +2936 2844 2918 2826 Dl +2972 2880 2954 2862 Dl +3007 2915 2989 2897 Dl +(HK)3087 2927 w +4 R f +(.)1476 2746 w +(.)1499 2757 w +(.)1522 2769 w +(.)1545 2780 w +(.)1568 2792 w +(.)1591 2803 w +(.)1614 2815 w +(.)1637 2827 w +(.)1661 2839 w +(.)1684 2850 w +(.)1707 2862 w +(.)1730 2873 w +(.)1753 2885 w +(.)1776 2896 w +(.)1799 2908 w +(.)1822 2919 w +(.)1845 2931 w +(.)1868 2942 w +(.)1891 2954 w +(.)1914 2965 w +(.)1938 2977 w +(.)1961 2989 w +(. .)1 10 1 1984 3000 t +(.)2008 2992 w +(.)2033 2984 w +(.)2057 2976 w +(.)2081 2968 w +(.)2105 2960 w +(.)2129 2952 w +(.)2154 2944 w +(.)2178 2936 w +(.)2202 2927 w +(.)2226 2919 w +(.)2250 2911 w +(.)2274 2904 w +(.)2299 2896 w +(.)2323 2887 w +(.)2347 2879 w +(.)2372 2871 w +(.)2395 2863 w +(.)2420 2855 w +(.)2444 2847 w +(.)2468 2839 w +(. .)1 10 1 2493 2831 t +(.)2516 2842 w +(.)2539 2854 w +(.)2562 2865 w +(.)2585 2877 w +(.)2608 2888 w +(.)2631 2900 w +(.)2654 2911 w +(.)2677 2923 w +(.)2700 2935 w +(.)2723 2946 w +(.)2747 2958 w +(.)2770 2969 w +(.)2793 2981 w +(.)2816 2992 w +(.)2839 3004 w +(.)2862 3016 w +(.)2885 3027 w +(.)2908 3039 w +(.)2931 3050 w +(.)2954 3062 w +(.)2977 3073 w +(.)3000 3085 w +6 R f +(KS)3087 3096 w +1507 3422 1482 3422 Dl +1560 3422 1535 3422 Dl +1614 3422 1589 3422 Dl +1668 3422 1643 3422 Dl +1722 3422 1697 3422 Dl +1775 3422 1750 3422 Dl +1829 3422 1804 3422 Dl +1882 3422 1857 3422 Dl +1936 3422 1911 3422 Dl +1989 3422 1964 3422 Dl +2013 3411 1990 3422 Dl +2057 3390 2034 3401 Dl +2101 3367 2078 3378 Dl +2146 3345 2123 3356 Dl +2190 3324 2167 3335 Dl +2234 3301 2211 3312 Dl +2278 3280 2255 3291 Dl +2322 3257 2299 3268 Dl +2366 3235 2343 3246 Dl +2410 3213 2387 3224 Dl +2455 3191 2432 3202 Dl +2499 3169 2476 3180 Dl +2522 3179 2499 3168 Dl +2566 3202 2543 3191 Dl +2609 3224 2586 3213 Dl +2653 3245 2630 3234 Dl +2698 3268 2675 3257 Dl +2742 3290 2719 3279 Dl +2786 3312 2763 3301 Dl +2831 3334 2808 3323 Dl +2874 3356 2851 3345 Dl +2918 3378 2895 3367 Dl +2963 3400 2940 3389 Dl +3007 3423 2984 3412 Dl +(KN)3087 3409 w +10 B f +(Fig. 4. Two Search Enhancements \(NBP\).)5 1766 1 2134 3913 t +cleartomark +showpage +saveobj restore +%%EndPage: 25 25 +%%Page: 26 26 +/saveobj save def +mark +26 pagesetup +11 R f +(- 26 -)2 238 1 2761 490 t +974 882 974 3422 Dl +5039 882 974 882 Dl +5040 3422 5040 882 Dl +975 3422 5040 3422 Dl +(%)629 2174 w +(depth)2884 3699 w +974 3473 974 3422 Dl +(2)947 3556 w +1482 3473 1482 3422 Dl +(3)1455 3556 w +1990 3473 1990 3422 Dl +(4)1963 3556 w +2499 3473 2499 3422 Dl +(5)2472 3556 w +3006 3473 3006 3422 Dl +(6)2979 3556 w +3515 3473 3515 3422 Dl +(7)3488 3556 w +4023 3473 4023 3422 Dl +(8)3996 3556 w +4531 3473 4531 3422 Dl +(9)4504 3556 w +5040 3473 5040 3422 Dl +(10)4985 3556 w +923 3422 974 3422 Dl +(0)868 3444 w +923 3168 974 3168 Dl +(10)813 3190 w +923 2915 974 2915 Dl +(20)813 2937 w +923 2661 974 2661 Dl +(30)813 2683 w +923 2406 974 2406 Dl +(40)813 2428 w +923 2152 974 2152 Dl +(50)813 2174 w +923 1898 974 1898 Dl +(60)813 1920 w +923 1644 974 1644 Dl +(70)813 1666 w +923 1390 974 1390 Dl +(80)813 1412 w +923 1136 974 1136 Dl +(90)813 1158 w +923 882 974 882 Dl +(100)758 904 w +1990 1136 1482 1390 Dl +2498 1161 1990 1136 Dl +3007 1415 2499 1161 Dl +3514 1268 3006 1415 Dl +4023 1642 3515 1267 Dl +4531 1324 4023 1644 Dl +(H)4582 1346 w +8 R f +(.)1471 1520 w +(.)1495 1527 w +(.)1519 1535 w +(.)1544 1542 w +(.)1567 1549 w +(.)1592 1556 w +(.)1616 1563 w +(.)1640 1571 w +(.)1665 1578 w +(.)1688 1585 w +(.)1713 1592 w +(.)1737 1599 w +(.)1761 1607 w +(.)1786 1614 w +(.)1809 1622 w +(.)1834 1629 w +(.)1858 1636 w +(.)1882 1643 w +(.)1907 1651 w +(.)1930 1658 w +(.)1955 1665 w +(. .)1 20 1 1979 1672 t +(.)2003 1664 w +(.)2028 1656 w +(.)2052 1647 w +(.)2076 1638 w +(.)2100 1630 w +(.)2124 1622 w +(.)2149 1613 w +(.)2173 1605 w +(.)2197 1596 w +(.)2221 1587 w +(.)2245 1579 w +(.)2269 1571 w +(.)2294 1562 w +(.)2318 1553 w +(.)2342 1545 w +(.)2367 1537 w +(.)2390 1528 w +(.)2415 1520 w +(.)2439 1512 w +(.)2463 1503 w +(. .)1 20 1 2488 1494 t +(.)2513 1498 w +(.)2538 1502 w +(.)2563 1506 w +(.)2589 1509 w +(.)2614 1514 w +(.)2640 1517 w +(.)2665 1521 w +(.)2691 1525 w +(.)2716 1529 w +(.)2742 1533 w +(.)2767 1536 w +(.)2792 1540 w +(.)2817 1544 w +(.)2843 1548 w +(.)2869 1551 w +(.)2894 1556 w +(.)2920 1559 w +(.)2945 1563 w +(.)2970 1567 w +( .)1 26(. .)1 20 2 2995 1571 t +( .)1 25(. .)1 46 2 3046 1570 t +( . .)2 50( .)1 26(. .)1 45 3 3123 1569 t +(. . .)2 72 1 3249 1568 t +( .)1 25(. .)1 46 2 3326 1567 t +( .)1 0( .)1 26( .)1 25( .)1 26(. .)1 45 5 3402 1566 t +(.)3526 1579 w +(.)3548 1591 w +(.)3570 1604 w +(.)3592 1617 w +(.)3614 1630 w +(.)3636 1643 w +(.)3658 1655 w +(.)3681 1668 w +(.)3703 1681 w +(.)3725 1694 w +(.)3747 1707 w +(.)3769 1719 w +(.)3791 1732 w +(.)3813 1745 w +(.)3835 1758 w +(.)3857 1771 w +(.)3879 1783 w +(.)3902 1796 w +(.)3923 1809 w +(.)3946 1822 w +(.)3968 1835 w +(.)3990 1847 w +(.)4012 1860 w +11 R f +(K)4074 1905 w +1503 2598 1482 2610 Dl +1547 2571 1526 2583 Dl +1592 2544 1571 2556 Dl +1635 2518 1614 2530 Dl +1680 2492 1659 2504 Dl +1724 2465 1703 2477 Dl +1768 2438 1747 2450 Dl +1813 2412 1792 2424 Dl +1857 2385 1836 2397 Dl +1901 2358 1880 2370 Dl +1945 2332 1924 2344 Dl +1989 2306 1968 2318 Dl +2008 2286 1990 2304 Dl +2043 2252 2025 2270 Dl +2078 2216 2060 2234 Dl +2113 2182 2095 2200 Dl +2148 2147 2130 2165 Dl +2183 2111 2165 2129 Dl +2219 2077 2201 2095 Dl +2253 2041 2235 2059 Dl +2288 2006 2270 2024 Dl +2323 1972 2305 1990 Dl +2358 1936 2340 1954 Dl +2394 1901 2376 1919 Dl +2428 1866 2410 1884 Dl +2463 1831 2445 1849 Dl +2499 1797 2481 1815 Dl +2522 1786 2499 1797 Dl +2566 1763 2543 1774 Dl +2609 1741 2586 1752 Dl +2653 1719 2630 1730 Dl +2698 1697 2675 1708 Dl +2742 1675 2719 1686 Dl +2786 1653 2763 1664 Dl +2831 1631 2808 1642 Dl +2874 1609 2851 1620 Dl +2918 1587 2895 1598 Dl +2963 1565 2940 1576 Dl +3007 1542 2984 1553 Dl +3027 1530 3006 1542 Dl +3072 1504 3051 1516 Dl +3116 1477 3095 1489 Dl +3160 1451 3139 1463 Dl +3204 1424 3183 1436 Dl +3249 1397 3228 1409 Dl +3293 1371 3272 1383 Dl +3337 1345 3316 1357 Dl +3381 1318 3360 1330 Dl +3425 1291 3404 1303 Dl +3470 1265 3449 1277 Dl +3514 1238 3493 1250 Dl +3540 1235 3515 1237 Dl +3588 1230 3563 1232 Dl +3637 1224 3612 1226 Dl +3685 1219 3660 1221 Dl +3733 1214 3708 1216 Dl +3781 1209 3756 1211 Dl +3830 1204 3805 1206 Dl +3878 1198 3853 1200 Dl +3926 1193 3901 1195 Dl +3974 1188 3949 1190 Dl +4023 1182 3998 1184 Dl +4047 1174 4023 1181 Dl +4095 1161 4071 1168 Dl +4144 1147 4120 1154 Dl +4192 1134 4168 1141 Dl +4241 1120 4217 1127 Dl +4289 1106 4265 1113 Dl +4337 1093 4313 1100 Dl +4386 1080 4362 1087 Dl +4434 1066 4410 1073 Dl +4482 1052 4458 1059 Dl +4531 1039 4507 1046 Dl +(T)4582 1036 w +1990 2509 1482 2661 Dl +2498 2483 1990 2508 Dl +3007 2306 2499 2483 Dl +(R)3057 2326 w +1507 3371 1482 3372 Dl +1555 3368 1530 3369 Dl +1603 3366 1578 3367 Dl +1652 3364 1627 3365 Dl +1700 3361 1675 3362 Dl +1748 3359 1723 3360 Dl +1796 3357 1771 3358 Dl +1845 3354 1820 3355 Dl +1893 3352 1868 3353 Dl +1941 3349 1916 3350 Dl +1989 3347 1964 3348 Dl +2015 3344 1990 3347 Dl +2064 3336 2039 3339 Dl +2112 3329 2087 3332 Dl +2160 3321 2135 3324 Dl +2208 3314 2183 3317 Dl +2257 3307 2232 3310 Dl +2305 3300 2280 3303 Dl +2353 3293 2328 3296 Dl +2401 3285 2376 3288 Dl +2450 3278 2425 3281 Dl +2498 3271 2473 3274 Dl +2524 3269 2499 3270 Dl +2572 3267 2547 3268 Dl +2620 3264 2595 3265 Dl +2668 3262 2643 3263 Dl +2717 3259 2692 3260 Dl +2765 3257 2740 3258 Dl +2813 3255 2788 3256 Dl +2861 3252 2836 3253 Dl +2910 3250 2885 3251 Dl +2958 3247 2933 3248 Dl +3006 3245 2981 3246 Dl +(S)3057 3267 w +1990 3321 1482 3422 Dl +2498 3118 1990 3321 Dl +3007 3093 2499 3118 Dl +(N)3057 3115 w +1990 1523 1482 1802 Dl +2498 1562 1990 1522 Dl +3007 1715 2499 1563 Dl +(L)3057 1737 w +11 B f +(Fig. 5. Single Search Enhancement \(NC\).)5 1922 1 2056 3913 t +cleartomark +showpage +saveobj restore +%%EndPage: 26 26 +%%Page: 27 27 +/saveobj save def +mark +27 pagesetup +11 R f +(- 27 -)2 238 1 2761 490 t +974 882 974 3422 Dl +5039 882 974 882 Dl +5040 3422 5040 882 Dl +975 3422 5040 3422 Dl +(%)629 2174 w +(depth)2884 3699 w +974 3473 974 3422 Dl +(2)947 3556 w +1482 3473 1482 3422 Dl +(3)1455 3556 w +1990 3473 1990 3422 Dl +(4)1963 3556 w +2499 3473 2499 3422 Dl +(5)2472 3556 w +3006 3473 3006 3422 Dl +(6)2979 3556 w +3515 3473 3515 3422 Dl +(7)3488 3556 w +4023 3473 4023 3422 Dl +(8)3996 3556 w +4531 3473 4531 3422 Dl +(9)4504 3556 w +5040 3473 5040 3422 Dl +(10)4985 3556 w +923 3422 974 3422 Dl +(70)813 3444 w +923 2999 974 2999 Dl +(75)813 3021 w +923 2576 974 2576 Dl +(80)813 2598 w +923 2152 974 2152 Dl +(85)813 2174 w +923 1728 974 1728 Dl +(90)813 1750 w +923 1305 974 1305 Dl +(95)813 1327 w +923 882 974 882 Dl +(100)758 904 w +6 R f +1506 1532 1482 1525 Dl +1554 1547 1530 1540 Dl +1602 1561 1578 1554 Dl +1651 1576 1627 1569 Dl +1700 1591 1676 1584 Dl +1748 1605 1724 1598 Dl +1796 1619 1772 1612 Dl +1844 1634 1820 1627 Dl +1893 1648 1869 1641 Dl +1942 1663 1918 1656 Dl +1990 1678 1966 1671 Dl +2011 1690 1990 1678 Dl +2055 1716 2034 1704 Dl +2100 1742 2079 1730 Dl +2144 1767 2123 1755 Dl +2188 1793 2167 1781 Dl +2232 1819 2211 1807 Dl +2276 1845 2255 1833 Dl +2321 1871 2300 1859 Dl +2365 1896 2344 1884 Dl +2409 1922 2388 1910 Dl +2453 1948 2432 1936 Dl +2497 1974 2476 1962 Dl +2519 1989 2499 1974 Dl +2559 2018 2539 2003 Dl +2599 2048 2579 2033 Dl +2640 2077 2620 2062 Dl +2681 2105 2661 2090 Dl +2722 2135 2702 2120 Dl +2762 2164 2742 2149 Dl +2803 2193 2783 2178 Dl +2843 2222 2823 2207 Dl +2884 2252 2864 2237 Dl +2925 2280 2905 2265 Dl +2965 2310 2945 2295 Dl +3006 2339 2986 2324 Dl +(HK)3087 2351 w +1990 1594 1482 2466 Dl +2498 1728 1990 1593 Dl +3007 2473 2499 1728 Dl +(HN)3087 2460 w +4 R f +(.)1476 2593 w +(.)1488 2572 w +(.)1501 2550 w +(.)1514 2528 w +(.)1526 2506 w +(.)1539 2485 w +(.)1552 2463 w +(.)1565 2441 w +(.)1578 2419 w +(.)1590 2397 w +(.)1603 2376 w +(.)1616 2353 w +(.)1629 2332 w +(.)1641 2310 w +(.)1654 2288 w +(.)1667 2266 w +(.)1679 2245 w +(.)1692 2222 w +(.)1704 2201 w +(.)1717 2179 w +(.)1730 2158 w +(.)1742 2135 w +(.)1755 2114 w +(.)1768 2092 w +(.)1781 2070 w +(.)1794 2048 w +(.)1806 2027 w +(.)1819 2005 w +(.)1832 1983 w +(.)1845 1961 w +(.)1857 1939 w +(.)1870 1917 w +(.)1883 1896 w +(.)1895 1874 w +(.)1908 1852 w +(.)1920 1830 w +(.)1933 1808 w +(.)1946 1787 w +(.)1958 1765 w +(.)1971 1743 w +(. .)1 10 1 1984 1721 t +(.)2008 1729 w +(.)2033 1738 w +(.)2057 1747 w +(.)2081 1755 w +(.)2105 1764 w +(.)2129 1772 w +(.)2154 1780 w +(.)2178 1789 w +(.)2202 1798 w +(.)2226 1806 w +(.)2250 1814 w +(.)2274 1823 w +(.)2299 1831 w +(.)2323 1839 w +(.)2347 1848 w +(.)2372 1857 w +(.)2395 1865 w +(.)2420 1873 w +(.)2444 1882 w +(.)2468 1891 w +(. .)1 10 1 2493 1899 t +(.)2513 1914 w +(.)2533 1930 w +(.)2553 1946 w +(.)2574 1961 w +(.)2594 1977 w +(.)2614 1993 w +(.)2634 2008 w +(.)2655 2024 w +(.)2676 2040 w +(.)2696 2055 w +(.)2716 2071 w +(.)2736 2086 w +(.)2757 2101 w +(.)2777 2117 w +(.)2797 2132 w +(.)2817 2148 w +(.)2838 2164 w +(.)2858 2179 w +(.)2879 2195 w +(.)2899 2211 w +(.)2920 2226 w +(.)2940 2242 w +(.)2960 2258 w +(.)2980 2273 w +(.)3000 2289 w +6 R f +(HR)3087 2300 w +1494 2368 1482 2389 Dl +1520 2324 1508 2345 Dl +1546 2279 1534 2300 Dl +1572 2234 1560 2255 Dl +1598 2189 1586 2210 Dl +1624 2144 1612 2165 Dl +1650 2100 1638 2121 Dl +1676 2055 1664 2076 Dl +1703 2010 1691 2031 Dl +1729 1966 1717 1987 Dl +1755 1920 1743 1941 Dl +1781 1876 1769 1897 Dl +1806 1831 1794 1852 Dl +1833 1786 1821 1807 Dl +1859 1742 1847 1763 Dl +1885 1697 1873 1718 Dl +1911 1652 1899 1673 Dl +1938 1607 1926 1628 Dl +1963 1563 1951 1584 Dl +1989 1518 1977 1539 Dl +2015 1517 1990 1517 Dl +2069 1517 2044 1517 Dl +2123 1517 2098 1517 Dl +2176 1517 2151 1517 Dl +2230 1517 2205 1517 Dl +2283 1517 2258 1517 Dl +2337 1517 2312 1517 Dl +2390 1517 2365 1517 Dl +2444 1517 2419 1517 Dl +2498 1517 2473 1517 Dl +2513 1537 2499 1517 Dl +2541 1580 2527 1560 Dl +2570 1622 2556 1602 Dl +2600 1665 2586 1645 Dl +2629 1707 2615 1687 Dl +2657 1750 2643 1730 Dl +2687 1792 2673 1772 Dl +2716 1835 2702 1815 Dl +2744 1878 2730 1858 Dl +2774 1920 2760 1900 Dl +2803 1963 2789 1943 Dl +2832 2005 2818 1985 Dl +2861 2048 2847 2028 Dl +2890 2091 2876 2071 Dl +2919 2133 2905 2113 Dl +2948 2176 2934 2156 Dl +2977 2218 2963 2198 Dl +3007 2261 2993 2241 Dl +(HS)3087 2223 w +1501 2473 1482 2457 Dl +1538 2506 1519 2490 Dl +1576 2538 1557 2522 Dl +1614 2571 1595 2555 Dl +1651 2603 1632 2587 Dl +1689 2636 1670 2620 Dl +1726 2669 1707 2653 Dl +1765 2701 1746 2685 Dl +1802 2734 1783 2718 Dl +1839 2767 1820 2751 Dl +1877 2799 1858 2783 Dl +1915 2831 1896 2815 Dl +1952 2865 1933 2849 Dl +1990 2897 1971 2881 Dl +2006 2879 1990 2898 Dl +2039 2840 2023 2859 Dl +2072 2801 2056 2820 Dl +2104 2762 2088 2781 Dl +2137 2723 2121 2742 Dl +2170 2685 2154 2704 Dl +2203 2646 2187 2665 Dl +2235 2607 2219 2626 Dl +2268 2568 2252 2587 Dl +2302 2529 2286 2548 Dl +2334 2490 2318 2509 Dl +2367 2452 2351 2471 Dl +2399 2413 2383 2432 Dl +2433 2374 2417 2393 Dl +2465 2336 2449 2355 Dl +2498 2297 2482 2316 Dl +2522 2305 2499 2296 Dl +2570 2325 2547 2316 Dl +2618 2344 2595 2335 Dl +2667 2363 2644 2354 Dl +2715 2382 2692 2373 Dl +2764 2402 2741 2393 Dl +2812 2421 2789 2412 Dl +2861 2441 2838 2432 Dl +2909 2460 2886 2451 Dl +2957 2480 2934 2471 Dl +3006 2499 2983 2490 Dl +(KR)3087 2537 w +4 R f +(.)1476 2662 w +(.)1495 2678 w +(.)1515 2695 w +(.)1534 2711 w +(.)1554 2728 w +(.)1574 2744 w +(.)1593 2761 w +(.)1613 2778 w +(.)1632 2794 w +(.)1652 2811 w +(.)1671 2827 w +(.)1691 2844 w +(.)1711 2861 w +(.)1730 2878 w +(.)1750 2894 w +(.)1769 2911 w +(.)1788 2927 w +(.)1808 2944 w +(.)1828 2960 w +(.)1848 2977 w +(.)1867 2994 w +(.)1886 3010 w +(.)1906 3027 w +(.)1925 3043 w +(.)1945 3060 w +(.)1965 3077 w +(. .)1 10 1 1984 3094 t +(.)1999 3073 w +(.)2015 3054 w +(.)2030 3034 w +(.)2046 3014 w +(.)2061 2994 w +(.)2076 2975 w +(.)2092 2955 w +(.)2107 2935 w +(.)2123 2916 w +(.)2138 2896 w +(.)2154 2876 w +(.)2169 2856 w +(.)2184 2837 w +(.)2200 2816 w +(.)2215 2797 w +(.)2231 2777 w +(.)2246 2757 w +(.)2262 2737 w +(.)2277 2718 w +(.)2292 2698 w +(.)2308 2678 w +(.)2323 2659 w +(.)2339 2639 w +(.)2354 2619 w +(.)2369 2599 w +(.)2385 2580 w +(.)2400 2559 w +(.)2416 2540 w +(.)2431 2521 w +(.)2446 2500 w +(.)2462 2481 w +(.)2477 2461 w +(. .)1 10 1 2493 2441 t +(.)2514 2453 w +(.)2537 2464 w +(.)2559 2475 w +(.)2580 2487 w +(.)2603 2498 w +(.)2625 2510 w +(.)2647 2521 w +(.)2669 2533 w +(.)2691 2544 w +(.)2713 2555 w +(.)2735 2567 w +(.)2758 2578 w +(.)2780 2590 w +(.)2802 2601 w +(.)2824 2613 w +(.)2846 2623 w +(.)2868 2635 w +(.)2890 2647 w +(.)2912 2658 w +(.)2934 2670 w +(.)2956 2681 w +(.)2979 2693 w +(.)3000 2703 w +6 R f +(KS)3087 2714 w +1500 2907 1482 2889 Dl +1535 2943 1517 2925 Dl +1570 2978 1552 2960 Dl +1605 3014 1587 2996 Dl +1640 3049 1622 3031 Dl +1675 3085 1657 3067 Dl +1710 3121 1692 3103 Dl +1745 3156 1727 3138 Dl +1780 3192 1762 3174 Dl +1815 3227 1797 3209 Dl +1850 3263 1832 3245 Dl +1885 3299 1867 3281 Dl +1920 3335 1902 3317 Dl +1955 3370 1937 3352 Dl +1990 3406 1972 3388 Dl +2002 3385 1990 3406 Dl +2028 3342 2016 3363 Dl +2054 3298 2042 3319 Dl +2080 3256 2068 3277 Dl +2106 3213 2094 3234 Dl +2133 3170 2121 3191 Dl +2159 3127 2147 3148 Dl +2184 3084 2172 3105 Dl +2210 3041 2198 3062 Dl +2236 2997 2224 3018 Dl +2263 2955 2251 2976 Dl +2289 2912 2277 2933 Dl +2315 2869 2303 2890 Dl +2341 2826 2329 2847 Dl +2367 2783 2355 2804 Dl +2393 2740 2381 2761 Dl +2419 2697 2407 2718 Dl +2445 2654 2433 2675 Dl +2471 2611 2459 2632 Dl +2497 2568 2485 2589 Dl +2521 2578 2499 2567 Dl +2565 2601 2543 2590 Dl +2608 2624 2586 2613 Dl +2653 2646 2631 2635 Dl +2697 2669 2675 2658 Dl +2741 2693 2719 2682 Dl +2786 2715 2764 2704 Dl +2830 2738 2808 2727 Dl +2873 2761 2851 2750 Dl +2917 2783 2895 2772 Dl +2962 2806 2940 2795 Dl +3006 2829 2984 2818 Dl +(KN)3087 2842 w +1990 1357 1482 2483 Dl +2498 1043 1990 1356 Dl +3007 959 2499 1043 Dl +3514 892 3006 958 Dl +4023 907 3515 892 Dl +4531 887 4023 907 Dl +(HT)4612 950 w +4 R f +(.)1476 2271 w +(.)1499 2283 w +(.)1522 2294 w +(.)1545 2305 w +(.)1568 2316 w +(.)1591 2328 w +(.)1614 2338 w +(.)1637 2350 w +(.)1661 2361 w +(.)1684 2372 w +(.)1707 2383 w +(.)1730 2395 w +(.)1753 2406 w +(.)1776 2417 w +(.)1799 2428 w +(.)1822 2439 w +(.)1845 2451 w +(.)1868 2461 w +(.)1891 2473 w +(.)1914 2484 w +(.)1938 2495 w +(.)1961 2506 w +(. .)1 10 1 1984 2518 t +(.)1995 2495 w +(.)2007 2472 w +(.)2018 2449 w +(.)2029 2425 w +(.)2040 2402 w +(.)2052 2379 w +(.)2064 2356 w +(.)2074 2333 w +(.)2086 2311 w +(.)2097 2288 w +(.)2108 2265 w +(.)2120 2242 w +(.)2131 2219 w +(.)2142 2196 w +(.)2154 2173 w +(.)2165 2150 w +(.)2176 2127 w +(.)2187 2104 w +(.)2199 2081 w +(.)2210 2058 w +(.)2221 2035 w +(.)2233 2012 w +(.)2244 1989 w +(.)2255 1966 w +(.)2267 1943 w +(.)2278 1920 w +(.)2289 1897 w +(.)2300 1875 w +(.)2312 1852 w +(.)2323 1829 w +(.)2334 1806 w +(.)2346 1783 w +(.)2357 1759 w +(.)2368 1736 w +(.)2380 1713 w +(.)2390 1690 w +(.)2402 1667 w +(.)2413 1645 w +(.)2424 1622 w +(.)2436 1599 w +(.)2447 1576 w +(.)2459 1553 w +(.)2470 1530 w +(.)2481 1507 w +(. .)1 10 1 2493 1484 t +(.)2518 1481 w +(.)2543 1478 w +(.)2568 1475 w +(.)2594 1472 w +(.)2619 1469 w +(.)2645 1466 w +(.)2670 1463 w +(.)2696 1460 w +(.)2721 1457 w +(.)2747 1454 w +(.)2772 1451 w +(.)2797 1448 w +(.)2822 1446 w +(.)2848 1443 w +(.)2874 1440 w +(.)2899 1436 w +(.)2925 1433 w +(.)2950 1430 w +(.)2975 1428 w +(. .)1 10 1 3000 1425 t +(.)3020 1408 w +(.)3040 1392 w +(.)3059 1375 w +(.)3079 1358 w +(.)3098 1342 w +(.)3118 1325 w +(.)3138 1309 w +(.)3157 1292 w +(.)3177 1276 w +(.)3196 1259 w +(.)3216 1243 w +(.)3235 1226 w +(.)3254 1209 w +(.)3275 1193 w +(.)3294 1176 w +(.)3313 1160 w +(.)3333 1143 w +(.)3352 1127 w +(.)3372 1110 w +(.)3391 1093 w +(.)3411 1077 w +(.)3431 1060 w +(.)3450 1044 w +(.)3470 1027 w +(.)3489 1011 w +( .)1 25( .)1 26( .)1 25( .)1 26( .)1 25( .)1 26( . . .)3 75( .)1 26( .)1 25( . .)2 52( . . .)3 75( .)1 26( .)1 25( .)1 26( .)1 25(. .)1 10 16 3509 994 t +6 R f +(KT)4104 1005 w +3006 2754 2651 3422 Dl +(NT)3087 2766 w +4 R f +(.)2747 3423 w +(.)2760 3402 w +(.)2773 3380 w +(.)2786 3358 w +(.)2800 3336 w +(.)2813 3315 w +(.)2827 3292 w +(.)2840 3271 w +(.)2853 3249 w +(.)2867 3227 w +(.)2880 3205 w +(.)2894 3184 w +(.)2907 3161 w +(.)2920 3140 w +(.)2934 3118 w +(.)2947 3096 w +(.)2961 3074 w +(.)2974 3053 w +(.)2987 3030 w +(.)3000 3009 w +6 R f +(RT)3087 3020 w +2812 3399 2803 3422 Dl +2832 3353 2823 3376 Dl +2851 3306 2842 3329 Dl +2871 3259 2862 3282 Dl +2890 3213 2881 3236 Dl +2909 3166 2900 3189 Dl +2928 3119 2919 3142 Dl +2948 3073 2939 3096 Dl +2967 3026 2958 3049 Dl +2986 2979 2977 3002 Dl +3006 2932 2997 2955 Dl +(ST)3087 2943 w +10 B f +(Fig. 6. Two Search Enhancements \(NC\).)5 1710 1 2162 3913 t +cleartomark +showpage +saveobj restore +%%EndPage: 27 27 +%%Page: 28 28 +/saveobj save def +mark +28 pagesetup +11 R f +(- 28 -)2 238 1 2761 490 t +11 B f +(Fig. 1. The History Heuristic and Alpha-Beta.)6 2148 1 995 840 t +(Fig. 2. History Heuristic Example.)4 1607 1 995 1200 t +(Fig. 3. Single Search Enhancement \(NBP\).)5 1984 1 995 1560 t +(Fig. 4. Two Search Enhancements \(NBP\).)5 1946 1 995 1920 t +(Fig. 5. Single Search Enhancement \(NC\).)5 1922 1 995 2280 t +(Fig. 6. Two Search Enhancements \(NC\).)5 1884 1 995 2640 t +cleartomark +showpage +saveobj restore +%%EndPage: 28 28 +%%Trailer +done +%%Pages: 28 +%%DocumentFonts: Times-Bold Courier Times-Italic Times-Roman Symbol Times-Roman -- cgit v1.3