Faire jouer l'ordinateur au Mastermind, une solution

Rappel de l'énoncé

L'énoncé suggérait une technique.

  1. Commencer par produire tous les arrangements possibles pour le secret. Il s'agit de l'ensemble A(n, C) des arrangements de taille n des couleurs C = {1, …, 2n} dont la définition inductive est rappelée ci-dessous.
    A(k+1, C) =
     
    ∪
    c ∈ C
    		 {  (c ; X) | X ∈ A(k, C∖{c}) },    A(0, C) = { ∅ }
  2. Proposer au joueur MasterMind un des arrangements possibles g, en invoquant sa méthode processGuess. Le joueur répond par un objet r de la classe Result.
  3. Si l'arrangement proposé est le bon (méthode winningResult du joueur MasterMind) le jeu est fini.
  4. Sinon, ne garder que les arrangements qui, confrontés à l'essai g, produisent le Result r, et recommencer en 2.

Une solution simple

Les classes ListList et Finder.

On suit directement les indications de l'énoncé. Les essais (classe List, fournie) seront regroupés dans des listes (de listes donc)

class ListList { List val ; ListList next ; ListList (List val, ListList next) { this.val = val ; this.next = next ; } }

Il faut d'abord produire la liste de tous les arrangements de taille n des couleurs {1,…, 2n}. Une définition inductive est donnée, sa programmation sans fioritures conduit au code suivant, extrait de la classe Finder.

// Generate all possible attempts, ie sequence of n integers in 1..2n static ListList generate(int n) { List allColors = null ; for (int k = 2*n ; k >= 1 ; k--) { allColors = new List (k, allColors) ; } return generate(n, allColors) ; } // All subsequences of size n from elts private static ListList generate(int n, List elts) { if (n == 0) { return new ListList (null, null) ; } else { ListList r = null ; for (List p = elts ; p != null ; p = p.next) { int elt = p.val ; ListList q = generate(n-1, remove(elt, elts)) ; for ( ; q != null ; q = q.next) { r = new ListList (new List (elt, q.val), r) ; } } return r ; } }

Où la petite fonction remove est :

// Remove x from list p private static List remove(int x, List p) { if (p == null) return null ; else if (x == p.val) return p.next ; else return new List (p.val, remove(x, p.next)) ; }

On peut critiquer le code ci-dessus, en particulier la consommation mémoire est importante. Mais le code est juste, simple, et se déduit directement de la définition récursive. Par ailleurs, il suffit pour traiter le cas n=5.

Pour réaliser les étapes 2. à 4. de l'algorithme je propose une fois encore une solution très simple, qui suit (presque) l'énoncé à la lettre.

static List find(MasterMind m) { int n = m.length ; ListList p = generate(n) ; while (p.next != null) { List guess = p.val ; Result r = m.processGuess(guess) ; p = filter(r, guess, p) ; } return p.val ; }

La méthode statique filter réalise le gros de l'étape 4 : confronter tous les arrangements possibles à l'essai (guess) pour ne retenir que ceux qui se comportent comme le secret.

// Returns attempts from p, s.t. testing them against guess results in res static ListList filter(Result res, List guess, ListList p) { ListList r = null ; for ( ; p != null ; p = p.next) { if (res.equals(p.val.evaluate(guess))) { r = new ListList (p.val, r) ; } } return r ; }

Pour obtenir ce code assez simple, il fallait remarquer que l'opération relativement compliquée de confronter un arrangement à un essai (de confronter deux List) est réalisée par la méthode (dynamique) evaluate des List. Si on ne remarquait pas, on pouvait toujours la reprogrammer à partir des méthodes containElts et matchingElts qui elles étaient définies dans l'énoncé du contrôle.

