Geekly articles weekly

Un jeu (pas) pour les imbéciles. Nous écrivons l'IA pour "The Fool" (partie 1)

Je pense que ce n'est un secret pour personne que "Fool" (ci-après ce mot sera écrit avec une petite lettre et sans guillemets) est le jeu de cartes le plus populaire en Russie et dans les pays de l'ex-URSS (bien qu'il soit presque inconnu en dehors). Malgré son nom et des règles assez simples, le gagner dépend encore plus de l'habileté du joueur que de la distribution aléatoire des cartes (dans la terminologie anglaise, les jeux des deux types sont respectivement appelés jeu d'adresse et jeu de hasard . Donc - un imbécile dans plus de jeu d'adresse ).


Le but de l'article est d'écrire une IA simple pour le jeu. Le mot "simple" signifie ce qui suit:


  • un algorithme intuitif de prise de décision (c'est-à-dire, par conséquent, pas d'apprentissage automatique dans lequel cet algorithme est caché profondément "sous le capot");
  • manque d'état (c'est-à-dire que l'algorithme n'est guidé que par les données du moment présent, simplement dit, il ne se souvient de rien (par exemple, il ne "compte" pas les cartes qui ont quitté le jeu).

(À strictement parler, le premier paragraphe ne donne plus le droit à une telle IA d'être appelée intelligence artificielle en soi , mais seulement une pseudo-IA. Mais cette terminologie a été établie dans le développement de jeux, nous ne la changerons donc pas.)


Je pense que les règles du jeu sont connues de tout le monde, je ne vais donc plus les rappeler. Ceux qui veulent vérifier, je vous conseille de contacter Wikipédia , il y a un assez bon article sur ce sujet.


Commençons donc. Évidemment, dans un imbécile, plus la carte est ancienne, mieux c'est de l'avoir en main. Par conséquent, nous allons construire l'algorithme sur l'évaluation classique de la force de la main et prendre une décision (par exemple, lancer une carte particulière) sur la base de cette évaluation. Nous attribuons les valeurs aux cartes, par exemple comme ceci:


  • as (A) - +600 points,
  • roi (K) - +500,
  • dame (Q) - +400,
  • Jack (J) - +300,
  • dix (10) - +200,
  • neuf (9) - +100,
  • huit (8) - 0,
  • sept (7) - -100,
  • six (6) - -200,
  • cinq (5) - -300,
  • quatre (4) - -400,
  • trois (3) - -500,
  • et enfin, diable (2) - -600 points.

(Nous utilisons des nombres qui sont des multiples de 100 afin de se débarrasser de la virgule flottante dans nos calculs et n'utilisons que des entiers. Pour cela, nous avons besoin de notes négatives, voir ci-dessous dans l'article.)


Les cartes Trump sont plus précieuses que toutes les cartes simples (même un dump atout bat un as «ordinaire»), et la hiérarchie dans le costume d'atout est la même, donc pour les évaluer, nous ajoutons simplement 1300 à la valeur «de base» - puis, par exemple, le dump trump «coûtera» -600 + 1300 = 700 points (c'est-à-dire un peu plus qu'un atout aceless).


Dans le code (tous les exemples de code de l'article seront dans Kotlin), cela ressemble à ceci (la fonction relativaCardValue() renvoie l'estimation même, et RANK_MULTIPLIER n'est qu'un coefficient égal à 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 //   ,    }

Hélas, ce n'est pas tout. Il est également important de considérer les règles d'évaluation suivantes:


  • il est avantageux d'avoir de nombreuses cartes de même valeur - non seulement parce qu'elles peuvent «remplir» l'adversaire, mais aussi repousser facilement l'attaque (surtout si les cartes sont de grande valeur). Par exemple, à la fin du jeu, une main (pour simplifier, nous supposons que les atouts ci-après sont des tambourins)

    $$ afficher $$ \ clubuit 2 \ combinaison pique 2 \ combinaison diamant Q \ combinaison coeur Q \ combinaison club Q \ combinaison pique Q $$ afficher $$ presque parfait (bien sûr, si l'adversaire ne passe pas sous vous avec des rois ou des as): vous serez battu par les dames, après quoi accrocher des rivaux donnez-lui une paire de deux.


    mais de nombreuses cartes de la même couleur (bien sûr, non-atout), au contraire, ont un inconvénient - elles «interfèrent» les unes avec les autres. Par exemple, la main

    $$ afficher $$ \ combinaison de plongée 5 \ combinaison de plongée J \ combinaison de combinaison A \ combinaison de diamants 6 \ combinaison de diamants 9 \ combinaison de diamants K $$ afficher $$ très malheureux - même si l'adversaire ne "frappe pas" votre atout avec le premier coup et va avec une carte de la couleur de pointe, alors toutes les autres cartes lancées seront d'autres couleurs, et ils devront donner des atouts. De plus, il y a une forte probabilité que les cinq rushs restent non réclamés - vous avez tous les atouts avec une dignité supérieure à cinq, donc en aucun cas (à moins, bien sûr, que vous n'ayez initialement entré avec une carte plus jeune), vous ne pourrez pas le couvrir avec une autre carte - il est très probable que cela prenne haut. D'un autre côté, nous remplaçons le cric de pique par dix massues, et l'atout six par triple:

    $$ afficher $$ \ combinaison de plongée 5 \ combinaison de club 10 \ combinaison de combinaison A \ combinaison de diamants 3 \ combinaison de diamants 9 \ combinaison de diamants K $$ afficher $$ Malgré le fait que nous ayons remplacé les cartes par des cartes inférieures, une telle main est bien meilleure - premièrement, vous n'aurez pas à jouer un atout (et vous pouvez plus probablement utiliser l'as de pique), et deuxièmement, si vous battez n'importe quelle puis une carte avec votre atout trois, il y a une chance que quelqu'un vous jette un trois de pique (car il n'y a généralement aucun sens à détenir une telle carte), et vous "saisirez" les cinq.



    Pour mettre en œuvre ces stratégies, nous modifions notre algorithme: ici nous considérons le nombre de cartes de chaque couleur et avantage ...


     /*          - ,      -     ,   ,    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]++ }

    ... ici, nous leur ajoutons des bonus (l'appel Math.max est nécessaire pour ne pas accumuler de bonus négatifs pour les cartes basses - car dans ce cas, il est également bénéfique) ...


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

    ... et ici, au contraire, nous allons bien pour une combinaison non équilibrée en combinaisons (la valeur UNBALANCED_HAND_PENALTY fixée expérimentalement à 200):


     //      ... 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() } }

    Enfin, nous prenons en compte une chose aussi banale que le nombre de cartes en main. En fait, avoir 12 bonnes cartes en début de partie est très bien (surtout qu'elles ne peuvent toujours pas être lancées plus de 6), mais en fin de partie, quand il n'y a qu'un adversaire avec 2 cartes à côté de vous, ce n'est pas du tout le cas.


     //       (      ) 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

    Nous résumons - dans son intégralité, la fonction d'évaluation ressemble à ceci:


     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 }

    Nous avons donc la fonction d'évaluation prête. Dans la partie suivante, il est prévu de décrire une tâche plus intéressante - prendre des décisions sur la base d'une telle évaluation.


    Merci à tous pour votre attention!


    PS Ce code fait partie de l'application développée par l'auteur pendant son temps libre. Il est disponible sur GitHub (versions binaires pour Desktop et Android, pour ce dernier l'application est également disponible sur F-Droid ).

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

More articles:


All Articles