Vorläufer des Brettspiels "Stratego", bei dem zwei Spieler versuchen müssen, mit ihren verschiedenen Spielsteinen die Fahne des Gegners zu erobern, gab es bereits zu Beginn des 20. Jahrhunderts. Erstmals registriert wurde das Spiel allerdings erst vor 80 Jahren in den Niederlanden. Das Besondere an dem Spiel für die Wissenschaft: Die künstliche Intelligenz (KI) hat sich daran bisher die Zähne ausgebissen.

Der Grund dafür ist ein kombinierter: "Stratego" erfordert einerseits strategische Weitsicht ähnlich wie Schach. Andererseits muss aber auch auf Basis von nicht vollständigen Informationen entschieden werden, wie beispielsweise bei Poker. Denn bei "Stratego" haben die Figuren unterschiedliche Werte und schlagen verschiedene andere Figuren, werden allerdings anfangs verdeckt platziert. Darüber hinaus gibt es in dem Spiel sehr viele mögliche Optionen und Züge – mehr als bei Go oder Texas Hold'em Poker, also Spielen, bei denen KI in der Vergangenheit große Fortschritte erzielen und alle menschlichen Gegner schlagen konnte.

Neue Grenze der KI-Forschung

Entsprechend stellt nach Expertenansicht das Spielen von "Stratego" auf hohem Niveau eine der nächsten zu durchbrechenden Grenzen in der KI-Forschung dar. Doch nun scheint auch an dieser Front ein Durchbruch gelungen zu sein: Laut einer neuen Studie im Fachblatt "Science" setzte sich das von der KI-Schmiede Deepmind entwickelte Programm "Deep Nash" sowohl in Tests gegen andere "Stratego"-Programme als auch gegen Menschen durch – aber bei weitem nicht so klar wie etwa bei Go.

Gegen andere Programme hatte Deep Nash Gewinnraten zwischen 97 und 100 Prozent. Gegen menschliche Spieler konnte Deep Nash auf der Onlineplattform Gravon in 50 Spielen 84 Prozent der Partien gewinnen und stand damit temporär auf Rang drei unter den "Stratego"-Spielerinnen und -Spielern der Seite. Dabei legte es der Studie zufolge auch Verhalten an den Tag, das als Täuschung oder Bluffen interpretiert werden kann.

Lernen im Spiel gegen sich

Die KI basiert auf einem sogenannten Reinforcement-Learning-Algorithmus und hat beim Spielen gegen sich selbst gelernt – ohne menschliche Demonstration. Das Ziel der Forschenden war es, die KI nach einem sogenannten Nash-Gleichgewicht (benannt nach dem gleichnamigen Nobelpreisträger für Wirtschaftswissenschaften John Nash) suchen zu lassen. Das ist eine Strategie, die stabil ist, weil jeder Spieler bei einem einseitigen Abweichen von der Strategie schlechter dasteht, solange der andere seine Strategie beibehält.

Das Training war jedenfalls jetzt schon aufwendig: "Die Autoren geben gute Performance nach ungefähr zwei Millionen Lernschritten an. Für jeden Lernschritt werden circa 10.000 bis 100.000 Spiele simuliert, was insgesamt rund 10¹⁰ Spiele ausmacht", wie Marc Toussaint erläutert, der Leiter des Fachgebietes Intelligente Systeme an der TU Berlin, der nicht an der Studie beteiligt war. "Wenn ein Mensch eine knappe Stunde pro Spiel bräuchte, entspräche das grob einer Millionen Jahren Spielzeit. Die simulierten Daten sind also enorm."

Weitere Anwendungen sind unklar

In gewisser Weise komprimiere der Lernalgorithmus diese Daten laut Toussaint in ein neuronales Nachschlagewerk, den Actor, das für jede Situation direkt die optimale Aktion liefert – wie von den Autoren betont: ohne weiteres Suchen, Planen oder Vorausschauen. "Das unterstreicht, wie verschiedenartig diese Form der datenbasierten KI zur natürlichen ist."

In einem Nullsummenspiel wie "Stratego" garantiert die Nash-Gleichgewicht-Strategie laut den Deepmind-Fachleuten auch bei starken Gegnern ein gutes Abschneiden. Die Forschenden betonen aber auch, dass es momentan keine Hinweise gibt, ob der der KI zugrundeliegende Algorithmus in anderen Situationen Fortschritte bringen könnte. Sie stellen jedoch in Aussicht, dass diese Art von Algorithmus möglicherweise in Bereichen wie Verkehrsmodellierung, Auktionen oder bei Berechnungen zu Märkten Anwendung finden könnte. (tasch, 1.12.2022)