Le code de ma méthode find est un peu plus subtil que l'énoncé, puisque la condition d'arrêt est l'existence d'un unique « arrangement possible » et non pas un résultat de n noirs (c'est le premier prolongement). Si la liste des possibles p contient des éléments deux à deux distincts et l'élément guess (ce qui est le cas ici), il est immédiat qu'un résultat r = m.processGuess(guess) comprenant n noirs entraîne que la liste filter(r, guess, p) ne comprend qu'un seul élément, qui est d'ailleurs guess. Réciproquement, si la liste p ne contient qu'un seul arrangement, alors cet arrangement est le seul, parmi tous les arrangements possibles, qui reste compatible avec toutes les réponses de MasterMind. C'est donc le secret (si MasterMind n'a pas triché).

Efficacité

Voici, quelques exemples d'exécution le code de MasterMind étant légèrement modifié pour afficher les essais de Finder. On utilise la commande Unix time pour afficher le temps d'exécution (sous la forme temps réel, temps passé par la machine dans le code utilisateur et dans les appels systèmes). 

% time java Referee 5
Le secret est: 2 -> 5 -> 4 -> 6 -> 8
10 -> 1 -> 9 -> 2 -> 8 = [1; 1]
1 -> 7 -> 3 -> 6 -> 8 = [2; 0]
10 -> 2 -> 3 -> 6 -> 5 = [1; 2]
1 -> 5 -> 3 -> 2 -> 4 = [1; 2]
5 -> 4 -> 3 -> 10 -> 8 = [1; 2]
2 -> 5 -> 4 -> 6 -> 8 = [5; 0]
Finder a trouvé en 6 coups

real    0m0.627s
user    0m0.610s
sys     0m0.040s
% time java Referee 5
Le secret est: 3 -> 4 -> 9 -> 10 -> 5
10 -> 1 -> 9 -> 2 -> 8 = [1; 1]
1 -> 7 -> 3 -> 6 -> 8 = [0; 1]
10 -> 2 -> 7 -> 4 -> 5 = [1; 2]
2 -> 5 -> 9 -> 4 -> 3 = [1; 3]
10 -> 4 -> 5 -> 9 -> 3 = [1; 4]
3 -> 4 -> 9 -> 10 -> 5 = [5; 0]
Finder a trouvé en 6 coups

real    0m0.630s
user    0m0.510s
sys     0m0.050s

On voit donc que le problème est résolu pour n=5. Faisons un essai pour n=6. 

% time java Referee 6
Le secret est: 11 -> 7 -> 2 -> 9 -> 10 -> 3
Adios: Java heap space
java.lang.OutOfMemoryError: Java heap space

real    0m25.302s
user    0m1.110s
sys     0m0.100s

Le programme échoue par épuisement de la mémoire avant même de proposer son premier essai. Autrement dit la génération des arrangements consomme énormément de mémoire. La mémoire consommée est le « heap », c'est-à-dire la zone de mémoire utilisée par les new du programme. Il faut savoir que, par défaut, java limite la zone mémoire heap à une taille relativement faible selon des critères modernes (64 Mo). Il n'est pas scandaleux d'augmenter significativement cette limite, par exemple jusqu'à 256 Mo. Et là, ça fonctionne. 

% time java -Xmx256M Referee 6
Le secret est: 3 -> 10 -> 7 -> 2 -> 5 -> 12
12 -> 1 -> 11 -> 2 -> 10 -> 3 = [1; 3]
1 -> 12 -> 2 -> 9 -> 4 -> 3 = [0; 3]
12 -> 2 -> 10 -> 1 -> 8 -> 5 = [0; 4]
2 -> 11 -> 1 -> 8 -> 10 -> 9 = [0; 2]
10 -> 1 -> 12 -> 3 -> 5 -> 6 = [1; 3]
3 -> 10 -> 7 -> 2 -> 5 -> 12 = [6; 0]
Finder a trouvé en 6 coups

real    0m9.700s
user    0m9.400s
sys     0m0.320s

