Learning Plans for Competitive Domains

Abstract

Many machine learning systems learn from their problem solving experience in single-agent domains. This paper discusses an algorithm to learn complex, relevant, cost effective plans for a broad class of competitive, multi-agent domains. Such a plan, called a fork, is extracted from the explanation of a single failure, and represents a set of mutually overlapping simple plans to achieve a goal. Each plan is non-linear, provides alternatives for contingencies, is applicable both offensively and defensively, and has a clear upper bound for its execution time. This paper describes the representation and implementation of forks in HOYLE, a system to learn to play any two-person, perfect information game well. Together with a weak theory for its general domain, HOYLE has used forks to learn to play a broad variety of games perfectly without extensive forward search in the game tree. In more challenging games, however, the selection of a relevant plan and its binding to the current game state is unacceptably costly. This paper details the significantly improved performance directly attributable to learning about appropriate forks, and the heuristics that guard against unacceptable degradation of performance as new knowledge is acquired.