Donald Knuth

From Chessprogramming wiki
Jump to: navigation, search

Home * People * Donald Knuth

Donald Knuth [1]

Donald Ervin Knuth,
a renowned computer scientist, mathematician, writer, scholar, and Professor Emeritus at Stanford University, California, United States [2]. He is the author of the multi-volume work The Art of Computer Programming, and been called the "father" of the analysis of algorithms - in 1975 he analyzed Alpha-Beta along with Ronald W. Moore, first formulating its Node Types [3]. Beside his fundamental contributions to several branches of computer science and mathematics, Knuth is the creator of the TeX computer typesetting system.



Quote by John McCarthy from Human-Level AI is harder than it seemed in 1955:

Chess programs catch some of the human chess playing abilities but rely on the limited effective branching of the chess move tree. The ideas that work for chess are inadequate for go. Alpha-beta pruning characterizes human play, but it wasn't noticed by early chess programmers - Turing, Shannon, Pasta and Ulam, and Bernstein. We humans are not very good at identifying the heuristics we ourselves use. Approximations to alpha-beta used by Samuel, Newell and Simon, McCarthy. Proved equivalent to minimax by Hart and Levin, independently by Brudno. Knuth gives details.


Selected quotes by Donald Knuth [4]

  • A mathematical formula should never be "owned" by anybody! Mathematics belong to God. [5]
  • Beware of bugs in the above code; I have only proved it correct, not tried it. [6]
  • We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. [7]


Alpha-Beta F2 and Iterative Solution [8]

See also

Selected Publications


1960 ...

Volume 1 - Fundamental Algorithms (1968)
Volume 2 - Seminumerical Algorithms (1969)
Volume 3 - Sorting and Searching (1973)
Volume 4A - Combinatorial Algorithms, Part 1 (2011)
New material for Volume 4 will first appear in beta-test form as fascicles
Volume 4 Fascicle 0, Introduction to Combinatorial Algorithms and Boolean Functions (2008)
Volume 4 Fascicle 1, Bitwise Tricks & Techniques; Binary Decision Diagrams (2009)
Volume 4 Fascicle 2, Generating All Tuples and Permutations (2005)
Volume 4 Fascicle 3, Generating All Combinations and Partitions (2005)
Volume 4 Fascicle 4, Generating All Trees; History of Combinatorial Generation (2006)
Volume 5 - Syntactic Algorithms, planned (estimated in 2020).

1970 ...

1980 ...

1990 ...

2000 ...

2010 ...

External Links

Donald Knuth

Ershov Archive

Dancing D. Knuth
Khiva, summer hall; dancers, D.Knuth
Andrey Ershov, Donald E. Knuth
Khiva, summer hall; A. van Wijngaarden, Zemaneks, D.Knuth. F.Strassen, B.Trakhtenbrot



MMIX from Wikipedia
Metafont from Wikipedia



  1. Donald Knuth at a reception for the Open Content Alliance, hosted by the Internet Archive. Taken October 25, 2005 by Jacob Appelbaum in San Francisco, Donald Knuth from Wikipedia
  2. Computer Musings by Professor Donald E. Knuth | Stanford University Online
  3. Donald Knuth, Ronald W. Moore (1975). An analysis of alpha-beta pruning. Artificial Intelligence, Vol. 6, No. 4, pp 293–326. Reprinted in Donald Knuth (2000). Selected Papers on Analysis of Algorithms. CSLI lecture notes series 102, ISBN 1-57586-212-3
  4. Donald Knuth - Wikiquote
  5. Donald Knuth (1999). Digital Typography. CSLI lecture notes series 78
  6. Knuth: Frequently Asked Questions - What's the exact citation of your oft-cited comment about bugs?
  7. Donald Knuth (1974). Structured Programming with go to Statements. ACM Computing Surveys, Vol. 6, No. 4, pdf
  8. Donald Knuth, Ronald W. Moore (1975). An Analysis of Alpha-Beta Pruning. Artificial Intelligence, Vol. 6, No. 4, pp 293–326. Reprinted in Donald Knuth (2000). Selected Papers on Analysis of Algorithms. CSLI lecture notes series 102, ISBN 1-57586-212-3, pdf
  9. Preprints of Recent Papers including dancing links
  10. dblp: Donald E. Knuth
  11. Backus–Naur Form from Wikipedia
  12. The Art of Computer Programming from Wikipedia
  13. Re: Perft(15) estimate after averaging 800 MC samples by Daniel Shawul, CCC, November 21, 2013 » Perft
  14. Surreal number from Wikipedia
  15. John H. Conway (1976). On Numbers and Games. Academic Press
  16. Knuth–Morris–Pratt algorithm from Wikipedia
  17. TeX from Wikipedia
  18. Literate programming from Wikipedia

Up one level