Mastermind (https://fr.wikipedia.org/wiki/Mastermind) est un jeu de déduction classique, édité pour la première fois en 1972. De par la simplicité de ses règles, ce jeu a fait l'objet de nombreux travaux par des chercheurs dans différents domaines des mathématiques discrètes et de l'informatique (chercheurs en algorithmique, en optimisation combinatoire, en intelligence artificielle), afin de développer des stratégies pour trouver le code en un nombre minimum de coups.
Donald Knuth a notamment montré que, pour la version du jeu commercialisée (où l'on cherche à deviner une séquence de 4 couleurs, éventuellement avec plusieurs occurrences d'une même couleur), il existe une stratégie permettant de trouver le code en 5 coups maximum [1]. Divers autres travaux ont suivis avec des stratégies mobilisant des techniques de domaines variés. Pour une revue de littérature relativement récente sur le sujet, on pourra par exemple se référer à l'article de Merelo [2].
L'objectif de ce projet est d'étudier différentes stratégies existantes pour le mastermind, de les implanter et de les comparer à travers des expérimentations numériques. On développera aussi une interface de jeu où un joueur humain pourra se confronter à une intelligence artificielle, le vainqueur étant le joueur trouvant le code le plus rapidement. Une autre question intéressante pourra être d'identifier les codes les plus difficiles à identifier, selon la stratégie utilisée par l'algorithme.
Références
[1] Knuth, D.E. The Computer as Mastermind. Journal of Recreational Mathematics, 1976-77, 16.
[2] Merelo, J.J. The game of MasterMind in 2020: an overview of literature.