Les chapeaux de Hamming
(Le jeu des chapeaux et codes correcteurs d'erreurs)

Introduction

Les jeux de hasard ont toujours posé le problème de la meilleure stratégie gagnante, permettant d'atteindre une probabilité de gain maximal.
Ces jeux basés sur l'aléatoire laissent penser que seul le fait d'avoir « beaucoup de chance » y intervient...
Cependant, nous allons voir, en étudiant un de ces jeux (le célèbre jeu des chapeaux), que l'outil mathématique peut jouer un rôle important dans la recherche et le perfectionnement de stratégies.
En effet, ce jeu s'appuie sur un problème mathématique datant de 1998, développé dans la thèse d'un informaticien américain, Todd Ebert, de l'Université de Californie, et connaît actuellement un grand succès. Peu de temps après sa parution, le problème des chapeaux a circulé sur Internet, suscitant l'intérêt de grands mathématiciens...
Ainsi, l'étude de ce jeu nous a mené à la considération des codes correcteurs d'erreurs de Hamming, très utilisés en informatique.
Ce qui nous amène à nous demander comment ces codes correcteurs d'erreurs peuvent intervenir dans l'optimisation de la probabilité de gagner à des jeux aléatoires, essentiellement au jeu des chapeaux ?

I Le jeu des chapeaux

A) Présentation du jeu des chapeaux

Le jeu des chapeaux est un jeu récent qui a intéressé de nombreux mathématiciens, informaticiens, théoriciens du codage et même les médias !
Les règles sont assez simples :
Une équipe de n joueurs se présente (au moins 3 joueurs). On dispose de 2 couleurs de chapeaux différentes, disons ici Rouge et Bleu. On attribue à chaque joueur un chapeau en tirant à pile ou face sa couleur. Chaque membre de l'équipe voit le chapeau des autres mais pas le sien. Pendant tout le jeu, aucune communication n'est autorisée entre les différents joueurs, ils sont par la suite interrogés un à un (ou simultanément selon certain ! le but est qu'aucun des joueurs ne doit connaître le vote de ses partenaires...) pour qu'ils disent quelle couleur de chapeau ils ont.
Au final, une équipe gagne si au moins une bonne réponse a été donnée. Si l'un des joueurs donne une mauvaise réponse, l'équipe perd. Notons que l'alternative « Je passe » est acceptée (néanmoins elle ne peut être choisie par toute l'équipe si celle-ci veut avoir des chances de gagner !!)
Il est autorisé aux équipes avant le début du jeu de mettre en place une stratégie... C'est ce que nous allons tenter d'étudier, du moins pour le cas .

B) Etude des stratégies et optimisations possibles

A première vue, on pourrait croire que la meilleure probabilité de gain est de ½ : en effet cela peut se produire si tous les joueurs répondent « Je passe » sauf un qui répondra au hasard Rouge ou Bleu (il aura donc une chance sur deux de faire gagner son équipe !).
Toutefois, une stratégie proposée dans le cas de trois joueurs nous montre que l'on peut atteindre une probabilité de gagner de 75%, probabilité qui se révèle être maximale...
Notons d'abord que, sachant qu'il y a 2 couleurs de chapeaux différentes à attribuer à 3 joueurs, on aura au total configurations possibles à savoir :
{RRR ; BBR ; RRB ; BRB ; RBR ; RBB ; BRR ; BBB}
(Avec R pour Rouge et B pour Bleu)

L'équipe convient que si un joueur voit deux couleurs de chapeaux différentes chez ses partenaires, il vote « Je passe ». Sinon, il donnera la couleur opposée à celle qu'il voit.
Ainsi, on s'aperçoit que seul 2 cas sur 8 sont perdants (les configurations RRR et BBB) alors que les six restantes font gagner l'équipe ; par conséquent, la probabilité de gain est bien de .
De plus, on remarque que cette stratégie vérifie la propriété suivante :
Dans les configurations gagnantes, seul un joueur donne la bonne couleur, les autres « passent » ; dans les configurations perdantes tous les joueurs annoncent une mauvaise couleur.

