FAQ - Poker als KI Domäne

Warum sind Spiele für die Künstliche Intelligenz interessant?

Spiele waren für die Künstliche Intelligenz immer schon eine interessante Herausforderung, da sie in gewisser Hinsicht erlauben, Intelligenzleistung isoliert von Sensorik und Körper zu betrachten. Das heißt, man braucht keine vollständigen Roboter zu bauen, um Schach oder Poker zu spielen, sondern kann sich auf die Spielintelligenz konzentrieren.

Dabei muß aber natürlich gesagt werden, dass die Denkprozesse intelligenter Schach- oder Poker-Bots sich grundlegend von den Denkprozessen menschlicher Spieler unterscheiden. Im Schach zum Beispiel rührt der Erfolg der Maschine Deep Blue gegen den damaligen Weltmeister Garri Kasparov nicht etwa daher, daß Deep Blue mehr vom Schach verstünde als Kasparov, sondern hauptsächlich daher, daß es 200 Millionen Stellungen pro Sekunde analysieren konnte und auf eine große Partie-Datenbank Zugriff hatte. Bei aller Kritik an der Methodik (und die gab es auch innerhalb der KI-Community) muß man es dennoch als einen großen Erfolg einschätzen, daß erstmals (oder zumindest erstmals so prominent) die Maschine dem Menschen in einer Verstandestätigkeit überlegen war.

Was ist der State-of-the-Art in Game Playing?

Die Forschung der KI im Bereich Spiele ist sehr aktiv und sehr vielgestalt. Es gibt große Erfolge auf verschiedensten Gebieten.

• Viele Spiele sind schon komplett gelöst. Das jüngste Beispiel dafür ist Dame, wo nach 18 Jahren Rechenleistung das Spiel 2007 gelöst wurde. Es wurde also durch Analyse aller möglichen Spielvarianten bewiesen, daß der weiße Spieler bei bestem Spiel nicht verlieren, aber bei bestem Gegenspiel auch nicht gewinnen kann. Auf ähnliche Art und Weise haben jüngst Forscher an der Uni Bremen das Spiel Fuchs und Henne gelöst. Andere Spiele, die bereits gelöst sind, sind (natürlich) Tic-Tac-Toe, Mühle und 4-gewinnt.

• In vielen Spielen (wie z.B. Schach oder Othello) sind die Maschinen aufgrund ihrer großen Rechenkapazität überlegen.

• Aber Computer gewinnen nicht nur durch überlegene Suchtechniken. Das beste Beispiel dafür ist TD-Gammon, ein Backgammon-Programm, das aus Millionen von Spielen gegen sich selbst gelernt hat, die Gewinn-Chancen in Backgammon-Stellungen besser einzuschätzen als jeder Mensch. Es hat danach nicht nur auf weltmeisterlichem Niveau gespielt, sondern auch dazu geführt, daß starke Spieler ihr Eröffnungsrepertoire in einigen Punkten an den von TD-Gammon gewählten Weg angepaßt haben.

• Bei vielen Spielen ist jedoch der Mensch noch überlegen. Die besten Beispiele dafür sind Go und Poker, wobei viele Leute denken, daß Poker als nächstes prominentes Spiel fallen wird.

Was ist an Poker interessant für die KI?

Poker ist eine hervorragende Domäne zur Erprobung und Entwicklung von KI-Techniken. Im Vergleich zu Spielen wie Schach hat es Charakteristika, die das Spiel interessanter und schwieriger machen

• Multi-Player

• unvollständige Information

• zufällige Komponenten

Diese Charakteristika sind auch in zahlreichen real-world Anwendungen typisch.

Besonders interessant ist Poker jedoch, da es ein Spiel ist, das ohne adaptives Spiel (also ohne Verwendungen von Techniken des maschinelles Lernens) nicht lösbar ist. Der Grund ist, daß optimales Spiel im Sinne der Spieltheorie nicht unbedingt gewinnversprechend ist. Das kann man vielleicht am besten anhand eines einfacheren Spiels erklären: Schere-Stein-Papier

Es ist bekannt und nicht schwer zu überlegen, daß eine optimale Spielstrategie in diesem Spiel ist, wenn man zufällig eine der drei Optionen auswählt. Wenn das beide Spieler machen, kann kein Spieler verlieren (aber auch keiner gewinnen). Dieses Gleichgewicht ist auch als Nash-Gleichgewicht bekannt.

