Tiefensuche, Heuristiken und Spieltheorie in der KI

Tiefensuche (Depth-First Search)

Die Tiefensuche (Depth-First Search, DFS) ist ein Algorithmus zum Traversieren oder Suchen von Baum- oder Graphdatenstrukturen. Der Algorithmus beginnt am Wurzelknoten (Auswahl eines beliebigen Knotens als Wurzelknoten im Fall eines Graphen) und erkundet so weit wie möglich entlang jedes Zweigs, bevor er zurückweicht.

Heuristiken in der KI

Definition

Eine Heuristik ist eine Technik, die entwickelt wurde, um ein Problem schneller zu lösen, wenn klassische Methoden zu langsam sind, oder um eine ungefähre Lösung zu finden, wenn klassische Methoden keine exakte Lösung finden können. Dies geschieht durch den Verzicht auf Optimalität, Vollständigkeit, Genauigkeit oder Präzision im Austausch für Geschwindigkeit. Eine Heuristik ist im Wesentlichen eine Faustregel, die bei der Entscheidungsfindung hilft.

Ziel

Das Ziel einer Heuristik ist es, eine Lösung in einem angemessenen Zeitrahmen zu finden, die gut genug ist, um das gegebene Problem zu lösen. Diese Lösung ist möglicherweise nicht die beste von allen Lösungen für dieses Problem, oder sie kann die Lösung einfach approximieren. Aber sie ist immer noch wertvoll, weil das Finden nicht zu viel Zeit in Anspruch nimmt.

Heuristik-Typen

• Allgemeine Heuristiken: Diese sind für eine Vielzahl von Problemen geeignet.
• Spezifische Heuristiken: Diese nutzen domänenspezifisches Wissen, um Probleme zu lösen.

Bewertung von Heuristiken

• Zulässige Heuristiken: Eine zulässige Heuristik ist eine, die die Kosten zum Erreichen des Ziels niemals überschätzt. Zulässige Heuristiken sind von Natur aus optimistisch. Wenn eine Heuristik zulässig ist, wird die Funktion f die tatsächlichen Kosten zum Erreichen des Ziels niemals überschätzen. Man sagt, dass diese Heuristiken ein monotones Verhalten aufweisen. Wenn sie nicht monoton ist, kann f korrigiert werden:

  Angenommen, es gibt zwei Knoten, n und n', wobei n der Elternknoten von n' ist:

  • g(n) = 3; h(n) = 4; also f(n) = 7
  • g(n') = 4; h(n') = 2; also f(n') = 6

  Jeder Weg, der durch n' führt, führt auch durch n, daher ist f(n') nicht relevant. Jedes Mal, wenn ein neuer Knoten generiert wird, sollte bestätigt werden, dass seine Kosten niedriger sind als die seines Elternteils:

  f(n') = max(f(n), g(n') + h(n'))

• Dominante Heuristiken: Wenn h2(n) ≥ h1(n) für jeden Knoten n gilt, dominiert h2 h1. Eine dominante Heuristik erweitert weniger Knoten. Es ist immer besser, eine dominante Heuristikfunktion zu verwenden, sofern sie zulässig ist.

Spieltheorie

Das Ziel der Spieltheorie ist es, das Verhalten von Akteuren in strategischen Situationen zu analysieren. Eine strategische Situation ist eine Situation, in der das Ergebnis der Handlungen eines Akteurs von den Handlungen anderer Akteure abhängt.

Spiele können nach verschiedenen Kriterien klassifiziert werden. Hier betrachten wir die Klassifizierung nach dem Ergebnis:

• Nullsummenspiele: In einem Nullsummenspiel ist die Summe der Auszahlungen aller Spieler immer Null. Das bedeutet, dass der Gewinn eines Spielers immer dem Verlust eines anderen Spielers entspricht.

• Nicht-Nullsummenspiele: In einem Nicht-Nullsummenspiel ist die Summe der Auszahlungen aller Spieler nicht unbedingt Null. Das bedeutet, dass es möglich ist, dass alle Spieler gewinnen oder alle Spieler verlieren.

1. Minimax-Algorithmus

Der Minimax-Algorithmus ist ein rekursiver Algorithmus, der verwendet wird, um den optimalen Zug für einen Spieler zu wählen, unter der Annahme, dass der Gegner auch optimal spielt. Er wird häufig in Zwei-Spieler-Spielen wie Schach, Tic-Tac-Toe und Go verwendet.

Algorithmus:

1. Generiere den Spielbaum bis zu den terminalen Zuständen.
2. Wende die Bewertungsfunktion auf die terminalen Zustände an.
3. Verwende die Werte der terminalen Zustände, um den Wert der Knoten eine Ebene höher im Baum zu berechnen.
4. Fahre fort, bis du die Wurzel des Baums erreichst. Wähle in jedem Schritt den Zug mit dem maximalen Wert für Max und den Zug mit dem minimalen Wert für Min.

2. Alpha-Beta-Suche

Die Alpha-Beta-Suche ist eine Optimierungstechnik für den Minimax-Algorithmus. Sie reduziert die Anzahl der Knoten, die vom Minimax-Algorithmus im Suchbaum ausgewertet werden müssen, indem sie Zweige abschneidet, die die endgültige Entscheidung nicht beeinflussen können.

Die Effizienz der Alpha-Beta-Suche hängt stark von der Reihenfolge ab, in der die Nachfolger untersucht werden. Wenn die besten Nachfolger zuerst untersucht werden, kann die Alpha-Beta-Suche doppelt so weit vorausschauen wie der Minimax-Algorithmus.

Algorithmus (Alpha-Beta):

Funktion Alpha-Beta(Knoten, Tiefe, α, β)
  Wenn (Knoten ist terminal) oder (Tiefe == 0) dann
    gib Bewertung(Knoten) zurück
  Ende wenn
  Wenn Knoten maximiert dann
    Für jedes Kind i von Knoten tue
      α = max(α, Alpha-Beta(Kind_i, Tiefe - 1, α, β))
      Wenn α ≥ β dann
        gib β zurück (*schneide die folgenden Kinder ab*)
      Ende wenn
    Ende für
    gib α zurück
  Sonst (*Knoten minimiert*)
    Für jedes Kind i von Knoten tue
      β = min(β, Alpha-Beta(Kind_i, Tiefe - 1, α, β))
      Wenn α ≥ β dann
        gib α zurück (*schneide die folgenden Kinder ab*)
      Ende wenn
    Ende für
    gib β zurück
  Ende wenn
Ende Funktion