diff options
| author | Scott Gasch <[email protected]> | 2016-06-01 19:04:57 -0700 |
|---|---|---|
| committer | Scott Gasch <[email protected]> | 2016-06-01 19:04:57 -0700 |
| commit | 10acef9e6f2d1f56a39c7f4b9ccf4b4be6f8bed7 (patch) | |
| tree | 72a2bacbe76e6bf5b4c344279559f17cccb0ec35 /misc/vrfd_null.html | |
Diffstat (limited to 'misc/vrfd_null.html')
| -rw-r--r-- | misc/vrfd_null.html | 1268 |
1 files changed, 1268 insertions, 0 deletions
diff --git a/misc/vrfd_null.html b/misc/vrfd_null.html new file mode 100644 index 0000000..173cf22 --- /dev/null +++ b/misc/vrfd_null.html @@ -0,0 +1,1268 @@ +<html dir="ltr">
+
+<head>
+<meta http-equiv="Content-Language" content="en-us">
+<meta name="GENERATOR" content="Microsoft FrontPage 5.0">
+<meta name="ProgId" content="FrontPage.Editor.Document">
+<meta http-equiv="Content-Type" content="text/html; charset=windows-1252">
+<title>Verified Null-Move Pruning</title>
+</head>
+
+<body bgcolor="#FFFFFF" topmargin="50" leftmargin="100">
+
+<div align="center">
+ <center>
+ <table border="0" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="580" id="AutoNumber5">
+ <tr>
+ <td>
+ <div align="center">
+ <center>
+ <table border="0" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="100%" id="AutoNumber2">
+ <tr>
+ <td width="33%">
+ <p align="left"> </td>
+ <td width="33%">
+ <p align="center"><font face="Times New Roman" size="2">Verified
+ Null-Move Pruning</font></td>
+ <td width="34%">
+ <p align="right"><font face="Times New Roman" size="2">153</font></td>
+ </tr>
+ </table>
+ </center>
+ </div>
+ <font FACE="Times New Roman"><b>
+ <p ALIGN="center"> </p>
+ <p ALIGN="center">VERIFIED NULL-MOVE PRUNING</p>
+ </b><font FACE="Times New Roman" SIZE="2"><i>
+ <p ALIGN="center">Omid David Tabibi </i><sup>1</sup><i>
+ Nathan S. Netanyahu </i><sup>2</sup></p>
+ <p ALIGN="center">Ramat-Gan, Israel</p>
+ <p ALIGN="center">ABSTRACT</p>
+ </font></font>
+ <div align="center">
+ <center>
+ <table border="0" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" dir="ltr" id="AutoNumber1" width="520">
+ <tr>
+ <td><font FACE="Times New Roman" SIZE="2">
+ <p ALIGN="justify">In this article we review standard null-move
+ pruning and introduce our extended version of it, which we call <i>
+ verified null-move pruning</i>. In verified null-move pruning,
+ whenever the shallow null-move search indicates a fail-high, instead
+ of cutting off the search from the current node, the search is
+ continued with reduced depth.</p>
+ <p ALIGN="justify">Our experiments with verified null-move pruning
+ show that on average, it constructs a smaller search tree with
+ greater tactical strength in comparison to standard null-move
+ pruning. Moreover, unlike standard null-move pruning, which fails
+ badly in zugzwang positions, verified null-move pruning manages to
+ detect most zugzwangs and in such cases conducts a re-search to
+ obtain the correct result. In addition, verified null-move pruning
+ is very easy to implement, and any standard null-move pruning
+ program can use verified null-move pruning by modifying only a few
+ lines of code.</font></td>
+ </tr>
+ </table>
+ </center>
+ </div>
+ <p ALIGN="justify"><b><font size="2">1. INTRODUCTION</font></b></p>
+ <font FACE="Times New Roman" SIZE="2">
+ <p ALIGN="justify">Until the mid-1970s most chess programs were trying to
+ search the same way humans think, by generating �plausible� moves. By
+ using extensive chess knowledge at each node, these programs selected a
+ few moves which they considered plausible, and thus pruned large parts of
+ the search tree. However, plausible move generating programs had serious
+ tactical shortcomings, and as soon as brute-force search programs like
+ TECH (Gillogy, 1972) and CHESS 4.X (Slate and Atkin, 1977) managed to
+ reach depths of 5 plies and more, plausible-move generating programs
+ frequently lost to brute-force searchers due to their tactical weaknesses.</p>
+ <p ALIGN="justify">Brute-force searchers rapidly dominated the
+ computer-chess field. Most brute-force searchers of that time used no
+ selectivity in their full-width search tree, except for some extensions,
+ consisting mostly of check extensions and recaptures. The most successful
+ of these brute-force programs were BELLE (Condon and Thompson, 1983a,b),
+ DEEP THOUGHT (Hsu, Anantharaman, Campbell, and Nowatzyk, 1990), HITECH
+ (Berliner and Ebeling, 1990; Berliner, 1987; Ebeling, 1986), and CRAY
+ BLITZ (Hyatt, Gower, and Nelson, 1990), which for the first time managed
+ to compete successfully against humans.</font></p>
+ <p ALIGN="justify"><font FACE="Times New Roman" SIZE="2">The introduction
+ of null-move pruning (Beal, 1989; Goetsch and Campbell, 1990; Donninger,
+ 1993) in the early 1990s marked the end of an era, as far as the
+ domination of brute-force programs in computer chess is concerned. Unlike
+ other forward-pruning methods (e.g., <i>razoring </i>(Birmingham and Kent,
+ 1977), GAMMA (Newborn, 1975), and <i>marginal forward pruning </i>(Slagle,
+ 1971)), which had great tactical weaknesses, null-move pruning enabled
+ programs to search more deeply with minor tactical risks. Forward-pruning
+ programs frequently outsearched brute-force searchers, and started their
+ own reign which has continued ever since; they have won all World
+ Computer-Chess Championships since 1992 (van den Herik and Herschberg,
+ 1992; Tsang and Beal, 1995; Feist, 1999). DEEP BLUE (Hammilton and Garber,
+ 1997; Hsu, 1999) (the direct descendant of DEEP THOUGHT (Hsu <i>et al.</i>,
+ 1990)) was probably the last brute-force searcher. Today almost all top
+ tournament playing programs use forward-pruning methods, null-move pruning
+ being the most popular of them (Feist, 1999).</font></p>
+ <font FACE="Times New Roman" SIZE="1">
+ <hr noshade color="#000000" align="justify" width="35%" size="1">
+ <p ALIGN="justify"><sup>1</sup> Department of Computer Science, Bar-Ilan
+ University, Ramat-Gan 52900, Israel, Email:
+ <a href="mailto:[email protected]">[email protected]</a>.
+ <a href="Http://www.cs.biu.ac.il/~davoudo">
+ Http://www.cs.biu.ac.il/~davoudo</a><sup><br>
+ 2</sup> Department of Computer Science, Bar-Ilan University, Ramat-Gan
+ 52900, Israel, Email: <a href="mailto:[email protected]">
+ [email protected]</a>, and Center for Automation Research, University of
+ Maryland, College Park, MD 20742, USA, Email:
+ <a href="mailto:[email protected]">[email protected]</a>.</font></p>
+ <font FACE="Times New Roman" SIZE="1"><hr>
+ <p> </p>
+ <table border="0" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="100%" id="AutoNumber2">
+ <tr>
+ <td width="33%">
+ <p align="left"><font face="Times New Roman" size="2">154</font></td>
+ <td width="33%"><font FACE="Times New Roman" SIZE="2">
+ <p ALIGN="center">ICGA Journal</font></td>
+ <td width="34%">
+ <p align="right"><font size="2">September 2002</font></td>
+ </tr>
+ </table>
+ </font><font FACE="Times New Roman" SIZE="2">
+ <p align="justify">In this article we introduce our new <i>verified
+ null-move pruning </i>method, and demonstrate empirically its improved
+ performance in comparison with standard null-move pruning. This is
+ reflected in its reduced search tree size, as well as its greater tactical
+ strength. In Section 2 we review standard null-move pruning, and in
+ Section 3 we introduce verified null-move pruning. Section 4 presents our
+ experimental results, and Section 5 contains concluding remarks.</p>
+ <b>
+ <p align="justify">2. STANDARD NULL-MOVE PRUNING</p>
+ </b>
+ <p align="justify">As mentioned earlier, brute-force programs refrained
+ from pruning any nodes in the full-width part of the search tree, deeming
+ the risks of doing so as being too high. Null-move (Beal, 1989; Goetsch
+ and Campbell, 1990; Donninger, 1993) introduced a new pruning scheme which
+ based its cutoff decisions on dynamic criteria, and thus gained greater
+ tactical strength in comparison with the static forward pruning methods
+ that were in use at that time.</p>
+ <div align="center">
+ <center>
+ <table border="1" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" id="AutoNumber3">
+ <tr>
+ <td><font FACE="Times New Roman" SIZE="2">
+ <p ALIGN="LEFT">/* the depth reduction factor */</font><font FACE="Courier" SIZE="2"><br>
+ #define R 2<br>
+ int search (alpha, beta, depth) {<br>
+ if (depth </font><font FACE="CMMI10" SIZE="2"><</font><font FACE="Courier" SIZE="2">=
+ 0)<br>
+ return evaluate(); </font>
+ <font FACE="Times New Roman" SIZE="2">/* in practice, quiescence()
+ is called here */<br>
+ <font FACE="Courier" SIZE="2"> </font>/* conduct a null-move search if it is legal and desired */<br>
+ </font><font FACE="Courier" SIZE="2"> if (</font><font FACE="CMR10" SIZE="2">!</font><font FACE="Courier" SIZE="2">in_check()
+ && null_ok()) {<br>
+ make_null_move();<br>
+ </font>/* null-move search with
+ minimal window around beta */<br>
+ <font FACE="Courier" SIZE="2">
+ value = -search(-beta, -beta + 1, depth - R - 1);<br>
+ if (value </font>
+ <font FACE="CMMI10" SIZE="2">></font><font FACE="Courier" SIZE="2">=
+ beta) </font><font FACE="Times New Roman" SIZE="2">/* cutoff in case
+ of fail-high */<br>
+ <font FACE="Courier" SIZE="2">
+ </font></font><font FACE="Courier" SIZE="2">
+ return value;<br>
+ }<br>
+ </font><font FACE="Times New Roman" SIZE="2">/* continue
+ regular NegaScout/PVS search */<br>
+ <font FACE="Courier" SIZE="2"> </font>. . .<br>
+ <font FACE="Courier" SIZE="2">}</font></font></td>
+ </tr>
+ </table>
+ <p><b>Figure 1</b>: Standard null-move pruning.</p>
+ </center>
+ </div>
+ <p ALIGN="justify">There are positions in chess where any move will
+ deteriorate the position, so that not making a move is the best option.
+ These positions are called <i>zugzwang </i>positions. While zugzwang
+ positions are rare in the middle game, they are not an exception in
+ endgames, especially endgames in which one or both sides are left with
+ King and Pawns. Null-move pruning will fail badly in zugzwang positions
+ since the basic assumption behind the method does not hold. In fact, the
+ null-move search�s value is an upper bound in such cases. As a result,
+ null-move pruning is avoided in such endgame positions.</p>
+ </font><font FACE="Times New Roman" SIZE="1"><hr>
+ <p ALIGN="justify"> </p>
+ <table border="0" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="100%" id="AutoNumber2">
+ <tr>
+ <td width="33%">
+ <p align="left"> </td>
+ <td width="33%">
+ <p align="center"><font face="Times New Roman" size="2">Verified
+ Null-Move Pruning</font></td>
+ <td width="34%">
+ <p align="right"><font face="Times New Roman" size="2">155</font></td>
+ </tr>
+ </table>
+ </font><font FACE="Times New Roman" SIZE="2">
+ <p ALIGN="justify">As previously noted, the major benefit of null-move
+ pruning stems from the depth reduction in the null-move searches. However,
+ these reduced-depth searches are liable to tactical weaknesses due to the
+ <i>horizon effect </i>(Berliner, 1974). A horizon effect results whenever
+ the reduced-depth search misses a tactical threat. Such a threat would not
+ have been missed, had we conducted a search without any depth reduction.
+ The greater the depth reduction </font><font FACE="CMMI10" SIZE="2">R</font><font FACE="Times New Roman" SIZE="2">,
+ the greater the tactical risk due to the horizon effect. So, the saving
+ resulting from null-move pruning depends on the depth reduction factor,
+ since a shallower search (i.e., a greater </font>
+ <font FACE="CMMI10" SIZE="2">R</font><font FACE="Times New Roman" SIZE="2">)
+ will result in faster null-move searches and an overall smaller search
+ tree.</p>
+ <p ALIGN="justify">In the early days of null-move pruning, most programs
+ used </font><font FACE="CMMI10" SIZE="2">R </font>
+ <font FACE="CMR10" SIZE="2">= 1</font><font FACE="Times New Roman" SIZE="2">,
+ which ensures the least tactical risk, but offers the least saving in
+ comparison with other </font><font FACE="CMMI10" SIZE="2">R </font>
+ <font FACE="Times New Roman" SIZE="2">values. Other reduction factors that
+ were experimented with were </font><font FACE="CMMI10" SIZE="2">R </font>
+ <font FACE="CMR10" SIZE="2">= 2 </font>
+ <font FACE="Times New Roman" SIZE="2">and </font>
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3</font><font FACE="Times New Roman" SIZE="2">.
+ Research conducted over the years, most extensively by Heinz (1999),
+ showed that overall, </font><font FACE="CMMI10" SIZE="2">R </font>
+ <font FACE="CMR10" SIZE="2">= 2 </font>
+ <font FACE="Times New Roman" SIZE="2">performs better than the too
+ conservative </font><font FACE="CMMI10" SIZE="2">R </font>
+ <font FACE="CMR10" SIZE="2">= 1 </font>
+ <font FACE="Times New Roman" SIZE="2">and the too aggressive </font>
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3</font><font FACE="Times New Roman" SIZE="2">.
+ Today, almost all null-move pruning programs, use at least </font>
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 2
+ </font><font FACE="Times New Roman" SIZE="2">(Feist, 1999). However, using
+ </font><font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
+ 3 </font><font FACE="Times New Roman" SIZE="2">is tempting, considering
+ the reduced search effort resulting from shallower null-move searches.
+ (This will be demonstrated in Section 4.) Donninger (1993) was the first
+ to suggest an adaptive rather than a fixed value for </font>
+ <font FACE="CMMI10" SIZE="2">R</font><font FACE="Times New Roman" SIZE="2">.
+ Experiments conducted by Heinz (1999), in his article on adaptive
+ null-move pruning, suggest that using </font><font FACE="CMMI10" SIZE="2">
+ R </font><font FACE="CMR10" SIZE="2">= 3 </font>
+ <font FACE="Times New Roman" SIZE="2">in upper parts of the search tree
+ and </font><font FACE="CMMI10" SIZE="2">R </font>
+ <font FACE="CMR10" SIZE="2">= 2 </font>
+ <font FACE="Times New Roman" SIZE="2">in its lower parts can save 10 to 30
+ percent of the search effort in comparison with a fixed </font>
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 2</font><font FACE="Times New Roman" SIZE="2">,
+ while maintaining overall tactical strength.</p>
+ <p align="justify">In the next section we present a new null-move pruning
+ method which allows the use of </font><font FACE="CMMI10" SIZE="2">R
+ </font><font FACE="CMR10" SIZE="2">= 3 </font>
+ <font FACE="Times New Roman" SIZE="2">in all parts of the search tree,
+ while alleviating to a significant extent the main disadvantage of
+ standard null-move pruning.</p>
+ <b>
+ <p align="justify">3. VERIFIED NULL-MOVE PRUNING</p>
+ </b>
+ <p align="justify">Cutoffs based on a shallow null-move search can be too
+ risky at some points, especially in zugzwang positions. Goetsch and
+ Campbell (1990) hinted at continuing the search with reduced depth, in
+ case the null-move search indicates a fail-high, in order to substantiate
+ that the value returned from the null-move search is indeed a lower bound
+ on the position. Plenkner (1995) showed that this idea can help prevent
+ errors due to zugzwangs. However, verifying the search in the middle game
+ seems wasteful, as it appears to undermine the basic benefit of null-move
+ pruning, namely that a cutoff is determined by a shallow null-move search.</p>
+ <p ALIGN="justify">In addition to helping in detecting zugzwangs, the idea
+ of not immediately pruning the search tree (based on the value returned
+ from the shallow null-move search) can also help to reduce the tactical
+ weaknesses caused by the horizon effect, since by continuing the search we
+ may be able to detect threats which the shallow null-move search has
+ failed to detect. Based on these ideas, we developed our own
+ reformulation, which we call<i> verified null-move pruning</i>. At each
+ node, we conduct a null-move search with a depth reduction of </font>
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3</font><font FACE="Times New Roman" SIZE="2">.
+ If the returned value from that null-move search indicates a fail-high
+ (i.e., </font><i><font FACE="CMMI10" SIZE="2">value ≥ β</font></i><font SIZE="2" face="Times New Roman">),
+ we then reduce the depth by one ply and continue the search in order to
+ verify the cutoff. However, for that node�s subtree, we use standard
+ null-move pruning (cutoff takes place upon fail-highs). See Figure 2, for
+ an illustration.</font></p>
+ <div align="center">
+ <center>
+ <table border="1" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" id="AutoNumber4">
+ <tr>
+ <td><img border="0" src="example.gif" width="414" height="171"></td>
+ </tr>
+ </table>
+ <font FACE="Times New Roman" SIZE="2"><b>
+ <p>Figure 2</b>: Illustration of verified null-move pruning.</p>
+ </font></center>
+ </div>
+ <font FACE="Times New Roman" SIZE="2">
+ <p align="justify">The basic idea behind verified null-move pruning is
+ that null-move search with </font><font FACE="CMMI10" SIZE="2">R </font>
+ <font FACE="CMR10" SIZE="2">= 3 </font>
+ <font FACE="Times New Roman" SIZE="2">constructs a considerably smaller
+ search tree. However, because of its tactical deficiencies, a cutoff based
+ on it is too risky. So upon a fail-high, we reduce the depth and continue
+ the search, using standard null-move pruning</font></p>
+ <font FACE="Times New Roman" SIZE="1"><hr>
+ <p> </p>
+ <div align="center">
+ <center>
+ <table border="0" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="100%" id="AutoNumber6">
+ <tr>
+ <td width="33%">
+ <p align="left"><font size="2">156</font></td>
+ <td width="33%">
+ <p align="center"><font FACE="Times New Roman" SIZE="2">ICGA Journal</font></td>
+ <td width="34%">
+ <p align="right"><font size="2">September 2002</font></td>
+ </tr>
+ </table>
+ </center>
+ </div>
+ </font>
+ <p align="justify"><font FACE="Times New Roman" SIZE="2">(with </font>
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3</font><font FACE="Times New Roman" SIZE="2">)
+ in that node�s subtree. The search at a node is thus cut off (based on its
+ null-move search) only if there has been another null-move search
+ fail-high indication in one of the node�s ancestors (see Figure 2). As the
+ experimental results in the next section show, verified null-move pruning
+ constructs a search tree which is close in size to that of standard
+ null-move pruning with <font FACE="CMMI10" SIZE="2">R </font>
+ <font FACE="CMR10" SIZE="2">= 3</font>, and whose tactical strength is
+ greater on average than that of standard null-move pruning with
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 2</font>.
+ This is a smaller search tree with greater tactical strength, in
+ comparison with standard null-move pruning with
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 2</font>,
+ which is commonly used nowadays.</font></p>
+ <p align="justify"><font FACE="Times New Roman" SIZE="2">Since upon a
+ fail-high indication we do not cut off the search at once, we have the
+ ability to check whether the returned value is indeed a lower bound on the
+ position. If the null-move search indicates a cutoff, but the search shows
+ that the best value is smaller than </font><i>
+ <font FACE="CMMI10" SIZE="2">β</font></i><font FACE="Times New Roman" SIZE="2">,
+ this implies that the position is a zugzwang, as the value from the null
+ move is greater than or equal to the value from the best move. In such
+ cases, we restore the original depth (which was reduced by one ply after
+ the fail-high indication), and conduct a re-search to obtain the correct
+ value.</p>
+ <p align="justify">Implementation of verified null-move search is a matter
+ of adding a few lines of code to standard null-move search, as shown in
+ Figure 3. Regarding the pseudo-code presented, when the search starts at
+ the root level, the flag <font FACE="Courier" SIZE="2">verify </font>is
+ initialized to <font FACE="Courier" SIZE="2">true</font>. When the
+ null-move search indicates a fail-high, the remaining depth is reduced by
+ one ply, and <font FACE="Courier" SIZE="2">verify </font>is given the
+ value <font FACE="Courier" SIZE="2">false</font>, which will be passed to
+ the children of the current node, indicating that standard null-move
+ pruning will be conducted with respect to the children. Upon a fail-high
+ indication due to the standard null-move search of these children�s
+ subtrees, cutoff takes place immediately.</p>
+ <b>
+ <p align="justify">4. EXPERIMENTAL RESULTS</p>
+ </b>
+ <p align="justify">In this section we examine the performance of verified
+ null-move pruning, focusing on its tactical strength and smaller
+ search-tree size in comparison with standard null-move pruning. We
+ conducted our experiments using the G<font FACE="Times New Roman" SIZE="1">ENESIS<sup>3</sup>
+ </font>engine. G<font FACE="Times New Roman" SIZE="1">ENESIS </font>is
+ designed especially for research, emphasizing accurate implementation of
+ 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
+ (Campbell and Marsland, 1983; Reinefeld, 1983) search algorithm, with
+ history heuristic (Schaeffer, 1983, 1989) and transposition table (Slate
+ and Atkin, 1977; Nelson, 1985). To demonstrate the tactical strength
+ differences between the different methods even better, we used one-ply
+ check extensions on leaf nodes; the quiescence search consisted only of
+ captures/recaptures. In all test suites used, we discarded positions in
+ which at least one side had no more than King and Pawns. This was done to
+ avoid dealing with zugzwang positions, for which verified null-move
+ pruning obviously fares much better tactically, as explained before.</p>
+ <p ALIGN="justify">In order to obtain an estimate of the search tree, we
+ searched 138 test positions from <i>Test Your Tactical Ability </i>by
+ Yakov Neishtadt (see the Appendix) to depths of 9 and 10 plies, using
+ standard <font FACE="CMMI10" SIZE="2">R </font>
+ <font FACE="CMR10" SIZE="2">= 1</font>, <font FACE="CMMI10" SIZE="2">R
+ </font><font FACE="CMR10" SIZE="2">= 2</font>,
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3</font>,
+ and verified <font FACE="CMMI10" SIZE="2">R </font>
+ <font FACE="CMR10" SIZE="2">= 3</font>. Table 1 gives the total node count
+ for each method and the size of the tree in comparison with verified
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3</font>.
+ Table 2 gives the number of positions that each method solved correctly
+ (i.e., found the correct variation for). Later we will further examine the
+ tactical strength, using additional test suites.</p>
+ <div align="center">
+ <center>
+ <table border="1" cellpadding="3" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" id="AutoNumber7" height="88">
+ <tr>
+ <td align="center" valign="top" height="8">
+ <font FACE="Times New Roman" SIZE="2">Depth</font></td>
+ <td align="right" valign="top" height="8">
+ <font FACE="Times New Roman" SIZE="2">Std
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
+ 1</font></font></td>
+ <td align="right" valign="top" height="8">
+ <font FACE="Times New Roman" SIZE="2">Std
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
+ 2</font></font></td>
+ <td align="right" valign="top" height="8">
+ <font FACE="Times New Roman" SIZE="2">Std
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
+ 3 </font></font></td>
+ <td align="right" valign="top" height="8">
+ <font FACE="Times New Roman" SIZE="2">Vrfd
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
+ 3</font></font></td>
+ </tr>
+ <tr>
+ <td align="center" valign="top" height="30">
+ <font FACE="Times New Roman" SIZE="2">9</font></td>
+ <td align="right" valign="top" height="30">
+ <font FACE="Times New Roman" SIZE="2"> 1,652,668,804<br>
+ (+267.46%)</font></td>
+ <td align="right" valign="top" height="30">
+ <font FACE="Times New Roman" SIZE="2"> 603,549,66<br>
+ (+34.19%)</font></td>
+ <td align="right" valign="top" height="30">
+ <font FACE="Times New Roman" SIZE="2">267,208,422<br>
+ (-40.58%)</font></td>
+ <td align="right" valign="top" height="30">
+ <font FACE="Times New Roman" SIZE="2">449,744,588<br>
+ -</font></td>
+ </tr>
+ <tr>
+ <td align="center" valign="top" height="30">
+ <font FACE="Times New Roman" SIZE="2">10</font></td>
+ <td align="right" valign="top" height="30">
+ <font FACE="Times New Roman" SIZE="2">11,040,766,367<br>
+ (+661.64%)</font></td>
+ <td align="right" valign="top" height="30">
+ <font FACE="Times New Roman" SIZE="2">1,892,829,685<br>
+ (+30.57%)</font></td>
+ <td align="right" valign="top" height="30">
+ <font FACE="Times New Roman" SIZE="2">862,153,828<br>
+ (-40.52%)</font></td>
+ <td align="right" valign="top" height="30">
+ <font FACE="Times New Roman" SIZE="2">1,449,589,289<br>
+ -</font></td>
+ </tr>
+ </table>
+ </center><b>
+ <p align="justify">Table 1</b>: Total node count of standard
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 1</font><font FACE="CMMI10" SIZE="2">;
+ </font><font FACE="CMR10" SIZE="2">2</font><font FACE="CMMI10" SIZE="2">;
+ </font><font FACE="CMR10" SIZE="2">3 </font>and verified
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3
+ </font>at depths 9 and 10, for 138 Neishtadt test positions.</div>
+ <p ALIGN="justify">The results in Tables 1 and 2 reveal that the size of
+ the tree constructed by verified null-move pruning is between those of
+ standard <font FACE="CMMI10" SIZE="2">R </font>
+ <font FACE="CMR10" SIZE="2">= 2 </font>and <font FACE="CMMI10" SIZE="2">R
+ </font><font FACE="CMR10" SIZE="2">= 3</font>, and that its tactical
+ strength is greater on average than that of standard
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 2</font>.
+ These results also show that the use of <font FACE="CMMI10" SIZE="2">R
+ </font><font FACE="CMR10" SIZE="2">= 1 </font>is impractical due to its
+ large tree size in comparison with other depth-reduction values. Focusing
+ on the practical alternatives (i.e., standard <font FACE="CMMI10" SIZE="2">
+ R </font><font FACE="CMR10" SIZE="2">= 2 </font>and<font FACE="CMMI10" SIZE="2">
+ R </font><font FACE="CMR10" SIZE="2">= 3</font>, and verified
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3</font>),
+ we would like to examine the behavior of verified
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3
+ </font>and find out whether its tree size remains between the tree sizes
+ associated with <font FACE="CMMI10" SIZE="2">R </font>
+ <font FACE="CMR10" SIZE="2">= 2 </font>and <font FACE="CMMI10" SIZE="2">R
+ </font><font FACE="CMR10" SIZE="2">= 3</font>, or whether it approaches
+ the size of one</p>
+ <font FACE="Times New Roman" SIZE="1">
+ <hr noshade color="#000000" align="justify" width="35%" size="1">
+ <p ALIGN="LEFT"><sup>3</sup>
+ <a href="http://www.cs.biu.ac.il/~davoudo/genesis">
+ http://www.cs.biu.ac.il/~davoudo/genesis</a></p>
+ </font></font><font FACE="Times New Roman" SIZE="1"><hr>
+ <p ALIGN="LEFT"> </p>
+ <div align="center">
+ <center>
+ <table border="0" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="100%" id="AutoNumber8">
+ <tr>
+ <td width="33%">
+ <p align="left"> </td>
+ <td width="33%">
+ <p align="center"><font size="2">Verified Null-Move Pruning</font></td>
+ <td width="34%">
+ <p align="right"><font size="2">157</font></td>
+ </tr>
+ </table>
+ </center>
+ </div>
+ </font>
+ <p ALIGN="LEFT"> </p>
+ <div align="center">
+ <center>
+ <table border="1" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" id="AutoNumber9">
+ <tr>
+ <td><font FACE="Courier" SIZE="2">
+ <p ALIGN="LEFT">#define R 3 </font>
+ <font FACE="Times New Roman" SIZE="2">/* the depth reduction factor
+ */<br>
+ /* at the root level, verify = true */</font><font FACE="Courier" SIZE="2"><br>
+ int search (alpha, beta, depth, verify) {<br>
+ if (depth </font><font FACE="CMMI10" SIZE="2"><</font><font FACE="Courier" SIZE="2">=
+ 0)<br>
+ return evaluate(); </font>
+ <font FACE="Times New Roman" SIZE="2">/* in practice, quiescence()
+ is called here */<br>
+ </font><font FACE="Courier" SIZE="2"> </font>
+ <font FACE="Times New Roman" SIZE="2">/* if verify = true, and depth
+ = 1, null-move search is not conducted, since<br>
+ </font><font FACE="Courier" SIZE="2"> </font>
+ <font FACE="Times New Roman" SIZE="2"> * verification will not
+ be possible */<br>
+ </font><font FACE="Courier" SIZE="2"> if (</font><font FACE="CMR10" SIZE="2">!</font><font FACE="Courier" SIZE="2">in_check()
+ && null_ok() && (</font><font FACE="CMR10" SIZE="2">!</font><font FACE="Courier" SIZE="2">verify
+ || depth </font><font FACE="CMMI10" SIZE="2">> </font>
+ <font FACE="Courier" SIZE="2">1)) {<br>
+ make_null_move();</font><font FACE="Times New Roman" SIZE="2"><br>
+ </font><font FACE="Courier" SIZE="2">
+ </font><font FACE="Times New Roman" SIZE="2">/* null-move search
+ with minimal window around beta */<br>
+ </font><font FACE="Courier" SIZE="2">
+ value = -search(-beta, -beta + 1, depth - R - 1,<br>
+
+ verify);<br>
+ if (value </font>
+ <font FACE="CMMI10" SIZE="2">></font><font FACE="Courier" SIZE="2">=
+ beta)</font><font FACE="CMSY10" SIZE="2"> { </font>
+ <font FACE="Times New Roman" SIZE="2">/* fail-high */<br>
+ </font><font FACE="Courier" SIZE="2">
+ if (verify) {<br>
+
+ depth--; </font><font FACE="Times New Roman" SIZE="2">/* reduce the
+ depth by one ply */<br>
+ </font><font FACE="Courier" SIZE="2">
+ </font><font FACE="Times New Roman" SIZE="2">/* turn verification
+ off for the sub-tree */<br>
+ </font><font FACE="Courier" SIZE="2">
+ verify = false;<br>
+
+ </font><font FACE="Times New Roman" SIZE="2">/* mark a fail-high
+ flag, to detect zugzwangs later*/<br>
+ </font><font FACE="Courier" SIZE="2">
+ fail high = true;<br>
+ }<br>
+ else </font>
+ <font FACE="Times New Roman" SIZE="2">/* cutoff in a sub-tree with
+ fail-high report */<br>
+ </font><font FACE="Courier" SIZE="2">
+ return value;<br>
+ }<br>
+ }<br>
+ re search: </font><font FACE="Times New Roman" SIZE="2">/* if a
+ zugzwang is detected, return here for re-search */<br>
+ </font><font FACE="Courier" SIZE="2"> </font>
+ <font FACE="Times New Roman" SIZE="2">/* do regular NegaScout/PVS
+ search */<br>
+ </font><font FACE="Courier" SIZE="2"> </font>
+ <font FACE="Times New Roman" SIZE="2">/* search() is called with
+ current value of �verify� */<br>
+ </font><font FACE="Courier" SIZE="2"> </font>
+ <font FACE="Times New Roman" SIZE="2">. . .<br>
+ </font><font FACE="Courier" SIZE="2"> </font>
+ <font FACE="Times New Roman" SIZE="2">/* if there is a fail-high
+ report, but no cutoff was found, the position<br>
+ </font><font FACE="Courier" SIZE="2"> </font>
+ <font FACE="Times New Roman" SIZE="2"> * is a zugzwang and has
+ to be re-searched with the original depth */<br>
+ </font><font FACE="Courier" SIZE="2"> if(fail_high
+ && best </font><font FACE="CMMI10" SIZE="2">< </font>
+ <font FACE="Courier" SIZE="2">beta) {<br>
+ depth++;<br>
+ fail high = false;<br>
+ verify = true;<br>
+ goto re search;<br>
+ }<br>
+ }</font></td>
+ </tr>
+ </table>
+ <font FACE="Times New Roman" SIZE="2"><b>
+ <p>Figure 3</b>: Verified null-move pruning.</p>
+ </font></center>
+ </div>
+ <font FACE="Times New Roman" SIZE="2">
+ <p ALIGN="justify"> </p>
+ <p ALIGN="justify"> </p>
+ <div align="center">
+ <center>
+ <table border="1" cellpadding="3" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" id="AutoNumber10">
+ <tr>
+ <td valign="top" align="center">
+ <font FACE="Times New Roman" SIZE="2">Depth</font></td>
+ <td valign="top" align="center">
+ <font FACE="Times New Roman" SIZE="2">Std
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
+ 1</font></font></td>
+ <td valign="top" align="center">
+ <font FACE="Times New Roman" SIZE="2">Std
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
+ 2</font></font></td>
+ <td valign="top" align="center">
+ <font FACE="Times New Roman" SIZE="2">Std
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
+ 3</font></font></td>
+ <td valign="top" align="center">
+ <font FACE="Times New Roman" SIZE="2"><font FACE="CMR10" SIZE="2"> </font>Vrfd
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
+ 3</font></font></td>
+ </tr>
+ <tr>
+ <td valign="top" align="center">
+ <font FACE="Times New Roman" SIZE="2">9</font></td>
+ <td valign="top" align="center">
+ <font FACE="Times New Roman" SIZE="2">64</font></td>
+ <td valign="top" align="center">
+ <font FACE="Times New Roman" SIZE="2">62</font></td>
+ <td valign="top" align="center">
+ <font FACE="Times New Roman" SIZE="2">53</font></td>
+ <td valign="top" align="center">
+ <font FACE="Times New Roman" SIZE="2">60</font></td>
+ </tr>
+ <tr>
+ <td valign="top" align="center">
+ <font FACE="Times New Roman" SIZE="2">10</font></td>
+ <td valign="top" align="center">
+ <font FACE="Times New Roman" SIZE="2">71</font></td>
+ <td valign="top" align="center">
+ <font FACE="Times New Roman" SIZE="2">66</font></td>
+ <td valign="top" align="center">
+ <font FACE="Times New Roman" SIZE="2">65</font></td>
+ <td valign="top" align="center">
+ <font FACE="Times New Roman" SIZE="2">71</font></td>
+ </tr>
+ </table>
+ </center><b>
+ <p ALIGN="justify">Table 2</b>: Number of solved positions using
+ standard <font FACE="CMMI10" SIZE="2">R </font>
+ <font FACE="CMR10" SIZE="2">= 1</font><font FACE="CMMI10" SIZE="2">;
+ </font><font FACE="CMR10" SIZE="2">2</font><font FACE="CMMI10" SIZE="2">;
+ </font><font FACE="CMR10" SIZE="2">3 </font>and verified
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3
+ </font>at depths 9 and 10, for 138 Neishtadt test positions.</div>
+ <font FACE="Times New Roman" SIZE="1"><hr>
+ <p ALIGN="LEFT"> </p>
+ <div align="center">
+ <center>
+ <table border="0" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="100%" id="AutoNumber11">
+ <tr>
+ <td width="33%"><font size="2">158</font></td>
+ <td width="33%">
+ <p align="center"><font FACE="Times New Roman" SIZE="2">ICGA Journal</font></td>
+ <td width="34%">
+ <p align="right"><font size="2">September 2002</font></td>
+ </tr>
+ </table>
+ </center>
+ </div>
+ </font>
+ <p> </p>
+ <div align="center">
+ <center>
+ <table border="1" cellpadding="3" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" id="AutoNumber12">
+ <tr>
+ <td valign="top" align="center">
+ <font FACE="Times New Roman" SIZE="2">Depth </font></td>
+ <td align="right" valign="top">
+ <font FACE="Times New Roman" SIZE="2">Std
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
+ 2 </font></font></td>
+ <td align="right" valign="top">
+ <font FACE="Times New Roman" SIZE="2">Std
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
+ 3 </font></font></td>
+ <td align="right" valign="top">
+ <font FACE="Times New Roman" SIZE="2">Vrfd
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
+ 3</font></font></td>
+ </tr>
+ <tr>
+ <td valign="top" align="center">
+ <font FACE="Times New Roman" SIZE="2">9</font></td>
+ <td align="right" valign="top">
+ <font FACE="Times New Roman" SIZE="2">5,374,275,763<br>
+ (+10.84%) </font></td>
+ <td align="right" valign="top">
+ <font FACE="Times New Roman" SIZE="2">2,483,951,601<br>
+ (-48.76%)</font></td>
+ <td align="right" valign="top">
+ <font FACE="Times New Roman" SIZE="2">4,848,596,820<br>
+ -</font></td>
+ </tr>
+ <tr>
+ <td valign="top" align="center">
+ <font FACE="Times New Roman" SIZE="2">10</font></td>
+ <td align="right" valign="top">
+ <font FACE="Times New Roman" SIZE="2">16,952,333,579<br>
+ (+17.40%)</font></td>
+ <td align="right" valign="top">
+ <font FACE="Times New Roman" SIZE="2">7,920,812,800<br>
+ (-45.14%)</font></td>
+ <td align="right" valign="top">
+ <font FACE="Times New Roman" SIZE="2">14,439,185,304<br>
+ -</font></td>
+ </tr>
+ <tr>
+ <td valign="top" align="center">
+ <font FACE="Times New Roman" SIZE="2">11</font></td>
+ <td align="right" valign="top">
+ <font FACE="Times New Roman" SIZE="2">105,488,197,524<br>
+ (+106.51%) </font></td>
+ <td align="right" valign="top">
+ <font FACE="Times New Roman" SIZE="2">24,644,668,194<br>
+ (-51.75%)</font></td>
+ <td align="right" valign="top">
+ <font FACE="Times New Roman" SIZE="2">51,080,338,048<br>
+ -</font></td>
+ </tr>
+ </table>
+ </center><b>
+ <p ALIGN="justify">Table 3</b>: Total node count of standard
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 2</font>,
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3</font>,
+ and verified <font FACE="CMMI10" SIZE="2">R </font>
+ <font FACE="CMR10" SIZE="2">= 3 </font>at depths 9, 10, and 11, for 869
+ ECM test positions.</div>
+ <div align="center">
+ <center>
+ <table border="0" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" id="AutoNumber13">
+ <tr>
+ <td><img border="0" src="graph.gif" width="420" height="311"></td>
+ </tr>
+ </table>
+ </center><b>
+ <p align="justify">Figure 4</b>: Tree sizes of standard
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 2</font>,
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3</font>,
+ and verified <font FACE="CMMI10" SIZE="2">R </font>
+ <font FACE="CMR10" SIZE="2">= 3 </font>at depths 9, 10, and 11, for 869
+ ECM test positions.</div>
+ <p ALIGN="justify">of these trees. We therefore conducted a search to a
+ depth of 11 plies, using 869 positions from the<i> Encyclopedia of Chess
+ Middlegames </i>(ECM)<sup><font FACE="Times New Roman" SIZE="1">4</font></sup>.
+ Table 3 provides the total node counts at depths 9, 10, and 11, using
+ standard <font FACE="CMMI10" SIZE="2">R </font>
+ <font FACE="CMR10" SIZE="2">= 2</font>, <font FACE="CMMI10" SIZE="2">R
+ </font><font FACE="CMR10" SIZE="2">= 3</font>, and verified
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3</font>.
+ See also Figure 4. As Figure 4 clearly indicates, for depth 11 the size of
+ the tree constructed by verified null-move pruning with<font FACE="CMMI10" SIZE="2">
+ R </font><font FACE="CMR10" SIZE="2">= 3 </font>is closer to standard
+ null-move pruning with <font FACE="CMMI10" SIZE="2">R </font>
+ <font FACE="CMR10" SIZE="2">= 3</font>. This implies that the saving from
+ verified null-move pruning will be greater as we search more deeply. This
+ can be explained by the fact that the saving from the use of
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3
+ </font>in the shallow null-move search far exceeds the verification cost
+ of verified null-move pruning.</p>
+ <p ALIGN="justify">Having studied the effect of verified null-move pruning
+ on the search tree size, we now take a closer look at the resulting
+ tactical strength in comparison with standard null-move pruning with
+ different depth reductions.</p>
+ <p ALIGN="justify">For this purpose we used 999 positions from the <i>
+ Winning Chess Sacrifices </i>(WCS) test suite, and 434 positions of �mate
+ in 4� and 353 positions of �mate in 5� from the test suites of the <i>
+ Chess Analysis Project </i>(CAP); see the Appendix. The WCS positions were
+ searched to depths of 8, 9, and 10 plies, using standard
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 2</font>,
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3</font>,
+ and verified <font FACE="CMMI10" SIZE="2">R </font>
+ <font FACE="CMR10" SIZE="2">= 3</font>. Table 4 provides the total node
+ counts, and Table 5 gives the number of correctly solved positions for the
+ WCS test suite. For each position of �mate in 4� we conducted a search to
+ a depth of 8 plies, and for each �mate in 5� position a search to a depth
+ of 10 plies. The search was conducted using standard<font FACE="CMMI10" SIZE="2">
+ R </font><font FACE="CMR10" SIZE="2">= 1</font>,
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 2</font>,
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3</font>,
+ and verified <font FACE="CMMI10" SIZE="2">R </font>
+ <font FACE="CMR10" SIZE="2">= 3</font>. Table 6 provides the number of
+ positions that each method solved (i.e., found the checkmating sequence).</p>
+ <font FACE="Times New Roman" SIZE="1">
+ <hr noshade color="#000000" align="justify" width="35%" size="1">
+ <p ALIGN="LEFT"><sup>4</sup> Because of the large number of errors in
+ ECM�s suggested best moves, we did not check here for number of solved
+ positions.</p>
+ <font FACE="Times New Roman" SIZE="1"><hr>
+ <p ALIGN="LEFT"> </p>
+ <div align="center">
+ <center>
+ <table border="0" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="100%" id="AutoNumber14">
+ <tr>
+ <td width="33%"> </td>
+ <td width="33%"><font FACE="Times New Roman" SIZE="2">
+ <p ALIGN="center">Verified Null-Move Pruning</font></td>
+ <td width="34%">
+ <p align="right"><font size="2">159</font></td>
+ </tr>
+ </table>
+ </center>
+ </div>
+ </font>
+ <p> </p>
+ <div align="center">
+ <center>
+ <table border="1" cellpadding="3" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" id="AutoNumber15">
+ <tr>
+ <td align="left" valign="top"><font FACE="Times New Roman" SIZE="2">
+ <p ALIGN="center">Depth </font><font FACE="CMR10" SIZE="2">
+ </font></td>
+ <td align="right" valign="top">
+ <font FACE="Times New Roman" SIZE="1">
+ <font FACE="Times New Roman" SIZE="2">Std </font>
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
+ 2</font></font></td>
+ <td align="right" valign="top">
+ <font FACE="Times New Roman" SIZE="1">
+ <font FACE="Times New Roman" SIZE="2">Std </font>
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
+ 3</font></font></td>
+ <td align="right" valign="top">
+ <font FACE="Times New Roman" SIZE="1">
+ <font FACE="Times New Roman" SIZE="2">Vrfd </font>
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
+ 3</font></font></td>
+ </tr>
+ <tr>
+ <td valign="top" align="center">
+ <font FACE="Times New Roman" SIZE="2">8</font></td>
+ <td align="right" valign="top">
+ <font FACE="Times New Roman" SIZE="2">783,461,647<br>
+ (-13.55%)</font></td>
+ <td align="right" valign="top">
+ <font FACE="Times New Roman" SIZE="2">533,282,695<br>
+ (-41.15%)</font></td>
+ <td align="right" valign="top">
+ <font FACE="Times New Roman" SIZE="2">906,225,552<br>
+ -</font></td>
+ </tr>
+ <tr>
+ <td valign="top" align="center">
+ <font FACE="Times New Roman" SIZE="2">9</font></td>
+ <td align="right" valign="top">
+ <font FACE="Times New Roman" SIZE="2">3,742,064,688<br>
+ (+47.38%)</font></td>
+ <td align="right" valign="top">
+ <font FACE="Times New Roman" SIZE="2">1,316,719,980<br>
+ (-48.14%)</font></td>
+ <td align="right" valign="top">
+ <font FACE="Times New Roman" SIZE="2">2,539,057,043<br>
+ -</font></td>
+ </tr>
+ <tr>
+ <td valign="top" align="center">
+ <font FACE="Times New Roman" SIZE="2">10</font></td>
+ <td align="right" valign="top"><font size="2">11,578,143,939</font><font FACE="Times New Roman" SIZE="2"><br>
+ (+46.75%) </font></td>
+ <td align="right" valign="top">
+ <font FACE="Times New Roman" SIZE="2">4,871,295,877<br>
+ (-38.26%)</font></td>
+ <td align="right" valign="top">
+ <font FACE="Times New Roman" SIZE="2">7,889,544,754<br>
+ -</font></td>
+ </tr>
+ </table>
+ </center><font FACE="Times New Roman" SIZE="2"><b>
+ <p ALIGN="justify">Table 4</b>: Total node count of standard </font>
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 2</font><font FACE="Times New Roman" SIZE="2">,
+ </font><font FACE="CMMI10" SIZE="2">R </font>
+ <font FACE="CMR10" SIZE="2">= 3 </font>
+ <font FACE="Times New Roman" SIZE="2">and verified </font>
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3
+ </font><font FACE="Times New Roman" SIZE="2">at depths 8, 9, and 10, for
+ 999 WCS test positions.</font></div>
+ <div align="center">
+ <center>
+ <table border="1" cellpadding="3" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" id="AutoNumber16">
+ <tr>
+ <td valign="top"><font FACE="Times New Roman" SIZE="2">
+ <p ALIGN="center">Depth</font></td>
+ <td valign="top"><font FACE="Times New Roman" SIZE="1">
+ <font FACE="Times New Roman" SIZE="2">Std </font>
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
+ 2</font></font></td>
+ <td valign="top"><font FACE="Times New Roman" SIZE="1">
+ <font FACE="Times New Roman" SIZE="2">Std </font>
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
+ 3</font></font></td>
+ <td valign="top"><font FACE="Times New Roman" SIZE="1">
+ <font FACE="Times New Roman" SIZE="2">Vrfd </font>
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
+ 3</font></font></td>
+ </tr>
+ <tr>
+ <td valign="top"><font FACE="Times New Roman" SIZE="2">
+ <p ALIGN="center">8</font></td>
+ <td valign="top" align="center">
+ <font FACE="Times New Roman" SIZE="2">762</font></td>
+ <td valign="top" align="center">
+ <font FACE="Times New Roman" SIZE="2">760</font></td>
+ <td valign="top" align="center">
+ <font FACE="Times New Roman" SIZE="2">782</font></td>
+ </tr>
+ <tr>
+ <td valign="top"><font FACE="Times New Roman" SIZE="2">
+ <p ALIGN="center">9</font></td>
+ <td valign="top" align="center">
+ <font FACE="Times New Roman" SIZE="2">838</font></td>
+ <td valign="top" align="center">
+ <font FACE="Times New Roman" SIZE="2">812</font></td>
+ <td valign="top" align="center">
+ <font FACE="Times New Roman" SIZE="2">838</font></td>
+ </tr>
+ <tr>
+ <td valign="top"><font FACE="Times New Roman" SIZE="2">
+ <p ALIGN="center">10</font></td>
+ <td valign="top" align="center">
+ <font FACE="Times New Roman" SIZE="2">850</font></td>
+ <td valign="top" align="center">
+ <font FACE="Times New Roman" SIZE="2">849</font></td>
+ <td valign="top" align="center">
+ <font FACE="Times New Roman" SIZE="2">866</font></td>
+ </tr>
+ </table>
+ </center><font FACE="Times New Roman" SIZE="2"><b>
+ <p ALIGN="justify">Table 5</b>: Number of solved positions using </font>
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 2</font><font FACE="Times New Roman" SIZE="2">,
+ </font><font FACE="CMMI10" SIZE="2">R </font>
+ <font FACE="CMR10" SIZE="2">= 3 </font>
+ <font FACE="Times New Roman" SIZE="2">and verified </font>
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3
+ </font><font FACE="Times New Roman" SIZE="2">at depths 8, 9, and 10 for
+ 999 WCS test positions.</font></div>
+ <div align="center">
+ <center>
+ <table border="1" cellpadding="3" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" id="AutoNumber17">
+ <tr>
+ <td align="center" valign="top">
+ <font FACE="Times New Roman" SIZE="2">Test Suite</font></td>
+ <td align="center" valign="top">
+ <font FACE="Times New Roman" SIZE="1">
+ <font FACE="Times New Roman" SIZE="2">Std </font>
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
+ 1</font></font></td>
+ <td align="center" valign="top">
+ <font FACE="Times New Roman" SIZE="1">
+ <font FACE="Times New Roman" SIZE="2">Std </font>
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
+ 2</font></font></td>
+ <td align="center" valign="top">
+ <font FACE="Times New Roman" SIZE="1">
+ <font FACE="Times New Roman" SIZE="2">Std </font>
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
+ 3</font></font></td>
+ <td align="center" valign="top">
+ <font FACE="Times New Roman" SIZE="1">
+ <font FACE="Times New Roman" SIZE="2">Vrfd </font>
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
+ 3</font></font></td>
+ </tr>
+ <tr>
+ <td align="center" valign="top">
+ <font FACE="Times New Roman" SIZE="2">�Mate in 4�<br>
+ Depth 8 plies</font></td>
+ <td align="center" valign="top">
+ <font FACE="Times New Roman" SIZE="1">
+ <font FACE="Times New Roman" SIZE="2">433</font></font></td>
+ <td align="center" valign="top">
+ <font FACE="Times New Roman" SIZE="1">
+ <font FACE="Times New Roman" SIZE="2">385</font></font></td>
+ <td align="center" valign="top">
+ <font FACE="Times New Roman" SIZE="1">
+ <font FACE="Times New Roman" SIZE="2">379</font></font></td>
+ <td align="center" valign="top">
+ <font FACE="Times New Roman" SIZE="1">
+ <font FACE="Times New Roman" SIZE="2">431</font></font></td>
+ </tr>
+ <tr>
+ <td align="center" valign="top">
+ <font FACE="Times New Roman" SIZE="2">�Mate in 5�<font FACE="Times New Roman" SIZE="2"><br>
+ Depth 10 plies</font> </font></td>
+ <td align="center" valign="top">
+ <font FACE="Times New Roman" SIZE="1">
+ <font FACE="Times New Roman" SIZE="2">347</font></font></td>
+ <td align="center" valign="top">
+ <font FACE="Times New Roman" SIZE="1">
+ <font FACE="Times New Roman" SIZE="2">292</font></font></td>
+ <td align="center" valign="top">
+ <font FACE="Times New Roman" SIZE="1">
+ <font FACE="Times New Roman" SIZE="2">286</font></font></td>
+ <td align="center" valign="top">
+ <font FACE="Times New Roman" SIZE="1">
+ <font FACE="Times New Roman" SIZE="2">340</font></font></td>
+ </tr>
+ </table>
+ </center><font FACE="Times New Roman" SIZE="2"><b>
+ <p align="justify">Table 6</b>: Numbers of solved positions using
+ standard </font><font FACE="CMMI10" SIZE="2">R </font>
+ <font FACE="CMR10" SIZE="2">= 1</font><font FACE="CMMI10" SIZE="2">;
+ </font><font FACE="CMR10" SIZE="2">2</font><font FACE="CMMI10" SIZE="2">;
+ </font><font FACE="CMR10" SIZE="2">3 </font>
+ <font FACE="Times New Roman" SIZE="2">and verified </font>
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3
+ </font><font FACE="Times New Roman" SIZE="2">for 434 �mate in 4� and 353
+ �mate in 5� test suites.</font></div>
+ <font FACE="Times New Roman" SIZE="2">
+ <p ALIGN="justify">The results in Tables 5 and 6 indicate that verified
+ null-move pruning solved far more positions than standard null-move
+ pruning with depth reductions of </font><font FACE="CMMI10" SIZE="2">R
+ </font><font FACE="CMR10" SIZE="2">= 2 </font>
+ <font FACE="Times New Roman" SIZE="2">and </font>
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3</font><font FACE="Times New Roman" SIZE="2">.
+ This demonstrates that not only does verified null-move pruning result in
+ a reduced search effort (the constructed search tree is closer in size to
+ that of standard </font><font FACE="CMMI10" SIZE="2">R </font>
+ <font FACE="CMR10" SIZE="2">= 3</font><font FACE="Times New Roman" SIZE="2">),
+ but its tactical strength is greater than that of standard </font>
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 2</font><font FACE="Times New Roman" SIZE="2">,
+ which is the common depth reduction value.</p>
+ <p ALIGN="justify">Finally, to study the overall advantage of verified
+ null-move pruning over standard null-move pruning in practice, we
+ conducted 100 self-play games, using two versions of the G</font><font FACE="Times New Roman" SIZE="1">ENESIS
+ </font><font FACE="Times New Roman" SIZE="2">engine, one with verified
+ </font><font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
+ 3</font><font FACE="Times New Roman" SIZE="2"> and the other with standard
+ </font><font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">=
+ 2</font><font FACE="Times New Roman" SIZE="2">. The time control was set
+ to 60 minutes per game. The version using verified </font>
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3
+ </font><font FACE="Times New Roman" SIZE="2">scored 68.5 out of 100 (see
+ the Appendix), which demonstrates the superiority of verified null-move
+ pruning over the standard version.</font></p>
+ <font FACE="Times New Roman" SIZE="2"><b>
+ <p ALIGN="justify">5. CONCLUSION</p>
+ </b>
+ <p ALIGN="justify">In this article we introduced a new null-move pruning
+ method which outperforms standard null-move pruning, techniques, in terms
+ of reducing the search tree size as well as gaining greater tactical
+ strength. The idea of not cutting off the search as soon as the shallow
+ null-move search indicates a fail-high allows verification of the cutoff,
+ which results in greater tactical accuracy and prevents errors due to
+ zugzwangs. We showed empirically that verified null-move pruning with a
+ depth reduction of </font><font FACE="CMMI10" SIZE="2">R </font>
+ <font FACE="CMR10" SIZE="2">= 3 </font>
+ <font FACE="Times New Roman" SIZE="2">constructs a search tree which is
+ closer in size to that of the tree constructed by standard </font>
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 3</font><font FACE="Times New Roman" SIZE="2">,
+ and that the saving from the reduced search effort in comparison with
+ standard </font><font FACE="CMMI10" SIZE="2">R </font>
+ <font FACE="CMR10" SIZE="2">= 2 </font>
+ <font FACE="Times New Roman" SIZE="2">becomes greater as we search more
+ deeply. We also showed that on average, the tactical strength of verified
+ null-move pruning is greater than that of standard null-move pruning with</font><font FACE="CMMI10" SIZE="2">
+ R </font><font FACE="CMR10" SIZE="2">= 2</font><font FACE="Times New Roman" SIZE="2">.
+ Moreover, verified null-move pruning can be implemented within any
+ standard null-move pruning framework by merely adding a few lines of code.</font></p>
+ <font FACE="Times New Roman" SIZE="2">
+ <p ALIGN="justify">We considered a number of variants of standard
+ null-move pruning. The first variant was not to cut off at all upon
+ fail-high reports, but rather reduce the depth by 2 plies. We obtained
+ good results with this idea, but its tactical strength was sometimes
+ smaller than that of standard </font><font FACE="CMMI10" SIZE="2">R </font>
+ <font FACE="CMR10" SIZE="2">= 2</font><font FACE="Times New Roman" SIZE="2">.
+ We concluded that in order to improve the results, the depth should not be
+ reduced by more than one ply at a time upon fail-high reports. An
+ additional variant was not to cut off at any node, not even in the subtree
+ of a node with a fail-high report, but</p>
+ <font FACE="Times New Roman" SIZE="1"><hr>
+ <p ALIGN="LEFT"> </p>
+ <div align="center">
+ <center>
+ <table border="0" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="100%" id="AutoNumber18">
+ <tr>
+ <td width="33%"><font size="2">160</font></td>
+ <td width="33%">
+ <p align="center"><font FACE="Times New Roman" SIZE="2">ICGA Journal</font></td>
+ <td width="34%">
+ <p align="right"><font size="2">September 2002</font></td>
+ </tr>
+ </table>
+ </center>
+ </div>
+ </font></font></font><font FACE="Times New Roman">
+ <font FACE="Times New Roman" SIZE="2">
+ <p ALIGN="justify">merely to reduce the depth by one ply upon a fail-high
+ report. Unfortunately, the size of the resulting search tree exceeded the
+ size of the tree constructed by standard </font>
+ <font FACE="CMMI10" SIZE="2">R </font><font FACE="CMR10" SIZE="2">= 2</font><font FACE="Times New Roman" SIZE="2">.
+ Still, another variant was to reduce the depth by one ply upon fail-high
+ reports, and to reduce the depth by two plies upon fail-high reports in
+ that node�s subtree, rather than cutting off.</p>
+ <p ALIGN="justify">Our empirical studies showed that cutting off the
+ search at the subtree of a fail-high reported node does not decrease
+ tactical strength. Indeed, this is the verified null-move pruning version
+ that we studied in this article. In contrast to the standard approach
+ which advocates the use of immediate cutoff, the novel approach taken here
+ uses depth reduction, and delays cutting off the search until further
+ verification. This yields greater tactical strength and a smaller search
+ tree.</p>
+ <b>
+ <p align="justify">6. REFERENCES</p>
+ </b>
+ <p align="justify">Beal, D.F. (1989). Experiments with the null move. <i>
+ Advances in Computer Chess 5</i>, (Ed. D.F. Beal) , pp. 65�79. Elsevier
+ Science Publishers, Amsterdam, The Netherlands. ISBN 0-444-87-159-4.</p>
+ <p align="justify">Berliner, H.J. (1974). <i>Chess as Problem Solving: The
+ Development of a Tactics Analyzer</i>. Ph.D. thesis, Carnegie-Mellon
+ University, Pittsburgh, PA.</p>
+ <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">.
+ <i>ICCA Journal</i>, Vol. 10, No. 3, pp. 111�117.</font></p>
+ <p align="justify"><font FACE="Times New Roman" SIZE="2">Berliner, H.J.
+ and Ebeling, C. (1990). H</font><font FACE="Times New Roman" SIZE="1">ITECH</font><font FACE="Times New Roman" SIZE="2">.
+ <i>Computers, Chess and Cognition </i>(Eds. T.A. Marsland and J.
+ Schaeffer), pp. 79�109. Springer-Verlag, New York, N.Y. ISBN
+ 0-387-97415-6/3-540-97415-6.</p>
+ <p align="justify">Birmingham, J.A. and Kent, P. (1977). Tree-searching
+ and tree-pruning techniques. <i>Advances in Computer Chess 1</i>, (Ed.
+ M.R.B. Clarke), pp. 89�107. Edinburgh University Press, Edinburgh. ISBN
+ 0-852-24292-1.</p>
+ <p align="justify">Campbell, M.S. and Marsland, T.A. (1983). A comparison
+ of minimax tree search algorithms. <i>Artificial Intelligence</i>, Vol.
+ 20, No. 4, pp. 347�367. ISSN 0004-3702.</p>
+ <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">.
+ <i>Chess Skill in Man and Machine</i>, (Ed. P.W. Frey), pp. 201�210.
+ Springer-Verlag, New York, N.Y., 2nd ed., ISBN
+ 0-387-90790-4/3-540-90790-4.</p>
+ <p align="justify">Condon, J.H. and Thompson, K. (1983b), B</font><font FACE="Times New Roman" SIZE="1">ELLE
+ </font><font FACE="Times New Roman" SIZE="2">chess hardware. <i>Advances
+ in Computer Chess 3</i>, (Ed. M.R.B. Clarke), pp. 45�54. Pergamon Press,
+ Oxford, ISBN 0-080-26898-6.</p>
+ <p align="justify">Donninger, C. (1993). Null move and deep search:
+ Selective search heuristics for obtuse chess programs.<i> ICCA Journal</i>,
+ Vol. 16, No. 3, pp. 137�143.</p>
+ <p align="justify">Ebeling, C. (1986). <i>All the Right Moves: A VLSI
+ Architecture for Chess</i>. MIT Press, Cambridge, MA., ISBN 0-262-05035-8.</p>
+ <p align="justify">Feist, M. (1999). The 9th World Computer-Chess
+ Championship: Report on the tournament. <i>ICCA Journal</i>, Vol. 22, No.
+ 3, pp. 155�164.</p>
+ <p align="justify">Goetsch, G. and Campbell, M.S. (1990). Experiments with
+ the null-move heuristic. <i>Computers, Chess, and Cognition</i>, (Eds. T.A.
+ Marsland and J. Schaeffer), pp. 159�168. Springer-Verlag, New York, N.Y.,
+ ISBN 0-387-97415-6/3-540-97415-6.</p>
+ <p align="justify">Gillogy, J.J. (1972). The technology chess program. <i>
+ Artificial Intelligence</i>, Vol. 3, No. 1-3, pp. 145�163. ISSN 0004-3702.</p>
+ <p align="justify">Hammilton, S. and Garber, L. (1997). D</font><font FACE="Times New Roman" SIZE="1">EEP
+ </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">�s
+ hardware-software synergy. <i>IEEE Computer</i>, Vol. 30, No. 10, pp.
+ 29�35.</p>
+ <p align="justify">Heinz, E.A. (1999). Adaptive null-move pruning, <i>ICCA
+ Journal</i>, Vol. 22, No. 3, pp. 123�132.</p>
+ <p align="justify">Herik, H.J. van den and Herschberg, I.S. (1992). The
+ 7th World Computer-Chess Championship: Report on the tournament. <i>ICCA
+ Journal</i>, Vol. 15, No. 4, pp. 208�209.</p>
+ <p align="justify">Hsu, F.-h. (1999). IBM�s D</font><font FACE="Times New Roman" SIZE="1">EEP
+ </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">chess grandmaster chips. <i>
+ IEEE Micro</i>, Vol. 19, No. 2, pp. 70�80.</font></p>
+ <font FACE="Times New Roman" SIZE="2"></font>
+ <font FACE="Times New Roman" SIZE="1"><hr>
+ <p ALIGN="justify"> </p>
+ <table border="0" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="100%" id="AutoNumber19">
+ <tr>
+ <td width="33%">
+ <p align="left"> </td>
+ <td width="33%">
+ <p align="center"><font face="Times New Roman" size="2">Verified
+ Null-Move Pruning</font></td>
+ <td width="34%">
+ <p align="right"><font size="2">161</font></td>
+ </tr>
+ </table>
+ </font><font FACE="Times New Roman" SIZE="2">
+ <p ALIGN="justify">Hsu, F.-h., Anantharaman, T.S., Campbell, M.S., and
+ Nowatzyk, A. (1990). D</font><font FACE="Times New Roman" SIZE="1">EEP
+ </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">.
+ <i>Computers, Chess, and Cognition</i>, (Eds. T.A. Marsland and J.
+ Schaeffer), pp. 55�78. Springer-Verlag, New York, N.Y. ISBN
+ 0-387-97415-6/3-540-97415-6.</p>
+ <p ALIGN="justify">Hyatt, R.M., Gower, A.E., and Nelson, H.L. (1990). C</font><font FACE="Times New Roman" SIZE="1">RAY
+ </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">,
+ <i>Computers, Chess, and Cognition</i>, (Eds. T.A. Marsland and J.
+ Schaeffer), pp. 111�130. Springer-Verlag, New York, N.Y. ISBN
+ 0-387-97415-6/3-540- 97415-6.</p>
+ <p ALIGN="justify">Nelson, H.L. (1985). Hash tables in C</font><font FACE="Times New Roman" SIZE="1">RAY
+ </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">.
+ <i>ICCA Journal</i>, Vol. 8, No. 1, pp. 3�13.</p>
+ <p ALIGN="justify">Newborn, M.M. (1975). <i>Computer Chess</i>. Academic
+ Press. New York, N.Y. ISBN 0-125-17250-8.</p>
+ <p ALIGN="justify">Plenkner, S. (1995). A null-move technique impervious
+ to zugzwang. <i>ICCA Journal</i>, Vol. 18, No. 2, pp. 82�84.</p>
+ <p ALIGN="justify">Reinefeld, A. (1983). An improvement to the S</font><font FACE="Times New Roman" SIZE="1">COUT
+ </font><font FACE="Times New Roman" SIZE="2">tree-search algorithm. <i>
+ ICCA Journal</i>, Vol. 6, No. 4, pp. 4�14.</p>
+ <p ALIGN="justify">Schaeffer, J. (1983). The history heuristic. <i>ICCA
+ Journal</i>, Vol. 6, No. 3, pp. 16�19.</p>
+ <p ALIGN="justify">Schaeffer, J. (1989). The history heuristic and
+ alpha-beta search enhancements in practice. <i>IEEE Transactions on
+ Pattern Analysis and Machine Intelligence</i>, Vol. 11, No. 11, pp.
+ 1203�1212. ISSN 0162-8828.</p>
+ <p ALIGN="justify">Slagle, J.R. (1971). <i>Artificial Intelligence: The
+ Heuristic Programming Approach</i>. McGraw-Hill, New York, N.Y.</p>
+ <p ALIGN="justify">Slate, D.J. and Atkin, L.R. (1977). C</font><font FACE="Times New Roman" SIZE="1">HESS
+ </font><font FACE="Times New Roman" SIZE="2">4.5 � The Northwestern
+ University chess program. <i>Chess Skill in Man and Machine</i>, (Ed. P.W.
+ Frey), pp. 82�118. Springer-Verlag, New York, N.Y., 2nd ed. 1983, ISBN
+ 0-387-90790-4/3-540-90790-4.</p>
+ <p ALIGN="justify">Tsang, H.K. and Beal, D.F. (1995). The 8thWorld
+ Computer-Chess Championship: Report on the tournament and the contestants�
+ programs described. <i>ICCA Journal</i>, Vol. 18, No. 2, pp. 93�101.</p>
+ <b>
+ <p ALIGN="justify">7. ACKNOWLEDGEMENTS</p>
+ </b>
+ <p ALIGN="justify">We would like to thank Shay Bushinsky for his interest
+ in our research, and for promoting the discipline of Computer Chess in our
+ department. We would also like to thank Dann Corbit for providing the CAP
+ test positions for our empirical studies, and Azriel Rosenfeld for his
+ editorial comments. Finally, we are indebted to Jonathan Schaeffer and
+ Christian Donninger for their enlightening remarks and suggestions.</p>
+ <b>
+ <p ALIGN="justify">8. APPENDIX</p>
+ <p ALIGN="justify">EXPERIMENTAL SETUP</p>
+ </b>
+ <p ALIGN="justify">Our experimental setup consisted of the following
+ resources:</p>
+ <ul>
+ <li>
+ <p ALIGN="justify">138 positions (Diagrams 241 to 378) from: Yakov
+ Neishtadt (1993). <i>Test Your Tactical Ability</i>, pp. 110�135.
+ Batsford, ISBN 0-7134-4013-9.<br>
+ </li>
+ <li>
+ <p ALIGN="justify"><font FACE="Times New Roman" SIZE="2">869 positions
+ from <i>Encyclopedia of Chess Middlegames</i>, and 999 positions from <i>
+ Winning Chess Sacrifices</i>, as available on the Internet.<font FACE="Times New Roman" SIZE="2"><br>
+ </font></font></li>
+ <li>
+ <p ALIGN="justify"><font FACE="Times New Roman" SIZE="2">434 �Mate in 4�
+ and 353 �Mate in 5� positions from <i>Chess Analysis Project</i>,
+ available at <a href="ftp://cap.connx.com/">ftp://cap.connx.com/</a><br>
+ </font></li>
+ <li>
+ <p ALIGN="justify"><font FACE="Times New Roman" SIZE="2">G<font FACE="Times New Roman" SIZE="1">ENESIS
+ </font>chess engine, with <font FACE="CMR10" SIZE="2">2</font><sup>22</sup><font FACE="CMR7" SIZE="1">
+ </font>transposition table entries (64MB), running on a 733 MHz Pentium
+ III with 256MB RAM, with the Windows 98 operating system.</font></li>
+ </ul>
+ <p ALIGN="justify">The webpage
+ <a href="http://www.cs.biu.ac.il/~davoudo/pubs.html">
+ http://www.cs.biu.ac.il/~davoudo/pubs.html</a> contains additional
+ information about the test suites, move lists of self-play games, and
+ detailed experimental results.</font></font></font></td>
+ </tr>
+ </table>
+ </center>
+</div>
+
+</body>
+
+</html>
\ No newline at end of file |