Michael Bowling ist im Januar 2017 wohl ziemlich erschrocken. Ein Computerprogramm namens "Libratus" gewann damals in einem wochenlangen Wettkampf in Pittsburgh langsam, aber sicher die Oberhand über mehrere Weltklasse-Pokerspieler. Dabei hatte Bowling, der als Informatiker an der University of Alberta in Kanada arbeitet, mit Kollegen aus Prag selbst einige Zeit zuvor mit seiner künstlichen Intelligenz "DeepStack" gegen Profispieler gewonnen. Der Artikel, in dem Bowlings Team diese Leistung im Detail beschreibt, befand sich allerdings gerade im Review-Prozess der Fachzeitschrift "Science" – und die Veröffentlichung war noch nicht in Sicht.

Dumm gelaufen, könnte man meinen. Den Rekord, als erstes Team eine überlegene Poker-KI erschaffen zu haben, wollte sich Bowling aber nicht nehmen lassen. Also stellten er und seine Kollegen, kurz bevor Libratus seinen Siegeszug antrat, ihren noch nicht von Gutachtern geprüften Artikel auf die Internetplattform arXiv. Am Donnerstag ist diese Arbeit nun in "Science" erschienen und damit einer gewissen Qualitätsprüfung unterzogen worden. Eine Hürde, die Libratus noch nicht genommen hat.

Zehn von elf Pokerprofis besiegt

Bowling und seine Kollegen beschreiben in ihrem Aufsatz, wie ihr Programm DeepStack in jeweils 3000 Partien gegen elf professionelle Pokerspieler antrat. Zehn der Kontrahenten konnte die Software so oft besiegen, dass dies durch Pech auf Seite der Menschen praktisch nicht mehr erklärt werden kann. In der Forschung zur künstlichen Intelligenz markiert das einen signifikanten Fortschritt. Auch wenn die Regeln von Poker für Menschen deutlich einfacher zu verstehen sind als die des asiatischen Brettspiels Go, in dem im Jahr 2016 eine künstliche Intelligenz von Google brillierte: Für Computer ist Poker das schwierigere Spiel.

Bei Go oder Schach liegt alles, was vor sich geht, für alle Beteiligten sichtbar auf dem Spielbrett. Bei "Heads-up no-limit Texas hold'em" (HUNL), für das Libratus und DeepStack entwickelt wurden, hat jeder Spieler zwei Karten auf der Hand, die der Kontrahent nicht sehen kann. Das Ziel dieser Zwei-Personen-Variante von Poker ist, die beiden Handkarten mit mehreren offen ausliegenden Karten zu einem Blatt zu kombinieren, das wertiger ist als das des Gegenspielers. Außerdem können die Teilnehmer mit beliebigen Geldbeträgen auf ihren Sieg wetten.

Diese Eigenarten machen HUNL-Poker zu einem Paradebeispiel für ein Spiel, das auf "unvollständigen Informationen" basiert, wie Informatiker sagen. Verschärfend hinzu kommt, dass auch der Gegenspieler nicht alles weiß und deshalb aus einer bestimmten Situation möglicherweise falsche Schlüsse zieht – oder bewusst blufft. Diese Besonderheiten vergrößern die Zahl möglicher Entscheidungen beträchtlich. "Man muss die fehlenden Informationen schließlich trotzdem berücksichtigen", sagt der Informatiker Eneldo Loza Mencía von der Technischen Universität Darmstadt. Wie schon bei Go hatten viele Experten deshalb vermutet, dass die ersten Erfolge hier frühestens in einigen Jahren vermeldet werden würden. Wie bei Go wurden sie nun überrascht.

"Computer spielen nicht perfekt"
(Michael Thielscher, University of New South Wales)

Um zu berechnen, wie Computer mit unbekannten Informationen, die auch noch von Handlungen anderer abhängen, am besten umgehen können, nutzen Informatiker die Spieltheorie. In der Umsetzung bedeutet das, dass der Computer an jedem Punkt des Spiels berechnet, welche Aktion mit der größten Wahrscheinlichkeit zum optimalen Verlauf des nächsten Zuges führt. Die Maschine versucht dabei, so nah wie möglich an das so genannte Nash-Gleichgewicht heranzukommen. Dieses Vorgehen kann der Spieltheorie zufolge durch keine andere Strategie geschlagen werden.

Bei den meisten Spielen ist die Nash-Strategie, der ein Gegenüber allenfalls ein gleich wirksames Kalkül entgegensetzen kann, nur schwer zu finden. Selbst für Schach ist dieses Problem noch nicht gelöst, obwohl man das annehmen würde, weil Schachcomputer schon lange besser spielen als Menschen. "Aber sie spielen eben nicht perfekt", sagt Michael Thielscher von der University of New South Wales in Sydney, Australien.