Weicht jedoch Spieler B ab (und spielt zum Beispiel immer nur Stein), und Spieler A spielt nach wie vor die optimale Spielstrategie, ändert sich nichts. Beide Spieler werden nach wie vor 1/3 gewinnen, 1/3 verlieren, und 1/3 unentschieden spielen. Um gewinnen zu können, muß Spieler B also

1. die fehlerhafte Strategie von Spieler A erkennen und

2. dieses ausbeuten (indem er dazu übergeht, immer Papier zu spielen)

Dadurch wird Spieler B aber selbst ebenfall wieder angreifbar!

Bei Poker ist die Situation ähnlich, aber viel komplexer. Es ist bei einem derartig hochkomplexen Spiel schon nicht einfach, die optimale Strategie zu finden (daran wird gerade intensiv geforscht), aber selbst wenn man diese hätte, könnte man vermutlich nicht gewinnen. Wesentlich ist, daß man die Spielstrategie des Gegners zumindest rudimentär erkennen kann, und seine eigene Strategie an diese anpaßt.

Was ist der State-of-the-Art in Computer Poker?

Die besten Computer-Poker Programme werden z.Z. an der University of Alberta entwickelt. Dort wird schon seit Beginn der 90er Jahre an Computer-Poker geforscht, und dementsprechend groß ist der Vorsprung. Dieses Jahr wurden sie jedoch in einigen Wettkämpfen bereits geschlagen (von einem Bot aus UK).

2007 und 2008 gab es bereits zwei Man-Machine Poker Wettkämpfe gegen Spitzen-Poker-Spieler, von denen der Bot aus Alberta den ersten knapp verloren (1-1-2 in 4 x 500 Hands settings) und den zweiten knapp gewonnen hat (2-1-1 in 4 x 500 Hands).

Alles waren jedoch 2-Player-Limit Bots. In einem No-Limit und/oder Multi-Player-Setting ist das Problem noch schwieriger.

• Für No-Limit denkt Alberta, daß sie im Moment gutes Amateur-Niveau haben

• Ebenso für Multi-Player.

• Im Moment konzentrieren Sie sich auf No-limit Poker, wir versuchen unseren Schwerpunkt auf Multi-Player zu legen. Sind beide Probleme gelöst, kann man die beiden auch wieder zusammenführen.

Das kommerzielle Programm Poker Academy basiert auf der Software der University of Alberta.

Wie funktioniert unser Poker-Bot?

Wie viele Spiel-Programme funktioniert auch dieser Bot auf der Basis von Suche. Im Gegensatz zu konventionellen Spielen wie Schach werden jedoch nicht alle Züge bis zu einer bestimmten Anzahl von Zügen im Voraus berechnet (und die resultierenden Stellungen dann bewertet), sondern es wird eine große Anzahl von Spielen (mit unterschiedlichen Verteilungen der bekannten Karten) bis zum Ende gespielt und für jede der möglichen Aktionen (Fold, Check/Call, Bet/Raise) bestimmt, welche dabei im Durchschnitt am profitabelsten war.

Im einfachsten Fall werden dabei die Karten zufällig verteilt und die Spieler handeln zufällig.

Für eine verbesserte Spielstärke muß man sich jedoch von dieser unrealistischen Annahme lösen, und die zufälligen Verteilungen und Züge anpassen:

• der momentane Spielzustand (die Biet-Geschichte der Spieler für jede Straße) beeinflußt die Wahrscheinlichkeit, mit der sie bestimmte Karten erhalten sollten (z.B. starke Karten bei starken Geboten und umgekehrt)

• und die erhaltenen Karten (und der Spielzustand) beeinflussen umgekehrt das Verhalten der Spieler in diesen zufälligen Simulationen.

Für die Kartenvorhersage verwendet der Bot ein Neurales Netzwerk, das anhand von Spieldaten darauf trainiert wurde vorherzusagen, welche von 11 Karten-Kategorien (Pair, Top-Pair, Flush-Draw, etc.) der Gegenspieler hält.

Die Aktion des Gegners wird auf eine ähnliche Art und Weise vorhergesagt.

Eine wichtige Komponente ist eine Abstraktion des Zustandsraums, z.B. die Einteilung von Karten in einige wenige Gruppen (z.B. stark, mittel, schwach), sowie auch die Charakterisierung des Spielers in einige wenige Typen:

• Tight/Loose

• Aggressive/Passive