Accession Number : ADA309148
Title : Forward Estimation for Minimax Search.
Descriptive Note : Research rept.,
Corporate Author : UNIVERSITY OF SOUTHERN CALIFORNIA MARINA DEL REY INFORMATION SCIENCES INST
Personal Author(s) : Zhang, Weixiong
PDF Url : ADA309148
Report Date : JAN 1995
Pagination or Media Count : 20
Abstract : It is known that bounds on the minimax values of nodes in a game tree can be used to reduce the computational complexity on minimax search for two-player games. We describe a very simple method to estimate bounds on the minimax values of interior nodes of a game tree, and show how it can be used to improve minimax search. The new algorithm, called forward estimation, does not require additional domain knowledge 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 trade-off between computational complexity and decision quality. Our experimental results show that forward estimation outperforms alpha-beta pruning on random trees and the game of Othello.
Descriptors : *GAME THEORY, MATHEMATICAL MODELS, ALGORITHMS, COMPUTATIONS, RANDOM VARIABLES, LEARNING MACHINES, RULE BASED SYSTEMS, ESTIMATES, SEARCHING, HEURISTIC METHODS, PATTERN RECOGNITION, KNOWLEDGE BASED SYSTEMS, SYSTEMS ANALYSIS, ONLINE SYSTEMS, POINT THEOREM.
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE