Wie würde man eine KI für ein Sammelkartenspiel entwickeln [geschlossen]

7

Wie würde man eine KI für ein Sammelkartenspiel entwickeln (z. B. Magic The Gathering, YuGiOh usw.)?

Ich bin mir nicht sicher, wo ich überhaupt anfangen soll. Wie würden sich die KI-Schwierigkeiten "Leicht", "Normal" und "Schwer" unter der Haube unterscheiden?

Steve
quelle

Antworten:

5

Dies ist meine Erfahrung aus der Implementierung einer MTG-KI .

Wenn die KI von Anfang an nicht berücksichtigt wird, kann es schwierig sein, sie später hinzuzufügen.

Ihre Engine benötigt eine Möglichkeit, den Spielstatus zu kopieren. Es braucht auch eine Möglichkeit, eine Bewegung schnell rückgängig zu machen, damit der Suchbaum effizient generiert werden kann.

Jeder KI-Thread sollte mit einer eigenen Kopie des Spiels arbeiten.

Wenn der Computer eine Bewegung ausführt, simuliert er mögliche Ergebnisse des Spiels, indem er die Auswirkungen jeder möglichen Bewegung simuliert.

Der grundlegende Algorithmus ist:

Erstellen Sie eine Liste gültiger Züge (Zauber, Fähigkeiten, Pass ...). Führen Sie jeden Zug aus, um einen neuen Status zu generieren, und erstellen Sie dann eine neue Liste gültiger Züge. Wiederholen Sie diesen Vorgang, bis das Spiel endet oder bis Sie eine bestimmte Tiefe erreicht haben. Denken Sie daran, dass Sie das Spiel für beide Spieler simulieren.

Dieser Prozess generiert einen Baum. Jeder Pfad im Baum repräsentiert eine gültige Abfolge von Aktionen im Spiel. Weisen Sie jedem Blattknoten dieses Baums eine Punktzahl zu. Diese Punktzahl sollte ein Indikator dafür sein, welcher Spieler eine größere Chance hat, das Spiel zu gewinnen. Verwenden Sie den Minimax- Algorithmus, um diese Punktzahl an die Wurzel des Baums weiterzugeben.

Jeder Zug aus der ursprünglichen Liste hat jetzt eine Punktzahl. Wählen Sie den besten Zug aus.

Leider ist MTG ziemlich kompliziert und der grundlegende Algorithmus wird nicht sehr gut funktionieren ...

Dinge zu verbessern:

  • Manafähigkeiten (z. B. Landtippen) müssen unterschiedlich behandelt werden.
  • Deklarieren Sie nicht alle möglichen Kombinationen von Angreifern und Blockern, sondern verwenden Sie einige Heuristiken für den schnellen Kampf.
  • Zaubersprüche, für die Ziele erforderlich sind, beeinträchtigen die Leistung. Verwenden Sie Heuristiken, um nur "gute Ziele" auszuwählen. (Jede Karte, für die Ziele erforderlich sind, sollte einen Rangfolgenalgorithmus haben.)
  • Zuweisen von Zeitregeln zu jeder Karte, um zu begrenzen, wann KI in Betracht ziehen kann, sie zu spielen.
  • Wenn eine Karte X hat, sollte sie wissen, wie man einen guten X-Wert berechnet, und dies nur versuchen, wenn sie gespielt wird.
  • Wenn eine Karte wiederholt aktiviert werden kann, berechnen Sie mithilfe eines Algorithmus, wie oft und tun Sie dies als einen Zug.
  • Erzwingen Sie nur eine Option, wenn Sie Zaubersprüche mit mehreren spielen, basierend auf dem Spielstatus.

Hier ist eine Kartenimplementierung, die einige Heuristiken von oben verwendet:

