Mathematische Perfektion: Der Cepheus-Poker-Roboter wird euch immer besiegen

Wer hätte das gedacht: Der beste Limit-Texas Hold'em Poker-Spieler der Welt ist ein Roboter. Wenn du nur lange genug mit ihm spielst wird er immer gewinnen. Egal, welche Karten gespielt werden.

Und weil Poker eben Poker ist, wird der nach einer Sternkonstellation in der nördlichen Hemisphäre benante Roboter Cepheus, mit einem schlechten Blatt zwar durchaus auch mal eine Niederlage erleiden, dabei seine Verlustchancen jedoch so gut wie möglich zu minimieren wissen. Auch dir wird er bei einem Spiel langsam aber sicher mit mathematischer Übermacht das Geld aus den Taschen ziehen, indem er schlicht die „perfekte" Entscheidung in jedem gegebenen Szenario fällt.

Es tut mir wirklich leid, die Hobby-Zocker unter euch mit dieser tragischen Botschaft zu konfrontieren, aber seit dieser Woche ist es endgültig kühle, maschinelle Gewissheit: Die Mathematik hinter Heads-up Limit Hold'Em ist gelöst—und Cepheus wird euch immer besiegen.

Heads-up Limit Hold'Em ist ein Pokerspiel, in dem nur eine bestimmte Menge Geld zu bestimmten Zeitpunkten im Spiel gesetzt werden kann. Es ist weit weniger beliebt (und weniger komplex) als das Limitless Hold'Em Pokerspiel. Dort wird der Einsatz nur davon bestimmt, wieviel Geld ein Spieler hat, was bedeutet, dass im Spiel viel mehr mögliche Entscheidungen zur Verfügung stehen.

Gelöst wurde das Spiel von Informatikern der Universität Alberta, die selbst alles andere als Poker-Profis sind. Macht nichts, denn die Lösung eines solchen Spiels ist letztlich vor allem ein mathematisches Problem.

„Manchmal spielst du vielleicht eine Hand und Cepheus wird passen und verliert—doch das gehört zum Poker. Bei diesem Glücksspiel geht es jedoch darum, wie man sich langfristig schlägt, und wenn du nur lange genug spielst, wird Cepheus nie verlieren", erläuterte mir Neil Birch, der den Roboter mitentwickelt hat: „Er macht keine Fehler".

Und das ist natürlich die Hauptsache. Birch und seine Kollegen haben das Limit-Poker de facto einer „brute force"-Attacke ausgesetzt, wobei es ungefähr 3 x 10^14 Entscheidungsmöglichkeiten gibt. Manchen Schätzungen zufolge sind das mehr mögliche Permutationen, als jemals Hände in der Geschichte des Poker gespielt wurden.

„Poker ist so gigantisch groß, dass alleine die Festlegung auf eine Strategie—also zu bestimmen, wie jede Situation gespielt werden sollte—zahlenmäßig größer ist als die Gesamtanzahl der Karten, die die Menschheit je gespielt hat", sagte Birch.

Cepheus scannt eine gewaltig große Tabelle aller möglichen Permutationen des Spiels —die Tabelle allein ist elf Terrabyte groß— und entscheidet ständig, was der beste Zug ist.

In einer in Science veröffentlichten Analyse, schriebt Tuomas Sandholm von der Carnegie Mellon-Uni in Pittsburgh, dass Cepheus „mit signifikanter statistischer Wahrscheinlichkeit nicht innerhalb einer Lebenszeit geschlagen werden kann". Würde Birch als miserabler Pokerspieler jedoch gegen einen professionellen Pokerspieler antreten , würde der Profi am Ende wahrscheinlich mehr Geld gewinnen, als der Roboter Cepheus in einem Match gegen Birch.

Das liegt daran, dass menschliche Pokerspieler häufig versuchen, von den Fehlern ihrer Gegenüber maximal zu profitieren. Und deswegen können menschliche Spieler dickere Summen mit größeren Einsätze gewinnen, aber sich eben auch einmal verkalkulieren und dann verlieren.

Cepheus dagegen versucht einfach nur, das mathematisch logischste Spiel zu fahren, mit jeder einzelnen Hand und völlig unabhängig vom Gegner. Er neigt nicht dazu, andere Gegner unverhältnismäßig für ihre Fehler abzustrafen. Wenn zwei Cepheus-Maschinen gegeneinander spielen, wird der Gewinner immer der sein, der das beste Blatt bekommt.

