Wie würden Sie ein maschinelles Lernsystem entwickeln, um Angry Birds zu spielen?

22

Nachdem ich viel zu viel Angry Birds gespielt hatte, begann ich meine eigenen Strategien zu beobachten. Es stellt sich heraus, dass ich einen sehr spezifischen Ansatz entwickelt habe, um auf jeder Ebene 3 Sterne zu bekommen.

Das brachte mich auf die Herausforderung, ein maschinelles Lernsystem zu entwickeln, mit dem Angry Birds gespielt werden kann. Die Interaktion mit dem Spiel und das Starten der Vögel ist trivial. Aber eine Frage, die ich hatte, betrifft die "Bausteine" des Systems.

Maschinelle Lernsysteme scheinen mit einfachen Konzepten zu arbeiten oder das Problem zu verstehen. Dies wird häufig als Merkmale als Eingaben codiert. Das System muss also in der Lage sein, einige Konzepte auf hoher Ebene zu verstehen, um eine Strategie zu generieren.

Ist das wahr? Was sind die Herausforderungen oder schwierigen Teile bei der Entwicklung eines solchen Systems?

EDIT # 1:

Hier ist eine Klarstellung. 3 Sterne zu bekommen ist ein schwieriges Problem, da man die Punkte maximieren muss. Dies kann auf zwei nicht ausschließliche Arten erfolgen: 1) Minimierung der Anzahl der verwendeten Vögel (Sie erhalten 10.000 Punkte für jeden nicht verwendeten Vogel). 2) Maximiert die Zerstörung von Glas, Holz und anderen Objekten. Jedes zerstörte Objekt gibt dir Punkte. Es ist möglich, Objekte im Wert von mehr als 10.000 Punkten mit einem einzigen Vogel zu zerstören.

Hier finden Sie weitere Erklärungen zu "High-Level-Konzepten". Um die oben beschriebenen Punkte zu maximieren, müssen Sie die besonderen Kräfte jedes Vogels einsetzen. Das bedeutet also, dass je nach Kartenlayout verschiedene Vögel mit unterschiedlichen Flugbahnen abgefeuert werden. Und während ich spiele, entwickle ich eine Strategie, die bestimmte Gebiete mit bestimmten Vögeln in einer bestimmten Reihenfolge zerstört.

Es scheint, dass das System nicht lernen könnte, 3 Sterne zu bekommen, ohne zu verstehen, wie man jeden Vogel einsetzt, um ein bestimmtes Gebiet zu zerstören. Wie verwalten und codieren Sie so etwas? Wie stellen Sie sicher, dass das System diese übergeordneten Konzepte erlernen kann?

B Sieben
quelle

Antworten:

13

Angenommen, Sie könnten die richtigen Hooks in die Software einbinden (oder Sie arbeiten mit Ihrem eigenen Mock-up), wären einige Dinge hier einfach und andere weniger. Das ist ein ziemlich schwieriges Problem, denke ich. Wie von carlosdc erwähnt, ist Reinforcement Learning (RL) ein möglicher Weg, obwohl ich nicht sicher bin, ob es der richtige ist.

Wenn Sie beginnen, müssen Sie definieren, was Ihr Statusraum , Ihr Aktionsraum , Ihre Übergangsdynamik und Ihre Belohnungsfunktion sind. Die Zustands- / Aktionsräume können kontinuierlich oder diskret sein, und die Übergangsdynamik kann durch das Problem vorgegeben oder mathematisch modelliert werden. Schließlich kann die Belohnungsfunktion a priori gegeben oder abgetastet werden (mit oder ohne Rauschen).

Der Aktionsraum ist einfach: Es ist einfach die Richtung und Kraft, auf die Sie den aktuellen Vogel schießen. Für den Menschen ist dies ein diskretes Problem (die Maus / der Touchscreen ist ein digitales Eingabegerät) - zum Beispiel gibt es 32 mögliche Richtungen und 10 mögliche Kräfte, was 320 mögliche Aktionen ergibt.

