Algorithmen auf Spielbäumen

Question 1

Alpha-Beta Suche Algorithmus

Answer 1

Question 2

Wann wird der Alpha-Cutoff ausgeführt

Answer 2

Im Min-Knoten wenn der Wert eines Kindes kleiner ist als alpha.

Question 3

Wann wird der Beta-Cutoff ausgeführt

Answer 3

Im Max-Knoten wenn der Wert eines Kindes größer ist als beta

Question 4

Wann spricht man von einem deep cutoff?

Answer 4

Wenn das das alpha/beta durch welches der Cutoff ausgelöst wurde nicht im aktuellen Knoten gesetzt wurde sondern vom Elternknoten ‘herruntergegeben’ wurde

Question 5

Bei welcher tiefe kann der frühste alpha-cutoff ausgelöst werden?

Answer 5

Tiefe 1

Question 6

Bei welcher Tiefe kann der frühste beta cutoff ausgelöst werden?

Answer 6

Tiefe 2

Question 7

Welche Zweige müssen auf jeden Fall durchsucht worden sein damit ein Cufoff ausgelöst werden kann

Answer 7

Der Pfad links vom Cutoffknoten

Question 8

Pseudocode für die iterative Tiefensuche

Answer 8

Question 9

Was ist der Vorteil von iterativer Tiefensuche gegenüber MinMax?

Answer 9

• Wenn das Spiel auf Zeit kann es passieren das MinMax zu lange braucht und keine Lösung produziert. Iterative Tiefensuche hingegen kann einfach eine neue iteration machen wenn noch Zeit übrig ist.
• Durch die fühzeitige Sortierung der besten Züge können die vermutlich besten Züge als erstes expandiert werden was zu großen Cutoffs führt.

Question 10

Was ist der Nachteile von iterativer Tiefensuche gegenüber MinMax?

Answer 10

Man hat einen riesen Overhead, denn man muss für die x+1 Iteration noch mal alles berechnen was man in der x Iteration schon berechnet hat.