Artificial Intelligence with Python
lecture0-720p-en.txt
Übersicht der Suchalgorithmen aus dem Vortrag
Uninformierte Suchalgorithmen
Tiefensuche (Depth-First Search, DFS)
Breitensuche (Breadth-First Search, BFS)
Informierte Suchalgorithmen
Greedy Best-First Search (GBFS)
A*-Suche (A* Search)
Adversarial Search Algorithmus
Minimax
Optimierung von Minimax
Alpha-Beta-Pruning
Modifikation von Minimax für komplexe Spiele
Depth-limited Minimax mit Evaluationsfunktion
Funktionsweise und Vor- und Nachteile von Suchalgorithmen
Lineare Suche
Durchquert die Liste sequenziell und vergleicht jedes Element mit dem Zielwert.
Vorteile:
Einfach zu verstehen und zu implementieren.
Keine vorherige Sortierung notwendig.
Nachteile:
Ineffizient bei großen Listen; durchschnittliche und schlechteste Laufzeit ist O(n).
Binäre Suche
Funktioniert auf sortierten Listen, indem der Datensatz halbiert und der Zielwert in der entsprechenden Hälfte gesucht wird.
Vorteile:
Effizienter als lineare Suche; Laufzeit von O(log n).
Gut für große Datenmengen.
Nachteile:
Erfordert eine vorsortierte Liste.
Nicht effektiv bei häufigen Einsätzen oder Löschungen.
Tiefensuche (DFS)
Durchsucht einen Graphen oder Baum tief und verfolgt den Weg entlang der Kinder, bevor er zu einem Vorfahren zurückkehrt.
Vorteile:
Kann Lösungspfade finden oder ausschließen.
Weniger Speicherbedarf als Breitensuche.
Nachteile:
Kann in nicht-endlichen (zyklischen) Graphen gefangen werden.
Nicht garantiert, dass es den kürzesten Pfad findet.
Breitensuche (BFS)
Arbeitet ebenenweise von der Wurzel aus und erforscht alle Nachbarn eines Knotens, bevor weiter in die Tiefe gegangen wird.
Vorteile:
Findet den kürzesten Pfad in ungewichteten Graphen.
Geeignet für die Suche in breiten Strukturen.
Nachteile:
Höherer Speicherbedarf im Vergleich zur Tiefensuche.
Kann langsamer sein, besonders bei tiefen Graphen.
A*-Suchalgorithmus
Optimale und vollständige Suche, die eine heuristische Bewertung verwendet, um den effizientesten Pfad zu finden.
Vorteile:
Effizient und effektiv in der Pfadfindung.
Oft schneller als andere Graphensuchalgorithmen.
Nachteile:
Abhängigkeit von einer angemessenen Heuristik.
Kann teuer in Bezug auf Speicher und Berechnung sein, wenn der Suchraum groß ist.
Hash-Suche
Nutzt eine Hash-Tabelle, um den Speicherort des Zielwerts schnell zu finden.
Vorteile:
Oftmals schnelle Suche mit durchschnittlicher Laufzeitkomplexität von O(1).
Nachteile:
Speicherintensiv; erfordert zusätzlichen Speicher für die Hash-Tabelle.
Kollisionen können die Effizienz mindern.
lecture0-720p-en.txt
Notwendige Datentypen und Strukturen für Suchalgorithmen
Initialzustand
Der Startpunkt oder die Ausgangssituation des Suchproblems.
Zustandsraum
Eine Menge aller möglichen Zustände, die durch den Algorithmus erreicht werden können.
Nachfolgerfunktion (auch Übergangsfunktion)
Definiert die möglichen Aktionen, um von einem Zustand zum nächsten zu gelangen.
Zieltest (auch Endzustandsprüfung)
Ermöglicht die Überprüfung, ob der Endzustand oder Zielzustand erreicht ist.
Pfadkosten (auch Schrittkostenfunktion)
Eine Funktion, die die Kosten von Aktionen oder Übergängen zwischen Zuständen bewertet.
Suchbaum oder Graph
Eine strukturierte Darstellung aller Zustände als Knoten und der möglichen Übergänge zwischen diesen Zuständen als Kanten.
Offene Liste (Frontier)
Eine dynamische Menge von Blattknoten, die noch untersucht werden müssen.
Geschlossene Liste (Explored Set)
Eine Menge von Zuständen, die bereits expandiert oder besucht wurden.
Datenstrukturen für die Speicherung von Knoten
Strukturen wie Stacks (LIFO), Queues (FIFO), Priority Queues (nach Kosten sortiert) und andere, die je nach Suchalgorithmus variieren.
Heuristikfunktion (nur für heuristische Suchalgorithmen relevant)
Eine Funktion, die die geschätzte Kosten bis zum Erreichen des Zielzustandes von einem bestimmten Zustand aus angibt.
Minimax-Algorithmus
Der Minimax-Algorithmus ist eine grundlegende Technik in der Spieltheorie für die Optimierung der Entscheidungsfindung in sogenannten Nullsummen-Spielen mit zwei Spielern (wie Schach, Dame oder Tic-Tac-Toe), bei denen der Gewinn des einen Spielers dem Verlust des anderen entspricht.
Spieler
Max-Spieler
Angehend von der Maximierung seines Gewinns. Ziel ist es, die höchste Punktzahl zu erreichen.
Min-Spieler
Sucht das beste Ergebnis aus seiner Sicht, also die niedrigstmögliche Punktzahl für den Max-Spieler.
Spielbrettzustände
Anfangszustand (S0)
Das Spiel beginnt.
Intermediärer Zustand
Das Spiel entwickelt sich und die Spieler wechseln sich mit ihren Zügen ab.
Endzustand
Das Spiel ist zu Ende, wenn ein Spieler gewinnt oder ein Unentschieden vorliegt.
Wichtige Funktionen
Spieler-Funktion (Player)
Ermittelt, welcher Spieler am Zug ist.
Aktionen-Funktion (Actions)
Listet alle möglichen Züge für den aktuellen Spieler auf.
Ergebnis-Funktion (Result)
Berechnet den neuen Zustand des Spielbretts nach einem Zug.
Terminaltest-Funktion (Terminal Test)
Prüft, ob das Spiel vorbei ist (Endzustand erreicht ist).
Nutzenfunktion (Utility)
Weist jedem Endzustand einen Wert zu (Gewinn, Verlust, Unentschieden).
Arbeitsweise
Tiefe des Spiels
Anzahl der Züge, die im Voraus betrachtet werden, bevor der Algorithmus stoppt (bei "Depth-limited Minimax").
Bewertungsfunktion (Evaluation)
Schätzt den Wert eines nicht-terminalen Zustands ab, wenn eine Begrenzung der Tiefe angewendet wird.
Entscheidungsfindung
Minimax-Entscheidungsprozess
Beginnt mit dem aktuellen Zustand des Spiels.
Expandiert den Baum aller möglichen Züge rekursiv.
Wendet die Nutzenfunktion auf alle Endzustände an.
Propagiert diese Werte zurück an die vorherige Ebene, um zwischen Min- und Max-Zügen zu unterscheiden.
Der Max-Spieler wählt den Zug mit dem höchsten Wert, der Min-Spieler den mit dem niedrigsten Wert.
Optimierungen
Alpha-Beta-Pruning
Reduziert die Anzahl der zu prüfenden Zustände erheblich, indem offensichtlich schlechte Züge abgeschnitten werden.
Depth Limit
Begrenzt die Suche auf eine maximale Suchtiefe, um die Berechnung praktisch zu machen.
Der Minimax-Algorithmus ist essentiell für die Erstellung von künstlichen Intelligenzen (KI), welche in der Lage sind, strategische Spiele gegen menschliche Gegner oder andere KIs zu spielen und dabei schwierige Entscheidungen zu treffen.