Wir haben am Montag

über Alphabetersuche gesprochen und wir erinnern uns, das Ganze dreht sich um

suchbasierte Spiele-Löser und unterscheidet sich im Wesentlichen von der allgemeinen Suche

und das ist so dadurch, dass wir eben einen Gegner haben. Gegner, der versucht den Vorteil

des Spielers zu minimieren. Wir haben uns das angeguckt und die offensichtliche Verallgemeinerung

dieser ganzen Suchstrategie-Geschichten war, dass wir Minimax eingeführt haben. Minimax,

das immer abwechselt zwischen den beiden Spielern. So diese Art von Spiel hat man ausgesucht und

wo immer maximiert wird, minimiert wird, maximiert wird. Und wir hatten uns auch angeguckt, dass man

keine Chance hat, die Spiele durchzuspielen, außer für sowas wie Tic Tac Toe und dass man

deswegen irgendwie wiederum Heuristiken braucht, nur dass wir diesmal die Evaluationsfunktion

genannt haben. Ansonsten hat sich Minimax vollkommen erhalten. Und Alphabetersuche ist im Wesentlichen

ein kleiner, cleverer Kunstgriff, mit dem wir uns erlauben, etwa doppelt so weit die Suchräume

zu durchforsten. Und die Idee von Alphabetersuche ist ganz einfach im Prinzip. Wir haben uns zuerst

mal nur den Fall von Max angeguckt, also deswegen Alphabetersuche und nicht Alphabetersuche. Aber

natürlich ist das alles immer dual und was man für Max machen kann, kann man für Min machen und

sollte man natürlich auch. Und die Idee war einfach, wenn wir diesen Minimax-Baum durchsuchen und wir

haben hier irgendwo einen Minvalwert von N und später finden wir einen kleineren Minval von

Minwert, dann können wir sehen, aha, wir würden hier, falls er kleiner ist, wir würden nie hinkommen,

weil wir uns da schon anders entschieden haben. Das ist einfach so eine Art Lookahead und diese Idee

nutzen wir einfach ganz konsequent aus. Eine klassische Algorithmenoptimierung, dass man einfach

sieht, dass man gewisse Dinge nicht zu tun braucht, weil sie das Ergebnis nicht verändern.

Gut, da haben wir das immer wieder durchgespielt und hatten gesehen, dass wir hier, weil wir hier

höchstens, weil wir hier wissen, dass Min das Ergebnis auf zwei runterdrücken kann, wissen wir,

dass wir die anderen gar nicht mehr berechnen müssen, weil wir uns hier schon für die drei

entscheiden werden, weil wir hier höchstens eine 2 kriegen. Da könnte noch eine 1 kommen oder eine

0 kommen oder was weiß ich. Aber das interessiert uns alles gar nicht, weil wir wissen, wir können

wir können es schon besser machen. Das heißt, wir merken uns den sogenannten Alpha-Wert, der Wert,

über den wir drüber kommen müssen, damit es sich lohnt zu explorieren. Wir sehen, dass wir hier einen

Alpha-Wert von 3 kriegen und dann an der kritischen Stelle sehen, dass wir da nicht drüber kommen und

deswegen nicht mehr zu explorieren brauchen.

Das ist ein Fehler. Sie können sich vorstellen, dass ich sehr viel Copy und Paste gemacht habe, um diese

Bäume zu erzeugen. Das ist die Hauptidee und wenn Sie die begriffen haben, ist alles andere

praktisch zwangsläufig. Es gibt zwei Ideen. Der Max kann seinen Suchraum trimmen, indem er sich

diesen Alpha-Wert behält und das Offensichtliche ist, dass man im dualen Fall dann auch sich den

Beta-Wert für den Min-Wert merkt und im Prinzip ist das auch schon alles. Wenn man sich zurück

erinnert an den Minimax-Algorithmus, kommt eigentlich nur jeweils immer diese beiden Zahlen und diese

beiden Zahlen dazu. Merkt er den Wert und wenn du außerhalb des Intervalls, das uns interessiert,

mit Alpha-Beta-Intervalls bist, dann macht halt nichts und das macht halt nichts, ist genau das,

was wir wollen. Hausaufgabe wird sein, sich das mal für mehr Spieler, zum Beispiel drei Spieler,

zu überlegen. Das ist relativ straightforward, das können Sie, aber in diesem Zug versteht man

dann wirklich, was man aus seiner Vorlesung tun kann. Okay, dann hatten wir das Beispiel. Hier

haben wir dieses Intervall von Minimax und sehen, dass wir sparen können. Da sieht man auch ganz schön,

wie sich die Werte immer hoch und runter propagieren und hier habe ich auf die rechte Seite so ein bisschen

erweitert, um zu zeigen, dass sich je weiter man runtergeht, natürlich die Sparen, die Ersparnisse

multiplizieren. Wenn man sich das Ganze wirklich überlegt, dann sieht man, dass man maximal

die Suchtiefe verdoppeln kann, weil man aus Max-Sicht immer letztlich, wenn man Glück hat,

den Min-Wert sozusagen nahezu ohne Wahl machen kann. Wenn man also in dieser Situation, das ist

auch schon relativ typisch, man muss hier am Anfang so ein bisschen vorstellen, muss man

explorieren, damit man auf den jeweiligen Alpha-Wert kommt und wenn der Alpha-Wert gut genug ist, dann

verschwindet die Wahl für die weiteren Kinder. Und in der Praxis ist es so, und das muss man sich