Hint

Swipe to navigate through the chapters of this book

2017 | OriginalPaper | Chapter

6. Search, Games and Problem Solving

Author: Wolfgang Ertel

Publisher: Springer International Publishing

Published in: Introduction to Artificial Intelligence

» Get access to the full version

Abstract

Many AI problems, like automated theorem proving, game playing, planning or routing, involve combinatorial search in large discrete spaces. We introduce the classical uninformed and heuristic search algorithms such as for example A^★ and apply them to simple examples. Game search techniques like minimax and alpha-beta pruning and their application in chess computers are discussed.

Please log in to get access to this content

To get access to this content you need the following product:

Computer Science Explorer

Purchase now

The average branching factor of a tree is the branching factor that a tree with a constant branching factor, equal depth, and an equal amount of leaf nodes would have.

For an 8-puzzle the average branching factor depends on the starting state (see Exercise 6.2 on page 122).

When sorting in a new node from the node list, it may be advantageous to check whether the node is already available and, if so, to delete the duplicate.

Both graphs in Fig. 6.18 were generated by A. Batzill using the system described in [Bat16].

Title

Search, Games and Problem Solving

Book

Introduction to Artificial Intelligence

Print ISBN: 978-3-319-58486-7

Electronic ISBN: 978-3-319-58487-4

https://doi.org/10.1007/978-3-319-58487-4

DOI

https://doi.org/10.1007/978-3-319-58487-4_6

Author:

Wolfgang Ertel

Publisher

Springer International Publishing

Sequence number

Chapter number

Chapter 6