04/01/1990 09:00 AM
Computer Science
Adaptive-predictive search (APS) is a new method by which systems can improve their search performance through experience. It is believed that the development of such methods is critical as currently a tremendous amount of computational results are potentially wasted by not integrating search and partial search results into the knowledge of a problem-solving system. In the adaptive-predictive search model pattern formation and associative recall are used to improve or replace search. In this paper the theory, background and motivations behind the model are presented and its application to two- player game-playing programs is discussed. In these programs, the system develops a knowledge base of patterns (boolean features) coupled with weights and using pattern-oriented evaluation performs only 1-ply search, yet competes respectably with programs that search more. The learning mechanism is a hybridization of machine learning and artificial intelligence techniques that have been successful in other settings. Specific examples and performance results are taken from the domains of Hexapawn, Tic-Tac-Toe, Pente, Othello, and Chess. [This report is much like 89-22, but focuses on 2-player games and gives new results.]
