Ebook: A Theory of Heuristic Information in Game-Tree Search
Author: Chun-Hung Tzeng (auth.)
- Tags: Artificial Intelligence (incl. Robotics), Probability Theory and Stochastic Processes, Statistics general, Operations Research/Decision Theory
- Series: Symbolic Computation
- Year: 1988
- Publisher: Springer-Verlag Berlin Heidelberg
- Edition: 1
- Language: English
- pdf
Searching is an important process in most AI systems, especially in those AI production systems consisting of a global database, a set of production rules, and a control system. Because of the intractability of uninformed search procedures, the use of heuristic information is necessary in most searching processes of AI systems. This important concept of heuristic informatioD is the central topic of this book. We first use the 8-puzzle and the game tic-tac-toe (noughts and crosses) as examples to help our discussion. The 8-puzzle consists of eight numbered movable tiles set in a 3 x 3 frame. One cell of the frame is empty so that it is possible to move an adjacent numbered tile into the empty cell. Given two tile configurations, initial and goal, an 8-puzzle problem consists of changing the initial configuration into the goal configuration, as illustrated in Fig. 1.1. A solution to this problem is a sequence of moves leading from the initial configuration to the goal configuration, and an optimal solution is a solution having the smallest number of moves. Not all problems have solutions; for example, in Fig. 1.1, Problem 1 has many solutions while Problem 2 has no solution at all.
Content:
Front Matter....Pages I-X
Introduction....Pages 1-6
Games and Minimax Values....Pages 7-17
Heuristic Game-Tree Searches....Pages 18-27
Probability Spaces and Martingales....Pages 28-39
Probabilistic Game Models and Game Values....Pages 40-50
Heuristic Information....Pages 51-63
Estimation and Decision Making....Pages 64-72
Independence and Product-Propagation Rules....Pages 73-80
Estimation of Minimax Values in P b -Game Models....Pages 81-86
Estimation of Minimax Values in G d -Game Models....Pages 87-97
Conclusions....Pages 98-99
Back Matter....Pages 100-107
Content:
Front Matter....Pages I-X
Introduction....Pages 1-6
Games and Minimax Values....Pages 7-17
Heuristic Game-Tree Searches....Pages 18-27
Probability Spaces and Martingales....Pages 28-39
Probabilistic Game Models and Game Values....Pages 40-50
Heuristic Information....Pages 51-63
Estimation and Decision Making....Pages 64-72
Independence and Product-Propagation Rules....Pages 73-80
Estimation of Minimax Values in P b -Game Models....Pages 81-86
Estimation of Minimax Values in G d -Game Models....Pages 87-97
Conclusions....Pages 98-99
Back Matter....Pages 100-107
....