``Scalable Search in Computer Chess''  --  My Latest Book !!



  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



General

Although Vieweg Verlag operates mainly in Germany, the entire book is written in English.
Please click here to view an image of the cover illustration.

Independent reviews of the book by Dr. Dap Hartmann (in English) and Dr. Christian Donninger (in German) were published in the ICCA Journal and the periodical Computer-Schach & Spiele in March /April 2000. Excerpts from these reviews follow below.



Ordering and Price Information

Morgan Kaufmann Publishers distribute the book in the US and worldwide in all other countries except for Austria, Germany, and Switzerland (Vieweg's home domain). As of October 2000, the book was available for online purchase from Amazon, Barnes&Noble.com, Bertelsmann Online, Booxtra, Brian's Books, Buch.de, Kaigai, Morgan Kaufmann Online, Netstore/USA.com, VarsityBooks.com, Vieweg's Internet Bookshop, and Yurinsha (among others) 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 Morgan Kaufmann's list of international resellers and contact them or Vieweg's distribution officer Ruediger Pech directly 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 sincerely intended the book to cost much less, there was no chance to hit a lower price point for a printed volume in a specialty area such as computer chess (even if I renounced all royalties). So, please do not blame me for the price.

For your information, full reprints of the preface and table of contents follow below - please enjoy!



Preface

This book presents the results of our past two-and-a-half years of research aimed at increasing the scalability and performance of game-tree search in computer chess. We elaborate on our respective works in the areas of (I) selective forward pruning, (II) the efficient application of game-theoretical knowledge, and (III) the behaviour of the search at increasing depths.

The broad range of topics covered by the three distinct parts of the book seek to provide exiting material for everybody interested in the field of ``Computational Intelligence'', regardless of their individual focus (researcher, student, or other). The text does not require readers to know about chess and computer game-playing beforehand. The initial chapter entitled ``Computer-Chess Primer'' introduces all the necessary basics and fundamentals thereof.

The remaining chapters, however, go far beyond those topics. They show how to make sophisticated game-tree searchers still more scalable at ever higher depths. Throughout the whole book, our high-speed and master-strength chess program DARKTHOUGHT serves as a realistic test vehicle to conduct numerous experiments at unprecedented search depths. The extensive experimental evaluations provide convincing empirical evidence for the practical usefulness of the techniques presented by us. These results will certainly be of special interest to researchers 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 the series editors for offering me the opportunity to publish my book under their auspices.

Ernst A. Heinz  -  September 1999



Table of Contents

Author:     Ernst A. Heinz
Title:      ``Scalable Search in Computer Chess''
Publisher:  Vieweg Verlag [268 pages, 31 figures, 57 tables]
ISBN:       3-528-05732-7

Preface ..........................................................   V
Thanks ........................................................... VII
Acknowledgements ................................................ VIII
Contents .........................................................  XI

Summary and Contributions ........................................   1

0  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 ...........................  40

2  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 ...........................  50

3  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 ................................  78

5  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 .........................  98

6  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 ............. 142

8  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 ................................ 155

9  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 ............................................... 178

Perspectives 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 .............................................. 198

B  Tournament History of DarkThought ............................. 199
   B.1  World Championships ...................................... 199
   B.2  AEGON Man vs. Machine Tournaments ........................ 200
   B.3  Public Exhibition Matches ................................ 200

C  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 ....................................... 202

D  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 ................................. 238

Bibliography ..................................................... 243

Index ............................................................ 259



Created by Ernst A. Heinz, Tue Jan 30 14:53:38 EST 2001