public class LightningBolt : CardTemplateSource
{
    public override IEnumerable<CardTemplate> GetCards()
    {
      yield return Card
        .Named("Lightning Bolt")
        .ManaCost("{R}")
        .Type("Instant")
        .Text("Lightning Bolt deals 3 damage to target creature or player.")
        .Cast(p =>
          {
            p.Effect = () => new DealDamageToTargets(3);
            p.TargetSelector.AddEffect(trg => trg.Is.CreatureOrPlayer().On.Battlefield());
            p.TargetingRule(new EffectDealDamage(3));
            p.TimingRule(new TargetRemovalTimingRule(removalTag: EffectTag.DealDamage));
          });
    }
}
Gregor Slavec
quelle
Es wäre eine elegantere Lösung, wenn die KI nicht schummeln müsste, indem sie weiß, welche Karten der Spieler spielen kann und welche Karten in Zukunft gezogen werden.
Philipp
1
@Philipp. Ich habe vergessen, das zu erwähnen. Die KI betrügt nicht. Dies geschieht, indem die 'versteckten' Zauber nicht in die Liste der gültigen Züge aufgenommen werden. Karten in der gegnerischen Hand sind standardmäßig ausgeblendet, ebenso wie Karten in beiden Bibliotheken.
Gregor Slavec
Die Idee, "gutes Ziel" und eine ähnliche Hinweislogik in die Karten aufzunehmen, hat einen interessanten Nebeneffekt: Sie können dies in den Tutorial-Modi verwenden, um nützliche Züge für den Spieler hervorzuheben oder sinnvolle Standardeinstellungen auszuwählen (insbesondere, wenn die Tutorial-Decks darauf zugeschnitten sind Karten mit stark andeutbarem Verhalten). Indem Sie eine Instanz der KI im menschlichen Zug ausführen, können Sie die Vorteile mehrerer Karten auf diese Weise abwägen und eine Reihe von Aktionen vorschlagen, die gut zusammenarbeiten.
DMGregory
Dang, eine MTG-KI in C #, die sauber, gut organisiert und Open Source ist? Diese Antwort ist eine Goldmine unter den Antworten auf gamedev.se =)
Ken
wow, daran habe ich nicht gedacht; Der Automat kann in seiner eigenen Welt arbeiten und eine Reihe seiner möglichen Spiele spielen und entscheiden, welcher den größten Wert im Verhältnis zum subjektiven Wertesystem des Automaten erzeugt. Anstatt dass jeder Automat vorhersehbare perfekte Spiele basierend auf der Kenntnis des Decks des Gegners und einer statistischen Analyse jedes möglichen Szenarios im Metaspiel basierend auf der Popularität macht, kann er einfach seine eigene Strategie mit unterschiedlichem Maß an Rücksicht auf den Gegner oder das Metaspiel spielen , abhängig von der Persönlichkeit, die Sie für den Automaten wünschen.
Dmitry
4

1) Eine Werteheuristik . Sie benötigen eine Heuristik, mit der die KI bewerten kann, wie "gut" ein bestimmter Spielstatus ist. In MTG könnte beispielsweise eine sehr einfache Heuristik 2 Punkte für jede Karte, die Sie im Spiel haben, und 1 Punkt für jeden Lebenspunkt des Feindes zuweisen. Eines der Ziele der KI wäre es also, alle anderen Dinge gleich zu spielen so viele Karten wie möglich, aber es wäre auch bereit, jede Karte zu opfern, um dem Feind 2 oder mehr Schaden zuzufügen. Beachten Sie, dass diese Heuristik wahrscheinlich vom Deck im Spiel abhängt. Bei Mill-Decks müssen Sie beispielsweise die Deckgröße des Gegners als primäre Punktquelle einbeziehen.

2) Lookahead bewegen . Die Spielregeln beschreiben alle legalen Züge, die einem Spieler zur Verfügung stehen, einschließlich des Ziehens / Abwerfens / Platzierens / Aktivierens einer Karte. Jeder Zug kann anhand der Heuristik bewertet werden, die Sie in Schritt 1 erstellt haben. Dies liest jedoch nur einen Zug. Erfolgreichere Strategien sollten den nachfolgenden Zug des Gegners und den Zug der KI danach berücksichtigen und so weiter. Normalerweise verwenden Sie eine Minimax- Strategie.

  • Ein Schritt voraus: Bestimmen Sie für jeden Ihrer Züge den Wert des resultierenden Spielstatus und wählen Sie den mit den höchsten Punkten aus.
  • Zwei Schritte voraus. Bestimmen Sie für jeden Ihrer Züge und für jede Antwort Ihres Gegners den höchsten Punktwert, vorausgesetzt, Ihr Gegner wählt die optimale Antwort auf Ihren ersten Zug.
  • Drei Schritte voraus. Wählen Sie für [Ihren Zug, den Zug des Gegners, Ihren Zug erneut] erneut den besten Spielstatus aus und stellen Sie sicher, dass der Zug des Gegners für den Gegner optimal ist.

