Search Procedures for Perfect Information Trees Containing Chance Nodes.

Abstract

An extension of the alpha-beta tree pruning strategy to game trees with 'probability' nodes, whose values are defined as the (possibly weighted) average of their successors' values, is developed. These '*-minimax' trees pertain to games involving chance but no concealed information. Casino blackjack, backgammon, some card games, and board games such as Monopoly are games of this type. An initial left-to-right depth-first algorithm is developed and shown to reduce the complexity of an exhaustive search strategy by 10 to 35 percent. An improved algorithm is then formulated for the class of 'regular' -minimax trees. With random ordering of successor nodes, this modified algorithm is shown to reduce search by more than 50 percent. With optimal ordering, it is shown to reduce search complexity by an order of magnitude. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1982
Accession Number
ADA123126

Entities

People

  • Bruce W. Ballard

Organizations

  • Duke University

Tags

Communities of Interest

  • Advanced Electronics
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Artificial Intelligence
  • Case Studies
  • Computer Science
  • Efficiency
  • Information Science
  • Probability
  • Random Number Generators
  • Scientific Research
  • Security
  • Simulations
  • Standards
  • Terminals
  • Test And Evaluation
  • Trees (Data Structures)

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Game Theory.