An analysis of expected-outcome

Abstract

Static evaluators have been used in every game program ever written. These heuristic functions attempt to differentiate between strong and weak moves by assigning them values based on directly detectable game features. Despite their ubiquity, evaluation functions are not well understood; the development of a theory of evaluator design has been too long coming. In fact, the general consensus is that no theory is possible, because expertise is required to develop even a simple evaluator.

One recently introduced ‘generic’ evaluation function, the expected-outcome model, proposed evaluating a node as the expected value of a game's outcome, given random play from that node on. Experimental studies conducted on evaluators designed under this model yielded encouraging results in tac-tac-toe, Othello, and chess. This paper analyzes the expected-outcome model on a simple class of game trees, and shows that the moves recommended under the assumptions of random play and perfect play are identical. This vindicates what appeared to have been an overly naive assumption, and furthers the claim that statistically interpreted evaluation functions are powerful, as well as elegant.