Alexander Reinefeld
Informatik-Fachberichte 200, Springer-Verlag Berlin 1989, ISBN 3-540-50742-6

Zusammenfassung

Baumsuchverfahren werden in der Informatik, insbesondere im Teilbereich der Künstlichen Intelligenz, zum Durchsuchen von Entscheidungsbäumen eingesetzt. Das vorliegende Buch befasst sich mit Baumsuchverfahren für eine spezielle Art von Entscheidungsbäumen, den Spielbäumen. Es werden zwei grundlegende Klassen von Spielbaum-Suchverfahren ausführlich behandelt, die Nullfenster-Suchverfahren, die den Baum in einer vorher festgelegten Reihenfolge durchsuchen, und die Zustandsraum-Suchverfahren, deren Suchabfolge dynamisch gesteuert ist.

Der praktisch orientierte Spielprogrammierer findet in diesem Buch einen universell verwendbaren Grundstock von Baum-Suchalgorithmen für Zwei-Personen-Null-Summen-Spiele. Neben den Baum-Suchalgorithmen selbst werden ihm theoretische und empirische Bewertungskriterien an die Hand gegeben, mit denen er die zu erwartende Suchleistung eines Algorithmus abschätzen kann. Der an den theoretischen Grundlagen der Spielbaumsuche interessierte Leser findet in diesem Buch Ansätze zur Analyse der Suchabfolge und zur Berechnung der Sucheffizienz der Algorithmen. Den Ausgangspunkt bilden die zu durchsuchenden Bäume, deren Knoten-Beziehungen auf einfache Weise in mathematischen Gleichungssystemen beschrieben werden.

Abstract

Tree search algorithms are used in computer science – more specifically in the field of Artificial Intelligence – for searching decision trees. This book deals with algorithms for a special kind of decision trees, the game trees. Two important classes of algorithms for searching game trees are investigated: the minimal window search algorithms, which examine the tree in a predetermined order, and the state space search algorithms, which utilize dynamically acquired information to control the search sequence.

In this book, the practitioner will find a variety of tree search algorithms for two-person-zero-sum games. In addition to that, he will be provided with analytical and empirical criteria to evaluate their expected search performance in a given application. The theorist, on the other hand, will find a number of analytical approaches which assess the influence of static node values on the dynamic search process.