Subject: My Thesis available at last!

From: [email-masked] (Barney Pell)
Date: Wed, 5 Jan 94 16:43:46 PST

My PhD thesis is now available.  
The thesis can be obtained in a number of ways:

1. Request the official tech report from the University of Cambridge Computer
Laboratory, by emailing:  [email-masked]

2. Retrieve a postscript version by ftp, from:
	ftp.cl.cam.ac.uk:users/bdp/thesis.ps.Z

3. A version has been printed at NASA Ames, and limited numbers of
these are available from the author ([email-masked]).
Non-US readers are recommended to try receiving the Cambridge version
first. 

Cheers,
  Barney

==============================================================================
Strategy Generation and Evaluation
for Meta-Game Playing

Barney Darryl Pell
PhD Thesis, University Of Cambridge
August, 1993

Abstract:

Meta-Game Playing (METAGAME) is a new paradigm for research in
game-playing in which we design programs to take in the rules of
unknown games and play those games without human assistance. Strong
performance in this new paradigm is evidence that the program, instead
of its human designer, has performed the analysis of each specific
game.

SCL-METAGAME is a concrete METAGAME research problem based around the
class of symmetric chess-like games.  The class includes the games of
chess, checkers, noughts and crosses, Chinese-chess, and Shogi.  An
implemented game generator produces new games in this class, some of
which are objects of interest in their own right.

METAGAMER is a program that plays SCL-METAGAME. The program takes as input
the {\em rules} of a specific game and analyses those rules to
construct for that game an efficient representation and an evaluation
function, both for use with a generic search engine.  The strategic
analysis performed by the program relates a set of general knowledge
sources to the details of the particular game.  Among other
properties, this analysis determines the relative value of the
different pieces in a given game.  Although METAGAMER does not learn
from experience, the values resulting from its analysis are
qualitatively similar to values used by experts on known games, and
are sufficient to produce competitive performance the first time the
program actually plays each game it is given.  This appears to be the
first program to have derived useful piece values directly from
analysis of the rules of different games.

Experiments show that the knowledge implemented in METAGAMER is
useful on games unknown to its programmer in advance of the
competition and make it seem likely that future programs which
incorporate learning and more sophisticated active-analysis techniques
will have a demonstrable competitive advantage on this new problem.
When playing the known games of chess and checkers against humans and
specialised programs, METAGAMER has derived from more general
principles some strategies which are familiar to players of those
games and which are hard-wired in many game-specific programs.