Ich weiß, dass der Titel der Frage etwas vage ist, aber tragen Sie mit mir hier ist das Problem, jedes Mal, wenn ich ein Spiel oder einen Bot für ein Spiel schreibe, benutze ich eine Zustandsmaschine, einen Entscheidungsbaum oder einen Verhaltensbaum. Das Problem mit diesen Techniken besteht darin, dass ich vorschreibe alle Bedingungen, die Charakter / Bot begegnen wird, so dass der Benutzer etwas Unerwartetes tut, dass ich keine Bedingung für sie verliere.
Im Moment arbeite ich an einem Starcraft-Bot (bwapi), benutze State Machines Ich denke daran, eine einzelne State Machine für jede Einheit und einen Master Commanding Lothers zu verwenden, aber es erfordert immer noch ich vorprogrammieren und Für ein Spiel wie Starcraft ist es unmöglich, die einzige Art und Weise, wie ich daran denken kann, dass ich es zum Lernen bringen kann, ist die Verwendung von GP, um diese Zustandsautomaten zu entwickeln.
Sagen Sie, es gibt eine Brücke auf der Karte, wenn 20 Marines gleichzeitig versuchen, durch die Brücke zu gehen, es wird einen großen Stau geben, welche Techniken ich verwenden kann, damit sie aus einem Fehler lernen kann? Ich muss also keine Bedingung vorprogrammieren, die besagt, dass man nacheinander durch die Brücke geht.
EDIT: Nur weil eine Frage die Wörter Starcraft oder Bot enthält, macht es das nicht automatisch zur Frage, ob diese Frage auch für Robotik gilt.
Um irgendwohin zu kommen, müssen Sie zuerst die empirische Messung der Fitness für Ihre Bots definieren. Es muss etwas viel klarer sein als "großer Stau".
Wie messen Sie das?
Was gewinnt? Gibt es numerische Indikatoren, die Ihr Bot "gewinnt"? Löse dieses Problem zuerst, und wenn du einen Bot auf eine andere Art bewerten kannst, schließe ihn als Fitness-Funktion für einen GP-Algorithmus an.
Sie stellen hier zwei verschiedene Fragen.
Der erste ist "Was ist eine KI, die lernen kann"? Das ist die allgemeine Frage, die maschinelles Lernen Forschung zu beantworten versucht. Es gibt Dutzende verschiedener Tools für die Implementierung von maschinellem Lernen, aber kein Wundermittel für Ihre Anwendung. Sie müssen viel genauer darüber nachdenken, was die KI "lernen" soll - was werden ihre Eingaben sein und was wird sie ausgeben?
Die zweite ist "wie können 20 Marines gleichzeitig eine Brücke überqueren, ohne sich in ein Cluster zu verwandeln". Sie beschreiben Gruppenpfadfindung , bei der es sich um einen anderen Bereich der KI handelt, der heuristische Suche genannt wird. Das gleichzeitige Lösen eines Pfades für mehrere Einheiten (Agenten) hat seine eigenen Algorithmen, ist aber im Allgemeinen ein viel besser verstandenes Problem als Ihr erstes. Von Kopf bis Kopf können Sie einen Lösungsansatz für eine Teilmenge der Einheiten gleichzeitig verwenden (abhängig von der Breite der Brücke) und das Element in jeder Gruppe gleichzeitig verschieben. Sie können auch versuchen, für jeden einzelnen Marine zu beginnen, beginnend mit dem, der der anderen Seite der Brücke am nächsten ist.
Wenn Sie die Google-Suche verwenden, werden Sie viel mehr Informationen erhalten, als ich in eine Antwort hineinstopfen kann, vor allem, weil Ihre Frage eher offen ist (Lernsysteme).
Da Sie bereits endliche Automaten verwenden, sollten Sie sich KB-NEAT ansehen.
Es ist eine Neuroevolutionstechnik; das heißt, die Schaffung neuronaler Netzwerke durch Evolution.
Sehen Sie sich auch rtNEAT an, was sehr nützlich sein kann. Eine gewöhnliche Implementierung von NEAT verwendet einen Generationen-Ansatz, das heißt, eine Anzahl von Spielen, sagen wir hundert, wählt die besten Kandidaten aus und erzeugt daraus Nachkommen. (Andere erwähnte Fitness; diese wird immer im evolutionären Ansatz verwendet, und somit auch hier) rtNEAT erlaubt die Evolution in Echtzeit zu geschehen; das heißt, während eines Spiels. (Das erfordert eine ausgefeiltere Fitness-Berechnung, wie es Midgame passiert, wo Sie immer noch nicht wissen, das Ergebnis)
Die Implementierung ist eigentlich nicht so schwer, aber der Schlüssel zu dieser Technik ist die genetische Geschichte, die für den evolutionären Prozess entscheidend ist. (Es ist auch, was diese Technik im Vergleich zu früheren Versuchen als Neurovolution so erstaunlich macht; das Problem liegt hier darin, dass die Eingabe und die Ausgabe identisch sein müssen, und das mag nicht der Fall sein)
Oh, und Ihr Problem kann entweder von einem Planer auf der höheren Ebene gelöst werden, oder die Einheiten können es selbst lernen. Und Eingabe, die die nächsten freundlichen Einheiten und Hindernisse enthält, könnte mit der richtigen Fitness lernen, dass es kontraproduktiv ist, die Pfeife sozusagen zu takten. Dies wird emergentes Verhalten genannt, und es wurde gezeigt, dass die obigen Techniken in der Lage sind, ein solches Verhalten autonom zu entwickeln.
Hier ist eine Implementierung, die ich sehr schön finde, um Ihre Arbeit zu gründen;
Das obige Beispiel verwendet Generationen. Ich habe keine Implementierung von rtNEAT gesehen. Aber Sie können sich das Buch "Anpassung in natürlichen und künstlichen Systemen" von John Holland ansehen. Zugegeben, es mag schwer zu lesen sein, da es sehr mathematisch ist. Aber überspringen Sie das meiste und schauen Sie sich die Vorschläge bei Algorithmen an. Es ist allgemein für alle evolutionären Algorithmen, von denen Neuroevolution ein Unterfeld ist. Es hat einen Algorithmus, der in der Regel von rtNEAT verwendet wird. (Und wenn Sie mit der Genetik, die in evolutionären Algorithmen verwendet wird, nicht vertraut sind, definiert es schön, was ein Gen, Allel, Chromosom, Phänotyp und Genom ist, das Sie in den NEAT Publikationen finden werden; NEAT verwendet Genom um Dinge zu beschreiben Allgemein, das ist nur ein Satz von Chromosomen, die zusammen den Phänotyp beschreiben, da die Codierung ein wenig mehr als nur genetische Algorithmen und genetische Programmierung beteiligt ist)
Die Homepage der Technik ist hier;
Hier ist die Publikation in chronologischer Reihenfolge;
(Der KB-NEAT verwendet rtNEAT bereits in der obigen Veröffentlichung)
Der Punkt ist, dass Sie im Grunde nehmen können, was Sie haben, es in eine neuroevolutionäre Technik bringen und sich von dort entwickeln. Es ist eine Mischung aus domänenspezifischer AI und Machine Learning AI.
Oh und eine Notiz; der evolutionsteil ist prozessorintensiv, zumindest ohne rtNEAT. rtNEAT ist stattdessen zeitintensiv, da Sie viel dagegen spielen müssen, bevor es lernt. (KB-NEAT gibt ihm natürlich eine Intelligenzbasis.) Wenn es jedoch entwickelt wird, ist es sehr, sehr schnell, da die Antwort von einem neuronalen Netzwerk sehr schnell zu berechnen ist. (Es ist eine ziemlich kleine Grafik, und es gibt keine Suche beteiligt)
Oh, und zweite Sache; Sie müssen intensiv über Eingabe und Ausgabe nachdenken. Die Ausgabe kann einfach sein, denn das ermöglicht das Spiel deinen Einheiten. Aber die Eingabe ist das, was sie sehen sollen, und Sie können nicht alles einschließen; Das würde das Problem zu schwierig für die Entwicklung machen, zumindest in realistischer Zeit. (Obwohl es theoretisch zur unendlichen Zeit zur optimalen Lösung konvergiert)
Oh, und eine dritte Note; Sie können mehrere Gehirne für die Einheiten entwickeln und sogar unterschiedliche Gehirne für jeden Einheitentyp haben. Der Himmel ist die Grenze. Vielleicht möchtest du ein Gehirn für jede Technologieebene deines oder des Feindes haben. Dies erfordert natürlich zusätzliche Zeit, aber die Gehirne sind klein im Speicher, so dass die Menge kein Problem ist.
Ack, und eine vierte Note; Dies ist eine Black-Box-Technik. Sie können das Gehirn nicht zurück in eine FSM konvertieren, fürchte ich. Die Kodierung in einem neuronalen Netzwerk ist nicht menschlich verständlich, und daher kann nicht genau gewusst werden, wie genau es funktioniert. Es besteht also die Gefahr, dass Sie mit etwas enden, das Sie mögen, aber Sie können nicht verstehen, warum. Und Sie können dieses Wissen nicht einfach mit anderen Agenten teilen. (Sie können es natürlich als Basis verwenden, um für diese ein neues Verhalten zu entwickeln)
Implementiert die Starcraft AI die Bewegung der Einheiten nicht schon? z.B. Wähle einfach 12 Marines aus und sag ihnen dann, dass sie sich wie ein menschlicher Spieler über die Brücke bewegen sollen. Natürlich ist die KI sehr fehlerhaft und nicht annähernd so gut wie die Schwarm-KI von SCII. Ich denke jedoch, dass es viele andere Probleme beim Entwerfen einer KI gibt, bevor Sie sich um das Mikromanagement jeder einzelnen Einheit kümmern müssen.
Zum Beispiel ist es wohl wichtiger, zu wissen, wo / wann Sie Ihre Einheiten positionieren sollen, als herauszufinden, wie Sie dies mit 100% Effizienz erreichen können.
Ich persönlich denke, der beste Weg, dieses Spiel anzugehen, ist der Einsatz von Zustandsautomaten. Es gibt Schlüsselphasen in einem Spiel, auf die es richtige Antworten gibt (z. B. sind lurker out? Sind Wissenschaftsschiffe ?, usw.). Aber anstatt jede einzelne Einheit zu einem SM zu machen, konzentriere dich eher auf eine größere Einheit wie eine Kontrollgruppe von Einheiten. Ich glaube, das vereinfacht die Dinge sehr und wenn du später bist, kannst du das Mikro deiner KI bei Bedarf verbessern.
Ich denke, dass es wirklich eine schlechte Idee ist, deine Charaktere zu lernen. Sie werden Bewusstsein entwickeln, aus dem Computer ausbrechen und versuchen, dich mit einem Mauskabel im Schlaf zu erwürgen.
Ok, Spaß. Ich denke, es ist nur Übertechnik. Die Entwicklung eines Charakters wird ihn nicht unbedingt robust auf alle Eventualitäten reagieren lassen, aber es wird wahrscheinlich sehr schwierig sein, daran zu arbeiten, ihn zu erweitern und einen Überblick über seine Attribute zu behalten.
Sie könnten an einem zielbasierten Ansatz interessiert sein:
Es ist ein bisschen anstrengend, aber auf lange Sicht macht es viel sauberer und einfacher, das Verhalten Ihrer Jungs zu erweitern.
Anstatt Ihnen einen Vorschlag für bestimmte Algorithmen oder Techniken zu geben, denke ich, dass es hilfreich wäre, zuerst das Problem anzusprechen, das Sie lösen möchten. Ich spiele oft StarCraft, also weiß ich, was du unter "großer Stau" meinst. "Großer Stau" ist jedoch nur ein Label und im Zusammenhang mit maschinellem Lernen bedeutungslos.
Man könnte sagen, dass ein Bot in seiner speziellen Domäne aus Erfahrung E in Bezug auf eine Klasse von Aufgaben T und Leistungsmaß P lernt, wenn seine Leistung bei Aufgaben in T, wie durch P gemessen, mit der Erfahrung E verbessert wird / p>
Wir müssen jetzt daran arbeiten, E, T und P auf eine Weise zu definieren, die für jedes Problem, das du wahrscheinlich im Spiel findest, sinnvoll ist. Zum Beispiel könnte die Klasse von Aufgaben das Verschieben von Einheiten von einem Bereich zu einem anderen in einer Gruppe umfassen. Dieser Bereich weist möglicherweise einige Merkmale auf, die darauf hinweisen, dass er schmal ist und es daher unmöglich ist, die Einheiten in der optimalen Gruppengröße zu verschieben. Das Leistungsmaß könnte also die Zeit sein, die der Einheitsfluss (die Bewegung einiger Marinesoldaten pro Zeiteinheit pro Flächeneinheit) sein kann. Sie möchten diesen Fluss natürlich durch ein Volumen messen, das nur die normalisierte Summe der Flussvorgänge ist. Mit Erfahrung maximieren Sie diesen Fluss.
Sobald Sie dieses Problem ein wenig besser verstehen, können Sie damit beginnen, Designs zu entwickeln, die alle Ihre Anforderungen am besten verkörpern.
Tags und Links algorithm language-agnostic artificial-intelligence