D'autres essais confirment un temps de l'ordre de la dizaine de secondes, et aussi que la majorité du temps d'exécution est consommée par la génération des arrangements. Pour obtenir un programme plus efficace, il convient de chercher d'abord à améliorer cette première phase, qui est la plus gourmande en termes de mémoire et de temps machine.

Un peu plus efficace

Regardons donc à nouveau la méthode statique generate.

12 // All subsequences of size n from elts 13 private static ListList generate(int n, List elts) { 14 if (n == 0) { 15 return new ListList (null, null) ; 16 } else { 17 ListList r = null ; 18 for (List p = elts ; p != null ; p = p.next) { 19 int elt = p.val ; 20 ListList q = generate(n-1, remove(elt, elts)) ; 21 for ( ; q != null ; q = q.next) { 22 r = new ListList (new List (elt, q.val), r) ; 23 } 24 } 25 return r ; 26 } 27 }

Il y a une inefficacité facile à corriger : la méthode remove (appel à la ligne 20) parcourt la liste elts au pire en entier et la copie. Or, si on encode l'ensemble elts comme une paire d'un tableau et d'un indice initial k (c'est-à-dire que l'ensemble des elts est l'ensemble des cases du tableau à partir de celle d'indice k), on peut enlever un élément en incrémentant tout simplement l'indice k. Pour un k donné, on doit parcourir le tableau des elts à partir de k puis enlever l'élément vu avant l'appel récursif. On y parvient en echangeant l'élément vu et l'élément d'indice k, avant l'appel récursif. On oublie pas d'annuler l'échange après le retour de l'appel récursif, afin de rendre le tableau dans l'état où on l'a trouvé. On obtient.

// All subsequences of size n from indices [k...[ in elts private static ListList generate(int n, int k, int [] elts) { if (n == 0) { return new ListList (null, null) ; } else { ListList r = null ; int c = elts[k] ; for (int i = k ; i < elts.length ; i++) { int elt = elts[i] ; // Couleur « vue » /* Echanger c et elt dans elts */ elts[k] = elt ; elts[i] = c ; ListList q = generate(n-1, k+1, elts) ; for ( ; q != null ; q = q.next) { r = new ListList (new List (elt, q.val), r) ; } /* Défaire l'échange */ elts[k] = c ; elts[i] = elt ; } return r ; } }

Malheureusement le gain en temps et mémoire est faible. En tout cas insuffisant pour passer n=6 sans utiliser l'option -Xmx de java. J'ai quand même décrit l'optimisation car elle illustre un point important, un bon choix de structure de donnée pour l'ensemble elts évite des operations inutiles.

Heureusement, il a une autre source d'allocation mémoire abusive dans le code de generate : on construit énormément de ListList intermédiaires pour ensuite les parcourir et les jeter immédiatement (lignes 20 à 23, dans generate) Il serait plus malin de construire directement la ListList à l'ordre n sans passer par les listes d'arrangements de cardinaux inférieurs. C'est tout à fait possible à condition de construire les arrangements en descendant lors de la récursion au lieu de le faire en remontant. On considère maintenant l'ensemble A(n, C, suffix) de la forme (a; suffix) où a est un arrangement de taille n des couleurs de C.

A(k+1, C, suffix) =
 
∪
c ∈ C
 {  A(k, C∖{c}, (c; suffix)) },    A(0, C, suffix) = { suffix }

On veut donc calculer A(n, {1, …, 2n}, ∅).

Il est important de remarquer que les éléments de la liste finale sont ajoutés un par un et que leur ordre importe peu, on peut alors utiliser le vieux truc d'un argument de style « continuation » pour éviter de concaténer les listes (voir par exemple l'amphi 05) Soit au final :

