%% -------------------------------------------------------------- %% Datei: astar_8puzzle.pl %% Datum: 09.05.1998, 01.08.2002 %% Autor: Ralf Klinkenberg, Thorsten Joachims %% -------------------------------------------------------------- %% Programm zum Uebungsblatt 1, Aufgaben 1+2 (Kuenstliche Intelligenz SoSe 1998). %% Programm zum Uebungsblatt 6, Aufgaben 1+2 (Programmierkurs Prolog SoSe 2002). %% (A*-Algorithmus & Bergsteigen, 8-Puzzle) %% -------------------------------------------------------------- %% %% Bibliotheken fuer Listenfunktionen und Negation: % :- ensure_loaded(library(basics)). %% bei Quintus-Prolog, nicht bei SWI-Prolog % :- ensure_loaded(library(not)). %% bei Quintus-Prolog, nicht bei SWI-Prolog %% -------------------------------------------------------------- %% %% Aufgabe 6.1 + 6.2: A*-Algorithmus & Bergsteigen %% ------------------ %% %% Zwei Repraesentationsebenen: %% %% a) Repraesentation eines Spielzustandes (welcher Stein steht wo ?): %% %% Die Implementation von A* und Bergsteigen (im Praedikat 'suche') %% ist von dieser aufgabenspezifische Repraesentation unabhaengig, %% setzt sie aber ebenso als gegeben voraus wie ein Praedikat %% 'nachf(Z1,Z2,K)', dass zulaessige Uebergaenge zwischen jeweils %% einem solchen Spielzustaend Z1 und einem seiner Nachfolger, Z2, %% mit den fuer diesen Uebergang verbundenen Kosten K angibt. %% Ausserdem wird ein Praedikat 'zielzustand(Z)' vorausgesetzt, dass %% den gewuenschten Ziel-Spielzustand identifiziert (oder allgemeiner %% den oder die zulaessigen Zielzustaende des jeweils betrachteten %% Suchproblems). %% Die Repraesentation der Spielzustaende des 8-Puzzles, die zulaessigen %% Uebergaenge zwischen Spielzustaenden sowie die Bewertung von %% Spielzustaenden (Praedikat 'bewerte' zur Schaetzung der Restweglaenge %% von einem gegebenen Knoten aus) werden erst nach dem A*-Algorithmus %% und dem Bergsteigen beschrieben. %% %% b) Repraesentation eines Knotens im Suchraum, der neben dem aktuellen %% Spielzustand Informationen zum bisherigen Pfad, den bisherigen %% Kosten und den geschaetzten Restkosten enthaelt, in einer Struktur %% mit dem (willkuerlich gewaehlten) Namen 'pfad': %% %% pfad(F_K,G_K,H_K,K,Pfad) %% %% mit G_K : g(K), die realen Kosten fuer den Pfad vom %% Start-Spielzustand zum aktuellen Spielzustand K. %% H_K : h(K), die geschaetzten Kosten fuer den Weg vom %% Spielraumknoten K zum Ziel, die kleiner oder gleich %% den realen Kosten h*(K) fuer diesen Restweg sein muessen, %% damit A* ein zulaessiges Suchverfahren ist. %% F_K : f(K) = g(K) + h(K), die geschaetzen Kosten fuer den %% gesamten Weg vom Start zum Ziel ueber den Zustand K. %% K : aktueller Spielzustand. %% Pfad : der bisherige Pfad vom Start-Spielzustand zu K, %% als Liste der Spielzustaende auf diesem Pfad in %% umgekehrter Reihenfolge und noch ohne K, d.h. der %% direkte Vorgaengerspielzustand vom K ist das erste %% Element der Liste (wenn es einen Vorgaengerzustand %% gab). %% %% Die Sortierung der offenen Nachfolgezustaende erfolgt mit dem %% Prolog-Praedikat 'sort' (siehe 'help(sort).'), dass eine Liste von %% Termen in die lexikalische Standard-Prolog-Reihenfolge bringt. %% Mit 'sort' wird eine Liste von 'pfad'-Strukturen (Suchraumknoten) %% also nach den geschaetzten Gesamtkosten F_K sortiert (und bei %% gleichen geschaetzten Gesamtkosten nach den bisherigen realen %% Kosten G_K, etc.), weil F_K die erste Komponente der Struktur %% 'pfad' ist. %% Praedikat zum Starten des Suchprozesses, das den Start-Spielzustand %% auf den zugehoerigen Suchraumknoten abbildet, die Suche startet und %% die Anzahl der zum Erreichen des Ziels benoetigten Expansionen sowie %% den Suchraumknoten mit der Loesung liefert, der unter anderen den %% Pfad der Spielzustaende zum Ziel sowie die Kosten dieses Pfades umfasst: %% start( Startzustand+, Expansionen-, Loesung- ) start(Startzustand,Expansionen,Loesung) :- suche([pfad(0,0,0,Startzustand,[])],[],0,Expansionen,Loesung). %% A*-Suche (und Bergsteigen durch Aendern einer Zeile in 'sortiere'): %% suche( Offen+, Geschlossen+, AnzahlBisherigerExpansionen+, %% AnzahlExpansionenDerLoesung-, Loesung- ) suche([Aktuell|_],_Geschl,Expansionen,Expansionen,Aktuell) :- ziel(Aktuell). %% Ende der Suche: Ziel erreicht (aktueller gleich Ziel-Suchraumknoten) suche([],_Geschl,Expansionen,Expansionen,[]). %% Ende der Suche: keine Loesung gefunden ('Offen' ist leer und Ziel %% nicht erreicht). %% Expandierung des aktuell besten, noch offenen (Suchraum)Zustands %% (= erstes Element in der 'Offen'-Liste): suche([Aktuell|Offen],Geschl,Expansionen,ExpansionenErg,Loesung) :- % write(Aktuell),nl, nachfolger(Aktuell,Geschl,Nachf), %% Ermitteln aller noch zu %% betrachtenden Nachfolger sortiere(Offen,Nachf,OffenNeu), %% Aktualisiere & sortiere die Vereinigung %% der Menge offener Knoten und der %% Menge der aktuellen Nachfolger ExpansionenNeu is Expansionen+1, suche(OffenNeu,[Aktuell|Geschl],ExpansionenNeu,ExpansionenErg,Loesung). %% Bestimme alle noch zu betrachtenden Nachfolger-Suchraum-Zustaende des %% Suchraum-Zustands mit dem Spielzustand K: nachfolger(pfad(_,G,_,K,P),Geschl,Nachf) :- findall(pfad(F1,G1,H1,K1,[K|P]), %% Ermittle alle (Spielzustand-)Nachfolger (nachf(K,K1,Kosten), %% K1 von K mit realen Kosten des %% Wegs zu ihnen bewerte(K1,H1), %% Schaetze Restkosten von K1 aus %% entsprechend aktueller Heuristik G1 is G+Kosten, %% Berechne neue reale Kosten F1 is G1+H1, %% Berechne geschaetzte Gesamtkosten \+ (member(pfad(_,G2,_,K1,_),Geschl), %% betrachte noch nicht G1 >= G2)), %% geschlossene Nachfolger Nachf). %% sowie auch geschlossene, %% wenn sie jetzt mit %% kuerzerem realen Weg %% erreichbar sind %% Sortierte (Nachfolger)Liste: eine Zeile fuer den A*-Algorithmus %% (Aufgabe 1.1) und eine Zeile fuer das Bergsteigen (Aufgabe 1.2), %% d.h. die jeweils andere ist auszukommentieren; %% die dritte Klausel ist beiden gemein: %% sortiere( Offen+, Nachfolger+, OffenNeu- ) sortiere(Offen,[],OffenNeu) :- sort(Offen,OffenNeu). %% A*-Algorithmus % sortiere(Offen,[],[A]) :- sort(Offen,[A|_]). %% Bergsteigen %% (nur aktuell bestes %% Element behalten, %% den Rest verwerfen) sortiere(Offen,[pfad(F,G,H,K,P)|Nachf],OffenNeu) :- %% beide Verfahren ((member(pfad(FAlt,GAlt,HAlt,K,PAlt),Offen), G < GAlt) -> (append(Vor,[pfad(FAlt,GAlt,HAlt,K,PAlt)|Nach],Offen), append(Vor,Nach,Offen2)); %% Entferne alten Suchraumknoten mit Offen2 = Offen), %% groesseren realen Kosten fuer %% aktuellen Spielraumknoten sortiere([pfad(F,G,H,K,P)|Offen2],Nachf,OffenNeu). %% Abbildung Problemraum-Zielzustand <-> Spiel-Zielzustand ziel(pfad(_,_,_,K,_)) :- zielzustand(K). %% -------------------------------------------------------------- %% %% Repraesentation der Zustaende des 8-Puzzle: %% %% Die Belegung der neun Felder wird in einer linearen Liste gespeichert. %% Die Nummerierung der Felder erfolgt dabei im Uhrzeigersinn links oben %% startend: %% %% Spielfeld: X1 X2 X3 Liste: %% X8 X9 X4 ==> L = [X1,X2,X3,X4,X5,X6,X7,X8,X9] %% X7 X6 X5 %% %% Beispiel von Aufgabenblatt 1 aus dem SoSe 1998: %% %% s: 2 8 3 %% 1 6 4 ==> L = [2,8,3,4,leer,5,7,1,6] %% 7 5 _ %% %% z: 1 2 3 %% 8 _ 4 ==> L = [1,2,3,4,5,6,7,8,leer] %% 7 6 5 %% %% Sachbereich: Nachfolger-Relation zulaessiger Zustaende fuer 8-Puzzle nachf([A,B,C,D,E,F,G,H,leer],[A,leer,C,D,E,F,G,H,B],1). %% Verschiebung von nachf([A,B,C,D,E,F,G,H,leer],[A,B,C,leer,E,F,G,H,D],1). %% der Mitte an den nachf([A,B,C,D,E,F,G,H,leer],[A,B,C,D,E,leer,G,H,F],1). %% Rand nachf([A,B,C,D,E,F,G,H,leer],[A,B,C,D,E,F,G,leer,H],1). nachf([A,leer,C,D,E,F,G,H,I],[A,I,C,D,E,F,G,H,leer],1). %% Verschiebung vom nachf([A,B,C,leer,E,F,G,H,I],[A,B,C,I,E,F,G,H,leer],1). %% Rand in die nachf([A,B,C,D,E,leer,G,H,I],[A,B,C,D,E,I,G,H,leer],1). %% Mitte nachf([A,B,C,D,E,F,G,leer,I],[A,B,C,D,E,F,G,I,leer],1). nachf([leer,A,B,C,D,E,F,G,H],[G,A,B,C,D,E,F,leer,H],1). %% Sonderfaelle der nachf([G,A,B,C,D,E,F,leer,H],[leer,A,B,C,D,E,F,G,H],1). %% folgenden Ver- %% schiebung entlang %% des Randes nachf([leer,A|Rest],[A,leer|Rest],1). %% Verschiebung entlang des Randes nachf([A,leer|Rest],[leer,A|Rest],1). nachf([A|Rest],[A|Rest2],Kosten) :- %% Uebergang zur naechsten Position \+ A=leer, nachf(Rest,Rest2,Kosten). %% -------------------------------------------------------------- %% %% Gewuenschter Zielzustand (Endstellung): zielzustand([1,2,3,4,5,6,7,8,leer]). %% -------------------------------------------------------------- %% %% Heuristiken zur Bewertung von Zwischenloesungen beim 8-Puzzle: %% %% bewerte( K+, Kosten- ) liefert die geschaetzten Kosten fuer den Weg %% vom aktuellen Spielzustand K zum Zielzustand % bewerte(K,Kosten) :- bewerte1(K,Kosten). %% Heuristik 1 % bewerte(K,Kosten) :- bewerte2(K,Kosten). %% Heuristik 2 bewerte(K,Kosten) :- bewerte3(K,Kosten). %% Heuristik 3 %% Heuristik 1: Breitensuche (h = 0) (Breitensuche bei A*; %% Tiefensuche bei Bergsteigen, %% allerdings ohne Back-Tracking) bewerte1(_,0). %% Heuristik 2: Anzahl Fehler (h = Anzahl der Teile auf falscher Position; %% Hinweis: Das Leerfeld wird nicht gezahelt, %% auch wenn es an der falschen Stelle liegt, %% denn sonst gilt eventuell h(K) =< h*(K) %% nicht mehr) bewerte2(K,H):- %% Anzahl Teile an falscher Position zielzustand(Ziel), mismatches(K,Ziel,0,H). %% Achtung, genau ein Zielzustand mismatches([],[],Erg,Erg). mismatches([H1|L1],[H2|L2],X,Erg) :- (H1 = H2 -> %% if-then-else: Falls H1 = H2, dann bleibt die XNeu = X; %% Anzahl der Fehler unveraendert, sonst waechst XNeu is X+1), %% sie um eins (weiterer Fehler identifiziert) mismatches(L1,L2,XNeu,Erg). %% Heuristik 3: Manhattan Distanz (nur rechtwinklige Wege statt Luftlinie, %% Kosten als Summe der Manhattan Distanzen %% aller Steine zu ihren Soll-Positionen) bewerte3(K,Kosten) :- bewerte3(1,K,0,Kosten). %% Gemaess der beschriebenen Repraesentation eines Spielzustands und des %% gegebenen Zielzustands, sollte an der i-ten Position der Liste die %% Zahl i stehen (Stein mit Zahl i). Fuer jede Position in der Liste wird %% ermittelt, wieviele Zuege man mindestens braucht, um den jeweiligen Stein %% auf seine Zielposition zu bringen. Die Anzahl der minimal notwendigen %% Zuege wird nach unten durch die Manhattan Distanz beschraenkt. %% %% bewerte3( AktuelleSpielfeldPosition+, Spielzustand+, BisherigeKosten+, %% ErgebnisKosten- ) bewerte3(_,[],Kosten,Kosten). %% Spielfeld abgearbeitet: Gib bisherige %% Kosten (Summe der Distanzen) als Ergebnis %% (Gesamtkosten fuer den Restweg) zurueck bewerte3(P,[A|Rest],Kosten,Erg) :- %% Das Leerfeld (A=leer) wird nicht (A=leer; P=A), %% gezaehlt, ebenso Steine an der PNeu is P+1, %% richtigen Stelle (A=P); bewerte3(PNeu,Rest,Kosten,Erg). %% Untersuche die naechste Position bewerte3(P,[A|Rest],Kosten,Erg) :- %% A steht nicht an der Zielposition P \+ A=leer, %% und ist auch nicht das Leerfeld \+ A=P, (P > A -> (X1=P, X2=A); (X1=A, X2=P)), %% also: X1 > X2 D1 is X1-X2, %% Abstand X1<->X2 vorwaerts in der Liste D2 is X2+8-X1, %% Abstand X1<->X2 rueckwaerts in der Liste D is min(D1,D2), %% Waehle kleineren der beiden Abstaende (X1 = 9 -> %% Sonderfall: X1 ist Mittelfeld und (member(X2,[1,3,5,7]) -> Distanz=2; %% X2 ist Eckfeld oder Distanz=1); %% X2 ist Mittelrandfeld; ((member(X1,[1,3,5,7]); %% X1 ist nicht Mittelfeld, aber member(X2,[1,3,5,7])) -> Distanz=D; %% X1 oder X2 ist Eckfeld; Distanz=2)), %% X1 und X2 Mittelrandfelder; PNeu is P+1, %% Bestimme naechste Position KostenNeu is Kosten+Distanz, %% Addiere aktuelle Distanz zu Gesamtkosten bewerte3(PNeu,Rest,KostenNeu,Erg). %% Bewerte alle folgenden Positionen %% -------------------------------------------------------------- %% %% Anmerkung zum Programm fuer die beiden Aufgaben und die drei Heuristiken: %% ------------------------------------------------------------------------- %% Um zwischen den beiden Aufgaben zu wechseln, muss man beim %% Praedikat 'sortiere' (siehe oben beim Algorithmen-Abschnitt) %% die jeweils passende Klausel fuer Bergsteigen bzw. A* verwenden %% und die jeweils andere auskommentieren. %% Um zwischen den Heuristiken umzuschalten, ist das Praedikat %% 'bewerte' auf das entsprechende Praedikat 'bewerte1', 'bewerte2' %% bzw. 'bewerte3' abzubilden (siehe oben beim Heuristiken-Abschnitt). %% %% %% Aufgabe 6.1: A*-Algorithmus %% ------------ -------------- %% Heuristik 1: h = 0 (Breitensuche) %% %% ?- start([2,8,3,4,leer,5,7,1,6],AnzahlExpandierterKnoten,Pfad). %% %% AnzahlExpandierterKnoten = 51, %% Pfad = pfad(6,6,0,[1,2,3,4,5,6,7,8,leer], %% [[1,2,3,4,5,6,7,leer,8], %% [leer,2,3,4,5,6,7,1,8], %% [2,leer,3,4,5,6,7,1,8], %% [2,8,3,4,5,6,7,1,leer], %% [2,8,3,4,5,leer,7,1,6], %% [2,8,3,4,leer,5,7,1,6]]) %% %% Heuristik 2: h = Anzahl der Teile auf falscher Position %% %% AnzahlExpandierterKnoten = 7, %% Pfad = pfad(6,6,0,[1,2,3,4,5,6,7,8,leer], %% [[1,2,3,4,5,6,7,leer,8], %% [leer,2,3,4,5,6,7,1,8], %% [2,leer,3,4,5,6,7,1,8], %% [2,8,3,4,5,6,7,1,leer], %% [2,8,3,4,5,leer,7,1,6], %% [2,8,3,4,leer,5,7,1,6]]) %% %% Heuristik 3: h = Manhattan-Distanz %% %% AnzahlExpandierterKnoten = 6, %% Pfad = pfad(6,6,0,[1,2,3,4,5,6,7,8,leer], %% [[1,2,3,4,5,6,7,leer,8], %% [leer,2,3,4,5,6,7,1,8], %% [2,leer,3,4,5,6,7,1,8], %% [2,8,3,4,5,6,7,1,leer], %% [2,8,3,4,5,leer,7,1,6], %% [2,8,3,4,leer,5,7,1,6]]) %% %% Laenge des kuerzesten Weges inklusive Start- und Zielzustand: %% 7 Zustaende, also 6 Uebergaenge (Spielzuege). %% %% -------------------------------------------------------------- %% %% Aufgabe 6.2: Bergsteigen %% ------------ ----------- %% Heuristik 1: h = 0 (Tiefensuche ohne Back-Tracking) %% %% ?- start([2,8,3,4,leer,5,7,1,6],AnzahlExpandierterKnoten,Pfad). %% %% no %% %% ==> keine Loesung gefunden, weil der erste Zweig der %% Tiefensuche fehlgeschlagen ist ! %% %% Heuristik 2: h = Anzahl der Teile auf falscher Position %% %% AnzahlExpandierterKnoten = 10, %% Pfad = pfad(10,10,0,[1,2,3,4,5,6,7,8,leer], %% [[1,leer,3,4,5,6,7,8,2], %% [leer,1,3,4,5,6,7,8,2], %% [8,1,3,4,5,6,7,leer,2], %% [8,1,3,4,5,6,7,2,leer], %% [8,leer,3,4,5,6,7,2,1], %% [leer,8,3,4,5,6,7,2,1], %% [2,8,3,4,5,6,7,leer,1], %% [2,8,3,4,5,6,7,1,leer], %% [2,8,3,4,5,leer,7,1,6], %% [2,8,3,4,leer,5,7,1,6]]) %% %% ==> suboptimaler Pfad gefunden mit 10 statt 6 Zuegen ! %% %% Heuristik 3: h = Manhattan-Distanz %% %% AnzahlExpandierterKnoten = 6, %% Pfad = pfad(6,6,0,[1,2,3,4,5,6,7,8,leer], %% [[1,2,3,4,5,6,7,leer,8], %% [leer,2,3,4,5,6,7,1,8], %% [2,leer,3,4,5,6,7,1,8], %% [2,8,3,4,5,6,7,1,leer], %% [2,8,3,4,5,leer,7,1,6], %% [2,8,3,4,leer,5,7,1,6]]) %% %% ==> optimaler Pfad mit 6 Zuegen gefunden. %% %% --------------------------------------------------------------