Archiv

Künstliche Intelligenz
Das fast perfekte Poker-Programm

Seit jeher sind Strategiespiele das beliebteste Experimentierfeld für die sogenannte "Künstliche Intelligenz". Jetzt vermelden kanadische Wissenschaftler einen Meilenstein. Sie haben einen Algorithmus entwickelt, der eine populäre Poker-Variante annähernd perfekt spielt.

Von Michael Gessat |
    Dass beim Pokern das Kartenglück die entscheidende Rolle spielt, das behaupten nur ahnungslose Laien - oder Leute in Finanz- oder Ordnungsbehörden, die das überaus populäre Zocken im Internet besteuern oder verbieten wollen. Aber natürlich kann auch das Pokerprogramm, das Michael Bowling von der University of Alberta im kanadischen Edmonton zusammen mit seinen Kollegen über viele Jahre hinweg entwickelt hat, nur passen, wenn es ein miserables Blatt auf die Hand bekommt.
    "Wenn wir von "perfekten" Algorithmus sprechen, dann natürlich nur nach einer sehr langen Spielserie, so wie das ja auch beim Pokern üblich ist. In diesem Fall haben wir eine Strategie entwickelt, die unser Programm unschlagbar macht. Auf lange Sicht würde es auch gegen einen absolut perfekten Gegner nicht verlieren."
    Stärkster Algorithmus für Pokerprogramme
    Im Gegensatz zu Dame oder Schach sind beim Poker nicht alle relevanten Informationen in jeder einzelnen Entscheidungssituation verfügbar - die Spieler wissen nicht, welche Karten ihre Gegner auf der Hand haben, sie wissen nicht, welche Karten als Nächste aufgedeckt werden.
    Im richtigen Leben gibt es für solche Situationen zumindest einen Trost: "Nachher ist man immer schlauer." Und genau nach diesem Motto funktioniert der bislang stärkste Algorithmus für Pokerprogramme. CRM heißt das Verfahren, und das steht für "Counterfactual regret minimization", auf Deutsch also "nachträgliche Bedauerns-Minimierung":
    "Der Algorithmus fragt sich: Wie viel Geld hätte ich gewonnen, wenn ich anders gespielt hätte. Und geht dann zurück und wählt eine andere Strategie und setzt diesen Prozess immer und immer wieder fort – und verfeinert seine Strategie im Spiel gegen sich selbst."
    Nach einer ausreichend großen Zahl von Durchläufen kann der Algorithmus also ermitteln, welche Entscheidung in einer konkreten Spielsituation mit der höchsten Wahrscheinlichkeit optimal ist. Im Spiel selbst dann rechnet ein CRM-Pokerprogramm nichts mehr voraus - es schaut schlicht in einer Datenbank nach. Nur - diese Datenbank erst einmal zu erstellen, das ist alles andere als trivial. Mit dem CRM-Verfahren war der Entscheidungsbaum immer noch so gigantisch, dass die Datenmenge schlicht nicht in den Hauptspeicher verfügbarer Computersysteme passte. Aber Bowlings Kollege Oskari Tammelin aus Finnland konnte den Algorithmus entscheidend verbessern:"
    "Die neue Idee bei CRM+ ist, das wir alte schlechte Entscheidungen ab einer bestimmten Stelle vergessen und uns nur an nur die guten erinnern. Das coole ist: Das ändert nichts am Ergebnis der Optimierung, aber die Trainingsphase ist viel kürzer."
    Perfekte Strategie
    Hinzu kamen neue, ausgefeilte Komprimierungsstrategien, mit denen sich der gestutzte Entscheidungsbaum endlich komplett handhaben ließ. Das Ergebnis: Die Poker-Variante Texas Hold'em mit festen Einsätzen kann als gelöst gelten - zumindest ist die Strategie des CRM+-Programms nicht mehr von einer perfekten Strategie unterscheidbar. Alles nur Spielerei? Nein, sagt Michael Bowling – auch im Sicherheitsbereich gebe es Situationen, die dem Poker ähneln. Polizei oder Sicherheitskräfte am Flughafen zum Beispiel müssen Kontrollen so durchführen, dass sie nicht klar vorhersagbar sind. Und mögliche Angreifer wiederum können versuchen, vorhandene Sicherheitskonzepte auszuhebeln - mit einer Vielzahl von Optionen.
    "All diese Möglichkeiten zu berücksichtigen klappt mit derzeitigen Computern nicht, die Komplexität ist zu groß. Es ist also das Hauptziel in der Künstlichen Intelligenz, Ideen, die in kleinem Maßstab funktionieren, hochzuskalieren - sodass sie auch in dem Maßstab funktionieren, in dem Menschen typischerweise Entscheidungen treffen."