algorithme 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.

Hello,

Ce serait intéressant que tu mettes un lien vers l’algorithme que tu décris.

Par rapport au niveau de jeu réglable, de façon générale il y a plusieurs approches possibles avec ce genre de jeu de réflexion/stratégie:

• Limiter la profondeur de la recherche
• Choisir des heuristiques différentes, vérifier moins de contraintes ou prendre en compte moins d’élément dans le calcul du meilleur coup
• Choisir, avec une certaine probabilité, aléatoirement un coup qui soit moins bon que le coup optimal

La troisième option est sans doute la meilleure, mais peut-être la moins facile à implémenter car c’est peut-être plus difficile à équilibrer (avec une probabilité P trop grande et/ou un aléatoire trop aléatoire, c’est vite fait de faire une IA trop faible ou très inconstante)

Une méthode générique pour résoudre le mastermind est de conserver une liste de toutes les combinaisons possible et à chaque tours, proposer une combinaison possible et éliminer toutes les combinaisons qui ne sont plus possible d’après les indications donnés par l’autre joueur.

Tant que le nombre de combinaisons initiale est assez faible¹, un tel algo permet de trouver la bonne combinaison, mais pas forcément de manière optimale. En regardant l’algo de Knuth, ce que j’ai décris est assez similaire, sauf que plutôt que de choisir la prochaine proposition de manière optimale, on choisi la prochaine proposition parmi les combinaisons possibles. Choisir la première combinaisons possible d’une liste trié est probablement beaucoup moins efficace que en choisir une aléatoirement.

Au passage, l’algorithme de Knuth peut tout à fait s’implémenter quelque soit le nombre de pions et de couleurs. Par contre, le temps d’exécution risque de devenir trop long si le nombre de combinaisons est trop grand. Sans optimisation et si je me trompe pas, au premier tour le complexité de l’algo est $O((3c^2)^p\times K)$ avec $c$ le nombre de couleurs, $p$ le nombre de pions et $K$ une truc polynomial en $c$ et $p$ (la complexité de l’algo qui détermine le nombre de pions de la bonne couleur bien/mal placés). Au delà de 6 couleurs et 4 pions (le mastermind standard), le temps d’exécutions sera probablement déjà trop long au début.

L’avantage de l’algo de Knuth, c’est qu’il calcul un score pour chaque proposition. Pour obtenir la solution au plus vite, on prends la proposition avec le meilleur score, mais il est aussi possible de prendre une solution avec un moins bon score si tu veux rendre l’IA plus simple à battre.

Dans les autres idées, il est tout à fait possible de créer d’autres algos (peu efficaces) pour résoudre le mastermind. Par exemple, l’IA peut commencer par des propositions de couleur uni jusqu’à savoir quels sont les couleurs de la combinaison à déduire et ensuite essayer de trouver l’ordre correcte. On peut aussi imaginer une amélioration possible où au lieux de tester des combinaisons uni, on teste $n$ pions dont on connait la couleur et $p-n$ de couleur uni pour savoir combien de pions de la nouvelle couleur sont dans la combinaison finale. Cela permet de glaner des informations de position plus tôt.