Klassischerweise berechnen Informatiker für komplexere Spiele das gesamte Spiel im Vorfeld. Sie generieren einen so genannten Entscheidungsbaum, in dem das Programm nach dem optimalen Zug in einer bestimmten Situation suchen kann. Bei manchen Spielen stößt diese "globale" Strategie aber an ihre Grenzen: Für HUNL-Poker gilt es 10160 mögliche Entscheidungen zu berechnen, bei Go sind es sogar 10170. Das ist selbst für moderne Supercomputer zu viel. "Der Poker-Spielbaum ist nicht berechenbar", fasst Loza Mencía zusammen.

Intuition statt roher Rechenpower

Daher setzen Informatiker ihrer künstlichen Intelligenz für gewöhnlich eine reduzierte Variante des Spiels vor. Dabei stehen nicht mehr alle denkbaren Entscheidungen offen. Stattdessen werden ähnliche Handlungsoptionen zu Gruppen zusammengefasst. So gingen die Forscher um Tuomas Sandholm von der Carneggie Melon University auch bei der Programmierung von Libratus vor, der künstlichen Intelligenz, die unter großem öffentlichem Aufsehen im Januar 2017 Pokerprofis besiegte.

Den vereinfachten Entscheidungsbaum ließen die Forscher anschließend von einem Supercomputer nach dem jeweils besten Zug durchsuchen. "Aber die Abstraktion des Spiels kann dazu führen, dass du ein sehr schlechter Pokerspieler bist", kritisiert Bowling, der DeepStack-Erfinder. Schließlich verfüge Libratus damit nicht über alle nötigen Informationen. Denn der Entscheidungsbaum der Poker-KI ist beschnitten wie ein Baum im Winter, nachdem der Gärtner da war.

Pokerchips auf Tastatur
© Carla Schaffer / AAAS
(Ausschnitt)
Pokerchips auf Tastatur
Spezielle Computerprogramme können mittlerweile besser pokern als Profis.

Mit ihrer eigenen, nun in "Science" vorgestellten Kreation wollten es Bowling und seine Kollegen besser machen. Statt auf rohe Rechenpower zu setzen, arbeite DeepStack mit Intuition, sagt der Forscher. Zudem laufe das Programm auf einem handelsüblichen Laptop und benötige nicht wie Sandholms KI einen Supercomputer. Doch wie kann eine Maschine Intuition haben? Eigentlich ist das eine menschliche Eigenart, mit der Menschen gewissermaßen ihre begrenzte Rechenkapazität ausgleichen: Sie berücksichtigen bei der Entscheidungsfindung nicht alle möglichen Wege, sondern nur diejenigen, auf denen sie mit einer gewissen Wahrscheinlichkeit ihr Ziel erreichen können.

Um diesen Kniff einer Maschine beizubringen, ließ Bowlings Team die DeepStack-Software zunächst zehn Millionen Pokerpartien gegen sich selbst spielen, eine Form von "Deep Learning" neuronaler Netze. Dabei entwickelte das Computerprogramm laut Bowling eine Art Bauchgefühl, auf das sich auch Profispieler berufen: ein Gespür dafür, welcher Zug in welcher Situation erfolgreich sein könnte, ohne die Folgen der Handlung bis zum Ende des Spiels durchrechnen zu müssen. Die Software berücksichtigte jeweils bloß die nächsten sieben Spielzüge und entschied dann, welche die beste Aktion sei. Auf ähnliche Weise reduzierte die Google-Software AlphaGo bei ihrem Sieg gegen Go-Profis die Entscheidungspunkte.

DeepStack nutzt seine Erfahrung

"Neuronale Netze können gut von bekannten Situationen auf ähnliche, aber unbekannte Situationen schließen", sagt Loza Mencía. Das System muss die Situationen nicht jedes Mal neu berechnen, es muss sie nicht einmal kennen. Es sucht sich eine vergleichbare Situation aus, beispielsweise Tischkarten mit ähnlichen Werten, und schließt aus diesen, was in der unbekannten Situation der richtige Weg ist. Intuition ist allerdings ein unscharfer Begriff: "Wahrscheinlich verwenden wir ihn genau deshalb: Neuronale Netze lernen etwas, was wir als Programmierer nicht verstehen, wir sehen nur das richtige Ergebnis", sagt Thielscher.

"DeepStack machte im Spiel gegen sich selbst die Erfahrung, dass man erfolgreicher ist, wenn man blufft"
(Michael Bowling, University of Alberta)

