Maîtriser le Mastermind

Après avoir étudié le Qui-est-ce?, attaquons-nous à un jeu un peu plus complexe: le Mastermind.

Le Mastermind est un jeu qui se joue à 2, dans lequel un joueur, le « codificateur », décide en secret d’une combinaison ordonnée de 4 couleurs parmi 8 (les répétitions étant autorisées). Le second joueur, le « décodeur », doit essayer de trouver cette combinaison en faisant des propositions qui sont évaluées par le codificateur qui donne pour chacune le nombre de pions de la bonne couleur qui sont à la bonne place et le nombre de pions de la bonne couleur mais mal placés.

Un peu de combinatoire

On peut se poser un certain nombre de questions de combinatoire sur ce jeu.

Tout d’abord, le nombre de combinaisons possibles. Avec 4 couleurs à choisir parmi 8, les répétitions étant autorisées, le codificateur a 8 choix possible pour chaque emplacement ce qui conduit à 8*8*8*8=8⁴=4096 possibilités.

Ces possibilités se répartissent en:

Type	Masques	Nombre	Pourcentage
4 couleurs	1234	8*7*6*5 = 1680	41%
3 couleurs	1123, 1213, 1231, 2113, 2131, 2311	8*7*6*6 = 2016	49%
2 couleurs (2 pions de chaque)	1122, 1212, 1221	8*7*3 = 168	4.1%
2 couleurs (3 pions d’une)	1112, 1121, 1211, 2111	8*7*4 = 224	5.5%
1 couleur	1111	8	0.2%

En effet, pour 4 couleurs, il y a 8 choix possible pour la première, puis 7 pour la suivante (puisqu’elle doit être différente de la première), puis 6 pour la troisième (différente des deux premières) et enfin 5 pour la dernière.

Pour 3 couleurs et 2 couleurs, il y a respectivement 8*7*6 et 8*7 façons de choisir les couleurs. Ensuite, il faut multiplier ce résultat par le nombre de façon d’arranger ces différentes couleurs (appelées masques dans le tableau ci-dessus).

On vérifie bien que le total est 1680+2016+168+224+8=4096.

On remarque aussi que les combinaisons avec répétition, lorsque la combinaison est réellement tirée de manière aléatoire, sont fréquentes (plus que les combinaisons sans répétition!).

Comment s’y attaquer?

Les nombres en jeu ne sont pas énormes. 4096 combinaisons, c’est ridicule pour un ordinateur. Il devrait donc être facile de produire un algorithme qui soit assez fort à ce jeu.

En y réfléchissant un peu, ce jeu a pas mal de ressemblance avec le « Qui-est-ce? » et en particulier avec la variante à deux cartes. Chaque information que nous donne le codificateur vient éliminer un certain nombre de combinaisons. Évidemment, on ne sait pas quelle sera la réponse à l’avance. Il faudrait donc maximiser l’espérance du nombre de combinaisons éliminées à chaque coup.

Pour cela, partant de la liste de combinaisons encore possibles à un stade donné du jeu (les 4096 au début) il suffit d’évaluer combien d’entre elles seraient éliminées par chaque réponse possible du codificateur pour chaque proposition possible. Comme il y a 4096 propositions possibles à chaque coup et 4096 combinaisons possibles au départ, on doit évaluer au maximum 4096*4096=16’777’216 de combinaisons. 16 millions c’est beaucoup, mais pas hors de portée d’un ordinateur.

À noter qu’il n’est pas nécessaire de refaire systématiquement le calcul pour le premier coup. Si l’on trouve, par exemple, que jouer 4 couleurs différentes le premier coup est le meilleur choix alors on pourra sauvegarder ce résultat et faire cela directement au premier coup pour éviter les calculs les plus coûteux.

On peut se demander si il est nécessaire d’évaluer les 4096 propositions possibles à chaque coup où si l’on pourrait se contenter des combinaisons encore valables, réduisant ainsi les calculs nécessaires. Malheureusement, une combinaison dont on sait déjà qu’elle est invalide peut tout de même apporter des informations. On peut s’en assurer facilement en ajoutant une ligne de log lorsque cela ce produit: c’est extrêmement fréquent. Et un peu de code supplémentaire permet de vérifier qu’il n’y a en général pas d’aussi bon choix dans les combinaisons candidates. En fait, la majorité des propositions faites par le programme sont des combinaisons dont il sait qu’elles n’ont aucune chance d’être la bonne.

