Sieg fürs Maschinengehirn: Erstmals hat ein Computerprogramm Profispieler im Pokerspiel „Heads-Up No-Limit Texas Hold’em“ besiegt. Das Programm DeepStack gewann mit großem Vorsprung gegen seine 33 Gegner. Das Besondere daran: Im Gegensatz zu Schach oder Go liegt das Blatt beim Poker nicht offen auf dem Tisch. Die unvollständigen Informationen erfordern daher ganz neue Strategien, so die Forscher im Fachmagazin „Science“.
Die Machinengehirne holen auf: Vor allem dank lernfähiger neuronaler Netze hat die künstliche Intelligenz in den letzten Jahren rasante Fortschritte gemacht. Computer werten inzwischen selbstständig Sprache, Bilder oder Texte aus und schreiben sie sogar, sie haben auch gelernt, sich gegenseitig etwas beizubringen. Für Aufsehen sorgten zudem Siege von KI-Programmen in komplexen Brettspielen wie Schach und Go, aber auch im Fragespiel Jeopardy.
Allerdings: „All diese Erfolge erzielten die Programme in Spielen mit Informations-Symmetrie“, erklären Matej Moravcik von der University of Alberta und seine Kollegen. „Alle Mitspieler haben dabei die gleiche Information über den Stand des Spiels.“ Das jedoch ist weder im richtigen Leben noch in vielen anderen Spielen der Fall – beispielsweise bei Kartenspielen.
Komplex durch unvollständige Information
Poker ist ein klassisches Beispiel für ein solches Spiel mit unvollständiger Information: Bei der Variante „Heads-Up No-Limits Texas Hold’em“ (HUNL) hat jeder Spieler zwei Karten, die nur er kennt, der Rest des Blattes wird in drei Folgerunden sukzessive offen ausgeteilt. Jeder Spieler muss aus der Reaktion des Gegners und dessen vergangenen Spielzügen versuchen zu schließen, welches Blatt dieser haben könnte.
„Ein solches Spiel mit unvollständiger Information erfordert viel komplexere Überlegungen als Spiele mit Informations-Symmetrie“, so die Forscher. „Das Pokerspiel Heads-Up Texas Hold’em ist in der Anzahl der möglichen Spielentscheidungen vergleichbar mit dem Brettspiel Go – es gibt mehr als 10 hoch 160 Entscheidungspunkte.“ Wollte ein Computer diese alle im Vorhinein durchrechnen, hätte er kaum eine Chance.
Jede Situation für sich – der Rest ist „Intuition“
Mit ihrem Computerprogramm DeepStack wählten die Forscher daher eine andere Strategie: „DeepStack betrachtet jede Situation des Spiels für sich und denkt in diesem Moment nicht über den Rest der Partie nach“, erklären die Forscher. Statt wie beim Schach oder Go die Folgen jeder Spielentscheidung bis zum Ende durchzugehen, nutzt DeepStack nur eine Art grobe Schätzung des Spielausgangs.
„Jede Spielsituation ist für DeepStack wie ein Pokerspiel im Kleinen“, erklärt Seniorautor Michael Bowling von der University of Alberta. „Statt das gesamte Spiel zu lösen, bewältigt er Millionen dieser Mini-Pokerrunden – und jede hilft ihm dabei intuitiv zu erfassen, wie Poker funktioniert.“ Möglich wird dies durch ein neuronales Netzwerk, das DeepStack als Basis für seine „Intuition“ dient und vor dem eigentlichen Turnier an zehn Millionen Partien trainiert wurde.
Fähig zur Intuition und zum Bluff
Genau diese „Intuition“ ist das Besondere an DeepStack, wie auch Christian Bauckhage vom Fraunhofer-Institut für Intelligente Analyse- und Informationssysteme kommentiert: „Programme, die Poker spielen können sind natürlich nicht neu. Die völlig neuartige und bahnbrechende Leistung der DeepStack Software besteht aber darin, dass die dort verwendeten neuronalen Netze es so etwas wie ‚Intuition´ entwickelt haben“, erklärt der Forscher.
„DeepStack kann somit beispielsweise überzeugend bluffen und ist in seiner Spielweise nicht mehr von Menschen zu unterscheiden“, so Bauckhage weiter. Seiner Ansicht würde DeepStack sogar den Turing Test bestehen, wenn dabei die Fähigkeit getestet würde, Poker zu spielen.
Duell Mensch gegen Maschine
Wie aber schlägt sich DeepStack gegen echte Pokerprofis? Um das herauszufinden, trat das Computer gegen 33 Pokerspieler aus 17 Ländern an. Jeder der Mitspieler sollte im Laufe mehrerer Wochen online 3.000 Partien gegen DeepStack absolvieren. Insgesamt wurden in diesem Turnier 44.852 Pokerpartien gespielt. Aus Zeitgründen schafften allerdings nur elf menschliche Spieler die geforderten 3.000 Partien.
Das Ergebnis: Einmal mehr hatte der Computer die Nase vorn. DeepStack gewann in Bezug auf die Gesamtzahl der Partien mit einem Vorsprung von 492 Millibinds per Game (mbb/g). Diese Einheit gibt an, welchen Anteil der Einsätze ein Pokerspieler gewinnt. Profi-Spieler gewinnen typischerweise mit Vorsprüngen von mindestens 50 mbb/g, wie die Forscher erklären. Der Computer schlug zudem zehn der elf bis zum Schluss mitspielenden Gegner überlegen, beim elften lag sein Vorsprung „nur“ bei 70 mbb/g.
„Das ist ein Paradigmenwechsel“
„Poker war lange Zeit eine echte Herausforderung für die künstliche Intelligenz“, sagt Bowling. Doch jetzt haben die Computergehirne auch dieses Spiel mit verdeckten Karten endgültig gemeistert. Nach dem Sieg eines KI-Vorgängers im etwas einfacheren Heads-Up Limit Texas Hold’em vor einigen Jahren hat das Programm DeepStack nun auch die schwierigere No-Limit-Variante dieses Pokerspiels geknackt.
„Das ist mehr als nur ein Meilenstein für die künstliche Intelligenz“, konstatieren Moravcik und seine Kollegen. „DeepStack repräsentiert auch einen Paradigmenwechsel für die Lösung von großen, sequenziellen Spielen mit unvollständiger Information.“ Das Programm – das im Übrigen auf einem ganz einfachen Laptop läuft – kommt damit der Bewältigung von realistischen Problemen und Situationen deutlich näher.
Der Computerpionier John von Neumann konstatierte bereits: „Das echte Leben besteht auch aus Bluffs, kleinen Täuschungstaktiken und Fragen wie: Was denkt der andere wohl, was ich als nächstes tue.“ Der Lösung solcher Fragen könnte die künstliche Intelligenz mit DeepStack einen Schritt näher gekommen sein. (Science, 2017; doi: 10.1126/science.aam6960)
(University of Alberta/ Science, 03.03.2017 – NPO)