La stratégie est dite alors optimale ou parfaite. (C'est-à-dire qu'il y a 3 (n dans le cas général) fois plus de chances de gagner que de perdre)

C) Etude des stratégies parfaites

En revenant au cas général avec n joueurs, ces stratégies, sous réserve d'existence, assurent le fait qu'au mieux, il y aura n fois plus de votes gagnants que perdants. Cela signifie en termes de probabilité (en notant p le nombre de configurations perdantes) que la probabilité de gagner dans ce cas est de
(résultat que l'on retrouve bien avec )
Mais alors, dans quels cas peut-on espérer avoir une stratégie parfaite ?
Supposons l'existence d'une telle stratégie, avec n joueurs.
Notons p le nombre de configurations perdantes. Ainsi, comme la stratégie est supposée optimale, le nombre de cas gagnants est de .
On a donc, sachant que le nombre total de configurations est de , la probabilité de gagner est de d'une part, d'autre part (d'après ce qui a été établi précédemment)
d'où , c'est-à-dire que , soit que est un entier (naturel).
Par conséquent, est une puissance de 2, et il existe tel que (et de plus ).
Ainsi, l'existence d'une stratégie parfaite nécessite que n, le nombre de joueurs, s'écrive sous la forme (avec ...). Néanmoins, ces stratégies existent-elles toujours ? Peut-on affirmer que :
Si le nombre de joueurs vérifie la condition précédente, il existe alors une stratégie assurant une probabilité de gagner de ?

Nous allons donc voir que ce problème que pose la recherche de stratégies optimales et leurs conditions d'existence a été résolu par Richard Hamming en 1940 en définissant et construisant ses fameux codes correcteurs d'erreurs.

II Les codes de Hamming

A) Présentation

Le but premier des codes de Hamming, c'est de trouver un moyen de vérifier l'intégralité d'un message codé en binaire, cela grâce à un code (appelé code correcteur ou code de contrôle) qu'on liera au message envoyé, et qu'on supposera sans erreurs à la réception. On pourrait penser par exemple à un code de sorte que chaque élément du code soit répété trois fois (par exemple pour envoyer 010, on envoie 000111000), ce qui fait que n'importe quelle erreur (ou même beaucoup plus si elles ne sont pas trop proches les unes des autres) pourra être détectée et corrigée, puisqu'il suffit de regarder lequel entre 0 et 1 est le plus présent dans la suite des trois éléments qui sont sensés être égaux. Cependant, pour un message utile de taille n, il faudra envoyer en tout un message de taille...3n !, ce qui commence à faire beaucoup lorsqu'on envoie des messages assez importants.

Le code de Hamming permet, pour un message de taille n de la forme , de faire un code correcteur de taille m, qui détecte et corrige de façon sûre 1 erreur, et en détecte la plupart du temps 2. Ainsi, pour coder par exemple un message de taille 247, il suffit d'un code de contrôle de taille 8, ce qui est bien plus pratique que la solution proposée précédemment (mais permet moins d'erreurs).

B) Quel rapport avec le jeu des chapeaux ?

En réalité, ce n'est pas tout à fait le code de Hamming présenté précédemment qui est utile pour le jeu des chapeaux, mais un autre type de code :

Pour ce code, on se donne, pour une valeur de n donnée, un ensemble de messages de taille n de sorte que la modification d'un élément d'un message envoyé puisse permettre de retrouver l'erreur de façon non ambiguë connaissant l'ensemble des messages possibles. Ainsi, avec , on peut prendre par exemple comme ensemble {000, 111}. Un code dont l'ensemble des messages est de cardinal maximum est dit parfait ; Hamming a montré que pour n s'écrivant sous la forme , ce cardinal valait (pour , on a donc trouvé un code parfait).