Une différence à noter avec le Qui-est-ce: on gagne en soumettant une proposition qui est la bonne. Il ne suffit donc pas de réduire l’ensemble des candidats jusqu’à ce qu’il ne contienne qu’une seule combinaison, il faut aussi jouer cette combinaison si ça n’a pas déjà été fait. C’est une erreur que j’ai faite au début (en gros, « while len(combination) > 1 » au lieu de « while score != (0, nb_slots)« ) et qui m’a fait penser que mon code était plus fort que ce qu’il n’était en réalité!

Un coup d’œil au code

Le code est disponible ici et les tests associés sont là. Bien qu’assez brouillon, il peut être adapté facilement pour servir d’aide au jeu ou pour jouer contre lui soit en tant que codificateur, soit en tant que décodeur. J’espère le mettre à jour bientôt avec plus de fonctionnalités et potentiellement une interface graphique.

Parmi les choses intéressantes, la fonction la plus critique en matière de performances est score_proposal. C’est elle qui prend la majeure partie du temps. Elle est exécutée pour chaque paire (combinaison, proposition), soit plus de 16 millions de fois en début de jeu sans l’utilisation du résultat hard-codé (qui se trouve dans la fonction try_to_guess: au premier essai on utilise 4 couleurs différentes choisies au hasard). Différentes approches sont disponibles dans le code, mais aucune n’a apportée d’amélioration significative. Toute suggestion d’optimisation est bienvenue!

La fonction play_alone permet d’exécuter un certain nombre de parties où l’ordinateur joue contre lui même, choisissant les combinaisons aléatoirement. Cela permet de se faire une idée de l’efficacité. J’ai obtenu les statistiques suivantes sur 1000 parties:

Nombre de parties par nombre de coups:
3 coups: 15 (1.5%)
4 coups: 151 (15.1%)
5 coups: 580 (58.0%)
6 coups: 249 (24.9%)
7 coups: 5 (0.5%)
Nombre moyen de coups: 5.078

Mais ces statistiques ne sont de toute évidence pas parfaitement précises. En particulier, on devrait s’attendre à gagner du premier coup dans 1 cas sur 4096. Bien sûr, cela peut très facilement ne pas se produire au cours de 1000 parties. Mais du coup, on rate peut être aussi d’autres cas, en particulier des cas où la victoire prendrait plus de 7 essais. Il nous faut un moyen de s’assurer du pire cas.

Pour cela, la fonction exhaustive_stats utilise une approche simple: on utilise un mode deterministe (utilisation de [1, 2, 3, 4] comme premier essai, utilisation du premier essai à chaque coup au lieu d’un essai aléatoire parmi ceux ayant une espérance d’élimination identique) et on l’essaie sur les 4096 combinaisons possibles. Dans le cas d’une approche aléatoire (plus sympathique quand on joue contre l’ordinateur mais aussi nécessaire pour éviter que l’adversaire n’adopte une stratégie optimisée contre une stratégie déterministe), la partie sera a priori équivalente à une des 4096 jouées par exhaustive_stats à un isomorphisme prêt (Note: je ne suis pas 100% sure de cela, une confirmation ou une infirmation est bienvenue en commentaire).

Cette fonction nous fournit les statistiques suivantes:

Nombre de jeux par nombre de coups:
1 coups: 1 (0.0244140625%)
2 coups: 4 (0.09765625%)
3 coups: 63 (1.5380859375%)
4 coups: 604 (14.74609375%)
5 coups: 2431 (59.3505859375%)
6 coups: 979 (23.9013671875%)
7 coups: 14 (0.341796875%)
Nombre moyen de coups: 5.063720703125

Ainsi que les statistiques par type de combinaison, avec la légende suivante:

– 4 pions de la même couleur
3 coups: 1
4 coups: 2
5 coups: 5
4.5 coups en moyenne
– 2 couleurs, l’une apparaissant 3 fois
4 coups: 33
5 coups: 145
6 coups: 46
5.058035714285714 coups en moyenne
– 2 couleurs, chacune apparaissant 2 fois
3 coups: 1
4 coups: 33
5 coups: 93
6 coups: 41
5.035714285714286 coups en moyenne
– 3 couleurs, l’une apparaissant 2 fois
2 coups: 1
3 coups: 16
4 coups: 226
5 coups: 1225
6 coups: 536
7 coups: 12
5.148313492063492 coups en moyenne
– 4 couleurs distinctes
1 coups: 1
2 coups: 3
3 coups: 45
4 coups: 310
5 coups: 963
6 coups: 356
7 coups: 2
4.968452380952381 coups en moyenne

Il vaut donc mieux choisir une combinaison où une couleur apparaît 2 fois lorsque l’on joue en tant que codificateur contre ce programme. Étonnamment, 4 couleurs distinctes est le deuxième pire choix, juste après 4 couleurs identiques!

