A Bayesian approach to relevance in game playing

摘要

The point of game tree search is to insulate oneself from errors in the evaluation function. The standard approach is to grow a full width tree as deep as time allows, and then value the tree as if the leaf evaluations were exact. The alpha-beta algorithm implements this with great computational efficiency. This approach has been effective in many games. Our approach is to form a Bayesian model of our uncertainty. We adopt an evaluation function that returns a probability distribution estimating the probability of various errors in valuing each position. These estimates are obtained by training from data. We thus use additional information at each leaf not available to the standard approach. We utilize this information in three ways: to evaluate which move is best after we are done expanding, to allocate additional thinking time to moves where additional time is most relevant to game outcome, and, perhaps most importantly, to expand the tree along the most relevant lines. Our measure of the relevance of expanding a given leaf provably approximates a measure of the impact of expanding the leaf on expected payoff, including the impact of the outcome of the leaf expansion on later expansion decisions. Our algorithms run (under reasonable assumptions) in time linear in the size of the final tree and hence except for a small constant factor, are as time efficient as alpha-beta. Our algorithm focuses on relevant lines, on which it can in principle grow a tree several times as deep as alpha-beta in a given amount of time.