IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Algorithme pour Mastermind


Sujet :

Algorithmes et structures de données

  1. #1
    Nouveau Candidat au Club
    Femme Profil pro
    Étudiant
    Inscrit en
    Juin 2021
    Messages
    1
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 23
    Localisation : France, Aveyron (Midi Pyrénées)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Enseignement

    Informations forums :
    Inscription : Juin 2021
    Messages : 1
    Points : 1
    Points
    1
    Par défaut Algorithme pour Mastermind
    bonjour à toutes et tous !

    nous avons développé un mastermind dans le cadre de nos études qui est fonctionnel. Nous aimerions ajouter une fonctionnalité : jouer contre l'ordinateur. Nous sommes confrontés à deux problèmes.

    Le premier est que notre mastermind est configurable. Il peut se jouer avec un nombre variable de pion (de 3 à 6) et de couleurs (de 3 à 8 également). Nous avons bien trouvé quelques algorithmes comme celui de Knuth que nous avons réussi à adapter pour 3 et 4 pions avec 6 couleurs. Nous avons trouvé un article qui décrit un algo que nous n'arrivons pas à écrire pour 4 pions et 7 couleurs.
    Il nous manque un algo général et configurable en nombre de pions et couleurs. Nous nous posions la question de savoir si vous pourriez nous aider.

    Le second est que les algos que nous avons codés sont imbattables. Comment peut-on créer un joueur artificiel avec un niveau ?

    En espérant avoir été claire, je vous remercie par avance de l'aide que vous pourrez nous apporter.

  2. #2
    Expert confirmé
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Mai 2002
    Messages
    3 410
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : Mai 2002
    Messages : 3 410
    Points : 5 801
    Points
    5 801
    Par défaut
    salut


    il est difficile de comprendre votre problématique

    en utilisant des tableau dynamique (variable) quelque soit le nombre
    le problème peut se résoudre de la même manière
    tu as donc un tableau de couleur
    un tableau de solution (1 ligne). ce n'est qu'un simple tableau dans lequel chaque indice contient une des couleur prédéfinie
    et une matrice de proposition ... celle-ci correspond a toutes les propositions déjà faites

    on test toujours la dernière ligne de la matrice avec la ligne de solution ...
    comme tu le vois je ne parle pas du nombre de pion ou du nombre de couleur ceux-ci sont déterminé par les tableaux

    pour créer un joueur artificiel il faut que tu détermine un seuil de réutilisation des coups passés
    je m'explique :
    imaginons un joueur de niveau 1 (niveau débutant)
    entre chaque proposition tu ne reprend que les valeur qui sont a la bonne place tu ne tient pas compte des valeurs mal placées
    le joueur de niveau 2 (niveau intermédiaire)
    entre chaque proposition tu ne reprend que les valeur qui sont a la bonne place
    tu ne tient compte des valeurs mal placées avec un pourcentage donnée par exemple 15% des pièces mal placé vont resservir a un endroit différent
    ou alors calculer la probabilité que la couleur de la case est inférieur a 50% de chance tu ne l'a met pas
    et pour l'expert tu met ton algos imbattables

    pour que l'on puisse t'aider il faut que l'on sache qu'elle est le choix et les algo que tu as realisé
    en 1 mots voir un debut de travail

    sinon oui on peut t'aider ici c'est fait pour cela ... mais nous ne faisons pas le travail a ta place
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  3. #3
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 038
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : Décembre 2013
    Messages : 4 038
    Points : 9 347
    Points
    9 347
    Par défaut
    Un algorithme simple, celui que je pratique quand je joue au MasterMind (jamais en fait, mais c'est secondaire) sans ordinateur, sans rien.

    On a par exemple 6 couleurs ABCDEF et 5 cases.
    Je joue AAAAA au 1er coup. Quelle que soit la réponse, je sais sans ambiguité combien il y a de A. Imaginons que la réponse soit 1 A
    Je joue ensuite ABBBB (je mets autant de A que ce que j'ai obtenu comme réponse à la 1ère question).
    Je peux donc en déduire sans ambiguité combien il y a de B. Et je connais aussi le nombre de pions bien placés. Imaginons que la réponse soit 2 pions de bonne couleur, dont 1 bien placé.
    Il y a donc 1 A et 1 B , et le A ne peut pas être en 1ère colonne, sinon j'aurais eu 2 pions bien placés.

    Au 3ème tour, je joue donc CABCC ... je sais qu'il y a un A et un B, et je vais donc savoir combien il y a de C ... et je vais avoir quelques infos de plus sur les emplacements des pions.

    Méthodiquement, je prends les couleurs dans l'ordre, et je place les A le plus à gauche possible, ppuis je complète par les B, le plus à gauche possible en respectant les infos reçues, etc...

    Etc etc ... ce n'est pas hyper efficace, mais contre tout humain normalement constitué, ça permet de gagner assez souvent.

    Une variante, c'est de jouer au 1er tour AAAAF ... et dans ce cas, on est amené à raisonner de façon 'probabiliste' : j'ai joué AAAAF, et on me dit que j'ai un pion, et qu'il est mal placé ... c'est probablement le pion F ; et si par hasard il s'avère que c'est un pion A, alors jackpot, je connais en plus son emplacement, il ne peut être qu'en dernière colonne.

    L'algorihme de Knuth batit une toile d'araignée, il peut éventuellement jouer au 3ème coup une proposition 'incompatible avec les 2 premières propositions', pour collecter des informations.
    Moi, je joue à chaque fois une proposition compatible avec les informations collectées. Et tant pis si les informations reçues sont hyper-redondantes.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

Discussions similaires

  1. algorithme pour arbre
    Par d-a-v-e dans le forum Algorithmes et structures de données
    Réponses: 6
    Dernier message: 06/02/2006, 22h16
  2. algorithme pour calcul de probabilité
    Par filsdugrand dans le forum Algorithmes et structures de données
    Réponses: 9
    Dernier message: 14/12/2005, 15h11
  3. Quel algorithme pour insertion d'objets "triés" da
    Par phplive dans le forum Langage
    Réponses: 3
    Dernier message: 04/08/2005, 10h27
  4. Algorithme pour trier trois nombres
    Par legosam dans le forum Algorithmes et structures de données
    Réponses: 9
    Dernier message: 17/01/2005, 22h47
  5. Algorithme pour chiffres significatifs en Assembleur
    Par lutin2003 dans le forum Assembleur
    Réponses: 5
    Dernier message: 09/09/2004, 11h47

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo