Christopher C. McConnell
PhD Student, Computer Science
Email:
ccm+@cs.cmu.edu
Office:
Wean Hall 4207, (412) 2683728
Fax: (412) 2685576
Mailing Addresses:
 hamming.zip Code for
generating Hamming distance seperated random keys. Includes a good
random number generator.
Minimal Model Complexity Search
Abstract
SURFER is an empirical discovery system that given a set of input data
and a modelling vocabulary returns the model that best describes that
data. The best model is considered to be the one that minimizes the
description length of that model plus the data encoded using that
model. The search for models is controlled by the a priori
estimate of model likelihoods as encoded in the modelling vocabulary.
SURFER includes domain independent mechanisms for identifying
redundant models and for finding free parameters. The system is
described together with the results of running the system on several
different types of problems.
Keywords: Bayesian Learning, discovery, explanationbased
learning, minimum description length.
Postscript
B* Probability Based Search
Abstract
We describe a search algorithm for twoplayer games that relies on
selectivity rather than bruteforce to achieve success. The key ideas
behind the algorithm are:
 Stopping when one alternative is clearly better than all the others, and
Focusing the search on the place where the most progress can likely be
made toward stopping.
Critical to this process is identifying uncertainty about the ultimate value
of any move. The lower bound on uncertainty is the best estimate of the
real value of a move. The upper bound is its optimistic value, based on
some measure of unexplored potential. This provides an
Ihaveoptimismthatneedstobeinvestigated attitude that is an
excellent guiding force. Uncertainty is represented by probability
distributions. The search develops those parts of the tree where moving
existing bounds would be most likely to succeed and would make the most
progress toward terminating the search. Termination is achieved when the
established real value of the best move is so good that the likelihood of
this being achieved by any other alternative is minimal.
The B* probability based search algorithm has been implemented on the chess
machine Hitech. En route we have developed effective techniques for:
 Producing viable optimistic estimates to guide the search,
 Producing cheap probability distribution estimates to measure goodness,
 Dealing with independence of alternative moves, and
 Dealing with the Graph History Interaction problem.
This report describes the implementation, and the results of tests including
games played against bruteforce programs. Test data indicate that B*
Hitech is better than any searcher that expands its whole tree based on
selectivity. Further, analysis of the data indicates that should additional
power become available, the B* technique will scale up considerably better
than bruteforce techniques.
Keywords: Probabilistic B*, Computer Chess, Selective Search,
TwoPerson Games
Postscript
*CART: Parallel CART on the CM2
Abstract
*CART is a parallel implementation of the CART decsion tree algorithm
in *LISP on the CM2 from Thinking Machines. It exhibits significant
speed up over a serial version of the same algorithm on a SUN4. The
implementation is described together with some performance comparisons
with the serial version.
Keywords: CART, Parallel, CM2
Postscript
Tuning Evaluation Functions for Search
Abstract
This paper examines the problem of applying machine learning
techniques to improving the performance of actual game playing
programs in complex domains like chess. This is a challenging problem
because chess is a domain where a great deal of human effort has been
spent and the performance level of programs is already very high.
Keywords: Games, Strategy, Optimization
Postscript
 School:

Box E1
School of Computer
Science
Carnegie Mellon University
5000 Forbes Avenue.
Pittsburgh,
Pennsylvania 152133891 USA
 Home:

2870 Beechwood Blvd
Pittsburgh,
Pennsylvania 15217 USA
(412) 5215032
ccm+@cs.cmu.edu