3) Weitere Optimierung Die naive Bewegungssuche nimmt exponentiell zu, je weiter Sie suchen. Mit einer Technik ähnlich der Alpha / Beta-Bereinigung bewerten Sie keine wirklich schlechten Pfade. Wenn Sie herausfinden können, dass ein Spielstatus streng von einem anderen Spielstatus dominiert wird, müssen Sie diesen Zweig des Bewegungsbaums nicht weiter nach unten schauen. Auch wenn die Heuristik einen allgemeinen "Orientierungssinn" vermittelt, ist das Ergebnis bestimmter Kartenkombinationen möglicherweise nicht ersichtlich. Insbesondere bei Verwendung von Themen-Decks können Sie eine Liste mit leistungsstarken Combos führen, insbesondere Gambits, die mehrere Schritte ausführen, bevor die Heuristik den Wert der Combo erkennt.

Jimmy
quelle
Move Lookahead ist in einer Umgebung, in der zu einem bestimmten Zeitpunkt einfach zu viele Moves verfügbar sind, von fragwürdiger Machbarkeit, sodass der Spielbaum schnell explodiert. Minimaxing macht zum Beispiel im Schach Sinn, aber in einem Spiel wie Go macht es so gut wie nichts, und ich kann mir vorstellen, dass es in TCGs noch schlimmer wäre. Ich denke, ein planungsbasierter Ansatz wäre besser.
Steven Stadnicki
Der Minmax-Algorithmus funktioniert nicht gut in einem Spiel, in dem die KI nicht weiß, welche Bewegungen der andere Spieler ausführen kann. In einem TCG ist dies normalerweise nicht der Fall, da die KI die Hand des Spielers nicht sieht und nicht weiß, welche Karten der Spieler und er selbst ziehen werden. Es sei denn natürlich, Sie lassen die KI betrügen.
Philipp
3

Magie: Die Versammlungsduelle der Planeswalker haben eine KI, die mögliche zukünftige Spielzustände simuliert. Unterschiedliche KI-Schwierigkeiten können unterschiedlich lange dauern, um Vorabdrehungen zu planen. Zusätzlich werden die Decks einfacher KI-Gegner so sortiert, dass seltenere Karten eher am unteren Rand des Decks erscheinen.

Hier ist ein ausführlicher Artikel mit Bildern (!):

http://www.wizards.com/Magic/Magazine/Article.aspx?x=mtg/daily/feature/44

Jim
quelle
1

Nun, Sie müssen verschiedene Dinge tun:

  1. Die KI muss Regeln für das Spiel kennen.
  2. Als nächstes muss die KI eine Strategie kennen, da diese Kartenspiele im Allgemeinen mehrere Abschnitte und / oder mögliche Kartentypen haben. Beispiel: Magie, Angriff, Monster, Fähigkeiten, Waffen und so weiter ...
  3. Für die eigentliche Schwierigkeit; Die KI sollte nur ein besserer Stratege sein, also könnte ein möglicher Vorausschau-Algorithmus, beispielsweise eine einfache KI, einen Angriff vorausplanen, aber keine Falle, während eine harte KI mehr Arten von Möglichkeiten und mehrere Tiefen des Denkens einplanen soll.
  4. Die KI sollte in der Lage sein, Techniken zu kombinieren und die allgemeine Strategie für ein effektives Spiel zu kennen.

Das sind die Grundlagen. Natürlich kann es variieren, wie das Spiel selbst ist.

Rivasa
quelle
Wie übersetzt sich das in Code? Besonders Nr. 1
Steve
Hmm, wenn @Steve neu in der Programmierung ist, benötigt er möglicherweise eine weniger abstrakte Antwort mit mehr Beispielen. Ich werde versuchen, es später aufzuschreiben, aber ich habe jetzt Arbeit zu erledigen.
JCora
@Steve, in welcher Sprache hast du das vor?
Rivasa
1
@TheEliteNoob Die Frage "@TheEliteNoob Actionscript 3.0" wurde von einem anonymen Benutzer bearbeitet. Ich gehe also davon aus, dass diese Frage beantwortet wurde. Ich denke, Steve hat seine Informationen verloren. Ich weiß es nicht.
MichaelHouse