Aufgaben PAI

Quiz: Grundlagen der Künstlichen Intelligenz

Grundlagen der KI

Frage 1 von 4

Welche Arten von AI-Agenten gibt es?

Python-Aufgaben: Grundlagen für Labyrinth-Navigation

Aufgabe 1: Koordinate eines Elements finden

Schreibe eine Funktion finde_koordinate(liste_2d, element), die die Koordinate (x, y) eines Elements in einer 2D-Liste zurückgibt. Wenn das Element nicht gefunden wird, soll None zurückgegeben werden.

Beispiel:

labyrinth = [
    [0, 0, 1],
    [0, 'S', 0],
    [1, 0, 'G']
]
koordinate = finde_koordinate(labyrinth, 'S')  # Sollte (1, 1) zurückgeben

Aufgabe 2: Element an Koordinate abrufen

Schreibe eine Funktion hole_element(liste_2d, x, y), die eine 2D-Liste, x- und y-Koordinaten bekommt und das Element an dieser Koordinate zurückgibt. Wenn die Koordinate außerhalb der Liste liegt, soll None zurückgegeben werden.

Beispiel:

labyrinth = [
    [0, 0, 1],
    [0, 'S', 0],
    [1, 0, 'G']
]
element = hole_element(labyrinth, 1, 1)  # Sollte 'S' zurückgeben

Aufgabe 3: Direkte Nachbarn finden

Schreibe eine Funktion finde_nachbarn(liste_2d, x, y), die die Koordinaten der direkten Nachbarn (Manhattan-Distanz = 1) einer Koordinate in einer 2D-Liste zurückgibt. Die Nachbarn sind die Zellen direkt oben, unten, links und rechts. Berücksichtige die Grenzen der Liste.

Beispiel:

labyrinth = [
    [0, 0, 1],
    [0, 'S', 0],
    [1, 0, 'G']
]
nachbarn = finde_nachbarn(labyrinth, 1, 1)  
# Sollte [(0, 1), (2, 1), (1, 0), (1, 2)] zurückgeben

Aufgabe 4: Nachbarn mit Kriterium finden

Schreibe eine Funktion finde_nachbarn_mit_kriterium(liste_2d, x, y, wert), die die Koordinaten der Nachbarn einer Koordinate zurückgibt, welche einem Kriterium entsprechen (gleich dem Parameter wert der Funktion sind).

Beispiel:

labyrinth = [
    [0, 0, 1],
    [0, 'S', 0],
    [1, 0, 'G']
]
freie_nachbarn = finde_nachbarn_mit_kriterium(labyrinth, 1, 1, 0)  
# Sollte [(0, 1), (2, 1), (1, 0), (1, 2)] zurückgeben (alle mit Wert 0)

Labyrinth-Aufgabe

Gegeben ist das folgende Labyrinth:

S . . . . .
. X X X . .
. . . . . .
. X X X . .
. . . . . G

Wobei:

• S = Start
• G = Ziel
• . = freier Weg
• X = Wand

Aufgaben:

1. Markiere den schnellsten Weg zum Ziel - Zeichne den kürzesten Pfad von S zu G ein.

2. Wie viele Wege findest du? - Zähle alle möglichen Wege von S zu G (ohne zurückzugehen).

3. Findest du eine Strategie, die immer funktioniert? - Beschreibe eine Suchstrategie, die garantiert einen Weg findet, wenn einer existiert. Welche Eigenschaften muss diese Strategie haben?

Türme von Hanoi

Gegeben sind die Türme von Hanoi mit 3 Scheiben. Die Scheiben sind unterschiedlich groß und müssen von Stab A nach Stab C bewegt werden, wobei:

• Nur eine Scheibe zur Zeit bewegt werden darf
• Nur die oberste Scheibe eines Stabes bewegt werden darf
• Eine größere Scheibe darf nie auf eine kleinere gelegt werden

Aufgabe:

Zeichne einen Baum/Graph, der alle möglichen Zustände zeigt, die beim Lösen des Problems mit 3 Scheiben erreicht werden können. Beginne mit dem Startzustand (alle Scheiben auf Stab A) und zeige, wie sich die Zustände verzweigen, bis das Ziel erreicht ist (alle Scheiben auf Stab C).

Tipp: Jeder Knoten im Graph repräsentiert einen Zustand (welche Scheiben sind auf welchem Stab). Jede Kante repräsentiert einen gültigen Zug.

Angeleitete Implementation: BFS (Breitensuche)

In dieser Aufgabe implementierst du Schritt für Schritt die Breitensuche (BFS) für ein Labyrinth.

Funktionssignatur:

def bfs(map, start_char, goal_char):
    # Gibt den Pfad von Start zu Ziel zurück (Liste von Koordinaten)
    # Falls kein Pfad gefunden wird, gibt None zurück
    pass

Map-Format: Die map ist eine 2D-Liste mit folgenden Werten:

• 0: freie Zelle
• 1: besetzte Zelle (Wand)
• "S": Start
• "A": Agent (optional)
• "G": Goal (Ziel)

BFS Implementation - Breitensuche

Schritt 1 von 9

