Grundlagen KI - Blatt 3


Albert-Ludwigs-Universität Freiburg Kursvorlesung Grundlagen der KI Sommersemester 1999	Institut für Informatik Intelligente Autonome Systeme Dr. Wolfram Burgard Dipl.-Inf. Hatzack/Hoffmann

3. Übungsblatt
Abgabetermin: 7. Mai 1999

Aufgabe 3.1 (3 Punkte)

Spielen Sie das 8-Puzzle mit dem A*-Algorithmus durch, ausgehend von dem Zustand:

               1  6  2
               8     3
               7  5  4

Dabei soll der Zielzustand sein:

               1  2  3
               8     4
               7  6  5

Verwenden Sie dabei die beiden in der Vorlesung vorgestellten Heuristik-Funktionen ``Misplaced Tiles'' und Manhatten Distanz.

Aufgabe 3.2: (3 Punkte)

Beweisen Sie, daß IDA* optimale Lösungen liefert, sofern genügend Speicher für den längsten Pfad mit Kosten von höchstens f* vorhanden ist (f* = Kosten des optimalen Lösungspfades).

Aufgabe 3.3: (3 Punkte)

Zwei Spieler entfernen abwechselnd je eine, zwei oder drei Münzen von einem Stapel von Münzen. Derjenige Spieler, der die letzte Münze entfernt, hat verloren.

(a): Zeichnen Sie jeweils einen Spielgraphen für einen Ausgangszustand von 3, 4 und 5 Münzen. Verwenden Sie das Minimax-Verfahren, um die Gewinnmöglichkeiten der beiden Spieler zu analysieren.
(b): Wie sieht es allgemein bei einem Ausgangszustand von mindestens 3 Münzen aus?

Aufgabe 3.4: (1 Punkt)

Der Minimax Algorithmus ergibt den besten Zug för MAX unter der Voraussetzung, daß MIN optimal spielt. Was passiert, wenn dies nicht der Fall ist?