Eine Bomberman KI intelligent platzieren

13

Ich versuche, einen AI-Algorithmus für Bomberman zu implementieren. Derzeit habe ich eine funktionierende, aber nicht sehr clevere rudimentäre Implementierung (die derzeitige KI ist beim Platzieren von Bomben übereifrig).

Dies ist die erste KI, die ich jemals versucht habe, umzusetzen, und ich stecke ein bisschen fest. Die ausgefeilteren Algorithmen, die ich im Auge habe (die ich für bessere Entscheidungen erwarte), sind zu kompliziert, um gute Lösungen zu sein.

Welche allgemeinen Tipps haben Sie für die Implementierung einer Bomberman-KI? Gibt es radikal unterschiedliche Ansätze, um den Bot entweder defensiver oder offensiver zu machen?


Bearbeiten: Aktueller Algorithmus

Mein aktueller Algorithmus sieht ungefähr so ​​aus (Pseudocode):

1) Versuche eine Bombe zu platzieren und finde dann eine Zelle, die vor allen Bomben sicher ist, einschließlich der, die du gerade platziert hast. Um diese Zelle zu finden, durchlaufen Sie die vier Richtungen. Wenn Sie eine sichere divergierende Zelle finden und rechtzeitig erreichen können (z. B. wenn die Richtung nach oben oder unten zeigt, suchen Sie nach einer Zelle, die sich links oder rechts von diesem Pfad befindet), können Sie sicher eine Bombe platzieren und sich bewegen in diese Richtung.

2) Wenn Sie divergierende Zellen nicht finden und retten können, versuchen Sie, KEINE Bombe zu platzieren und suchen Sie erneut. Dieses Mal müssen Sie nur in einer Richtung nach einer sicheren Zelle suchen (Sie müssen nicht davon abweichen).

3) Wenn Sie immer noch keine sichere Zelle finden, tun Sie nichts.

for $(direction) in (up, down, left, right):
    place bomb at current location
    if (can find and reach divergent safe cell in current $(direction)):
        bomb = true
        move = $(direction)
        return

for $(direction) in (up, down, left, right):
    do not place bomb at current location
    if (any safe cell in the current $(direction)):
        bomb = false
        move = $(direction)
        return

else:
    bomb = false
    move = stay_put

Dieser Algorithmus macht den Bot sehr triggerglücklich (er wird sehr häufig Bomben platzieren). Es tötet sich nicht selbst, aber es hat die Angewohnheit, sich verwundbar zu machen, indem es in Sackgassen gerät, in denen es von den anderen Spielern geblockt und getötet werden kann.

Haben Sie Vorschläge, wie ich diesen Algorithmus verbessern könnte? Oder sollte ich mal was ganz anderes probieren?

Eines der Probleme mit diesem Algorithmus besteht darin, dass es dazu neigt, dem Bot sehr wenige (häufig nur eine) sichere Zellen zu hinterlassen, auf denen er stehen kann. Dies liegt daran, dass der Bot eine Spur von Bomben hinterlässt, solange er sich nicht selbst tötet.

Wenn Sie jedoch eine Spur von Bomben zurücklassen, bleiben nur wenige Orte übrig, an denen Sie sich verstecken können. Wenn einer der anderen Spieler oder Bots beschließt, irgendwo in Ihrer Nähe eine Bombe zu platzieren, kann es vorkommen, dass Sie keinen Platz zum Verstecken haben und sterben.

Ich brauche eine bessere Möglichkeit, um zu entscheiden, wann ich Bomben platzieren soll.

Paul Manta
quelle
Es ist schwer, sich etwas vorzustellen, das zu 100% aus heiterem Himmel funktioniert. Aber wenn Sie den Algorithmus, den Sie derzeit haben, hinzufügen, können wir alle dazu beitragen, ihn schrittweise zu verbessern. Sie sind wahrscheinlich auch nicht der erste Bastler, der versucht, eine Bomberman-KI zu implementieren, und ich habe einige Bomberman-KI-Wettbewerbe mit einer zufälligen Google-Suche gefunden, die sich als unschätzbare Informationsquelle für Sie erweisen könnten.
Roy T.
Ich denke, Sie können die Bomberman-KI auf zwei Arten verallgemeinern: 1) Sie wollen sich davor schützen, von Bomben anderer Spieler gesprengt zu werden / gefangen von deinen eigenen Bomben).
Tigrou
Es wäre wahrscheinlich besser, wenn Sie zumindest einen umfassenden Überblick über Ihre aktuelle Implementierung veröffentlichen würden (vorausgesetzt, es handelt sich um viel Code), und wir könnten Ihnen möglicherweise dabei helfen, das Problem zu lösen, dass sie beim Platzieren von Bomben übereifrig sind.
Tetrad
@ Tetrad Ich bin gerade dabei, einen neuen Algorithmus zu implementieren. Ich werde sehen, wie das geht und den Algorithmus hier bei Bedarf posten.
Paul Manta
es ist zwar kein echter tipp aber du kannst dir den clanbomber code ansehen . Es ist ein Spiel in vielerlei Hinsicht ähnlich wie Bomberman.
Ali1S232

Antworten:

4

Das Problem, mit dem Sie konfrontiert sind, ist, dass Ihre KI nie aufhört, eine intelligente Entscheidung darüber zu treffen, wo sie ihre nächste Bombe platzieren soll. Dadurch wirft sie nur Bomben ab, wann immer es geht, und arbeitet dann "Scheiße, Scheiße, was mache ich jetzt! ? "

Pause zum Nachdenken

