four sample gamesMorph's play, with some analysis of its strengths and weaknesses.
Morph is a learning chess program. MorphII is a programming environment to support experimentation in domains including machine learning of games. Both are results of an ambitious project headed by Robert Levinson at UC Santa Cruz.
| Jay : game learning : Morph |
Some of the goals are:
Some of the principles are:
Morph is a learning chess program, comparable to SAL. (Morph is more sophisticated, but SAL can learn other games as well as chess.)
Morph represents chess knowledge as weighted patterns, which the papers refer to as “pws” for “pattern-weight pairs”. The patterns are graphs of attack and defense relationships between pieces on the board and vectors of relative material difference between the players.
To play, Morph uses one-ply search. For each position, it computes which patterns match the position and uses a global formula to combine the weights of the matching patterns into an evaluation. Morph plays the move with the best evaluation.
Morph uses a wide variety of learning methods to learn the patterns and their weights. Different methods add patterns, delete patterns, and set the weights. The methods include temporal differences, simulated annealing, a genetic algorithm-like method, generalization and specialization of patterns, and explanation-based generalization.
four sample games
Morph's play, with some analysis of
its strengths and weaknesses.
Morph is an Adaptive-Predictive Search program. Morph only plays chess, but APS systems similar to Morph can tackle any discrete state-space search problem.
MorphII can be seen as an improved, domain-independent outgrowth of Morph. It represents game rules and patterns as PEIRCE conceptual graphs, using a clever scheme that permits efficient incremental update. It combines pattern scores hierarchically for evaluation, rather than globally as Morph does, for a big leap in expressiveness.
MorphII is far more sophisticated than Morph, both in its implementation and in its intellectual background. It fixes Morph’s biggest (or at least, most obvious) weaknesses.
MorphII is not finished yet. Bob Levinson e-mailed me that when tried on simple games like tic-tac-toe and nim, it learns to play nearly perfectly without search.
This is another chess program. It was under development when I last heard, but may have been abandoned by now. There has been no news for a long time.
Morph is one of the best from-scratch game learning systems, perhaps the best. It learns faster than SAL and may play more strongly despite doing less search. Even so, its performance is disappointing—it plays like a beginner; it should be possible to do much better, even with one-ply search. APS systems have not proved themselves, at least not in print. MorphII has ambitious goals, but the results aren’t in; some of the subgoals on the way to completing the MorphII plan are tough research problems in their own right.
Nevertheless, I think this project is worth keeping an eye on. The later papers below are progressively more sophisticated than the early ones, which is promising. Some technical advances are definite, such as the efficient general-purpose incrementally-updatable knowledge representations of MorphII. Also, I’ve been impressed by Bob Levinson’s pragmatism (in private communication); he seems willing to do whatever works.
The Morph project’s goals are the central goals of artificial intelligence: efficient autonomous domain-independent machine learning for high performance. Few other researchers attack the problems of the field so directly (Doug Lenat’s CYC project comes to mind). I admire that.
Projects that aim this high don’t often achieve their aims. But I believe that somebody should try the direct approaches, no matter how difficult. They may succeed! And if not, we can learn from analysing the reasons behind a failure or a partial success.
Adaptive-predictive game-playing programs (1992 version, paywalled)
Robert Levinson, Brian Beach, Tal Dayan, Richard Snyder, and Kirack Sohn
Method integration for experience-based learning
(1991, Citeseer)
Jeffrey Gould and Robert Levinson
A description of Morph, focusing on how Morph combines a wide variety
of learning methods.
Experience-based creativity (1991, Google Books)
Robert Levinson
A general discussion of automated creativity, sample
“creative” chess play by Morph (but no complete games),
and a description of Morph and its performance.
“MORPH: A programmer’s guide” (1991, 20 pages)
W. Paul Zola
This manual is not online.
Experience-based adaptive search (1992, Citeseer)
Jeffrey Gould and Robert Levinson
Casts Morph as an implementation of an
“adaptive predictive search” (APS) architecture, which learns
solely by experience.
Towards domain-independent machine intelligence (1993, Citeseer)
Robert Levinson
The first work on transforming Morph into a domain-independent
system using
PEIRCE conceptual graphs.
MORPH II: A universal agent: Progress report and proposal
(1994, Citeseer)
Robert Levinson
The plan and goals for MorphII. As the title suggests, this paper
reads like a grant proposal. It contains the first description
of the “game of abstract mathematical relations”
(a generic knowledge representation, using the conceptual graphs).
Exploiting the physics of state-space search (1994, Citeseer)
Robert Levinson
The following paper, “General game-playing”,
is an updated, expanded version of this one.
General game-playing and reinforcement learning (1995, Citeseer)
Robert Levinson
Tenets of machine intelligence,
a more detailed description of the generic knowledge representation,
the architecture of a learning system smarter than Morph,
and a description of MorphII with some early performance results.
There’s an enlightening discussion of how the system’s
generality makes its learning problem more difficult.
New advances in adaptive pattern-oriented chess (1996)
Jonathan Allen, Edward Hamilton, and Robert Levinson
Formerly a web page, now a dead link.
This unfinished paper describes Morph III, a learning
chess program in progress.