PhD Thesis Available: Meta-Game Playing
Barney Pell
--
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: tech-r...@cl.cam.ac.uk
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 (pe...@ptolemy.arc.nasa.gov).
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.
==================================================
Barney Pell
Computer Laboratory
University of Cambridge
phone: (0223) 334602
e-mail: b...@cl.cam.ac.uk
==================================================
rhk8563
>==============================================================================
>Strategy Generation and Evaluation
>for Meta-Game Playing
>Barney Darryl Pell
>Abstract:
>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.
It would be interesting to see how this program would function with
some chess variants taken at random from World Game Review #10 (which con-
tains 600+ variants).
How does the program determine the value of a piece when the values
of certain pieces can change radically in the course of a game? I humbly
suggest that the value of a piece can be a rather nebulous concept at times.
In Unambiguous Chess, the rules state that a piece can only be moved
if its move can be written unambiguously with three alphanumeric characters.
Therefore, you can't move, say, N-B3 if there is more than one way of doing
this. This rule has the peculiar result of making a piece worth almost as
much (maybe more, sometimes) as two pieces of that kind would be worth.
Piece values cannot necessarily be added. When computing the value
of a pair of bishops, it definitely makes a difference whether or not they
are on opposite color squares.
Robin
Barney Pell
|>
|> It would be interesting to see how this program would function with
|> some chess variants taken at random from World Game Review #10 (which con-
|> tains 600+ variants).
That would be fun. However, while the class of games is fairly general,
it is not possible to represent (easily) the idiosyncracies of many games
within the current grammar for symmetric chess-like games used by Metagamer.
Anyone who is interested is encouraged to get the code for the program,
which is available from ftp.cl.cam.ac.uk:users/bdp/metagame3a.tar.Z
(warning: the code is in PROLOG).
|> How does the program determine the value of a piece when the values
|> of certain pieces can change radically in the course of a game? I humbly
|> suggest that the value of a piece can be a rather nebulous concept at times.
|> In Unambiguous Chess, the rules state that a piece can only be moved
|> if its move can be written unambiguously with three alphanumeric characters.
|> Therefore, you can't move, say, N-B3 if there is more than one way of doing
|> this. This rule has the peculiar result of making a piece worth almost as
|> much (maybe more, sometimes) as two pieces of that kind would be worth.
|> Piece values cannot necessarily be added. When computing the value
|> of a pair of bishops, it definitely makes a difference whether or not they
|> are on opposite color squares.
Yes, there are many ways to improve upon the use of a static set of
linear piece values. The static piece values developed by Metagamer
for a given game are just one component of its evaluation function,
as discussed in my thesis.
Extending consideration beyond just a single game (like chess or checkers) makes
the necessity for this even clearer. It also provides a way to demonstrate the
improvement in strength across a class of games by adding, for example,
dynamic considerations to an otherwise static program. Such experiments
are also discussed in the thesis.
|>
|> Robin
Thanks for your interest,
Barney
========================================
Barney Pell
NASA Ames Research Center
e-mail: pe...@ptolemy.arc.nasa.gov
========================================
Sam E. Trenholme
I can print the post-script files, but the spacing is pretty ugly on the
printer (an old apple) I am using. thanx
Sam Trenholme
s...@soda.berkeley.edu
this may help, btw:
Grammer Probabilities Constraints
| | |
| V |
\-------> Generator <---------/
|
|
V
Problem Definition
ASCII can handle quite a bit, if you are creative.