„Völlig egal, wer spielt, Cepheus wird immer ein bisschen besser sein", sagte Birch. „Wenn er gegen mich spielt, wird er immer noch darauf achten, keine Fehler zu machen. Denn es könnte ja eine klitzekleine Chance bestehen, dass ich doch ein guter Spieler bin."

Insofern ist er der „perfekte" Pokerspieler, aber vielleicht nicht der optimalste—soll heißen: jemand, der die Fehler seines Gegenübers gnadenlos ausnutzt, um die Ausbeute pro Runde zu maximieren.

Ich hab auch einmal gegen Cepheus gespielt und zunächst sogar ein paar Hände gewonnen. Anschließend habe ich ein paar verloren und dann noch viele, viele mehr. Irgendwie hatte ich schon währenddessen das Gefühl, grandios vorgeführt zu werden.

Cepheus ist ein riesiger Durchbruch in der KI. Es ist eine wahrhaftige Premiere, dass ein sogenanntes Spiel der imperfekten Informationen gelöst wurde—soll heißen, der Roboter schlägt sich perfekt, ohne zu wissen, welche Karten sein Gegenüber hat.

Von einer Perspektive der Informatik und der künstlichen Intelligenz gesehen ist Cepheus eine viel größere Errungenschaft als die Erschaffung eines Roboters, der beispielsweise extrem gut in Schach oder Checkers ist, schreibt Richard Carter in einem Paper der Uni Edinburgh von 2007.

Um das Spiel zu knacken, wurde es in unendlich viele kleine Entscheidungs-Sets zerlegt. Bei jedem Zug sind die Entscheidungsmöglichkeiten natürlich: mitgehen, erhöhen oder passen. Letztlich ist es aber völlig egal, was der Gegner tut—es gibt immer einen perfekten Spielzug, erklärt Birch. „Es gibt eine statische, festgelegte Strategie, die Folgendes garantiert: Egal wie gut der Gegner ist, der Roboter wird mindestens so gut sein, als hätte der Gegner perfekt gespielt", sagte er. „Und egal wie gut der Gegner ist, er wird nicht perfekt sein."

Sein Team hat außerdem einen wichtigen Fehler mathematisch bewiesen, den professionelle Pokerspieler schon lange vermutet haben: Die Idee, mit den Blinds (dem kleinen Einsatz zu Beginn einer Hand) mitzugehen, ist einfach falsch. „Du gehst nicht mit den Blinds mit. Du passt entweder oder erhöhst. Das ist das, was du mathematisch korrekterweise tun musst.", stellt Birch klar.

Weil das Paper (auch in Science veröffentlicht) noch nicht herausgekommen ist, hatte Birch noch keine Gelegenheit, ausführliches Feedback von der riesigen Online-Pokercommunity zu bekommen. Aber er erzählte mir, dass ein professioneller Spieler, der über die Arbeit gelesen hatte nicht überrascht gewesen sei, dass eine solche Strategie existierte. In der Community kursiert schon lange das Gerücht, dass Limit-Poker gelöst werden könne.

Also, ist Onlinepoker jetzt tot? Von Robotern unwiederbringlich zerstört? Nicht ganz: No Limit Texas Hold'Em—bei dem Summen in beliebiger Größe gesetzt und gewonnen werden können—ist bei Weitem das beliebteste, und während Roboter dieses Spiel auch schon ganz gut spielen können, haben sie es noch nicht mal ansatzweise gelöst. Wir erinnern uns: Limit Poker hat ungefähr 3 x 10^14 Permutationen; No-Limit Poker 3 x 10^48, ist also kurz gesagt unglaublich viele Größenordnungen schwieriger zu lösen.

„Dieses Problem direkt zu lösen, erscheint mir sehr unwahrscheinlich und in naher Zukunft nicht machbar", sagte Birch. „Das heißt nicht, dass wir nicht daran arbeiten. Wir können das Spiel nicht komplett brute forcen, also müssen wir spezifisches Pokerwissen mit einbeziehen. Du kannst sehr, sehr gut spielen, aber du verlierst die Garantie, perfekt zu sein.". Hier kannst du gegen Cepheus spielen und dich komplett zerstören lassen.