Forward Estimation for Game-Tree Search

Abstract

It is known that bounds on the minimax values of nodes in a game tree can be used to reduce the compu-tational complexity of minimax search for two-player games. We describe a very simple method to esti-mate bounds on the minimax values of interior nodes of a game tree, and use the bounds to improve min-imax search. The new algorithm, called forward es-timation, does not require additional domain knowl-edge other than a static node evaluation function, and has small constant overhead per node expansion. We also propose a variation of forward estimation, which provides a tradeoff between computational complexity and decision quality. Our experimental results show that forward estimation outperforms alpha-beta prun-ing on random game trees and the game of Othello. 1.