Learning Through Pattern Recognition Applied to a Class of Games

摘要

The objective of this research was to investigate a technique for machine learning useful in solving problems involving forcing states. In games or control problems, a forcing state is a state from which the final goal can always be reached, regardless of what disturbances may arise. A program which learns forcing states in a class of games (in a game-indepndent format) by working backwards from a previous loss has been written. The class of positions which ultimately results in the opponent's win is learned by the program (using a specially designed description language) and stored in its memory together with the correct move to be made when this pattern reoccurs. During future plays of the game, these patterns are searched for. If they are formed by the opponent, the learning program blocks them before the opponent's win sequence can begin. If they are formed by the learning program, it initiates the win sequence. The class of games in which the program is effective includes Qubic, Go-Moku, Hex, and the Shannon Network Games including Bridg-it. The description language enables the learning program to generalize from one example of a forcing state to all other configurations which are strategically equivalent. (Author)