On the Application of Dynamic Programming to the Determination of Optimal Play in Chess and Checkers

摘要

A great deal of effort has been expended in connection with the use of digital computers to play chess and checkers. The most successful has been the checker-playing program of Samuel. It is of some interest then to indicate how the theory of dynamic programming can be used to determine optimal play in the great majority of Pawn-King end-games in Chess, with computers currently available, and in all probability, to determine optimal play for the entire game of checkers. The basic methods are outlined involving as they do the concept of semigroups in structure.