Beim Pokern muss die künstliche Intelligenz einen Vorgang berücksichtigen, der Maschinen an und für sich fremd ist: das Bluffen. So zu tun, als habe man bessere Karten, als man tatsächlich hat, das scheint auf den ersten Blick Menschen vorbehalten zu sein. Interessanterweise lernte DeepStack das Bluffen aber von ganz allein, ohne sich dabei an menschlichen Spielern zu orientieren: "DeepStack machte im Spiel gegen sich selbst die Erfahrung, dass man erfolgreicher ist, wenn man blufft", sagt Bowling. Auch hier hat das neuronale Netz ein Muster gefunden, das den Weg zum perfekten Ergebnis ebnet. Ob das nun bluffen oder lügen heißt, ist der künstlichen Intelligenz egal.

Sandholm hingegen wollte bei der Entwicklung von Libratus so wenig wie möglich von seinem System überrascht werden und nutzte deshalb kein Deep Learning. "Da gibt es keinerlei Garantien, wie gut diese Lösung ist und ob nicht Zufall eine Rolle spielt", sagte er im Januar. Das ist im Spielebereich keine seltene Haltung. DeepStack sei nach AlphaGo erst die zweite Spiele-Software gewesen, die mittels Deep Learning trainiert worden sei, sagt Thielscher: "Wir nutzen Deep Learning eigentlich nur als zweite Wahl, wenn wir nicht wissen, wie wir ein Problem lösen können."

Sandholm habe den Einsatz des modernen Verfahrens wahrscheinlich nicht für nötig gehalten, da er die Erfolgsstrategien im Poker kannte und die Herausforderung "nur" darin bestand, seine Software so zu programmieren, dass die Datenmassen handhabbar blieben. "Die einfachste Stellschraube ist hier das Abstraktionsniveau", sagt Loza Mencía. "Wenn man doppelt so viel vereinfacht, ist der Spielbaum nur halb so groß." Und damit auch schneller durchsuchbar. Noch vor einem Jahr habe ein Vorläufer von Libratus in einem Wettbewerb gegen Menschen verloren. Offenbar haben Sandholm und Kollegen die notwendigen Abstraktionen im Entscheidungsbaum verringert und verfeinert, so dass das System nun gut genug war, um jetzt menschliche Profis zu schlagen.

Ist es nun ein Meilenstein, wenn Computer Entscheidungen auf der Grundlage unvollständiger Informationen fällen können? Bei den bisherigen Spielerfolgen von künstlichen Intelligenzen in Spielen von Schach bis Go konnte man stets argumentieren, dass die Maschinen sehr viel besser als Menschen in der Lage sind, Massen an Informationen zu verarbeiten. Der Erfolg beim Pokern zeigt nun allerdings, dass Computerprogramme Fähigkeiten entwickeln können, die auch bei vielen Alltagsproblemen hilfreich wären.

Künstliche Intelligenz in der Medizin

"Jede Entscheidung im echten Leben beruht auf unvollständigen Informationen", sagt Bowling. Letztlich könne seine Arbeit daher dazu dienen, Programme wie DeepStack in der Medizin oder bei Verhandlungen einzusetzen. "Wenn eine künstliche Intelligenz für uns verhandeln soll, könnte ich meine Präferenzen eingeben, ohne dass sie diese gleich verrät." Der Computer schlägt dann das Beste für den Auftraggeber heraus, entwickelt die perfekte Verhandlungsstrategie.

Ähnliches proklamiert Sandholm für Libratus: Ein künftiges "Spiel" der Software könnte die Suche nach Arzneimitteln gegen resistente Keime sein. Solche Probleme könnten jedoch noch deutlich komplexer sein als Go oder Poker, gibt Thielscher zu bedenken: "Es ist viel einfacher, ein Programm für ein klar definiertes Problem zu schreiben." Spiele wie Poker haben trotz der unbekannten Informationen eindeutige Regeln, und die Menge der Möglichkeiten ist zwar gigantisch, aber immer noch begrenzt. In der echten Welt werden Entwicklungen hingegen von einer unbegrenzten und vor allem unvorhersehbaren Anzahl von Faktoren beeinflusst: "Aktienkurse hängen beispielsweise von einem neuen Präsidenten ab, der twittert."

Das letzte Wort in der Frage, wer nun die Lorbeeren für den Sieg der Maschine über die Pokerspieler dieser Welt verdient hat, ist derweil noch nicht gesprochen. DeepStack hat zwar deutlicher gegen menschliche Spieler gewonnen, dafür waren diese nach Einschätzung von Experten weniger hochkarätig als die Opponenten von Libratus. "DeepStack hat nicht gegen die besten Spieler gespielt", stichelte Libratus-Schöpfer Tuomas Sandholm im Januar.

Generell ist es im Poker nicht so einfach wie bei Go oder Schach, den Weltmeister zu bestimmen. Es gibt Spitzenspieler, doch wer der weltweit Beste ist, ist nicht definiert. Absehbar ist aber, dass keiner von ihnen mit der neuen Generation der Pokerbots mithalten können wird. Das zeigt einmal mehr, wie rasant die Entwicklung der künstlichen Intelligenz mittlerweile vorangeht.