Christopher C. McConnell

PhD Student, Computer Science

Email: ccm+@cs.cmu.edu
Office: Wean Hall 4207, (412) 268-3728
Fax: (412) 268-5576
Mailing Addresses:

Papers:

Talks:

Software:

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, explanation-based learning, minimum description length.

Postscript

B* Probability Based Search

 Abstract 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:
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 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.

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 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, Two-Person Games

Postscript

*CART: Parallel CART on the CM-2

 Abstract *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

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

Mailing Addresses

School:
Box E-1
School of Computer Science
Carnegie Mellon University
5000 Forbes Avenue.
Pittsburgh, Pennsylvania 15213-3891 USA
Home:
2870 Beechwood Blvd
Pittsburgh, Pennsylvania 15217 USA
(412) 521-5032
ccm+@cs.cmu.edu