Kapitel 2

Suchverfahren

2.1 Algorithmische Suche

Oft hat man in einer vorgegebenen Problemlosungs-Situation die Aufgabe, einenbestimmten Zweck zu erreichen, einen (Aktions-)Plan fur einen Agenten zu ent-wickeln, einen Weg zu finden o.a. Hierzu benotigt man zunachst eine Reprasen-tation des aktuellen Zustandes sowie der Moglichkeiten, die man hat, um seinZiel zu erreichen. I.a. gibt es kein effizientes Verfahren, um den Plan zu berech-nen, denn nicht alle Probleme haben so einfache Losungen wie die Aufgabe zuzwei gegebenen Zahlen deren Produkt zu bestimmen. Man benotigt somit Such-verfahren. In diesem Abschnitt werden einige Suchverfahren, deren Anwendungund Eigenschaften besprochen.

Beispiele sind:Spiele: Suche nach dem besten ZugLogik: Suche nach einer Herleitung einer AussageAgenten: Suche nach der optimalen nachsten AktionPlanen: Suche nach einer Folge von Aktionen eines intelligenten

Agenten.Optimierung: Suche eines Maximums einer mehrstelligen Funktion auf

den reellen Zahlen

Wir beschranken uns auf die Falle, in denen die Aufgabe eindeutig und exaktformulierbar ist.Die exakte Reprasentation der Zustande, der Ubergange, der Regeln ist Teil derProgrammierung und Optimierung der Suche.Meist hat man:

• Anfangssituationen

• Kalkulregeln, die es erlauben aus einer Situation die nachste zu berechnen(Spielregeln)

• Test auf Zielsituation

1

KI, SS 2006, Kapitel 2, 15. Mai 2006 2

Beispiel 2.1.1

Schach: Gegeben eine Stellung,Gesucht ist ein Zug, der zum Gewinn fuhrt.

Deduktion: Gegeben eine Menge von Axiomen und evtl. schon bewiesenenSatzen und Lemmas. Ebenso eine zu beweisende Aussage AGesucht ist ein Beweis fur A.

Planen: Gegeben eine formale Beschreibung des interessierenden Bereichs; z.B.Fahrplan, Anfangsort, Zeit, Zielort der zu planenden Reise.Gesucht: Ein Plan, der die Reise ermoglicht.

2.1.1 Beispiel: das n-Damen Problem1

Auf ein n×n - Schachfeld verteile n Damen so, dass keine die anderebedroht

Moglicher Ablauf der Suche, wenn n = 4 ist.1. Dame A-12. Dame A-2; Bedrohung3. Dame A-2 nach B-2 Bedrohung (Diagonale)4. Dame B-2 nach C-25. Dame A-3; Bedrohung6. Dame A-3 nach B-3; Bedrohungusw9. Dame auf Reihe 3 zurucknehmen, Dame C-2 auf D-210. Dame A-311. Dame A-3 nach B-3usw.

A B C D

1

2

3

4

1Dies ist nur als Demonstrationsbeispiel gedacht, denn es gibt linear berechenbare syste-matische Losungen.

KI, SS 2006, Kapitel 2, 15. Mai 2006 3

2.1.2 Beispiel:”Missionare und Kannibalen“

3 Missionare und 3 Kannibalen sind auf einer Seite eines Flusses.Es gibt ein Boot, in dem hochstens zwei Personen rudern konnen.Bedingung: Die Kannibalen durfen weder auf einer Uferseite nochim Boot jemals in der Uberzahl sein.Gesucht: ein Plan zur Uberquerung des Flusses, der diese Bedingungeinhalt.

Kodierungsmoglichkeiten des Problems:Wir betrachten aufeinanderfolgende Zustande, die aus der Anzahl M. und K.an einem Ufer bestehen sowie der Position des Bootes:1. Am Anfang: 3M, 3K, L, 0M, 0KZiel ist die Situation: 0M, 0K, R, 3M, 3K

mogliche zweite Situationen:2.1 2M, 3K, R, 1M, 0K2.2 3M, 2K, R, 0M, 1K2.3 2M, 2K, R, 1M, 1K

Man sieht: 2.1 ist verboten, die anderen erlaubt. Die naive Suche wurde Zyklenenthalten, die dem Hin-und-Her-Rudern entsprechen, ohne dass sich etwasandert.Es gibt offensichtliche Verbesserungen der naiven Suche:

• Suche nicht in einem Baum aller Moglichkeiten, sondern in einem gerich-teten Graphen.

• schon versuchte Situationen werden nicht noch einmal verfolgt.

3,3,<

2,3,> 3,2,> 2,2,>

M,K,B

2,3,<

1,3,> 3,1,>

3,2,<

Die Losung ist (ohne ungultige Situationen)

KI, SS 2006, Kapitel 2, 15. Mai 2006 4

3,3,<

3,2,> 2,2,>

M,K,B

3,1,>

3,2,<

3,0,>3,1,<1,1,>2,2,<0,2,>0,3,<0,1,>0,2,<0,0,>

Beobachtungen: Das Problem ist doch nicht ganz eindeutig formuliert: Es gibtfolgende Probleme der Reprasentation:

1. Die Reprasentation kann Eindeutigkeit herbeifuhren, die in der Problem-stellung nicht enthalten war. Zum Beispiel ist das Ein-und Aussteigen ausdem Boot nicht mitberucksichtigt: Was passiert, wenn ein Kannibale mitdem Boot am Ufer ankommt, und dort befinden sich ein Missionar und einKannibale, und der Missionar will im Boot zuruckfahren. Ist das erlaubtoder nicht? Reprasentiert man andere Zustande, z.B. nur die Zustandewahrend des Bootfahrens, kann es erlaubt sein.

2. Die Reprasentation bestimmt die Struktur des Suchraumes mit. Z.B.Wenn man die Missionare und Kannibalen mit Namen benennt, danngibt es folgende Anfangssituation: {M1,M2,M3,K1,K2,K3, B}Jetzt gibt es 15 Folgesituationen:

(a) {M2,M3,K1,K2,K3}(b) {M1,M3,K1,K2,K3}(c) {M1,M2,K1,K2,K3}(d) usw

Die Anzahl der erlaubten Folgesituationen ist 12.

Offensichtlich ist in dieser Reprasentation die Suche sehr viel schwieriger.

KI, SS 2006, Kapitel 2, 15. Mai 2006 5

3. Die Reprasentation hat auch eine Wahl bei der Festlegung der Knoten undder Nachfolgerfunktion. z.B. kann man bei n-Dame auch als Nachfolgerjede Situation nehmen, bei der eine Dame mehr auf dem Schachbrett steht

!!! Das Finden einer geeigneten Reprasentation und die Organisation der Sucheerfordert Nachdenken und ist Teil der Optimierung der Suche.

2.1.3 Suchraum, Suchgraph

Wenn man vom Problem und der Reprasentation abstrahiert, kann man die Su-che nach einer Losung als Suche in einem gerichteten Graphen (Suchgraph, Such-raum) betrachten. Hier ist zu beachten, dass der gerichtete Graph nicht explizitgegeben ist, er kann z.B. auch unendlich groß sein, sondern dass der Graph im-plizit durch Erzeugungsregeln gegeben ist. Die Suche und partielle Erzeugungdes Graphen sind somit verflochten. Der Suchgraph besteht aus:

Knoten Situation, ZustandeKanten zeigen auf Nachfolgesituationen; das entspricht Ubergangen zwi-

schen den SituationenAnfangssituationZielsituationen Eigenschaft eines Knotens, die gepruft werden kann.

Diesen Graphen (zusammen mit seiner Erzeugung) nennt man auch Suchraum.

Wichtige Begriffe sind:

Verzweigungrate des Suchraumes bei Knoten K (branching factor) = An-zahl der direkten Nachfolger von K.

Große des Suchraumes ab K in Tiefe d = Anzahl der Knoten, die von Kaus in d Schritten erreichbar sind.

mittlere Verzweigungrate des Suchraumes

Suchstrategie: Vorgehensweise bei der Durchmusterung des Suchraumes

vollstandige Strategie findet in endlicher Zeit ein Ziel, falls eines existiert.

Bemerkung 2.1.2 Im allgemeinen hat man eine mittlere Verzweigungsratec > 1. Damit ist der Aufwand der Suche (mindestens) exponentiell in der Tiefedes Suchraumes. Das nennt man auch kombinatorische Explosion.Die meisten Suchprobleme sind NP-vollstandig bzw. NP-hart. In diesem Fallbenotigen alle bekannten Algorithmen im schlechtesten Fall (mindestens) expo-nentiellen Zeitaufwand in der Große des Problems.

2.1.4 Prozeduren fur nicht-informierte Suche (Blindsearch)

Nicht-informiert bedeutet hier, dass die Suche nur den Graphen und die Erzeu-gungsfunktion verwenden darf (kann), aber keine anderen Informationen uberdie Knoten, Kanten usw.

KI, SS 2006, Kapitel 2, 15. Mai 2006 6

Parameter:

• Menge der initialen Knoten

• Menge der Zielknoten, bzw. eindeutige Festlegung der Eigenschaften derZielknoten

• Nachfolgerfunktion

Algorithmus nicht-informierte SucheL sei Multimenge der noch nicht untersuchten Knoten, markiert mit dem dorthinfuhrenden Weg.Eingabe: Menge der initialen Knoten. (I.a. ein Knoten)

1. Wenn L leer ist, dann breche ab.

2. Wahle einen beliebigen Knoten K aus L .

3. Wenn K ein Zielknoten ist, dann gebe aus: Zielknoten und Weg dorthin(d.h. Weg im Graphen dorthin)

