Demande de suggestion optimale Cluedo

Question

J'écris un algorithme pour demander la suggestion la plus optimale (meurtrier, arme, lieu). J'aimerais connaître votre avis sur cette méthode, les améliorations possibles ou les limites.

Par ordre d'importance :

1. N'utilisez jamais une carte dont vous savez déjà qu'un autre joueur la possède : Vous ne gagnerez aucune information.

2. N'utilisez jamais une carte qu'un autre joueur sait que je possède : Ce joueur pourrait potentiellement tirer autant d'informations de ma suggestion que moi-même.

Par exemple, je possède la dague, et le joueur B le sait. De plus, il possède la cuisine, et je ne le sais pas. Je suggère alors que c'était Plum, avec la dague, dans la cuisine ; lorsque quelqu'un réfute mon accusation, le joueur B sait que l'autre joueur a dû me montrer Plum.

3. Utiliser mes propres cartes une seule fois au maximum pendant toute la partie : Le but de l'utilisation d'une de vos cartes est de suggérer que quelqu'un d'autre l'a, ou qu'il s'agit d'une des cartes de l'enveloppe. Si je répète une de mes cartes, cela se produira :

J'utilise ma carte n° 1 : la personne qui me réfute a maintenant la carte n° 1 (selon tous les autres joueurs). Mais ensuite, j'utilise à nouveau la carte n° 1 et ce même joueur n'est plus en mesure de réfuter ma proposition. (Tous les autres joueurs savent maintenant qu'il ne l'avait pas ; cela leur donne une information supplémentaire que soit je l'ai, soit elle est dans l'enveloppe).

4. N'utilisez jamais une carte dont vous savez qu'elle se trouve dans l'enveloppe : Cela ne fait que donner aux autres joueurs des informations sur les autres personnes qui n'ont pas cette carte.

5. Si vous avez utilisé toutes vos cartes une fois, faites des suggestions sur 3 cartes inconnues.

Answer 1

Vous essayez d'écrire un ensemble de règles compréhensibles par l'homme pour un problème qu'une machine peut résoudre bien mieux. Ce que vous avez conçu est un ensemble d'heuristiques pour ce qui est fondamentalement un problème de statistiques. Si vous voulez atteindre une véritable optimalité, je vous recommande de recommencer entièrement.

Il y a 9 pièces, 6 joueurs et 6 armes. Cela signifie qu'il n'y a que 324 suppositions valides différentes (9 * 6 * 6) en général, et si vous limitez cet algorithme à une supposition en fonction de la pièce dans laquelle vous vous trouvez, vous n'avez que 36 options. Si ces chiffres sont trop importants pour qu'un humain puisse les évaluer en temps réel, ils sont négligeables pour un ordinateur. Ce que vous voulez écrire, c'est un ensemble de critères de notation pour chacune de ces combinaisons de cartes, et ensuite choisir la combinaison de cartes qui a le score le plus élevé pour deviner (en brisant les égalités au hasard).

Pour pouvoir continuer à parler d'optimisation, nous devons être rigoureux sur ce mécanisme de notation. D'après votre tentative de départ, il semble qu'il y ait deux choses qui vous intéressent :

1. Obtenir le maximum d'informations que vous ne connaissez pas encore.

2. Révéler aux autres joueurs le moins d'informations possible que vous connaissez déjà.

Il va être assez compliqué de traiter ces deux points, aussi concentrons-nous d'abord sur le point 1 (car c'est le plus important des deux).

Pour obtenir des informations, votre algorithme doit avoir en entrée tout ce que vous savez déjà sur l'endroit où se trouvent les cartes. C'est-à-dire :

• Combien de cartes possède chaque joueur

• Les cartes dont vous connaissez l'emplacement (y compris vos propres cartes)

• Quelles cartes vous savez que certains joueurs ne détiennent pas

Vous construisez ensuite un modèle de probabilité de l'emplacement de chaque carte (y compris le milieu). Les cartes dont vous connaissez l'emplacement auront une probabilité de 100% associée à cet emplacement. Ensuite, pour une estimation arbitraire, vous modélisez ce que les joueurs feront avec cette estimation, à savoir vous montrer une carte ou passer au joueur suivant. À cette fin, vous voudrez probablement supposer le pire des cas, à savoir que si un joueur détient une carte correspondant à votre estimation et dont vous connaissez déjà l'emplacement, c'est cette carte qui vous sera montrée. Avec tout cela, vous pouvez déterminer la probabilité que l'on vous montre une nouvelle carte par rapport à celle que l'on vous montre sans rien vous montrer. Vous devez ajouter un peu de logique pour déterminer ce que vous apprenez si la carte vous est retournée sans que personne ne vous montre quoi que ce soit.

Mais au bout du compte, vous avez une probabilité d'apprendre de nouvelles informations avec une estimation donnée. À ce stade, vous pourriez ajouter une pondération pour les différents types de cartes (je pense que les chambres sont des éléments d'information plus précieux parce que vous devez vous rendre dans la chambre pour la deviner), mais ce n'est pas nécessaire. Comparez cette probabilité pour chaque proposition et choisissez celle qui a le plus de chances de vous apprendre quelque chose de nouveau.

