AI - Einführung, Suche & Exploration, Steering & Control, Path Finding  

Spiel- und Entscheidungsbäume

Wie funktioniert die Alpha Beta Suche?

1. Prationiere Baum T and der Wurzel in 2 Teilbäume LR
2. Bestimme v(L) vollständig
  • zusätzlich zum Wert jedes Zwischenknotens auch das Fenster [Alpha, Beta]
    • Alpha in minimierenden Knoten
    • Beta in maximierenden Knoten
3. Bestimme v(R) partiell
  • bestimme v(R') vollständig
  • teste auf Cut-Bedingungen (pruning)
    • wenn Knoten R maximiert (Beta Cut-Off möglich)
      • wenn v(R') > v(L) wird der Spieler L wählen, da alle Werte der Teilbäume von R größer oder gleich v(R') sein müssen => Teilbäume von R können abgeschnitten werden.
    • wennKnoten R minimiert (Alpha Cut-Off möglich)
      • wenn v(R') < v(L) wird der Gegner L wählen, da alle Werte der Teilbäume von R kleiner oder gleich v(R') sein müssen (da Spieler maximiert) => Teilbäume von R können abgeschnitten werden
 

Diskussion