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

Spiel- und Entscheidungsbäume

Was ist Alpha Beta Pruning?

  • Pruning: abschneiden von (sinnlosen) Teilbäumen
    • Verfahren liefert selbe Ergebnis wie Minimax
    • wesentlich besseres Laufzeitverhalten
      • O(bd/2im besten Fall
      • O(b3d/4) im Durchschnitt
  • Alpha ist das erreichte Maximum (minimales Maximum von Spieler A)
  • Beta ist das erreichte Minimum (maximales Minimum von Spieler B)
  • Window für jeden Knoten [Alpha, Beta]

Diskussion