Analyse d'une version modifiée du jeu de cartes «War»

Un jeu simple habituellement joué par des enfants, le jeu de guerre est joué par deux personnes en utilisant un jeu standard de 52 cartes à jouer. Initialement, le jeu est mélangé et toutes les cartes sont distribuées entre les deux joueurs, de sorte que chacun a 26 cartes aléatoires dans un ordre aléatoire. Nous supposerons que les joueurs sont autorisés à examiner (mais pas à modifier) ​​les deux decks, afin que chaque joueur connaisse les cartes et les ordres de cartes dans les deux decks. Ceci est généralement fait dans la pratique, mais ne changerait rien à la façon dont le jeu est joué, et aide à garder cette version de la question complètement déterministe.

Ensuite, les joueurs révèlent les cartes les plus hautes de leurs decks respectifs. Le joueur qui révèle la plus grande carte (selon l'ordre habituel: 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King, Ace) remporte la manche en plaçant d'abord sa carte (la carte haute) au bas de son deck, puis la carte de son adversaire (la carte basse) au bas du deck (généralement, l'ordre n'est pas appliqué, mais pour garder la première version de cette question déterministe, telle une commande sera exécutée).

En cas d'égalité, chaque joueur révèle quatre cartes supplémentaires du haut de son deck. Si la quatrième carte montrée par un joueur est plus élevée que la quatrième carte montrée par un autre joueur, le joueur avec la quatrième carte la plus élevée gagne toutes les cartes jouées pendant le bris d'égalité, auquel cas les cartes du gagnant sont d'abord placées au bas de la deck du gagnant (dans le premier entré, premier sorti; en d'autres termes, les anciennes cartes sont placées en premier en bas), suivies des cartes du perdant (dans le même ordre).

En cas d'égalité subséquente, le processus est répété jusqu'à ce qu'un gagnant de l'égalité soit déterminé. Si un joueur n'a plus de cartes et ne peut pas continuer à briser l'égalité, le joueur qui a encore des cartes est déclaré vainqueur. Si les deux joueurs manquent de cartes pour jouer en même temps, le jeu est déclaré à égalité.

