Beste Techniken für eine KI eines Kartenspiels

27

Ich versuche, eine KI für ein Kartenspiel zu entwickeln und bin ein bisschen über die Technik / den Algorithmus, den ich verwenden sollte, festgefahren. Hier einige Annahmen zum Spiel:

  • Nachdem die Karten an die Spieler verteilt wurden, gibt es keine Zufälligkeit mehr. Ich meine hier, dass jeder Spieler wählen kann, welche Karten er spielt, aber es findet kein zufälliger Prozess statt, wie beim Verteilen der Karten zu Beginn des Spiels.
  • Es gibt eine Einschränkung bezüglich der Karten, die gespielt werden können, wenn eine Karte bereits gespielt wurde.
  • Der Spieler, der den Stich gewinnt, spielt dann zuerst. ZB Spieler 1 spielt eine Karte, Spieler 2 spielt eine Karte und gewinnt. Dann spielt Spieler 2 eine Karte und dann spielt Spieler 1.

Ich kenne viele Hinweise / Regeln (zB wenn ich weiß, dass der Spieler die Karten A, B, C hat, sollte ich D spielen), die mir helfen, das Spiel zu gewinnen. Daher wollte ich zuerst ein Bayes'sches Netzwerk verwenden, um diese Regeln zu beschreiben. Das Problem ist, dass ich keine zuzuweisenden Wahrscheinlichkeiten kenne, aber ich könnte eine Heuristik unter Verwendung der Geschichte der gespielten Spiele (gegen einen Menschen) berechnen. Zweitens ist es sehr wahrscheinlich, dass ich nicht alle Regeln kenne und dass es einige implizite Regeln gibt, die von der KI benötigt werden, um das optimale Spiel zu finden.

Ich bin mir nicht sicher, ob dies eine gute Möglichkeit wäre, eine KI für ein solches Kartenspiel zu entwickeln.

Ich frage mich auch, ob es andere Techniken gibt, die am besten zu dem Problem passen. Ich habe mir beispielsweise Minimax angesehen (möglicherweise mit einem Beschneidungsalgorithmus), wäre aber eine gute Option für dieses Problem? Ich bin mir ziemlich unsicher, da die wichtigsten Spiele zu Beginn des Spiels sind, wenn es die höchsten unbekannten Parameter gibt (die meisten Karten sind noch nicht gespielt).

LaurentG
quelle
1
Gute Frage! Ich habe keine vollständige Antwort. Ich möchte nur mein 2c hinzufügen: Wenn Sie alle möglichen Zustände kennen, in denen sich Ihr Spiel befinden kann, wäre Minimax theoretisch ein guter Weg, um diesen Spielzustandsbaum zu durchlaufen. Könnte in Leistungsprobleme geraten, wenn das Spiel besagt, dass der Baum zu groß ist ...
Shivan Dragon
1
Was ist das Ziel des Spiels? Wer gewinnt? Könnte es einem Spieler möglich sein, seine / ihre Gewinnchancen zu einem bestimmten Zeitpunkt abzuschätzen?
KOMMEN SIE VOM
Ich kann das Spiel nicht im Detail erklären. Um zu gewinnen, muss man die höchste Punktzahl erreichen (mehr als der andere Spieler). Am Anfang ist es schwer / unmöglich zu sagen, ob wir gewinnen werden. Am Ende können wir sicher sein, dass wir gewinnen, wenn einer bereits genug Punkte hat (der andere Spieler kann nicht mehr genug Punkte gewinnen, um zu gewinnen).
LaurentG
1
Ist das Spiel HeartStone? :)
Lescai Ionel
1
Es sieht so aus, als ob ich mich in einer sehr ähnlichen Situation wie Sie befinde, auch in einem Kartenspiel, auch in einem lokalen (allerdings nicht in der Schweiz), und ich versuche auch zu verstehen, wo ich anfange. Eine Sache, die ich interessant fand, ist ein Evolver, bei dem Sie virtuellen Spielern DNAs zuweisen und sie dann gegeneinander antreten lassen. Sie töten die Verlierer und Sie züchten die Gewinner. Das Ergebnis könnten recht anständige KI-Bots sein. Ich habe nicht herausgefunden, wie ich diesen tropiceuro.com/puerto-rico-evolver für mein Kartenspiel anpasse , aber ich denke, dass dies möglich ist.
Andrew Savinykh

Antworten:

11