Revenons maintenant au jeu des chapeaux maintenant :
On suppose que le nombre de joueurs s'écrit sous la forme , où . On construit alors un code parfait de Hamming pour des messages de taille n. On note pour la suite CP l'ensemble des suites du code. (Ainsi, selon Hamming, CP est de cardinal ) On considère maintenant la stratégie suivante :
On note ici 0 pour un chapeau Rouge, 1 pour un chapeau Bleu, et les joueurs conviennent au départ d'un numéro entre 1 et n qui leur sera attribué à chacun, et chacun aura un numéro différent (mais qui n'a pas d'importance pour l'ordre dans lequel ils donneront leur réponse)
Chacun des joueurs observe les chapeaux des autres joueurs de sont équipe, et forme ainsi une suite de 0 et de 1, dans l'ordre convenu, avec un blanc pour sa position. Il regarde ensuite si le fait de choisir l'une ou l'autre des couleurs pour son chapeau (c'est-à-dire 0 ou 1) fait qu'il se retrouvera dans le cas où la suite appartient à CP (il y aura au maximum une seule solution, par construction de CP). Si c'est le cas, il choisira la couleur opposée, sinon il passe. Ainsi :
Si la configuration était effectivement une configuration correspondant à une suite u de CP, tout le monde aura répondu de façon erronée : tout le monde n'ayant qu'une seule « erreur » à savoir la couleur de leur chapeau, chacun aura trouvé que u était la bonne configuration et dira la couleur opposée. On a donc configurations perdantes.

Si maintenant la configuration ne correspond pas à une suite de CP :
Alors il suffirait qu'un seul chapeau change, et il n'y en aurait qu'un seul possible, pour avoir la configuration correspondant à une suite v de CP. La personne ayant ce chapeau, d'après la stratégie proposée, verra de quelle couleur doit être son chapeau pour avoir cette suite, et dira alors la couleur inverse, qui correspond bien à la couleur de son chapeau. Quant aux autres, ils choisiront tous de passer : aucune des deux configurations qu'ils pourront former avec ce qu'ils voient ne correspondra à une suite de CP puisque sinon, en une seule modification (celle du joueur introduit précédemment), on passerait de cette suite à v, ce qui contredirait la définition de CP. On a donc montré que toutes les autres configurations (c'est-à-dire celles qui ne sont pas un élément de CP) sont gagnantes pour les joueurs, c'est-à-dire combinaisons gagnantes. Ainsi, la probabilité de gagner est de :

On a donc trouvé une stratégie donnant une probabilité de gagner de , d'où la réciproque au résultat vu précédemment.

Lorsque le nombre de joueur n'est pas de la forme , on peut envisager de « laisser de côté » ceux qui sont en trop pour avoir cette configuration en leur demandant de choisir systématiquement de passer. Mais la stratégie n'aura alors aucune raison d'être parfaite.
Le problème avec ce type de code de Hamming, c'est que l'algorithme permettant de créer un tel code (ou du moins l'ensemble) a une complexité de temps polynomiale, et nécessite de stocker l'ensemble des messages possibles (donc complexité spatiale aussi, mais moins importante). Nous allons donc voir ici le codage du premier code de Hamming proposé, puis une de ses applications les plus importantes, en informatique.

C) Codage en Caml/Maple

1) Codage en Caml

