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
      Cybernetics

Distribution Statement : APPROVED FOR PUBLIC RELEASE