PacMan Charakter AI Vorschläge für eine optimale nächste Richtung

Erstens ist dies KI für PacMan und nicht für die Geister .

Ich schreibe ein Android Live Wallpaper, das PacMan um Ihre Symbole spielt. Während es Benutzervorschläge über Bildschirmberührungen unterstützt, wird der Großteil des Spiels von einer KI gespielt. Ich bin zu 99% mit der gesamten Programmierung für das Spiel fertig, aber die KI für PacMan selbst ist immer noch extrem schwach. Ich suche Hilfe bei der Entwicklung einer guten KI zur Bestimmung der nächsten Fahrtrichtung von PacMan.

Mein ursprünglicher Plan war folgender:

1. Initialisieren Sie für jede Richtung einen Bewertungszähler mit dem Wert Null.
2. Beginnen Sie an der aktuellen Position und verwenden Sie ein BFS, um die vier möglichen Anfangsrichtungen nach außen zu durchlaufen, indem Sie sie der Warteschlange hinzufügen.

3. Entfernen Sie ein Element aus der Warteschlange, stellen Sie sicher, dass es noch nicht "gesehen" wurde, stellen Sie sicher, dass es sich um eine gültige Boardposition handelt, und addieren Sie zu den entsprechenden Anfangsrichtungen einen Wert für die aktuelle Zelle, basierend auf:

   1. Hat einen Punkt: plus 10
   2. Hat ein Power-Up: plus 50
   3. Hat eine Frucht: plus Fruchtwert (variiert je nach Stufe)
   4. Hat einen Geist, der Angst hat: plus 200
   5. Hat ein Geist in Richtung PacMan: subtrahieren Sie 200
   6. Hat ein Geist von PacMan weg: nichts tun
   7. Hat ein Geist senkrecht: subtrahieren Sie 50
   8. Multiplizieren Sie den Wert der Zelle mit einem Prozentsatz basierend auf der Anzahl der Schritte zur Zelle. Je mehr Schritte von der Anfangsrichtung entfernt sind, desto näher kommt der Wert der Zelle Null.

   und die drei möglichen Richtungen aus der aktuellen Zelle in die Warteschlange stellen.

4. Sobald die Warteschlange leer ist, finden Sie die höchste Punktzahl für jede der vier möglichen Anfangsrichtungen und wählen Sie diese aus.

Auf dem Papier klang es gut für mich, aber die Geister umgeben PacMan extrem schnell und er zuckt in denselben zwei oder drei Zellen hin und her, bis eine ihn erreicht. Das Anpassen der Werte für die Geisterpräsenz hilft auch nicht. Mein nächster Punkt-BFS kann mindestens Level 2 oder 3 erreichen, bevor das Spiel endet.

Ich suche nach Code, Gedanken und / oder Links zu Ressourcen für die Entwicklung einer richtigen KI - vorzugsweise der beiden ersteren. Ich möchte dies irgendwann an diesem Wochenende auf den Markt bringen, also habe ich es etwas eilig. Jede Hilfe wird sehr geschätzt.

Zu Ihrer Information, dies wurde ursprünglich auf StackOverflow veröffentlicht

Tandems Idee eines Algorithmus zum Bergsteigen ist gut. Eine andere ist: eine Variation von A *, um zu sehen, wie weit Sie gehen können, um zu sehen, wie Sie in den nächsten N Runden die höchste Punktzahl erzielen können, wobei N so eingestellt ist, dass das gewünschte Ergebnis erzielt wird.

Die von Ihnen angegebenen Bewertungswerte können als "Kosten für den Umzug" betrachtet werden. Sie sind im Grunde genommen auf dem richtigen Weg, müssen die Werte jedoch anpassen, bis Sie das gewünschte Ergebnis erzielen.

Im Allgemeinen (nicht PacMan-spezifisch) müssen Sie geeignete Werte für zuweisen

• Verwundete den anderen Kerl.
• Einen anderen Kerl getötet.
• Ein anderes Ziel erreicht (außer töten)
• Wurde verwundet.
• Wurde getötet.

und dann suchen Sie nach dem Zug, der in Zukunft zur maximalen Punktzahl von N Runden führen wird. Möglicherweise möchten Sie auch Bewegungen vermeiden, die zu einer Punktzahl unter X führen (z. B. die Kosten für das Sterben). N wird in die Zukunft.