Die Belohnungsfunktion ist auch ziemlich einfach abzuleiten: Das Ziel ist es, alle Schweine mit der geringsten Anzahl von Vögeln loszuwerden (OK, es gibt also zusätzliche Punkte für andere Dinge, aber lassen Sie uns dies vorerst ignorieren). Das Beste wäre, wenn wir die tatsächliche Funktion kennen würden, die Punkte aus dem Töten von Schweinen generiert (abhängig von der Größe des Schweins usw. IIRC) - aber für eine einzelne Ebene könnte dies perfekt modelliert werden.

Der Zustandsraum und die Übergangsdynamik sind viel schwieriger. Um dies richtig zu modellieren, müssten wir das gesamte Layout der Karte und die Physik des Spiels kennen. Die Übergangsdynamik lautet "Wenn ich im Zustand x bin und die Aktion y durchführe , lande ich im Zustand z ". Sie können die Schwierigkeit dieses Problems erkennen, zum einen, weil es aufgrund der komplexen Physik des Systems äußerst schwierig sein wird, dies genau zu modellieren, und zum anderen, weil es nach der ersten Runde so viele mögliche resultierende Zustände gibt (320), und dies ist, wenn Wir gehen davon aus, dass es keine Stochastizität in der Physik-Engine gibt. Ich denke, zu diesem Zeitpunkt würden Sie aufgeben und nach Hause gehen.

Ein anderer Ansatz besteht darin, es so zu behandeln, wie es ein Mensch von Anfang an tut - dh Versuch und Irrtum. Zumindest der Mensch feuert praktisch willkürlich (obwohl er ziemlich stark ist, bevor er die Vögel zu den Schweinen schickt, was sich jedoch leicht einkodieren lässt), bis eine Reihe guter Aktionen gefunden werden. Dies ist eher wie der mehrarmige BanditRahmen. Die "Arme" der Banditen sind hier die möglichen Aktionen. Der Algorithmus versucht, Erkundung und Ausbeutung in ein Gleichgewicht zu bringen - dh den Aktionsraum zu erkunden und gute Aktionen auszunutzen, wenn sie gefunden werden. Dazu müssen Sie nichts über die zugrunde liegende Dynamik wissen - Sie müssen nur über Aktionen und Belohnungen Bescheid wissen. Um es vollständig zu machen, müssten Sie einen Arm für jede mögliche Aktion über alle Runden haben (z. B. Sie haben 5 Vögel * 320 Aktion = 320 ^ 5 = ca. 10 ^ 12 Aktionen), also ist der Aktionsraum sehr groß! Sie können jedoch einige Tricks anwenden, um dies zu verbessern, wenn Sie ein wenig wissenüber den Staatsraum. Zum Beispiel könnten Sie wahrscheinlich Aktionen ausschließen, die den Vogel von den Schweinen wegschicken, in den Boden oder ohne genügend Kraft, um einen von ihnen zu erreichen. Außerdem müssen Sie nur den fünften Vogel erreichen, wenn Sie die Schweine in den vorherigen Runden nicht getötet haben, sodass ein Teil der Aktionszustände tatsächlich nicht möglich ist. Dies erinnert ein wenig an den Ansatz, der im Algorithmus MoGo verwendet wird , einem Computerprogramm zum Spielen von Go auf der Grundlage der oberen Vertrauensgrenzen für Bäume , einem Ansatz zur Lösung des mehrarmigen Banditenproblems.