Avec un tel algorithme, vous pourriez même l'exécuter sur les 324 combinaisons de cartes, examiner les 10 suppositions les plus valables et, à partir de là, déterminer la pièce la plus valable à visiter ensuite (ou peut-être même ajouter une pondération pour la distance entre les pièces).

À ce stade, vous pouvez maintenant essayer de vous attaquer à la deuxième partie : donner le moins d'informations possible. Ce que vous voulez probablement faire, c'est soustraire un certain montant du score de chaque proposition en fonction de la quantité d'informations qu'elle révèle, mais cela se complique assez vite car pour le faire de manière optimale, il faut modéliser tout ce que les autres joueurs savent. Vous pourriez simplement ajouter un poids négatif à toute proposition qui révélerait une carte que vous savez être dans l'enveloppe, mais ce serait une chose délicate à calibrer, et à ce stade, nous sommes de retour dans le domaine de l'heuristique plutôt que de pouvoir parler d'une proposition "optimale". Je vous recommande de ne pas inclure cet élément dans votre premier essai de cet algorithme.

Answer 2

Votre algorithme actuel est défectueux car il ne tient pas compte.. :

A. la difficulté de déplacer les pièces, le nombre de passages nécessaires pour déplacer les pièces.

B. le fait qu'il y ait plus de pièces à éliminer que d'armes ou de meurtriers.

C. Il ne suggère pas quand vous devrait utiliser vos propres cartes dans votre suggestion, juste quand vous ne devriez pas

D. Votre règle n°2 ne tient pas compte d'un adversaire qui a une mémoire suffisante (ou qui conserve suffisamment de traces) - ce n'est pas parce qu'un autre joueur ne sait pas que vous avez la carte maintenant qu'il ne peut pas revenir en arrière lorsque vous lui montrez la carte plus tard. Vous pourriez utiliser ceci pour résoudre mon problème C, et dire que vous ne devriez jamais utiliser vos propres cartes. Mais bien sûr, si vous ne montrez jamais la carte, cela n'a aucune importance. Vous devez donc tenir compte de la probabilité de montrer une carte plus tard.

---

À titre d'exemple pour mon problème A, disons que vous commencez avec une distance égale à deux pièces - l'une dont vous avez la carte et l'autre non. Avec votre algorithme actuel, il n'y a pas de priorité entre les deux. Mais il est évident que vous obtenez plus d'informations en allant dans la pièce que vous n'avez pas. Disons maintenant que la pièce que vous n'avez pas est 2 cases plus loin, mais que le dernier lancer de dés vous permet d'aller dans l'une ou l'autre - est-il acceptable d'aller dans la pièce que vous n'avez pas, ou cela va-t-il éveiller les soupçons ? Cette suspicion en vaut-elle la peine de toute façon ? Et si la distance supplémentaire vous fait passer un tour de plus ? Est-ce que cela devient trop suspect ?

Pour mon problème B, il peut s'avérer préférable d'éliminer les pièces et de ne pas se soucier d'éliminer les armes/personnes. Il pourrait être possible d'éliminer les armes/personnes en analysant les suppositions des autres et les réponses qu'ils obtiennent. Cela peut donc vous amener à proposer vos propres cartes pour les armes et les personnes afin d'éliminer les pièces. Mais si on vous montre une carte et qu'à votre tour suivant vous quittez la pièce, c'est un signal assez fort pour tous les autres joueurs que la carte qu'on vous a montrée était la pièce.

Mais disons que vous utilisez vos propres cartes pour l'arme et la personne, et que personne ne peut vous aider pour la pièce ; vous connaissez maintenant la pièce. Avant votre prochain tour, vous êtes entraîné dans une autre pièce, une pièce pour laquelle vous avez la carte, et vous êtes obligé de montrer cette carte à la personne dont c'est le tour. Selon la règle n°2 de votre algorithme, vous DEVEZ changer de salle avant de faire une suggestion. Cela va a) vous faire perdre du temps dans le déplacement des salles, b) vous amener à vous déplacer dans une salle où les gens vous montreront la carte de salle ou c) rendre évident que la salle d'où vous avez été déplacé était importante lorsque vous essayez d'y retourner. En fait, vous avez fait le plus difficile (trouver la salle dans l'enveloppe) ; votre meilleure ligne de conduite est de rester dans la salle pour laquelle vous avez la carte, et de forcer les autres joueurs à vous montrer leurs cartes d'armes/personnes.

Un autre exemple où votre algorithme tombe à l'eau est lorsque vous avez la carte qui prouve votre propre innocence. Si vous accusez constamment la même personne, cela signifie que personne ne vous montre la carte de cette personne, ce qui veut dire que soit vous l'avez, soit elle est dans l'enveloppe. Les joueurs qui ne savent pas que vous l'avez vont donc accuser cette personne pour vérifier si vous l'avez ou si elle est dans l'enveloppe. Si cette personne est vous, vous pouvez vous déplacer librement dans de nombreuses pièces différentes ! Mais cela peut être une bénédiction ou une malédiction : s'il vous déplace dans une pièce que vous avez déjà éliminée, cela peut vous faire perdre un temps précieux.

---

En résumé, votre algorithme est trop simpliste. Si vous ignorez les salles et ne l'appliquez qu'aux armes et aux personnes, il est assez bon.