Christopher C. McConnell
PhD Student, Computer Science
Wean Hall 4207, (412) 268-3728
Fax: (412) 268-5576
- hamming.zip Code for
generating Hamming distance seperated random keys. Includes a good
random number generator.
Minimal Model Complexity Search
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, explanation-based
learning, minimum description length.
B* Probability Based Search
We describe a search algorithm for two-player games that relies on
selectivity rather than brute-force to achieve success. The key ideas
behind the algorithm are:
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
I-have-optimism-that-needs-to-be-investigated 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.
- 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.
The B* probability based search algorithm has been implemented on the chess
machine Hitech. En route we have developed effective techniques for:
This report describes the implementation, and the results of tests including
games played against brute-force 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 brute-force techniques.
Keywords: Probabilistic B*, Computer Chess, Selective Search,
- 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.
*CART: Parallel CART on the CM-2
*CART is a parallel implementation of the CART decsion tree algorithm
in *LISP on the CM-2 from Thinking Machines. It exhibits significant
speed up over a serial version of the same algorithm on a SUN-4. The
implementation is described together with some performance comparisons
with the serial version.
Keywords: CART, Parallel, CM-2
Tuning Evaluation Functions for Search
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
School of Computer
Carnegie Mellon University
5000 Forbes Avenue.
Pennsylvania 15213-3891 USA
2870 Beechwood Blvd
Pennsylvania 15217 USA