// Generate all possible attempts, ie sequence of n integers in 1..2n static ListList generate(int n) { int [] allColors = new int [2*n] ; for (int k = 2*n ; k >= 1 ; k--) { allColors[k-1] = k ; } return generate(n, 0, allColors, null, null) ; } // All subsequences of size n from indices [k...[ in elts, appended to suffix private static ListList generate(int n, int k, int [] elts, List suffix, ListList result) { if (n == 0) { return new ListList (suffix, result) ; } else { ListList r = null ; int c = elts[k] ; for (int i = k ; i < elts.length ; i++) { int elt = elts[i] ; // Couleur « vue » /* Echanger c et elt dans elts */ elts[k] = elt ; elts[i] = c ; result = generate(n-1, k+1, elts, new List(elt,suffix), result) ; /* Défaire l'échange */ elts[k] = c ; elts[i] = elt ; } return result ; } }

On a enfin un programme qui fonctionne pour n=6. 

% time java Referee 6
Le secret est: 1 -> 9 -> 2 -> 4 -> 6 -> 10
Finder a trouvé en 9 coups

real    0m3.873s
user    0m3.660s
sys     0m0.140s
% time java Referee 6
Le secret est: 6 -> 8 -> 2 -> 10 -> 3 -> 1
Finder a trouvé en 5 coups

real    0m3.812s
user    0m3.760s
sys     0m0.080s

Chipotage

On peut pousser le bouchon encore un peu plus loin en remplaçant la ListList par un tableau de List. En effet, les tableaux sont systématiquement moins gourmands en mémoire que les listes, puisque le champ next des ListList doit bien se trouver quelque part en mémoire. Cette technique est ici facilitée parce que nous connaissons la taille du tableau par avance (c'est le nombre d'arrangements de n éléments pris dans 2n).

private static int nbArrangements(int q, int n) { int r = 1 ; for (int k = 1 ; k <= q ; k++) { r *= n ; n-- ; } return r ; } // Generate all possible attempts, ie sequence of n integers in 1..2n static List [] generate(int n) { int [] allColors = new int [2*n] ; for (int k = 2*n ; k >= 1 ; k--) { allColors[k-1] = k ; } next = 0 ; result = new List[nbArrangements(n, 2*n)] ; generate(n, 0, allColors, null) ; return result ; } private static int next ; private static List [] result ; // All subsequences of size n from indices [k...[ in elts, appended to suffix private static void generate(int n, int k, int [] elts, List suffix) { if (n == 0) { result[next] = suffix ; next++ ; // Collect one subsequence } else { ListList r = null ; int c = elts[k] ; for (int i = k ; i < elts.length ; i++) { int elt = elts[i] ; // Couleur « vue » /* Echanger c et elt dans elts */ elts[i] = c ; generate(n-1, k+1, elts, new List(elt,suffix)) ; /* Défaire l'échange */ elts[i] = elt ; } } }

Dans le code ci-dessus on a limité l'échange des éléments c et elt à ce qui est utile. On a également utilisé un tableau global resultat et un indice global next. Notez que ces deux variables sont déclarées private et systématiquement initialisées avant le premier appel de la méthode generate récursive.

Évidemment il faudra aussi modifier les méthodes find et filter pour travailler sur des tableaux. Rien de vraiment difficile, on peut même ranger le résultat de filter dans le tableau passé en argument.

