4 <meta http-equiv="Content-Language" content="en-us">
\r
5 <meta name="GENERATOR" content="Microsoft FrontPage 5.0">
\r
6 <meta name="ProgId" content="FrontPage.Editor.Document">
\r
7 <meta http-equiv="Content-Type" content="text/html; charset=windows-1252">
\r
8 <title>Verified Null-Move Pruning</title>
\r
11 <body bgcolor="#FFFFFF" topmargin="50" leftmargin="100">
\r
13 <div align="center">
\r
15 <table border="0" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="580" id="AutoNumber5">
\r
18 <div align="center">
\r
20 <table border="0" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="100%" id="AutoNumber2">
\r
23 <p align="left"> </td>
\r
25 <p align="center"><font face="Times New Roman" size="2">Verified
\r
26 Null-Move Pruning</font></td>
\r
28 <p align="right"><font face="Times New Roman" size="2">153</font></td>
\r
33 <font FACE="Times New Roman"><b>
\r
34 <p ALIGN="center"> </p>
\r
35 <p ALIGN="center">VERIFIED NULL-MOVE PRUNING</p>
\r
36 </b><font FACE="Times New Roman" SIZE="2"><i>
\r
37 <p ALIGN="center">Omid David Tabibi </i><sup>1</sup><i>
\r
38 Nathan S. Netanyahu </i><sup>2</sup></p>
\r
39 <p ALIGN="center">Ramat-Gan, Israel</p>
\r
40 <p ALIGN="center">ABSTRACT</p>
\r
42 <div align="center">
\r
44 <table border="0" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" dir="ltr" id="AutoNumber1" width="520">
\r
46 <td><font FACE="Times New Roman" SIZE="2">
\r
47 <p ALIGN="justify">In this article we review standard null-move
\r
48 pruning and introduce our extended version of it, which we call <i>
\r
49 verified null-move pruning</i>. In verified null-move pruning,
\r
50 whenever the shallow null-move search indicates a fail-high, instead
\r
51 of cutting off the search from the current node, the search is
\r
52 continued with reduced depth.</p>
\r
53 <p ALIGN="justify">Our experiments with verified null-move pruning
\r
54 show that on average, it constructs a smaller search tree with
\r
55 greater tactical strength in comparison to standard null-move
\r
56 pruning. Moreover, unlike standard null-move pruning, which fails
\r
57 badly in zugzwang positions, verified null-move pruning manages to
\r
58 detect most zugzwangs and in such cases conducts a re-search to
\r
59 obtain the correct result. In addition, verified null-move pruning
\r
60 is very easy to implement, and any standard null-move pruning
\r
61 program can use verified null-move pruning by modifying only a few
\r
62 lines of code.</font></td>
\r
67 <p ALIGN="justify"><b><font size="2">1. INTRODUCTION</font></b></p>
\r
68 <font FACE="Times New Roman" SIZE="2">
\r
69 <p ALIGN="justify">Until the mid-1970s most chess programs were trying to
\r
70 search the same way humans think, by generating
\93plausible
\94 moves. By
\r
71 using extensive chess knowledge at each node, these programs selected a
\r
72 few moves which they considered plausible, and thus pruned large parts of
\r
73 the search tree. However, plausible move generating programs had serious
\r
74 tactical shortcomings, and as soon as brute-force search programs like
\r
75 TECH (Gillogy, 1972) and CHESS 4.X (Slate and Atkin, 1977) managed to
\r
76 reach depths of 5 plies and more, plausible-move generating programs
\r
77 frequently lost to brute-force searchers due to their tactical weaknesses.</p>
\r
78 <p ALIGN="justify">Brute-force searchers rapidly dominated the
\r
79 computer-chess field. Most brute-force searchers of that time used no
\r
80 selectivity in their full-width search tree, except for some extensions,
\r
81 consisting mostly of check extensions and recaptures. The most successful
\r
82 of these brute-force programs were BELLE (Condon and Thompson, 1983a,b),
\r
83 DEEP THOUGHT (Hsu, Anantharaman, Campbell, and Nowatzyk, 1990), HITECH
\r
84 (Berliner and Ebeling, 1990; Berliner, 1987; Ebeling, 1986), and CRAY
\r
85 BLITZ (Hyatt, Gower, and Nelson, 1990), which for the first time managed
\r
86 to compete successfully against humans.</font></p>
\r
87 <p ALIGN="justify"><font FACE="Times New Roman" SIZE="2">The introduction
\r
88 of null-move pruning (Beal, 1989; Goetsch and Campbell, 1990; Donninger,
\r
89 1993) in the early 1990s marked the end of an era, as far as the
\r
90 domination of brute-force programs in computer chess is concerned. Unlike
\r
91 other forward-pruning methods (e.g., <i>razoring </i>(Birmingham and Kent,
\r
92 1977), GAMMA (Newborn, 1975), and <i>marginal forward pruning </i>(Slagle,
\r
93 1971)), which had great tactical weaknesses, null-move pruning enabled
\r
94 programs to search more deeply with minor tactical risks. Forward-pruning
\r
95 programs frequently outsearched brute-force searchers, and started their
\r
96 own reign which has continued ever since; they have won all World
\r
97 Computer-Chess Championships since 1992 (van den Herik and Herschberg,
\r
98 1992; Tsang and Beal, 1995; Feist, 1999). DEEP BLUE (Hammilton and Garber,
\r
99 1997; Hsu, 1999) (the direct descendant of DEEP THOUGHT (Hsu <i>et al.</i>,
\r
100 1990)) was probably the last brute-force searcher. Today almost all top
\r
101 tournament playing programs use forward-pruning methods, null-move pruning
\r
102 being the most popular of them (Feist, 1999).</font></p>
\r
103 <font FACE="Times New Roman" SIZE="1">
\r
104 <hr noshade color="#000000" align="justify" width="35%" size="1">
\r
105 <p ALIGN="justify"><sup>1</sup> Department of Computer Science, Bar-Ilan
\r
106 University, Ramat-Gan 52900, Israel, Email:
\r
108 <a href="Http://www.cs.biu.ac.il/~davoudo">
\r
109 Http://www.cs.biu.ac.il/~davoudo</a><sup><br>
\r
110 2</sup> Department of Computer Science, Bar-Ilan University, Ramat-Gan
\r
113 Maryland, College Park, MD 20742, USA, Email:
\r
115 <font FACE="Times New Roman" SIZE="1"><hr>
\r
117 <table border="0" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="100%" id="AutoNumber2">
\r
120 <p align="left"><font face="Times New Roman" size="2">154</font></td>
\r
121 <td width="33%"><font FACE="Times New Roman" SIZE="2">
\r
122 <p ALIGN="center">ICGA Journal</font></td>
\r
124 <p align="right"><font size="2">September 2002</font></td>
\r
127 </font><font FACE="Times New Roman" SIZE="2">
\r
128 <p align="justify">In this article we introduce our new <i>verified
\r
129 null-move pruning </i>method, and demonstrate empirically its improved
\r
130 performance in comparison with standard null-move pruning. This is
\r
131 reflected in its reduced search tree size, as well as its greater tactical
\r
132 strength. In Section 2 we review standard null-move pruning, and in
\r
133 Section 3 we introduce verified null-move pruning. Section 4 presents our
\r
134 experimental results, and Section 5 contains concluding remarks.</p>
\r
136 <p align="justify">2. STANDARD NULL-MOVE PRUNING</p>
\r
138 <p align="justify">As mentioned earlier, brute-force programs refrained
\r
139 from pruning any nodes in the full-width part of the search tree, deeming
\r
140 the risks of doing so as being too high. Null-move (Beal, 1989; Goetsch
\r
141 and Campbell, 1990; Donninger, 1993) introduced a new pruning scheme which
\r
142 based its cutoff decisions on dynamic criteria, and thus gained greater
\r
143 tactical strength in comparison with the static forward pruning methods
\r
144 that were in use at that time.</p>
\r
145 <div align="center">
\r
147 <table border="1" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" id="AutoNumber3">
\r
149 <td><font FACE="Times New Roman" SIZE="2">
\r
150 <p ALIGN="LEFT">/* the depth reduction factor */</font><font FACE="Courier" SIZE="2"><br>
\r
152 int search (alpha, beta, depth) {<br>
\r
153 if (depth </font><font FACE="CMMI10" SIZE="2"><</font><font FACE="Courier" SIZE="2">=
\r
155 return evaluate(); </font>
\r
156 <font FACE="Times New Roman" SIZE="2">/* in practice, quiescence()
\r
157 is called here */<br>
\r
158 <font FACE="Courier" SIZE="2"> </font>/* conduct a null-move search if it is legal and desired */<br>
\r
159 </font><font FACE="Courier" SIZE="2"> if (</font><font FACE="CMR10" SIZE="2">!</font><font FACE="Courier" SIZE="2">in_check()
\r
160 && null_ok()) {<br>
\r
161 make_null_move();<br>
\r
162 </font>/* null-move search with
\r
163 minimal window around beta */<br>
\r
164 <font FACE="Courier" SIZE="2">
\r
165 value = -search(-beta, -beta + 1, depth - R - 1);<br>
\r
166 if (value </font>
\r
167 <font FACE="CMMI10" SIZE="2">></font><font FACE="Courier" SIZE="2">=
\r
168 beta) </font><font FACE="Times New Roman" SIZE="2">/* cutoff in case
\r
169 of fail-high */<br>
\r
170 <font FACE="Courier" SIZE="2">
\r
171 </font></font><font FACE="Courier" SIZE="2">
\r
173 }<br>
\r
174 </font><font FACE="Times New Roman" SIZE="2">/* continue
\r
175 regular NegaScout/PVS search */<br>
\r
176 <font FACE="Courier" SIZE="2"> </font>. . .<br>
\r
177 <font FACE="Courier" SIZE="2">}</font></font></td>
\r
180 <p><b>Figure 1</b>: Standard null-move pruning.</p>
\r
183 <p ALIGN="justify">There are positions in chess where any move will
\r
184 deteriorate the position, so that not making a move is the best option.
\r
185 These positions are called <i>zugzwang </i>positions. While zugzwang
\r
186 positions are rare in the middle game, they are not an exception in
\r
187 endgames, especially endgames in which one or both sides are left with
\r
188 King and Pawns. Null-move pruning will fail badly in zugzwang positions
\r
189 since the basic assumption behind the method does not hold. In fact, the
\r
190 null-move search
\92s value is an upper bound in such cases. As a result,
\r
191 null-move pruning is avoided in such endgame positions.</p>
\r
192 </font><font FACE="Times New Roman" SIZE="1"><hr>
\r
193 <p ALIGN="justify"> </p>
\r
194 <table border="0" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="100%" id="AutoNumber2">
\r
197 <p align="left"> </td>
\r
199 <p align="center"><font face="Times New Roman" size="2">Verified
\r
200 Null-Move Pruning</font></td>
\r
202 <p align="right"><font face="Times New Roman" size="2">155</font></td>
\r
205 </font><font FACE="Times New Roman" SIZE="2">
\r
206 <p ALIGN="justify">As previously noted, the major benefit of null-move
\r
207 pruning stems from the depth reduction in the null-move searches. However,
\r
208 these reduced-depth searches are liable to tactical weaknesses due to the
\r
209 <i>horizon effect </i>(Berliner, 1974). A horizon effect results whenever
\r
210 the reduced-depth search misses a tactical threat. Such a threat would not
\r
211 have been missed, had we conducted a search without any depth reduction.
\r
212 The greater the depth reduction </font><font FACE="CMMI10" SIZE="2">R</font><font FACE="Times New Roman" SIZE="2">,
\r
213 the greater the tactical risk due to the horizon effect. So, the saving
\r
214 resulting from null-move pruning depends on the depth reduction factor,
\r
215 since a shallower search (i.e., a greater </font>
\r
216 <font FACE="CMMI10" SIZE="2">R</font><font FACE="Times New Roman" SIZE="2">)
\r
217 will result in faster null-move searches and an overall smaller search
\r
219 <p ALIGN="justify">In the early days of null-move pruning, most programs
\r
220 used </font><font FACE="CMMI10" SIZE="2">R </font>
\r
221 <font FACE="CMR10" SIZE="2">= 1</font><font FACE="Times New Roman" SIZE="2">,
\r
222 which ensures the least tactical risk, but offers the least saving in
\r
223 comparison with other </font><font FACE="CMMI10" SIZE="2">R </font>
\r
224 <font FACE="Times New Roman" SIZE="2">values. Other reduction factors that
\r
225 were experimented with were </font><font FACE="CMMI10" SIZE="2">R </font>
\r
226 <font FACE="CMR10" SIZE="2">= 2 </font>
\r
227 <font FACE="Times New Roman" SIZE="2">and </font>
\r
228 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3</font><font FACE="Times New Roman" SIZE="2">.
\r
229 Research conducted over the years, most extensively by Heinz (1999),
\r
230 showed that overall, </font><font FACE="CMMI10" SIZE="2">R </font>
\r
231 <font FACE="CMR10" SIZE="2">= 2 </font>
\r
232 <font FACE="Times New Roman" SIZE="2">performs better than the too
\r
233 conservative </font><font FACE="CMMI10" SIZE="2">R </font>
\r
234 <font FACE="CMR10" SIZE="2">= 1 </font>
\r
235 <font FACE="Times New Roman" SIZE="2">and the too aggressive </font>
\r
236 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3</font><font FACE="Times New Roman" SIZE="2">.
\r
237 Today, almost all null-move pruning programs, use at least </font>
\r
238 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 2
\r
239 </font><font FACE="Times New Roman" SIZE="2">(Feist, 1999). However, using
\r
240 </font><font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
\r
241 3 </font><font FACE="Times New Roman" SIZE="2">is tempting, considering
\r
242 the reduced search effort resulting from shallower null-move searches.
\r
243 (This will be demonstrated in Section 4.) Donninger (1993) was the first
\r
244 to suggest an adaptive rather than a fixed value for </font>
\r
245 <font FACE="CMMI10" SIZE="2">R</font><font FACE="Times New Roman" SIZE="2">.
\r
246 Experiments conducted by Heinz (1999), in his article on adaptive
\r
247 null-move pruning, suggest that using </font><font FACE="CMMI10" SIZE="2">
\r
248 R </font><font FACE="CMR10" SIZE="2">= 3 </font>
\r
249 <font FACE="Times New Roman" SIZE="2">in upper parts of the search tree
\r
250 and </font><font FACE="CMMI10" SIZE="2">R </font>
\r
251 <font FACE="CMR10" SIZE="2">= 2 </font>
\r
252 <font FACE="Times New Roman" SIZE="2">in its lower parts can save 10 to 30
\r
253 percent of the search effort in comparison with a fixed </font>
\r
254 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 2</font><font FACE="Times New Roman" SIZE="2">,
\r
255 while maintaining overall tactical strength.</p>
\r
256 <p align="justify">In the next section we present a new null-move pruning
\r
257 method which allows the use of </font><font FACE="CMMI10" SIZE="2">R
\r
258 </font><font FACE="CMR10" SIZE="2">= 3 </font>
\r
259 <font FACE="Times New Roman" SIZE="2">in all parts of the search tree,
\r
260 while alleviating to a significant extent the main disadvantage of
\r
261 standard null-move pruning.</p>
\r
263 <p align="justify">3. VERIFIED NULL-MOVE PRUNING</p>
\r
265 <p align="justify">Cutoffs based on a shallow null-move search can be too
\r
266 risky at some points, especially in zugzwang positions. Goetsch and
\r
267 Campbell (1990) hinted at continuing the search with reduced depth, in
\r
268 case the null-move search indicates a fail-high, in order to substantiate
\r
269 that the value returned from the null-move search is indeed a lower bound
\r
270 on the position. Plenkner (1995) showed that this idea can help prevent
\r
271 errors due to zugzwangs. However, verifying the search in the middle game
\r
272 seems wasteful, as it appears to undermine the basic benefit of null-move
\r
273 pruning, namely that a cutoff is determined by a shallow null-move search.</p>
\r
274 <p ALIGN="justify">In addition to helping in detecting zugzwangs, the idea
\r
275 of not immediately pruning the search tree (based on the value returned
\r
276 from the shallow null-move search) can also help to reduce the tactical
\r
277 weaknesses caused by the horizon effect, since by continuing the search we
\r
278 may be able to detect threats which the shallow null-move search has
\r
279 failed to detect. Based on these ideas, we developed our own
\r
280 reformulation, which we call<i> verified null-move pruning</i>. At each
\r
281 node, we conduct a null-move search with a depth reduction of </font>
\r
282 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3</font><font FACE="Times New Roman" SIZE="2">.
\r
283 If the returned value from that null-move search indicates a fail-high
\r
284 (i.e., </font><i><font FACE="CMMI10" SIZE="2">value ≥ β</font></i><font SIZE="2" face="Times New Roman">),
\r
285 we then reduce the depth by one ply and continue the search in order to
\r
286 verify the cutoff. However, for that node
\92s subtree, we use standard
\r
287 null-move pruning (cutoff takes place upon fail-highs). See Figure 2, for
\r
288 an illustration.</font></p>
\r
289 <div align="center">
\r
291 <table border="1" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" id="AutoNumber4">
\r
293 <td><img border="0" src="example.gif" width="414" height="171"></td>
\r
296 <font FACE="Times New Roman" SIZE="2"><b>
\r
297 <p>Figure 2</b>: Illustration of verified null-move pruning.</p>
\r
300 <font FACE="Times New Roman" SIZE="2">
\r
301 <p align="justify">The basic idea behind verified null-move pruning is
\r
302 that null-move search with </font><font FACE="CMMI10" SIZE="2">R </font>
\r
303 <font FACE="CMR10" SIZE="2">= 3 </font>
\r
304 <font FACE="Times New Roman" SIZE="2">constructs a considerably smaller
\r
305 search tree. However, because of its tactical deficiencies, a cutoff based
\r
306 on it is too risky. So upon a fail-high, we reduce the depth and continue
\r
307 the search, using standard null-move pruning</font></p>
\r
308 <font FACE="Times New Roman" SIZE="1"><hr>
\r
310 <div align="center">
\r
312 <table border="0" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="100%" id="AutoNumber6">
\r
315 <p align="left"><font size="2">156</font></td>
\r
317 <p align="center"><font FACE="Times New Roman" SIZE="2">ICGA Journal</font></td>
\r
319 <p align="right"><font size="2">September 2002</font></td>
\r
325 <p align="justify"><font FACE="Times New Roman" SIZE="2">(with </font>
\r
326 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3</font><font FACE="Times New Roman" SIZE="2">)
\r
327 in that node
\92s subtree. The search at a node is thus cut off (based on its
\r
328 null-move search) only if there has been another null-move search
\r
329 fail-high indication in one of the node
\92s ancestors (see Figure 2). As the
\r
330 experimental results in the next section show, verified null-move pruning
\r
331 constructs a search tree which is close in size to that of standard
\r
332 null-move pruning with <font FACE="CMMI10" SIZE="2">R </font>
\r
333 <font FACE="CMR10" SIZE="2">= 3</font>, and whose tactical strength is
\r
334 greater on average than that of standard null-move pruning with
\r
335 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 2</font>.
\r
336 This is a smaller search tree with greater tactical strength, in
\r
337 comparison with standard null-move pruning with
\r
338 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 2</font>,
\r
339 which is commonly used nowadays.</font></p>
\r
340 <p align="justify"><font FACE="Times New Roman" SIZE="2">Since upon a
\r
341 fail-high indication we do not cut off the search at once, we have the
\r
342 ability to check whether the returned value is indeed a lower bound on the
\r
343 position. If the null-move search indicates a cutoff, but the search shows
\r
344 that the best value is smaller than </font><i>
\r
345 <font FACE="CMMI10" SIZE="2">β</font></i><font FACE="Times New Roman" SIZE="2">,
\r
346 this implies that the position is a zugzwang, as the value from the null
\r
347 move is greater than or equal to the value from the best move. In such
\r
348 cases, we restore the original depth (which was reduced by one ply after
\r
349 the fail-high indication), and conduct a re-search to obtain the correct
\r
351 <p align="justify">Implementation of verified null-move search is a matter
\r
352 of adding a few lines of code to standard null-move search, as shown in
\r
353 Figure 3. Regarding the pseudo-code presented, when the search starts at
\r
354 the root level, the flag <font FACE="Courier" SIZE="2">verify </font>is
\r
355 initialized to <font FACE="Courier" SIZE="2">true</font>. When the
\r
356 null-move search indicates a fail-high, the remaining depth is reduced by
\r
357 one ply, and <font FACE="Courier" SIZE="2">verify </font>is given the
\r
358 value <font FACE="Courier" SIZE="2">false</font>, which will be passed to
\r
359 the children of the current node, indicating that standard null-move
\r
360 pruning will be conducted with respect to the children. Upon a fail-high
\r
361 indication due to the standard null-move search of these children
\92s
\r
362 subtrees, cutoff takes place immediately.</p>
\r
364 <p align="justify">4. EXPERIMENTAL RESULTS</p>
\r
366 <p align="justify">In this section we examine the performance of verified
\r
367 null-move pruning, focusing on its tactical strength and smaller
\r
368 search-tree size in comparison with standard null-move pruning. We
\r
369 conducted our experiments using the G<font FACE="Times New Roman" SIZE="1">ENESIS<sup>3</sup>
\r
370 </font>engine. G<font FACE="Times New Roman" SIZE="1">ENESIS </font>is
\r
371 designed especially for research, emphasizing accurate implementation of
\r
372 algorithms and detailed statistics. For our experiments we used the N<font FACE="Times New Roman" SIZE="1">EGA</font>S<font FACE="Times New Roman" SIZE="1">COUT</font>/PVS
\r
373 (Campbell and Marsland, 1983; Reinefeld, 1983) search algorithm, with
\r
374 history heuristic (Schaeffer, 1983, 1989) and transposition table (Slate
\r
375 and Atkin, 1977; Nelson, 1985). To demonstrate the tactical strength
\r
376 differences between the different methods even better, we used one-ply
\r
377 check extensions on leaf nodes; the quiescence search consisted only of
\r
378 captures/recaptures. In all test suites used, we discarded positions in
\r
379 which at least one side had no more than King and Pawns. This was done to
\r
380 avoid dealing with zugzwang positions, for which verified null-move
\r
381 pruning obviously fares much better tactically, as explained before.</p>
\r
382 <p ALIGN="justify">In order to obtain an estimate of the search tree, we
\r
383 searched 138 test positions from <i>Test Your Tactical Ability </i>by
\r
384 Yakov Neishtadt (see the Appendix) to depths of 9 and 10 plies, using
\r
385 standard <font FACE="CMMI10" SIZE="2">R </font>
\r
386 <font FACE="CMR10" SIZE="2">= 1</font>, <font FACE="CMMI10" SIZE="2">R
\r
387 </font><font FACE="CMR10" SIZE="2">= 2</font>,
\r
388 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3</font>,
\r
389 and verified <font FACE="CMMI10" SIZE="2">R </font>
\r
390 <font FACE="CMR10" SIZE="2">= 3</font>. Table 1 gives the total node count
\r
391 for each method and the size of the tree in comparison with verified
\r
392 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3</font>.
\r
393 Table 2 gives the number of positions that each method solved correctly
\r
394 (i.e., found the correct variation for). Later we will further examine the
\r
395 tactical strength, using additional test suites.</p>
\r
396 <div align="center">
\r
398 <table border="1" cellpadding="3" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" id="AutoNumber7" height="88">
\r
400 <td align="center" valign="top" height="8">
\r
401 <font FACE="Times New Roman" SIZE="2">Depth</font></td>
\r
402 <td align="right" valign="top" height="8">
\r
403 <font FACE="Times New Roman" SIZE="2">Std
\r
404 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
\r
405 1</font></font></td>
\r
406 <td align="right" valign="top" height="8">
\r
407 <font FACE="Times New Roman" SIZE="2">Std
\r
408 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
\r
409 2</font></font></td>
\r
410 <td align="right" valign="top" height="8">
\r
411 <font FACE="Times New Roman" SIZE="2">Std
\r
412 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
\r
413 3 </font></font></td>
\r
414 <td align="right" valign="top" height="8">
\r
415 <font FACE="Times New Roman" SIZE="2">Vrfd
\r
416 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
\r
417 3</font></font></td>
\r
420 <td align="center" valign="top" height="30">
\r
421 <font FACE="Times New Roman" SIZE="2">9</font></td>
\r
422 <td align="right" valign="top" height="30">
\r
423 <font FACE="Times New Roman" SIZE="2"> 1,652,668,804<br>
\r
424 (+267.46%)</font></td>
\r
425 <td align="right" valign="top" height="30">
\r
426 <font FACE="Times New Roman" SIZE="2"> 603,549,66<br>
\r
427 (+34.19%)</font></td>
\r
428 <td align="right" valign="top" height="30">
\r
429 <font FACE="Times New Roman" SIZE="2">267,208,422<br>
\r
430 (-40.58%)</font></td>
\r
431 <td align="right" valign="top" height="30">
\r
432 <font FACE="Times New Roman" SIZE="2">449,744,588<br>
\r
436 <td align="center" valign="top" height="30">
\r
437 <font FACE="Times New Roman" SIZE="2">10</font></td>
\r
438 <td align="right" valign="top" height="30">
\r
439 <font FACE="Times New Roman" SIZE="2">11,040,766,367<br>
\r
440 (+661.64%)</font></td>
\r
441 <td align="right" valign="top" height="30">
\r
442 <font FACE="Times New Roman" SIZE="2">1,892,829,685<br>
\r
443 (+30.57%)</font></td>
\r
444 <td align="right" valign="top" height="30">
\r
445 <font FACE="Times New Roman" SIZE="2">862,153,828<br>
\r
446 (-40.52%)</font></td>
\r
447 <td align="right" valign="top" height="30">
\r
448 <font FACE="Times New Roman" SIZE="2">1,449,589,289<br>
\r
453 <p align="justify">Table 1</b>: Total node count of standard
\r
454 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 1</font><font FACE="CMMI10" SIZE="2">;
\r
455 </font><font FACE="CMR10" SIZE="2">2</font><font FACE="CMMI10" SIZE="2">;
\r
456 </font><font FACE="CMR10" SIZE="2">3 </font>and verified
\r
457 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3
\r
458 </font>at depths 9 and 10, for 138 Neishtadt test positions.</div>
\r
459 <p ALIGN="justify">The results in Tables 1 and 2 reveal that the size of
\r
460 the tree constructed by verified null-move pruning is between those of
\r
461 standard <font FACE="CMMI10" SIZE="2">R </font>
\r
462 <font FACE="CMR10" SIZE="2">= 2 </font>and <font FACE="CMMI10" SIZE="2">R
\r
463 </font><font FACE="CMR10" SIZE="2">= 3</font>, and that its tactical
\r
464 strength is greater on average than that of standard
\r
465 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 2</font>.
\r
466 These results also show that the use of <font FACE="CMMI10" SIZE="2">R
\r
467 </font><font FACE="CMR10" SIZE="2">= 1 </font>is impractical due to its
\r
468 large tree size in comparison with other depth-reduction values. Focusing
\r
469 on the practical alternatives (i.e., standard <font FACE="CMMI10" SIZE="2">
\r
470 R </font><font FACE="CMR10" SIZE="2">= 2 </font>and<font FACE="CMMI10" SIZE="2">
\r
471 R </font><font FACE="CMR10" SIZE="2">= 3</font>, and verified
\r
472 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3</font>),
\r
473 we would like to examine the behavior of verified
\r
474 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3
\r
475 </font>and find out whether its tree size remains between the tree sizes
\r
476 associated with <font FACE="CMMI10" SIZE="2">R </font>
\r
477 <font FACE="CMR10" SIZE="2">= 2 </font>and <font FACE="CMMI10" SIZE="2">R
\r
478 </font><font FACE="CMR10" SIZE="2">= 3</font>, or whether it approaches
\r
479 the size of one</p>
\r
480 <font FACE="Times New Roman" SIZE="1">
\r
481 <hr noshade color="#000000" align="justify" width="35%" size="1">
\r
482 <p ALIGN="LEFT"><sup>3</sup>
\r
483 <a href="http://www.cs.biu.ac.il/~davoudo/genesis">
\r
484 http://www.cs.biu.ac.il/~davoudo/genesis</a></p>
\r
485 </font></font><font FACE="Times New Roman" SIZE="1"><hr>
\r
486 <p ALIGN="LEFT"> </p>
\r
487 <div align="center">
\r
489 <table border="0" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="100%" id="AutoNumber8">
\r
492 <p align="left"> </td>
\r
494 <p align="center"><font size="2">Verified Null-Move Pruning</font></td>
\r
496 <p align="right"><font size="2">157</font></td>
\r
502 <p ALIGN="LEFT"> </p>
\r
503 <div align="center">
\r
505 <table border="1" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" id="AutoNumber9">
\r
507 <td><font FACE="Courier" SIZE="2">
\r
508 <p ALIGN="LEFT">#define R 3 </font>
\r
509 <font FACE="Times New Roman" SIZE="2">/* the depth reduction factor
\r
511 /* at the root level, verify = true */</font><font FACE="Courier" SIZE="2"><br>
\r
512 int search (alpha, beta, depth, verify) {<br>
\r
513 if (depth </font><font FACE="CMMI10" SIZE="2"><</font><font FACE="Courier" SIZE="2">=
\r
515 return evaluate(); </font>
\r
516 <font FACE="Times New Roman" SIZE="2">/* in practice, quiescence()
\r
517 is called here */<br>
\r
518 </font><font FACE="Courier" SIZE="2"> </font>
\r
519 <font FACE="Times New Roman" SIZE="2">/* if verify = true, and depth
\r
520 = 1, null-move search is not conducted, since<br>
\r
521 </font><font FACE="Courier" SIZE="2"> </font>
\r
522 <font FACE="Times New Roman" SIZE="2"> * verification will not
\r
524 </font><font FACE="Courier" SIZE="2"> if (</font><font FACE="CMR10" SIZE="2">!</font><font FACE="Courier" SIZE="2">in_check()
\r
525 && null_ok() && (</font><font FACE="CMR10" SIZE="2">!</font><font FACE="Courier" SIZE="2">verify
\r
526 || depth </font><font FACE="CMMI10" SIZE="2">> </font>
\r
527 <font FACE="Courier" SIZE="2">1)) {<br>
\r
528 make_null_move();</font><font FACE="Times New Roman" SIZE="2"><br>
\r
529 </font><font FACE="Courier" SIZE="2">
\r
530 </font><font FACE="Times New Roman" SIZE="2">/* null-move search
\r
531 with minimal window around beta */<br>
\r
532 </font><font FACE="Courier" SIZE="2">
\r
533 value = -search(-beta, -beta + 1, depth - R - 1,<br>
\r
534
\r
536 if (value </font>
\r
537 <font FACE="CMMI10" SIZE="2">></font><font FACE="Courier" SIZE="2">=
\r
538 beta)</font><font FACE="CMSY10" SIZE="2"> { </font>
\r
539 <font FACE="Times New Roman" SIZE="2">/* fail-high */<br>
\r
540 </font><font FACE="Courier" SIZE="2">
\r
542
\r
543 depth--; </font><font FACE="Times New Roman" SIZE="2">/* reduce the
\r
544 depth by one ply */<br>
\r
545 </font><font FACE="Courier" SIZE="2">
\r
546 </font><font FACE="Times New Roman" SIZE="2">/* turn verification
\r
547 off for the sub-tree */<br>
\r
548 </font><font FACE="Courier" SIZE="2">
\r
549 verify = false;<br>
\r
550
\r
551 </font><font FACE="Times New Roman" SIZE="2">/* mark a fail-high
\r
552 flag, to detect zugzwangs later*/<br>
\r
553 </font><font FACE="Courier" SIZE="2">
\r
554 fail high = true;<br>
\r
555 }<br>
\r
556 else </font>
\r
557 <font FACE="Times New Roman" SIZE="2">/* cutoff in a sub-tree with
\r
558 fail-high report */<br>
\r
559 </font><font FACE="Courier" SIZE="2">
\r
561 }<br>
\r
562 }<br>
\r
563 re search: </font><font FACE="Times New Roman" SIZE="2">/* if a
\r
564 zugzwang is detected, return here for re-search */<br>
\r
565 </font><font FACE="Courier" SIZE="2"> </font>
\r
566 <font FACE="Times New Roman" SIZE="2">/* do regular NegaScout/PVS
\r
568 </font><font FACE="Courier" SIZE="2"> </font>
\r
569 <font FACE="Times New Roman" SIZE="2">/* search() is called with
\r
570 current value of
\93verify
\94 */<br>
\r
571 </font><font FACE="Courier" SIZE="2"> </font>
\r
572 <font FACE="Times New Roman" SIZE="2">. . .<br>
\r
573 </font><font FACE="Courier" SIZE="2"> </font>
\r
574 <font FACE="Times New Roman" SIZE="2">/* if there is a fail-high
\r
575 report, but no cutoff was found, the position<br>
\r
576 </font><font FACE="Courier" SIZE="2"> </font>
\r
577 <font FACE="Times New Roman" SIZE="2"> * is a zugzwang and has
\r
578 to be re-searched with the original depth */<br>
\r
579 </font><font FACE="Courier" SIZE="2"> if(fail_high
\r
580 && best </font><font FACE="CMMI10" SIZE="2">< </font>
\r
581 <font FACE="Courier" SIZE="2">beta) {<br>
\r
582 depth++;<br>
\r
583 fail high = false;<br>
\r
584 verify = true;<br>
\r
585 goto re search;<br>
\r
586 }<br>
\r
590 <font FACE="Times New Roman" SIZE="2"><b>
\r
591 <p>Figure 3</b>: Verified null-move pruning.</p>
\r
594 <font FACE="Times New Roman" SIZE="2">
\r
595 <p ALIGN="justify"> </p>
\r
596 <p ALIGN="justify"> </p>
\r
597 <div align="center">
\r
599 <table border="1" cellpadding="3" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" id="AutoNumber10">
\r
601 <td valign="top" align="center">
\r
602 <font FACE="Times New Roman" SIZE="2">Depth</font></td>
\r
603 <td valign="top" align="center">
\r
604 <font FACE="Times New Roman" SIZE="2">Std
\r
605 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
\r
606 1</font></font></td>
\r
607 <td valign="top" align="center">
\r
608 <font FACE="Times New Roman" SIZE="2">Std
\r
609 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
\r
610 2</font></font></td>
\r
611 <td valign="top" align="center">
\r
612 <font FACE="Times New Roman" SIZE="2">Std
\r
613 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
\r
614 3</font></font></td>
\r
615 <td valign="top" align="center">
\r
616 <font FACE="Times New Roman" SIZE="2"><font FACE="CMR10" SIZE="2"> </font>Vrfd
\r
617 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
\r
618 3</font></font></td>
\r
621 <td valign="top" align="center">
\r
622 <font FACE="Times New Roman" SIZE="2">9</font></td>
\r
623 <td valign="top" align="center">
\r
624 <font FACE="Times New Roman" SIZE="2">64</font></td>
\r
625 <td valign="top" align="center">
\r
626 <font FACE="Times New Roman" SIZE="2">62</font></td>
\r
627 <td valign="top" align="center">
\r
628 <font FACE="Times New Roman" SIZE="2">53</font></td>
\r
629 <td valign="top" align="center">
\r
630 <font FACE="Times New Roman" SIZE="2">60</font></td>
\r
633 <td valign="top" align="center">
\r
634 <font FACE="Times New Roman" SIZE="2">10</font></td>
\r
635 <td valign="top" align="center">
\r
636 <font FACE="Times New Roman" SIZE="2">71</font></td>
\r
637 <td valign="top" align="center">
\r
638 <font FACE="Times New Roman" SIZE="2">66</font></td>
\r
639 <td valign="top" align="center">
\r
640 <font FACE="Times New Roman" SIZE="2">65</font></td>
\r
641 <td valign="top" align="center">
\r
642 <font FACE="Times New Roman" SIZE="2">71</font></td>
\r
646 <p ALIGN="justify">Table 2</b>: Number of solved positions using
\r
647 standard <font FACE="CMMI10" SIZE="2">R </font>
\r
648 <font FACE="CMR10" SIZE="2">= 1</font><font FACE="CMMI10" SIZE="2">;
\r
649 </font><font FACE="CMR10" SIZE="2">2</font><font FACE="CMMI10" SIZE="2">;
\r
650 </font><font FACE="CMR10" SIZE="2">3 </font>and verified
\r
651 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3
\r
652 </font>at depths 9 and 10, for 138 Neishtadt test positions.</div>
\r
653 <font FACE="Times New Roman" SIZE="1"><hr>
\r
654 <p ALIGN="LEFT"> </p>
\r
655 <div align="center">
\r
657 <table border="0" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="100%" id="AutoNumber11">
\r
659 <td width="33%"><font size="2">158</font></td>
\r
661 <p align="center"><font FACE="Times New Roman" SIZE="2">ICGA Journal</font></td>
\r
663 <p align="right"><font size="2">September 2002</font></td>
\r
670 <div align="center">
\r
672 <table border="1" cellpadding="3" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" id="AutoNumber12">
\r
674 <td valign="top" align="center">
\r
675 <font FACE="Times New Roman" SIZE="2">Depth </font></td>
\r
676 <td align="right" valign="top">
\r
677 <font FACE="Times New Roman" SIZE="2">Std
\r
678 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
\r
679 2 </font></font></td>
\r
680 <td align="right" valign="top">
\r
681 <font FACE="Times New Roman" SIZE="2">Std
\r
682 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
\r
683 3 </font></font></td>
\r
684 <td align="right" valign="top">
\r
685 <font FACE="Times New Roman" SIZE="2">Vrfd
\r
686 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
\r
687 3</font></font></td>
\r
690 <td valign="top" align="center">
\r
691 <font FACE="Times New Roman" SIZE="2">9</font></td>
\r
692 <td align="right" valign="top">
\r
693 <font FACE="Times New Roman" SIZE="2">5,374,275,763<br>
\r
694 (+10.84%) </font></td>
\r
695 <td align="right" valign="top">
\r
696 <font FACE="Times New Roman" SIZE="2">2,483,951,601<br>
\r
697 (-48.76%)</font></td>
\r
698 <td align="right" valign="top">
\r
699 <font FACE="Times New Roman" SIZE="2">4,848,596,820<br>
\r
703 <td valign="top" align="center">
\r
704 <font FACE="Times New Roman" SIZE="2">10</font></td>
\r
705 <td align="right" valign="top">
\r
706 <font FACE="Times New Roman" SIZE="2">16,952,333,579<br>
\r
707 (+17.40%)</font></td>
\r
708 <td align="right" valign="top">
\r
709 <font FACE="Times New Roman" SIZE="2">7,920,812,800<br>
\r
710 (-45.14%)</font></td>
\r
711 <td align="right" valign="top">
\r
712 <font FACE="Times New Roman" SIZE="2">14,439,185,304<br>
\r
716 <td valign="top" align="center">
\r
717 <font FACE="Times New Roman" SIZE="2">11</font></td>
\r
718 <td align="right" valign="top">
\r
719 <font FACE="Times New Roman" SIZE="2">105,488,197,524<br>
\r
720 (+106.51%) </font></td>
\r
721 <td align="right" valign="top">
\r
722 <font FACE="Times New Roman" SIZE="2">24,644,668,194<br>
\r
723 (-51.75%)</font></td>
\r
724 <td align="right" valign="top">
\r
725 <font FACE="Times New Roman" SIZE="2">51,080,338,048<br>
\r
730 <p ALIGN="justify">Table 3</b>: Total node count of standard
\r
731 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 2</font>,
\r
732 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3</font>,
\r
733 and verified <font FACE="CMMI10" SIZE="2">R </font>
\r
734 <font FACE="CMR10" SIZE="2">= 3 </font>at depths 9, 10, and 11, for 869
\r
735 ECM test positions.</div>
\r
736 <div align="center">
\r
738 <table border="0" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" id="AutoNumber13">
\r
740 <td><img border="0" src="graph.gif" width="420" height="311"></td>
\r
744 <p align="justify">Figure 4</b>: Tree sizes of standard
\r
745 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 2</font>,
\r
746 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3</font>,
\r
747 and verified <font FACE="CMMI10" SIZE="2">R </font>
\r
748 <font FACE="CMR10" SIZE="2">= 3 </font>at depths 9, 10, and 11, for 869
\r
749 ECM test positions.</div>
\r
750 <p ALIGN="justify">of these trees. We therefore conducted a search to a
\r
751 depth of 11 plies, using 869 positions from the<i> Encyclopedia of Chess
\r
752 Middlegames </i>(ECM)<sup><font FACE="Times New Roman" SIZE="1">4</font></sup>.
\r
753 Table 3 provides the total node counts at depths 9, 10, and 11, using
\r
754 standard <font FACE="CMMI10" SIZE="2">R </font>
\r
755 <font FACE="CMR10" SIZE="2">= 2</font>, <font FACE="CMMI10" SIZE="2">R
\r
756 </font><font FACE="CMR10" SIZE="2">= 3</font>, and verified
\r
757 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3</font>.
\r
758 See also Figure 4. As Figure 4 clearly indicates, for depth 11 the size of
\r
759 the tree constructed by verified null-move pruning with<font FACE="CMMI10" SIZE="2">
\r
760 R </font><font FACE="CMR10" SIZE="2">= 3 </font>is closer to standard
\r
761 null-move pruning with <font FACE="CMMI10" SIZE="2">R </font>
\r
762 <font FACE="CMR10" SIZE="2">= 3</font>. This implies that the saving from
\r
763 verified null-move pruning will be greater as we search more deeply. This
\r
764 can be explained by the fact that the saving from the use of
\r
765 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3
\r
766 </font>in the shallow null-move search far exceeds the verification cost
\r
767 of verified null-move pruning.</p>
\r
768 <p ALIGN="justify">Having studied the effect of verified null-move pruning
\r
769 on the search tree size, we now take a closer look at the resulting
\r
770 tactical strength in comparison with standard null-move pruning with
\r
771 different depth reductions.</p>
\r
772 <p ALIGN="justify">For this purpose we used 999 positions from the <i>
\r
773 Winning Chess Sacrifices </i>(WCS) test suite, and 434 positions of
\93mate
\r
774 in 4
\94 and 353 positions of
\93mate in 5
\94 from the test suites of the <i>
\r
775 Chess Analysis Project </i>(CAP); see the Appendix. The WCS positions were
\r
776 searched to depths of 8, 9, and 10 plies, using standard
\r
777 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 2</font>,
\r
778 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3</font>,
\r
779 and verified <font FACE="CMMI10" SIZE="2">R </font>
\r
780 <font FACE="CMR10" SIZE="2">= 3</font>. Table 4 provides the total node
\r
781 counts, and Table 5 gives the number of correctly solved positions for the
\r
782 WCS test suite. For each position of
\93mate in 4
\94 we conducted a search to
\r
783 a depth of 8 plies, and for each
\93mate in 5
\94 position a search to a depth
\r
784 of 10 plies. The search was conducted using standard<font FACE="CMMI10" SIZE="2">
\r
785 R </font><font FACE="CMR10" SIZE="2">= 1</font>,
\r
786 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 2</font>,
\r
787 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3</font>,
\r
788 and verified <font FACE="CMMI10" SIZE="2">R </font>
\r
789 <font FACE="CMR10" SIZE="2">= 3</font>. Table 6 provides the number of
\r
790 positions that each method solved (i.e., found the checkmating sequence).</p>
\r
791 <font FACE="Times New Roman" SIZE="1">
\r
792 <hr noshade color="#000000" align="justify" width="35%" size="1">
\r
793 <p ALIGN="LEFT"><sup>4</sup> Because of the large number of errors in
\r
794 ECM
\92s suggested best moves, we did not check here for number of solved
\r
796 <font FACE="Times New Roman" SIZE="1"><hr>
\r
797 <p ALIGN="LEFT"> </p>
\r
798 <div align="center">
\r
800 <table border="0" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="100%" id="AutoNumber14">
\r
802 <td width="33%"> </td>
\r
803 <td width="33%"><font FACE="Times New Roman" SIZE="2">
\r
804 <p ALIGN="center">Verified Null-Move Pruning</font></td>
\r
806 <p align="right"><font size="2">159</font></td>
\r
813 <div align="center">
\r
815 <table border="1" cellpadding="3" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" id="AutoNumber15">
\r
817 <td align="left" valign="top"><font FACE="Times New Roman" SIZE="2">
\r
818 <p ALIGN="center">Depth </font><font FACE="CMR10" SIZE="2">
\r
820 <td align="right" valign="top">
\r
821 <font FACE="Times New Roman" SIZE="1">
\r
822 <font FACE="Times New Roman" SIZE="2">Std </font>
\r
823 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
\r
824 2</font></font></td>
\r
825 <td align="right" valign="top">
\r
826 <font FACE="Times New Roman" SIZE="1">
\r
827 <font FACE="Times New Roman" SIZE="2">Std </font>
\r
828 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
\r
829 3</font></font></td>
\r
830 <td align="right" valign="top">
\r
831 <font FACE="Times New Roman" SIZE="1">
\r
832 <font FACE="Times New Roman" SIZE="2">Vrfd </font>
\r
833 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
\r
834 3</font></font></td>
\r
837 <td valign="top" align="center">
\r
838 <font FACE="Times New Roman" SIZE="2">8</font></td>
\r
839 <td align="right" valign="top">
\r
840 <font FACE="Times New Roman" SIZE="2">783,461,647<br>
\r
841 (-13.55%)</font></td>
\r
842 <td align="right" valign="top">
\r
843 <font FACE="Times New Roman" SIZE="2">533,282,695<br>
\r
844 (-41.15%)</font></td>
\r
845 <td align="right" valign="top">
\r
846 <font FACE="Times New Roman" SIZE="2">906,225,552<br>
\r
850 <td valign="top" align="center">
\r
851 <font FACE="Times New Roman" SIZE="2">9</font></td>
\r
852 <td align="right" valign="top">
\r
853 <font FACE="Times New Roman" SIZE="2">3,742,064,688<br>
\r
854 (+47.38%)</font></td>
\r
855 <td align="right" valign="top">
\r
856 <font FACE="Times New Roman" SIZE="2">1,316,719,980<br>
\r
857 (-48.14%)</font></td>
\r
858 <td align="right" valign="top">
\r
859 <font FACE="Times New Roman" SIZE="2">2,539,057,043<br>
\r
863 <td valign="top" align="center">
\r
864 <font FACE="Times New Roman" SIZE="2">10</font></td>
\r
865 <td align="right" valign="top"><font size="2">11,578,143,939</font><font FACE="Times New Roman" SIZE="2"><br>
\r
866 (+46.75%) </font></td>
\r
867 <td align="right" valign="top">
\r
868 <font FACE="Times New Roman" SIZE="2">4,871,295,877<br>
\r
869 (-38.26%)</font></td>
\r
870 <td align="right" valign="top">
\r
871 <font FACE="Times New Roman" SIZE="2">7,889,544,754<br>
\r
875 </center><font FACE="Times New Roman" SIZE="2"><b>
\r
876 <p ALIGN="justify">Table 4</b>: Total node count of standard </font>
\r
877 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 2</font><font FACE="Times New Roman" SIZE="2">,
\r
878 </font><font FACE="CMMI10" SIZE="2">R </font>
\r
879 <font FACE="CMR10" SIZE="2">= 3 </font>
\r
880 <font FACE="Times New Roman" SIZE="2">and verified </font>
\r
881 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3
\r
882 </font><font FACE="Times New Roman" SIZE="2">at depths 8, 9, and 10, for
\r
883 999 WCS test positions.</font></div>
\r
884 <div align="center">
\r
886 <table border="1" cellpadding="3" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" id="AutoNumber16">
\r
888 <td valign="top"><font FACE="Times New Roman" SIZE="2">
\r
889 <p ALIGN="center">Depth</font></td>
\r
890 <td valign="top"><font FACE="Times New Roman" SIZE="1">
\r
891 <font FACE="Times New Roman" SIZE="2">Std </font>
\r
892 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
\r
893 2</font></font></td>
\r
894 <td valign="top"><font FACE="Times New Roman" SIZE="1">
\r
895 <font FACE="Times New Roman" SIZE="2">Std </font>
\r
896 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
\r
897 3</font></font></td>
\r
898 <td valign="top"><font FACE="Times New Roman" SIZE="1">
\r
899 <font FACE="Times New Roman" SIZE="2">Vrfd </font>
\r
900 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
\r
901 3</font></font></td>
\r
904 <td valign="top"><font FACE="Times New Roman" SIZE="2">
\r
905 <p ALIGN="center">8</font></td>
\r
906 <td valign="top" align="center">
\r
907 <font FACE="Times New Roman" SIZE="2">762</font></td>
\r
908 <td valign="top" align="center">
\r
909 <font FACE="Times New Roman" SIZE="2">760</font></td>
\r
910 <td valign="top" align="center">
\r
911 <font FACE="Times New Roman" SIZE="2">782</font></td>
\r
914 <td valign="top"><font FACE="Times New Roman" SIZE="2">
\r
915 <p ALIGN="center">9</font></td>
\r
916 <td valign="top" align="center">
\r
917 <font FACE="Times New Roman" SIZE="2">838</font></td>
\r
918 <td valign="top" align="center">
\r
919 <font FACE="Times New Roman" SIZE="2">812</font></td>
\r
920 <td valign="top" align="center">
\r
921 <font FACE="Times New Roman" SIZE="2">838</font></td>
\r
924 <td valign="top"><font FACE="Times New Roman" SIZE="2">
\r
925 <p ALIGN="center">10</font></td>
\r
926 <td valign="top" align="center">
\r
927 <font FACE="Times New Roman" SIZE="2">850</font></td>
\r
928 <td valign="top" align="center">
\r
929 <font FACE="Times New Roman" SIZE="2">849</font></td>
\r
930 <td valign="top" align="center">
\r
931 <font FACE="Times New Roman" SIZE="2">866</font></td>
\r
934 </center><font FACE="Times New Roman" SIZE="2"><b>
\r
935 <p ALIGN="justify">Table 5</b>: Number of solved positions using </font>
\r
936 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 2</font><font FACE="Times New Roman" SIZE="2">,
\r
937 </font><font FACE="CMMI10" SIZE="2">R </font>
\r
938 <font FACE="CMR10" SIZE="2">= 3 </font>
\r
939 <font FACE="Times New Roman" SIZE="2">and verified </font>
\r
940 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3
\r
941 </font><font FACE="Times New Roman" SIZE="2">at depths 8, 9, and 10 for
\r
942 999 WCS test positions.</font></div>
\r
943 <div align="center">
\r
945 <table border="1" cellpadding="3" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" id="AutoNumber17">
\r
947 <td align="center" valign="top">
\r
948 <font FACE="Times New Roman" SIZE="2">Test Suite</font></td>
\r
949 <td align="center" valign="top">
\r
950 <font FACE="Times New Roman" SIZE="1">
\r
951 <font FACE="Times New Roman" SIZE="2">Std </font>
\r
952 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
\r
953 1</font></font></td>
\r
954 <td align="center" valign="top">
\r
955 <font FACE="Times New Roman" SIZE="1">
\r
956 <font FACE="Times New Roman" SIZE="2">Std </font>
\r
957 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
\r
958 2</font></font></td>
\r
959 <td align="center" valign="top">
\r
960 <font FACE="Times New Roman" SIZE="1">
\r
961 <font FACE="Times New Roman" SIZE="2">Std </font>
\r
962 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
\r
963 3</font></font></td>
\r
964 <td align="center" valign="top">
\r
965 <font FACE="Times New Roman" SIZE="1">
\r
966 <font FACE="Times New Roman" SIZE="2">Vrfd </font>
\r
967 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
\r
968 3</font></font></td>
\r
971 <td align="center" valign="top">
\r
972 <font FACE="Times New Roman" SIZE="2">
\93Mate in 4
\94<br>
\r
973 Depth 8 plies</font></td>
\r
974 <td align="center" valign="top">
\r
975 <font FACE="Times New Roman" SIZE="1">
\r
976 <font FACE="Times New Roman" SIZE="2">433</font></font></td>
\r
977 <td align="center" valign="top">
\r
978 <font FACE="Times New Roman" SIZE="1">
\r
979 <font FACE="Times New Roman" SIZE="2">385</font></font></td>
\r
980 <td align="center" valign="top">
\r
981 <font FACE="Times New Roman" SIZE="1">
\r
982 <font FACE="Times New Roman" SIZE="2">379</font></font></td>
\r
983 <td align="center" valign="top">
\r
984 <font FACE="Times New Roman" SIZE="1">
\r
985 <font FACE="Times New Roman" SIZE="2">431</font></font></td>
\r
988 <td align="center" valign="top">
\r
989 <font FACE="Times New Roman" SIZE="2">
\93Mate in 5
\94<font FACE="Times New Roman" SIZE="2"><br>
\r
990 Depth 10 plies</font> </font></td>
\r
991 <td align="center" valign="top">
\r
992 <font FACE="Times New Roman" SIZE="1">
\r
993 <font FACE="Times New Roman" SIZE="2">347</font></font></td>
\r
994 <td align="center" valign="top">
\r
995 <font FACE="Times New Roman" SIZE="1">
\r
996 <font FACE="Times New Roman" SIZE="2">292</font></font></td>
\r
997 <td align="center" valign="top">
\r
998 <font FACE="Times New Roman" SIZE="1">
\r
999 <font FACE="Times New Roman" SIZE="2">286</font></font></td>
\r
1000 <td align="center" valign="top">
\r
1001 <font FACE="Times New Roman" SIZE="1">
\r
1002 <font FACE="Times New Roman" SIZE="2">340</font></font></td>
\r
1005 </center><font FACE="Times New Roman" SIZE="2"><b>
\r
1006 <p align="justify">Table 6</b>: Numbers of solved positions using
\r
1007 standard </font><font FACE="CMMI10" SIZE="2">R </font>
\r
1008 <font FACE="CMR10" SIZE="2">= 1</font><font FACE="CMMI10" SIZE="2">;
\r
1009 </font><font FACE="CMR10" SIZE="2">2</font><font FACE="CMMI10" SIZE="2">;
\r
1010 </font><font FACE="CMR10" SIZE="2">3 </font>
\r
1011 <font FACE="Times New Roman" SIZE="2">and verified </font>
\r
1012 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3
\r
1013 </font><font FACE="Times New Roman" SIZE="2">for 434
\93mate in 4
\94 and 353
\r
1014 \93mate in 5
\94 test suites.</font></div>
\r
1015 <font FACE="Times New Roman" SIZE="2">
\r
1016 <p ALIGN="justify">The results in Tables 5 and 6 indicate that verified
\r
1017 null-move pruning solved far more positions than standard null-move
\r
1018 pruning with depth reductions of </font><font FACE="CMMI10" SIZE="2">R
\r
1019 </font><font FACE="CMR10" SIZE="2">= 2 </font>
\r
1020 <font FACE="Times New Roman" SIZE="2">and </font>
\r
1021 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3</font><font FACE="Times New Roman" SIZE="2">.
\r
1022 This demonstrates that not only does verified null-move pruning result in
\r
1023 a reduced search effort (the constructed search tree is closer in size to
\r
1024 that of standard </font><font FACE="CMMI10" SIZE="2">R </font>
\r
1025 <font FACE="CMR10" SIZE="2">= 3</font><font FACE="Times New Roman" SIZE="2">),
\r
1026 but its tactical strength is greater than that of standard </font>
\r
1027 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 2</font><font FACE="Times New Roman" SIZE="2">,
\r
1028 which is the common depth reduction value.</p>
\r
1029 <p ALIGN="justify">Finally, to study the overall advantage of verified
\r
1030 null-move pruning over standard null-move pruning in practice, we
\r
1031 conducted 100 self-play games, using two versions of the G</font><font FACE="Times New Roman" SIZE="1">ENESIS
\r
1032 </font><font FACE="Times New Roman" SIZE="2">engine, one with verified
\r
1033 </font><font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
\r
1034 3</font><font FACE="Times New Roman" SIZE="2"> and the other with standard
\r
1035 </font><font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
\r
1036 2</font><font FACE="Times New Roman" SIZE="2">. The time control was set
\r
1037 to 60 minutes per game. The version using verified </font>
\r
1038 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3
\r
1039 </font><font FACE="Times New Roman" SIZE="2">scored 68.5 out of 100 (see
\r
1040 the Appendix), which demonstrates the superiority of verified null-move
\r
1041 pruning over the standard version.</font></p>
\r
1042 <font FACE="Times New Roman" SIZE="2"><b>
\r
1043 <p ALIGN="justify">5. CONCLUSION</p>
\r
1045 <p ALIGN="justify">In this article we introduced a new null-move pruning
\r
1046 method which outperforms standard null-move pruning, techniques, in terms
\r
1047 of reducing the search tree size as well as gaining greater tactical
\r
1048 strength. The idea of not cutting off the search as soon as the shallow
\r
1049 null-move search indicates a fail-high allows verification of the cutoff,
\r
1050 which results in greater tactical accuracy and prevents errors due to
\r
1051 zugzwangs. We showed empirically that verified null-move pruning with a
\r
1052 depth reduction of </font><font FACE="CMMI10" SIZE="2">R </font>
\r
1053 <font FACE="CMR10" SIZE="2">= 3 </font>
\r
1054 <font FACE="Times New Roman" SIZE="2">constructs a search tree which is
\r
1055 closer in size to that of the tree constructed by standard </font>
\r
1056 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3</font><font FACE="Times New Roman" SIZE="2">,
\r
1057 and that the saving from the reduced search effort in comparison with
\r
1058 standard </font><font FACE="CMMI10" SIZE="2">R </font>
\r
1059 <font FACE="CMR10" SIZE="2">= 2 </font>
\r
1060 <font FACE="Times New Roman" SIZE="2">becomes greater as we search more
\r
1061 deeply. We also showed that on average, the tactical strength of verified
\r
1062 null-move pruning is greater than that of standard null-move pruning with</font><font FACE="CMMI10" SIZE="2">
\r
1063 R </font><font FACE="CMR10" SIZE="2">= 2</font><font FACE="Times New Roman" SIZE="2">.
\r
1064 Moreover, verified null-move pruning can be implemented within any
\r
1065 standard null-move pruning framework by merely adding a few lines of code.</font></p>
\r
1066 <font FACE="Times New Roman" SIZE="2">
\r
1067 <p ALIGN="justify">We considered a number of variants of standard
\r
1068 null-move pruning. The first variant was not to cut off at all upon
\r
1069 fail-high reports, but rather reduce the depth by 2 plies. We obtained
\r
1070 good results with this idea, but its tactical strength was sometimes
\r
1071 smaller than that of standard </font><font FACE="CMMI10" SIZE="2">R </font>
\r
1072 <font FACE="CMR10" SIZE="2">= 2</font><font FACE="Times New Roman" SIZE="2">.
\r
1073 We concluded that in order to improve the results, the depth should not be
\r
1074 reduced by more than one ply at a time upon fail-high reports. An
\r
1075 additional variant was not to cut off at any node, not even in the subtree
\r
1076 of a node with a fail-high report, but</p>
\r
1077 <font FACE="Times New Roman" SIZE="1"><hr>
\r
1078 <p ALIGN="LEFT"> </p>
\r
1079 <div align="center">
\r
1081 <table border="0" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="100%" id="AutoNumber18">
\r
1083 <td width="33%"><font size="2">160</font></td>
\r
1085 <p align="center"><font FACE="Times New Roman" SIZE="2">ICGA Journal</font></td>
\r
1087 <p align="right"><font size="2">September 2002</font></td>
\r
1092 </font></font></font><font FACE="Times New Roman">
\r
1093 <font FACE="Times New Roman" SIZE="2">
\r
1094 <p ALIGN="justify">merely to reduce the depth by one ply upon a fail-high
\r
1095 report. Unfortunately, the size of the resulting search tree exceeded the
\r
1096 size of the tree constructed by standard </font>
\r
1097 <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 2</font><font FACE="Times New Roman" SIZE="2">.
\r
1098 Still, another variant was to reduce the depth by one ply upon fail-high
\r
1099 reports, and to reduce the depth by two plies upon fail-high reports in
\r
1100 that node
\92s subtree, rather than cutting off.</p>
\r
1101 <p ALIGN="justify">Our empirical studies showed that cutting off the
\r
1102 search at the subtree of a fail-high reported node does not decrease
\r
1103 tactical strength. Indeed, this is the verified null-move pruning version
\r
1104 that we studied in this article. In contrast to the standard approach
\r
1105 which advocates the use of immediate cutoff, the novel approach taken here
\r
1106 uses depth reduction, and delays cutting off the search until further
\r
1107 verification. This yields greater tactical strength and a smaller search
\r
1110 <p align="justify">6. REFERENCES</p>
\r
1112 <p align="justify">Beal, D.F. (1989). Experiments with the null move. <i>
\r
1113 Advances in Computer Chess 5</i>, (Ed. D.F. Beal) , pp. 65
\9679. Elsevier
\r
1114 Science Publishers, Amsterdam, The Netherlands. ISBN 0-444-87-159-4.</p>
\r
1115 <p align="justify">Berliner, H.J. (1974). <i>Chess as Problem Solving: The
\r
1116 Development of a Tactics Analyzer</i>. Ph.D. thesis, Carnegie-Mellon
\r
1117 University, Pittsburgh, PA.</p>
\r
1118 <p align="justify">Berliner, H.J. (1987). Some innovations introduced by H</font><font FACE="Times New Roman" SIZE="1">ITECH</font><font FACE="Times New Roman" SIZE="2">.
\r
1119 <i>ICCA Journal</i>, Vol. 10, No. 3, pp. 111
\96117.</font></p>
\r
1120 <p align="justify"><font FACE="Times New Roman" SIZE="2">Berliner, H.J.
\r
1121 and Ebeling, C. (1990). H</font><font FACE="Times New Roman" SIZE="1">ITECH</font><font FACE="Times New Roman" SIZE="2">.
\r
1122 <i>Computers, Chess and Cognition </i>(Eds. T.A. Marsland and J.
\r
1123 Schaeffer), pp. 79
\96109. Springer-Verlag, New York, N.Y. ISBN
\r
1124 0-387-97415-6/3-540-97415-6.</p>
\r
1125 <p align="justify">Birmingham, J.A. and Kent, P. (1977). Tree-searching
\r
1126 and tree-pruning techniques. <i>Advances in Computer Chess 1</i>, (Ed.
\r
1127 M.R.B. Clarke), pp. 89
\96107. Edinburgh University Press, Edinburgh. ISBN
\r
1128 0-852-24292-1.</p>
\r
1129 <p align="justify">Campbell, M.S. and Marsland, T.A. (1983). A comparison
\r
1130 of minimax tree search algorithms. <i>Artificial Intelligence</i>, Vol.
\r
1131 20, No. 4, pp. 347
\96367. ISSN 0004-3702.</p>
\r
1132 <p align="justify">Condon, J.H. and Thompson, K. (1983a). B</font><font FACE="Times New Roman" SIZE="1">ELLE</font><font FACE="Times New Roman" SIZE="2">.
\r
1133 <i>Chess Skill in Man and Machine</i>, (Ed. P.W. Frey), pp. 201
\96210.
\r
1134 Springer-Verlag, New York, N.Y., 2nd ed., ISBN
\r
1135 0-387-90790-4/3-540-90790-4.</p>
\r
1136 <p align="justify">Condon, J.H. and Thompson, K. (1983b), B</font><font FACE="Times New Roman" SIZE="1">ELLE
\r
1137 </font><font FACE="Times New Roman" SIZE="2">chess hardware. <i>Advances
\r
1138 in Computer Chess 3</i>, (Ed. M.R.B. Clarke), pp. 45
\9654. Pergamon Press,
\r
1139 Oxford, ISBN 0-080-26898-6.</p>
\r
1140 <p align="justify">Donninger, C. (1993). Null move and deep search:
\r
1141 Selective search heuristics for obtuse chess programs.<i> ICCA Journal</i>,
\r
1142 Vol. 16, No. 3, pp. 137
\96143.</p>
\r
1143 <p align="justify">Ebeling, C. (1986). <i>All the Right Moves: A VLSI
\r
1144 Architecture for Chess</i>. MIT Press, Cambridge, MA., ISBN 0-262-05035-8.</p>
\r
1145 <p align="justify">Feist, M. (1999). The 9th World Computer-Chess
\r
1146 Championship: Report on the tournament. <i>ICCA Journal</i>, Vol. 22, No.
\r
1147 3, pp. 155
\96164.</p>
\r
1148 <p align="justify">Goetsch, G. and Campbell, M.S. (1990). Experiments with
\r
1149 the null-move heuristic. <i>Computers, Chess, and Cognition</i>, (Eds. T.A.
\r
1150 Marsland and J. Schaeffer), pp. 159
\96168. Springer-Verlag, New York, N.Y.,
\r
1151 ISBN 0-387-97415-6/3-540-97415-6.</p>
\r
1152 <p align="justify">Gillogy, J.J. (1972). The technology chess program. <i>
\r
1153 Artificial Intelligence</i>, Vol. 3, No. 1-3, pp. 145
\96163. ISSN 0004-3702.</p>
\r
1154 <p align="justify">Hammilton, S. and Garber, L. (1997). D</font><font FACE="Times New Roman" SIZE="1">EEP
\r
1155 </font><font FACE="Times New Roman" SIZE="2">B</font><font FACE="Times New Roman" SIZE="1">LUE</font><font FACE="Times New Roman" SIZE="2">
\92s
\r
1156 hardware-software synergy. <i>IEEE Computer</i>, Vol. 30, No. 10, pp.
\r
1158 <p align="justify">Heinz, E.A. (1999). Adaptive null-move pruning, <i>ICCA
\r
1159 Journal</i>, Vol. 22, No. 3, pp. 123
\96132.</p>
\r
1160 <p align="justify">Herik, H.J. van den and Herschberg, I.S. (1992). The
\r
1161 7th World Computer-Chess Championship: Report on the tournament. <i>ICCA
\r
1162 Journal</i>, Vol. 15, No. 4, pp. 208
\96209.</p>
\r
1163 <p align="justify">Hsu, F.-h. (1999). IBM
\92s D</font><font FACE="Times New Roman" SIZE="1">EEP
\r
1164 </font><font FACE="Times New Roman" SIZE="2">B</font><font FACE="Times New Roman" SIZE="1">LUE
\r
1165 </font><font FACE="Times New Roman" SIZE="2">chess grandmaster chips. <i>
\r
1166 IEEE Micro</i>, Vol. 19, No. 2, pp. 70
\9680.</font></p>
\r
1167 <font FACE="Times New Roman" SIZE="2"></font>
\r
1168 <font FACE="Times New Roman" SIZE="1"><hr>
\r
1169 <p ALIGN="justify"> </p>
\r
1170 <table border="0" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="100%" id="AutoNumber19">
\r
1173 <p align="left"> </td>
\r
1175 <p align="center"><font face="Times New Roman" size="2">Verified
\r
1176 Null-Move Pruning</font></td>
\r
1178 <p align="right"><font size="2">161</font></td>
\r
1181 </font><font FACE="Times New Roman" SIZE="2">
\r
1182 <p ALIGN="justify">Hsu, F.-h., Anantharaman, T.S., Campbell, M.S., and
\r
1183 Nowatzyk, A. (1990). D</font><font FACE="Times New Roman" SIZE="1">EEP
\r
1184 </font><font FACE="Times New Roman" SIZE="2">T</font><font FACE="Times New Roman" SIZE="1">HOUGHT</font><font FACE="Times New Roman" SIZE="2">.
\r
1185 <i>Computers, Chess, and Cognition</i>, (Eds. T.A. Marsland and J.
\r
1186 Schaeffer), pp. 55
\9678. Springer-Verlag, New York, N.Y. ISBN
\r
1187 0-387-97415-6/3-540-97415-6.</p>
\r
1188 <p ALIGN="justify">Hyatt, R.M., Gower, A.E., and Nelson, H.L. (1990). C</font><font FACE="Times New Roman" SIZE="1">RAY
\r
1189 </font><font FACE="Times New Roman" SIZE="2">B</font><font FACE="Times New Roman" SIZE="1">LITZ</font><font FACE="Times New Roman" SIZE="2">,
\r
1190 <i>Computers, Chess, and Cognition</i>, (Eds. T.A. Marsland and J.
\r
1191 Schaeffer), pp. 111
\96130. Springer-Verlag, New York, N.Y. ISBN
\r
1192 0-387-97415-6/3-540- 97415-6.</p>
\r
1193 <p ALIGN="justify">Nelson, H.L. (1985). Hash tables in C</font><font FACE="Times New Roman" SIZE="1">RAY
\r
1194 </font><font FACE="Times New Roman" SIZE="2">B</font><font FACE="Times New Roman" SIZE="1">LITZ</font><font FACE="Times New Roman" SIZE="2">.
\r
1195 <i>ICCA Journal</i>, Vol. 8, No. 1, pp. 3
\9613.</p>
\r
1196 <p ALIGN="justify">Newborn, M.M. (1975). <i>Computer Chess</i>. Academic
\r
1197 Press. New York, N.Y. ISBN 0-125-17250-8.</p>
\r
1198 <p ALIGN="justify">Plenkner, S. (1995). A null-move technique impervious
\r
1199 to zugzwang. <i>ICCA Journal</i>, Vol. 18, No. 2, pp. 82
\9684.</p>
\r
1200 <p ALIGN="justify">Reinefeld, A. (1983). An improvement to the S</font><font FACE="Times New Roman" SIZE="1">COUT
\r
1201 </font><font FACE="Times New Roman" SIZE="2">tree-search algorithm. <i>
\r
1202 ICCA Journal</i>, Vol. 6, No. 4, pp. 4
\9614.</p>
\r
1203 <p ALIGN="justify">Schaeffer, J. (1983). The history heuristic. <i>ICCA
\r
1204 Journal</i>, Vol. 6, No. 3, pp. 16
\9619.</p>
\r
1205 <p ALIGN="justify">Schaeffer, J. (1989). The history heuristic and
\r
1206 alpha-beta search enhancements in practice. <i>IEEE Transactions on
\r
1207 Pattern Analysis and Machine Intelligence</i>, Vol. 11, No. 11, pp.
\r
1208 1203
\961212. ISSN 0162-8828.</p>
\r
1209 <p ALIGN="justify">Slagle, J.R. (1971). <i>Artificial Intelligence: The
\r
1210 Heuristic Programming Approach</i>. McGraw-Hill, New York, N.Y.</p>
\r
1211 <p ALIGN="justify">Slate, D.J. and Atkin, L.R. (1977). C</font><font FACE="Times New Roman" SIZE="1">HESS
\r
1212 </font><font FACE="Times New Roman" SIZE="2">4.5
\96 The Northwestern
\r
1213 University chess program. <i>Chess Skill in Man and Machine</i>, (Ed. P.W.
\r
1214 Frey), pp. 82
\96118. Springer-Verlag, New York, N.Y., 2nd ed. 1983, ISBN
\r
1215 0-387-90790-4/3-540-90790-4.</p>
\r
1216 <p ALIGN="justify">Tsang, H.K. and Beal, D.F. (1995). The 8thWorld
\r
1217 Computer-Chess Championship: Report on the tournament and the contestants
\92 \r
1218 programs described. <i>ICCA Journal</i>, Vol. 18, No. 2, pp. 93
\96101.</p>
\r
1220 <p ALIGN="justify">7. ACKNOWLEDGEMENTS</p>
\r
1222 <p ALIGN="justify">We would like to thank Shay Bushinsky for his interest
\r
1223 in our research, and for promoting the discipline of Computer Chess in our
\r
1224 department. We would also like to thank Dann Corbit for providing the CAP
\r
1225 test positions for our empirical studies, and Azriel Rosenfeld for his
\r
1226 editorial comments. Finally, we are indebted to Jonathan Schaeffer and
\r
1227 Christian Donninger for their enlightening remarks and suggestions.</p>
\r
1229 <p ALIGN="justify">8. APPENDIX</p>
\r
1230 <p ALIGN="justify">EXPERIMENTAL SETUP</p>
\r
1232 <p ALIGN="justify">Our experimental setup consisted of the following
\r
1236 <p ALIGN="justify">138 positions (Diagrams 241 to 378) from: Yakov
\r
1237 Neishtadt (1993). <i>Test Your Tactical Ability</i>, pp. 110
\96135.
\r
1238 Batsford, ISBN 0-7134-4013-9.<br>
\r
1241 <p ALIGN="justify"><font FACE="Times New Roman" SIZE="2">869 positions
\r
1242 from <i>Encyclopedia of Chess Middlegames</i>, and 999 positions from <i>
\r
1243 Winning Chess Sacrifices</i>, as available on the Internet.<font FACE="Times New Roman" SIZE="2"><br>
\r
1244 </font></font></li>
\r
1246 <p ALIGN="justify"><font FACE="Times New Roman" SIZE="2">434
\93Mate in 4
\94 \r
1247 and 353
\93Mate in 5
\94 positions from <i>Chess Analysis Project</i>,
\r
1248 available at <a href="ftp://cap.connx.com/">ftp://cap.connx.com/</a><br>
\r
1249 </font></li>
\r
1251 <p ALIGN="justify"><font FACE="Times New Roman" SIZE="2">G<font FACE="Times New Roman" SIZE="1">ENESIS
\r
1252 </font>chess engine, with <font FACE="CMR10" SIZE="2">2</font><sup>22</sup><font FACE="CMR7" SIZE="1">
\r
1253 </font>transposition table entries (64MB), running on a 733 MHz Pentium
\r
1254 III with 256MB RAM, with the Windows 98 operating system.</font></li>
\r
1256 <p ALIGN="justify">The webpage
\r
1257 <a href="http://www.cs.biu.ac.il/~davoudo/pubs.html">
\r
1258 http://www.cs.biu.ac.il/~davoudo/pubs.html</a> contains additional
\r
1259 information about the test suites, move lists of self-play games, and
\r
1260 detailed experimental results.</font></font></font></td>
\r
projects / typhoon-papers.git / blob