Künstliche Intelligenzen können nun auch menschliche Profi-Pokerspieler schlagen. Zwei verschiedene Programme verfolgen dabei unterschiedliche Strategien.
Andrew Brown | Fotolia
Als die von Google Deepmind entwickelte Künstliche Intelligenz "AlphaGo" 2015 erstmals einen menschlichen Profi ohne Handicap im Strategie-Brettspiel Go schlug und wenige Monate später sich auch der beste Go-Spieler der Welt, Lee Sedol, dem Computerprogramm geschlagen geben musste, ging jeweils ein Raunen durch die Welt. Im Schach konnten Computer Menschen schon längst besiegen, das Spiel Go jedoch ist um ein Vielfaches komplexer und galt bis vor etwas mehr als einem Jahr noch als letzte Bastion des Menschen in Strategiespielen.
Eine Ausnahme bildete noch Poker, das Kartenspiel, das Laien meist als Glücksspiel sehen und betreiben. Profi-Pokerspieler verdienen ihre Millionen allerdings kaum durch Glück, sondern hauptsächlich durch stochastische Berechnungen sowie durch Beobachtung und hervorragende Menschenkenntnis, um beispielsweise einen Bluff des Gegners zu erkennen. Ein Strategiespiel par excellence. Computerprogramme konnten den Poker-Profis bisher nicht das Wasser reichen. Denn anders als in Brettspielen wie Schach oder Go, bei denen alle möglichen Spielzüge exakt berechenbar sind, sind im Poker dem jeweiligen Spieler (und auch einer Software) einige Informationen nicht bekannt: Welche Karten hat der Gegenspieler auf der Hand, welche liegen noch im Stapel und an welcher Stelle? Dazu kommt das Verhalten des Spielers: Setzt er einen Betrag ein, obwohl er kein gutes Blatt hält, blufft er also? Aber mit der Herrschaft des Menschen ist auch hier jetzt Schluss.
Deepstack kam vor Libratus
Forscher der Carnegie-Mellon-Universität in Pittsburgh/USA haben vor kurzem mit ihrer Künstlichen Intelligenz "Libratus" auf einem leistungsstarken Supercomputer erstmals Profi-Pokerspieler schlagen können und die Ergebnisse im Januar veröffentlicht. Doch schon im Dezember haben Forscher der Universität von Alberta (Kanada), der Charles-Universität Prag und der Tschechischen Technischen Universität Prag eine Künstliche Intelligenz, "Deepstack", vorgestellt die in einer Poker-Variante, dem Heads-up no-limit (HUNL) Texas Hold’em, erstmals Profis besiegen konnte. Der größte Unterschied: Im Gegensatz zu Libratus arbeitet Deepstack nicht auf einem Großrechner sondern auf einer Nvidia-Grafikkarte in einem fast schon herkömmlichen PC.
Zum Spiel: Im HUNL Texas Hold’em sitzen sich nur zwei Spieler gegenüber, regelmäßig wird diese Variante am Ende von Texas-Hold’em-Poker-Turnieren gespielt, wenn nur noch zwei Spieler am Finaltisch übrig sind und um den Turniersieg spielen. Im "No limit" gibt es keine obere Grenze für den Einsatz von Jetons – jeder Spieler kann zu jeder Setzrunde theoretisch alles setzen, was er hat.
Fast 45.000 Hände gegen Menschen gespielt
In ihrem Bericht zur Studie, die sie mit "DeepStack" durchgeführt haben – es wurden 44.852 Hände mit insgesamt 33 menschlichen Teilnehmern aus 17 Ländern gespielt – erklären die zehn beteiligten Computer- und Mathematikwissenschaftler, was "DeepStack" ausmacht:
Künstliche Intelligenz hat in den letzten Jahren eine Reihe von Durchbrüchen erzielt, wobei Spiele oft als bedeutende Meilensteine dienen. Ein gemeinsames Merkmal der Spiele mit diesen Erfolgen ist, dass sie Informationssymmetrie unter den Spielern beinhalten, alle Spieler haben dort identische Informationen. Diese Eigenschaft von perfekter Information ist jedoch weit häufiger bei Spielen als bei Problemen in der realen Welt zu finden. Poker ist das Quintessenz-Spiel der unvollständigen Informationen und das war ein langjähriges Problem in der künstlichen Intelligenz. DeepStack, ein neuer Algorithmus für unvollständige Informationseinstellungen wie im Poker, nutzt ein rekursives logisches Denken um die Informations-Asymmetrie zu verarbeiten, eine Sortierung, um die Berechnungen auf relevante Entscheidungen zu beschränken und eine Form der Intuition zu willkürlichen Poker-Situationen, die automatisch aus Selfplay-Spielen mit Hilfe von Deep Learning erlernt wird." Matej Moravcik, Martin Schmid, Neil Burch, Viliam Lisy, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson und Michael Bowling in der Facharbeit "DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker".
Bisher hatte es einige Erfolge von Künstlicher Intelligenz im Heads-up-Poker-Spiel mit limitierten Einsätzen gegeben. Allerdings, so schreiben die Wissenschaftler, haben die Spieler beim Heads-up limit Texas Hold’em gerade einmal 1014 mögliche Entscheidungen, die sie treffen können. Wegen der Möglichkeit, in der No-limit-Variante allerdings jede beliebige Menge von Jetons setzen zu können, steigt hier die Anzahl der Entscheidungspunkte drastisch auf 10160. Im Vergleich hat eine Partie Go 10170 mögliche Spielzüge. "Spiele mit unvollständigen Informationen erfordern eine komplexere Logik als die mit perfekter Information", schreiben die Forscher. Die richtige Entscheidung zu einem bestimmten Zeitpunkt hängt von der wahrscheinlichen Verteilung von geheimen Informationen ab, die der Gegner hat und davon, wie er in der Vergangenheit agierte. Deswegen lassen sich aus einzelnen, isolierten Spielsituationen nicht so einfach die richtigen Schlüsse auf die beste Handlung folgern.
Ein Suchbaum mit einem geringen Verzweigungsfaktor als Darstellung der riesigen Anzahl an Entscheidungsmöglichkeiten in einem Spiel.
W. Ertel | Grundkurs Künstliche Intelligenz (2016)
CFR statt Deep Learning bei Libratus
Die Ansätze in der KI, um ein Pokerspiel mit einem Computer zu gewinnen, betrachteten bisher also immer ein gesamtes Spiel. Daraus wurde ihre Strategie entwickelt, wie in Zukunft gespielt werden soll. In Libratus beispielsweise wurden keine tiefen neuronalen Netze verwendet, wie beispielsweise in AlphaGo. Counterfactual regret minimization (CFR) ist stattdessen eine Technik aus dem Sektor des Reinforcement Learning, die Self-play nutzt, um durch rekursives Denken die Strategie gegen sich selbst über Iteration anzupassen. Wenn das Spiel zu komplex ist, um direkt gelöst zu werden, löst man ein kleineres, abstraktes Spiel mit übersetzten Situationen und Handlungen. Wie CFR auf Basis der Monte-Carlo-Simulation arbeitet, erklärt István Szita im Buchkapitel "Reinforcement Learning in Games". Außerdem gibt der Springer-Autor und Wissenschaftler Einblicke in die verschiedenen Probleme und Lösungsansätze für die erfolgreiche Entwicklung künstlicher Intelligenz in Spielen. Libratus kombiniert CFR mit Regret Based Pruning, um die Anzahl der möglichen Entscheidungen auf ein in realistischer Zeit berechenbares Maß zu reduzieren.
CFR-Kombination schenkt der KI eine Intuition
Deepstack arbeitet jedoch in einer bisher nicht angewandten Methode und nutzt die tiefen neuronalen Netze wie in AlphaGo. Es wird zwar weiterhin der rekursive Ansatz von CFR verwendet, um mit der Informations-Asymmetrie umzugehen. Doch Deepstack berechnet nicht eine komplette Strategie vor dem Spiel und deswegen gibt es auch nicht die Notwendigkeit der Abstraktion. Stattdessen betrachtet die KI jede einzelne Situation, wie sie im Spiel auftritt – aber nicht isoliert. Sie vermeidet das logische Denken über den gesamten Rest des Spiels, indem die aufwendige exakte Berechnung durch eine schnelle Näherungsschätzung ersetzt wird. Heißt: Wenn die Möglichkeiten der Spielzüge im Deep-Learning-Baum zu groß wird, dient diese Schätzung quasi als die Intuition von DeepStack, schreiben die Prager und Kanadier in ihrer Arbeit. Ein Bauchgefühl für jede mögliche Kombination der geheimen Karten in jeder Poker-Hand. Diese künstliche Intuition müsse, wie beim Menschen auch, trainiert werden. Die Entwickler nutzen dazu Deep Learning mit Beispielen, die aus zufälligen Pokersituationen generiert werden.
Ein schematischer Suchbaum mit möglichen Spielentscheidungen beim Poker.
Deepstack Forschungsprojekt | "DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker" (2017)
In ihrer Arbeit beschreiben die Deepstack-Entwickler unter anderem auch eingehender, wie im Deepstack-Algorithmus ein Hybrid aus „Vanilla CFR“ und „CFR+“ arbeitet und wie eine hohe Spielgeschwindigkeit von 0,2 bis 5,9 Sekunden Bedenkzeit pro Spielrunde mit der Berechnung der Algorithmen auf einer Grafikkarte in einem PC realisiert werden.
Derzeit kann Deepstack beim Heads-Up-Poker den Menschen schlagen. Wie internationale Medien die Entwickler zitieren, ist der Schritt hin zu einem Einsatz an virtuellen Poker-Tischen mit mehreren Spielern aber nur ein kleiner. Mit einigen Anpassungen sollte Deepstack auch dort funktionieren. Wie auch das renommierte Wissenschaftsmagazin Nature aus der SpringerNature-Verlagsgruppe berichtet, wird das jedoch nicht das Ende des lukrativen Online-Pokerspiels bedeuten. Denn die meisten Online-Casinos erlauben keinen Einsatz von Computern als Spieler. Stattdessen bietet die KI den menschlichen Spielern die Möglichkeit, gegen starke Gegner zu trainieren. Die Frage ist nur, ob die Künstliche Intelligenz davon nicht schneller und besser lernt, als ihr menschlicher Gegenüber ...