4. Wenn K kein Zielknoten, dann nehme Menge N(K) der direkten Nachfol-ger von K und verandere L folgendermaßen:L′ := (L ∪N(K)) \ {K}Mache weiter mit Schritt 1 und L := L′

Varianten der blinden Suche: Breitensuche und Tiefensuche

Algorithmus Tiefensuche:Nehme bei Auswahl den ersten Knoten in L:L ist Liste von Knoten, markiert mit dem Pfad.Das kann man auch als Stack der besuchten Knoten implementieren.

1. Wenn L leer ist, dann breche ab.

2. Wahle ersten Knoten K aus L, sei R die Restliste.

3. Wenn K ein Zielknoten ist, dann gebe aus: Zielknoten und Weg dorthin(d.h. Weg im Graphen dorthin)

4. Wenn K kein Zielknoten, dann sei N(K) (geordnete) Liste der direktenNachfolger von K, mit dem Weg dorthin markiertL := N(K) ++ R. 2

Mache weiter mit 1.

Bemerkung 2.1.3 Eigenschaften der Tiefensuche:Komplexitat: (bei fester Verzweigungsrate c > 1)

Platz: linear in der Tiefe. (wenn die Verzweigungsrate eine obere Schranke hat)

2++ bezeichnet das Zusammenhangen von Listen

KI, SS 2006, Kapitel 2, 15. Mai 2006 7

Zeit: entspricht Anzahl der besuchten Knoten (als Baum gesehen) Aufwand istexponentiell in der Tiefe.

Beachte, dass Tiefensuche nicht vollstandig ist, wenn der Suchgraph unendlichgroß ist.

Pragmatische Verbesserungsmoglichkeiten der Tiefensuche:

Tiefensuche mit Tiefenbeschrankung kWenn die vorgegebene Tiefenschranke k uberschritten wird, werden keineNachfolger dieser Knoten mehr erzeugt.

Die Tiefensuche findet in diesem Fall jeden Zielknoten, der hochstens Tiefek hat.

Tiefensuche mit SharingNutze aus, dass der gerichtete Graph manchmal kein Baum ist. Schon un-tersuchte Knoten werden nicht nochmal untersucht und redundant weiter-verfolgt. Implementierung durch Speichern der bereits besuchten Knotenz.B. in einer Hash-Tabelle.

Platzbedarf Anzahl der besuchten Knoten (wegen Speicher fur schonuntersuchte Knoten)

Zeit: n ∗ log(n) mit n = Anzahl der untersuchten Knoten.

Tiefensuche mit Sharing, aber beschranktem SpeicherFunktioniert wie Tiefensuche mit Sharing, aber es werden maximal nur BKnoten gespeichert.Der Vorteil gegenuber Tiefensuche ist Ausnutzen von gemeinsamen Kno-ten; besser als Tiefensuche mit Sharing, da die Suche weiterlauft, wenndie Speicherkapazitat nicht fur alle besuchten Knoten ausreicht.

Effekt des Zurucksetzen: (Backtracking)

Tiefensuche bewirkt Backtracking, wenn nicht erfolgreiche Pfade erkannt wer-den.Die Arbeitsweise der Tiefensuche ist: Wenn Knoten K keine Nachfolger hat,oder Tiefenbeschrankung uberschritten, dann mache weiter mit dem nachstenBruder von K. (auch chronologisches Zurucksetzen; chronological backtracking).Abwandlungen:

dynamic backtracking

dependency-directed backtracking

Diese Varianten, die Teile des Suchraumes abschneiden, kann man verwenden,wenn mehr uber die Struktur des Suchproblems bekannt ist. Insbesondere wennklar ist, dass man trotz der Abkurzungen der Suche auf jeden Fall noch einen

KI, SS 2006, Kapitel 2, 15. Mai 2006 8

Zielknoten finden kann.

Es gibt auch Suchprobleme, bei denen kein Backtracking erforderlich ist (greedyVerfahren ist moglich)Dies kann z.B. der Fall sein, wenn jeder Knoten noch einen Zielknoten als Nach-folger hat. Die Tiefensuche reicht dann aus, wenn die Tiefe der Zielknoten inalle Richtungen unterhalb jedes Knotens beschrankt ist. Anderenfalls reicht Tie-fensuche nicht aus (ist nicht vollstandig), da diese Suche sich immer den Astaussuchen kann, in dem der Zielknoten weiter weg ist.

Algorithmus Breitensuche:L als Menge von Knoten, markiert mit dem Pfad

1. Wenn L leer ist, dann breche ab.

2. Wenn L einen Zielknoten K enthalt, dann gebe aus: K und Weg dorthin.

3. Sonst, sei N(L) Menge aller direkten Nachfolger der Knoten von L, miteinem Weg dorthin markiert.Mache weiter mit Schritt 1 und L := N(L).

Komplexitat: (bei fester Verzweigungsrate c > 1)

Platz: ∼ Anzahl der Knoten in Tiefe d, d.h. cd, und das ist exponentiell in derTiefe d.

Zeit: (Anzahl der Knoten in Tiefe d) + Aufwand fur Mengenbildung: n + n ∗log(n), wenn n = #Knoten. Bei obiger Annahme einer fester Verzwei-gungsrate ist das cd(1 + d ∗ log(c)).

Die Breitensuche ist vollstandig! D.h. wenn es einen (erreichbaren) Zielknotengibt, wird sie auch in endlicher Zeit einen finden.

Iteratives Vertiefen (iterative deepening)

Dieses Verfahren ist ein Kompromiss zwischen Tiefen- und Breitensuche, wo-bei man die Tiefensuche mit Tiefenbeschrankung anwendet. Hierbei wird dieTiefenschranke iterativ erhoht. Wenn kein Zielknoten gefunden wurde, wird dieganze Tiefensuche jeweils mit großerer Tiefenschranke nochmals durchgefuhrt.Man beachte, dass man die Tiefe, in der der erste Zielknoten auftritt, nichtvorhersagen kann.Der Vorteil des iterativen Vertiefens ist der viel geringere Platzbedarf gegenuberder Breitensuche bei Erhaltung der Vollstandigkeit des Verfahrens. Man nimmteine leichte Verschlechterung des Zeitbedarfs in Kauf, da Knoten mehrfach un-tersucht werden.

Komplexitatsbetrachtung: bei fester Verzweigungsrate c > 1.

Platzbedarf: linear in der Tiefe !

KI, SS 2006, Kapitel 2, 15. Mai 2006 9

Zeitbedarf: Wir zahlen nur die im Mittel besuchten Knoten, wenn der erste

Zielknoten in Tiefe k ist, wobei wir bei der Rechnung die Naherungn∑

i=1

ai =

an+1

a− 1fur a > 1 verwenden.

Tiefensuche mit Tiefenbeschrankung k:

