Geekly articles weekly

Ein Spiel (nicht) für Narren. Wir schreiben AI für "The Fool" (Teil 1)

Ich denke, es ist für niemanden ein Geheimnis, dass "Fool" (im Folgenden wird dieses Wort mit einem kleinen Buchstaben und ohne Anführungszeichen geschrieben) das beliebteste Kartenspiel in Russland und den Ländern der ehemaligen UdSSR ist (obwohl es außerhalb davon fast unbekannt ist). Trotz seines Namens und seiner recht einfachen Regeln hängt das Gewinnen immer noch mehr von den Fähigkeiten des Spielers als von der zufälligen Verteilung der Karten ab (in der englischen Terminologie werden Spiele beider Typen als Geschicklichkeitsspiel bzw. Glücksspiel bezeichnet. Also - ein Dummkopf mehr Geschicklichkeitsspiel ).


Der Zweck des Artikels ist es, eine einfache KI für das Spiel zu schreiben. Das Wort "einfach" bedeutet Folgendes:


  • ein intuitiver Entscheidungsalgorithmus (dh kein maschinelles Lernen, bei dem dieser Algorithmus tief "unter der Haube" verborgen ist);
  • Mangel an Status (das heißt, der Algorithmus wird nur von den Daten zum aktuellen Zeitpunkt geleitet, einfach ausgedrückt, er erinnert sich an nichts (zum Beispiel "zählt" er keine Karten, die das Spiel verlassen haben).

(Genau genommen gibt der erste Absatz einer solchen KI nicht mehr das Recht, als künstliche Intelligenz an sich bezeichnet zu werden , sondern nur noch eine Pseudo-KI. Diese Terminologie wurde jedoch in der Spieleentwicklung festgelegt, sodass wir sie nicht ändern.)


Ich denke, die Spielregeln sind allen bekannt, deshalb werde ich sie nicht noch einmal daran erinnern. Diejenigen, die überprüfen möchten, ich rate Ihnen, Wikipedia zu kontaktieren, es gibt einen ziemlich guten Artikel zu diesem Thema.


Also fangen wir an. Je älter die Karte ist, desto besser ist es für einen Narren, sie in der Hand zu haben. Daher bauen wir den Algorithmus auf der klassischen Bewertung der Stärke der Hand auf und treffen auf der Grundlage dieser Bewertung eine Entscheidung (z. B. eine bestimmte Karte zu werfen). Wir ordnen die Werte den Karten zum Beispiel folgendermaßen zu:


  • Ass (A) - +600 Punkte,
  • König (K) - +500,
  • Dame (Q) - +400,
  • Jack (J) - +300,
  • zehn (10) - +200,
  • neun (9) - +100,
  • acht (8) - 0,
  • sieben (7) - -100,
  • sechs (6) - -200,
  • fünf (5) - -300,
  • vier (4) - -400,
  • drei (3) - -500,
  • und schließlich Deuce (2) - -600 Punkte.

(Wir verwenden Zahlen, die ein Vielfaches von 100 sind, um Gleitkommawerte in unseren Berechnungen zu entfernen, und verwenden nur Ganzzahlen. Dazu benötigen wir negative Bewertungen, siehe unten im Artikel.)


Trumpfkarten sind wertvoller als einfache Karten (selbst ein Trumpf-Zweikampf schlägt ein „gewöhnliches“ Ass), und die Hierarchie in der Trumpf-Farbe ist dieselbe. Um sie zu bewerten, addieren Sie einfach 1300 zum „Basiswert“ - dann kostet der Trumpf-Zweikampf beispielsweise -600 + 1300 = 700 Punkte (das ist nur etwas mehr als eine nutzlose Trumpfkarte).


Im Code (alle Codebeispiele im Artikel befinden sich in Kotlin) sieht es relativaCardValue() Funktion relativaCardValue() gibt genau die Schätzung zurück und RANK_MULTIPLIER ist nur ein Koeffizient gleich 100):


 for (c in hand) { val r = c.rank val s = c.suit res += ((relativeCardValue(r.value)) * RANK_MULTIPLIER).toInt() if (s === trumpSuit) res += 13 * RANK_MULTIPLIER //   ,    }

Leider ist das nicht alles. Es ist auch wichtig, die folgenden Bewertungsregeln zu berücksichtigen:


  • Es ist vorteilhaft, viele Karten mit demselben Wert zu haben - nicht nur, weil sie den Gegner „ausfüllen“ können, sondern auch, um den Angriff leicht abzuwehren (insbesondere wenn die Karten einen hohen Wert haben). Zum Beispiel am Ende des Spiels eine Hand (der Einfachheit halber nehmen wir an, dass Trümpfe im Folgenden Tamburine sind)

    $$ Anzeige $$ \ Clubsuit 2 \ Spadesuit 2 \ Diamondsuit Q \ Herzensanzug Q \ Clubsuit Q \ Spadesuit Q $$ Anzeige $$ Fast perfekt (natürlich, wenn der Gegner nicht mit Königen oder Assen unter dich geht): Danach wirst du von den Damen geschlagen Rivalen hängen Gib ihm ein Paar Zweien.


    Aber viele Karten der gleichen Farbe (natürlich ohne Trumpf) haben im Gegenteil einen Nachteil - sie „stören“ sich gegenseitig. Zum Beispiel Hand

    $$ display $$ \ spadesuit 5 \ spadesuit J \ spadesuit A \ diamondsuit 6 \ diamondsuit 9 \ diamondsuit K $$ display $$ Sehr unglücklich - selbst wenn der Gegner Ihre Trumpfkarte beim ersten Zug nicht „ausschlägt“ und mit einer Karte der Spitzenfarbe geht, werden alle anderen geworfenen Karten andere Farben haben und müssen Trumpfkarten geben. Darüber hinaus besteht eine hohe Wahrscheinlichkeit, dass die fünf Anstürme nicht beansprucht werden - Sie haben alle Trumpfkarten mit einer Würde von mehr als fünf, sodass Sie sie unter keinen Umständen (es sei denn, Sie haben sie ursprünglich mit einer jüngeren Karte eingegeben) mit einer anderen Karte abdecken können - dies ist sehr wahrscheinlich hoch. Auf der anderen Seite ersetzen wir den Pik-Wagenheber durch zehn Schläger und den Trumpf sechs durch Dreifach:

    $$ Anzeige $$ \ Spadesuit 5 \ Clubsuit 10 \ Spadesuit A \ Diamondsuit 3 \ Diamondsuit 9 \ Diamondsuit K $$ Anzeige $$ Trotz der Tatsache, dass wir die Karten durch jüngere ersetzt haben, ist eine solche Hand viel besser - erstens müssen Sie keine Trumpfkarte auf die Farbe der Karten geben (und es ist wahrscheinlicher, dass Sie das Pik-Ass verwenden), und zweitens, wenn Sie eine schlagen Wenn Sie dann eine Karte mit Ihrem Trumpf drei haben, besteht die Möglichkeit, dass Ihnen jemand drei Pik wirft (weil es normalerweise keinen Sinn macht, eine solche Karte zu halten), und Sie werden die fünf "ergreifen".



    Um diese Strategien umzusetzen, modifizieren wir unseren Algorithmus: Hier betrachten wir die Anzahl der Karten jeder Farbe und den Vorteil ...


     /*          - ,      -     ,   ,    4    1.25 */ val bonuses = doubleArrayOf(0.0, 0.0, 0.5, 0.75, 1.25) var res = 0 val countsByRank = IntArray(13) val countsBySuit = IntArray(4) for (c in hand) { val r = c.rank val s = c.suit res += ((relativeCardValue(r.value)) * RANK_MULTIPLIER).toInt() if (s === trumpSuit) res += 13 * RANK_MULTIPLIER countsByRank[r.value - 1]++ countsBySuit[s.value]++ }

    ... hier fügen wir Boni für sie hinzu (der Aufruf von Math.max wird benötigt, um keine negativen Boni für niedrige Karten zu erhalten - weil dies in diesem Fall auch von Vorteil ist) ...


     for (i in 1..13) { res += (Math.max(relativeCardValue(i), 1.0) * bonuses[countsByRank[i - 1]]).toInt() }

    ... und hier wird im Gegenteil eine Geldstrafe für einen in Anzügen unausgeglichenen Anzug UNBALANCED_HAND_PENALTY (der Wert UNBALANCED_HAND_PENALTY experimentell auf 200 gesetzt):


     //      ... var avgSuit = 0.0 for (c in hand) { if (c.suit !== trumpSuit) avgSuit++ } avgSuit /= 3.0 for (s in Suit.values()) { if (s !== trumpSuit) { //              val dev = Math.abs((countsBySuit[s.value] - avgSuit) / avgSuit) res -= (UNBALANCED_HAND_PENALTY * dev).toInt() } }

    Schließlich berücksichtigen wir eine banale Sache wie die Anzahl der Karten in der Hand. Tatsächlich ist es sehr gut, zu Beginn des Spiels 12 gute Karten zu haben (zumal sie immer noch nicht mehr als 6 geworfen werden können), aber am Ende des Spiels, wenn es nur einen Gegner mit 2 Karten neben Ihnen gibt, ist dies überhaupt nicht der Fall.


     //       (      ) var cardsInPlay = cardsRemaining for (p in playerHands) cardsInPlay += p cardsInPlay -= hand.size // ,      ,     ( MANY_CARDS_PENALTY = 600) val cardRatio = if (cardsInPlay != 0) (hand.size / cardsInPlay).toDouble() else 10.0 res += ((0.25 - cardRatio) * MANY_CARDS_PENALTY).toInt() return res

    Wir fassen zusammen - vollständig sieht die Bewertungsfunktion folgendermaßen aus:


     private fun handValue(hand: ArrayList<Card>, trumpSuit: Suit, cardsRemaining: Int, playerHands: Array<Int>): Int { if (cardsRemaining == 0 && hand.size == 0) { return OUT_OF_PLAY } val bonuses = doubleArrayOf(0.0, 0.0, 0.5, 0.75, 1.25) // for cards of same rank var res = 0 val countsByRank = IntArray(13) val countsBySuit = IntArray(4) for (c in hand) { val r = c.rank val s = c.suit res += ((relativeCardValue(r.value)) * RANK_MULTIPLIER).toInt() if (s === trumpSuit) res += 13 * RANK_MULTIPLIER countsByRank[r.value - 1]++ countsBySuit[s.value]++ } for (i in 1..13) { res += (Math.max(relativeCardValue(i), 1.0) * bonuses[countsByRank[i - 1]]).toInt() } var avgSuit = 0.0 for (c in hand) { if (c.suit !== trumpSuit) avgSuit++ } avgSuit /= 3.0 for (s in Suit.values()) { if (s !== trumpSuit) { val dev = Math.abs((countsBySuit[s.value] - avgSuit) / avgSuit) res -= (UNBALANCED_HAND_PENALTY * dev).toInt() } } var cardsInPlay = cardsRemaining for (p in playerHands) cardsInPlay += p cardsInPlay -= hand.size val cardRatio = if (cardsInPlay != 0) (hand.size / cardsInPlay).toDouble() else 10.0 res += ((0.25 - cardRatio) * MANY_CARDS_PENALTY).toInt() return res }

    Wir haben also die Bewertungsfunktion bereit. Im nächsten Teil ist geplant, eine interessantere Aufgabe zu beschreiben - Entscheidungen auf der Grundlage einer solchen Bewertung zu treffen.


    Vielen Dank für Ihre Aufmerksamkeit!


    PS Dieser Code ist Teil der Anwendung, die der Autor in seiner Freizeit entwickelt hat. Es ist auf GitHub verfügbar (Binärversionen für Desktop und Android, für letztere ist die Anwendung auch auf F-Droid verfügbar).

Source: https://habr.com/ru/post/de437346/

More articles:


All Articles