Correct and optimal strategies in game playing programs
Max Bramer · The Computer Journal · 1980
This paper considers the distinction between winning strategies in game playing programs which are either ‘optimal’ or ‘correct’, i.e. which do or do not invariably select shortest path winning moves. The relative merits of these two types of strategy are considered and methods are proposed for producing correct algorithms by a process of iterative refinement based on an analysis of ‘win-trees’. An example is given of a fully correct strategy for the King and Rook against King chess endgame produced in this way.