tdc
quelle
1
Gute Antwort! Ich denke, der Aktionsraum ist viel größer als 320 mögliche Aktionen. Jedes Pixel, das mit einem Bogen von etwa 0,7 Zoll (auf dem iPad) von horizontal links nach vertikal unten überstrichen wird, erzeugt eine andere Flugbahn und ein anderes Ergebnis. Das iPad hat eine Auflösung von 132 dpi, sodass möglicherweise etwa 8.000 Pixel zum Starten zur Auswahl stehen. Ich wollte mich nicht mit den Details befassen, aber ändert sich die Antwort, wenn der Aktionsbereich auf 8.000 erhöht wird? Wie kann man mit einem größeren Aktionsraum arbeiten?
B Seven
Der Versuch, die Dynamik zu simulieren, ist eine ganz andere (und schwierige) Frage. Ich denke, für diese Diskussion sollten wir davon ausgehen, dass wir Zugriff auf den Quellcode haben und die Statusinformationen genau abrufen können. Die Belohnungsfunktion ist auch nicht nur, wie viele Schweine Sie töten. Um 3 Sterne auf einem Level zu bekommen, musst du etwas Schwierigeres tun. Siehe Bearbeiten auf Frage.
B Seven
@BSeven Im Prinzip nicht, der größere Aktionsraum ändert nichts an der Antwort, obwohl Sie möglicherweise mehr Bereinigen und viel mehr Rechenleistung benötigen müssen ;-) Beachten Sie jedoch, dass dies ein perfekter Kandidat für die parallele Verarbeitung ist. Die Frage nach den Sternen ist schwierig, da dies impliziert, dass es keine einfache Zuordnung von Abschüssen zu Sternen gibt, obwohl ich dachte, dass Sie mehr Sterne erhalten, indem Sie einfach die Grenzwerte für Punkte überschreiten (normalerweise wird dies durch die Verwendung weniger Vögel erreicht). Wenn nicht, müssten Sie den Explorationsaufwand künstlich erhöhen, um zu vermeiden, dass Sie sich zu früh auf suboptimale Pfade begeben.
tdc
8

Coole Frage!

Anscheinend handelt es sich bei dieser Frage um die natürliche Technik für diese Art von Problem. Ich denke, die natürliche Technik für diese Art von Problem ist das Verstärkungslernen (RL). In RL geht es darum, wie ein Agent in einer Umgebung Maßnahmen ergreifen sollte, um eine möglichst hohe kumulative Belohnung zu erzielen. Der vielleicht bekannteste Algorithmus für RL ist das Q-Lernen . Ich denke, dies ist die erste Frage auf dieser Website zum Thema Lernen zur Stärkung.

Ich denke, was Sie fragen, ist wahr, wenn Sie versuchen, dies als Klassifizierung / Regression zu betrachten, aber diese scheinen nicht das richtige Werkzeug für dieses Problem zu sein. Dies ist natürlich ein RL-Problem, bei dem Abfolgen von Aktionen und Ergebnissen berücksichtigt werden müssen.

carlosdc
quelle
5

Überprüfen Sie hier, wie andere es tun, oder beteiligen Sie sich selbst: Angry Birds AI Challenge http://ai2012.web.cse.unsw.edu.au/abc.html

Jochen Renz
quelle
Vielleicht können Sie zusammenfassen, worum es in dem Link geht und wie sich das auf die Frage bezieht. Wie es jetzt ist, ist Ihre Antwort als Kommentar besser.
FredrikD
4

Ich habe das gerade in Meta erwähnt. Es gab eine bahnbrechende Verwendung genetischer Algorithmen von Koza, um das Videospiel Pacman zu lösen. Er konstruierte algorithmische Primitive, die erkennen und handeln konnten. Soweit ich mich erinnere, wurden diese in Lisp-ähnlichen Bäumen kombiniert, um größere Algorithmen zu erstellen. Crossover mit Lisp-Bäumen beinhaltet das Ersetzen oder Austauschen von Teilbäumen, die die Algorithmusausdrücke darstellen. die erfolgsfunktion ist so etwas wie "punkte gefressen" oder "punkte plus geister gefressen" oder "zeit am leben geblieben". In diesem Bereich gibt es noch einige Arbeiten. Es gibt einen Koza-Verweis in diesem Artikel, der folgt. Die Übungszeit kann sehr lang und die "Konvergenz" für diese Art von Problemen sehr allmählich sein.

Pac-Man lernen: Ein evolutionärer, regelbasierter Ansatz von Gallagher und Ryan

vzn
quelle