Solution au jeu de société Avalon

Question

Question : Si les joueurs peuvent discuter de leur stratégie avant de jouer à Avalon, le jeu a-t-il une solution optimale ?

La stratégie peut être aussi alambiquée que vous le souhaitez. Je veux juste savoir si en principe il s'agit d'un jeu "résolu".

Les règles du jeu sont assez simples et, à titre de référence, les détails concernant le nombre de joueurs bons et mauvais et les tours peuvent être consultés ici : https://en.wikipedia.org/wiki/The_Resistance_(jeu)

S'il y a des joueurs G bons et E mauvais, à la fin de la partie, l'équipe mauvaise peut toujours deviner Merlin au hasard pour gagner. Une solution optimale sera donc définie comme suit :

• pour l'équipe des bons, une stratégie dans laquelle (quel que soit le choix de l'équipe des méchants) ils peuvent garantir la réussite d'au moins 3 missions et l'équipe des méchants ne peut pas faire mieux que 1/G de chance de choisir Merlin
• pour l'équipe mauvaise, une stratégie qui (indépendamment de ce que l'équipe bonne choisit de faire) maximise ses chances de gagner le jeu, avec une chance supérieure à la solution triviale consistant à deviner avec une chance 1/G

Pour autant que je sache, les règles ne sont pas tout à fait claires sur la communication que les joueurs peuvent faire (à part l'interdiction de montrer directement leurs cartes de personnage), pour les besoins de cette question, considérez la règle suivante sur la communication (si vous jouez par courrier électronique, cela équivaudrait à chaque message doit être envoyé à tous) :

• On ne peut pas compter sur la transmission de notes "sous la table", l'envoi de SMS, etc. Toutes les déclarations faites par un joueur doivent être publiques, dans le sens où chaque joueur dispose du message brut (même si tous les joueurs n'ont pas suffisamment de contexte pour en déduire la même signification - par exemple, une personne maléfique déclarant qu'elle est Merlin ne prête jamais à confusion pour un personnage maléfique puisque les personnages maléfiques se connaissent tous, mais peut induire en erreur un personnage gentil). Seul le message brut doit être public, la connaissance asymétrique des intentions obtenues à partir d'un message est acceptable).

J'ai le sentiment qu'en dépit de l'impossibilité de croire qu'un personnage en particulier dit la vérité, il pourrait y avoir une solution en faveur des bons personnages qui tirerait parti de l'asymétrie inhérente au personnage de Merlin et du fait qu'il y a toujours plus de bons que de méchants.

Quelqu'un a-t-il une solution ?

Answer 1

Bien qu'il ne soit pas possible de croire qu'un personnage en particulier dit la vérité, dans certaines circonstances, il semble y avoir une solution en faveur des bons personnages qui tire parti de l'asymétrie inhérente au personnage de Merlin et du fait qu'il y a toujours plus de bons que de méchants.

Voici une tentative de solution mathématique pour le bien de l'équipe.

Cela suppose que Merlin connaisse tous les personnages maléfiques. Cela ne fonctionnera donc pas si le personnage de Mordred est inclus (un personnage maléfique dont Merlin ne connaît pas l'existence). Si d'autres caractères spéciaux sont utilisés, cela ne devrait rien changer. Il s'agit également d'un travail en cours dans la mesure où cette stratégie donne pas mal d'informations supplémentaires à "l'équipe des bons", mais il peut y avoir encore quelques détails qui doivent être réglés. (Par exemple, quelqu'un m'a déjà fait remarquer qu'il fallait faire attention à bien remplir les messages ou que la seule connaissance de la longueur suffisait pour savoir qui était Merlin avec cette stratégie).

---

Après avoir distribué les cartes de caractère, une bonne personne suggère :

1. la stratégie suivante permet au bien de gagner, de sorte que le fait de s'écarter de ces règles indique que vous êtes mauvais
2. le premier chef de mission sera désormais appelé "joueur n° 0".
3. les joueurs à partir du numéro 0, dans le sens des aiguilles d'une montre, sont numérotés en conséquence
4. chaque joueur (i) propose une phrase secrète : phrase_i
5. à partir de là, chaque joueur (i) génère un numéro secret pour l'autre joueur (j) sous la forme secret_ij = HASH( phrase_i + string(j) )
6. utiliser ces nombres secret_ij avec l'échange de clés publiques pour générer une clé cryptographique entre chaque joueur : Clé_ij = Clé_ji = résultat de l'échange de clé publique entre les joueurs (i) et (j)

Après cette mise en place, le bon joueur propose ce qui suit :

7. Tour de table spécial : tous les joueurs donnent ouvertement/publiquement des messages cryptés aux autres joueurs indiquant l'un des points suivants :

   7a) se déclarer comme n'étant pas un Merlin

   7b) se déclarer merlin, déclarer que tout est bon, et donner sa phrase_i pour que toutes les clés et donc les messages de lui puissent être lus par cette personne.