Ihr Beispiel klingt ähnlich wie Bridge . Top Bridge-Systeme verwenden Monte-Carlo-Methoden , um Züge auszuwählen. Auf hohem Niveau:

  • Bestimmen Sie die Wahrscheinlichkeiten, mit denen sich jede Karte auf einer bestimmten Hand befindet. Sie wissen mit Sicherheit, welche Karten sich in Ihrer Hand befinden und welche Karten gespielt wurden. Bestimmen Sie die Wahrscheinlichkeit aller anderen Karten basierend auf den gespielten Karten und möglicherweise dem Gebot eines Spielers, wenn es sich um ein Gebot handelt. Zu Beginn könnten Sie einfach eine naive und gleiche Wahrscheinlichkeit verwenden, dass sich eine Karte in der Hand eines Spielers befindet.
  • Führen Sie nun so viele "virtuelle" Spiele durch, wie Sie können. Simulieren Sie das Ausspielen einer Karte aus Ihrer Hand und bestimmen Sie dann die Reaktionen Ihrer Gegner anhand der Spielregeln und Ihrer Wahrscheinlichkeiten. Verwenden Sie für jedes virtuelle Spiel Ihre Wahrscheinlichkeiten, um einem Spieler Karten zuzuweisen und das Spiel dann schnell zu simulieren. Angenommen, jeder Spieler wird nach besten Kräften spielen. Sie kennen alle Karten in Ihrem virtuellen Spiel, sodass jeder Spieler perfekt spielen kann.
  • Wenn Sie eine solide Stichprobe haben (oder Ihnen die Zeit ausgeht), wählen Sie den legalen Schritt, der Ihnen am häufigsten das beste Ergebnis gebracht hat.

Sobald Sie etwas zum Laufen gebracht haben, können Sie alle möglichen erweiterten Strategien hinzufügen. Variieren Sie beispielsweise Ihre Wahrscheinlichkeiten basierend auf den historischen Spielen eines Spielers, variieren Sie die Wahrscheinlichkeiten basierend auf dem Stil eines Spielers (passiv, vorsichtig, aggressiv) oder berücksichtigen Sie sogar die Auswirkungen bestimmter Spieler, die zusammen spielen.


Bearbeiten Sie den Kommentar von LaurentG:

Letztendlich möchten Sie vielleicht die Idee des perfekten Spiels für alle Spieler aufgeben und etwas Realistischeres ersetzen. Trennen Sie konzeptionell die Wahrscheinlichkeiten für eine Karte auf der Hand einer anderen Person (Kartenverteilung) von der Wahrscheinlichkeit, dass ein Spieler während einer Hand eine bestimmte legale Karte spielt (Kartenauswahl).

Die Kartenauswahl ist reif zum Lernen. Wenn Sie Spiele über Spiele hinweg verfolgen, können Sie lernen, wie ein bestimmter Spieler oder Spieler im Allgemeinen dazu neigen, basierend auf den Karten in ihrer Hand und den Karten, die gespielt wurden, zu spielen. Sie könnten sich sogar etwas einfallen lassen und ihre Annahmen über Karten modellieren, die vor ihnen versteckt sind.

Es gibt auch Lernmöglichkeiten für die Kartenverteilung. Die vergangenen Gebote und die Kartenauswahl eines Spielers während einer Hand können ein "Tell" darüber anzeigen, was in ihrer Hand verborgen ist. Sie können historische Daten verwenden, um die Wahrscheinlichkeiten beim Erstellen der einzelnen virtuellen Spiele anzupassen.

Corbin March
quelle
Vielen Dank für Ihre interessante Antwort. Sie haben recht, das Spiel teilt einige Regeln mit Bridge. Soweit ich weiß, ist Ihre KI nicht besser als das, was Sie codiert haben. Gibt es eine Möglichkeit, eine Monte-Carlo-Methode anzuwenden und die KI zum Lernen zu bringen? Wäre es möglich, die Wahrscheinlichkeiten für jede Karte anhand der vergangenen Ereignisse (aller vorherigen Spiele) zuzuweisen?
LaurentG
Sie können die KI definitiv zum Lernen bringen. Der Trick wäre, die Wahrscheinlichkeiten für eine Karte in einer bestimmten Hand von der Wahrscheinlichkeit zu trennen, dass ein Spieler eine bestimmte legale Karte spielt, sobald sie auf der Hand ist. Ich werde oben näher darauf eingehen.
Corbin
6

Ein Fall aus jüngster persönlicher Erfahrung:

Ich habe selbst an einem Kartenspiel gearbeitet (Bisca, ein portugiesisches 2-Spieler-Spiel) und mit Monte-Carlo-Methoden gute Ergebnisse erzielt, insbesondere mit dem neueren Algorithmus für die Monte-Carlo-Baumsuche (ISMCTS, beschrieben mit) Beispielquellcode in Python unter http://www.aifactory.co.uk/newsletter/2013_01_reduce_burden.htm ).

Es spielt sich einigermaßen gut, mit dem gelegentlichen falschen Zug, nur mit der Kenntnis der Spielregeln. Ich versuche gerade, es zu untersuchen, um es verbessern zu können, da es nach den Informationen, die ich darüber (und übergeordnetes MCTS) gelesen habe, möglich ist, das Spiel mit Heuristiken zu verbessern ( http: // www .orangehelicopter.com / ed / papers / aiide13.pdf ) und Rückschluss auf die Gegnerkarte .

Schwarze Katze
quelle
1
Dieser Beitrag ist ziemlich schwer zu lesen (Textwand). Hätten Sie etwas dagegen bearbeiten sie in eine bessere Form ing?
gnat
Vielen Dank für die Antwort von jemandem mit echter Erfahrung zu dem Problem. tolle links!
Luben
3

Ich denke, das hängt von den Spielregeln ab.

Folgendes verstehe ich aus Ihrer Frage:

  • Das Spiel wird in Runden gespielt, wobei jeder Spieler eine Karte pro Runde spielt
  • Der Spieler, der zuerst geht, kann jede Karte spielen, die er will
  • Der Spieler, der Zweiter wird, kann nur bestimmte Karten spielen, je nachdem, was zuerst gespielt wurde
  • Der Spieler, der die Runde gewinnt, geht zuerst in die nächste Runde
  • Alle Karten werden vor der ersten Runde verteilt

Annahmen :

  • Mit vollständiger Kenntnis der Karten des anderen Spielers kann der Spieler, der zuerst geht, für jeden seiner Spieler entscheiden, ob eine Karte die Runde gewinnt oder nicht (der erste Spieler kann eine sichere Gewinnkarte spielen).
  • Wenn die Karten A und B beide gewinnen, wenn sie diese Runde zuerst gespielt werden, A diese Runde spielen (und gewinnen), dann bedeutet das Spielen von B in der folgenden Runde auch, dass B gewinnt (Karten verlieren nicht an Wert).
  • Bei voller Kenntnis der Karten des anderen Spielers kann der zweite Spieler entscheiden, ob eine Karte diese Runde gewinnen kann, würde aber verlieren, wenn er in der folgenden Runde als Erster spielt (wählte die schlechteste gewinnende Karte).

Beispielspiel nach folgenden Regeln:

Der erste Spieler spielt eine Karte. Der zweite Spieler muss eine Karte der gleichen Reihe spielen oder verlieren. Wenn die Suiten übereinstimmen, gewinnt die höchste Karte.

Dieses Spiel wird nun durch das Unentschieden entschieden und indem Sie sich merken können, welche Karten gespielt wurden, um die Hand Ihres Gegners zu kennen.
In dieser Situation würde ich die KI nur teilweise daran erinnern lassen, welche Karten gespielt wurden, dh einen gewissen Prozentsatz der gespielten Karten (niedrigere Zahl = höhere Schwierigkeitsstufe KI) aus der Liste entfernen, aber keine wichtigen wie Asse oder Könige. Auf diese Weise weiß die KI beispielsweise, dass es sicher ist, eine Herzdame zu spielen, da sie sich daran erinnert, dass der Gegner weder das Ass noch den König hat, sondern eine Wahrscheinlichkeit berechnen muss, wenn er dann die 10 spielen möchte. weil er sich vielleicht nicht erinnert, ob der Jack noch im Spiel ist.
Dies ahmt die menschliche Aufmerksamkeitsspanne nach.

TL; DR
Begrenze, wie viel die KI weiß, damit ihre Entscheidungen nicht perfekt sind, nur gut genug.

Cezar Moise
quelle
Danke für deine Antwort. Aber wie in der Frage gesagt, gibt es kein Glück / keine Zufälligkeit, nachdem die Karten verteilt wurden. Und ein Spieler kennt die Karten anderer Spieler nicht. Er muss unter Verwendung der bereits gespielten Karten und einiger "Regeln" Vermutungen anstellen.
LaurentG
2
Wie die Idee, auswendig gelernte Karten zufällig zu entfernen. Dies gibt einen Hinweis auf die Entwicklung von Levels wie leicht, mittel und schwer.
SuperM