(* Pour un message de taille de la forme 2^n-n-1, et d'un code de contrôle de taille n (où n est un entier naturel). Toutes les matrices utilisées ici ne contiennent que des 0 ou des 1 *)

(* détermine si k est une puissance de 2 *)
let rec puiss2 m =
   if m = 1 then true
   else
      if m mod 2 = 0 then (puiss2 (m/2))
      else false;;

(* produit d'une matrice-ligne type (1,p) par une matrice type (p,n) "modulo 2", renvoie une matrice-ligne type (1,n) *)
let prod t1p tpn =
    let p = vect_length t1p and n = vect_length tpn.(0) in
    let t1n = make_vect n 0 and g = ref 0 in
    for i = 0 to n-1 do
       g :=0;
       for j = 0 to p-1 do
          g:= (t1p.(j) * tpn.(j).(i)) + !g;
          done;
       g := !g mod 2;
       t1n.(i) <- !g;
    done;
    t1n;;

(* Création d'une matrice type (2^k-k-1,k) pour déterminer la matrice-ligne du code de contrôle par "produit", modulo 2, avec la matrice-ligne du message, de taille 2^k-k-1 *)
let créemat k =
    let n = int_of_float(2.**float_of_int(k)) in
    let mat = make_matrix (n-k-1) k 0
        and g = ref 0
        and b = ref 0 in
    for i = 1 to n do
        if not(puiss2(i)) then
      begin
        g:=i;
        for j = k downto 1 do
            mat.(i-1- !b).(j-1) <- !g mod 2; (* mat.(a).(b) : élément de la a-ième ligne de la b-ième colonne *)
            g := !g/2;
            done;
      end
        else b:= !b+1;
        done;
     mat;;

(* matrice-ligne de controle pour un message de taille du type 2^n-n-1 *)
let controle t =
  let k = vect_length t and n = ref 0 in
     while int_of_float(2.**float_of_int(!n)) - !n - 1 < k do
        n:=!n+1;
        done;
     if int_of_float(2.**float_of_int(!n)) - !n - 1 <> k
       then failwith "il faut un message de taille du type 2^n-n-1"
       else prod t (créemat !n);;

(* message et code de contrôle ensemble *)
let coder t =
    let k = vect_length t (* longueur du message *)
        and contt = controle t in (* code de contrôle du message *)
    let n = vect_length (controle t) in (* longueur du code de contrôle du messsage *)
    let t_et_contt = make_vect (k+n) 0 in (* message et code de contrôle ensemble *)
            for i = 0 to k-1 do
                t_et_contt.(i) <- t.(i);
                done;
            for i = 0 to n-1 do
                t_et_contt.(k+i) <- contt.(i)
                done;
            t_et_contt;;

(* décodage d'un ensemble message-code de contrôle de taille de la forme 2^n-1, où il y a n codes de contrôle à la fin *)
let decoder t =
    let n= int_of_float(log(float_of_int(vect_length t) +. 1.) /. log(2.)) in (* longueur du contrôle *)
    let k = int_of_float(2.**float_of_int(n))-n-1 (* longueur du message *)
        and cont_r = make_vect n 0 in (* code de contrôle recu *)
    let c = make_vect k 0 (* message recu, puis corrigé si nécessaire *)
        and g = créemat n
        and m = ref (-1) (* endroit de l'erreur si il y en a une *)
        and cont_m_r = ref [||] (* code de controle du message recu *)
        and e = make_vect n 0 in (* matrice-ligne représentant les différences entre cont_r et !cont_m_r modulo 2 *)
         for i = 0 to k-1 do
            c.(i) <- t.(i);
            done;
         cont_m_r:= controle c;
         for i=0 to n-1 do
            cont_r.(i) <- t.(k+i);
         done;
         if cont_r = !cont_m_r then
           c
         else begin
         for i = 0 to n-1 do
           e.(i) <- ((cont_r.(i)+ (!cont_m_r).(i)) mod 2);
           done;
         for i = 0 to k-1 do
           if e = g.(i) then m:= i
           done;
         try
           c.(!m) <- ((c.(!m) + 1) mod 2);
           c;
            with
             | vect_item -> failwith "trop d'erreurs"
             (* "rattrape" l'erreur lorsque !m = -1 : il y a au moins deux erreurs dans le message*)
             end;;

2) Codage en Maple

créemat := proc(k)
local n,mat,g,b,i,j,f;
n:=2^k;
b:=0;
mat:=[seq(0,f=1..n-k-1)];
for i from 1 to n do
   if not(type(ln(i)/ln(2),integer)) then
      g:=i;
      mat[i-b]:=[seq(0,f=1..k)];
      for j from k to 1 by -1 do
          mat[i-b][j]:= g mod 2;
          g:=floor(g/2);
          od;
      else b:=b+1;
      fi;
   od;
eval(mat);
end:

prod:=proc(t1p,tpn)
local p,n,g,t1n,i,j;
p:=nops(t1p);
n:=nops(tpn[1]);
t1n:=[];
for i from 1 to n do
    g:=0;
    for j from 1 to p do
        g:= (t1p[j] * tpn[j][i]) + g;
        od;
    t1n:= [op(t1n),(g mod 2)];
    od;
eval(t1n);
end:

controle:= proc(t)
local k,n,mcont;
k:=nops(t);
n:=0;
while 2^n-n-1<k do
   n:=n+1;
   od;
if 2^n-n-1<>k then "il faut un message de taille de la forme 2^n-n-1"
   else prod(t,créemat(n));
   fi;
end:

coder:= proc(t)
local h;
h:=controle(t);
if h="il faut un message de taille de la forme 2^n-n-1" then h else
   [op(t),op(h)];
   fi;
end:

decoder:=proc(t)
local i,n,k,c,cont_m_r,g,m,cont_r,e;
n:=ln(nops(t)+1)/ln(2);
k:=2^n-n-1;
c:=t[1..k];
cont_m_r:=controle(c);
g:=créemat(n);
m:=-1;
cont_r:=t[k+1..k+n];
e:=[];
if cont_r = cont_m_r then c else
       for i from 1 to n do
          e:= [op(e),(cont_r[i] + cont_m_r[i]) mod 2];
          od;
       for i from 1 to k do
          if e = g[i] then m:=i fi;
          od;
       if m = -1
          then "trop d'erreurs"
          else
          c[m]:=1-c[m];
          c;
          fi;
       fi;
end:

(Le codage en Maple est moins long, mais celui en Caml est plus facilement adaptable à d'autres langages de programmation, car plus basique).

Comme on peut le voir, bien que le code soit assez long, il est assez facile et rapide de coder et décoder des messages binaires (pour des messages de taille , on remarque que la complexité est généralement en , voire en n parfois, on a ainsi une complexité temporelle quasi logarithmique !).

Conclusion

Ce code est très pratique en informatique, où les données reçues et envoyées, souvent altérées, doivent pouvoir être vérifiées rapidement. Ce codage permet ainsi, pour des messages de grande taille, de n'avoir qu'une très petite partie pour le contrôle et permet ainsi d'accélérer le transfert de donnée tout en permettant une certaine marge d'erreur par rapport à l'efficacité du transfert. Un inconvénient de ce codage est qu'une erreur dans le code de contrôle lui-même peut rendre le message illisible.
En revenant au jeu des chapeaux, les stratégies parfaites étant d'autant plus « efficaces » que le nombre de joueurs augmente, - en effet, la probabilité de gagner, , tend vers sa valeur maximale, à savoir 1, quand n tend vers l'infini ! - pourrait-on alors espérer gagner le Jackpot (Ce jeu répandu aux Etats-Unis permet de gagner quelque 2.000.000$ à se partager entre toute l'équipe) en se présentant au sein d'une équipe formée de 255 (si ) joueurs et ayant préalablement convenu d'une stratégie « parfaite » ? (mais si la probabilité de gagner augmente vite, le gain par joueur diminue lui aussi rapidement...)

Et qu'en serait-il si l'on décidait d'augmenter le nombre de couleurs des chapeaux... Dans ce cas, les codes de Hamming ne nous seraient d'aucune utilité, mais de nombreux mathématiciens se sont penchés sur le sujet et ont démontré que la probabilité de gain tendait vers 1 quand le nombre de joueurs d'une équipe tendait vers l'infini... Néanmoins, il est moins évident de trouver une stratégie idéale pour un tel jeu ! Alors, bon courage à ceux qui s'y aventureront !

Sources

Pour la Science n°319 : Mai 2004, « Couleurs des chapeaux et codes correcteurs d'erreurs », Jean-Paul Delahaye.

Exercice de DEUG, TCA 101 et corrigé (archive)

TIPE réalisé par Gobel's end Timmy et Immae, élèves du lycée Saint-Louis.

Cette création est mise à disposition sous un contrat Creative Commons.

Mes cours de sup et spé en prépa