KI-Grundlagen in der Praxis: Suchalgorithmen und Agentendesign für Tic-Tac-Toe

Einführung in die Künstliche Intelligenz: Von Tic-Tac-Toe bis zur Fruchtsortiermaschine

Künstliche Intelligenz (KI) begegnet uns heute überall: in Sprachassistenten wie Siri, in Empfehlungsalgorithmen von Netflix oder in selbstfahrenden Autos. Doch wie funktioniert eine KI eigentlich? Dieser Artikel führt dich in die grundlegenden Konzepte der KI ein – anhand von Aufgaben, wie sie in einem typischen Informatikstudium vorkommen. Wir betrachten Agentendesign, Suchalgorithmen und Heuristiken, immer mit Bezug zu aktuellen Trends und Alltagsbeispielen.

1. Agentendesign am Beispiel Tic-Tac-Toe

Ein KI-Agent ist ein System, das seine Umgebung wahrnimmt und darauf basierend Aktionen ausführt. Stell dir einen Roboter vor, der Tic-Tac-Toe auf Papier spielt. Er muss erkennen, ob ein Feld X oder O enthält, selbst zeichnen können und den Spielstand analysieren. Die PEAS-Beschreibung hilft, die Aufgabe zu strukturieren:

• Performance: Gewinnen, nicht verlieren, schnell spielen.
• Environment: Das 3x3-Gitter, die Marker, der Gegner.
• Actuators: Roboterarm mit Stift.
• Sensors: Kamera zur Markererkennung.

Die Umgebung ist vollständig beobachtbar (das ganze Spielfeld ist sichtbar), multi-agent (Gegner), deterministisch (Züge haben feste Ergebnisse), sequentiell (jeder Zug beeinflusst den nächsten), statisch (das Spiel wartet), diskret (9 Felder) und bekannt (Regeln sind klar).

2. Suchalgorithmen: Der Weg zum Ziel

Suchalgorithmen sind das Herz vieler KI-Systeme. Sie finden einen Pfad von einem Startzustand zu einem Zielzustand. Wir betrachten einen Baum mit Knoten A bis K, Kosten an den Kanten und einer Heuristik. Die Algorithmen werden in einer bestimmten Reihenfolge expandiert.

2.1 Breitensuche (BFS)

BFS expandiert Knoten Ebene für Ebene. Reihenfolge: A, B, C, D, E, F (Ziel gefunden). BFS ist vollständig und optimal bei einheitlichen Kosten, aber speicherintensiv.

2.2 Tiefensuche (DFS)

DFS geht zuerst in die Tiefe. Reihenfolge: A, C, G, H, I, J, K (Ziel). DFS benötigt wenig Speicher, ist aber nicht optimal und kann in unendlichen Bäumen scheitern.

2.3 Iterative Tiefensuche (IDS)

IDS kombiniert die Vorteile von BFS und DFS. Es führt wiederholt DFS mit steigender Tiefe durch. Reihenfolge: Tiefe 1: A; Tiefe 2: A, B, C; Tiefe 3: A, B, D, E, C, F (Ziel). IDS ist vollständig und optimal bei einheitlichen Kosten, mit moderatem Speicher.

2.4 Uniform Cost Search (UCS)

UCS expandiert den Knoten mit den geringsten Pfadkosten. Reihenfolge: A (0), B (1), C (3), D (4), E (5), F (6) (Ziel). UCS ist optimal für beliebige positive Kosten.

2.5 Greedy Best-First Search

Greedy BFS nutzt nur die Heuristik. Reihenfolge: A (h=6), C (h=4), G (h=3), H (h=2), I (h=1), K (h=0) (Ziel). Es ist schnell, aber nicht optimal.

2.6 A*-Suche

A* kombiniert Pfadkosten und Heuristik (f = g + h). Reihenfolge: A (0+6=6), B (1+5=6), C (3+4=7), D (4+3=7), E (5+2=7), F (6+1=7) (Ziel). A* ist optimal, wenn die Heuristik zulässig ist.

3. Fruchtsortiermaschine: Zustandsraum und optimale Suche

Stell dir eine Sortieranlage vor, die n Kisten mit verschiedenen Früchten sortiert. Der Roboterarm kann sich bewegen, Früchte aufnehmen und ablegen. Der Zustand wird beschrieben durch: Position des Arms, Inhalt der Kisten, und ob der Arm eine Frucht hält. Aktionen: moveLeft, moveRight, grab(fruitType), place. Ziel: Jede Kiste enthält nur eine Fruchtsorte. Der optimale Algorithmus ist Uniform Cost Search (UCS), da alle Aktionskosten gleich sind und UCS den kürzesten Pfad garantiert. Die Frontier ist eine Prioritätswarteschlange. Eine Reached-Menge (geschlossene Liste) verhindert das Wiederholen von Zuständen und spart Speicher.

4. Heuristiken: Schätzen hilft

Heuristiken schätzen die Entfernung zum Ziel. In einem Grid mit Bewegungen nach links, rechts, oben, unten (Kosten 10) ist die Manhattan-Distanz M(s) eine zulässige Heuristik, da sie die minimalen Schritte ohne Hindernisse angibt. Die gegebene Heuristik h(s) = M(s) + r, wobei r eine Zufallszahl ist, ist nicht konsistent, da die Zufallszahl die Schätzung aufblähen kann und die Konsistenzbedingung h(s) ≤ c(s,s') + h(s') verletzt werden kann.

5. Hill Climbing: Den PIN knacken

Hill Climbing ist ein lokaler Suchalgorithmus, der iterativ den besten Nachbarn wählt. Für einen 2-stelligen PIN (00-99) könnte der Agent mit einem zufälligen PIN starten und dann jeweils die Ziffern ändern, um die „Höhe“ (z.B. Anzahl korrekter Ziffern) zu maximieren. Problem: lokale Optima. Der Agent könnte in einer Schleife stecken bleiben oder das globale Optimum verfehlen. Ein zufälliger Neustart oder Simulated Annealing könnten helfen.

Fazit

Die Grundlagen der KI – Agentendesign, Suchalgorithmen und Heuristiken – sind essenziell für moderne Anwendungen. Ob beim Spielen von Tic-Tac-Toe, Sortieren von Früchten oder Entsperren von Dateien: Diese Konzepte helfen, intelligente Systeme zu bauen. Mit dem Aufkommen von generativer KI und Large Language Models (LLMs) bleiben diese klassischen Methoden das Fundament, auf dem komplexere Systeme aufbauen.