Skip to main content
main-content

Über dieses Buch

Baum-Suchverfahren werden in der Informatik, insbesondere im Teilbereich der Künstlichen Intelligenz, zum Durchsuchen von Entscheidungsbäumen eingesetzt. Das vorliegende Buch befaßt sich mit Baum-Suchverfahren 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, wie z.B. Schach, Dame und Go. Neben den Algorithmen 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 dabei die zu durchsuchenden Bäume, deren Knotenbeziehungen auf einfache Weise in mathematischen Gleichungssystemen beschrieben werden.

Inhaltsverzeichnis

Frontmatter

Kapitel 1. Grundlagen

Zusammenfassung
Ohne den Einsatz effizienter Baum-Suchverfahren wären die ersten spektakulären Erfolge der Künstlichen Intelligenz (KI) in den frühen sechziger Jahren nicht denkbar gewesen. Sowohl die Problemlösungssysteme der ersten Generation als auch die Spielprogramme, die schon sehr früh als Testobjekt für die Programmierung komplexer Entscheidungsprozesse dienten, beruhen auf der Analyse umfangreicher Bäume von Handlungsalternativen.
Alexander Reinefeld

Kapitel 2. Baum-Suchalgorithmen

Zusammenfassung
In diesem Kapitel stellen wir Baum-Suchalgorithmen zur Berechnung des Minimaxwertes von Spielbäumen vor. Genauer gesagt, handelt es sich um Suchbaum-Reduktionsverfahren, denn diese Algorithmen dienen nicht nur dem bloßen Durchsuchen von Bäumen, sondern mit ihrer Hilfe sollen während des Suchprozesses möglichst viele überflüssige Knoten, und sogar ganze Unterbäume, abgeschnitten werden. Das darf natürlich nur in den Unterbäumen geschehen, die den Minimaxwert garantiert nicht beeinflussen können. Der Abschnitt geschieht auf der Grundlage von zuvor im Suchprozeß erworbenen Knoteninformationen.
Alexander Reinefeld

Kapitel 3. Theoretische Effizienzanalyse

Zusammenfassung
Mit der stetig zunehmenden Verfügbarkeit von Rechenzeit wurden empirische Experimente in den letzten Jahren zwar immer beliebter, auf eine theoretische Effizienzanalyse kann aber dennoch nicht verzichtet werden: Sie unterliegt keinen empirischen Unwägbarkeiten (wie z.B. der Güte des übersetzten Programmkodes oder der Effizienz des Zielrechners), sie erfordert anstelle von Rechenaufwand nur gedanklichen Aufwand und ihre Ergebnisse können—zumindest im Prinzip—leicht verifiziert werden.
Alexander Reinefeld

Kapitel 4. Empirische Effizienzanalyse

Zusammenfassung
Als Ergänzung zu den theoretischen Studien des vorangegangenen Kapitels stellen wir im folgenden eine Reihe empirischer Untersuchungen zur praktischen Leistungsmessung der Suchalgorithmen vor. Die Experimente haben das Ziel, dem Anwender Vergleichsdaten in die Hand zu geben, mit deren Hilfe er entscheiden kann, welcher Suchalgorithmus am besten in einer gegebenen Aufgabe zu verwenden ist. Wesentliche Grundlage der Entscheidung sind die drei Effizienzmaße Speicherplatzbedarf, Suchkomplexität und Rechenzeitbedarf.
Alexander Reinefeld

Kapitel 5. Schlußbemerkungen

Zusammenfassung
Die Entwicklung im Bereich „Spielbaum-Suchverfahren“ ist in letzter Zeit so stürmisch verlaufen, daß nur wenig Zeit blieb, die Neuerungen zu werten und einzuordnen. Man denke nur an die rasche Folge grundlegender Erfindungen, wie die des SSS*-Verfahrens (1979), des NegaScout-Verfahrens (1982) und des Dual*-Verfahrens (1984/85). Hinzu kommen die vielen, in derselben kurzen Zeitspanne entwickelten algorithmischen Verbesserungen.
Alexander Reinefeld

Backmatter

Weitere Informationen