Author: Ernst A. Heinz Title: ``Scalable Search in Computer Chess'' Subtitle: Algorithmic Enhancements and Experiments at High Search Depths Series: Computational Intelligence (ser. eds. Profs. Bibel and Kruse) Publisher: Vieweg Verlag [268 pages, 31 figures, 57 tables] ISBN: 3-528-05732-7
AlthoughVieweg Verlag operates mainly in Germany, the entire book is writtenin English.
Please clickhereto view animage of the cover illustration.
Independent reviews of the book by Dr. Dap Hartmann (in English) andDr. Christian Donninger (in German) were published in theICCA Journaland the periodicalComputer-Schach & Spiele in March /April 2000. Excerpts from thesereviews follow below.
Morgan Kaufmann Publishers distribute the book in the US and worldwide in all othercountries except for Austria, Germany, and Switzerland (Vieweg's homedomain). As of October 2000, the book was available for online purchasefrom Amazon, Barnes&Noble.com, Bertelsmann Online, Booxtra, Brian'sBooks, Buch.de, Kaigai, Morgan Kaufmann Online, Netstore/USA.com,VarsityBooks.com, Vieweg's Internet Bookshop, and Yurinsha (amongothers) at the following URLs.
http://www.amazon.com/exec/obidos/ASIN/3528057327/
http://www.amazon.co.jp/exec/obidos/ASIN/3528057327/
http://www.amazon.co.uk/exec/obidos/ASIN/3528057327/
http://www.amazon.de/exec/obidos/ASIN/3528057327/
http://shop.barnesandnoble.com/bookSearch/isbnInquiry.asp?isbn=3528057327
http://www.bol.de/
http://www.bol.com/
http://www.uk.bol.com/
http://www.booxtra.de/
http://www.briansbooks.com/catalog/books/3528057327
http://www.buch.de/
http://www.kaigai-pub.co.jp/SHINKAN/H/H80.htm
http://www.mkp.com/books_catalog/3-52805-732-7.asp
http://www.netstore.com.au/cbbooks/352/3528057327.shtml
http://www.opengroup.com/cbbooks/352/3528057327.shtml
http://www.varsitybooks.com/detail.asp?intProductID=352805732
http://www.vieweg.de/bookshop/
http://www.yurinsha.com/320/1.htm
If you encounter any ordering problems, please take a look at MorganKaufmann's list ofinternational resellersand contact themor Vieweg's distribution officerRuediger Pechdirectly by email.
The book features a suggested retail price of 98 DM (roughly 50 US-$).I know that this is not cheap. :-( But although I sincerelyintended the book to cost much less, there was no chance to hit a lowerprice point for a printed volume in a specialty area such as computerchess (even if I renounced all royalties). So, please do not blame mefor the price.
For your information, full reprints of the preface and table ofcontents follow below - please enjoy!
This book presents the results of our past two-and-a-half years ofresearch aimed at increasing the scalability and performance ofgame-tree search in computer chess. We elaborate on our respectiveworks in the areas of (I) selective forward pruning, (II) theefficient application of game-theoretical knowledge, and (III) thebehaviour of the search at increasing depths.
The broad range of topics covered by the three distinct parts of thebook seek to provide exiting material for everybody interested in thefield of ``Computational Intelligence'', regardless of their individualfocus (researcher, student, or other). The text does not requirereaders to know about chess and computer game-playing beforehand. Theinitial chapter entitled ``Computer-Chess Primer'' introduces all thenecessary basics and fundamentals thereof.
The remaining chapters, however, go far beyond those topics. They showhow to make sophisticated game-tree searchers still more scalable atever higher depths. Throughout the whole book, our high-speed andmaster-strength chess programDARKTHOUGHT serves as a realistictest vehicle to conduct numerous experiments at unprecedented searchdepths. The extensive experimental evaluations provide convincingempirical evidence for the practical usefulness of the techniquespresented by us. These results will certainly be of special interest toresearchers and programmers of computer strategy-games alike (chess,checkers, Go, and Othello in particular).
Last but not least, I like to mention that I am most grateful to theseries editors for offering me the opportunity to publish my book undertheir auspices.
Ernst A. Heinz - September 1999
Author: Ernst A. HeinzTitle: ``Scalable Search in Computer Chess''Publisher: Vieweg Verlag [268 pages, 31 figures, 57 tables]ISBN: 3-528-05732-7Preface .......................................................... VThanks ........................................................... VIIAcknowledgements ................................................ VIIIContents ......................................................... XISummary and Contributions ........................................ 10 Computer-Chess Primer ......................................... 7 0.1 The Game of Chess ........................................ 7 0.2 Basic Search Techniques .................................. 11 0.2.1 Minimax and Negamax ............................... 11 0.2.2 Alpha-Beta ........................................ 13 0.2.3 Minimal-Window Search ............................. 16 0.2.4 Quiescence Search ................................. 17 0.3 Advanced Search Techniques ............................... 20 0.3.1 Search Extensions ................................. 20 0.3.2 Transposition Tables .............................. 22 0.3.3 Move Ordering ..................................... 22 0.3.4 Iterative Deepening ............................... 23 0.3.5 Aspiration Search ................................. 24 0.3.6 Forward Pruning ................................... 24#######################################Part I -- Forward Pruning without Tears#######################################1 Adaptive Null-Move Pruning .................................... 29 1.1 Introduction ............................................. 29 1.2 Related Work ............................................. 31 1.3 Standard Null-Move Pruning ............................... 32 1.4 Recursively Adaptive Null-Move Pruning ................... 34 1.4.1 Theory ............................................ 35 1.4.2 Practice .......................................... 36 1.5 Conclusion ............................................... 39 1.6 Appendix -- Experimental Setup ........................... 402 Extended Futility Pruning ..................................... 41 2.1 Introduction ............................................. 41 2.2 Normal Futility Pruning .................................. 42 2.2.1 Theory ............................................ 42 2.2.2 Practice .......................................... 44 2.3 Futility Pruning at Pre-Frontier Nodes ................... 44 2.3.1 Theory ............................................ 44 2.3.2 Practice .......................................... 45 2.4 Limited Razoring at Pre-Pre-Frontier Nodes ............... 47 2.4.1 Theory ............................................ 47 2.4.2 Practice .......................................... 49 2.5 Conclusion ............................................... 50 2.6 Appendix -- Experimental Setup ........................... 503 AEL Pruning ................................................... 53 3.1 Introduction ............................................. 53 3.2 Combined AEL Pruning ..................................... 54 3.2.1 Theory ............................................. 54 3.2.2 Practice ........................................... 56 3.3 Test Games ............................................... 56 3.3.1 Self-Play ......................................... 57 3.3.2 Nunn Matches ...................................... 58 3.4 Conclusion ............................................... 60 3.5 Appendix -- Experimental Setup ........................... 60###########################################Part II -- Integration of Perfect Knowledge###########################################4 Efficient Interior-Node Recognition ........................... 65 4.1 Introduction ............................................. 65 4.2 Fundamentals of Interior-Node Recognition ................ 66 4.3 Recognizers and Transposition Tables ..................... 68 4.3.1 Recognizer Results ................................ 68 4.3.2 Recognizer Scores ................................. 69 4.4 Efficient Recognizer Detection and Selection ............. 71 4.4.1 Material Signatures ............................... 72 4.4.2 Further Empirical Refinements ..................... 73 4.5 Recognizer Functions ..................................... 76 4.5.1 Implementation Example ............................ 78 4.6 Discussion and Conclusion ................................ 785 Index Schemes of Endgame Databases ............................ 83 5.1 Introduction ............................................. 83 5.2 Related Work ............................................. 85 5.3 Indexing Endgame Databases without Pawns ................. 86 5.4 Indexing Endgame Databases with Pawns .................... 88 5.4.1 The Two Kings ..................................... 88 5.4.2 Directly Rammed Pawns ............................. 89 5.4.3 En-Passant Captures ............................... 89 5.5 Further General Indexing Improvements .................... 90 5.5.1 Equal Locations ................................... 91 5.5.2 Equal Pieces ...................................... 92 5.5.3 Equal Material .................................... 94 5.6 Discussion and Conclusion ................................ 95 5.7 Appendix -- Thompson's Endgame Databases ................. 97 5.8 Appendix -- Edwards' Tablebases .......................... 98 5.9 Appendix -- Nalimov's Tablebases ......................... 986 Knowledgeable Endgame Databases ............................... 99 6.1 Introduction ............................................. 99 6.2 Knowledgeable Encoding ................................... 101 6.3 Knowledgeable Probing .................................... 105 6.4 Knowledgeable Scoring .................................... 106 6.5 Knowledgeable Querying ................................... 110 6.6 Knowledgeable Databases in Practice ...................... 112 6.7 Related Work ............................................. 114 6.7.1 Infallible Rule-Based Endgame Play in Chess ....... 117 6.8 Discussion and Conclusion ................................ 119#################################################Part III -- Search Behaviour at Increasing Depths#################################################7 DarkThought Goes Deep ......................................... 123 7.1 Introduction ............................................. 123 7.2 Search Depth vs. Strength of Chess Programs .............. 125 7.3 Newborn's Original Hypothesis Revisited .................. 128 7.4 Corrected Test Positions ................................. 129 7.5 Experimental Results ..................................... 130 7.5.1 "Best Change" Rates for All Test Positions ........ 131 7.5.2 Experimental Results for All Test Positions ....... 133 7.5.3 Experimental Results for the Opening Positions .... 135 7.5.4 Experimental Results for the Middlegame Positions . 136 7.5.5 Experimental Results for the Remaining Positions .. 138 7.6 Conclusion ............................................... 140 7.7 Appendix -- Experimental Setup ........................... 141 7.8 Appendix -- Bounds on the "Best Change" Probabilities .... 141 7.9 Appendix -- Published Results of Crafty 1997 ............. 1428 Modeling the "Go Deep" Behaviour .............................. 145 8.1 Introduction ............................................. 145 8.2 General Considerations ................................... 147 8.3 Modeling the Behaviour of Crafty ......................... 148 8.3.1 Exponential Model ................................. 148 8.3.2 Piece-Wise Linear Model ........................... 149 8.3.3 Piece-Wise Constant/Linear Model .................. 149 8.3.4 Comparative Evaluation of the Models .............. 150 8.4 Modeling the Behaviour of DarkThought .................... 150 8.4.1 Exponential Model ................................. 151 8.4.2 Piece-Wise Linear Models .......................... 152 8.4.3 Piece-Wise Constant/Linear Models ................. 153 8.4.4 Comparative Evaluation of the Models .............. 154 8.5 Discussion and Conclusion ................................ 1559 Self-Play Experiments Revisited ............................... 157 9.1 Introduction ............................................. 157 9.2 Statistical Analysis of Self-Play Experiments ............ 158 9.3 Self-Play Experiments in Computer Chess .................. 162 9.3.1 1982 -- Belle (Thompson) .......................... 162 9.3.2 1983 -- Belle (Condon and Thompson) ............... 163 9.3.3 1988 -- TechMate (Szabo and Szabo) ................ 164 9.3.4 1990 -- Hitech and Lotech (Berliner et al.) ....... 166 9.3.5 1994 -- Zugzwang (Mysliwietz) ..................... 171 9.3.6 1996 -- Phoenix (Schaeffer) ....................... 172 9.3.7 1997 -- The Turk (Junghanns et al.) ............... 173 9.4 Self-Play Experiments in Computer Checkers ............... 174 9.4.1 1993 -- Chinook (Schaeffer et al.) ................ 174 9.4.2 1995 -- Chinook (Schaeffer et al.) ................ 174 9.5 Self-Play Experiments in Computer Othello ................ 175 9.5.1 1990 -- Bill (Lee and Mahajan) .................... 175 9.5.2 1997 -- Keyano (Brockington) ...................... 176 9.6 Conclusion ............................................... 178Perspectives on Future Work ...................................... 181#####################Part IV -- Appendices#####################A How DarkThought Plays Chess ................................... 185 A.1 Introduction ............................................. 185 A.2 Implementation History ................................... 186 A.3 Bitboard Engine .......................................... 187 A.3.1 Bitboard Infrastructure ........................... 187 A.3.2 Rotated Bitboards ................................. 189 A.4 Search Engine ............................................ 191 A.4.1 Node Expansion .................................... 192 A.4.2 Extension Heuristics .............................. 193 A.4.3 Search Parameterization ........................... 194 A.5 Evaluation Engine ........................................ 195 A.5.1 Programmable Evaluation Function .................. 195 A.5.2 Evaluation Machines ............................... 197 A.6 Future Work .............................................. 198B Tournament History of DarkThought ............................. 199 B.1 World Championships ...................................... 199 B.2 AEGON Man vs. Machine Tournaments ........................ 200 B.3 Public Exhibition Matches ................................ 200C DarkThought and Test Suites ................................... 201 C.1 Solution Times for BS-2830 ............................... 201 C.2 Solution Times for BT-2630 ............................... 201 C.3 Solution Times for LCT-II ................................ 201 C.4 Measured Peak Speed ...................................... 202 C.5 Test Configuration ....................................... 202D DarkThought at Test Games ..................................... 203 D.1 Test Games vs. Strong PC Chess Programs .................. 203 D.1.1 Games Played from Nunn Position #2 (ECO B89) ...... 205 D.1.2 Games Played from Nunn Position #3 (ECO C19) ...... 210 D.1.3 Games Played from Nunn Position #4 (ECO C97) ...... 214 D.1.4 Games Played from Nunn Position #5 (ECO D36) ...... 219 D.1.5 Games Played from Nunn Position #7 (ECO E15) ...... 224 D.1.6 Games Played from Nunn Position #8 (ECO E98) ...... 229 D.1.7 Games Played from Nunn Position #9 (ECO A25) ...... 234 D.2 Selected Self-Play Games ................................. 238Bibliography ..................................................... 243Index ............................................................ 259
