Ganz gleich, ob Sie gegen einen einzelnen Gegner Poker spielen oder sich mit einem anderen potenziellen Käufer in einem Bietergefecht um einen Hauskauf befinden, Sie operieren unter Bedingungen unvollständiger Informationen. Sie wissen, welche Karten Sie beim Pokerspiel auf der Hand haben, und Sie wissen auch, wie viel Sie sich über den Angebotspreis des Hauses hinaus leisten können, aber Sie kennen nicht die Hand Ihres Gegners beim Kartenspiel oder wie hoch der andere Hauskäufer zu gehen bereit ist.
A Papier Das von MIT-Forschern mitverfasste und im April auf der Worldwide Convention on Studying Representations in Rio De Janeiro vorgestellte Buch wird Ihnen nicht sagen, was Sie in solchen Situationen konkret tun sollen. Aber es bietet neue Einblicke in sogenannte Spiele mit unvollständiger Info, bei denen zwei Teilnehmer in einem „Nullsummen“-Wettbewerb gegeneinander antreten, bei dem der Gewinn eines Spielers den Verlust des anderen Spielers bedeutet.
Zu den MIT-Forschern an dem Projekt gehören Sobhan Mohammadpour, ein Doktorand in der Abteilung für Elektrotechnik und Informatik (EECS) und dem Labor für Informations- und Entscheidungssysteme (LIDS) des MIT; und Gabriele Farina, Assistenzprofessorin für EECS und Hauptforscherin am LIDS. Weitere Co-Autoren sind Max Rudolph von der College of Texas in Austin (UT), Nathan Lichtlé von der College of California in Berkeley (UCB), Alexandre Bayen von UCB, J. Zico Kolter von der Carnegie Mellon College (CMU), Amy X. Zhang ’11, MNG ’12 von UT; Eugene Vinitsky von der New York College; und Samuel Sokota von der CMU.
Der Schwerpunkt der neuen Arbeit liegt auf Algorithmen, mit denen neuronale Netze für die Teilnahme an Spielen mit unvollständigen Informationen trainiert werden könnten. In diesem Bereich herrschte seit langem die Annahme vor, dass Algorithmen, die auf Prinzipien der Spieltheorie basieren, in diesem Umfeld eine Vielzahl von Allzweckalgorithmen, sogenannte Coverage-Gradienten-Methoden, die in den 1990er Jahren für die Entscheidungsfindung eingesetzt wurden, deutlich übertreffen würden. Der Begriff „Politik“ bedeutet in diesem Zusammenhang grundsätzlich Strategie, während sich „Gefälle“ auf einen Weg bezieht, der in Richtung der größten Veränderung führt – zum Beispiel auf die Spitze (oder den Fuß) eines Hügels. Richtliniengradientenmethoden werden verwendet, um neuronale Netze darauf zu trainieren, Entscheidungen zu treffen, die sich – in kleinen, aufeinanderfolgenden Schritten – auf ein bestimmtes Ziel zubewegen (metaphorisch gesprochen das Erreichen eines Gipfels), wobei auf dem Weg kontinuierliche Anpassungen und Kurskorrekturen vorgenommen werden, um den Agenten näher an das beabsichtigte Ziel zu bringen.
Obwohl strategische Spiele nicht auf der ursprünglichen Agenda standen, als in den frühen 1990er-Jahren Coverage-Gradient-Methoden konzipiert wurden, fragten sich die Autoren des neuen Papiers dennoch, wie diese Klasse von Algorithmen in Spielen für zwei Spieler abschneiden könnte. Laut Farina wird die Analyse dieser Methoden in Multi-Agent-Umgebungen schwieriger. „Es gibt immer noch eine Richtung, in die Sie gehen können, um Ihre Scenario zu verbessern, aber aufgrund der Aktionen der anderen Spieler kann sich diese Richtung im Laufe des Spiels ständig ändern. Und diese Veränderungen können schnell erfolgen.“
„Es wurde weitgehend davon ausgegangen, dass spezielle spieltheoretische Algorithmen für dieses Szenario der richtige Ansatz sind“, sagt Sokota. „Unsere Studie hat gezeigt, dass Coverage-Gradient-Methoden besser funktionieren können als diese spezialisierten Algorithmen und dass die spezialisierten Algorithmen möglicherweise nicht so intestine funktionieren, wie die Leute dachten – was eine interessante soziologische Frage aufwirft, warum dies so lange unbemerkt blieb. Ein Teil der Antwort liegt darin, dass das Fachgebiet nicht die technische Arbeit geleistet hatte, die für eine gründliche Bewertung der Algorithmen erforderlich struggle, sodass es schwer struggle zu sagen, was funktionierte und was nicht.“
Folglich bestand ein wesentlicher Beitrag dieser Arbeit darin, eine ausgewogene Methode zur Bewertung verschiedener Algorithmen bereitzustellen, die Agenten – additionally neuronalen Netzen – beibringen kann, wie sie in Spielen mit unvollständigen Informationen konkurrieren können. „Wir verfolgen einen anderen Ansatz“, bemerkt Rudolph. „Anders als viele der auf diesem Gebiet veröffentlichten Arbeiten schlagen wir keinen neuen Algorithmus vor, der andere Algorithmen schlagen kann. Wir schlagen einen Benchmark vor, der diese Algorithmen bewerten kann.“
Vereinfacht ausgedrückt besteht ein Benchmark aus einer Software program, die dazu dient, die Leistung von Algorithmen zu bewerten. „Was wir anbieten, ist ein Testgelände oder Spielgelände, auf dem die Leute ihre Algorithmen nehmen, sie für eine bestimmte Aufgabe trainieren und sehen können, wie intestine sie funktionieren“, sagt Farina.
Die Gruppe berechnet die Leistung eines Spielers anhand eines Konzepts namens Ausnutzbarkeit, das misst, wie intestine ein Spieler gegen den „Worst-Case-Gegner“ abschneidet, erklärt Sokota. „In einem Spiel wie Poker wüsste dieser Gegner nicht, was meine Hand ist, aber er wüsste, wie ich mich bei jeder Hand verhalten würde.“ Das Erreichen einer Null auf dieser Skala deutet auf ein perfektes Spiel hin, wohingegen ein hoher Ausnutzbarkeitswert auf ein alles andere als optimales Spiel hinweist.
In den vom Workforce durchgeführten Experimenten wurden fünf Spiele gespielt: zwei Versionen von Phantom Tic-Tac-Toe, bei denen die Spieler nicht sehen können, was ihr Gegner getan hat, außerdem zwei Varianten eines Brettspiels namens Hex mit unvollständigen Informationen und ein weiteres Täuschungsspiel namens Liar’s Cube.
Die größte Herausforderung für die Forscher bestand darin, das Ausnutzbarkeitsmaß für Spiele dieser Größe, die bis zu 30 Milliarden Staaten umfassen kann, zum Laufen zu bringen. Ein „Zustand“ umfasst in diesem Fall nicht nur alle möglichen Spielfeldpositionen, sondern umfasst auch die gesamte Spielgeschichte, einschließlich aller Schritte und Fehltritte auf dem Weg dorthin.
„Es ist, als würde man in einen dunklen Raum blicken, der voller Objekte ist, die man nicht sehen kann“, sagt Mohammadpour. „Irgendwie muss man herausfinden, wo sich diese Objekte befinden und wie sie genau dorthin gelangt sind.“ Frühere Forscher, fügt Mohammadpour hinzu, haben die Ausnutzbarkeit typischerweise für Spiele genutzt, die 100.000 Mal kleiner sind als die in ihrer Studie analysierten.
In den an diesen fünf Spielen durchgeführten Experimenten erzielten neuronale Netze, die mit Coverage-Gradient-Algorithmen trainiert wurden, bessere (niedrigere) Ausnutzbarkeitswerte als Netzwerke, die mit spieltheoretischen Algorithmen trainiert wurden. In Kopf-an-Kopf-Wettbewerben, die in der nächsten Runde stattfanden, schlugen die auf dem Politikgradienten trainierten Netzwerke erneut ihre spieltheoretisch geschulten Gegner. „Diese Ergebnisse waren beruhigend“, sagt Rudolph, „weil sie uns mehr Vertrauen in unseren Benchmarking-Ansatz geben.“
Das Workforce hat seine Benchmarking-Software program frei verfügbar und benutzerfreundlich gemacht. „Man braucht keinen Supercomputer“, sagt Mohammadpour. „Sie können es auf einem gewöhnlichen Laptop computer ausführen. Und alles, was Sie tun müssen, ist, einer häufig verwendeten Sammlung von Benchmarking-Software program namens OpenSpiel eine einzige Codezeile hinzuzufügen.“
Obwohl es sich bei ihren Experimenten um einige ziemlich obskure Spiele handelte, möchte Farina diese Arbeit in einen breiteren Kontext stellen. „Denken Sie daran, dass der Begriff ‚Spiel‘ wirklich für jede strategische Interaktion mit mehreren Agenten gilt“, sagt er. „Die Lehren, die wir aus dieser Forschung ziehen, beschränken sich additionally keineswegs auf Freizeitspiele.“
Vinitsky stimmt zu. „Versteckte Informationen sind ein sehr wichtiges Eigentum der Welt“, sagt er. „Es durchdringt eine Reihe von Dingen – einschließlich militärischer Operationen, Handelsszenarien und Verhandlungen – die alle unter der Bedingung verborgener Informationen durchgeführt werden. Die Idee, dass wir diese Spiele verbessern können, legt nahe, dass wir auch in diesen anderen Situationen bessere Ergebnisse erzielen können.“
Ian Gemp – ein Informatiker und Spieltheorie-Experte bei Google DeepMind, der nicht an dieser Studie beteiligt struggle – findet diese Ergebnisse ermutigend. „Diese Arbeit ist eine überzeugende Erinnerung“, sagt er, „dass die Modernisierung klassischer Instrumente (wie Coverage-Gradient-Methoden) ein äußerst produktiver Weg zur Lösung komplexer strategischer Probleme bleibt.“