Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Also, ich sag gleich nach der Wiederholung hoffe ich, sonst erinnern Sie mich dran, etwas zu den zwei Prüfungsanmeldungen, wenn mehr Leute da sind.

Im Moment befassen wir uns mit Spielalgorithmen, also mit Algorithmen, die in Spielen für Spiele, in einer Offlinesuche optimale Strategien versuchen zu finden.

Die Idee ist, wir haben ein Spiel, zwei Spieler, rundenbasiert, Nullsummenspiel, was noch, deterministisch und alles was preiswert und einfach ist.

Wir haben uns gestern den Minimax Algorithmus, den klassischen Algorithmus, dazu angeguckt.

Die Idee ist, dass wir eine optimale Strategie für einen Spieler finden wollen, wir nennen ihn Max, das ist der der gerade dran ist.

Wir haben einen Gegner, den nennen wir Min und wir wollen diese Offline Strategie finden.

Typisches Beispiel, Tic Tac Toe, wir haben hier den Suchbaum, am Ende haben wir die terminalen Knoten, also die wenn das Spiel aus ist.

Das ist immer gut definiert. Tic Tac Toe ist aus, wenn einer der beiden eine Diagonale geschafft hat.

Dann wissen wir die Nützlichkeit, die wir verteilen können, minus 100 bis 100, je nachdem ob man gewinnt, verloren oder unentschieden hat.

Dann kann man immer Nützlichkeiten zurück berechnen, aus den tatsächlichen Nützlichkeiten, indem man immer maximiert, minimiert, maximiert, minimiert, daher auch der Name.

Das ist im Prinzip sehr einfach, wir machen Tiefensuche, maximieren, minimieren, maximieren, minimieren.

Wir haben hier in einem solchen Dreieck, wenn wir hier unten die tatsächlichen Nützlichkeiten haben, dann kann Min hier, dadurch dass er hier von den kleinsten aus wählt, eine 3 erzwingen.

Hier kann er eine 2 erzwingen, da kann er eine 2 erzwingen und deswegen kann Max eine 3 erzwingen, wenn er nämlich diesen Ast wählt.

Man kann auch die 14 hoffen, aber nur dann, wenn Min blöd spielt und das wollen wir jetzt nicht tun.

Die ganze Psychologie dahinter, dass man jemanden ins Boxhorn jagen kann, dass er sich blöd verhält, die bleibt hier total draußen, wir spielen total auf Sicherheit.

Wenn man das aufschreibt, dann hat man Minimax Decision, man nimmt immer das beste Max Value und das Max Value kann man auswählen über das maximale Min Value und das Min Value in einer wunderbaren gemeinsamen Rekursion wird der Min Wert aus dem Max Wert gemacht.

Solange, bis man irgendwo, und das ist immer der Basisfall der Rekursion, auf einen terminalen Knoten stößt.

Rekursion ist genau das Richtige, um solche Bäume abzulaufen.

Wir haben uns das genau angeguckt und die roten Zahlen hier sind immer sozusagen, was kann Max erzwingen und wir sehen, dass sich so langsam von unten her immer irgendwelche Werte durchsetzen.

Bis man dann hinterher da ist, was wir schon vorher hatten.

Minimax ist prima, theoretisch großartig, leider praktisch unbrauchbar, weil die Bäume exponentiell sind und damit viel zu groß.

Das ist fast, das ist eigentlich immer so in dem, was wir hier machen.

Wir überlegen uns schlaue Sachen und dann sagen wir, leider gehen die schlauen Sachen nicht, weil es zu groß wird.

Was machen wir nun? Und die Antwort ist typischerweise, wir approximieren entweder oder wir überlegen uns noch was Schlaues oder wir betrügen.

Das sind so die drei Standardantworten, wenn Sie sich die merken, dann haben Sie schon einen großartigen Wegweiser in die KI-Forschung.

Natürlich ist es nicht immer trivial zu wissen, wie wir abschätzen und approximieren und wie wir betrügen und wie wir noch was Schlaueres uns ausdenken.

Da ist schon ein bisschen was, was man machen muss in der KI.

Aber im Prinzip ist es immer das, man hat einen Basisfall, der bei uns durch Minimax gegeben wird und da müssen wir es halt ein bisschen besser machen.

Eine Art und Weise, wie man in diesem Fall approximiert, ist, dass man nur einen endlichen Horizont anguckt.

Da unten geht es noch unglaublich weit weiter.

Aber wir haben eine heuristische oder Evaluationsfunktion, die uns irgendwelche Schätzwerte gibt.

Dann kommen die Werte, die man hat, nicht aus der Evaluation hoch, sondern sind Schätzwerte, die man direkt an den Knoten ablesen kann.

Wir hatten uns angeguckt, wie man das macht, zum Beispiel im Schach durch Materialzellen.

Materialzellen sind häufig eine gute Heuristik und wenn man das macht, kann man irgendwelche Features designen,

die man dann durch irgendeine gewichtete, lineare Funktion zusammenaddiert.

Das geht schnell, das ist preiswert und manchmal ist es auch gut.

Wenn man eine gute Evaluationsfunktion hat, dann hilft das was, weil wir von denen sehr viele berechnen müssen.

Sie erinnern sich, dies hier sieht so klein aus, aber wenn wir erstmal bei Tiefe 6 sind,

zum Beispiel im Schach bei einem Verzweigungsfaktor 5,35, dann sind wir schon bei einer Milliarde von denen.

Bei einer Milliarde Evaluationsfunktionsberechnungen kommt es schon darauf an, wie schnell das geht.

Das heißt, wir fallen immer in irgendwelche praktischen Probleme rein.

Dann ist es ganz gut, wenn man nur zählen muss und ein bisschen addieren und multiplizieren.

Das geht schnell. Wenn man scharf nachdenken müsste für jedes dieser Features, dann wäre es unter Umständen zu lang.

Das verwundert nicht ein endlicher Horizont, das gibt uns natürlich Probleme, weil wir nicht über den Horizont gucken können.

Hinter dem Horizont könnte wer weiß was sein. Im Mittelalter bedachte man, dass da Drachen sind.

Hier kann Schachmatt sein und solche Dinge.

Ich hatte ein bisschen von dieser Quiescence Search erzählt, wo man sich an den Stellen, wo wirklich was abgeht, tiefer sucht.

Und an den Stellen, wo Ruhe herrscht, eben dann spart. Das hilft einem.

Und man braucht jede Hilfe, die man kriegen kann bei exponentiellen Suchräumen.