A Model of Two-Player Evaluation Functions

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 6

Automated Reasoning

We present a model of heuristic evaluation functions for two-player games. The basis of the proposal is that an estimate of the expected-outcome of a game situation, assuming random play from that point on, is an effective heuristic function. The model is supported by three distinct sets of experiments. The first set, run on small, exhaustively searched game-trees, shows that the quality of decisions made on the basis of exact values for the expected-outcome is quite good. The second set shows that in large games, estimates of the expected-outcome derived by randomly sampling terminal positions produce reasonable play. Finally, the third set shows that the model can be used to automatically learn efficient and effective evaluation functions in a game-independent manner.