Abstract

According to Shannon there are ”at least 10120 ways to play the game of Chess from start to finish. A computer operating at the rate of one variation per micro-second would require over 1090 years to calculate the first move!”[5]. This brings to the fore the importance of applying efficient algorithms, heuristics and data structures in the design of computer chess engines. Much work has been done in the development of computer chess algorithms. This paper takes a journey on the history of a few famous, published algorithms for computer chess. It considers in a concise manner, the strategies conceived and applied in designing different chess engines from 1947-1986 (the eras of foundational computer chess and the start of computer chess championships). These strategies, include chess knowledge, game tree search, tree pruning strategies, the use of evaluation, transposition and refutation tables, as well as specialized hardware designed to optimize strength of play of computers.

References

• Bernstein A., Roberts M. de V., Arbuckle T., and Belsky M. A. Chess Playing Program for the IBM 704. Western Joint Computer Conference, 157-159, 1958.
• Newell A., Shaw J. C., and Simon H. A. Chess-playing Programs and the Problem of complexity. IBM J. Res. Dev., 2(4):320–335, October 1958.
• Arlazarov V.L. Donskoy M.V. Adelson-Velskiy, G.M. Some methods of controlling the tree search in chess programs. In: Levy, D. (eds) Computer Chess Compendium. Springer, New York, NY. https://doi.org/10.1007/978-1-4757- 1968-0 14, 1988.
• Berliner H. J. Hitech Becomes First Computer Senior Master. AI Magazine, 9(3):85, Sep. 1988.
• Shannon C. Programming a Digital Computer for Playing Chess. Philosophical Magazine Ser.7, Vol. 41, No. 314 - March, 1950.
• Condon J. and Thompson K. Belle Chess Hardware. In: Levy, D. (eds) Computer Chess Compendium. Springer, New York, NY. https://doi.org/10.1007/978-1-4757-1968-0 28, 1988.
• Greenblatt R. D., Eastlake D. E., and S. D. Crocker. The Greenblatt Chess Program. Proceedings of the FJCC, 31, 801-810., 1967.
• Ebeling C. All the Right Moves: A VLSI Architecture for Chess. PhD thesis, Carnegie Mellon University, Pittsburgh, PA, May 1986. Ph.D. Thesis. Winner of the 1986 ACM Doctoral Dissertation Award. Later published by MIT Press in the ACM Distinguished Dissertation Series (1987).
• Boos G., Cooper D. W., Gillogly J. J., Levy D. N. L., Raymond H., Slate D. J., Smith R. C., and Mittman B. Computer Chess Programs (panel). Proc. 1971 Annual ACM Conference, 25, 97-102., 1971.
• Boos G., Cooper D. W., Gillogly J. J., Levy D. N. L., Raymond H., Slate D. J., Smith R. C., and Mittman B. Computer Chess Programs (panel). Proc. 1971 Annual ACM Conference, 25, p.100. par. 8, 1971.
• Richard D. Greenblatt and Donald E. Eastlake III. The greenblatt chess program (mac hack vi). SIGART Newsletter, (6):8, October 1967.
• Davidson H.A. A Short History of Chess. David McKay: Dysart, UK, 2012.
• Hsu, F. Two designs of functional units for vlsi based chess machines. Technical Report CMU-CS-86-103, Carnegie Mellon University, Department of Computer Science, Jan 1986.
• Hyatt, R.A., Gower, A.E. and Nelson, H.L. Cray blitz. In: Levy, D. (eds) Computer Chess Compendium. Springer, New York, NY. https://doi.org/10.1007/978-1-4757-1968- 0 10, 1988.
• Gillogly J.J. The Technology Chess Program. Artificial Intelligence, 1972.
• Harkness K. and Battell J. S. This made Chess History. Chess Review. February-November, 1947.
• Kotok, A. A Chess Playing Program for the IBM 7090 Computer, pages 48–55. Springer New York, New York, NY, 1988.
• Levy, D., editor. Computer Chess Compendium. Springer- Verlag, Berlin, Heidelberg, 1988.
• Adel’son-Vel’skii G. M., Arlazarov V. L., Bitman A. R., Zhivotovskii A. A., and Uskov A. V. Programming a Computer to Play Chess. Russian Math. Surveys, 25:2 (1970), 221–262, 1970.
• Botvinnik M. M. Computers, Chess and Longrange planning. New York: Springer Verlag, 1970.
• Taboga M. Beta-binomial distribution, 2021. Accessed: 2025- 10-13.
• B. Mittman. Computer chess programs (panel). PDF archived at The Computer History Museum, 1971.
• Newborn M. Computer Chess. New York: Academic Press, 1975.
• Newborn, M. Mac Hack and Transposition Tables.In: Kasparov versus Deep Blue. Springer, New York, NY, 1997.
• SIGART. Progress report on the kotok–mccarthy vs. itep chess match. SIGART Newsletter, (4):11, June 1967.
• Slate D. J. and Atkin L. R. CHESS 4.5—The Northwestern University chess program, pages 82–118. Springer New York, New York, NY, 1983.
• Van Den Herik, J. Computer Chess, the ChessWorld, and Artificial Intelligence. Ph.D. thesis, Delft University of Technology. Academic Service, The Hague. ISBN 90 62 33 093 2. (in Dutch), 1983.
• Atkin L. W. and Slate D. J. Chess 4.0 at the 1973 ACM north american computer chess championship. In Proceedings of the 4th Annual ACM North American Computer Chess Championship, New York City, NY, 1973. Association for Computing Machinery (ACM).
• Atkin L. W. and Slate D. J. Chess 4.5 at the 2nd world computer chess championship. In Proceedings of the 2nd World Computer Chess Championship, Toronto, Canada, 1976. International Federation for Information Processing (IFIP).
• Atkin L. W., Slate D. J., and K. D. Gorlen. Chess 3.0: Northwestern university chess program. In Proceedings of the 1st Annual ACM North American Computer Chess Championship, pages 1–3, ACM National Conference, Houston, Texas, 1970. Association for Computing Machinery (ACM).
• Atkin L.W., Slate D. J., and Gorlen K. Chess 3.5 and 3.6 at the 1972 ACM north american computer chess championship. In Proceedings of the 3rd Annual ACM North American Computer Chess Championship, Sheraton Boston Hotel, Boston, MA, 1972. Association for Computing Machinery (ACM).
• Baylor G. W. A Computer Model of Checkmating Behaviour in Chess. In A. D. De Groot and W. R. Reitman, editors, Heuristic Processes in Thinking. Nauka, Moscow, 1966.