Overview

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.

Full Product Details

Author:   Chun-Hung Tzeng
Publisher:   Springer-Verlag Berlin and Heidelberg GmbH & Co. KG
Imprint:   Springer-Verlag Berlin and Heidelberg GmbH & Co. K
Edition:   Softcover reprint of the original 1st ed. 1988
Dimensions:   Width: 17.00cm , Height: 0.60cm , Length: 24.40cm
Weight:   0.222kg
ISBN:  

9783642648120

ISBN 10:   3642648126
Pages:   107
Publication Date:   08 October 2011
Audience:   Professional and scholarly ,  Professional & Vocational
Format:   Paperback
Publisher's Status:   Active
Availability:   Manufactured on demand  
We will order this item for you from a manufactured on demand supplier.

Table of Contents

1 Introduction.- 2 Games and Minimax Values.- 2.1 Finite Perfect Information Games and Game Trees.- 2.2 Zero-Sum Two-Person Perfect Information Games.- 2.3 Subgames and Game Graphs.- 2.4 Example 1: G1-Games.- 2.5 Example 2: P2-Games.- 2.6 Minimax Values, the Minimax Procedure and the Alpha-Beta.- Procedure.- 3 Heuristic Game-Tree Searches.- 3.1 The Conventional Heuristic Game-Tree Search.- 3.1.1 Static Evaluation Functions.- 3.1.2 The Back-Up Process.- 3.2 Heuristic Arguments and the Pathological Phenomenon.- 3.3 New Back-Up Processes.- 3.3.1 The Product-Propagation Procedure.- 3.3.2 The M & N Procedure.- 3.3.3 The *-MIN Procedure.- 3.3.4 Average Propagation.- 4 Probability Spaces and Martingales.- 4.1 Borel Fields and Partitions.- 4.2 Probability Spaces.- 4.3 Random Variables.- 4.4 Product Spaces.- 4.5 Conditional Probabilities and Martingales.- 5 Probabilistic Game Models and Games Values.- 5.1 Probabilistic Game Models.- 5.2 Strategies and Game Values.- 5.2.1 Non-randomized Strategies.- 5.2.2 Randomized Strategies.- 5.2.3 Minimax Values.- 5.3 Pb-Game Models.- 5.4 Gd-Game Models.- 6 Heuristic Information.- 6.1 Examples: P2- and G1-Game Models.- 6.1.1 P2-Game Models.- 6.1.2 G1-GameModels.- 6.2 Formulation of Heuristic Information.- 6.3 Heuristic Search.- 6.4 Improved Visibility of a Heuristic Search.- 7 Estimation and Decision Making.- 7.1 Random Variable Estimators.- 7.2 Comparison of Estimators.- 7.3 Decision Making.- 7.3.1 Decision Models.- 7.3.2 Decision Qualities.- 8 Independence and Product-Propagation Rules.- 8.1 Product Models.- 8.2 Product Heuristic Information and Product Heuristic Searches.- 8.3 Product-Propagation Rules.- 9 Estimation of Minimax Values in Pb-Game Models.- 9.1 More About Probabilities on Pb-Game Trees.- 9.2 The Conditional Probability of a Forced Win, p(h,l).- 9.3 An Approximation of p(h,l).- 10 Estimation of Minimax Values in Gd-Game Models.- 10.1 Estimation in G1-Game Models.- 10.2 Estimation in Gd-Game Models.- 11 Conclusions.- References.

Reviews

Author Information

Tab Content 6

Author Website:  

Customer Reviews

Recent Reviews

No review item found!

Add your own review!

Countries Available

All regions