Download Spielbaum-Suchverfahren by Alexander Reinefeld (auth.) PDF

By Alexander Reinefeld (auth.)

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 artwork 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 move. 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 examine 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.

Show description

Read or Download Spielbaum-Suchverfahren PDF

Similar german_5 books

Angewandtes Problemlösungsverhalten: Denken und Handeln in komplexen Zusammenhängen

Dies Buch wendet sich vor allem an Ingenieure; es bietet ein education zum systematischen, methodischen und kreativen, produktiven Denken und Probleml? severhalten. Die aus der Denkpsychologie bekannten Ans? tze und Methoden werden in einer f? r Ingenieure geeigneten artwork und Weise entwickelt und zusammengestellt.

Technischer Lehrgang Motorkraftstoffe

BuchhandelstextAus der Sicht des Herstellers werden in diesem Heft die f? r den Kfz-Mechaniker wichtigen Informationen zusammengetragen. Die Darstellung ist mit umfangreichem Bildmaterial versehen und enth? lt neben einem einf? hrenden Grundlagenteil einen ausf? hrlichen Praxisteil mit folgenden Abschnitten:Inhalt: Erdgas, Fl?

Berechenbarkeit und Unlösbarkeit: Eine kurze Einführung für Mathematiker und Informatiker

Herr Prof. Dr. em. Klemens Döpp struggle Professor für Mathematik mit dem Schwerpunkt theoretische Informatik an der Universität Bremen.

Additional info for Spielbaum-Suchverfahren

Example text

Zum Gliick brauchen jedoch nicht samtliche bisher ermittelten Knotenwerte aufbewahrt zu werden, sondern die Schnitte konnen scllon auf der Basis zweier Schrankenwerte durchgeffihrt werden: einer unteren a-Schranke und einer oberen {3-Schmnke. Sie formen das sogenannte Suchintervall oder Suchfenster (search window). xwert der besten, bisher bekannten MAX-Zugfolge und {3 ist der Wert, den der MIN-Spieler im seinerseits besten Fall erzielen kann. 3 - Baum mit a- und p-Schnitten den MAX-Spieler eine neue Zugfolge mit einem besseren Minimaxwert gefunden wird, erhOht sich die a-Schranke entsprechend.

Nach der Diskussion der unterschiedlichen NegaScout-Varianten wollen wir nun die Funktionsweise der Nullfenster-Suche anhand eines kurzen Beispiels erlautern. 12 zeigt einen Baum, dessen Knoten mit den jeweiligen Suchfenstern der Minimax-Version des NegaScout-Algorithmus versehen sind. Angenommen, der linke Wurzel-Unterbaum ist bereits von NegaScout expandiert worden und sein Minimaxwert v(l) = 5 ist bekannt. 1 depth bei jedem rekursiven NegaScout-Aufruf explizit iibergeben werden, wie es teilweise in der Literatur iiblich ist [Rein83,Rei-Sch-Mar85J.

In der englischsprachigen Literatur ist diese Verbesserung als "failsoft" -Verbesserung [Fish83] bekannt geworden-wir verwenden im folgenden die Kurzbezeichnung F- Verbesserung. 7 zeigt die Negamax-Version des F-OI{3-Algorithmus. Die MinimaxVersion erhatt man durch sinngemaBe Anderung der Programmzeilen 6 und 8 der OI/3MAX- und OI/3MINFunktionen. Bei geschickt gewabltem Suchfenster treten in der OI{3-Baumsuche nur selten Wiederholungssuchen auf, so daB die F-Verbesserung hier bum von Nutzen ist.

Download PDF sample

Rated 4.96 of 5 – based on 17 votes