Un jeu optimal?

Est-ce que le programme ci-dessus joue de manière optimale?

On pourrait le penser puisqu’il joue à chaque fois le coup qui à l’espérance d’élimination maximale. N’est-ce pas le meilleur coup?

Et bien pas nécessairement! On pourrait imaginer qu’un coup soit celui qui a l’espérance d’élimination la plus grande mais conduise à des coups suivants moins efficaces. Pour être sûr de choisir le meilleur coup, il faudrait regarder l’espérance d’élimination à plusieurs coups. Les statistiques obtenues plus tôt nous permettent de mettre une limite à la profondeur de notre exploration: inutile d’aller plus loin que 6 coups puisque l’approche actuelle nous permet de gagner en 7 coups. Seule une approche garantissant la victoire en 6 coups ou moins sera supérieure.

Je n’ai pas (encore) implémenté cela. N’hésitez pas à me faire part de vos résultat dans les commentaires si vous vous y attaquez. Il est peut être possible de gagner systématiquement en 6 coups ou moins et il est certain qu’il est possible d’améliorer l’espérance du nombre de coups. C’est ce que confirme (pour le cas à 7 couleurs) un papier fourni en lien ci-dessous.

Généralisation

L’idée du Mastermind peut être généralisé selon deux dimensions:

• Le nombre de pions à choisir
• Le nombre de couleurs parmi lesquelles choisir

À noter qu’une variante fréquente est d’autoriser à inclure des « trous » dans les combinaisons. Cela revient simplement à utiliser une couleur supplémentaire.

Une notation utilisée dans certains papiers étudiant le Mastermind (voir liens plus bas) est MM(p,c) où p est le nombre de pions à choisir et c le nombre de couleurs. Ainsi, la version que nous avons étudié jusque là est MM(4,8). Les versions étudiées dans les papiers en lien plus bas sont en général MM(4,6) (il semblerait que la version initiale du Mastermind utilisait 6 couleurs) ou MM(4,7) (cette version initiale en autorisant les trous). La version MM(4,9) est aussi intéressante puisqu’elle correspond à la version 8 couleurs en autorisant les trous.

Le nombre de combinaisons possibles augment très rapidement avec p et c:

	c=1	2	3	4	5	6	7	8	9
p=1	1	2	3	4	5	6	7	8	9
2	1	4	9	16	25	36	49	64	81
3	1	8	27	64	125	216	343	512	729
4	1	16	81	256	625	1296	2401	4096	6561
5	1	32	243	1024	3125	7776	16807	32768	59049
6	1	64	729	4096	15625	46656	117649	262144	531441

Le nombre de coups nécessaires en moyenne pour gagner avec notre approche est, lorsque l’on s’autorise à faire des propositions dont on sait qu’elles sont invalides:

	c=1	2	3	4	5	6	7	8	9
p=1	1	1.5	2	2.5	3	3.5	4	4.5	5
2	1	2	2.33	2.81	3.24	3.66	4.04	4.43
3	1	2.5	2.96	3.25	3.61	3.97	4.34	4.69
4	1	2.88	3.33	3.76	4.07	4.43	4.75	5.06
5	1	3.125	3.69	4.12	4.54
6	1	3.48	3.996	4.52

Et lorsque l’on ne s’autorise à faire que des propositions encore valides (ce qui est parfois noté MM*(p,c) dans la littérature):

	c=1	2	3	4	5	6	7	8	9
p=1	1	1.5	2	2.5	3	3.5	4	4.5	5
2	1	2	2.33	2.81	3.24	3.72	4.18	4.67
3	1	2.5	2.96	3.27	3.63	4	4.40	4.78
4	1	2.88	3.36	3.80	4.10	4.45	4.81	5.14
5	1	3.125	3.71	4.18	4.61
6	1	3.52	3.997	4.56

On voit que si l’avantage existe bien, il reste très léger.

Pour aller plus loin

https://fr.wikipedia.org/wiki/Mastermind

Le reste des références est malheureusement en anglais.

Une approche du problème pour le Mastermind à 6 couleurs, par Donald Knuth: The Computer As Mastermind, Donald Knuth

Une étude d’une stratégie optimale pour le Mastermind à 7 couleurs (équivalent à 6 couleurs en autorisant les trous): An optimal Mastermind (4,7) Strategy and More Results in the Expected Case, Geoffroy Ville

Un article détaillant l’implémentation d’algorithmes optimaux pour le Mastermind (6 couleurs) et pour « Bulls & Cows », un jeu proche du Mastermind mais utilisant 9 couleurs (les chiffres) et interdisant les répétitions: Optimal algorithms for mastermind
and bulls-cows games.