Schritt 1: Queue-Klasse implementieren

Implementiere eine eigene Queue-Klasse für BFS. Eine Queue funktioniert nach dem FIFO-Prinzip (First In, First Out) - das erste Element, das hinzugefügt wird, wird auch als erstes entfernt. Erstelle eine Klasse Queue mit folgenden Methoden:

• init(self): Initialisiert eine leere Liste
• enqueue(self, element): Fügt ein Element am Ende hinzu
• dequeue(self): Entfernt und gibt das erste Element zurück
• is_empty(self): Gibt True zurück, wenn die Queue leer ist

Die Klasse sollte eine interne Liste self.items verwenden. Die Methode enqueue fügt am Ende hinzu (append), dequeue entfernt vom Anfang (pop(0)), und is_empty prüft ob die Liste leer ist.

Mazes Code

Mit dem Code im Ordner mazes im folgenden Repository kannst du deine Such-Algorithmen visualisieren: Mazes

Angeleitete Implementation: DFS (Tiefensuche)

In dieser Aufgabe implementierst du Schritt für Schritt die Tiefensuche (DFS) für ein Labyrinth. DFS funktioniert ähnlich wie BFS, verwendet aber einen Stack statt einer Queue.

Funktionssignatur:

def dfs(map, start_char, goal_char):
    # Gibt den Pfad von Start zu Ziel zurück (Liste von Koordinaten)
    # Falls kein Pfad gefunden wird, gibt None zurück
    pass

Map-Format: Die map ist eine 2D-Liste mit folgenden Werten:

• 0: freie Zelle
• 1: besetzte Zelle (Wand)
• "S": Start
• "A": Agent (optional)
• "G": Goal (Ziel)

DFS Implementation - Tiefensuche

Schritt 1 von 10

Schritt 1: Stack-Klasse implementieren

Implementiere eine eigene Stack-Klasse für DFS. Ein Stack funktioniert nach dem LIFO-Prinzip (Last In, First Out) - das letzte Element, das hinzugefügt wird, wird als erstes entfernt. Erstelle eine Klasse Stack mit folgenden Methoden:

• init(self): Initialisiert eine leere Liste
• push(self, element): Fügt ein Element am Ende hinzu
• pop(self): Entfernt und gibt das letzte Element zurück
• is_empty(self): Gibt True zurück, wenn der Stack leer ist

Die Klasse sollte eine interne Liste self.items verwenden. Die Methode push fügt am Ende hinzu (append), pop entfernt vom Ende (pop() ohne Index), und is_empty prüft ob die Liste leer ist.

Angeleitete Implementation: Greedy Best-First Search

In dieser Aufgabe implementierst du Schritt für Schritt die gierige Bestensuche (Greedy BFS) für ein Labyrinth. Greedy BFS nutzt eine Heuristik, um immer den vielversprechendsten Zustand zuerst zu erkunden.

Funktionssignatur:

def greedy_bfs(map, start_char, goal_char):
    # Gibt den Pfad von Start zu Ziel zurück (Liste von Koordinaten)
    # Falls kein Pfad gefunden wird, gibt None zurück
    pass

Map-Format: Die map ist eine 2D-Liste mit folgenden Werten:

• 0: freie Zelle
• 1: besetzte Zelle (Wand)
• "S": Start
• "A": Agent (optional)
• "G": Goal (Ziel)

Greedy BFS Implementation - Gierige Bestensuche

⋯

Schritt 1 von 12

Schritt 1: Heuristik-Funktionen implementieren

Implementiere zwei Heuristik-Funktionen: Manhattan-Distanz und Euklidische Distanz. Diese Funktionen schätzen die Entfernung von einem Punkt zum Ziel.

Manhattan-Distanz: Die Summe der absoluten Differenzen in x- und y-Richtung. Formel: |x1 - x2| + |y1 - y2|. Perfekt für Gitter mit 4-Richtungs-Bewegung.

Euklidische Distanz: Die Luftlinie zwischen zwei Punkten. Formel: √((x1 - x2)² + (y1 - y2)²). Benötigt math.sqrt().

Aufgabe: Erstelle zwei Funktionen:

• manhattan_distanz(x1, y1, x2, y2)
• euklidische_distanz(x1, y1, x2, y2)

Beide geben einen numerischen Wert zurück.

Angeleitete Implementation: A* Search

In dieser Aufgabe implementierst du Schritt für Schritt den A*-Algorithmus für ein Labyrinth. A* kombiniert die Vorteile von BFS (findet kürzesten Pfad) und Greedy BFS (nutzt Heuristik) und ist garantiert optimal, wenn die Heuristik zulässig ist.

Funktionssignatur:

def a_stern(map, start_char, goal_char):
    # Gibt den Pfad von Start zu Ziel zurück (Liste von Koordinaten)
    # Falls kein Pfad gefunden wird, gibt None zurück
    pass

Map-Format: Die map ist eine 2D-Liste mit folgenden Werten:

• 0: freie Zelle
• 1: besetzte Zelle (Wand)
• "S": Start
• "A": Agent (optional)
• "G": Goal (Ziel)

