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