static int filter(Result res, List guess, List [] p, int sz) { int next = 0 ; for (int k = 0 ; k < sz ; k++) { List elt = p[k] ; p[k] = null ; // Gagne petit, enlever une référence vers la liste elt if (res.equals(elt.evaluate(guess))) { p[next++] = elt ; } } return next ; } static List find(MasterMind m) { int n = m.length ; List [] p = generate(n) ; int sz = p.length ; while (sz != 1) { List guess = p[0] ; Result r = m.processGuess(guess) ; sz = filter(r, guess, p, sz) ; } return p[0] ; }

Au final on arrive à la classe Finder quand même plus efficace. 

% time java Referee 6
Le secret est: 4 -> 3 -> 7 -> 12 -> 5 -> 9
Finder a trouvé en 8 coups

real    0m2.492s
user    0m2.350s
sys     0m0.080s

On pourrait optimiser encore, par exemple représenter les arrangements eux-mêmes par des listes n'est en fait pas très malin. On pourrait essayer les tableaux ou mêmes les chaînes. Mais bon, pour passer à l'ordre 7 facilement il convient maintenant d'examiner l'algorithme lui-même.

Franchement plus efficace

L'analyse précédente montre que le point critique de l'algorithme est la génération des 2n (2n−1) … (n+1) arrangements. Et même en fait, la construction d'une structure de donnée qui contient tous ces arrangements. Une analyse plus détaillée des cellules de listes allouées révèle qu'en tout nous allouons

A(n) = A2n1 + A2n2 + ⋯ + A2nn−1 + A2nn

cellules de List et B(n) = A2nn cellules de ListList ou cases de tableaux, selon la technique adoptée (où A2nq est le nombre d'arrangements de q éléments parmi 2n). Sans pousser jusqu'à l'analyse asymptotique on voit que pour n=7 on a besoin de 2428804 cellules de List et de 2162160 cellules de ListList. Soit de l'ordre de 4,5 milions de cellules de listes, ce que Java a bien du mal à nous donner.

Il s'agit maintenant de diminuer drastiquement la taille de la liste initiale. On peut le faire assez facilement en tirant quelques esssais au hasard et en limitant les arrangements de la liste initiale à ceux qui donnent des résultats compatibles avec les réponses données par MasterMind aux essais faits au hasard. Ainsi, en sacrifiant quelques coups, on arrive généralement à limiter la longueur de la liste initiale à une taille raisonnable. Notez que cette technique ne réduit pas le temps passé a engendrer les arrangements initiaux — au contraire il faut confronter chaque arrangement aux essais faits au hasard, mais seulement la taille de la liste initiale. En pratique, une telle optimisation ne portant que sur la taille de la structure produite est valable, tant il est vrai que souvent la mémoire coûte plus que le temps (l'emploi exagéré de la mémoire empêche les programme de s'exécuter et les machines modernes sont rapides).

Mais un élève a trouvé une solution plus astucieuse. Il s'agit d'abord d'identifier les couleurs du secret, puis ensuite leur ordre dans le secret. Pour identifier les couleurs du secret on procède exactement comme dans l'algorithme suggéré, mais

Considérons d'abord la génération :

// Tous les sous-ensembles (listes ordonnées décroissantes) de 1..2n de taille n static ListList subsets(int n) { return subsets(1, 2*n, n, null, null) ; } /* Renvoie la concatenation formée de 1. La liste de toutes les listes de la forme (liste de taille card dont les éléments sont pris dans min..max) concaténée avec suffix. 2. et de k */ static ListList subsets(int min, int max, int card, List suffix, ListList k) { if (max-min+1 < card) { return k ; } else if (card == 0) { return new ListList(suffix, k) ; } else { k = subsets(min+1, max, card, suffix, k) ; return subsets(min+1, max, card-1, new List(min, suffix), k) ; } }

Puis le filtrage :

static ListList filterSubsets(Result res, List guess, ListList p) { ListList r = null ; int nCorrect = res.white+res.black ; for ( ; p != null ; p = p.next) { if (nCorrect == p.val.containsElts(guess)) { r = new ListList (p.val, r) ; } } return r ; }

On obtient alors les couleurs du secret exactement comme on obtenait le secret dans les solutions précédentes :

static List find(MasterMind m) { int n = m.length ; Try tries = null ; ListList p = subsets(n) ; while (p.next != null) { List guess = p.val ; Result r = m.processGuess(guess) ; tries = new Try (guess, r, tries) ; p = filterSubsets(r, guess, p) ; } List colors = p.val ;

Dans le code ci-dessus on notera que les essais effectués sont mémorisés dans tries de type Try qui est une bête liste de paires (List × Result).

En effet, nous devons maintenant essayer toutes les permutations des éléments de la liste colors des couleurs du secret. Parmi toutes ces listes, nous n'allons retenir que celles qui sont compatibles avec les réponses aux essais effectués lors de la phase de recherche des couleurs. En procédant ainsi, nous tirons un parti maximal de tous les coups joués (et donc diminuons le nombre de ceux-ci), mais nous produisons aussi une liste plus petite et nous avons vu qu'économiser la mémoire est important. Voici donc la méthode qui engendre toutes les permutations de colors et ne retient que celles qui sont compatibles avec les coups déjà joués.

static ListList permut(int n, List colors, Try tries) { int [] t = new int [n] ; int k = 0 ; for (List q = colors ; q != null ; q = q.next) { t[k++] = q.val ; } return permut(tries, 0, n, t, null, null) ; } private static boolean compatible (List p, Try tries) { for ( ; tries != null ; tries = tries.next) { if (!p.evaluate(tries.guess).equals(tries.result)) return false ; } return true ; } private static ListList permut(Try tries, int k, int n, int [] t, List p, ListList r) { if (k >= n) { if (compatible(p, tries)) { return new ListList (p, r) ; } else { return r ; } } else { int c = t[k] ; for (int i = k ; i < n ; i++) { int x = t[i] ; t[i] = c ; r = permut(tries, k+1, n, t, new List (x, p), r) ; t[i] = x ; } return r ; } }

La technique utilisée pour engendrer les permutations est celle que nous avons déjà employée pour les arrangements (construire en descendant la récursion, accumuler les résultats dans une liste).

Il reste, pour compléter find, à réutiliser la boucle de recherche que nous avons déjà écrite lors de notre premier essai.

ListList q = permut(n, colors, tries) ; while (q.next != null) { List guess = q.val ; Result r = m.processGuess(guess) ; q = filter(r, guess, q) ; } return q.val ; }

Le programme final, constitué des classes ListList, Try et Finder, est très rapide à l'ordre n=7 et fonctionne à peu près jusqu'à n=11. 

% time java Referee 7 
Le secret est: 7 -> 4 -> 10 -> 11 -> 12 -> 9 -> 6
Finder a trouvé en 8 coups

real    0m0.200s
user    0m0.100s
sys     0m0.040s
% time java Referee 7
Le secret est: 11 -> 10 -> 4 -> 13 -> 9 -> 7 -> 5
Finder a trouvé en 10 coups

real    0m0.208s
user    0m0.160s
sys     0m0.040s
% time java Referee 11
Le secret est: 2 -> 17 -> 19 -> 8 -> 7 -> 21 -> 1 -> 13 -> 5 -> 15 -> 22
Finder a trouvé en 15 coups

real    2m31.525s
user    2m29.120s
sys     0m0.410s

Évidemment, pour des n petits on peut craindre que le programme optimisé joue quelques coups de plus que les programmes plus simples de la section précédente. Deux tests de 10 essais de secrets de taille 5 pris au hasard donnent une moyenne de 6,2 coups pour le programme simple et de 6,7 coups pour le programme optimisé. C'est sans doute un peu léger pour conclure.

Enfin on constate, à l'aide de quelques affichages, que c'est maintenant le temps de génération des permutations (méthode permut) qui domine. Ce qui n'est pas trop surprenant, ce temps étant de l'ordre de n! asymptotiquement bien plus grand que C2nn.

C2nn
n!
 = 
(2n)!
n!3
 ≈
√
2 π 2n
⎛
⎜
⎜
⎝
2n
e
⎞
⎟
⎟
⎠
2n



 
⎛
⎜
⎜
⎜
⎜
⎜
⎝		√
2 π n
⎛
⎜
⎜
⎝
n
e
⎞
⎟
⎟
⎠
n



 
⎞
⎟
⎟
⎟
⎟
⎟
⎠
3






 
 =
√
2
2π
·
1
n
· ⎛
⎜
⎜
⎝
4e
n
⎞
⎟
⎟
⎠
n



 

(Avec la formule de Stirling et sauf erreur !)

Ce document a été traduit de LATEX par HEVEA