A* Implementation - A-Stern Algorithmus

⋯

Schritt 1 von 14

Schritt 1: Heuristik-Funktionen sicherstellen

A* benötigt die gleichen Heuristik-Funktionen wie Greedy BFS. Falls du sie noch nicht implementiert hast, hole das jetzt nach.

Aufgabe: Stelle sicher, dass du manhattan_distanz(x1, y1, x2, y2) und optional euklidische_distanz(x1, y1, x2, y2) implementiert hast.

Erinnerung:

• Manhattan: |x1 - x2| + |y1 - y2|
• Euklidisch: √((x1 - x2)² + (y1 - y2)²)

Für unsere Labyrinth-Aufgabe verwenden wir Manhattan-Distanz.

Projekt: Kingsheep - AI Agent Competition

In diesem Projekt wendest du deine gelernten Suchalgorithmen in einem echten Spiel an! Kingsheep ist ein Zwei-Spieler-Spiel, bei dem zwei Schafe um Essen (Gras und Rhabarber) konkurrieren.

Repository: https://github.com/cbrasser/kingsheep-newfield

Das Spiel

Spielfeld:

• Ein 2D-Gitter mit Zäunen (#), freien Feldern (.), Gras (g), und Rhabarber (r)
• Zwei Schafe: Schaf 1 (S) und Schaf 2 (s)

Regeln:

• Schafe können sich in 4 Richtungen bewegen: HOCH, RUNTER, LINKS, RECHTS
• Schafe können nicht durch Zäune gehen
• Gras gibt 1 Punkt, Rhabarber gibt 5 Punkte
• Das Spiel läuft für 100 Runden
• Das Schaf mit den meisten Punkten gewinnt!

Ziel: Programmiere einen Agenten, der intelligent Essen sammelt und den Gegner übertrumpft!

Aufgabe 1: Setup und erste Schritte

Kingsheep Setup

Schritt 1 von 5

Schritt 1: Projekt herunterladen

Lade das Kingsheep-Projekt herunter und öffne es in deiner Entwicklungsumgebung.

Option 1: Mit Git (empfohlen):

1. Clone das Repository: git clone https://github.com/cbrasser/kingsheep-newfield.git
2. Navigiere in den Ordner: cd kingsheep-newfield

Option 2: Als ZIP herunterladen:

1. Gehe zu https://github.com/cbrasser/kingsheep-newfield
2. Klicke auf den grünen "Code" Button
3. Wähle "Download ZIP"
4. Entpacke die ZIP-Datei
5. Navigiere in den entpackten Ordner

Dann für beide Optionen:

• Installiere die Abhängigkeiten: pip install pygame
• Teste das Spiel: Führe python kingsheep_simple.py aus

Was du siehst: Zwei zufällige Schafe bewegen sich auf dem Spielfeld und sammeln Essen.

Aufgabe 2: Hilfsfunktionen implementieren

Kingsheep Hilfsfunktionen

Schritt 1 von 5

Schritt 1: Position finden

Erstelle eine Hilfsfunktion, die die Position deines Schafs findet.

Aufgabe: Implementiere get_player_position(board, player_nr):

def get_player_position(board, player_nr):
    # Player 1 hat Schaf "S", Player 2 hat Schaf "s"
    char = "S" if player_nr == 1 else "s"
    
    # Suche in board nach diesem Zeichen
    for y in range(len(board)):
        for x in range(len(board[y])):
            if board[y][x] == char:
                return (y, x)
    return None

Diese Funktion gibt ein Tupel (y, x) zurück mit der Position des Schafs.

Aufgabe 3: BFS-Agent implementieren

Kingsheep BFS Agent

Schritt 1 von 6

Schritt 1: BFS für Kingsheep anpassen

Passe deine BFS-Implementation aus den früheren Aufgaben für Kingsheep an.

Unterschiede zu Labyrinth-BFS:

• board statt map (aber gleiche Struktur)
• Mehrere Ziele (alle Essen-Positionen)
• Dynamisches Spielfeld (Essen verschwindet nach Sammlung)

Aufgabe: Erstelle bfs_to_food(board, start_pos), das den kürzesten Pfad zu irgendeinem Essen findet.

Plan:

1. Verwende Queue für BFS
2. Starte bei start_pos
3. Suche bis du "g" oder "r" findest
4. Gib den ersten Zug des Pfades zurück

Aufgabe 4: A*-Agent implementieren

Kingsheep A* Agent

Schritt 1 von 7

Schritt 1: Von BFS zu A*

Verstehe den Unterschied zwischen BFS und A* für Kingsheep.

BFS: Findet nächstes Essen (kürzester Weg)
A:* Findet wertvollstes Essen (bestes Kosten-Nutzen-Verhältnis)

Idee: Rhabarber (5 Punkte) kann weiter weg wertvoller sein als nahes Gras (1 Punkt)!

Aufgabe: Plane einen A*-Agenten:

• g(n) = Schritte von Start zu n
• h(n) = Manhattan-Distanz zu einem Ziel
• f(n) = g(n) + h(n)
• Aber: Berücksichtige Essens-Wert!