Dynamic Programming, (DP)
a mathematical, algorithmic optimization method of recursively nesting overlapping sub problems of optimal substructure inside larger decision problems. The term DP was coined by Richard E. Bellman in the 50s not as programming in the sense of producing computer code, but mathematical programming, planning or optimization similar to linear programming, devoted to the study of multistage processes. These processes are composed of sequences of operations in which the outcome of those preceding may be used to guide the course of future ones ^{[1]}.

DP in Computer Chess

In computer chess, dynamic programming is applied in depth-firstsearch with memoization aka using a transposition table and/or other hash tables while traversing a tree of overlapping sub problems aka child positions after making a move by one side in top-down manner, gaining from stored positions of sibling subtrees due to transpositions and/or common aspects of positions, in particular effective inside an iterative deepening framework. Another approach of dynamic programming in computer chess or computer games is the application of retrograde analysis, to solve a problem by solving subproblems in bottom-up manner starting from terminal nodes ^{[2]}.

Richard E. Bellman (1954). On a new Iterative Algorithm for Finding the Solutions of Games and Linear Programming Problems. Technical Report P-473, RAND Corporation, U. S. Air Force Project RAND

## Table of Contents

Home * Programming * Algorithms * Dynamic ProgrammingDynamic Programming, (DP)a mathematical, algorithmic optimization method of recursively nesting overlapping sub problems of optimal substructure inside larger decision problems. The term DP was coined by Richard E. Bellman in the 50s not as programming in the sense of producing computer code, but mathematical programming, planning or optimization similar to linear programming, devoted to the study of multistage processes. These processes are composed of sequences of operations in which the outcome of those preceding may be used to guide the course of future ones

^{[1]}.## DP in Computer Chess

In computer chess, dynamic programming is applied in depth-first search with memoization aka using a transposition table and/or other hash tables while traversing a tree of overlapping sub problems aka child positions after making a move by one side in top-down manner, gaining from stored positions of sibling subtrees due to transpositions and/or common aspects of positions, in particular effective inside an iterative deepening framework. Another approach of dynamic programming in computer chess or computer games is the application of retrograde analysis, to solve a problem by solving subproblems in bottom-up manner starting from terminal nodes^{[2]}.## See also

## Selected Publications

## 1953 ...

1953).An Introduction to the Theory of Dynamic Programming. R-245, RAND Corporation1954).The Theory of Dynamic Programming. P-550, RAND Corporation, pdf1954).On a new Iterative Algorithm for Finding the Solutions of Games and Linear Programming Problems. Technical Report P-473, RAND Corporation, U. S. Air Force Project RAND1955).The Stucture of Dynamic Programming Models. Naval Research Logistics, Vol. 21957).Dynamic Programming. Princeton University Press1958).Dynamic Programming and Stochastic Control Processes. RAND Corporation, Santa Monica, CA, Information and Control 1## 1960 ...

1960).Sequential Machines, Ambiguity, and Dynamic Programming. Journal of the ACM, Vol. 7, No. 11960).Dynamic Programming and Markov Processes. MIT Press, amazon^{[3]}1962).Applied Dynamic Programming. RAND Corporation, Princeton University Press, pdf1962).Dynamic Programming Treatment of the Travelling Salesman Problem. Journal of the ACM, Vol. 9, No. 1, 1961 pdf preprint1962).Discrete Dynamic Programming. Annals of Mathematical Statistics, Vol. 33, No. 21965).On the Application of Dynamic Programming to the Determination of Optimal Play in Chess and Checkers.PNAS1965).Discounted Dynamic Programming. Annals of Mathematical Statistics, Vol. 36, No. 1^{[4]}1967).Positive Dynamic Programming. Proc. 5th Berkeley Symposium on Mathematical Statistics and Probability## 1970 ...

1976).The Stochastic Processes of Borel Gambling and Dynamic Programming. Annals of Statistics, Vol. 4, No. 21977).Art and Theory of Dynamic Programming. Academic Press1979).Universally Measurable Policies in Dynamic Programming. Mathematics of Operations Research, Vol. 4, No. 1## 1990 ...

1996, 2017).Dynamic Programming and Optimal Control. Athena Scientific## 2000 ...

2001).Neuro-Dynamic Programming: An Overview. Encyclopedia of Optimization, pdf, slides as pdf2002).Richard Bellman on the Birth of Dynamic Programming. Operations Research, Vol. 50, No. 1, pdf2003).Dynamic Programming. Dover Publications2006).Algorithms. McGraw-Hill, Chapter 6 Dynamic programming (pdf)2006).Learning for stochastic dynamic programming. pdf, pdf2007).Active learning in regression, with application to stochastic dynamic programming. ICINCO and CAP, 2007, pdf2007).Approximate Dynamic Programming - Solving the Curses of Dimensionality. Wiley## 2010 ...

2010).Dynamic Programming. With a new introduction by Stuart E. Dreyfus, Princeton University Press2010).Approximate dynamic programming. In Olivier Sigaud and Olivier Buffet, editors, Markov Decision Processes in Artificial Intelligence, chapter 3, ISTE Ltd and John Wiley & Sons Inc., pdf2011).Approximate Dynamic Programming - Solving the Curses of Dimensionality. 2nd edition, Wiley2013).Abstract Dynamic Programming. Athena Scientific2015).Applied Dynamic Programming. Princeton University Press## External Links

Algorithms that use dynamic programming

## References

1953).An Introduction to the Theory of Dynamic Programming. R-245, RAND Corporation1965).On the Application of Dynamic Programming to the Determination of Optimal Play in Chess and Checkers.PNAS## What links here?

Up one Level