Willkommen, schön sind Sie da!
Logo Ex Libris

Spielbaum-Suchverfahren

  • Kartonierter Einband
  • 204 Seiten
(0) Erste Bewertung abgeben
Bewertungen
(0)
(0)
(0)
(0)
(0)
Alle Bewertungen ansehen
In Zusammenarbeit mit dem Fachausschuß 1.2. "Künstliche Intelligenz und Mustererkennung" der GIBaum-Suchverfahren werden... Weiterlesen
20%
75.00 CHF 60.00
Print on demand - Exemplar wird für Sie besorgt.
Bestellung & Lieferung in eine Filiale möglich

Beschreibung

In Zusammenarbeit mit dem Fachausschuß 1.2. "Künstliche Intelligenz und Mustererkennung" der GI

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.

Inhalt
1 Grundlagen.- 1.1 Einführung.- 1.2 Bäume.- 1.2.1 Allgemeine Bäum.- 1.2.2 UND/ODER-Bäum.- 1.2.3 Spielbäum.- 1.3 Konzepte der Baumsuche.- 1.3.1 Grundlegende Suchstrategien.- 1.3.2 Minimax und Negamax.- 1.3.3 Solve.- 2 Baum-Suchalgorithmen.- 2.1 Varianten des Alpha-Beta-Verfahrens.- 2.1.1 Alpha-Beta.- 2.1.2 B&B.- 2.1.3 Alpha-Beta-Verbesserungen.- 2.1.3.1 Suchfenster-Technik.- 2.1.3.2 F-Verbesserung.- 2.1.3.3 L-Verbesserung.- 2.2 Nullfenster-Suchverfahren.- 2.2.1 Scout.- 2.2.2 NegaScout.- 2.2.3 NegaScout-Verbesserungen.- 2.2.3.1 F-Verbesserung.- 2.2.3.2 L-Verbesserung.- 2.2.3.3 TL-Verbesserung.- 2.2.3.4 Verbesserte Informationsakquisition.- 2.3 Zustandsraum-Suchverfahren.- 2.3.1 Dual .- 2.3.2 SSS .- 2.3.3 Eigenschaften und Verbesserungen.- 2.3.3.1 Suchfenster-Technik.- 2.3.3.2 Verbesserte Zustandsreihenfolge.- 2.3.3.3 Elimination überflüssiger Zustände.- 2.3.3.4 L-Verbesserung für Dual .- 2.3.3.5 Globale Bestensuche für Dual .- 2.3.3.6 Zustandsraum-Suche in Graphen.- 2.3.3.7 Hybride Algorithmen.- 2.3.3.8 Iterative Zustandsraum-Suche.- 2.3.4 Zusammenfassung.- 3 Theoretische Effizienzanalyse.- 3.1 Effizienzanalyse bei gegebener Blattwertverteilung.- 3.2 Notwendige und hinreichende Knoten-Expansionskriterien.- 3.2.1 Expansionskriterium für B&B.- 3.2.2 Expansionskriterium für Alpha-Beta.- 3.2.3 Expansionskriterium für SSS .- 3.2.4 Expansionskriterium für Dual .- 3.2.5 Expansionskriterium für NegaScout.- 3.2.6 Expansionskriterium für Solve.- 3.2.7 Dominanzrelationen.- 3.3 Effizienzanalyse auf der Basis rekursiver Expansionsgleichungen.- 3.3.1 Knotentypen in optimal sortierten Bäumen.- 3.3.2 Gleichungssystem für NegaScout.- 3.3.3 Gleichungssystem für Alpha-Beta.- 3.3.4 Modellerweiterung für Wiederholungssuchen.- 3.3.5 Auswertung der Gleichungssysteme.- 3.3.6 Zusammenfassung.- 3.4 Kritik der drei theoretischen Modelle.- 4 Empirische Effizienzanalyse.- 4.1 Speicherplatzbedarf.- 4.2 Statistische Effizienzanalyse anhand großer Bäume.- 4.2.1 Auswahl der Baumart, Baumform und Blattwertverteilung.- 4.2.2 Erzeugung synthetischer Bäume.- 4.2.3 Leistungsmaße.- 4.2.4 Versuchsdurchführung und Auswertung.- 4.3 Vollständige Effizienzanalyse anhand kleiner Bäume.- 4.3.1 Überblick.- 4.3.2 Sucheffizienz der Nullfenster-Suchverfahren.- 4.3.3 Sucheffizienz der Zustandsraum-Suchverfahren.- 4.3.4 Zusammenfassung und Ausblick.- 4.4 Der Wert globaler Knoteninformationen.- 4.5 Rechenzeitbedarf.- 4.6 Zusammenfassung.- 5 Schlußbemerkungen.- 5.1 Zusammenfassung.- 5.2 Offene Probleme.- Abbildungsverzeichnis.- Tab eilenVerzeichnis.

Produktinformationen

Titel: Spielbaum-Suchverfahren
Autor:
EAN: 9783540507420
ISBN: 978-3-540-50742-0
Format: Kartonierter Einband
Herausgeber: Springer Berlin Heidelberg
Genre: Informatik
Anzahl Seiten: 204
Gewicht: 387g
Größe: H245mm x B170mm x T15mm
Jahr: 1989

Weitere Produkte aus der Reihe "Subreihe Künstliche Intelligenz"