Les rounds sont joués jusqu'à ce qu'un joueur soit à court de cartes (c'est-à-dire qu'il n'y ait plus de cartes dans son deck), auquel cas le joueur qui a encore des cartes est déclaré vainqueur.

Comme le jeu a été décrit jusqu'à présent, ni compétence ni chance ne sont impliquées dans la détermination du résultat. Puisqu'il y a un nombre fini de permutations de 52 cartes, il existe un nombre fini de façons dont les decks peuvent être initialement traités, et il s'ensuit que (puisque la seule information d'état dans le jeu est l'état actuel des decks des deux joueurs ) le résultat de chaque configuration de jeu peut être décidé a priori. Certes, c'est peut-être pour gagner le jeu de Guerre, et du même coup, pour le perdre. Nous laissons également ouverte la possibilité qu'un jeu de guerre puisse entraîner une égalité ou une boucle infinie; pour la version complètement déterministe décrite ci-dessus, tel peut être le cas ou non.

Plusieurs variantes du jeu qui tentent de le rendre plus intéressant (et non, toutes n'impliquent pas d'en faire un jeu à boire). Une façon à laquelle j'ai pensé pour rendre le jeu plus intéressant est de permettre aux joueurs de déclarer des "atouts" automatiques à certains tours. À chaque tour, l'un ou l'autre des joueurs (ou les deux) peut déclarer "atout". Si un joueur déclare «atout», ce joueur gagne la manche quelles que soient les cartes jouées. Si les deux joueurs déclarent "atout", alors le tour est traité comme une égalité et le jeu continue en conséquence.

On peut imaginer une variété de règles limitant la capacité des joueurs à l'emporter (l'atout illimité entraînerait toujours un match nul, comme les joueurs l'emporteraient à chaque tour). Je propose deux versions (juste au-dessus de ma tête; des versions plus intéressantes dans ce sens sont probablement possibles) de War basées sur cette idée mais en utilisant différents mécanismes de limitation des atouts:

1. $k$
2. $k$

Maintenant, pour les questions, qui s'appliquent à chacune des versions décrites ci-dessus:

1. Existe-t-il une stratégie telle que, pour un ensemble de configurations de jeu initiales possibles, le joueur l'utilisant gagne toujours (stratégie fortement gagnante)? Si oui, quelle est cette stratégie? Sinon, pourquoi pas?
2. Existe-t-il une stratégie telle que, pour un ensemble de configurations de jeu initiales possibles, le joueur l'utilisant peut toujours gagner ou forcer une égalité (stratégie gagnante)? Si oui, quelle est cette stratégie? Sinon, pourquoi pas?
3. $S$$S'$

Pour être clair, je pense à une "stratégie" comme un algorithme fixe qui détermine à quel tour le joueur utilisant la stratégie doit l'emporter. Par exemple, l'algorithme «l'emporte quand vous le pouvez» est une stratégie et un algorithme (un algorithme heuristique). Une autre façon de demander ce que je demande est la suivante:

Existe-t-il une bonne heuristique (ou une optimisation prouvée) pour jouer à ces jeux?

$k$$k=0$

Si je comprends bien, toutes les informations sur le jeu sont disponibles pour les deux joueurs. Autrement dit, la configuration de départ et tous les mouvements possibles sont connus des deux joueurs (principalement parce que les deux joueurs peuvent regarder les cartes de l'autre joueur). Cela fait du jeu un jeu à somme nulle d'informations parfaites. Il existe donc une stratégie parfaite à la disposition des deux joueurs qui permettrait d'obtenir le meilleur résultat dans chaque jeu pour ce joueur. Cela a été prouvé en 1912 par le mathématicien allemand Ernst Zermelo.

Je ne sais pas quelle est la stratégie, mais on pourrait imaginer construire un grand arbre de jeu pour cela et obtenir un ordinateur pour trouver la stratégie pour moi en utilisant l' algorithme min-max .

L'arbre de chaque partie aurait comme racine les mains des deux joueurs. Les branches de l'arbre correspondent aux mouvements des joueurs. Dans le cas le plus simple, celles-ci consistent simplement à déposer les cartes requises. Dans les cas les plus avancés, le mouvement «atout» peut être fait. Les nœuds internes de l'arborescence enregistrent la configuration actuelle des cartes ainsi que toute information sur l'état par rapport aux atouts. Les feuilles de l'arbre correspondent aux positions de fin de partie, qui seront étiquetées avec, par exemple, +1 pour une victoire au joueur 1, 0 pour une égalité et -1 pour une victoire au joueur 2. Ignorez les jeux en boucle pour l'instant.

Maintenant, l'algorithme min-max fonctionnera comme suit (du point de vue du joueur 1). Supposons qu'il regarde un nœud où le joueur 1 fait un mouvement et que les nœuds ci-dessous soient annotés avec +1, 0 ou -1 (le gain) ainsi que les choix que le joueur doit faire pour obtenir le résultat donné. Le joueur 1 sélectionne simplement le nœud avec le plus gros gain, enregistre ce gain et le choix requis pour l'obtenir. Pour le nœud où le joueur 2 effectue le déplacement, le nœud avec le gain minimum est choisi et le choix est enregistré. Cela reflète le fait que le joueur 2 vise le score le plus bas pour gagner. Ceci est propagé à l'arbre. Les choix enregistrés à chaque nœud correspondent correspondent à la meilleure stratégie qu'un joueur peut faire. Le gain final détermine qui gagne. C'est finalement une fonction en termes de gain, bien que le choix exact des mouvements puisse varier.

Des configurations potentiellement en boucle peuvent être incorporées dans l'arborescence de jeu en ajoutant simplement des boucles qui reviennent à une configuration déjà vue (lors du calcul à partir du haut). Pour de tels nœuds, vous prenez le plus grand point fixe s'il s'agit d'un nœud où le joueur 1 joue et le moins fixe lorsque le joueur 2 joue.

Notez que si vous n'aviez pas fait l'hypothèse que les deux joueurs pouvaient examiner les deux decks, cette approche ne s'appliquerait pas. Le jeu impliquerait alors le hasard et la stratégie choisie serait spécifique au jeu.

Qu'il y ait ou non une stratégie de gain forte ou faible pour l'un des joueurs dépend du résultat de l'algorithme min-max appliqué à tous les arbres. Mais il y en a certainement beaucoup ... Le calcul de l'arbre pour un est probablement assez facile, car il n'y a pas beaucoup de choix à faire dans le jeu.