8. Merlin devrait déclarer "merlin" à tous les gentils, et "non-merlin" à tous les méchants. Les serviteurs loyaux normaux devraient simplement déclarer "not-merlin" à tout le monde.

9. si un bon joueur reçoit un message dérogeant à cette règle, il peut immédiatement libérer la clé correspondante utilisée pour cette communication afin d'éliminer la personne malveillante. Les méchants doivent donc effectivement se faire passer pour des gentils normaux ou des merlins.

10. Plus généralement, une bonne personne devrait immédiatement démasquer tout faux merlin (divulguer sa phrase secrète) si elle peut prouver qu'il s'agit d'un faux sans donner d'informations sur merlin.

    Par exemple, si un faux Merlin prétend qu'une autre personne prétendant être Merlin est bonne, il se présente comme un faux, car le vrai Merlin ne ferait jamais cela. Malheureusement, une personne bonne peut avoir besoin de garder cela pour elle, car le révéler pourrait révéler des informations sur Merlin. Cependant, si plusieurs merlins choisissent des groupes tels qu'il n'y a aucun moyen cohérent pour l'un d'entre eux d'être réel (par exemple, deux merlins se déclarant mutuellement bons, ou trois merlins se déclarant tels qu'ils forment un cycle), alors le groupe entier est faux et doit être démasqué.

11. Maintenant, un tour de table en texte clair (pas de cryptage). Chaque joueur indique quels groupes de gentils lui ont été déclarés par des personnes déclarant être Merlin. (Note : seuls les groupes sont divulgués, pas la personne qui a déclaré le groupe).

12. S'il existe un groupe déclaré tel que tous les membres du groupe ne déclarent pas qu'on leur a dit qu'ils faisaient partie du groupe, alors ce groupe est clairement faux (car il n'a aucune raison de s'écarter du plan).

    Puisque le nombre de bons > le nombre de mauvais, tout groupe avec le nombre correct de personnes comprendra nécessairement au moins un bon. Cela signifie que le mal ne peut pas utilement induire en erreur.

13. S'il existe un joueur qui apparaît dans tous les ensembles de bons joueurs proposés, il doit être bon. Tous les bons joueurs doivent lui communiquer toutes les phrases secrètes qu'ils connaissent. De manière encore plus restrictive qu'auparavant, ce joueur peut alors dévoiler de faux merlins dont les sélections de groupe s'incluent les unes les autres de manière révélatrice.

14. S'il y a suffisamment d'informations pour que tout le monde soit capable de déduire une bonne équipe garantie sans révéler merlin, quelqu'un peut simplement l'expliquer. Les bons, ayant une supériorité numérique, peuvent maintenant s'assurer que le bon groupe est envoyé à chaque fois.

15. S'il n'y a pas assez d'informations pour que tout le monde puisse déterminer le bien ou le mal, le chef de mission choisit une équipe qui éliminera le plus grand nombre possible de "bons groupes" proposés. Si Merlin était le chef de mission, il pourrait délibérément choisir un groupe correct ou incorrect, de sorte qu'aucune information sur Merlin ne soit perdue. Si la mission n'élimine pas un "bon groupe" possible, et que la personne insiste quand même sur cette équipe de mission ou demande un vote avant la discussion, elle se présente comme maléfique et les bons peuvent voter contre l'équipe de mission. (Notez que cela n'indique pas si l'équipe proposée est bonne ou mauvaise). Le mal doit donc jouer le jeu pour essayer de réduire le nombre de membres de l'équipe.

16. Si la mission échoue, elle devrait, de par sa conception, éliminer au moins un, sinon plusieurs, des "bons groupes" proposés. Si la mission réussit, elle ne fournit aucune information. Passez au suivant.

J'ai peut-être raté quelque chose, mais je ne crois pas que l'équipe maléfique obtienne des informations sur Merlin grâce à cette stratégie. Je ne sais pas non plus comment le prouver, mais il me semble qu'il y a suffisamment d'informations pour que la victoire soit toujours au rendez-vous.

Notez d'abord que si à chaque fois qu'une mission échoue, au moins un "bon groupe" possible est éliminé, il doit y avoir au moins 3 faux merlins pour que l'équipe maléfique ait une chance de s'en sortir. Le seul problème potentiel est donc dans la version 7-10 joueurs.

Deuxièmement, il convient de noter que l'intersection de tous les ensembles proposés comme bons doit être effectivement bonne.

Troisièmement, si l'intersection entre deux ensembles proposés ne comporte qu'une seule personne, cette personne doit être bonne.

Ceci, ajouté aux informations précédentes et à d'autres déductions simples, est assez restrictif.

---

Pour un exemple concret, considérons le jeu à sept personnes : 3 mauvais, 4 bons.

Les trois personnages maléfiques doivent réussir à se faire passer pour Merlin pour avoir une chance. Donc si nous pouvons en éliminer un par déduction, le bien gagne.

Si aucun faux merlin n'inclut un membre maléfique supplémentaire dans le groupe proposé, alors il y a E+1 personnes qui n'ont été incluses que dans un seul groupe. Le complément de ce groupe doit être bon.

Si tous les faux merlins incluent un membre maléfique supplémentaire dans le groupe proposé, il y aura un cycle de faux merlins prétendant que d'autres faux merlins sont bons, et donc s'éliminant les uns les autres.

Ainsi, au moins un faux merlin doit inclure des bons membres G-1 dans le groupe proposé. Ainsi, si un groupe proposé n'a pas d'intersection de taille G-1 avec au moins un autre groupe, il peut être écarté. (Ce qui ramène le nombre de groupes à 2, permettant ainsi aux bons de gagner).

Pour une partie à sept joueurs, il y a trois missions nécessitant <= G-1 personnes. Donc, si aucun groupe proposé ne peut être éliminé uniquement par déduction, il faut toujours choisir pour la mission l'intersection d'au moins deux groupes. Si le mal échoue dans sa mission, il élimine plus d'un groupe et le bien l'emporte à nouveau.

Answer 2

Il semble que tout ce que les méchants ont à faire est : tous les joueurs méchants conspirent pour savoir qui ils pensent que Merlin est (cela peut être une supposition aléatoire), et ils font chacun semblant d'être Merlin et éliminent les autres espions et déclarent que le vrai Merlin est également un espion.

S'ils ont raison de deviner Merlin au hasard, les autres joueurs n'obtiennent aucune nouvelle information et Merlin semble indiscernable des autres joueurs. Le jeu se poursuit normalement, les espions sachant qu'ils ont eu raison de deviner Merlin et que l'assassin gagnera donc la partie pour eux.

Si, comme c'est plus probable, ils se trompent, les espions sont facilement démasqués, les missions sont brèves et évidentes, et l'assassin a déjà éliminé une cible possible pour Merlin, et a une chance légèrement meilleure de la choisir.

Le fait est que l'on est encore loin d'une "bonne" victoire garantie.