Apprenez-vous une astuce pour utiliser Python pour résoudre la fin de partie des propriétaires

Doudizhu devrait être familier à tout le monde. L'article suivant partage principalement avec vous les informations pertinentes sur l'utilisation de Python pour déchiffrer la phase finale de Doudizhu. L'article le présente de manière très détaillée et revêt une certaine importance pour tout le monde. . La valeur d'apprentissage de référence, les amis qui en ont besoin peuvent jeter un œil ci-dessous.

Avant-propos

Je crois que tout le monde a déjà joué à Landlords, donc je ne présenterai plus les règles.

Aller directement à la photo de fin de partie vue dans le cercle d'amis :

J'ai essayé cette question la première fois que je l'ai vue. essayez de le déchiffrer manuellement, et chaque fois que je pense avoir trouvé la stratégie gagnante du fermier, je finis par découvrir que le fermier ne peut pas s'échapper. Puisque le cracking manuel ne peut pas épuiser toutes les possibilités, nous ne pouvons utiliser que des codes pour nous aider à résoudre ce problème.

Cet article décrira brièvement comment résoudre de tels problèmes via le code. À la fin, le résultat final de la fin du jeu sera annoncé et le code sera open source pour que tout le monde puisse se plaindre.

minimax

L'idée centrale du code est minimax. Minimax peut être décomposé en deux parties, mini et max, qui signifient respectivement minimum et maximum.

Qu'est-ce que la compréhension intuitive ? C'est un peu comme si deux personnes A et B jouaient aux échecs. A peut maintenant déplacer les échecs à N points. Supposons que A déplace les échecs à un certain point, de sorte que le score d'évaluation du coup de A soit le plus élevé, mais lorsque c'est au tour de B de jouer, il se déplacera certainement dans la direction qui est la suivante. le plus défavorable à A. Go, de sorte que la prochaine étape de A doit suivre la trajectoire fixée par B et ne peut pas atteindre le score le plus élevé que A a estimé à cette étape dans la première étape.

Il en est de même dans le jeu de cartes. Si la main de cartes du fermier ne peut pas être gagnée par le propriétaire, quelle que soit la façon dont il la gère, alors on peut dire que le fermier a une stratégie gagnante ; , l'agriculteur perdra.

Logique de base

Nous pouvons utiliser une fonctionhand_out pour simuler le processus de jeu de cartes d'une personne. Dans la vraie vie, si une personne veut jouer aux cartes, elle doit connaître toutes les cartes de sa main : me_pokers, et elle doit également connaître les cartes jouées lors de la main précédente : last_hand. Si nous voulons utiliser cette fonction pour simuler le jeu à deux, nous avons également besoin de connaître toutes les cartes actuelles de l'adversaire : Enemy_pokers.

La valeur de retour de cette fonction est de savoir si je peux gagner la carte quand c'est mon tour pour moi_pokers de jouer. Renvoie vrai s'il peut gagner, faux sinon.

def hand_out(me_pokers, enemy_pokers, last_hand)

Supposons que lorsque ce soit mon tour de jouer aux cartes, si toutes les cartes de ma main sont jouées, alors je saurai immédiatement que j'ai gagné sinon ; , si les cartes de l'adversaire Tout est fait, mais je ne l'ai pas fait, alors j'ai échoué.

if not me_pokers:
 return True
if not enemy_pokers:
 return False

Comme c'est mon tour de jouer aux cartes maintenant, je dois d'abord connaître toutes les combinaisons de mains que je peux jouer maintenant. Remarque : Cette combinaison inclut la stratégie de vérification (c'est-à-dire de ne pas jouer).

all_hands = get_all_hands(me_pokers)

Maintenant, nous voulons parcourir toutes les combinaisons de mains possibles.

Tout d'abord, j'ai besoin de savoir quelle carte l'adversaire a joué lors de la dernière main.

• Si l'adversaire a choisi de checker lors de la main précédente, ou n'avait pas la main précédente, alors je ne dois pas checker lors de ce tour, mais je peux jouer n'importe quelle carte

• Si mon adversaire a joué une carte lors de la main précédente, je dois jouer une carte plus grosse que celle-ci ou choisir de checker directement (sans jouer de carte) dans ce tour
  

Voici le point clé. Après avoir joué mes cartes ou choisi de passer, nous devons utiliser un appel récursif pour simuler le prochain comportement de l'adversaire. Si le prochain jeu de cartes de l'adversaire ne peut pas gagner, alors mon jeu de cartes cette fois gagnera certainement, sinon, pour chaque choix de jeu de cartes que je fais, si l'adversaire peut gagner, alors je perdrai ;

L'ensemble du code est le suivant :

def hand_out(me_pokers, enemy_pokers, last_hand, cache):
 if not me_pokers:
  # 我全部过牌，直接获胜
  return True
 if not enemy_pokers:
  # 对手全部过牌，我失败
  return False
 # 获取我当前可以出的所有手牌组合，包括过牌
 all_hands = get_all_hands(me_pokers)
 # 遍历我的所有出牌组合，进行模拟出牌
 for hand in all_hands:
  # 如果上一轮对手出了牌，则这一轮我必须要出比对手更大的牌 或者 对手上一轮选择过牌，那么我只需出任意牌，但是不能过牌
  if (last_hand and can_comb2_beat_comb1(last_hand, hand)) or (not last_hand and hand['type'] != COMB_TYPE.PASS):
   # 模拟对手出牌，如果对手不能取胜，则我必胜
   if not hand_out(enemy_pokers, make_hand(me_pokers, hand), hand, cache):
    return True
  # 如果上一轮对手出了牌，但我这一轮选择过牌
  elif last_hand and hand['type'] == COMB_TYPE.PASS:
   # 模拟对手出牌，如果对手不能取胜，则我必胜
   if not hand_out(enemy_pokers, me_pokers, None, cache):
    return True
 # 如果之前的所有出牌组合均不能必胜，则我必败
 return False

Construction

La logique de base ci-dessus Une fois que vous avez compris cela, construire un cracker devient très simple.

Tout d'abord, nous devons utiliser des nombres pour représenter la taille des cartes. Ici, nous utilisons 3 pour représenter 3, 11 pour représenter J, 12 pour représenter Q, et ainsi de suite...

Deuxièmement, nous devons découvrir Toutes les combinaisons de cartes dans une main nécessitent la fonction get_all_hands La mise en œuvre spécifique est compliquée mais très simple, je n'entrerai donc pas dans les détails ici.

Ensuite, nous avons également besoin d'une fonction de jugement de la force de la carte can_comb2_beat_comb1(comb1, comb2) Cette fonction est utilisée pour comparer la force de la carte des deux groupes de mains pour voir si comb2 peut vaincre comb1. La seule chose à laquelle vous devez faire attention est que dans les règles de Landlord, à l'exception des bombes, toutes les autres cartes ont la même force. Seules les cartes du même type peuvent être comparées.

Enfin, nous avons besoin d'une fonction de jeu de cartes simulé make_hand(pokers, hand) , qui permet de connaître les mains restantes après avoir joué une main avec des pokers en main. La mise en œuvre est également très simple, il suffit de retirer simplement les cartes qui se trouvent. ont été joués.

Efficacité

En raison du grand nombre de mains possibles dans un jeu de cartes, le nombre de branches récursives est énorme. Par conséquent, la surcharge temporelle est très importante, ce qui correspond au niveau factoriel O(N !). Selon la formule de Stirling, elle est d'environ O(N^N).

Comme il peut y avoir de nombreuses cartes en double, cela entraîne de nombreux appels récursifs répétés. Ainsi, l’ajout d’un cache peut grandement améliorer l’efficacité.

est la description de notre main, de la main de l'ennemi et de la main du tour précédent （str(me_pokers)+str(enemy_pokers)+str(last_hand)） est la clé, et le résultat est stocké dans le dictionnaire cache. La prochaine fois que vous rencontrerez la même situation, vous pourrez la récupérer directement depuis le dictionnaire de cache sans avoir à répéter le calcul. La complexité temporelle est optimisée en exponentielle O(C^N).

Résultat

Le résultat du calcul du code est que les agriculteurs n'ont pas de stratégie gagnante. En d’autres termes, tant que les propriétaires savent jouer, les agriculteurs ne peuvent pas gagner. La solidification de la classe est-elle déjà comme ça...

Open source

Le code est placé sur Github : doudizhu_solver, ou vous pouvez le télécharger localement, sous licence MIT , et jouez comme vous le souhaitez.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!