Partage
  • Partager sur Facebook
  • Partager sur Twitter

Méthode pour jouer au MasterMind

    14 novembre 2021 à 22:06:40

    Bonjour,

    Vous connaissez certainement le MasterMind, un célèbre jeu où il est question de trouver une combinaisons de plusieurs boules colorées. 

    Je cherche, pour m'amuser, à faire une IA capable d'y jouer. Dans le jeu classique, les combinaisons font 4 boules et il y a 6 couleurs mais j'étends le principe en augmentant le nombre de boules et de couleurs.

    Pour le moment, j'ai implémenté un algorithme de force brute qui peut trouver la solution d'une combinaison 8 boules 8 couleurs en une dizaine d'essais et en quelques secondes. Après, si on augmente le nombre de couleurs ou de boules, ça devient trop long.

    J'ai aussi essayé un algorithme génétique qui me permet de trouver des combinaisons jusqu'à 10 boules 10 couleurs assez rapidement, mais parfois la population va s'uniformiser autour d'une mauvaise solution. J'ai beau faire varier les paramètres : population, taux d'enjambements, taux de mutations, je ne trouve pas de réglage qui fonctionne à tous les coup. C'est un peu la loterie.

    Deux questions :
    1) Comment peut-on optimiser le réglage d'un algorithme génétique ?
    2) Existe-t-il une autre méthode pour résoudre ce problème ? Les raisonnements que l'on fait intuitivement en tant qu'humain lorsqu'on joue au jeu ne sont pas faciles à généraliser sous forme d'algorithme, je trouve. Pourtant ils doivent être intéressants, ils permettent de trouver en envisageant un très petit nombre de solutions (en comparaison des algos présentés ci-dessus). Peut-on imiter ces raisonnements par un algo ? Je pensais à une sorte de recherche dans un arbre.

    Merci de partager vos connaissances.

    -
    Edité par Umbre37 15 novembre 2021 à 10:20:15

    • Partager sur Facebook
    • Partager sur Twitter
      14 novembre 2021 à 22:52:05

      J'avoue que j'utiliserai des approches plus classiques. Récemment, l'algo de Knuth a été évoqué https://openclassrooms.com/forum/sujet/algorithme-pour-mastermind
      • Partager sur Facebook
      • Partager sur Twitter
      C++: Blog|FAQ C++ dvpz|FAQ fclc++|FAQ Comeau|FAQ C++lite|FAQ BS| Bons livres sur le C++| PS: Je ne réponds pas aux questions techniques par MP.
        14 novembre 2021 à 23:05:43

        lmghs a écrit:

        J'avoue que j'utiliserai des approches plus classiques. Récemment, l'algo de Knuth a été évoqué https://openclassrooms.com/forum/sujet/algorithme-pour-mastermind


        Merci, je n'avais pas vu le sujet, et je ne connais pas l'algo de Knuth, je vais m'y intéresser.
        • Partager sur Facebook
        • Partager sur Twitter

        Méthode pour jouer au MasterMind

        × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
        • Editeur
        • Markdown