Prior knowledge strengthens learning to control search in weak theory domains
Susan L. Epstein · International Journal of Intelligent Systems · 1992
Rather than search exhaustively in large problem spaces, people use heuristics that entail minimal search and yet support intelligent decisions. Human performance in such spaces is robust and improves with experience. Game playing is a good example. the traditional AI approach to game playing, however, has been to build a program that plays only a single game, and plays it very well. Because exhaustive search of the game graph and minimax of the resultant values guarantees perfect play, programmed champions rely on deep, fast, efficient search. Despite their more limited, fallible memories and arguably slower processors, human masters often defeat a program whose search is incomplete. People search less, remember less, and somehow make the right choices. This article describes HOYLE, a program that learns to play specific games under the direction of a weak theory, clearly delineated prior knowledge about games in general. HOYLE differs from most game-playing programs in two ways: it is able to play any of a broad class of games according to the rules, and it improves its performance through a variety of learning paradigms. HOYLE shows that, for a class of related problems, it is possible to replace deep search with a weak theory based upon heuristically selective cache memories and a consensus about action among reliable rationales.