Im Moment wandert Ihre KI nur ins Nirgendwo. Manchmal sollte es sich jedoch tatsächlich um ein Ziel handeln. Wenn es zum Beispiel ein Powerup sieht und denkt, dass es es erreichen kann, bevor der Spieler es erreicht, sollte es vielleicht einen sicheren Weg zu diesem Plättchen finden und sich dorthin bewegen, nach Bomben Ausschau halten und sie auf dem Weg meiden.

Das gleiche Verhalten beim Bewegen zum Ziel kann angewendet werden, wenn überlegt wird, wo die nächste Bombe platziert werden soll .

Wenn Ihre KI eine Bombe platzieren kann, anstatt dies sofort zu tun, sollte sie kurz einen Suchalgorithmus verwenden , um aus den verfügbaren Bombenplatzierungspunkten zu wählen, basierend auf Kriterien wie:

  • Ist es in der Nähe? (damit es nicht jedes Mal, wenn es eine Bombe platzieren will, in die diagonale gegenüberliegende Ecke der Karte geht)
  • Gibt es einen Ort, an dem ich mich vor der Explosion verstecken kann - und den ich erreichen kann, bevor die Bombe explodiert?
  • Sprengt die Explosion Kacheln und gibt mir Powerups?
  • Wird es den Spieler möglicherweise angreifen? (Eine einfachere KI könnte dies im frühen Spiel vermeiden, eine aggressive KI wird dies verfolgen - ohne die Powerups zu vergessen.)

Nachdem diese Entscheidung getroffen wurde, hat die KI einen Ort für die Bombenplatzierung und einen Ort ausgewählt, an dem sie sich vor ihrer Explosion verstecken kann. Es kann jetzt zur Stelle gehen, seine Bombe platzieren und dann zu seinem Versteck gehen. Sobald es sein Versteck erreicht hat, möchte es möglicherweise weitergehen und Bombenstandorte finden (wenn es mehrere Bomben hat), vorausgesetzt, es wird daran gedacht, sich aus dem Weg der Bombe zu halten, die es hier gegangen ist, um zu vermeiden.

Zu Fuß und auf der Suche nach einem sicheren Weg

Sie können für Ihre KI eine einzelne Punkt-zu-Punkt-Methode entwickeln und diese jedes Mal anwenden, wenn Sie möchten, dass sie irgendwohin läuft. Diese Methode könnte den Suchalgorithmus A * verwenden , um den Pfad zu finden.

Um die KI zu schützen, möchten Sie sie möglicherweise veranlassen, ihren Pfad jedes Mal zu überprüfen, wenn eine neue Bombe platziert wird. Um Explosionen zu vermeiden, könnte die Zeit bis zum Explodieren der Bombe überprüft werden und ein potenzielles Explosionsplättchen in Betracht gezogen werden, über das man sicher gehen kann, wenn die Bombe nicht explodiert, während sie durch das Plättchen läuft - und wenn es nicht sicher ist, behandeln Sie es als unpassierbares Plättchen .

Um Ihre KI-Fehler zu vermeiden (so dass sie manchmal tatsächlich in die Luft gejagt werden können), sollten Berechnungsfehler auftreten: Unachtsames Vergessen einer Bombe, Unterschätzung der Explosionsgröße oder der Zeit bis zur Explosion der Bombe usw.

Randnotiz: Sie können das zufällige Gehen auch zielgerichteter erscheinen lassen, indem Sie nach dem Zufallsprinzip Punkte auswählen, zu denen Sie gehen möchten, oder immer einen neuen Bombenplatz im Auge behalten, anstatt nur nach dem Zufallsprinzip ein benachbartes Plättchen auszuwählen, zu dem Sie wandern möchten. Auf diese Weise wandert es nicht an derselben Stelle hin und her, als könne es sich nicht entscheiden.

doppelgreener
quelle
Ich habe vergessen, einige relevante Details zum Spiel anzugeben. Es ist eine vereinfachte Version von Bomberman: Keine Power-Ups, Spieler können immer unbegrenzt Bomben platzieren und Bomben haben immer die maximale Reichweite (von einem Ende der Karte zum anderen). Das Punktesystem ist auch anders ... [Fortsetzung]
Paul Manta
[Forts.] Sie erhalten 1 Punkt für das Platzieren einer Bombe, aber 0 Punkte für das Zerstören einer Mauer. Sie erhalten außerdem 30 Punkte für einen Kill, 15 für eine Assistenz und -20 für einen Selbstmord. [Fortsetzung]
Paul Manta
[Forts.] In diesem Sinne sollte die KI versuchen, so oft wie möglich eine Bombe zu platzieren (weil das Platzieren von Bomben Bomben ergibt), aber es muss nicht besonders vorsichtig sein, wo die Bombe platziert wird. Es muss darauf geachtet werden, immer einen sicheren Platz zu haben. [Fortsetzung]
Paul Manta
[Fort.] Glauben Sie, dass , wenn eine Richtung der Wahl, es ist genug für mich derjenige, der führt zu einem sicheren zu holen Bereich . Anstatt nach einer sicheren Zelle zu suchen, würde ich nach dem größten sicheren Bereich Ausschau halten, damit ich mich auch vor Bomben anderer Spieler verstecken kann, nicht nur vor meinen eigenen. Wäre es auch eine gute Idee, Richtungen zu bevorzugen, die mich einem der anderen Spieler näher bringen?
Paul Manta
3
Na dann reden wir ja gar nicht über Bomberman und seine KI! Wir haben gerade ein Spiel mit Bomben, das Bomberman oberflächlich ähnelt, aber unter der Haube völlig anders ist und Sie dazu ermutigt, ein Trigger Happy Lunatic zu sein , und ich habe viel weniger Erfahrung mit diesem Spiel.
Doppelgreener