path: root/parallel/pami.ps

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