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

Als im Wesentlichen Standardalgorithmus angeguckt, der Standardalgorithmus, der systematisch den Baum optimal und in Erwartung, dass der Gegner optimal spielt, im schlechtesten Fall durchsucht.

Man merkt sich pro Knoten immer einen Wert, nämlich was ist der Wert, der von unten die Nützlichkeit hochkommt.

Und dann eben den Alpha und Beta Wert, je nachdem wann kann ich Teilbäume auslassen.

Das funktioniert in unserem Beispiel so, dass wir erstmal runtergehen, bis zu unserem Horizont die Nützlichkeit abfragen, dann die Werte, die Maximalwerte hier hoch transportieren und haben hier diesen Beta Wert hier für Min, nämlich den Wert, den der Min erzwingen kann zu dieser Zeit.

Wir machen hier weiter. Wir sehen, dass wir hier mit einer 2 im Beta Wert unterhalb der 3 liegen.

Das heißt wir brauchen den Teilbaum, der hier unten sitzt, nicht mehr zu explodieren und gehen immer weiter sofort.

Wir sehen auch einen sehr starken Ordnungseffekt, in diesem Fall, wo wir hier aufsteigend geordnete Knoten hatten, der Nützlichkeit nach aufteigend Nützlichkeit,

können wir abschneiden, während wir hier, wo wir ungünstig geordnet haben, das eben nicht können. Das heißt wir werden in Alpha Beta irgendwelche Baum-Kinder-Umordnungsstrategien nutzen, um das Beste rauszukriegen.

Wir hatten uns noch ein Beispiel angeguckt, in dem es besser gezeigt wurde und hatten uns theoretisch überlegt, dass man mit Alpha Beta Pruning etwa doppelt so tief suchen kann, wie ohne.

Das ist ein echter, in der Tiefe sind wir exponentiell, das heißt wir kriegen einen echten Komplexitätsfortschritt von D auf die halbe.

Das ist nicht einfach ein konstanter Faktor, sondern das ist ein ganz exponentieller Faktor, der in der Praxis enorm einen Unterricht macht.

Dann hatten wir uns einen total anderen Ansatz angeguckt. Es ist ja häufig so, dass wenn wir Algorithmen randomisieren, dass sie dann besser werden.

Und hier ist die Idee, dass statt Nützlichkeiten abzuschätzen am Horizont, dass wir Nützlichkeiten samplen.

Das ist genau das, was das Go-Spielen tatsächlich geknackt hat. Die Idee hier ist, dass wir die Nützlichkeiten durch Sampling herauskriegen.

Sie erinnern sich, dass die Bäume wieder exponentiell breit sind, das heißt wir suchen unsystematisch ab, merken uns immer in dem Sampling die Rewards, also die Nützlichkeiten im Durchschnitt.

Statt exponentiell viel zum Beispiel in diesem Teilbaum abzusuchen, laufen wir randomisiert ein paar Mal runter, gucken an was kriegen wir denn wieder, machen den Durchschnitt und nehmen das als eine Abschätzung.

Wir brauchen keine Evaluationsfunktionen, sondern durch das Sampling bekommen wir Nützlichkeiten, samplen weiter.

Und dann, wenn wir fertig gesamplt haben, in diesem Fall habe ich einfach zwei Samples mir genommen, können wir dann entscheiden, was wir machen.

Und dann machen wir tatsächlich Greedy-Tiefensuche in Monte Carlo, Baumsuche und dann verschiebt sich dieses ganze Problem eine Baumstufe nach unten.

Und so weiter und so fort. Es gibt da noch eine Verbesserung, die üblichen Geschichten, Memoisierung, dass man sich gewisse Werte, die man schon mal hatte, dass man die nicht wegschmeißt.

Und was man dann natürlich tut, und das ist ja auch eine Sache, die wir sehr häufig in Algorithmen sehen, ist, dass wir letztlich Platz gegen Zeit tauschen können.

Und natürlich beliebig hin und her tauschen. Wenn wir Platzprobleme haben, können wir Informationen wegschmeißen und müssen die unter Umständen später nochmal berechnen.

Wenn wir genug Platz haben, können wir uns den merken, müssen es dann nicht nochmal berechnen. Und das ist, was wir uns in diesem Beispiel angeguckt haben.

Sie sehen schon, wenn wir es lang genug machen, kommen wir in Platzprobleme. Und so weiter.

AlphaGo benutzt genau dieses Verfahren und das ist ein symbolisches Suchverfahren, was zwei große Parameter hat, nämlich wie soll ich wann samplen?

Und der andere ist, wenn ich gesamplt habe, und auch wie lange muss ich samplen, was mache ich dann? Wie tief gehe ich tatsächlich mit dieser Information weiter?

Wenn man die gut gegeneinander abwägen kann, dann kann man unter Umständen gut suchen.

Und der AlphaGo Ansatz ist, dass man diese im Wesentlichen Balanciierungsentscheidung, dass man die lernt, indem man häufig gegen sich selber spielt oder gegen Menschen spielt oder so etwas.

Und die setzen dafür spezielle neuronale Netzwerke ein, die genau einmal die Policy sample, also wie weit laufe ich auf der gesampelten Information vorwärts und wieviel muss ich samplen?

Das wird in diesen Policy- und Value-Networks gelernt. Und das scheint die richtige Kombination zu sein für Go.

Und deswegen sind die da besonders gut.

Okay.

Irgendwelche Fragen zu Suche?

Ich habe schon gehört, dass es Leute gibt, die schon angefangen haben, Kalaha zu programmieren. Das ist durchaus okay.

Wir werden natürlich gewisse Schnittstellen brauchen, sodass wir diese, dass wir die gegeneinander antreten lassen können.

Und das ist ein Rufgang für die ganzen, ja, für die Wettbewerbsmechanik haben wir noch aus dem letzten Jahr ein Framework, ein Java Framework oder was, Galah?

Ich weiß schon gar nicht mehr.

Und das werden wir jetzt, da sind wir bereits dabei, das zu überholen und aus den Fehlern, die wir das letzte Jahr gemacht haben, zu lernen.

Das werden wir dann irgendwo auf dem Forum bereitstellen, auch mit einer Testumgebung, sodass Sie gucken können, ob das alles zusammenarbeitet.

Und das happening wird sein in der Woche am 13. März.

Das heißt, es sind noch zwei Wochen Zeit, ein interessantes Programm zu bauen.

Okay, wir wechseln jetzt mit diesen Constraints Satisfaction Problemen, die als nächstes kommen, wechseln wir in eine neue Algorithmenklasse.

Und die sich vor allen Dingen dadurch unterscheidet, dass wir die Zustände anders darstellen.

Wir haben bisher Blackbox Zustände gehabt, die man nicht reingucken kann, die hatten im Wesentlichen eine Nummer.

Auch wenn wir uns die immer anders vorstellen, das ist ein Schachbrett, wo die Damen auf Position 1, 2, 7, 8, 5, irgendwas sitzen, wo ich mir immer sofort ein Schachbrett vorstelle.

Aber natürlich ist eigentlich für das Suchprogramm Zustände, die sich nur durch die keine innere Struktur haben.

Das Einzige, was das Programm weiß, ist, was sind die Folgezustände.

Möglicherweise eine Evaluationsfunktion darauf, die unter Umständen auf die innere Struktur zugreifen kann.

Aber für das Suchprogramm selber sind die Zustände Blackboxes.