M.Sc. Thesis: Parallel Search of Narrow Game Trees

Overview:

Among the achievements of the Chinook checkers playing program include being the first computer program to challenge a man vs. machine world championship title in 1992 (losing to Dr. Marion Tinsley) and the first computer program to win a world man vs. machine championship title in 1995 (against Mr. Don Lafferty).

The thesis describes the parallel alpha-beta game tree search algorithm and implementation used in both ParaChinook-1992 and ParaChinook-1995. Pseudo-code and results using a test suite of positions are presented.

Downloading Options:

1. Abstract only. Compressed Postscript (21 kbytes) and HTML version
2. Complete thesis (single Postscript file). Gzip'ed (230 kbytes)
3. Complete thesis (individual Postscript files for each chapter). Gzip'ed tar file (460 kbytes) and Compressed tar file (589 kbytes)
4. Individual chapters (compressed Postscript files)
   • Title Page (19 kbytes)
   • Abstract (21 kbytes)
   • Acknowledgements (20 kbytes)
   • Table of Contents (21 kbytes)
   • List of Tables (20 kbytes)
   • List of Figures (20 kbytes)
   • List of Formulas (19 kbytes)
   • Chapter 1: Introduction (26 kbytes)
   • Chapter 2: Game Tree Search (52 kbytes)
   • Chapter 3: Parallel Alpha-Beta Game Tree Search (45 kbytes)
   • Chapter 4: Parallel Chinook (50 kbytes)
   • Chapter 5: Improving Parallel Chinook (71 kbytes)
   • Chapter 6: Conclusions (24 kbytes)
   • Bibliography (27 kbytes)
   • Appendix A: Rules of Checkers In Brief (21 kbytes)
   • Appendix B: Tinsley-Chinook 1992 Test Suite (46 kbytes)
   • Appendix C: Experimental Data in Detail (139 kbytes)