Forward Estimation for Minimax Search.

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1995
Accession Number
ADA309148

Entities

People

  • Weixiong Zhang

Organizations

  • University of Southern California

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Classification
  • Computational Complexity
  • Computations
  • Demographic Cohorts
  • Information Operations
  • Information Science
  • Instructions
  • Intervals
  • Learning
  • Mathematics
  • Monitoring
  • Optical Scanning
  • Security
  • Specific Volume
  • Test And Evaluation

Fields of Study

  • Computer science

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Game Theory.
  • Neural Network Machine Learning.