Sobald Sie alle möglichen Züge erzielt haben, Boni hinzugefügt haben, wie gut es in Zukunft ausgehen könnte, und abgezogen, wie schlecht es in Zukunft ausfallen könnte, sortieren Sie einfach das Array und machen den besten Zug.

Lassen Sie uns wissen, wie es ausgeht!

Schauen Sie sich auf jeden Fall dieses Video an: http://www.youtube.com/watch?v=2XjzjAfGWzY

Sie werden wahrscheinlich eine Art Algorithmus zur Suche nach Bergsteigerpfaden wollen .

Sie werden eine Suche durchführen.

• Knoten / Status: Pacman-Standort, Ghost-Standorte, Pellet-Standorte, Gesamtpunktzahl, Gesamtleben.
• Übergang: Pacman bewegt sich nach oben, unten, links oder rechts. Wenn Pacman gegen eine Wand zieht und die Position wechselt, ist das völlig in Ordnung (dies könnte zu einigen wirklich interessanten Stalling-Strategien führen). Wenn Pacman einen Geist trifft, entferne ein Leben und bewege ihn und die Geister zum Ursprung.
• Kosten: Wenn sich Pacman auf ein Pellet 1 bewegt, wenn er sich auf ein leeres Feld 2 bewegt.
  Die Kosten sind etwas knifflig, da sie nicht offensichtlich sind. Die von mir beschriebene Kostenfunktion wird Pacman ermutigen, das Level zu beenden. Dies schließt eine mögliche Strategie aus und wartet nur darauf, dass Bonusfrüchte erscheinen. Aber ich denke, wir wollen, dass der AI Pacman das Labyrinth beendet, auch wenn es eine niedrigere Punktzahl ergibt.
• Ziel: maximale Punktzahl erreicht. Das bedeutet, dass alle Pellets, Früchte und Kraftpellets gegessen werden.

A * oder UCS sind großartig, wenn Sie ein Ziel suchen. Die Art und Weise, wie ich den Zustand / Übergang / Ziel beschrieben habe, wird einen großartigen Weg für Pacman finden, den die KI nicht speziell in Betracht ziehen muss, um den Tod zu vermeiden oder Früchte zu suchen. Es wird das alleine tun. Da das Spiel vollständig deterministisch ist, können Sie von Pacmans Startort aus "suchen" und den optimalen Gehweg bis zum Ende (alle verbrauchten Pellets) als Vorberechnung finden und nur AI Pacman diesen Weg gehen lassen, keine spontane KI. Der Hauptnachteil dieses Ansatzes besteht darin, dass dies bei der CPU-Zeit und dem Speicherverbrauch leicht außer Kontrolle geraten kann.

Anstatt die CPU und den Speicher für die Durchführung einer vollständigen Suche zu verwenden, können Sie auch eine Teilsuche im laufenden Betrieb durchführen.

Sie können UCS / A * weiterhin verwenden, aber die Suche beenden, nachdem die Inspektionsknoten Ninspiziert wurden, und nur den besten Pfad verwenden, der bisher gefunden wurde. Dieser Ansatz ist insofern hilfreich N, als Sie das Gleichgewicht zwischen Geschwindigkeit und Präzision finden können.

Eine andere Methode, die ich besonders mag, ist die Monte-Carlo-Baumsuche. Bei dieser Methode lässt du Pacman einen zufälligen Lauf von NBewegungen ausführen . Nach jedem zufälligen Spaziergang zeichnen Sie seinen ersten Zug und sein Endergebnis auf. Führen Sie Mzufällige Spaziergänge durch (oder machen Sie sie einfach so lange, bis Sie keine Zeit mehr haben oder was auch immer). Wählen Sie den ersten Zug mit dem besten Durchschnitt der zufälligen Spaziergänge.

Diese Teilsuchen haben einen schwerwiegenden Nachteil. Wenn die Suche mit UCS und Pacman in den ersten untersuchten NKnoten überhaupt nicht punktet , bleibt er stecken und da alle Bewegungen gleich schlecht sind.
A * würde dieses Problem nicht haben, solange die Heuristik darauf achtete, Pacman näher an nicht gefressene Pellets heranzuführen.
MCTS ist möglicherweise in der Lage, dieses Problem zu vermeiden, wenn der zufällige Gang voreingenommen ist, um sich in Richtung nicht gefressener Pellets zu bewegen, und der zufällige Gang nie vor der Wertung stoppt (dh der zufällige Gang geht weiter, wenn Pacman 0 Punkte hat.