05/01/1995 09:00 AM
Computer Science
This paper gives a blueprint for the development of a fully domain-independent single-agent and multi-agent heuristic search system. It gives a graph-theoretic representation of search problems based on conceptual graphs, and outlines two different learning systems. One, an ``informed learner,\" makes use of the the graph-theoretic definition of a search problem or game in playing and adapting to a game in the given environment. The other, a ``blind learner,\" is not given access to the rules of a domain, but must discover and then exploit the underlying mathematical structure of a given domain. Relevant work of others is referenced within the context of the blueprint. To illustrate further how one might go about creating general game-playing agents, we show how we can generalize the understanding obtained with the Morph chess system to all games involving the interactions of abstract mathematical relations. An example of a monitor for such domains is presented, along with an implementation of a blind and informed learning system known as MorphII. Performance results with MorphII are preliminary but encouraging and provide a few more data points with which to understand and evaluate the blueprint.