Poker-KI DeepStack braucht nur einen PC um Profispieler zu schlagen

Ende Januar versetzte die KI Libratus die professionelle Poker-Szene in Aufruhr, weil sie erstmals einige der weltbesten Profispieler im Poker besiegte. Damit stahl sie jedoch einer anderen KI die Show: DeepStack besiegte nämlich bereits im Dezember 33 Poker-Profis. Das Team um Matej Moravčík von der University of Alberta und zwei Prager Universitäten entschied sich lediglich gegen ein öffentlichkeitswirksames Turnier.

Ein PC mit Grafikkarte reicht

Libratus überraschte damit, kein Deep Learning einzusetzen. Stattdessen baut der Algorithmus auf Counterfactual Regret Minimization (CFR) auf. Libratus kombiniert das mit Regret Based Pruning, um den Entscheidungsbaum beim Poker von 10^160 Möglichkeiten auf ein Maß zu reduzieren, das sich auf dem Supercomputer "Bridges" berechnen ließ.

DeepStack setzt dagegen ganz ähnlich wie Googles Go-KI AlphaGo auf Deep Learning in Form eines neuronalen Netzes. Bei beiden KIs ergänzt eine Intuition in Form eines neuronalen Netzes einen erprobten Algorithmus. Die Intuition kommt immer dann zum Einsatz, wenn der Entscheidungsbaum mehr Möglichkeiten eröffnet, als der Lösungsalgorithmus ausprobieren kann. DeepStack nutzt wie Libratus auch CFR, fällt aber nach wenigen Rechenschritten auf sein neuronales Netz zurück, das eine Schätzung abgibt, welche Werte die vollständige Berechnung aller Möglichkeiten geliefert hätte. Mit diesem Trick muss DeepStack nur 10^17 mögliche Spielverläufe abwägen, um menschliche Profis zu schlagen.

Computer trainiert Computer

DeepStacks Intuition besteht aus einem voll verbundenen neuronalen Netz mit sieben verdeckten Schichten. Als Eingabe bekommt es den aktuellen Einsatz, die offen liegenden Karten, die eigenen Karten und eine Schätzung dazu, welche Karten der Gegner haben könnte. Daraus berechnet es ein geschätztes Risiko, mit diesem Blatt zu verlieren. Diese Werte sollen dem entsprechen, was auch CFR mit deutlich höherer Rechenzeit berechnen könnte. Da CFR anhand der Spieltheorie korrekte Werte berechnet, konnten die Forscher das Netzwerk mit Daten trainieren, die sie mit dem systematischen Algorithmus berechneten. Deswegen musste DeepStack keine realen Spiele analysieren, um seine Intuition zu entwickeln.

In ihrem Artikel im Science-Magazin beschreiben die Forscher auch, warum die 44.852 Spiele der KI für eine statistisch signifikante Aussage ausreichen. Durch die Glücksspielkomponente ergibt sich im Poker ein erhebliches Rauschen. Hat der Computer schlechte Karten, verliert er nämlich trotz Strategie und Intuition. (pmk)