0.5 ∗ (k∑

i=1

ci ≈ 0.5 ∗ (ck+1

c− 1)

Iteratives Vertiefen bis Tiefe k:k−1∑i=1

ci+1

c− 1+ 0.5 ∗ (

ck+1

c− 1) ≈ ck+1

(c− 1)2+ 0.5 ∗ (

ck+1

c− 1).

Der Faktor des Mehraufwandes fur iteratives Vertiefen im Vergleich zurTiefensuche (mit der richtigen Tiefenbeschrankung) ergibt sich zu:

ck+1

(c− 1)2+ 0.5 ∗ (

ck+1

c− 1)

0.5 ∗ (ck+1

c− 1)

=

ck+1

(c− 1)2

0.5 ∗ (ck+1

c− 1)

+ 1

=2

c− 1+ 1

Ein Tabelle der ca.-Werte des Faktors d =2

c− 1+ 1 ist

c 2 3 4 5 . . . 10d 3 2 1, 67 1, 5 . . . 1, 22

D.h. der eigentliche Aufwand ergibt sich am Horizont der Suche. Der Ver-gleich ist zudem leicht unfair fur iteratives Vertiefen, da die Tiefensucheja den Wert von k nicht kennt.

Dieses Verfahren des iteratives Vertiefen wird z.B. im Automatischen Beweisenverwendet:M. Stickel: A PROLOG-technology theorem prover.Die Entscheidungsalternativen, die man beim Optimieren abwagen muss, sind:

• Speichern

• Neu Berechnen.

Stickels Argument: in exponentiellen Suchraumen greift die Intuition nicht im-mer: Neuberechnen kann besser sein als Speichern und Wiederverwenden.

Bemerkung 2.1.4 Beim dynamischen Programmieren ist in einigen Fallender Effekt gerade umgekehrt. Man spendiert Platz fur bereits berechnete Er-gebnisse und hat dadurch eine enorme Ersparnis beim Zeitbedarf.

KI, SS 2006, Kapitel 2, 15. Mai 2006 10

Iteratives Vertiefen (iterative deepening) mit Speicherung

Die Idee hierbei ist, den freien Speicherplatz beim iterativen Vertiefen sinnvollzu nutzen.Dies kann man zu zwei unterschiedliche Nutzungen:

1. Bei jedem Restart der Tiefensuche wird der zugehorige Speicher initia-lisiert. Wahrend der Tiefensuchphase speichert man Knoten, die bereitsexpandiert waren und vermeidet damit die wiederholte Expansion. Hierkann man soviele Knoten speichern wie moglich. Man spart sich redundan-te Berechnungen, aber der Nachteil ist, dass bei jeder Knotenexpansionnachgeschaut werden muss, ob die Knoten schon besucht wurden.

2. Man kann Berechnungen, die in einer Tiefensuchphase gemacht wurden, indie nachste Iteration der Tiefensuche retten und somit redundante Berech-nungen vermeiden. Wenn alle Knoten der letzten Berechnung gespeichertwerden konnen, kann man von dort aus sofort weiter machen (d.h. manhat dann Breitensuche). Da man das i.a. nicht kann, ist folgendes sinnvoll:Man speichert den linken Teil des Suchraum, um den Anfang der nachstenIteration schneller zu machen, und Knoten, die schon als Fehlschlage be-kannt sind, d.h. solche, die garantiert keinen Zielknoten als Nachfolgerhaben.

2.1.5 Ruckwartssuche

Idee der Ruckwartssuche ist:

man geht von einem (bekannten) Zielknoten aus und versucht denAnfangsknoten zu erreichen.

Voraussetzungen:

• Man kann Zielknoten explizit angeben (nicht nur eine Eigenschaft, die derZielknoten erfullen muss).

• man kann von jedem Knoten die direkten Vorganger berechnen.

Ruckwartssuche ist besser als Vorwartssuche, falls die Verzweigungsrate inRuckwartsrichtung kleiner ist die Verzweigungsrate in Vorwartsrichtung.Man kann normale Suche und Ruckwartssuche kombinieren zurBidirektionalen Suche.

2.2 Informierte Suche, Heuristische Suche

Die Suche nennt man ”informiert“, wenn man zusatzlich eine Bewertung vonallen Knoten des Suchraumes angeben kann, d.h. eine Schatzfunktion, die maninterpretieren kann als Ahnlichkeit zu einem Zielknoten, oder als Schatzung des

KI, SS 2006, Kapitel 2, 15. Mai 2006 11

Abstands zum Zielknoten. Der Zielknoten sollte ein Maximum bzw. Minimumder Bewertungsfunktion sein.Eine Heuristik (”Daumenregel“) ist eine Methode, die oft ihren Zweck erreicht,aber nicht mit Sicherheit. Man spricht von heuristischer Suche, wenn die Schatz-funktion in vielen praktisch brauchbaren Fallen die richtige Richtung zu einemZiel angibt, aber moglicherweise manchmal versagt.Das Suchproblem kann jetzt ersetzt werden durch:

Minimierung (bzw. Maximierung) einer Knotenbewertung (einerFunktion) auf einem gerichteten Graphen

Variante: Maximierung in einer Menge oder in einem n-dimensionaler Raum.

Beispiel: 8-Puzzle

4

8

6

7 2

5

1

3

Reprasentation als 3× 3-Matrix, wobei aij = n, wenn n die Nummer des Platt-chens ist, das an Position (i, j) ist.

Anfang: beliebige Permutation der Matrix, z.B. 8 B 16 5 47 2 3

Ziel: 1 2 3

4 5 67 8 B

Bewertungsfunktionen: zwei Beispiele sind:

KI, SS 2006, Kapitel 2, 15. Mai 2006 12

1. f1() Anzahl der Plattchen an der falschen Stelle

2. f2() Anzahl der Zuge (ohne Behinderungen zu beachten), die manbraucht, um Endzustand zu erreichen.

2 3 18 7 6B 5 4

f1 = 7 ; f2 = 2 + 1 + 1 + 3 + 1 + 0 + 2 + 2 = 12

2 3 1B 7 68 5 4

f1 = 7 ; f2 = 2 + 1 + 1 + 3 + 1 + 0 + 2 + 1 = 11

3 Man sieht, dass die zweite Bewertungsfunktion genauer angibt als die erste,wie gut die erreichte Situation ist.Aber: es ist bekannt, dass es Ausgangssituationen gibt, von denen aus man dasZiel nicht erreichen kann (Permutation ist ungerade).In den Unterlagen ist ein Haskell-Programm, das mit Best-First und verschiede-nen Bewertungsfunktionen, nach nicht allzu langer Zeit eine Zugfolge fur 3× 3findet. Wenn man dieses Puzzle fur großere n per Hand und per Suche probiertund vergleicht, so erkennt man, dass der Rechner sich in lokalen Optimierungenverliert, wahrend man von Hand eine Strategie findet, die die Zielsituationherstellt, falls es uberhaupt moglich ist. Diese Strategie ist in etwa so:

• Verschiebe zunachst die 1 so, dass diese an ihrem Platz ist.

• Verschiebe zunachst die 2 so, dass diese an ihrem Platz ist.

• . . . . . .

• bei den letzten beiden Ziffern der ersten Zeile: n− 1, n erlaube eine Suchedurch Verschieben innerhalb eines 3× 2-Kastchens.

• Benutze diese Strategie bis zur vorletzten Zeile.

• Bei der vorletzten Zeile, fange von links an, jeweils zwei Plattchen korrektzu schieben, bis das letzte 2× 3 Rechteck bleibt.

• Innerhalb dieses Rechtecks probiere, bis die Plattchen an ihrem Platz sind.

Man sieht, dass einfache Bewertungsfunktionen diese Strategie nicht erzeugen.Kennt man die Strategie, kann man eine (komplizierte) Bewertungsfunktion an-geben, die dieses Verhalten erzwingt. Beim n-Puzzle ist es vermutlich schwierigerdiese Bewertungsfunktion zu finden, als das Probkem direkt zu programmieren,wenn man eine Strategie erzwingen will. Hier braucht man eigentlich einen gutenPlanungsalgorithmus mit Zwischen- und Unterzielen und Prioritaten.

3Die Summe ist in der Reihenfolge 1, . . . , n

KI, SS 2006, Kapitel 2, 15. Mai 2006 13

2.2.1 Bergsteigerprozedur (Hill-climbing)

Dies ist auch als Gradientenaufstieg (-abstieg) bekannt, wenn man einen-dimensionale Funktion in die reellen Zahlen maximieren will (siehe auchVerfahren im Bereich Operations Research).

Parameter der Bergsteigerprozedur

• Menge der initialen Knoten

• Menge der Zielknoten, bzw. eindeutige Festlegung der Eigenschaften derZielknoten (ohne Kontext)

• Nachfolgerfunktion (Nachbarschaftsrelation)

• Bewertungsfunktion der Knoten

Prozedur: BergsteigenEingabe: L Liste der initialen Knoten: jeder Knoten ist mit dem Weg dorthinmarkiert.

1. Wenn L leer ist, dann breche ab

2. sei K der erste Knoten von L und R der Rest. Wenn K ein Zielknoten ist,dann gebe K und den Weg dahin aus.

3. Sei N(K) die (nach Gute) sortierte Liste der Nachbarn (Nachfolger) vonK. Entferne aus N(K) die bereits im Weg bis K besuchten Knoten mitErgebnis N ′ (um zirkulare Wege zu vermeiden).Mache weiter mit Schritt 1 und L := N ′ ++ R 4

Bemerkungen: Bergsteigen verhalt sich analog zur Tiefensuche:Der Platzbedarf ist linear abhangig von der Suchtiefe.Bei guter Bewertungsfunktion wird das Ziel direkt angesteuert.Es werden nur Wege ohne doppelte Knoten erzeugt.

Probleme mit der Bergsteigerprozedur

1. Der Aufwand fur Berechnung der Bewertungsfunktion darf nicht zu hochsein

2. Eine gute Bewertungsfunktion ist nicht immer zu finden: Z.B: bei Bewei-sen: wie weit ist das gerade bewiesene Lemma vom Theorem entfernt?

3. Bewertungsfunktionen konnen lokale Maxima oder Plateaus haben.Bei lokalen Maxima wird die Optimierung in einem evtl. zu kleinen Werteingefangen. Wenn in diesem lokalen Maximum kein Zielknoten ist, ist dieSuche zunachst erfolglos.Das lokale Minimum wird erst verlassen, wenn die Bedingung der nichtzirkularen Wege einen Weg aus dem lokalen Optimum erzwingt. Vorherwerden aber alle moglichen Wege zum lokalen Optimum ausprobiert.

4++ bezeichnet das Zusammenhangen von Listen

KI, SS 2006, Kapitel 2, 15. Mai 2006 14

4. Bei Plateaus lasst sich die Menge der Nachfolger nicht mehr sortieren undsomit die Richtung nicht mehr bestimmen

2.2.2 Der Beste-zuerst (Best-first) Suche

Prozedur:Eingabe: L Liste der initialen Knoten, sortiert, so dass die besseren Knotenvorne sind.Jeder Knoten sei mit einem Weg zum aktuellen Knoten markiert.

1. Wenn L leer ist, dann breche ab

2. sei L = K : R . Wenn K ein Zielknoten ist, dann gebe K und den Wegdahin aus.

3. Sei N(K) die Liste der Nachfolger von K. Entferne aus N(K) die bereitsim Weg besuchten Knoten mit Ergebnis N ′

Sortiere N ′ ++ R mit Ergebnis L′ nach den Bewertungen. Mache weitermit Schritt 1 wobei L := L′.

Unterschied zum Bergsteigen:wenn ein guter Knoten nur schlechte Nachfolger hat, dann werden vorher be-suchte, gute Knoten relativ schnell wieder berucksichtigt, da alle Knoten, dienoch offen sind, sortiert werden.Wenn die Nachfolgerfunktion symmetrisch ist (z.B. Nachbar-von) dann gibt es(fast) keinen Unterschied.

Markiert man bereits besuchte Knoten, dann ist es eine gesteuerte Breitensuche,die lokale Maxima wieder verlassen kann, aber der Preis ist ein hoher Speicher-bedarf.

2.2.3 Simuliertes Ausgluhen (simulated annealing)

Die Analogie zum Ausgluhen ist:Am Anfang hat man hohe Energie und alles ist beweglich,dann langsame Abkuhlung, bis die Kristallisation eintritt (bei minimaler Ener-gie)Die Anwendung in einem Suchverfahren ist sinnvoll fur Optimierung vonn-dimensionalen Funktionen mit reellen Argumenten, weniger bei einer Suchenach einem Zielknoten in einem gerichteten Suchgraphen.Bei Optimierung von n-dimensionalen Funktionen kann man die Argumenteverandern wobei man den Abstand der verschiedenen Argumenttupel abhangigvon der Temperatur definieren kann. Bei geringerer Temperatur sinkt dieserAbstand. Der Effekt ist, dass man zunachst mit einem etwas groben Rasterversucht, Anhaltspunkte fur die Nahe zu einem Optimum zu finden. Hat mansolche Anhaltspunkte, verfeinert man das Raster, um einem echten Maximumnaher zu kommen, und um nicht uber den Berg druber zu springen bzw. diesen

KI, SS 2006, Kapitel 2, 15. Mai 2006 15

zu untertunneln.

Implementierung in einem Optimierungsverfahren:

1. Am Anfang große Schrittweite (passend zum Raum der Argumente).Mit diesen Werten und der Schrittweite Suche analog zu Best-First; dannallmahliche Verminderung der Schrittweite, hierbei Schrittweite und Rich-tung zufallig auswahlen, bis sich das System stabilisiert. Die besten Knotenwerden jeweils weiter expandiert.

2. Alternativ:Das System lauft getaktet. Am Anfang wird eine zufallige Menge vonKnoten berucksichtigt. Bessere Knoten durfen mit großerer Wahrschein-lichkeit im nachsten Takt Nachfolger erzeugen als schlechte Knoten. DieWahrscheinlichkeit fur schlechte Knoten wird allmahlich gesenkt, ebensodie Schrittweite.

Analoge Verfahren werden auch in kunstlichen neuronalen Netzen verwendetbeim Lernen verwendet. Variante 2 hat Analogien zum Vorgehen bei evoluti-onaren Algorithmen.Vorteil des Verfahrens: lokale Maxima konnen verlassen werden.Probleme: Es gibt einige Parameter zu justieren, die stark vom Problemabhangen konnen:

• Schnelligkeit der ”Abkuhlung“

• Abhangigkeit der Wahrscheinlichkeit von der ”Temperatur“ (bzw. Wertder Schatzfunktion)

2.3 A∗-Algorithmus

Gegeben sind:

• ein (gerichteter) Graph (wobei die Nachfolgerbeziehung i.a. algorithmischgegeben ist), d.h. es gibt einen Algorithmus NF, der zu jedem Knoten Ndie Nachfolger NF(N) berechnet. Wir nehmen an, dass der Graph schlichtist, d.h. es gibt hochstens eine Kante zwischen zwei Knoten.

• eine (i.a. reellwertige) Kostenfunktion gW (.) auf Wegen. Wir nehmen an,dass diese Kostenfunktion additiv ist, d.h. gW (N1 . . . Nk) = gW (N1N2) +gW (N2N3) + . . . + gW (Nk−1Nk).

• ein Startknoten S

• eine Schatzfunktion h(·), die die Kosten von einem bereits erreichten Kno-ten N bis zum nachsten Zielknoten abschatzt.

KI, SS 2006, Kapitel 2, 15. Mai 2006 16

• einen Test auf Zielknoten Z. Die Zielknoten sind meist algorithmisch defi-niert, d.h. man hat nur einen Test, ob ein gegebener Knoten ein Zielknotenist.

Ziel ist das Auffinden eines optimalen (d.h. mit minimalen Kosten) Weges vomStartknoten zu einem der Zielknoten,

Beispiel 2.3.1 Als typisches Beispiel verwenden wir die Suche nach einemkurzesten Weg von A nach B in einem Stadtplan. Hier sind die Knoten dieKreuzungen und die Kanten die Straßenabschnitte zwischen den Kreuzungen;die Kosten entsprechen der Weglange.

Der A∗-Algorithmus stutzt sich auf eine Kombination der bereits verbrauch-ten Kosten g(N) vom Start bis zu einem aktuellen Knoten N und der nochgeschatzten Kosten bis zu einem Zielknoten Z, d.h. man benutzt die Funktionf(N) = g(N) + h(N). Die Funktion h(·) sollte leicht zu berechnen sein, undmuss nicht exakt sein.Es gibt 2 Varianten des A∗-Algorithmus:

• Baum-Such-Verfahren: Kein Update des minimalen Weges bis zu einemKnoten wahrned des Ablaufs.

• Graph-Such-Verfahren: Update des minimalen Weges bis zu einem Knotenwahrend des Ablaufs

Bei Baumsuche kann der gleiche Knoten mehrfach in OPEN stehen mit ver-schiedenen Wegen.Bei Graphsuche hat man immer den aktuell bekannten minimalen Weg, undsomit den Knoten nur einmal.

Definition 2.3.2 Der A∗-Algorithmus zu f = g + h mit den oben erwahntenParametern ist folgendermaßen definiert:Datenstrukturen sind:Eine Liste OPEN von Knoten, von denen aus der Weg weiterverfolgt werdensoll.Eine Liste CLOSED von besuchten Knoten. Alle Knoten N in OPEN undCLOSED sind zusatzlich mit dem besten bisherigen Weg zum Knoten Nmarkiert. (Bezeichung im Algorithmus: g(N))

Start mit N = S, OPEN={S}, CLOSED = ∅.WHILE OPEN 6= ∅ AND N kein Zielknoten

Berechne Liste der Nachfolger NF = NF(N)Schiebe N von OPEN nach CLOSED.FOR N ′ ∈ NF DO

berechne g(N) + g(N,N ′).Wenn N ′ bereits in OPEN oder CLOSED undg(N ′) neues Optimum,dann

KI, SS 2006, Kapitel 2, 15. Mai 2006 17

Update mit neuem Optimum g(N ′) und schiebe N ′ nach OPEN.Wenn N ′ 6∈ OPEN ∪ CLOSED, dann N ′ einfugen in OPEN

END-FORWahle neuen Knoten N aus OPEN mitminimalem f(N) = g(N) + h(N)

END-WHILEWenn OPEN = ∅, dann Fehler,Sonst ist N der Zielknoten, mit dem gefundenen Weg markiert.

Beispiel 2.3.3 Im Beispiel kann man sich den Fortschritt des A∗-Algorithmusleicht klarmachen, wenn man eine Kante als 1 zahlt, weiß wo das Ziel ist, undals Schatzfunktion des Abstands die Rechteck-Norm |y2 − y1| + |x2 − x1| desAbstands vom aktuellen Knoten zum Ziel nimmt.

S

Z

Man sieht, dass der Algorithmus sowohl den oberen als auch den unteren Wegversucht.

2.3.1 Eigenschaften des A∗-Algorithmus

Im folgenden einige Bezeichnungen, die wir zur Klarung der Eigenschaftenbenotigen.g∗(N) = Kosten des optimalen Weges bis Ng∗(N,N ′) = Kosten des optimalen Weges von N nach N ′

h∗(N) = Kosten des optimalen Weges von N bis zu einem Z.f∗(N) = g∗(N) + h∗(N)

Wir bezeichnen mit f(.) = g(.) + h(.) die heuristische Gesamt-Schatzfunktion.Der A∗-Algorithmus hat gute Eigenschaften, wenn die Schatzfunktion h dieKosten unterschatzt. D.h., wenn fur jeden Knoten N : h(N) ≤ h∗(N) gilt.

Beispiel 2.3.4 Die Lange jedes Weges von A nach B in einem Stadtplan iststets langer als die direkte Entfernung (Luftlinie)

√(b2 − a2)2 + (b1 − a1)2. Die-

se einfach zu berechnende Schatzfunktion unterschatzt die echten Kosten.Wenn alle Straßen rechtwinklig aufeinander zulaufen, und es keine Abkurzungengibt, kann man auch die Rechtecknorm als Schatzung nehmen: |b2−a2|+|b1−a1|,

KI, SS 2006, Kapitel 2, 15. Mai 2006 18

denn die echten Wege konnen dann nicht kurzer als die Rechtecknorm sein (auchManhattan-Abstand genannt).

Definition 2.3.5 Voraussetzungen fur den A∗-Algorithmus:

1. es gibt nur endlich viele Knoten N mit g∗(N) + h(N) ≤ h∗(S) .

2. Fur jeden Knoten N gilt: h(N) ≤ h∗(N).

3. Fur jeden Knoten N ist die Anzahl der Nachfolger endlich.

4. Der Graph ist schlicht5.

Die Voraussetzung 1 der Endlichkeit der Knoten ist z.B. erfullt, wenn es eineuntere Schranke δ > 0 fur die Kosten einer Kante gibt.

Satz 2.3.6 Es existiere ein optimaler Weg vom Start bis zu einem ZielknotenZ. Seien d = h∗(S) die Kosten des optimalen Weges. Weiter seien die Voraus-setzungen in Definition 2.3.5 erfullt.Dann findet der A∗-Algorithmus einen optimalen Weg zu einem Zielknoten.

Beweis. Der Einfachheit halber nehmen wir an, dass es nur einen Zielknoten Zgibt. Sei S = K0,K1,K2, . . . ,Kn = Z ein optimaler Weg vom Anfang bis zumZiel. Dann gilt fur jeden Knoten Ki: der Weg Wi = S, K1, . . . ,Ki ist optimalnach Ki; denn sonst ware der Weg S, K1,K2, . . . ,Kn nicht optimal.Mit Induktion zeigen wir, dass jeder Knoten Ki vom Algorithmus expandiertwird, und der Anfangsweg Wi nach Ki (oder ein gleich guter) irgendwann alsoptimaler Weg nach Ki erkannt wird. Fur i = 0 ist das offensichtlich, denn espassiert im ersten Schritt.Sei i < n der maximale Index, so dass Ki mit dem optimalen Wert des WegesWi wahrend eines Laufs des Algorithmus markiert wurde.Wenn Ki niemals expandiert wird, dann muss es nach der Erzeugung von Ki

immer ein M in OPEN geben mit g(M) + h(M) ≤ g∗(Ki) + h(Ki) ≤ d. Dag∗(M) + h(M) ≤ g(M) + h(M) ≤ g∗(Ki) + h(Ki) ≤ d kann man die Voraus-setzung der Endlichkeit verwenden. Die letzte Ungleichung gilt, da die Schatz-funktion unterschatzend ist.Das es endlich viele Knoten M gibt, ist irgendwann entweder ein Zielknoten mitoptimalen Weg gefunden oder die Moglichkeit der Verbesserungen ausgeschopft,und alle diese Knoten sind in CLOSED.Also wird Ki irgendwann expandiert. Wenn Ki betrachtet und expandiert wird,dann werden alle Nachfolger in die Listen verteilt.Da Ki+1 Nachfolger ist, wird der Weg Wi+1 und dessen Wert auf jeden Fall beiKi+1 gespeichert. D.h. Ki+1 wird mit dem optimalen Weg markiert. Ki+1 wirdin die OPEN-Liste aufgenommen, da wir mit Induktionshypothese angenommenhaben, dass kein Kj mit j > i bereits mit optimalem Wert in einer Liste ist.Damit haben wir einen Widerspruch. Damit wird insbesondere versucht, den

5schlicht = zwischen zwei Knoten gibt es hochstens eine Kante

KI, SS 2006, Kapitel 2, 15. Mai 2006 19

Knoten Kn zu expandieren. In diesem Fall beendet der A∗-Algorithmus dieSuche und gibt den optimalen Weg aus.D.h. der A∗-Algorithmus wird auch auf jeden Fall einen optimalen Weg zumZiel finden. 2

Beachte, dass der A∗-Algorithmus auch einen anderen optimalen Weg findenkann, der von K1, . . . ,Kn verschieden ist.Folgendes Beispiel zeigt, dass im Fall einer nicht unterschatzenden Funktion h(.)der gefundene Weg nicht optimal sein muss:

Beispiel 2.3.7

SZ

A

B

1

1

h(A) = 3

h(B) = 6

h(S) = 4 5

4

Der erste gefundene Weg ist SAZ der Lange 6, da die Funktion f auf A minimalist. Aber der Weg SBZ ist optimal, da er Lange 5 hat. Er wird nicht gefunden,da die Schatzung vorgaukelt, er sei noch zu weit weg.

Beispiel 2.3.8 Fur das Stadtplan-Beispiel konnen wir folgern, dass der A∗-Algorithmus im Falle des Abstandsmaßes h(.), das die Luftlinienentfernung zumZiel misst, einen optimalen Weg finden wird. Hat der Stadtplan nur Straßen inzwei zueinander senkrechten Richtungen, dann kann man auch die Rechteck-norm nehmen.

Der Aufwand des A∗-Algorithmus ist i.a. exponentiell in der Lange des opti-malen Weges. Diese Abschatzung gilt, wenn der Graph algorithmisch gegebenist.

Bemerkung 2.3.9 Wenn man den endlichen Graphen als gegeben annimmt,mit Bewertungen der Kanten, dann kann man mit dynamischem Programmierenin polynomieller Zeit (in der Große des Graphen) alle kostenoptimalen Wegeberechnen, indem man analog zur Berechnung der transitiven Hulle eine Ma-trix von Zwischenergebnissen iteriert (Floyd-Algorithmus fur kurzeste Wege,Dijkstra-Algorithmus).

Der Dijkstra-Algorithmus passt zum A∗-Algorithmus, wenn man die Schatzfunk-tion h(N) = 0 setzt fur alle Knoten N . Dieser hat als Aufgabe, einen Weg mitminimalen Kosten zwischen zwei Knoten eines gegebenen endlichen Graphen zufinden.In diesem Fall hat man stets eine Front (OPEN) der Knoten mit minimalenWegen ab dem Starknoten.

KI, SS 2006, Kapitel 2, 15. Mai 2006 20

2.3.2 Spezialisierungen des A∗-Algorithmus:

Beispiel 2.3.10 Weitere Beispiele fur Graphen und Kostenfunktionen sind:

Wenn g(N) = Anzahl der Knoten auf dem Weg, und h(N) = 0, dann entsprichtder A∗-Algorithmus der Breitensuche.Wenn g∗(N) die Kosten des bisherigen Weges und h(N) = 0, dann ist derA∗-Algorithmus dasselbe wie die Gleiche-Kostensuche (branch-and-bound)

Die Variante A∗o des A∗-Algorithmus, die alle optimalen Weg finden soll, hatfolgende Erganzung im Algorithmus: sobald ein Weg zum Ziel gefunden wurde,mit einem Wert d, werden nur noch Knoten in OPEN akzeptiert, bei deneng(N) + h(N) ≤ d. Der Algorithmus stoppt erst, wenn keine Knoten mehr inOPEN sind.

Satz 2.3.11 Es gelten die Voraussetzung von Satz 2.3.6. Dann findet der Al-gorithmus A∗o alle optimalen Wege von S nach Z.

Beweis. Zunachst findet der A∗-Algorithmus einen optimalen Weg zu einem Ziel.Daraus ergibt sich eine obere Schranke d fur die Kosten eines optimalen Weges.Aus der Voraussetzungen ergibt sich, dass der A∗o-Algorithmus nur endlich vieleKnoten und Wege inspiziert. 2

Definition 2.3.12 Wenn man zwei Schatzfunktionen h1 und h2 hat mit:

1. h1 und h2 unterschatzen den Aufwand zum Ziel

2. fur alle Knoten N gilt: h1(N) ≤ h2(N) ≤ h∗(N)

dann nennt man h2 besser informiert als h1.

Hieraus alleine kann man noch nicht folgern, dass der A∗-Algorithmus zu h2

sich besser verhalt als zu h1. (Ubungsaufgabe)Notwendig ist: Die Abweichung bei Sortierung der Knoten mittels f muss kleinsein. D.h. optimal ware f(k) ≤ f(k′) ⇔ f∗(k) ≤ f∗(k′).

Der wichtigere Begriff ist:

Definition 2.3.13 Eine Schatzfunktion h(.) ist monoton, gdw.h(N) ≤ g(N,N ′)+h(N ′) fur alle Knoten N und deren Nachfolger N ′ und wennh(Z) = 0 ist fur Zielknoten Z.

Offenbar gilt die Monotonie-Ungleichung auch fur die optimale Weglange vonN nach N ′, wenn N ′ kein direkter Nachfolger von N ist. Dies kann man sosehen:h(N) ≤ g(N,N1) + h(N1) ≤ g(N,N1) + g(N1, N2) + h(N2)Iteriert man das, erhalt man: h(N) ≤ gW (N,N ′) + h(N ′)Und damit auch h(N) ≤ g∗(N,N ′) + h(N ′)Fur den Weg zum Ziel Z gilt damit h(N) ≤ g∗(N,Z) + h(Z) = g∗(N,Z) , dah(Z) = 0 ist.

KI, SS 2006, Kapitel 2, 15. Mai 2006 21

Lemma 2.3.14 Eine monotone Schatzfunktion h(.) ist unterschatzend.

Die Monotonie der Schatzfunktion hangt mit der Dreiecksungleichung der Eu-klidischen Geometrie zusammen.Die Monotonie sieht man am Verhalten der Funktion f : Wenn die Schatzfunk-tion monoton ist, dann wachst der Wert von f monoton, wenn man einen Wegweiter expandiert.

Aussage 2.3.15 Ist die Schatzfunktion h monoton, so expandiert der A∗-Algorithmus jeden untersuchten Knoten beim ersten mal bereits mit dem op-timalen Wert. D.h. g(N) = g∗(N) fur alle expandierten Knoten.

Beweis. Sei W ein optimaler Weg von S nach N und sei g(N) > g∗(N).Betrachte den Moment, in dem N expandiert wird. Da N auf einem nichtop-timalen Weg erreicht wurde, ist ein Knoten M des optimalen Weges W in derOPEN-Liste. Mit Induktion nach der Anzahl Schritte konnen wir annehmen,dass g(M) = g∗(M). Damit gilt:

f(M) = g∗(M) + h(M)≤ g∗(M) + g∗(M,N) + h(N) folgt aus Monotonie= g∗(N) + h(N)< g(N) + h(N) = f(N).

Damit musste aber M vor N expandiert worden sein. 2

Diese Aussage erlaubt es bei montonen Schatzfunktionen, den A∗-Algorithmusetwas zu vereinfachen: man braucht kein Update der optimalen Weglangein CLOSED durchzufuhren. D.h. die Baumsuch-variante des A∗-Algorithmusreicht aus.

Beispiel 2.3.16 Die Aussage bedeutet nicht, dass nicht schon Knoten des op-timalen Weges vorher in OPEN sind. Diese konnten auf einem nichtoptimalenWeg erreicht werden, werden dann aber nicht expandiert.

SN

A

B

1

1

h(A) = 4

h(B) = 5

h(S) = 5 5

4Z

1

Satz 2.3.17 Ist die Schatzfunktion h monoton, so findet der A∗-Algorithmusauch in der Baum-Variante (ohne update) den optimalen Weg zum Ziel.

KI, SS 2006, Kapitel 2, 15. Mai 2006 22

Bemerkung 2.3.18 Der Dijkstra-Algorithmus zum Finden optimaler Wege ineinem Graphen entspricht (wenn man von der Speicherung des optimalen Wegesabsieht) folgender Variante:Man wahlt h() = 0 und nimmt den A∗-Algorithmus.Dann ist h() monoton und es gelten die Aussagen fur monotone Schatzfunktio-nen.

Es gelten folgende weitere Tatsachen fur monotone Schatzfunktionen:

Aussage 2.3.19 Unter den Voraussetzungen von Aussage 2.3.15 (d.h. Mono-tonie von h) gilt:

1. Wenn N spater als M expandiert wurde, dann gilt f(N) ≥ f(M).

2. Wenn N expandiert wurde, dann gilt g∗(N) + h(N) ≤ d wobei d der opti-male Wert ist.

3. Jeder Knoten mit g∗(N) + h(N) ≤ d wird von A∗o expandiert.

Satz 2.3.20 Wenn eine monotone Schatzfunktion gegeben ist, die Schatzfunk-tion in konstanter Zeit berechnet werden kann, dann lauft der A∗-Algorithmusin Zeit O(|D|), wenn D = {N |g∗(N) + h(N) ≤ d}.Nimmt man die Verzweigungsrate c als konstant an, d als Wert des optimalenWeges und δ als der kleinste Abstand zweier Knoten, dann ist die KomplexitatO(c

dδ ).

In einem rechtwinkligen Stadtplan, in dem die Abstande zwischen zwei Kreuzun-gen alle gleich sind, gilt, dass der A∗-Algorithmus in quadratischer Zeit abhangigvon der Weglange des optimalen Weges einen Weg findet. Das liegt daran, dasses nur quadratisch viele Knoten in allen Richtungen gibt. Im allgemeinen kanndie Suche exponentiell dauern.

Beispiel 2.3.21 Die Suche eines kurzesten Weges im Stadtplan mit dem Luft-linienabstand als Schatzfunktion ist monoton: Mit ll() bezeichnen wir den Luft-linienabstand. Es gilt wegen der Dreiecksungleichung: ll(N,Z) < ll(N,N ′) +ll(N ′, Z). Da der echte Abstand stets großer als Luftlinie ist, gilt: ll(N,N ′) ≤g(N,N ′), und mit der Bezeichnung h(·) := ll(·) gilt h(N) ≤ g(N,N ′) + h(N ′).Dasselbe gilt fur das Beispiel des gitterformigen Stadtplans, bei dem man dieRechtecknorm nimmt, da auch diese die Dreiecksungleichung erfullt.

Man sieht auch, dass in einem quadratischen Stadtplan die Rechtecknorm besserinformiert ist als die Luftlinienentfernung.

Aussage 2.3.22 es gelten die Voraussetzungen in Satz 2.3.6. Seien d die Ko-sten des optimalen Weges. Seien h1, h2 zwei monotone Schatzfunktionen, sodass h2 besser informiert sei als h1.Sei A1 der A∗o-Algorithmus zu h1 und A2 sei der A∗o-Algorithmus zu h2.Dann gilt: Alle Knoten N mit g∗(N)+h2(N) ≤ d die von A2 expandiert werden,werden auch von A1 expandiert.

KI, SS 2006, Kapitel 2, 15. Mai 2006 23

Beweis. Der A∗o-Algorithmus stoppt erst, wenn er keine Knoten mehr findet,die unter der Grenze sind. Ein Knoten N wird von A1 expandiert, wenn es einenWeg von S nach N gibt, so dass fur alle Knoten M auf dem Weg die Ungleichungg∗(M) + h2(M) ≤ d gilt. Da wegen h1(M) ≤ h2(M) dann g∗(M) + h1(M) ≤ dgilt, wird der Knoten auch von A1 expandiert

2

Was macht man, wenn die Schatzfunktion nicht monoton ist? Im Fall einerunterschatzenden Funktion h gibt es eine Methode der Korrektur wahrend desAblaufs des Algorithmus.Angenommen, N hat Nachfolger N ′ und es gilt h(N) > g(N,N ′) + h(N ′).Nach Voraussetzung ist der optimale Wert eines Weges von N zum Zielknotengroßer als h(N). Wenn es einen Weg von N ′ zu einem Ziel gabe der besser alsh(N) − g(N,N ′) ist, dann hatte man einen Widerspruch zur Unterschatzung.Damit kann man h′(N ′) := h(N) − g(N,N ′) definieren. Danach gilt h(N) =g(N,N ′) + h′(N ′).

Beispiel 2.3.23

S

A

B

1

1

h(A) = 7

h(B) = 8

4

2Z

1

C D

5

h(C) =3 h(D)=4

In diesem Beispiel sieht man, dass es vorkommen kann, dass ein Knoten im nor-malen A∗-Algorithmus von OPEN nach CLOSED geschoben wird, aber danachnochmal nach OPEN bewegt wird, da man doch einen besseren Weg gefundenhat. Die Expansionsreihenfolge ist:

expandiert Nachfolger OPEN CLOSEDS A,B SA C A,B SC D B,C S,AB C B,D S,A,CC D C,D S,A,B. . .

Dies tritt beim Knoten C auf.Diese Schatzfunktion kann nicht monoton sein. Es gilt 8 = h(B) > g(B,C) +h(C) = 5.Was dieses Beispiel auch noch zeigt, ist dass der Reparaturmechanismus, derdynamisch h zu einer monotonen Schatzfunktion verbessert, das Verhalten desAlgorithmus nicht so verbessert, dass Aussage 2.3.15 gilt, denn die Aussage giltnicht fur dieses Beispiel unter der Annahme der nachtraglichen Korrektur vonh.

KI, SS 2006, Kapitel 2, 15. Mai 2006 24

2.3.3 IDA∗-Algorithmus und SMA∗-Algorithmus

Da der A∗-Algorithmus sich alle jemals besuchten Knoten merkt, wird er oft andie Speichergrenze stoßen und aufgeben. Um das zu umgehen, nimmt man eineKombination des abgeschwachten A∗-Algorithmus und des iterativen Vertiefens.Die Rolle der Grenze spielt in diesem Fall der maximale Wert d eines Weges,der schon erzeugt wurde.IDA∗ mit Grenze d:

• Ist analog zu A∗.

• es gibt keine OPEN/CLOSED-Listen, nur einen Stack mit Knoten undWegekosten.

• der Wert g(N) wird bei gerichteten Graphen nicht per Update verbessert.

• Der Knoten N wird nicht expandiert, wenn f(N) > d.

• das Minimum der Werte f(N) mit f(N) > d wird das d in der nachstenIteration.

Dieser Algorithmus benotigt nur linearen Platz in der Lange des optimalenWeges, da er nur einen Stack (Rekursions-Stack des aktuellen Weges) verwaltenmuss.Da dieser Algorithmus in einem gerichteten Graphen moglicherweise eine expo-nentielle Anzahl von Wegen absuchen muss, obwohl das beim A∗-Algorithmusdurch Update zu vermeiden ist, gibt es eine pragmatische Variante, den SMA∗-Algorithmus, der wie ein iterativer A∗-Algorithmus arbeitet, aber im Fall, dassder Speicher nicht reicht, bereits gespeicherte Knoten loscht. Der Algorithmusnutzt hierzu die verfugbare Information und loscht die Knoten, der am ehestennicht zu einem optimalen Weg beitragt. Das sind Knoten, die hohe f -Wertehaben. Es gibt weitere Optimierungen hierzu (siehe Russel-Norvig).

2.4 Suche in Spielbaumen

(siehe 2 Artikel aus Ingo Wegener(Hrsg), Highlights aus der Informatik,Springer-Verlag (1996))Ziel dieses Kapitels ist die Untersuchung von algorithmischen Methoden zum in-telligenten Beherrschen eines strategischen Zweipersonenspiels, wie z.B. Schach,Dame, Muhle, Go, Tictactoe, bei dem der Zufall keine Rolle spielt.Spiele mit mehr als zwei Personen sind auch interessant, aber erfordern andereMethoden und werden hier nicht behandelt.Zum Schachspiel existierten bereits vor Benutzung von Computern Schach-theorien, Untersuchungen zu Gewinnstrategien in bestimmten Spielsituationen(Eroffnungen, Endspiel, usw) und zum Bewerten von Spielsituationen. Mittler-weile gibt es zahlreiche Varianten von recht passabel spielenden Schachprogram-men, und auch einige sehr spielstarke Programme.Es gibt zwei verschiedene Ansatze, ein Programm zum Schachspielen zu konzi-pieren:

KI, SS 2006, Kapitel 2, 15. Mai 2006 25

1. Man baut auf den bekannten Schachtheorien und Begriffen auf, wie Ver-teidigung, Angriff, Bedrohung, Decken, Mittelfeld, . . . , und versucht diemenschliche Methode zu programmieren.

2. Man versucht mit reiner Absuche aller Moglichkeiten unter Ausnutzungder Geschwindigkeit eines Computers, einen guten nachsten Zug zu finden.

Betrachtet man heutige, erfolgreiche Schachprogramme, dann ist die wesentli-che Methode das Absuchen der Varianten, wobei auf einer (einfachen) stati-schen Bewertung von Spielsituationen aufgebaut wird. Erganzend dazu wird ei-ne Eroffnungsbibliothek verwendet und Endspielvarianten werden getrennt pro-grammiert. Die Programmierung der meisten Schachtheorien scheitert daran,dass sie nicht auf Computer ubertragbar sind, da die Begriffe unscharf definiertsind.SpielbaumEs gibt zwei Spieler, die gegeneinander spielen (Maximierer und Minimierer).Der Spielbaum besteht aus Spielsituationen (dargestellt in einer Datenstruk-tur), und der Angabe, welcher Spieler am Zug ist.

• Die Wurzel ist die Anfangssituation

• Die Sohne einer Spielsituation sind genau die nach einem Zug moglichennachsten Spielsituationen.

• Es gibt Endsituationen (Gewinn, Verlust).Teilweise wird die Endsituation auch nach den bisher ausgefuhrten Zugendefiniert.

• Gewinnwert der Endsituation. Das ist normalerweise eine ganze Zahl.Schach: Gewinn (+1), Remis (0), Verlust (-1)Go: Differenz der Anzahl der besetzten Felder.

Ziel: Finden einer Gewinnstrategie.D.h. zu jeder Spielsituation soll der optimale Zug gefunden werden.Als Sprechweise kann man verwenden, dass man einen einzelnen Zug Halbzugnennt; ein Zug ist dann eine Folge von zwei Halbzugen.Fur die betrachteten Spiele ist die Menge der Spielsituationen endlich, alsokann man im Prinzip auch herausfinden, welche Spielsituationen bei optimalerSpielweise zum Verlust, Gewinn bzw. Remis fuhren.

Wenn man Spiele hat, die zyklische Zugfolgen erlauben, bzw. wie im Schach beidreifach sich wiederholender Stellung (bei gleichem Spieler am Zug) die Stellungals Remis werten, dann ist obige Minimax-Prozedur noch etwas zu erweitern.Das praktische Problem ist jedoch, dass ein vollstandiges Ausprobieren allerZuge und die Berechnung des Minimax-wertes i.a. nicht machbar ist.Selbst bei TicTacToe gibt es schon: 9! = 362880 mogliche Zugfolgen, was aufeinem Computer gerade noch machbar ist.

KI, SS 2006, Kapitel 2, 15. Mai 2006 26

Die Suche im Spielbaum der Abspielvarianten mit einer Bewertungsfunktionwurde schon von den Pionieren der Informatik vorgeschlagen (von Shannon,Turing; siehe auch die Ubersicht in Russel und Norvig). Dies nennt man dieMinimax-Methode.

Prozedur Minimax (Zustand, Spieler)Erzeuge NF = alle Nachfolgezustande zu (Zustand, Spieler)Wenn NF = ∅, return: Wert(Zustand).Sonst: Wenn Spieler == Maximierer,

return: max{Minimax(Z, Spieler) | Z ∈ NF}Sonst: Wenn Spieler == Minimierer,

return: min{Minimax(Z, Spieler) | Z ∈ NF}

Wobei Spieler den jeweils anderen Spieler bedeuten soll.

Um aus einer gegebenen Situation heraus den besten Zug zu finden, wird z.B.bei k Zugen Vorausschau der zugehorige Baum der Moglichkeiten erzeugt,die Blatter werden bewertet. Danach geht man von unten nach oben vor undbewertet innerhalb der direkten Nachfolger eines Knotens: Man minimiertuber die Situationen nach Zug des Gegners und maximiert uber die eigenenZugmoglichkeiten. Die Zugmoglichkeit, mit dem optimalen Wert ist dann derberechnete Zug.

Im Prinzip kann man damit bei allen solchen Spielen, wenn es eine obere Schran-ke fur die Anzahl der Zuge gibt, in endlicher Zeit ermitteln, ob es eine Gewinn-strategie gibt, indem man eine Vorausschau macht, die tief genug ist. Diese gibtauch fur alle Spielsituationen deren exakten erreichbaren Gewinnwert an.Da man das fur kein interessantes Spiel machen kann, braucht man heuristischeBewertungsfunktionen, die man als Ersatz fur den exakten Gewinnwert verwen-den kann. Man kann auf Basis heuristische Bewertungsfunktion ebenfalls dasMinimax-Verfahren anwenden, um den besten Zug zu finden.Im nachsten Paragraphen wird eine (exakte) Verbesserung der Minimax-Suchevorgestellt, die man Alpha-Beta-Suche nennt. Diese arbeitet mit zwei Parame-tern, die ein Suchfenster darstellen.Die Alpha-Beta-Suche kann man sowohl zur Beschleunigung des normalenMinimax-Verfahrens verwenden als auch fur das Minimax-Verfahren bzgl. ei-ner heuristischen Bewertungen.

Um die Methode des Spielbaumsuchens zu verwenden, ist notwendig:

Eine algorithmische Bewertung von Spielsituationen.

Schach: Materialvorteil, evtl. Stellungsvorteil, Gewinnsituation, ...

Muhle: Material, #Muhlen, Bewegungsfreiheit, . . .

KI, SS 2006, Kapitel 2, 15. Mai 2006 27

Tictactoe: am einfachsten: Gewinn = 1, Verlust = -1, Remis = 0nur eindeutige Spielsituationen werden direkt bewertet.Rein theoretisch reicht diese Bewertung bei allen diesen Spielen aus.

Minimax-Methode

• Der Spielbaum wird bis zur Tiefe d expandiert

• die Blatter werden direkt bewertet

• uber eigene Zugmoglichkeit wird maximiert

• uber Zugmoglichkeiten des Gegners wird minimiert.

Dies ergibt eine Bewertung der aktuellen Spielsituation, indem man d Zugevorausberechnet. Damit kann man eine Bewertung aller nachsten moglichenZuge erhalten, und den besten raussuchen.

Es gilt in Spielen ohne Zufallsanteil: Die Berechnung des besten Zu-ges ist unabhangig von den exakten Werten der Bewertungsfunktion;es kommt nur auf die erzeugte Ordnung zwischen den Spielsituatio-nen an.

Beispiel 2.4.1 Tictactoe. Man hat ein 3× 3 Raster. Der Spieler darf pro Zugein Kreuz in ein Feld machen, der Gegner jeweils einen Kreis. Die Spieler sindabwechselnd an der Reihe. Gewonnen hat, wer zuerst eine Zeile, Spalte oderDiagonale ganz mit seinen Zeichen gefullt hat.

Die einfachste Bewertung ist:1 Gewinn: es gibt drei X in einer Reihe, Spalte oder Diagonale0 In jeder Zeile, Spalte oder Diagonale befinden sich ein X und ein O-1 Verlust: es gibt drei O in einer Reihe, Spalte oder Diagonale

Hierbei braucht man die Sonderfalle, dass es sowohl eine Dreier-Reihe mit X’enals auch eine mit drei O’s gibt, nicht zu beachten, da diese im Spiel nicht vor-kommen konnen.Eine kompliziertere Bewertung ist:

(#einfach x-besetzte Zeilen/Spalten/Diag) * 1+ (# doppelt x-besetzte Zeilen/Spalten/Diag) * 5+ (20, falls Gewinnsituation)- (#einfach o-besetzte Zeilen/Spalten/Diag) * 1- (# doppelt o-besetzte Zeilen/Spalten/Diag) * 5- (20, falls Verlustsituation)

Die aktuelle Spielsituation seiX---O-O-X

. Die nachsten Spielsituationen zusammen

mit den Bewertungen, wenn X-Spieler dran ist, sind:

KI, SS 2006, Kapitel 2, 15. Mai 2006 28

XX--O-O-X

X-X-O-O-X

X--XO-O-X

X---OXO-X

X---O-OXX

0 8 −3 1 −3

Die Weiterfuhrung der ersten Situation nach moglichen Zugen von O-Spielerergibt:

XXO-O-O-X

XX-OO-O-X

XX--OOO-X

XX--O-OOX

−20 0 0 1

Uber diese ist zu minimieren, so dass sich hier ein Wert von −20 ergibt.In der ersten Ebene, nach der ersten Zugmoglichkeit von X, ist zu maximieren.Der erste Zug tragt −20 dazu bei.

Die Programmdatei zu diesem Skript enthalt ein Haskell-Programm, das zureinfachen Bewertung +1, 0,−1 eine Berechnung des nachsten Gewinnzuges bzw.falls es keinen solchen gibt, den Zug ausrechnet, der zum Remis fuhrt, oderaufgibt. Dieses Programm findet in annehmbarer Zeit jeweils den besten Zug,und erkennt auch, dass es keinen garantierten Gewinn fur den X-Spieler oderO-Spieler am Anfang gibt. Z.B.

*Main> nzug ’X’ "XBBBBOBBB""Siegzug Feld: 3"*Main> nzug ’X’ "XBBBBBOBB""Siegzug Feld: 2"*Main> nzug ’X’ "XBBBBBBOB""Siegzug Feld: 3"*Main> nzug ’X’ "XBBBBBBBO"

Man konnte die Bewertung verbessern, wenn man beachtet, wer am Zug ist,allerdings ergibt sich der gleiche Effekt, wenn man einen Zug weiter sucht undbewertet.Praktisch erwunschte Eigenschaften der Bewertungsfunktion sind:

• hoher Wert ≡ hohe Wahrscheinlichkeit zu gewinnen

• schnell zu berechnen

Dies verdeckt manchmal den Weg zum Sieg. z.B. im Schach: Ein Damenopfer,das zum Gewinn fuhrt, wurde zwischenzeitlich die Bewertung bzgl. Materialverringern.

KI, SS 2006, Kapitel 2, 15. Mai 2006 29

2.4.1 Alpha-Beta Suche

Die Alpha-Beta Suche geht rekursiv vor, und benutzt ein Suchfenster [α, β], umredundante Suchzweige abzuschneiden. Zur Terminierung verwendet sie eineTiefenschranke.

1. Starte mit alpha = −∞ und beta = ∞

2. Wenn Tiefenschranke erreicht, bewerte die Situation.

3. Wenn minimiert werden soll:UNTIL: alle Sohne abgearbeitet oder alpha ≥ beta.

Wende Alpha-Beta auf Sohn an mit aktuellen alpha, beta-Werten.wobei die Prozedur rekursiv und zum Maximieren aufgerufen wird.Dies ergibt einen Wert w.beta := min(beta, w)

RETURN beta

4. Wenn maximiert werden soll:UNTIL: alle Sohne abgearbeitet oder alpha ≥ beta

Wende Alpha-Beta auf Sohn an mit aktuellen alpha, beta-Werten.wobei die Prozedur rekursiv und zum Minimieren aufgerufen wird.Dies ergibt einen Wert w.alpha := max(alpha, w)

RETURN alpha

Beispiel 2.4.2 Spielbaum, bei dem an der Wurzel der Minimierer am Zug ist.(Innerhalb eines großeren Spielbaumes ist dann uber die Geschwister der Wurzelzu maximieren)

2 4 -1 6 1 0

Max

Min

Max

a

b c

Die Prozedur steigt rekursiv links den Baum herab, bisin Ebene 3 maximiert wird, es ergibt sich 4 als Maximum.

KI, SS 2006, Kapitel 2, 15. Mai 2006 30

In Ebene 2 ergibt sich β = 4, α = −∞.Mit diesen Werten wird der zweite Teilbaum bewertet.In Ebene 3 ergibt sich jetzt beim ersten Knoten:β = 4, α = 6, und es kann abgebrochen werden, Wert = 6In Ebene 2 ergibt sich kein neuer Wert, da minimiert wird.es wird 4 an die Wurzel zuruckgegeben.

Die Alpha-Beta-Prozedur kann bei geeignetem Suchfenster auf jeder Ebene dieSuche abbrechen, es muss nicht jeder innere Konten untersucht werden!.Eine genaue Analyse ergibt, dass die Wirkung des Alpha-Beta-Verfahrens (imMittel) den Exponenten halbiert, d.h. die Suchtiefe wird bei gleichem Ressour-cenbedarf um das doppelte gesteigert. Damit wird auch die Spielstarke einesentsprechenden Programms gesteigert, denn tiefere Suche fuhrt zur Verbesse-rung der Spielstarke.Die Gute der Alpha-Beta-Suche ist stark abhangig von der Reihenfolge der un-tersuchten Knoten (Stellungen im Schach). Wenn man Hinweise hat, welcheStellungen beim Maximieren besonders gut sind, dann sollten diese zuerst ex-pandiert werden, entsprechend sollten beim Minimieren die besten Zuge desGegners zuerst untersucht werden (Vorsortieren ). In dem Fall hat die Sucheeine sehr große Chance, Teilbaume abzuschneiden.Wichtige Optimierungen, die z.B. beim Schach vorgenommen werden, sind dieSpeicherung bereits bewerteter Stellungen, um bei Zugvertauschungen nicht zu-viele Stellungen mehrfach zu bewerten. Damit kann man die Vorsortierung vonZugen unterstutzen.

Auftretende Probleme bei der Suche:

• Tiefere Suche kann in seltenen Fallen zur schlechteren Zugauswahl fuhren.Dies tritt mit immer geringerer Wahrscheinlichkeit ein, falls man eine guteBewertungsfunktion hat

• Horizont-Effekt: (z.B. durch Schach bieten gerat ein wichtiger Zug außer-halb des Suchhorizonts)

Tiefere Suche bei besonders gutem Zug (singular extension)

Um den Horizont-Effekt in der Hauptvariante auszuschalten, kann man denHorizont unter gewissen Bedingungen erweitern.Idee: falls bei Suche mit Tiefe d ein einzelner Zug k0 besonders auffallt(d.h. gut beim Maximierer und schlecht beim Minimierer)Wenn vd(k0) > vd(k) + S fur alle Bruder k 6= k0 und fur feste, vorgegebeneSchranke S, wobei vd die Bewertung bei Suchtiefe d bezeichnet; Dann wirddieser Zug eine Tiefe weiter untersucht. Die tiefere Suche ist auch sinnvoll beiZugzwang, d.h. wenn nur ein weiterer Zug moglich ist.Im Falle des Zugzwangs vergroßert das den Suchraum nicht, aber erhoht dieVorausschau

KI, SS 2006, Kapitel 2, 15. Mai 2006 31

Die Implementierung dieser Idee ist eine wichtige Erweiterung der Suchmetho-den in Programmen zu strategischen Spielen.Folgendes Vorgehen ist ublich: es gibt mehrere Durchgange:

1. normale Bewertung

2. Erkennen aller besonderen Zuge:

3. Alle auffallenden Zuge durfen um 1 weiter expandieren.

Effekte:

• Die Suche kann instabil werden:ob ein Zug auf Ebene n als interessant auffallt, kann davon abhangen, wietief die Suche unterhalb dieses Knotens im Baum ist.

• Der Suchraum kann beliebig wachsen, falls man mehrere Durchgangemacht: jeweils ein anderer Knoten wird als wichtig erkannt.

• Durch die tiefere Suche kann ein guter Zug wieder schlechter bewertetwerden.

2.4.2 Spiele mit Zufallsereignissen

Auch in der Suche nach einer guten Strategie bei strategischen Spielen, bei denender Zufall eine Rolle spielt, kann man die Minimax-Suche in einer allgemeinerenForm verwenden.Z.B. beim Backgammon besteht ein Spielzug darin, zunachst mit zwei Wurfelnzu wurfeln und dann zu ziehen, wobei man bei der Zugwahl selbst entscheidenkann, welche Steine zu ziehen sind. Da der Gegner auch wurfelt und erst danneine Entscheidungsmoglichkeit fur seinen Zug hat, das gleiche aber auch furweitere eigene Zuge gilt, hat man keinen festen Baum der Zugmoglichkeiten.Man konnte einen Zug des Gegners vorausschauend uber alle seine Wurfel- undZugmoglichkeiten minimieren, aber sinnvoller erscheint es, uber die bekannteWahrscheinlichkeit zu argumentieren und den Erwartungswert des Gegners zuminimieren und den eigenen Erwartungswert zu maximieren.

Es gilt: Wenn Wahrscheinlichkeit eine Rolle spielt, dann ist die Be-rechnung des Zuges mit dem besten Erwartungswert abhangig vonden exakten Werten der Bewertungsfunktion; nicht nur von der re-lativen Ordnung auf den Situationen.

Als Beispiel, wobei die Wahrscheinlichkeiten 0, 7 und 0, 3 und 0, 1 und 0, 9 sind,und die Bewertungen der Situation A mit moglichen Situation A1, A2 und Bmit moglichen Situation B1, B2 seien ϕ1(A1) = 1, ϕ1(A2) = 20 und ϕ1(B1) =2, ϕ1(B2) = 8; bei der zweiten Bewertungsfunktion bleibe die Bewertung vonA1, A2 gleich und ϕ1(B1) = 3, ϕ1(B2) = 6.

KI, SS 2006, Kapitel 2, 15. Mai 2006 32

20

O

BA

A1 A2 B1 B2

0,7 0,3 0,1 0,9p =

1 20 2 8

3 61Dies erhalt die relative Ordnung der Situationen. Aber die Erwartungswerteverschieben sich:

A B0.7 ∗ 1 + 0.3 ∗ 20 < 0.1 ∗ 2 + 0.9 ∗ 8

0.7 ∗ 1 + 0.3 ∗ 20 > 0.1 ∗ 3 + 0.9 ∗ 6

Damit ist einmal der linke, einmal der rechte Erwartungswert großer. D.h. ein-mal ist B, einmal A zu bevorzugen.D.h., die Bewertungsfunktion muss auch von den Werten her vorsichtig definiertwerden. Beim Backgammon ware die richtige Intuition: die Anzahl der benotig-ten Zuge bis alle Steine das Ziel erreicht haben. Diese ist aber vermutlich schwerzu schatzen, da der Spielbaum viel zu groß ist.

KI, SS 2006, Kapitel 2, 15. Mai 2006 33

B würfelt

B zieht

A zieht

A würfelt

Maximum

E

A ziehtBewertungen

Maximum

E

Minimum

p1 p2 p3

Bei Vorausschau mit Tiefe 2 wird der Baum der Moglichkeiten aufgebaut. DieBlatter werden bewertet. Im Bild sind es die Situationen nach einem Zug vonA. Man maximiert uber die Geschwisterknoten und erhalt den besten Zug. Imnachsten Schritt nach oben berechnet man den Erwartungswert fur den Wertdes besten Zuges. Geht man weiter nach oben, ist das gleiche zu tun fur geg-nerische Zuge und Wurfeln, wobei man minimieren muss. An der Wurzel istdas Wurfelergebnis bekannt, so dass man als besten Zug denjenigen mit demhochsten Erwartungswert ermittelt.Hat man eine gute Bewertungsfunktion, dann kann man die Minimax-Sucheverbessern durch eine Variante der Alpha-Beta-Suche. Diese Optimierung spieltallerdings in der Praxis keine so große Rolle wie in deterministischen Spielen,da der Spielbaum i.a. viel zu groß ist, um mehrere Zuge voraus zu schauen.