|
Startseite zurück Inhaltsverzeichnis weiter
Kapitel
2 Suche
Kommen Sie Bert hier entlang!
Glauben Sie das ist der richtige Weg?
Sicher vertrauen Sie mir, es ist jetzt ganz nah.
Woher wollen Sie das wissen. Lassen Sie uns umkehren und einen anderen
Weg versuchen.
Nein, wir kommen dem Ziel doch immer näher. Lassen Sie uns einfach in
diese Richtung weiterlaufen.
Neinnein, wir hätten doch schon viel früher woanders abbiegen
müssen.
Nun stellen Sie sich nicht so an. Nun sind Sie schon bis hierher
mitgelaufen, nun stehen Sie das bitte auch bis zum Ende durch.
Daß Sie aber auch immer erstmal losstürmen müssen. Wir sind an sovielen
Abbiegungen vorbeigekommen, wieso sind wir gerade hier lag gelaufen. Außerdem
glaube ich, wir entfernen uns immer weiter vom Ziel.
Der Weg ist
Jetzt hören Sie mir bloß mit Platitüden auf. Ich frag jetzt jemanden, wie
weit es noch ist.
~Und?
Die Frau sagt, Sie weiß es nicht genau. Aber die Richtung stimmt auf
jedem Fall.
Sag ich doch, das ist bestimmt gleich um die Ecke.
Das konnte die Frau mir nicht bestätigen.
Das es aber auch so viele Straßen hier geben muß?
Dabei waren doch an jeder Kreutung maximal vier. Sie viele können es doch
nun auch nicht sein.
Ach, was wissen wir schon. Nun Laufen wir halt weiter.
Mir tun die Füße weh.
Und mir der Kopf.
2.1 Modellierung von Problemen als Suche
In diesem Kapitel wollen wir uns mit einer bestimmten Art eines rationalen
Agenten beschäftigen, eines problemlösenden Agenten. Als Leistungsbewertung
dieses Agenten geht es darum ein bestimmtes Ziel zu erreichen. Es geht um einem
Zielzustand, der aus einem aktuellen Zustand durch die Anwenung einer Folge
von Aktionen erreicht wird. Die Abfolge von Aktionen, die zum Zielzustand
führt, ist die Lösung des Problems. Wir gehen davon aus, daß es sich dabei um
ein statisches, komplett erfassbares, diskretes und deterministisches
Problemfeld handelt. Das zu lösende Problem läßt sich durch die folgenden vier
Komponenten beschreiben:
- der Ausgangszustand: dieses ist der Zustand der Umgebung, den der
Agent zum Start vorfindet.
- eine Nachfolgefunktion: diese Funktion beschreibt für jeden
Zustand alle möglichen auf diesen Zustand durch den Agenten anwendbare
Aktionen und deren Ergebniszustände.
- Zieltest: eine Testfunktion, die genau für die Zielzustände wahr
zurückgibt.
- Pfadkosten: eine Kostenfunktion, die angibt, wieviel eine
bestimmte Aktion den Agenten kostet. Diese Funktion summiert sich für eine
Folge von Aktionen auf.
Gesucht wird eine Folge von Aktionen, die ausgeführt auf den Ausgangszustand
zu einem Zielzustand führt. Die Lösung soll in dem Sinne optimal sein, daß
die Kosten jeder anderen Lösung größer oder gleich der Kosten der gefundenen
Lösung ist.
Wie der versierte Informatiker sieht, läßt sich ein solches Problem als ein
Baum modellieren. Die Knoten des Baumes sind mit jeweils einem Zustand
markiert. Der Wurzelknoten mit dem Ausgangszustand. Die Kinder eines Knotens
werden durch die Nachfolgefunktion bestimmt. Jede Kante des Baums entspricht
einer Aktion. Jeder Pfad im Baum bedingt bestimmte Kosten, nämlich die Kosten
der Aktionenfolge, die diesem Pfad entspricht. Für einen problemlösenden
Agenten geht es also darum, in diesem Baum einen Pfad von der Wurzel zu einem
Zielzustandsknoten zu finden. Eine solche Lösung ist optimal, wenn es keine
andere Lösung zu einem Zielzustand gibt, die weniger Kosten trägt.
Nun dürfte klar sein, wie ein problemlösender Agent durch Suche zu seiner
Lösung kommt. Er muß einfach nur den Baum durchlaufen, bis er einen
Zielzustand gefunden hat. Gut, wenn wir in den ersten drei Semestern einiges
über Bäume gelernt haben.
2.2 Uninformierte Suchstrategien
In diesen Abschnitt werden wir in einem Suchbaum nach Lösungen für ein Problem
suchen, ohne problemspezifische Information zu nutzen. Daher spricht man auch von
uninformierter Suche. Es ist nicht bekannt, wie weit die Lösung von einem
gegebenen Zustand zu einen Zielzustand entfernt sein könnte.
Der Einfachheit halber werden wir zumeist annehmen, daß jede Aktion gleich
viel Kosten verursacht. Die Gesammtkosten eines Pfades errechnen sich somit
aus seiner Länge.
2.2.1 allgemeiner Suchalgorithmus
In seiner allgemeinsten Form wird bei einer Suche ein Suchbaum expandiert. Es
wird ein Blatt ausgewählt und um die Folgezustände expandiert. Verschiedene
Suchstrategien unterscheiden sich dann darin, welches Blatt jeweils als
nächstes zum expandieren gewählt wird.
Wir können informell den allgemeinen Suchalgorithmus beschreiben:
Verwalte eine Liste von noch zu expandierenden Zuständen, den fringe.
Zu jedem Zustand im fringe sei zusätzlich der Pfad von Aktionen, mit
denen der Zustand vom Ausgangszustand erreicht wurde, markiert.
Der fringe ist als einelementige Liste mit dem Ausgangszustand und
der leeren Aktionsfolge zu initialisieren.
Solange der fringe nicht leer ist, und das
erste fringe-Element nicht der Zielzustand ist, verfahre wie folgt:
Nimm das erste Elements aus dem fringe, berechne dessen
Nachfolger und füge diese im fringe ein.
Der Algorithmus ist allgemein gehalten, da er nichts darüber sagt, an welcher
Stelle die neuen Elemente in den fringe eingefügt werden sollen. Der
Algorithmus nimmt sich immer das erste Element aus dieser Liste zum
expandieren. Jetzt ist entscheidend, wo und wie und eventuell auch ob überhaupt
alle neuen Elemente in den fringe eingefügt wurden:
am Anfang, irgendwo in der Mitte, oder am Ende. Je nachdem, nach welcher
Strategie die Elemente eingefügt wurden, ergibt sich eine unterschiedliche
Suchstrategie.
Implementierung
Es sei im Folgenden ein allgemeine Klasse zum expandieren eines Suchbaums in
Scala implementiert.
Wir sehen eine abstrakte Klasse vor, die einen Suchbaum repräsentiert. Diese
Klasse sei generisch über den Typ eines Zuges gehalten. Hierzu sei die
Typvariabel M (für move) gewählt. M repräsentiert
den Typ, der einen möglichen Zug zu einen Folgezustand auswählt. Das kann bei
verschiedenen Problemen jeweils etwas ganz anderes sein.
Die Klasse enthalte eine Methode, die der Nachfolgefunktion entspricht. Sie
gibt die Liste alle möglichen Züge auf den aktuellen Zustand zurück. So lange
wir kein konkretes Suchproblem haben, ist diese Methode natürlich abstrakt und
für entsprechende Probleme erst noch zu implementieren.
Desweiteren sei eine Methode vorgesehen, die prüft, ob es sich um einen
Zielzustand handelt.
Die nächste Methode gibt für eine Aktion einen Nachfolgezustand zurück. Es
wird dabei ein neuer Baumknoten erzeugt, der aus den aktuellen Knoten
entsteht, wenn ein bestimmter Zug (Aktion) ausgeführt wird.
Die Mehtode bisher waren alle abstrakt.
Wir können schon einmal eine einfache konkrete Methode implementieren, die
testet, ob ein bestimmter Zug in diesem Zustand ausführbar ist, eine Aktion
also anwendbar ist. Dazu wird einfach getestet, ob der Zug in der Liste der
mögliche Aktionen enthalten ist:
Es bleibt die eigentliche Suche zu implementieren. Für die Suche ist jeweils
ein Blatt auszuwählen, das expandiert werden soll.
Hierzu ist eine Hilfsliste notwendig, in der jeweils alle Blätter des
Suchbaumes aufgelistet sind.
Wir werden in dieser Hilfsliste nicht nur die Blätter des Suchbaums speichern,
sondern auch die Folge von Aktionen, die von der Wurzel des Baumes zu diesem
Blatt führte. Dieses beiden Informationen seien in einem Paar-Objekt
zusammengefasst. Der einfachen Lesbarbeit halber wird ein
TypsynonymTypsynonyme sind in C als typedef bekannt. Java
kennt ein vergleichbares Konstrukt leider noch nicht. für den Typ
des Paares einer Liste von Aktion und einem Baumknoten eingeführt.
Es folgt der eigentliche Algorithmus. Übergeben wird eine Einfügefunktion,
die eine Liste von Zuständen mit Pfaden weitere solche Zustände einfügt.
Diese Funktion ist die eigentliche Suchstrategie, über die gesteuert wird,
welches Blatt als nächstes exandiert wird. Für diesen Funktionstyp sei auch
entsprechend ein Name eingeführt:
Das Ergebnis einer Suche, soll die Liste der Aktionen sein, die von der Wurzel
zu einem Zielzustand führen.
Damit erhalten wir folgende Signatur für den allgemeinen
Suchalgorithmus:
Es sei eine Variabel für die noch zu untersuchenden
Teilpfade deklariert, also der noch nicht expandierten Bätter.
Sie repräsentiert den fringe, wie er im allgemeinen Suchalgorithmus
beschrieben wurde. Sie wird mit der einelementigen Liste, die den
Ausgangszustand des Problems enthält, initialisiert.
Ein Variabel sei für die Ergebnisliste vorgesehen. Sie wird
mit null initialisiert. Ein Gesamtergebnis null der Methode
signalisiere, daß kein Pfad zu einem Zielzustand gefunden wurde:
Der eigentliche Algorithmus läßt sich in einer while-Schleife formulieren:
solange noch kein Ergebnis erzielt wurde und weitere Knoten zu besuchen sind,
selektiere den nächsten zu untersuchenden Knoten und teste, ob es sich um
einen Zielzustand handelt; ansonsten lösche man den Knoten aus den noch zu
besuchenden Teilpfaden und hängt sein Nachfolgeknoten mit der übergebenen
Einfügefunktion in die noch zu behandelnen Blätter ein.
| SearchTree.scala |
while (!fringe.isEmpty && result==null){
val Pair(ms,headState) :: fringeTail = fringe
if (headState.terminalState()) result=ms.reverse
else{
val headsChildren
= for (val m<-headState.moves())
yield Pair(m::ms,headState.move(m))
fringe= insertNew(fringeTail,headsChildren)
}
}
result //is no longer null, or no solution is available
}
|
Das ist schon die gesammte Implementierung. Die
Methode generalSearch ist jeweils mit einer entsprechenden
Einfügefunktion als Parameter aufzurufen, um eine konkrete Suchstrategie zu erhalten.
2.2.2 Breitensuche
Die klassische einfache Form der Suche ist die Breitensuche, in der der Baum
ebenenweise Durchlaufen wird. Sofern ein Zustand stets eine endliche Anzahl
von Nachfolgerknoten enthält, ist damit sichergestellt, daß jeder erreichbare
Zustand nach endlicher Zeit erreicht wird. Das ebenenweise Durchlaufen eines
Baumes wird mitunter auch als military-order bezeichnet.
Wenn jede Aktion gleich teuer ist, so sind die Kosten einen Pfades vom
Ausgangszustand zu einem Zustand im Suchbaum stets nur die Länge des
Pfades. Um eine optimale Lösung zu finden, suchen wir einen Zielzustand
möglichst weit oben im Baum; möglichst nah an der Wurzel. Da die Breitensuche
ebenenweise durch den Baum läuft, als Knoten näher Wurzel früher betrachtet,
findet die Breitensuche eine optimale Lösung.
Die Breitensuche läßt sich aus dem allgemeinen Suchalgorithmus erhalten, indem
die neuen Knoten, die ja eine Ebene Tiefer im Baum zu finden sind, als der
gerade expandierte Knoten, ans Ende des fringe eingefügt werden.
Dann ist der frimge immer so sortiert, daß zustände, die weiter oben
im Baum steen, auch weiter vorne im fringe zu finden sind, und damit
durch den allgemeinen Suchalgorithmus früher berücksihctigt werden.
Implementierung
Implementieren wir also die Breitensuche in Scala. Da wir eine Funktion zur
allgemeinen Suche implementiert haben, brauchen wir nur die entsprechende
Selektionsfunktion und Einfügefunktion zu übergeben.
Als Einfügefunktion werden wir beim expandieren die neuen Blätter an
die Liste der offenen Blätter stets hinten anhängen. Somit ist das vorderste Blatt
das älteste und daher für die Breitensuche als nächstes zu expandieren.
Diese Einfügefunktion braucht nun der allgemeinen Suche nur als Parameter
übergeben zu werden. Scala hat die schöne Eingenschaft, die erstmals in der
KI-Programmiersprache Lisp umgesetzt war, anonyme Funktionen schreiben zu
können. Mit diesem programmiersprachlichen Konstrukt, läßt sich die
Breitensuche in einer Zeile schreiben.
Damit haben wir die Breitensuche implementiert. Jetzt kommt es darauf an
sie auf ein konkretes Problem anzuwenden, um den ersten problemlösenden
Agenten zu implementieren.
Schiebepuzzle
Unser erstes zu lösende Problem sei ein als Spielzeug Samuel Loyd ($\ast$ 30. Januar 1841
in Philadelphia, Pennsylvania, USA; $\dagger$ 10. April 1911 in New York) war
Amerikas berühmtester Spiele-Erfinder und Rätselspezialist.
Loyd war ein guter Schachspieler und nahm u. a. am internationalen Turnier
anlässlich der Weltausstellung in Paris 1867 teil. Doch machte er sich einen
bleibenden Namen vor allem als Komponist von Schachproblemen, die er in
Fachzeitschriften veröffentlichte. Gelegentlich benutzte er die Pseudonyme
W. King, A. Knight und K.W. Bishop.
Nach 1870 verlor er allmählich das Interesse am Schachspiel und widmete sich
von nun an dem Erfinden mathematischer Denkspiele und origineller
Werbegeschenke. Eins seiner berühmtesten Rätsel ist das
14/15-Puzzle. bekanntes
Schiebepuzzle. Diese Art von Puzzle waren bereits im 19.~Jahrhundert sehr
populär. Der Mathematiker Loyd hat damals eine unlösbare Variante des Puzzles
auf den Markt gebracht.
Bei dem 14/15-Puzzle handelt es sich um eine Schöpfung des
amerikanischen Rätselspezialisten Sam Loyd.
In einem quadratischen Rahmen der Größe 4×4 liegen 15 Steine, die von 1 bis 15
durchnummeriert sind. In der Ausgangsposition sind die Steine mit Ausnahme der
Steine 14 und 15 in aufsteigender Reihenfolge sortiert, das letzte Feld bleibt
frei. Dadurch ergibt sich folgendes Bild:
Die Aufgabe besteht nun darin, die Steine durch eine Folge von Zügen in die richtige Reihenfolge zu bringen:
Erlaubt sind nur solche Züge, bei denen ein Stein, der horizontal oder
vertikal direkt neben dem freien Feld liegt, auf dieses verschoben wird. Sam
Loyd setzte ein Preisgeld von 1000 Dollar für die erste richtige Lösung aus,
wohl wissend, dass das Problem unlösbar ist. Der Beweis basiert auf der
Tatsache, dass bei erlaubten Zügen die Parität von N = N_1 + N_2 erhalten bleibt
(das heißt, wenn N vor dem Zug (un)gerade war, ist es das auch nach dem
Zug). Dabei ist N_1 die Anzahl der Zahlenpaare, die sich in falscher
Reihenfolge befinden und N_2 die Nummer der Reihe, in der sich das leere Feld
befindet.
Es geht bei dem Spiel um 8 durchnummerierte Quadrate, die sich auf
einem quadratischen Spielfeld mit drei mal drei Feldern befinden, so daß also
immer genau ein Feld frei ist. Als mögliche Spielzüge können die Quadrate, die
in einem zum freien Feld benachbarten Feld liegen, in das freie Feld geschoben
werden. Ziel ist es die Quadrate so hin- und herzuschieben, bis ein Zustand
erreicht wird, in dem von links nach rechts, von oben nach unten die Ziffern
aufsteigend zu liegen gekommen sind.
Was sind hier die möglichen Aktionen? Es gibt maximal vier verschiedene
Aktionen: ein Plättchen nach oben, unten, links, rechts zu verschieben. Das
ist allerdings nur möglich, wenn das freie Feld genau in der Mitte liegt. Bei
freiem Randfeld sind es nur noch drei mögliche Aktionen, bei freiem Eckfeld
nur noch zwei. Abbildung zeigt das kleine GUI für das
Schiebepuzzle, wie es im Anhang des Skriptes implementiert ist.
In Scala schreiben wir folgende Definition um die vier Richtungen zu
modellieren:
| Direction.scala |
package name.panitz.ki
object Direction extends Enumeration("up","down","left","right") {
final val Up, Down, Left, Right = Value}
|
In Scala können auf diese Weise Aufzählungstypen erzeugt werden. Der
eigentliche Aufzählungstyp ist dann: Direction.Value.
Modellieren wir jetzt den Spielzustand des Schiebespiels. Ein
Schiebespielproblem ist ein Suchbaum, mit Objekten der
Klasse Direction.Value als Aktionen. Extsprechend wird
also SearchTree mit entsprechenden konkreten Typ für die Typvariabel
erweitert.
| SlidePuzzle.scala |
package name.panitz.ki
case class SlidePuzzle(val SIZE:Int)
extends SearchTree[Direction.Value] {
|
Der Parameter SIZE der Klasse SlidePuzzle, der im
konstruktor zu übergeben ist, repräsentiert die Kantenlänge und ist fortan
eine Konstante für eine Instanz.
Wir sehen zwei Variablen vor, die Zeile und Spalte des freien Feldes direkt angeben.
Der Gesamtzustand des Spiels sein natürlich in einer zweidimensionalen Reihung
gespeichert, die mit einem Finalzustand initialisiert wird (die
Initialisierung der Variablen r und c ist hiermit konsistent).
| SlidePuzzle.scala |
var field = new Array[Array[Int]](SIZE)
for (val i<-Iterator.range(0,SIZE)) field(i)=new Array[Int](SIZE)
for (val i<-Iterator.range(0,SIZE*SIZE)) field(i/SIZE)(i%SIZE)=i
|
Eine Art Kopierkonstruktor schafft ein neues Objekt mit gleichen Feldwerten:
| SlidePuzzle.scala |
def this(that:SlidePuzzle)={
this(that.SIZE)
copyFromThat(that)
}
def copyFromThat(that:SlidePuzzle)={
for(val i<-Iterator.range(0,SIZE);val j<-Iterator.range(0,SIZE))
field(j)(i)=that.field(j)(i)
r=that.r
c=that.c
}
|
Es folgt die die Implementiereung der Nachfolgerfunktion. Abhängig davon, ob
das freie Feld in Mitte, Rand oder Ecke steht, sind die vier verschiedenen
Schieberichtungen möglich:
| SlidePuzzle.scala |
import Direction.{_};
def moves():List[Direction.Value]={
var result=List[Direction.Value]()
if (r>0) result=Down::result
if (r<SIZE-1) result=Up::result
if (c>0) result=Right::result
if (c<SIZE-1) result=Left::result
result
}
|
Um auf einem Zielzustand zu testen, wird das Feld solange von links nach rechts
und oben nach unten durchlaufen, bis der Wert der Plättchen nicht mehr
auf der richtigen Position liegt.
| SlidePuzzle.scala |
def terminalState():Boolean={
var result=true;
for (val r<-Iterator.range(0,SIZE)
;val c<-Iterator.range(0,SIZE)
;result&&
{result= !(field(r)(c)/SIZE!=r || field(r)(c)%SIZE!=c)
;result}){}
result
}
|
Als nächstes sei die Methode move aus SearchTree implementiert:
Um tatsächlich eine Aktion auszuführen, wird eine Kopie des aktuellen Zustands
angefertigt, auf dieser Kopie das entsprechende Plättchen verschoben und die
derart manipulierte Kopie als Ergebnis genommen.
| SlidePuzzle.scala |
def move(m:Direction.Value):SlidePuzzle={
val res=new SlidePuzzle(this)
res.move(m,res)
}
|
Die eigentliche Verschiebeoperation auf der Kopie wurde in folgende Methode
ausgelagert:
| SlidePuzzle.scala |
def move(m:Direction.Value,res:SlidePuzzle)={
m match {
case Up =>
res.field(r)(c)=field(r+1)(c)
res.field(r+1)(c)=0
res.r=r+1
case Down=>
res.field(r)(c)=field(r-1)(c)
res.field(r-1)(c)=0
res.r=r-1
case Left=>
res.field(r)(c)=field(r)(c+1)
res.field(r)(c+1)=0
res.c=c+1
case Right=>
res.field(r)(c)=field(r)(c-1)
res.field(r)(c-1)=0
res.c=c-1
}
res
}
|
Um ein wenig zu sehen, wie das alles funktioniert, sei die
Methode toString überschrieben:
| SlidePuzzle.scala |
override def toString()={
val result = new StringBuffer()
for (val j<-Iterator.range(0,SIZE)){
for (val i<-Iterator.range(0,SIZE))
result append ("|"+(if (0==field(j)(i)) " "else field(j)(i)))
result append ("|\n")
}
result.toString()
}
|
Für spätere Zwecke sei auch die Methode zur Gleichheit überschrieben, so daß
sie zwei Werteweise gleiche Spielfelder als solche erkennt.
| SlidePuzzle.scala |
override def equals(other:Any):Boolean={
var result=true;
var that=other.asInstanceOf[SlidePuzzle]
for (val r<-Iterator.range(0,SIZE)
;val c<-Iterator.range(0,SIZE)
;result
){result=result&&this.field(r)(c)==that.field(r)(c)}
result
}
}
|
Damit ist unser erster rationaler problemlösender Agent implementiert.
Es ist an der Zeit, die Breitensuche für das Schiebepuzzle zu testen. Hierzu
erzeugen wir eine Schiebepuzzleinstanz, verschieben ein paar Plättchen und
lassen nach einer Lösung suchen, die dann ausgegeben wird:
| TestSlide.scala |
package name.panitz.ki
object TestSlide extends Application{
import Direction.{_}
val sp= (new SlidePuzzle(3)
move Left move Up move Left move Up
move Right move Down move Right move Down)
Console println "zu loesendes Problem"
Console println sp
Console println "ist das schon der Terminalzustand"
Console println (sp.terminalState)
val solution=sp.breadthFirst
Console println "loesende Zugfolge mit Breitensuche"
Console println solution
var tmp=sp
for (val m<-solution) tmp=tmp move m
Console println "geloestes Problem"
Console println tmp
}
|
Das sah doch schon recht gut aus. Versuchen wir das gleiche mit einem etwas
stärker verschobenen Puzzle, so müssen wir leider feststellen, das bereits die
uns realistisch zur Verfügung stehenden Zeit und Speicherresourcen gesprengt
werden.
| TestSlideComplex.scala |
package name.panitz.ki
object TestSlideComplex extends Application{
import Direction.{_}
val moves =
List(Left,Up,Up,Left,Down,Down,Right,Up,Up,Right,Down,Down
,Left,Up,Up,Right,Down,Down,Left,Up,Left,Down,Right
,Right,Up,Left)
var sp= new SlidePuzzle(3)
for (val m<-moves)sp=sp move m
Console println "zu loesendes Problem"
Console println sp
val solution=sp.breadthFirst
Console println "loesende Zugfolge mit Breitensuche"
Console println solution
}
|
Wird dieses Programm gestartet, so läßt die Lösung länger auf sich warten, als
wir gewillt sind zu warten. Obwohl es sich insgesamt um ein sehr simples Spiel
mit nur sehr wenigen Aktionen pro Zustand handelt, sprengt das naive
Hauruck-Verfahren der Breitensuche sehr schnell unsere Resourcen. Dieses ist
natürlich mit dem exponentiellen Anwachsen der Baumebenen zu erklären. Hier
ist die Crux der KI. Für die meisten Probleme der KI sind nur deterministische
Algorithmen
bekannt, die einen exponentiellen Aufwand haben; oder der wie der Fachmann
sagt, zur Klasse NP gehören.
2.2.3 Tiefensuche
Die mehr oder wenige komplett komplementäre Strategie zur Breitensuche ist
natürlich die Tiefensuche. Hier wird der Suchbaum nicht ebenenweise aufgebaut,
sondern zunächst ein Pfad möglichst weit in die Tiefe verfolgt, und erst wenn
dort ein Blatt nicht mehr expandiert werden kann, weil es keine
Nachfolgerknoten mehr gibt, wird im Baum zum vorletzten Knoten zurückgegangen,
um dort beim nächsten Kind in die Tiefe zu schauen.
Wir können tatsächlich die allgemeine Suchfunktion benutzen, um ihr die
Strategie zur Tiefensuche zu übergeben. Für die Tiefensuche
ist nicht das älteste Blatt zu expandieren, sondern das neueste, welches wir
daher an den Anfang der Blattliste einfügen werden. Somit ist
der fringe gerade genau umgekehrt wie in der Breitensuche
sortiert. Jetzt stehen Zustände weiter vorne im fringe, wenn sie
tiefer im Baum stehen.
Erweitern wir also die Suche, um die Tiefensuche.
| DepthSearch.scala |
package name.panitz.ki
trait DepthSearch[M] extends SearchTree[M] {
|
DieseEinfügefunktion, die neue knoten vorne einfügt,
erzeugt uns für unseren allgemeinen Suchalgorithmus
eine Tiefensuche.
Einen Nachteil der Breitensuche, hat die Tiefensuche nicht
mehr. Die Länge des fringe wächst nicht exponentiell an. Haben wir
einen durchschnittlichen Verzweigungsgrad im Baum von c, dann hat in
einer Baumtiefe n der fringe eine Länge von c*m. Im
Gegensatz dazu hat er für die Breitensuche eine Länge von c^{n+1}.
Wir haben ein ernsthaftes
Der Ariadnefaden war der griechischen Mythologie zufolge ein Geschenk der
Prinzessin Ariadne an Theseus. Mit Hilfe des Fadens fand Theseus den Weg durch
das Labyrinth, in dem sich der Minotauros befand. Nachdem Theseus den
Minotauros getötet hatte, konnte er mit Hilfe des Fadens das Labyrinth wieder
verlassen. Der Hinweis für die Verwendung des Fadens stammt von Daidalos, der
auch das Labyrinth entworfen hat.
Als Strafe für den Hinweis wurde anschließend Daidalos mit seinem Sohn Ikaros
ins Labyrinth gesperrt. Mit Hilfe selbst gebauter Flügel konnten sich beide
befreien. Problem mit dieser Tiefensuche. Sie wird für viele
Problemfelder nicht terminieren. Sie terminiert nur, wenn der Suchbaum eine
endliche Tiefe hat. Der Suchbaum für unser Schiebespiel hat leider, auch wenn
es nur endlich viele Zustände gibt, eine unendliche Tiefe. Damit
terminiert die Tiefensuche nicht. Ein Beispiel für ein Spiel mit endlicher Tiefe
wäre z.B.~Vier Gewinnt, das wir später kennenlernen werden. Dort ist
irgendwann das Spielfeld voll, und kein weiterer Stein kann gesetzt
werden.
Da es allerdings nur endlich viele Zustände im Schiebespiel gibt, kann man die
Tiefensuche darauf anwenden, wenn man Zustände, die an anderer Stelle des
Suchbaums bereits expandiert wurden, nicht ein weiteres Mal expandiert. Hierzu
ist allerdings die Menge aller bereits besuchten Spielzustände zu speichern.
Wir betrachten damit den Baum in gewisser Weise als gerichteter
Graph. Baumknoten, die mit dem gleichen Zustand markiert sind, werden darin
als ein gemeinsamer Graphknoten betrachtet. Dieser Graph enthält nun unter
Umständen Zyklen. Wenn wir die allgemeine Suche
nicht auf einem Baum, sondern den sogestallt definierten Graphen
implementieren wollen, müssen wir darüber Buch führen, welche Zustände bereits
besucht wurden. Damit ist man mit der klassischen Frage konfrontiert: wie verhindere ich
innerhalb eines Labyrinths immer im Kreis zu laufen? Hierzu ist darüber Buch
zu führen, welche Knoten schon besucht wurden. Ein sehr frühes Beispiel, über
bereits besuchte Knoten eines Graphen Buch zu führen, findet sich in der
griechischen Mythologie mit dem Ariadnefaden.
Unsere Scalaimplementierung wird keinen Faden durchs Labyrinth ziehen, sondern
in einer Menge speichern, welche Zustände bereits expandiert wurden.
Auch dieses läßt sich allgemein als eine Methode implementieren.
| DepthSearch.scala |
def generalGraphSearch(insertNew:Insert[M]):List[M]={
val allreadyExpanded = new java.util.HashSet/*[SearchTree[M]]*/()
generalSearch(
(xs,ys)=>{
val newNodes=
for (val y<-ys;!(allreadyExpanded contains y)) yield y
for (val y<-newNodes) allreadyExpanded add y
insertNew(newNodes,xs)}
)
}
|
Die Tiefensuche im Graphen, sei nun eine allgemeine Suche im Graphen, die beim
Einfügen, neu-expandierte Knoten vorne im fringe einfügt.
Damit haben wir nun zwar sichergestellt, daß die Tiefensuche terminiert,
sofern es endlich viele Zustände gibt. Glücklich werden wir für das
Schiebepuzzle damit allerdings nicht. Das Schiebepuzzle kennt keine Sackgassen
im herkömmlichen Sinne, es kann beliebig Hin-und-Her geschoben werden. Wir
können uns ganz schön in die Tiefe verlaufen, bis wir sehr naheliegende
Lösungen gefunden haben. Die gesuchte Lösung wird höchstwahrscheinlich
sehr kompliziert sein. Die Tiefensuche findet nicht unbedingt eine optimale
Lösung.
2.2.4 Tiefensuche mit maximaler Tiefe
Im letzten Abschnitt hat sich die Tiefensuche als problematische Suchstrategie
erwiesen, weil sie mitunter unendlich weit in die Tiefe absteigen kann. Weiß
man hingegen, daß die Lösung innerhalb einer bestimmten Tiefe zu finden ist,
so läßt sich mit einer Tiefensuche, die eine maximale Beschränkung hat, die
Lösung finden.
| DepthSearch.scala |
def depthSearch(depth:Int):List[M]=
generalSearch((xs,ys)=>{
val newNodes=for (val y<-ys;y._1.length < depth) yield y
newNodes:::xs}
)
|
Die Einfügefunktion fügt jetzt nur noch Knoten ein, deren Pfadlänge von der
Wurzel nicht eine bestimmte vorgegebene Tiefe überschreitet. Natürlich findet
diese Suchstrategie keine Lösung, wenn es keine in der vorgegebenen Tiefe
gibt. Aber auch wenn es eine Lösung gibt, garantiert die limitierte
Tiefensuche nicht, daß auch eine optimale Lösung gefunden wird.
2.2.5 Iteratives Vertiefen
Die Tiefensuche hat nicht die Speicherplatzprobleme der Breitensuche, findet
dafür aber nicht unbedingt eine optimale Lösung. Kann man die Vorteile der
beiden Strategien verbinden, ohne dadurch Einbußen in der Laufzeitkomplexität
zu erlangen. Man kann. Das entsprechende Verfahreen heißt: iteratives
Vertiefen. Als eigentlicher Suchalgorithmus wird dabei, die limitierte
Tiefensuche benutzt. Diese wird angefangen mit der Tiefe 0 solange mit
aufsteigenden maximalen Tiefen aufgerufen, bis bei einer Tiefe ein Ergebnis
gefunden wurde.
In Scala ergibt sich folgende naheliegende Implementierung.
| DepthSearch.scala |
def deepening():List[M]={
var result:List[M]=null;
var depth=0;
while (result==null){
result=depthSearch(depth)
depth=depth+1
}
result
}
}
|
Das iterative Vertiefen simuliert im Prinzip die Breitensuche über die
Tiefensuche. Damit findet es eine optimale Lösung. Allerdings, wenn der
Zielzustand in Tiefe n zu finden ist, dann ist die
Ebene n-1 in n-1 Durchläufen der Iteration zu generieren.
2.2.6 Tiefes Schieben
Es soll natürlich auch getestet werden, ob wir mit den in diesem Abschnitt
vorgestellten Suchverfahren zur Tiefensuche, auch Lösungen für das
Schiebepuzzle finden können. Hierzu sei eine Unterklasse des Schiebepuzzles
implementiert, die auch DepthSearch implementiert.
| DepthSlide.scala |
package name.panitz.ki
class DepthSlide(S:Int)
extends SlidePuzzle(S) with DepthSearch[Direction.Value]{
def this(that:SlidePuzzle)={this(that.SIZE);copyFromThat(that)}
override def move(m:Direction.Value):DepthSlide={
val res=new DepthSlide(this)
res.move(m,res).asInstanceOf[DepthSlide]
}
}
|
Ein paar kleine Testaufrufe zeigen, daß wir auch mit diesen Verfahren
tatsächlich Lösungen finden können.
| TestDepth.scala |
package name.panitz.ki
object TestDepth extends Application{
import Direction.{_}
val sp= (new DepthSlide(3)
move Left move Up move Left move Up
move Right move Down move Right move Down)
Console println sp
Console println (sp.terminalState)
Console println "depth search with limit 10"
val solution2=sp depthSearch 10
Console println solution2
var tmp=sp
for (val m<-solution2) tmp=tmp move m
Console println tmp
Console println "iterative deepening"
val solution3=sp.deepening
Console println solution3
tmp=sp
for (val m<-solution3) tmp=tmp move m
Console println tmp
Console println "depth first search"
Console println "I hope you have some time"
val solution1=sp.depthSearchGraph
Console println solution1
tmp=sp
for (val m<-solution1) tmp=tmp move m
Console println tmp
}
|
Unser hauptsächliches Problem mit der Komplexität ist leider noch nicht
gelöst. Unsere derzeitigen Hauchruck-Verfahren der Suche, sind nicht in der
Lage, ein wenig stärker verschobene Schiebespiele zu lösen.
2.2.7 Randbedingungen per Suche Lösen
Eine Sudoku (jap. \cntext{数独} Sūdoku, kurz
für \cntext{数字は独身に限る }Sūji wa dokushin ni kagiru, wörtlich: Zahlen als Einzel beschränken) ist ein Zahlenrätsel.
Das Spiel besteht aus einem Gitterfeld mit 3×3 Blöcken, die jeweils in 3×3
Felder unterteilt sind, insgesamt also 81 Felder in 9 Reihen und 9 Spalten. In
einige dieser Felder sind schon zu Beginn Ziffern zwischen 1 und 9
eingetragen. Ziel des Spiels ist es nun, die leeren Felder des Puzzles so zu
vervollständigen, dass in jeder der 9 Zeilen, Spalten und Blöcke jede Ziffer
von 1 bis 9 genau einmal auftritt.
Typischerweise sind 22 bis 36 Felder von 81 möglichen vorgegeben. Es gibt
allerdings auch bekannte Kombinationen, in denen 17 Zahlen ein eindeutiges
Sudoku bilden. Die minimale Anzahl Ziffern, die nötig ist, um ein eindeutiges
Sudoku zu bilden, ist nicht bekannt. Da jede Zahl in jedem der drei
genannten Bereiche nur einmal auftritt, ist der diesen Umstand
andeutende wörtliche Name des Puzzlespiels Einzelne Zahl.
Wenn eine Zahl in einem Feld möglich ist, bezeichnet man sie
als Kandidat. Die drei Bereiche (Reihe, Spalte, Block) werden
zusammengefasst als Einheiten bezeichnet.
Inzwischen gibt es auch Sudokus mit 4×4 Unterquadraten und somit 256 (=16×16)
Feldern, in die 16 verschiedene Zahlen, Buchstaben oder Symbole verteilt
werden, sowie Sudokus mit 4×3 Blöcken mit jeweils 3×4 Feldern. Ebenso sind 5×5
Sudokus denkbar, etc. Für Kinder gibt es Sudokus mit einer Kantenlänge von 2
pro Unterquadrat, also werden dort nur 4 Ziffern oder Bildsymbole
benötigt. Weitere Varianten sind Sudokus mit treppenförmiger Begrenzung der
Blöcke (engl. Stairstep Sudoku) und solche mit unregelmäßig geformten
Blöcken.
Beim Killer Sudoku gibt es keine Schlüsselzahlen, sondern die Summe von Zahlen
in zusammengefassten Blöcken wird angegeben.
Seit Ende 2005 gibt es tragbare, elektronische Sudoku-Geräte. Desweiteren gibt
es Brettspiele und Computerspiele. Ein Nachfolger von Sudoku ist Kakuro.
Der früheste Ursprung des Sudoku kann in den Rätselspielen des Schweizer
Mathematikers Leonhard Euler gesehen werden, der solche unter dem Namen Carré
latin (Lateinisches Quadrat) bereits im 18. Jahrhundert verfasste. Abweichend
von den modernen Sudoku-Rätseln sind diese nicht in Blöcke (Unterquadrate)
unterteilt.
Das heutige Sudoku in Blockform wurde 1979 in der Zeitschrift Math Puzzels \&
Logic Problems, die vom Computerhersteller Dell herausgegeben wird, erstmals
veröffentlicht. Die ersten Sudokus wurden zwar in den USA publiziert, seinen
Durchbruch erlangte das Zahlenrätsel jedoch erst um etwa 1984, als die
japanische Zeitschrift Nikoli diese zunächst unter dem
Namen Sūji wa dokushin ni kagiru regelmäßig abdruckte.
Hieraus entwickelte sich schließlich der
Begriff Sudoku. Der Neuseeländer Wayne Gould hat Sudoku auf einer Japanreise
kennen gelernt. Sechs Jahre brauchte er, um eine Software zu entwickeln, die
neue Sudokus per Knopfdruck entwickeln kann.
Anschließend bot er seine Rätsel der Times in London an. Die Tageszeitung
druckte die ersten Sudoku-Rätsel und trat auf diese Weise eine Sudoku-Lawine
in der westlichen Welt los.
In Österreich führte der regelmäßige Abdruck in Tageszeitungen wie Der
Standard und Kronen Zeitung zu einer raschen Verbreitung Ende 2005. Des
weiteren erscheint es regelmäßig in der Hersfelder Zeitung, der Frankfurter
Rundschau, in Der Tagesspiegel und mittlerweile auch in der
ZEIT. \ große Klasse von Problemen in der KI beschäftigen sich
damit bestimmte Lösungen unter Randbedingungen zu finden. Diese Probleme werden CSP genannt, als
Abkürzung für constraint satisfaction problem. Dabei geht es darum
bestimmte Variablen mit Werten zu belegen, so daß eine Reihe von
Randbedingungen eingehalten werden. In unserem Fachbereich ist Frau Groß-Bosch
jedes Semester damit beauftragt, ein relativ komplexes CSP zu lösen, wenn sie
die Stundenpläne plant. Hier sind die Variablen die uns zur Verfügung
stehenden Räume zu bestimmten Vorlesungszeiten. Gesucht ist eine Belegung
dieser Variablen mit Vorlesung und zugehörigen Dozenten. Die dabei zu
erfüllenden Randbedingungen sind mannigfach: Alle Vorlesungen müssen gehalten
werden, von Dozenten, die das Fach berherrschen. Kein Dozent kann zur gleichen
Zeit mehr als eine Vorlesung halten. Vorlesungen eines Semesters dürfen nicht
parallel liegen, Raumgrößen müssen zur erwarteten Teilnehmerzahl passen,
bestimmte Wünsche an die Raumtechnik der Dozenten müssen erfüllt werden, kaum ein
Dozent will morgens um acht, die Dozenten wollen möglichst keine Freistunden
zwischen den Vorlesungen haben undundund. Hier einmal ein kleines bewunderndes
Dankeschön an Frau Groß-Bosch, die allsemesterlich dieses CSP zur
Zufriedenheit aller löst.
Eine erst seit Kurzem in Europa populär gewordene Form eines CSP sind die
Sudoku, die mitlerweile in vielen Zeitungen abgedruckt werden und von vielen
Leuten gerne zum Zeitvertreib gelöst werden. Hier sind die Variablen die
freien Felder, die mit den Werten 1 bis 9 zu belegen sind, so daß keine
Ziffer in einer Reihe, Spalte oder Unterquadrat mehrfach auftritt.
Wir können unsere bisherigen Suchstrategien direkt benutzen, um CSP zu
lösen. Als Aktion ist dabei nur die Belegung einer Variablen mit einem
bestimmten Wert zu identifizieren. Jeder Plan ist exakt gleich lang: er
hat exakt die Anzahl n der zu belegenden Variablen als Länge. Damit hat der
Suchbaum eine endliche Tiefe, die, wenn das CSP lösbar ist, genau n ist.
Der Startzustand des CSP als Suchproblem ist der Zustand, in dem noch keine
Variabel belegt ist. Im Endzustand sind alle Variablen so belegt, daß gegen keine
Randbedingung verstoßen wurde. Die Kosten eines Zugs ist konstant der
Wert 1. Nimmt
man als Nachfolgerfunktion für einen Zustand, die Funktion, die die Menge aller
möglichen erlaubten Belegungen einer beliebigen Variablen zurückgibt, wächst
der Suchbaum allerdings kollossal in die Breite und sprengt sehr schnell die
realistisch zur Verfügung stehenden Resourcen.
Betrachten wir einmal die möglichen Lösungen eines CSP als Suchproblem. Die
einzelnen Aktionen eines Plans zur Lösung sind kommutativ. Wir können die
Aktionen einer Lösung beliebig permutieren und erhalten wieder eine
Lösung. Diese spezielle Eigenschaft können wir benutzen, um die Breite des
Suchbaums radikal einzuschränken. Jede Tiefe des Baums bekommt einfach eine
feste Variable zugeordnet, der zu dieser Zeit ein Wert zugewisen werden
kann. Damit reduziert sich der Verzweigungsgrad des Baumes auf jeder Ebene um
den Bruchteil der noch zu belegenden Variablen.
Da die Tiefe des Suchbaums nicht nur beschränkt ist, sondern auch bekannt ist,
daß nur in der maximalen Tiefe des Baums eine Lösung zu erwarten ist, sofern
es eine gibt, bietet sich die Tiefensuche dazu an, das CSP zu lösen. Der
allgemeine Nachteil der Tiefensuche, das sie die optimale Lsöung verpasst
existiert nicht mehr. Dafür hat sie jetzt den Vorteil, speichereffizienter als
die Breitensuche zu sein.
Implementierung von Sudokus
Versuchen wir jetzt einmal einen Agenten zum Lösen von Sudokus zu
implementieren. Wir brauchen eine Tiefensuche. Die Aktionen sind jetzt Tripel:
die erste Zahl des Tripels gebe die Zeile, die zweite die Spalte, in die ein
Wert gesetzt wird an, die dritte Zahl schließlich den Wert, der an die
entsprechende Position gesetzt wird.
| Sudoku.scala |
package name.panitz.ki
class Sudoku extends DepthSearch[Tuple3[Int,Int,Int]] {
type Move=Tuple3[Int,Int,Int]
|
Zur internen Speicherung des Spielfeldes bietet sich wieder eine
zweidimensionale Reihung an.
| Sudoku.scala |
val field:Array[Array[Int]]=new Array[Array[Int]](9)
for (val i<-Iterator.range(0,9))field(i)=new Array[Int](9)
|
Ein Konstruktor zum Kopieren des Spielfeldes sei vorgesehen:
| Sudoku.scala |
def this(that:Sudoku)={
this()
for (val r<-Iterator.range(0,9);val c<-Iterator.range(0,9))
field(r)(c)=that.field(r)(c)
}
|
Jetzt kommt die entscheidene Methode, die die möglichen Züge auf einem Zustand
zurückgibt. Hierzu soll bei einem Zustand als nächster Zug, nur das erste (von
links nach rechts, oben nach unten) freien Feld mit einem Wert belegt werden
dürfen. Hierzu suchen wir zunächst das erste freie Feld:
| Sudoku.scala |
def moves():List[Move]={
val freeFields=
for (val r<-Iterator.range(0,9)
;val c<-Iterator.range(0,9)
;field(r)(c)==0) yield Pair(r,c)
|
Wenn der daraus entstehende Iterator ein nächstes (also erstes) Element hat,
dann suchen wir unter den Randbedingen für Sudokus eine entsprechende Lösung
für dieses Feld. Ansonsten das Feld bereits voll.
| Sudoku.scala |
if (freeFields.hasNext){
val Pair(r,c)=freeFields.next
(for (val n<-Iterator.range(1,10)
;fullFillsConstraints(n,r,c)
) yield {Tuple(r,c,n)}).toList
}else List()
}
|
Drei Randbedingungen sind zu beachten: in Reihe, Spalte und Unterquadrat eines
Feldes dürfen keine zwei Felder mit dem gleichen Wert belegt sein.
| Sudoku.scala |
def fullFillsConstraints(n:Int,r:Int,c:Int)=
( fullFillsRow(n,r)
&&fullFillsColumn(n,c)
&&fullFillsSquare(n,(r-r%3),(c-c%3)))
|
Die drei Einzelbedingungen seien in relativ naiver Weise implementiert:
| Sudoku.scala |
def fullFillsRow(newVal:Int,r:Int)={
val values=newVal ::
(for (val c<-Iterator.range(0,9);val n=field(r)(c);n!=0)
yield n).toList
values.length==values.removeDuplicates.length
}
def fullFillsColumn(newVal:Int,c:Int)={
val values=newVal ::
(for (val r<-Iterator.range(0,9);val n=field(r)(c);n!=0)
yield n).toList
values.length==values.removeDuplicates.length
}
def fullFillsSquare(newVal:Int,r:Int,c:Int)={
var values=List[Int](newVal)
for (val i<-Iterator.range(0,3)
;val j<-Iterator.range(0,3)
;val n=field(r+i)(c+j)
;n!=0)
values=n::values
values.length==values.removeDuplicates.length
}
|
Noch sind die Methoden move und terminalState abstrakt. Um
einen tatsächlichen Zug durchzuführen. Die Methode move sei ähnlich
umgesetzt, wie es schon im Schiebepuzzle zu sehen war. Eine Kopie vom
aktuellen zustand wird angelegt, in der dann der Zug volluogen wird.
| Sudoku.scala |
def move(m:Move):Sudoku={
val result=new Sudoku(this)
val Tuple3(r,c,n)=m
result.field(r)(c)=n
result
}
|
Zum Testen, ob wir den Finalzustand erreicht haben, braucht lediglich
ausgeschlossen werden, daß ein Feld noch mit 0 belegt ist.
| Sudoku.scala |
def terminalState():Boolean=
(for (val r<-Iterator.range(0,9);val c<-Iterator.range(0,9)
;val n=field(r)(c)) yield n).forall((x)=>x!=0)
|
Auf eine einfache Implementierung von toString sei natürlich nicht
verzichtet.
| Sudoku.scala |
override def toString()={
val result = new StringBuffer()
for (val j<-Iterator.range(0,9)){
for (val i<-Iterator.range(0,9))
result append ("|"+(if (0==field(j)(i)) " "else field(j)(i)))
result append ("|\n")
}
result.toString()
}
}
|
Schließlich wollen wir unseren Agenten zum Lösen von Sudokus auch einmal
Testen.
| TestSudoku.scala |
package name.panitz.ki
object TestSudoku extends Application{
var sud=new Sudoku()
val f
=( List
( List(0,0,0,0,0,0,5,0,9)
, List(0,9,3,0,8,0,0,7,2)
, List(2,0,8,4,5,9,0,0,0)
, List(9,0,0,0,0,0,2,0,0)
, List(8,0,0,7,6,0,0,4,0)
, List(0,6,0,9,1,0,0,0,5)
, List(0,8,0,0,0,0,1,5,0)
, List(3,0,0,0,7,0,0,0,4)
, List(0,1,0,3,2,0,0,9,0)))
val f2=f.toArray
for (val r<-Iterator.range(0,9))
sud.field(r)=f2(r).toArray
Console.println(sud)
val solution=sud.depthSearch
Console.println(solution)
for (val s<-solution) sud=sud move s
Console.println(sud)
}
|
Tatsächlich ließ sich dieses Sudoku ohne Wartezeit problemlos von unserem
Agenten lösen. Im Anhang des Skripts findet sich eine minimale Gui-Anwendung,
die es erlaubt beliebige Sudoku-Aufgaben einzugeben und lösen zu lassen.
Waltz Prozedur zur Interpretation 2-dimensionaler Projektionen
Man mag einwänden, daß das vorangegangenen Beispiel zur Suche einer Lösung
unter Randbedingungen sehr künstlich, oder eben nur ein Spiel war, was weit
von den Zielen der KI entfernt ist. Ein sehr schönes Beispiel für die
Randbedingungen, daß seit bald 30 Jahren in Lehrbüchern und Vorlesungen zur KI
gerne benutzt wird, ist die Interpretation von Linienzeichnungen. Es geht
dabei um Zeichnungen, die ein Szenario von Bauklötzen darstellt. Dabei wird
folgende Einschränkung gemacht:
- jede Körper hat nur ebene Flächen
- jede Flächer hat genau vier Ecken
- in jeder Ecke stoßen genau drei Flächen aufeinander
- zwischen direkt aufeinander stehenden Flächen ist keine Linie
zu sehen.
Eine Zeichnung eines Szenarios soll die Projektion auf eine 2-dimensionale
Fläche einer beliebigen Anordnung solcher Körper sein.
Ein Beispielszenario findet sich in Abbildung~.
Aufgabe ist es nun, eine solche Zeichnung zu interpretieren. Dabei können die
Striche drei unterschiedliche Arten von Kanten in der Realität sein:
- sie können normale konkave Kanten eines Körpers sein.
- es kann sich auch um konvexe Kanten handeln, die entstehen, wenn zwei
Körper aneinander oder aufeinander stehen.
- es kann aber auch eine Kante sein, die das Gebilde von Körpern umrandet,
an der also keine zwei sichtbaren Ebene zusammenstoßen.
Die Interpretaion einer Zeichnung bedeutet jetzt, jede Kante zu markieren, ob
es sich um eine konvexe, konkave oder Umrandungskante handelt. Hierzu seien
die folgenden Symbole gewählt:
- + für konvexe Kanten
- - für konkave Kanten
- \rightarrow für Umrandungskanten
Die Markierung der Kanten soll möglichst konsistent sein und dem Szenario aus
der realen Welt entsprechen.
Auch hierbei handelt es sich um ein Suchproblem, in dem Randbedingungen zu
erfüllen sind. Diese Randbedingungen sind in diesem Fall natürliche
Beschränkungen, wie sie in einem Bild, das durch Projektion eines
Bauklotzszenarios entstehen kann. Wir wollen uns in diesem Abschnitt nicht zu
detailliert mit der eigentlichen Klötzchenwelt beschäftigen, sondern es
lediglich als Beispiel nehmen, um zu zeigen, wie die bisher vorgestellten
Algorithmen unterschiedlichste Aufgaben lösen können, wenn es gelingt, das
zu lösende Problem entsprechend zu modellieren.
Dazu wurde
analysiert was für Arten von Ecken in einer solchen Zeichnung überhaupt
auftreten können, und wie diese Ecken überhaupt markiert sein können. Dabei
stellt sich heraus, daß es nur vier Arten von Ecken gibt:
- L-förmige Ecken, an denen zwei sichtbare Kanten aneinander stoßen.
- T-förmige Ecken, an denen eine Kante auf eine in der Projektion optisch
durchgehende Kante stößt.
- Gabeln, an denen eine Kante im flachen Winkel zu wei im spitzen Winkel
zueinander stehenden Kanten steht.
- Pfeile, in denen drei Kanten im spitzen Winken zueinander stehen.
Die vier verschiedenen Eckenarten sind in Abbildung~ zu
sehen.
Nun stellt sich bei einer weiteren Analyse heraus, daß es für die vier
Eckenarten nur recht wenig Möglichkeiten geben kann, wie sie interpretiert
werden können. Alle natürlich möglichen Markierungen für die vier Eckentypen
sind in Abbildung~ zu sehen.
Damit ist klar, wie sich die Interpretation einer Linienzeichnung als
Suchproblem mit Randbedingungen darstellen läßt. Gesucht ist eine Markierung,
so daß jede Ecke mit einer für diesen Typ legalen Eckenmarkierung markiert
ist, und keine Kante zwei verschiedene Markierungen hat.
Implementierung in Scala
Da wir bereits die allgemeine Suche implementiert haben und da Scala es uns
erlaubt die Markierungsprozedur relativ elegant und knapp umzusetzen, wollen
wir uns auch für dieses Beispiel nicht um eine Implementierung drücken.
In diesem Beispiel werden zur Abwechslung verstärkt die Konzepte der funktionalen
Programmierung von Scala genutzt.
Zunächst seien die Klassen für die vier Eckentypen definiert. Als gemeinsame
Oberklasse haben sie die abstrakte Klasse Vertex.
| Vertex.scala |
package name.panitz.ki
abstract class Vertex
case class L(e1:Edge,e2:Edge) extends Vertex
case class Fork(e1:Edge,e2:Edge,e3:Edge) extends Vertex
case class T(left:Edge,middle:Edge,right:Edge) extends Vertex
case class Arrow(left:Edge,middle:Edge,right:Edge) extends Vertex
|
Die Ecken beinhalten Kanten. Eine Kante ist dabei ein Objekt, das eine
Markierung hat:
| Edge.scala |
package name.panitz.ki
class Edge(var marked:Marked.Value){
override def toString()
=if (marked==null) "null" else marked.toString
}
|
Eine Markierung sei eine der folgenden vier Werte.
| Marked.scala |
package name.panitz.ki
object Marked extends Enumeration("-","+","<-","->") {
final val Concave, Convex, BoundaryLeft, BoundaryRight = Value}
|
Ein zu interpretierendes Bild ist nun lediglich eine Liste von Ecken, daher
läßt sich gut von der
Standardklasse ArrayBuffer ableiten. Zusätzlich
soll die Tiefensuche implementiert werden. Beides spiegelt sich in der
Klassendeklaration wieder:
| Scene.scala |
package name.panitz.ki
class Scene extends scala.collection.mutable.ArrayBuffer[Vertex]
with DepthSearch[CaseClass] {
|
Wie in all den vorangegangenen Beispielen, sei ein Konstruktor, der eine Kopie
anlegt vorgesehen. In diesem Fall sieht dieser Kopiervorgang etwas eklig
aus. Die Ecken teilen sich Kanten. Es muß daher Buch darüber geführt werden,
welche Kante bereits kopiert wurde, damit diese kein zweites Mal kopiert
werden. Hierzu wird sich einer Abbildung bedient. Beim Kopieren von Kanten
wird diese Abbildung zunächst gefragt, ob bereits eine Kopie der Kante
existiert. Falls nicht, wird eine Kopie angelegt und diese in der Abbildung
vermerkt.
| Scene.scala |
def this(that:Scene)={
this()
import scala.collection.mutable.HashMap;
val copiedEdges=new HashMap[Edge,Edge]()
def cop(e:Edge)={
try {copiedEdges(e)}
catch{case _:java.lang.Error=>
val copy=new Edge(e.marked)
copiedEdges.update(e,copy)
copy
}
}
for (val v<-that.elements) {
v match {
case L(e1,e2)=>this += L(cop(e1),cop(e2))
case T(e1,e2,e3)=>this += T(cop(e1),cop(e2),cop(e3))
case Fork(e1,e2,e3)=>this += Fork(cop(e1),cop(e2),cop(e3))
case Arrow(e1,e2,e3)=>this += Arrow(cop(e1),cop(e2),cop(e3))
}
}
}
|
18 verschiedene legale Markierungen gibt es an den Ecken. Die folgende Methode
nutzt dieses Wissen über die natürliche Beschränkung der
Eckenmarkierungen. Für eine Kante wird die Liste der legalen Markierungen
einer solchen Kante zurückgegeben:
| Scene.scala |
def possibleMarks(v:Vertex)={
import Marked.{_};
v match{
case L(_,_)
=> List(Tuple(BoundaryLeft,BoundaryLeft)
,Tuple(BoundaryRight,BoundaryRight)
,Tuple(BoundaryRight,Convex)
,Tuple(Convex,BoundaryRight)
,Tuple(BoundaryLeft,Concave)
,Tuple(Concave,BoundaryLeft)
)
case Fork(_,_,_)
=> List(Tuple(Convex,Convex,Convex)
,Tuple(Concave,Concave,Concave)
,Tuple(BoundaryLeft,Concave,BoundaryLeft)
,Tuple(BoundaryLeft,BoundaryLeft,Concave)
,Tuple(Concave,BoundaryLeft,BoundaryLeft)
)
case T(_,_,_)
=> List(Tuple(BoundaryLeft,BoundaryLeft,BoundaryLeft)
,Tuple(BoundaryLeft,BoundaryRight,BoundaryLeft)
,Tuple(BoundaryLeft,Concave,BoundaryLeft)
,Tuple(BoundaryLeft,Convex,BoundaryLeft)
)
case Arrow(_,_,_)
=> List(Tuple(BoundaryLeft,Convex,BoundaryLeft)
,Tuple(Convex,Concave,Convex)
,Tuple(Concave,Convex,Concave)
)
}
}
|
Die obige Methode kann genutzt werden, um zu testen, ob eine Ecke soweit
korrekt markiert ist. Hierzu muß eine der legale Markierungen existieren, die
zur Markierung der Ecke paßt:
| Scene.scala |
def correctlyMarked(v:Vertex)
=possibleMarks(v).exists((p)=>markFits(v,p))
|
Für eine Ecke wird mit der folgenden Methode getestet, ob eine Markierung zur
bereits getätigten Markierung an entsprechender Ecke paßt:
| Scene.scala |
def markFits(v:Vertex,t:CaseClass)=
Pair(v,t) match{
case Pair(L(e1,e2),Tuple2(m1,m2)) =>
fit(e1.marked,m1)&&fit(e2.marked,m2)
case Pair(T(e1,e2,e3),Tuple3(m1,m2,m3)) =>
fit(e1.marked,m1)&&fit(e2.marked,m2)&&fit(e3.marked,m3)
case Pair(Fork(e1,e2,e3),Tuple3(m1,m2,m3)) =>
fit(e1.marked,m1)&&fit(e2.marked,m2)&&fit(e3.marked,m3)
case Pair(Arrow(e1,e2,e3),Tuple3(m1,m2,m3)) =>
fit(e1.marked,m1)&&fit(e2.marked,m2)&&fit(e3.marked,m3)
}
|
Eine Markierung paßt zu einer Kanten, wenn die Kante entweder noch nicht
markiert ist, oder genau mit der in Frage kommenden Markierung markiert ist.
| Scene.scala |
def fit(x:Marked.Value,y:Any)=null==x||x==y
|
Wir haben nun alles beieinander, um die nächsten Züge zu berechnen. Hierzu,
ähnlich wie beim Sudoku-Programm, wird die nächste noch nicht vollständig
markierte Ecke gesucht:
| Scene.scala |
def moves():List[CaseClass]={
val unmarkedVertexes
= for (val v<-this.elements;!isMarked(v)) yield v
|
Sofern noch eine solche Ecke existiert, werden aus alen möglichen Markierungen
für diesen Eckentyp, diejenigen herausgefiltert, die mit den bereits
getätigten Kantenmarkierungen dieser Ecke zusammenpassen und nicht eine
benachbarte Ecke damit illegal markieren:
| Scene.scala |
if (unmarkedVertexes.hasNext){
val v=unmarkedVertexes.next
(for (val pm<-possibleMarks(v)
;markFits(v,pm)
;this.elements.forall((x)=>correctlyMarked(x))
) yield pm).toList
}else List()
}
|
Die folgende kleine Methode testet, ob eine Ecke bereits vollständig markiert
ist, also keine Markierung mehr null ist.
| Scene.scala |
def isMarked(v:Vertex)=
v match{
case L(e1,e2) =>e1.marked!=null&&e2.marked!=null
case T(e1,e2,e3)
=>e1.marked!=null&&e2.marked!=null&&e3.marked!=null
case Fork(e1,e2,e3)
=>e1.marked!=null&&e2.marked!=null&&e3.marked!=null
case Arrow(e1,e2,e3)
=>e1.marked!=null&&e2.marked!=null&&e3.marked!=null
}
|
Nachdem somit auf einer Ebene möglichen Züge berechnet werden können, bleibt
einen bestimmten Zug auch durchzuführen. Hierzu werde wieder die nächste nicht
fertig markierte Ecke genommen. Alle übrigen Ecken werden in einer Kopie
übernommen, nur die entsprechende Ecke wird neu markiert.
| Scene.scala |
def move(m:CaseClass):Scene={
val Pair(marked,unmarked)
=new Scene(this).toList.span((v)=>isMarked(v))
val result=new Scene()
for (val v<-marked) result += v
result += markedCopy(unmarked.head,m)
for (val v<-unmarked.tail) result += v
result
}
|
Die eigentliche Neumarkierung einer Ecke nimmt folgende Methode vor:
| Scene.scala |
def markedCopy(v:Vertex,t:CaseClass)={
def mv(e:Edge,m:Any)={e.marked=m.asInstanceOf[Marked.Value];e}
Pair(v,t) match{
case Pair(L(e1,e2),Tuple2(m1,m2))
=> L(mv(e1,m1),mv(e2,m2))
case Pair(T(e1,e2,e3),Tuple3(m1,m2,m3))
=> T(mv(e1,m1),mv(e2,m2),mv(e3,m3))
case Pair(Fork(e1,e2,e3),Tuple3(m1,m2,m3))
=> Fork(mv(e1,m1),mv(e2,m2),mv(e3,m3))
case Pair(Arrow(e1,e2,e3),Tuple3(m1,m2,m3))
=> Arrow(mv(e1,m1),mv(e2,m2),mv(e3,m3))
}
}
|
Scließlich ist nur noch zu spezifizieren, wenn ein Zielzustand erreicht ist.
Das ist der Fall, wenn alle Ecken vollständig markiert sind:
| Scene.scala |
def terminalState():Boolean=
elements.forall((v)=>isMarked(v))
}
|
Abschließend soll unser kleines Programm zum Interpretieren von
Linienzeichnungen natürlich auch einem Beispiel ausgetestet werden. Hierzu
nehmen wir noch einmal die Stufen an einer Wand. Um die einzelnen Kanten und
Ecken zu identifizieren seien sie einmal durchnumeriert, wie in
Abildung~ angegeben.
Im folgenden Programm werden die 26 Kanten mit null markiert und
die Szene mit den 19 Ecken gebildet. Dann wird nach einer legalen
Interpretation der Kanten gesucht:
| Stairs.scala |
package name.panitz.ki
object Stairs extends Application{
val e1 = new Edge(null)
val e2 = new Edge(null)
val e3 = new Edge(null)
val e4 = new Edge(null)
val e5 = new Edge(null)
val e6 = new Edge(null)
val e7 = new Edge(null)
val e8 = new Edge(null)
val e9 = new Edge(null)
val e10 = new Edge(null)
val e11 = new Edge(null)
val e12 = new Edge(null)
val e13 = new Edge(null)
val e14 = new Edge(null)
val e15 = new Edge(null)
val e16 = new Edge(null)
val e17 = new Edge(null)
val e18 = new Edge(null)
val e19 = new Edge(null)
val e20 = new Edge(null)
val e21 = new Edge(null)
val e22 = new Edge(null)
val e23 = new Edge(null)
val e24 = new Edge(null)
val e25 = new Edge(null)
val e26 = new Edge(null)
val vA = Arrow(e8,e2,e1)
val vB = Fork(e2,e5,e3)
val vC = Arrow(e4,e3,e7)
val vD = L(e1,e4)
val vE = Arrow(e6,e5,e9)
val vF = L(e7,e6)
val vG = L(e9,e25)
val vH = Arrow(e23,e11,e10)
val vI = Fork(e14,e12,e11)
val vJ = Arrow(e13,e12,e16)
val vK = Fork(e13,e8,e10)
val vL = Arrow(e17,e15,e14)
val vM = Fork(e20,e18,e17)
val vN = Arrow(e19,e18,e22)
val vO = Fork(e19,e16,e15)
val vP = Arrow(e21,e20,e24)
val vQ = L(e22,e21)
val vR = L(e26,e23)
val vS = T(e26,e25,e24)
var scene=new Scene()
scene++
List(vA,vB,vC,vD,vE,vF,vG,vH,vI,vJ,vK,vL,vM,vN,vO,vP,vQ,vR,vS)
val solution = scene.depthSearch
if (solution!=null){
for (val sol<-solution) scene=scene move sol
var c='A'
for (val v<-scene){
Console print c
Console print " "
Console println v
c=(c+1).asInstanceOf[Char]
}
}
}
|
Und tatsächlich, wenn das Programm gestartet wird, liefert es genau die
Interpretation der Szene, wie wir sie auch mit unserer Sehgewohnheit gemacht
hätten. sep@pc305-3:~/fh/ki/student> scala -cp classes/ name.panitz.ki.Stairs
A Arrow(<-,+,<-)
B Fork(+,+,+)
C Arrow(<-,+,<-)
D L(<-,<-)
E Arrow(<-,+,<-)
F L(<-,<-)
G L(<-,<-)
H Arrow(<-,+,<-)
I Fork(+,+,+)
J Arrow(-,+,-)
K Fork(-,<-,<-)
L Arrow(+,-,+)
M Fork(+,+,+)
N Arrow(-,+,-)
O Fork(-,-,-)
P Arrow(<-,+,<-)
Q L(-,<-)
R L(<-,<-)
S T(<-,<-,<-)
sep@pc305-3:~/fh/ki/student>
2.3 Suche mit problemspezifischer Information
Bisher haben die benutzen Suchverfahren keinerlei Information über das zu
lösende Problem benutzt. Wie schon bei dem sehr einfachen Schiebepuzzle zu
sehen war, waren sie auf Grund der exponentiellen Komplexität nicht in der
Lage, schon recht einfache Lösungen zu finden. Dieses Problem kann nur gelöst
werden, indem zusätzliches Wissen über das Problem benutzt wird. Was könnte
solch zusätzliches Wissen sein? Es könnte doch interssant sein, wie weit man
glaubt, vom Zielzustand entfernt zu sein. Wenn eine derartige Information
vorliegt, dann ist jeweils der Knoten aus dem fringe zum Expandieren
vorzuziehen, von dem man annimmt, daß er schon möglichst Nahe am Zielzustand ist.
Natürlich ist nicht davon auszugehen, daß wir exakt wissen, wie weit es
jeweils noch bis zum Ziel ist. Wir können nur auf eine heuristische
Abschätzung der realen Kosten zum Ziel hoffen.
2.3.1 Greedy-Best-First
Der Suchalgorithmus, der immer den Knoten aus dem fringe expandiert,
für den die Abschätzung der Entfernung zum Ziel möglichst gering ist wird
als Greedy-Best-First bezeichnet. Er läßt sich aus dem allgemeinen
Suchalgorithmus erhalten, indem neue Knoten in den fringe so
eingefügt werden, daß der fringe stets nach den abgeschätzten Kosten
sortiert ist.
In der Scalaimplementierung schreiben wir wieder eine spezielle allgemeine
Suchklasse, die nun eine zusätzliche Information verlangt, nämlich die
abgeschätzte Entfernung zum Ziel:
| InformedSearch.scala |
package name.panitz.ki
trait InformedSearch[M] extends DepthSearch[M] {
def estimatedGoalDistance():Int;
|
Die Implemetierung hat sich entschieden, die Entfernung als ganze Zahl
abzuschätzen. Der Greedy-Best-First ist jetzt die Suchstrategie, in
der sortiert in den fringe eingefügt wird. Und zwar sortiert, nach
der abgeschätzten Entfernung zum Ziel. Dazu benutzen wir eine lokale
Funktion, die entscheidet, welche Zustand in dieser Relation kleiner ist:
| InformedSearch.scala |
def greedyBestFirst():List[M]={
def le=(x:Path[M],y:Path[M])
=>(x._2.asInstanceOf[InformedSearch[M]].estimatedGoalDistance
<=
y._2.asInstanceOf[InformedSearch[M]].estimatedGoalDistance)
|
Bezüglich dieser Kleiner-Relation sind die neuen Elemente in
den fringe einzufügen:
Es bleibt noch die Einfügefunktion zu implementieren:
| InformedSearch.scala |
type LE[A]=(A,A)=>Boolean
def insert[A]:(LE[A],A,List[A])=>List[A]=(le,x,ys)=>{
var temp:List[A]=Nil
var rest=ys
while (!rest.isEmpty&& !le(x,rest.head)){
temp=rest.head :: temp
rest=rest.tail
}
temp.reverse ::: x :: rest
}
def insertAll[A]:(LE[A],List[A],List[A])=>List[A]=(le,xs,ys)=>{
if (ys.isEmpty) xs
else insertAll(le,insert(le,ys.head,xs),ys.tail)
}
|
Wie sieht es jetzt mit dem Greedy-Best-First Algorithmus in Bezug auf
das Auffinden einer optimalen Lösung aus? Hierzu betrachte man den Fall, daß
nicht alle Aktionen gleich teuer sind. Angenommen vom Startzustand z_0 gibt es
zwei Aktionen die zu einen Folgezustand führen. Die erste a_1 hat
Kosten von 1000, die zweite a_2 Kosten von 1. Der
Folgezustand zu a_1 sei nur noch 1 vom Ziel entfernt, der
Folgezustand zu a_2 sei 2 vom Ziel
entfernt. Greedy-Best-First wählt daher a_2 als erste Aktion
und erhält eine Lösung mit Gesamtkosten von 1001, es gibt aber eine
Lösung mit Gesamtkosten von lediglich 3.
2.3.2 A*-Suche
Die Abschätzung, wie weit das Ziel noch vermutet wird allein zum bestimmen des
zu expandierenden Knotens zu benutzen, reichte nicht aus, um eine optimale
Lösung zu finden. Es muß zusätzlich auch noch berücksichtigt werden, wieviel
Kosten der Pfad zu dem betrachteten Zustand bereits gekostet hat. Der
Algorithmus, der auch dieses noch mit in Betracht zieht, wird als A*-Suche
bezeichnet. Er expandiert den Knoten des fringe, für den die Summe
aus geschätzten Kosten bis zum Ziel und den bereits erzielten Kosten vom Start
minimiert wird.
Zur Implementierung des A*-Algorithmus wird zusätzlich noch eine Methode
benötigt, die für eine Pfad die Kosten ermittelt:
Dann läßt sich der A*-Algorithmus schreiben, indem nun in
den fringe nach minimierter Summe von der Pfaddistanz von der Wurzel
und der abgeschäützten Distanz zum Ziel sortiert eingefügt wird.
Dazu ist die Kleiner-Relation verfeinert zu implementieren:
| InformedSearch.scala |
def aStar():List[M]={
def le=(x:Path[M],y:Path[M])
=>(pathDistance(x._1)
+x._2.asInstanceOf[InformedSearch[M]].estimatedGoalDistance
<=
pathDistance(y._1)
+y._2.asInstanceOf[InformedSearch[M]].estimatedGoalDistance)
|
Der A*-Algorithmus benutzt diese Relation zum sortierten Einfügen in den fringe.
Wie sieht es mit den Algorithmus A* aus? Findet er eine optimale
Lösung. Das ist abhängig von der heuristischen Abschätzungsfunktion. Hierzu
stelle man sich einmal die Extremfälle vor:
- Die Abschätzung ist sehr optimistisch. Sie schätzt die Kosten wesentlich
geringer ab, als sie in der Tat sind. Die optimistischste Abschätzung ist
dabei die, die immer glaubt, man sei schon so gut wie am Ziel; im extremsten
Fall konstant 0 ist. Dann mutiert der A*-Algorithmus aber zur
Breitensuche. Es werden dann ja nur noch die real schon angefallenen
Pfadkosten zur Auswahl, welcher Knoten als nächstes expandiert werden soll
herangezogen. Das sind also die Knoten, die als nächstes zur Wurzel liegen,
und somit wird Breitensuche vollzogen. Da die Breitensuche eine optimale
Lösung findet, findet auch der A*-Algorithmus mit sehr optimistischer
Abschätzung eine optimale Lösung.
- Nun betrachte man zum Gegensatz eine sehr pessimistische
Abschätzung. Vom der Wurzel z_0 seien zwei
Nachfolgezustände z_1 und z_2
erreichbar. Die Pfadkosten zu z_1 und z_2 seien beide gleich k.
Von z_1 sei das Ziel mit Kosten 1 erreichbar,
von z_2 mit Kosten 3. Die Abschätzung schätze die Entfernung
von z_2 zum Ziel korrekt ab, die Entfernung von z_1 zum Ziel
jedoch pessimistisch mit 4. Der Algorithmus wählt den Pfad
über z_2 und erreicht das Ziel mit k+3. Der kürzere Weg
über z_1 wird übersehen, weil die letzte Etappe dieser
Allgemein gilt, die Abschätzung darf die realen Kosten nie überschätzen, dann
findet der A*-Algorithmus in der obigen Form eine optimale Lösung. Je genauer
die Abschätzung ist, umso leichter findet der Algorithmus eine Lösung. Wenn
die Abschätzungsfunktion mit den realen Kosten identisch ist, so kann die
optimale Lösung direkt gefunden werden, dann entspricht die
Abschätzungsfunktion einen Wegweiser, der bei jeder Weggabelung zeigt, in
welche Richtung der kürzeste Weg liegt.
2.3.3 Abschätzungen im Schiebespiel
Versuchen wir nun zum Abschluß den A*-Algorithmmus auf unser Schiebespiel
anzuwenden. Wir benötigen dabei eine möglichst gute Funktion, die die Kosten
zum Ziel abschätzt. Eine sehr einfache solche Funktion ist die Funktion, die
angibt, wieviel Plättchen noch auf einem falschen Feld liegen. Da in einem
Schritt genau ein Plättchen seine Position verändert, ist die Zahl der falsch
liegenden Plättchen immer kleiner als die Länge einer optimalen Lösung des
Schiebepuzzles. Es wird damit der Aufwand nicht überschätzt und diese
Abschätzung könnte im A*-Algorithmus benutzt werden, um eine optimale Lösung
zu suchen. Die Abschätzung ist aber nicht sehr genau. Es läßt sich eine
genauere Abschätzung finden: hierzu zähle man für jedes einzelne Plättchen,
wie oft es minimal verschoben werden müßte, um an seine korrekte Position zu
kommen. Dabei kann man sich idealisiert vorstellen, daß das jeweilige
Plättchen allein auf dem Spielfeld ist. Diese Zahl ist maximal vier und leicht
zu ermitteln.
Die Summe dieser Anzahlen für alle Plättchen kann als Abschätzung
dienen.
Folgende Klasse implementiert mit dieser Abschätzung den A*-Algorithmus für
das Schiebespiel. Wir implementieren eine InformedSearch
| InformedSlide.scala |
package name.panitz.ki
class InformedSlide(I:Int) extends DepthSlide(I)
with InformedSearch[Direction.Value]{
|
Die Abschätzung summiert für jedes Plättchen auf, in wieviel Schritten es
minimal auf seinen richtigen Platz verschoben werden kann.
| InformedSlide.scala |
def estimatedGoalDistance():Int={
var result=0;
for (val i<-Iterator.range(0,SIZE);val j<-Iterator.range(0,SIZE)){
val v=field(i)(j)
if (v>0){
val shouldY=v/SIZE
val shouldX=v%SIZE
result=result+Math.abs(shouldY-i)+Math.abs(shouldX-j)
}
}
result
}
|
Die realen Kosten eines Pfades seien weiterhin die Länge des Pfades:
Schließlich noch der Konstruktor und aus mehr technischen Gründen, das
Überschreiben der Methode move, damit diese auch
ein InformedSlide-Objekt zurückgibt.
| InformedSlide.scala |
def this(that:SlidePuzzle)={this(that.SIZE);copyFromThat(that)}
override def move(m:Direction.Value):InformedSlide={
val res=new InformedSlide(this)
res.move(m,res)
res
}
}
|
2.4 Spielbäume
Die Algorithmen in diesem Kapitel konnten bisher recht ungestört arbeiten. In
der Umwelt gab es nur einen Agenten, der ein statische Problem per Suche
gelöst hat. Wir werden jetzt das Problemfeld erschweren, indem es einen
zweiten konkurrierenden Agenten gibt. Dieses ist der Fall in klassischen 2
Parteien spielen. Die jeweiligen zwei Spieler sind konkurrierende Agenten,
denn sie verfolgen ganz unterschiedliche Pläne. Jeder will, daß seine Farbe
gewinnt. Auch das Problem, für einen Spieler einen möglichst guten Zug zu
finden, läßt sich mit Suche lösen. Nun entscheidet allerdings bei jeder
zweiten Ebene des Suchbaums, der konkurrierende Agent, welche der Alternativen
genommen wird. Unter der Berücksichtigung, daß der konkurrierende Agent
versucht seinerseits optimale Züge zu machen.
2.4.1 Min-Max-Suche
Das naheliegenste Verfahren, um einen optimalen Zug zu finden, wird
als Min-Max-Suche bezeichnet. Der Name bezieht sich darauf, daß im
Suchbaum abwechselnd Züge des Gegners und eigene Züge in den Baumebenen
wiedergespiegelt werden.
Um auf dem Baumebenen minimierte bzw. maximierte Äste zu wählen, ist zunächst
eine Bewertung des jeweiligen Spielstandes notwendig. Für einfache Spiele
reicht eine Bewertung auf Endzustände aus, d.h. auf Spielzustände, die
keinen weiteren Zug mehr zulassen, weil z.B. das Spielfeld voll ist. Diese
Zustände können mit 1, wenn der in Frage kommende Spieler gewonnen hat,
mit -1, wenn der in Frage kommende Spieler verloren hat, und
mit 0 im Falle eines Remis gewertet werden.
Für einen Spieler, der einen optimalen Zug sucht, sind die Ebenen, in denen
der nächste Zug vom ihm getätigt wird, zu optimierende Ebenen, die anderen
sind zu minimierende Ebenen. Der Algorithmus läßt sich unformell wie folgt
beschreiben:
- wenn es sich um einen Finalzustand handelt:
- dann bewerte den Zustand für den Spieler
- ansonsten:
- für jeden möglichen Zug bewerte mit Min-Max-Suche den Nachfolgezustand.
Wenn es sich auf der Ebene um einen eigenen Zug handelt, wähle den Zug, der
zur maximalen Bewertung führt, ansonsten den der zur minimalen Bewertung führt.
Implementierung
Wollen wir es also wagen, allgemein eine Suche nach der Gewinnstrategie eines
Spiels zu programmieren. Hierzu sei eine abstrakte Klasse geschrieben, in der
die Suche implementiert wird. Um was für ein konkretes Spiel es sich dabei
handelt, lassen wir zunächst einmal wieder offen. Da verschiedene Spiele auch
verschiedene Arten haben, einen Zug zu beschreiben, und lassen wir auch den Typ für
die Spielzüge zunächst wieder offen. Wir erhalten folgende Klasse:
| GameTree.scala |
package name.panitz.ki
trait GameTree[M] extends SearchTree[M]{
|
M drückt dabei den noch variabel gehaltenen Typ der Spielzüge
aus. Für die Spieler, wir werden ja in der Regel nur zwei haben, legen wir uns
hingegen auf einen Datentyp fest und wollen Byte, also 8 Bit Zahlen
benutzen:
Wir haben hier einen neuen Namen für den Typ Byte eingeführt. Etwas,
was in Java nicht möglich wäre, in C mit typedef allerdings Gang und
Gebe ist.
Zwei Funktionen seien vorgesehen. Eine, die den Spieler, der gerade am Zug
ist, angibt:
Eine zweite, die für einen Spieler den anderen Spieler angibt:
das wichtigste für einen Spielzustand sind natürlich die in diesem Zustand
möglichen gültigen Züge. Diese soll die folgende Funktion in einer Liste
zurückgeben. Was genau ein Zug ist, haben wir vorerst offen gelassen. Wir
sprechen nur vom Typ M bei Zügen.
Wenn wir uns im Endeffekt für einen Zug entschieden haben, den wir ausführen
möchten, so sollte dieser Zug auch auf den Spielzustand ausgeführt werden, um
einen Nachfolgezustand zu erhalten. Hierzu sehen wir die
Methode move vor:
Und wir brauchen eine Funktion, die uns sagt, wie der Spielzustand für uns
denn zu bewerten ist.
Die Min-Max-Suche wird für den jeweils am Zug seienden Spieler gestartet:
Die Min-Max-Suche hat einen Spieler als Parameter, für den die Suche gemacht
wird, und gibt als Ergebnis ein Paar zurück, bestehend aus der Bewertung des
Nachfolgezustandes für einen Zug:
Zunächst der Fall wenn bereits ein Terminalzustand vorliegt. Dann ist kein
weiterer Zug zu machen, daher wird die zweite Komponente des Ergenispaares
auf null gesetzt. Der Bewertung ist dann, die Bewertung des aktuellen
Zustands:
Andernfalls ist zu prüfen, ob man sich auf einer minimier oder maximier Ebene
befindet:
Davon abhängig wird der größer bzw. kleiner Vergleich gewählt und der maximale
bzw minimale Bewertungswert:
| GameTree.scala |
val exVal=if(doMax) Integer.MIN_VALUE else Integer.MAX_VALUE
def comp(x:Int,y:Int)=if (doMax) (x>y) else (x<y)
|
Schließlich wird über alle möglichen Züge iteriert, diese rekursiv bewertet,
und über die Ergebnisse das Maximum bzw. Minimum gewählt.
| GameTree.scala |
((for (val i:M <- moves().elements)
yield Pair(move(i).minMaxValue(forPlayer)._1,i))
.foldLeft(Pair(exVal,null:M))
((x,y)=>if (comp (x._1,y._1)) x else y))
}
}
|
Und das war es schon. Die Min-Max-Suche können wir zum Ziehen für unseren
Agenten benutzen.
\eject
TicTacToe
Tic Tac Toe (auch: XXO, Kreis und Kreuz, Dodelschach oder
engl. Noughts and Crosses) ist ein klassisches, einfaches
Zweipersonen-Strategiespiel, dessen Geschichte sich bis ins 12. Jahrhundert
v. Chr. zurückverfolgen lässt.
Auf einem 3×3 Felder großen Spielfeld machen die beiden Spieler abwechselnd
ihre Zeichen (Kreuze und Kreise). Der Spieler, der als erstes drei seiner
Zeichen in einer Reihe, Spalte oder einer der beiden Hauptdiagonalen setzen
kann, gewinnt. Wenn allerdings beide Spieler das Spiel perfekt beherrschen,
kann keiner gewinnen und es ist unentschieden.
Für Tic Tac Toe gibt es 255.168 verschiedene Spielverläufe, von denen 131.184
mit einem Sieg des ersten Spielers enden, 77.904 mit einem Sieg des zweiten
Spielers, und 46.080 mit einem Unentschieden. Viele Spielverläufe sind
äquivalent in dem Sinne, dass sie sich durch Drehungen oder Spiegelungen des
Spielfelds ineinander überführen lassen. Äquivalente Verläufe zusammengefasst,
reduziert sich die Zahl der verschiedenen Spielverläufe auf 26.830. Im
Vergleich zu Spielen wie Go, Dame oder Schach ist dies eine verschwindend
geringe Zahl. Aufgrund dieser geringen Komplexität lässt sich leicht zeigen,
dass beide Spieler ein Unentschieden erzwingen können.
Die erste und zweite Spielrunde sind die wichtigsten und ausschlagebensten
Runden im Spiel, um nicht zu verlieren. Wenn der Gegner beginnt, gibt es von
72 nur 44 Möglichkeiten.
Erster Spieler (X) beginnt, zweiter Spieler (O) verhindert, dass X gewinnt
(gespiegelte Möglichkeiten sind nicht dargestellt).
\begin{verbatim}
X| | O| | |X| |X| O|X|
-+-+- -+-+- -+-+- -+-+- -+-+-
|O |X| |O| | | | |
-+-+- -+-+- -+-+- -+-+- -+-+-
| | | | | | |O| | |
\end{verbatim}
Wegen seiner Einfachheit wird Tic Tac Toe oft als Beispiel zur Erläuterung
grundlegender Konzepte der Spieltheorie herangezogen. Spieltheoretisch
betrachtet gehört Tic Tac Toe zu den endlichen, deterministischen
Zweipersonen-Nullsummenspielen mit alternierendem Zugrecht und vollständiger
Information.
Jetzt soll natürlich unser erste Spielagent auch für ein konkretes Spiel
angewendet werden. Eines der einfachsten Spiele ist das sogenannte Tic
Tac Toe. Auf einem 3 mal 3 Felder großen Brett setzen abwechseln zwei
Spieler ihre Spielsteine. Ziel ist es drei Steine seiner Farbe in eine Reihe
zu bringen.
Wir implementieren ein GameTree und definieren ein paar konstante
Werte. Züge sind im Fall von Tic Tac Toe Paare, die die x- und y-Koordinate
des zu setzenden Spielfeldes repräsentieren.
| TicTacToe.scala |
package name.panitz.ki
class TicTacToe() extends GameTree[Pair[Int,Int]]{
val EMPTY :Player= 0
val PLAYER_ONE:Player= 1
val PLAYER_TWO:Player= 2
val C:Int = 3
val R:Int = 3
|
Ein zweidimensionaler Array halte das eigentliche Spielfeld und sei als
leeres Spielfeld initialisiert:
| TicTacToe.scala |
var field = new Array[Array[Player]](C)
var currentPlayer = PLAYER_ONE
for (val i <- Iterator.range(0,C)){
field(i)=new Array[Player](R)
for (val j <- Iterator.range(0,R))
field(i)(j)=EMPTY
}
|
Ein Konstruktor, der einen Spielzustand kopiert, sei implementiert:
| TicTacToe.scala |
def this(other:TicTacToe)={
this()
for (val i<-Iterator.range(0,R);val j<-Iterator.range(0,C))
field(j)(i)=other.field(j)(i)
}
|
Es folgen die Methode zum Erfragen der Spieler:
| TicTacToe.scala |
def getCurrentPlayer()=currentPlayer
def otherPlayer(player:Player):Player
=if (player==PLAYER_ONE)PLAYER_TWO else PLAYER_ONE
|
Um einen konkreten Zug durchzuführen, wird der aktuelle Zustand kopiert und
das entsprechende Feld mit dem aktuellen Spieler belegt:
| TicTacToe.scala |
def move(i:Pair[int,int]):GameTree[Pair[int,int]]={
val result=new TicTacToe(this)
result.field(i._1)(i._2)=getCurrentPlayer
result.currentPlayer = otherPlayer(currentPlayer)
result
}
|
Gültige Züge sind genau die Züge auf Felder, die noch leer sind.
| TicTacToe.scala |
def moves():List[Pair[Int,Int]]=
(for(val i<-Iterator.range(0,R);val j<-Iterator.range(0,C)
;field(j)(i)==EMPTY) yield Pair(j,i)).toList
|
Das Spiel terminiert, wenn einer der Spieler gewonnen hat oder das Brett voll
ist.
| TicTacToe.scala |
def terminalState():boolean =
wins(PLAYER_ONE)||wins(PLAYER_TWO)||boardFull()
def boardFull():boolean =
((for (val i<-Iterator.range(0,R);val j<-Iterator.range(0,C))
yield field(i)(j)).forall((x)=>x!=EMPTY))
|
Die Bewertungsfunktion ist wie in der Einleitung angedeutet,
relativ einfach gestrickt:
| TicTacToe.scala |
def evalState(player:Player)
=if (wins(player)) 1 else if(wins(otherPlayer(player))) -1 else 0
|
Sämtliche Siegespositionen für einen Spieler seien lediglich aufgelistet:
| TicTacToe.scala |
def wins(player:Player)=
(field(0)(0)==player&&field(0)(1)==player&&field(0)(2)==player)||
(field(1)(0)==player&&field(1)(1)==player&&field(1)(2)==player)||
(field(2)(0)==player&&field(2)(1)==player&&field(2)(2)==player)||
(field(0)(0)==player&&field(1)(0)==player&&field(2)(0)==player)||
(field(0)(1)==player&&field(1)(1)==player&&field(2)(1)==player)||
(field(0)(2)==player&&field(1)(2)==player&&field(2)(2)==player)||
(field(0)(0)==player&&field(1)(1)==player&&field(2)(2)==player)||
(field(2)(0)==player&&field(1)(1)==player&&field(0)(2)==player)
|
Die Klasse sei abgeschlossen mit einer toString-Methode, so daß
eventuell ein Spiel ohne GUI auf der Kommandozeile möglich wird:
| TicTacToe.scala |
override def toString()={
val result = new StringBuffer()
for (val i<-Iterator.range(0,R)){
for (val j<-Iterator.range(0,C))
result append ("|"+field(j)(R-i-1))
result append ("|"+(R-i-1)+"\n")
}
for (val j<-Iterator.range(0,C)) result append "--"
result append "--\n"
for (val j<-Iterator.range(0,C))result append ("|"+j)
result append "|\n"
result.toString()
}
}
|
Im folgenden eine kleine Anwendung, die es erlaubt gegen den Rechner Tic Tac
Toe zu spielen. Viel Spaß beim Spielen.
| PlayTicTacToe.scala |
package name.panitz.ki
object PlayTicTacToe extends Application {
var s:GameTree[Pair[Int,Int]]=new TicTacToe()
Console println s
while (!s.terminalState()){
Console println "Lassen Sie mich meinen Zug ueberlegen."
s=s.move()
Console println s
if (!s.terminalState()){
var userMove:Pair[Int,Int]=null
repeat{
Console println "Ihr Zug"
Console print " x: ";val x=Console.readInt
Console print " y: ";val y=Console.readInt
userMove =Pair[Int,Int](x,y)
} until {Console println userMove;Console println (s.moves());
s legalMove userMove}
s=s move userMove
Console println s
}
}
def repeat(body: => Unit)=new RepeatUntilCond(body)
class RepeatUntilCond(body: => Unit) {
def until(cond: => Boolean):Unit={body;if (!cond)until(cond);}
}
}
|
2.4.2 Alpha-Beta-Suche
2.5 Aufgaben
Aufgabe 1
Betrachten Sie das folgende Problem:
Bert, Bengt, Ernie und Cindy wollen einen Fluß überqueren. Sie haben
nur ein Boot. Bert und Bengt sind so schwer, daß Sie nur alleine mit dem Boot
fahren können. Ernie und Cindy können hingegen auch zusammen im Boot fahren.
In dieser Aufgabe sollen Sie das Problem als Suchproblem modellieren.
a) geben Sie eine möglichst einfache Modellierung für die auftretenden
Zustände an.
b) Zeichnen Sie den vollständigen Suchgraphen.
c) Geben Sie die Lösung für das Problem an.
Aufgabe 2
Gegeben sei die Karte von Rumänien aus Abbildung~.
An Straßen steht
jeweils die Entfernung zwischen den verbundenen Orten. Zusätzlich sei in
folgender Tabelle die Luftlinie von jedem Ort nach Bukarest bekannt.
|
Arad
|
366 |
Mehadia
|
241 |
|
Bucharest
|
0 |
Neamt
|
234 |
|
Craiova
|
160 |
Oradea
|
380 |
|
Drobeta
|
242 |
Pitesti
|
100 |
|
Eforie
|
161 |
Rimnicu Vilcea
|
193 |
|
Fagaras
|
176 |
Sibiu
|
253 |
|
Giurgiu
|
77 |
Timisoara
|
329 |
|
Hirsova
|
151 |
Urziceni
|
80 |
|
Iasi
|
226 |
Vaslui
|
199 |
|
Lugoj
|
244 |
Zerind
|
374 |
Zeigen
Sie, wie der A*-Algorithmus den kürzesten Weg von Arad nach Bukarest findet.
|
