Le nom de Berlekamp n’est pas inconnu des amateurs de jeux mathématiques : Il est, avec John Horton Conway et Richard Guy, l’auteur du livre Winning Ways for your Mathematical Plays.

jeu original (100 lampes)	jeu avec curseur (de 1 à 100 lampes)

Le jeu avec les curseurs est intéressant à étudier, parce qu’en jouant on constate que

1. Avec une seule lampe on gagne du premier coup !
2. Avec 4 lampes on gagne aussi du premier coup, à condition de trouver le bon interrupteur !
3. Avec 9 lampes, il faut en général plus de temps pour gagner qu’avec 4 lampes.
4. Plus généralement, plus il y a de lampes, plus il faut de temps pour gagner : C’est la théorie de la complexité (informatique théorique).
5. Plus précisément, alors que le jeu à 16 lampes est à peine plus difficile que le jeu à 9 lampes, le jeu à 25 lampes est nettement plus difficile que le jeu à 16 lampes : Le jeu de Berlekamp n’est pas de classe P (pas résoluble en temps Polynomial). Le fait de pouvoir faire varier un nombre entier et voir l’effet produit sur le temps de résolution du jeu, est important pour comprendre ce que signifie P.
6. Enfin, même avec 100 lampes, il arrive qu’on trouve assez vite la solution, par chance ou intuition : Le Nondéterminsme rend le jeu Polynomial, et on dit donc qu’il est de classe NP (complexité).

Ainsi, rien qu’en jouant à actionner des interrupteurs, on peut avoir l’intuition du problème P = NP...

Eteins les lumières !

Essayez de baisser autant que possible la lumière, à l'aide des interrupteurs inverseurs

Pour l'instant il y a 4 lampes allumées alors qu'on peut descendre à 34...

Le code source de ce jeu

L’entête du fichier ne comprend que des liens vers les dépendances (CoffeeScript, jQuery etc) et les effets de style, que voici décrits :

En voici la traduction en langage CSS :

    body { background: black; color: lightgreen; }
    .ui-slider-handle { border-radius: 50%; }
    .ui-slider { background: darkcyan; }
    .intvert { margin-left: 4px; width: 12px; height: 32px; margin-bottom: 20px; }
    .inthoriz { width: 32px; height: 12px; margin-right: 20px; }
    .lumière { margin: 2px; width: 20px; height: 20px; border-radius: 50%; background: black; }
    .allumé { background: red; box-shadow: 0px 0px 8px orange; }

Une div devient une lumière simplement en lui attribuant la class Css « lumière », ce qui va en faire un disque noir de 20 pixels de diamètre ; et pour allumer une lumière, il suffit de lui ajouter la classe Css « allumé ». La gestion de l’aspect est donc assez facile, au point qu’on n’a même plus besoin de stocker les coordonnées des lumières allumées dans une matrice ; en fait presque toutes les données sont enregistrées hors JavaScript, dans le Document Object Model.

Quand au corps de la page html, il est finalement assez simple :

<h1>Eteins les lumières !</h1>
<h2>Essayez de baisser autant que possible la lumière, à l'aide des interrupteurs inverseurs</h2>
<h2>Pour l'instant il y a <span class="affN">4</span> lampes allumées alors qu'on peut descendre à 34...</h2>

<table id="panneau"></table>

<footer>Jeu inventé par Elwyn Berlekamp, dans le cadre de recherches sur les codes correcteurs d'erreur, en 1960</footer>

Il y a donc un titre principal, un énoncé assez court pour tenir dans un titre secondaire (h2), un diagnostic également sous forme d’un titre secondaire, un tableau vide d’identifiant « panneau » et une note de bas de page. C’est tout ! Maintenant si on regarde le contenu du second h2, on voit que dans son texte se trouve un span de classe affN (comme « affichage numérique ») qui sera utilisé dans le script.

Pourtant si on regarde la structure de la page html en 3D, on voit qu’il y a beaucoup plus de choses que ce qui y a été placé ; en l’occurence le tableau n’est plus vide :

On constate que le span contenant 52 est représenté surélevé par rapport au reste du titre h2 qui le contient ; c’est justement parce que dans l’arborescence de la page html, c’est un enfant du h2 en question. Quand au nombre 52, il a été placé par le script ci-dessous dans tous les spans de ce type (mais il n’y en a qu’un).

Le tableau a été déclaré vide et il est plein. Comment expliquer ce mystère ? C’est qu’en plus du html d’origine, il y a du html fabriqué par script. C’est assez fascinant : Le script est dans le html, et lorsqu’on affiche la page html dans le navigateur, le script s’exécute, ayant pour effet de modifier la page html qui le contient. Avant de voir comment les cellules sont ajoutées au tableau, on définit quelques fonctions utiles pour la suite :

dé = (nFaces) ->
    Math.ceil nFaces*Math.random()

comptage = ->
    $(".allumé").length

affichage = ->  
    $(".affN").text comptage()

La fonction dé simule un dé à n faces, ici on s’en servira pour choisir au hasard un interrupteur à actionner pour démarre le jeu sur une configuration aléatoire. L’algorithme est classique : On simule une variable aléatoire uniforme sur [0 ;n] en multipliant par n une variable aléatoire uniforme sur [0 ;1], puis on l’arrondit à l’entier supérieur pour avoir un nombre entre 1 et n.

La fonction suivante sert à compter les lampes allumées. La fonction notée par un dollar, c’est jQuery. En lui soumettant le nom d’une classe Css (on voit que c’est une classe Css parce que son nom commence par un point), elle renvoit un tableau contenant tous les objets de la page html possédant cette classe. Ici il s’agit d’un tableau contenant toutes les lampes allumées. La longueur de ce tableau est alors le nombre de lampes allumées.

Enfin la fonction d’affichage des résultats appelle, via jQuery, tous les éléments de classe affN (en fait il n’y en a qu’un mais si on veut enrichir la page web on n’a rien à modifier dans le script), mais plutôt que les compter, va leur envoyer une instruction : Remplacer leur texte par le nombre de lampes allumées.

Une autre fonction utilitaire est celle qui dit si on a gagné. Elle commence par appeler la fonction affichage puis, si le résultat du comptage est inférieur ou égal à 35, elle affiche un message disant qu’on a gagné :

verdict = ->                                                            
    affichage()
    alert "Gagné" if comptage() <= 35                                   

Maintenant on en arrive à se demander si jQuery n’a pas été inventé juste pour permettre de programmer ce jeu : La fonction toggleClass va

• ajouter la classe « allumé » à toute lampe qui ne la possède pas déjà (autrement dit, allumer toute lampe éteinte) ;
• enlever cette classe à toute lampe la possédant (autrement dit, éteindre toute lampe allumée).

On applique cette fonction d’inversion à toutes les lampes d’une ligne ou d’une colonne, que jQuery peut mettre dans un tableau pour peu que les lampes d’une même ligne aient une classe commune qui les identifie ainsi :

inverserLigne = (n) ->
    $(".ligne#{n}").toggleClass "allumé"
inverserColonne = (n) ->              
    $(".colonne#{n}").toggleClass "allumé"

L’astuce est qu’au moment où on crée par exemple la lampe qui se trouve à la 5^e ligne 3^e colonne, on lui donne à la fois la classe « ligne5 » et la classe « colonne3 », ce qui fait qu’une fois le tableau créé, toutes les lampes ayant la classe « colonne3 » sont précisément les lampes de la troisième colonne. C’est donc au moment de la création des 100 lampes qu’on va prendre soin de leur attribuer les classes qui permettront de les repérer.

La préparation du jeu se fait dans une fonction appelée shaker (on agite les interrupteurs aux hasard). L’algorithme consiste à partir de la solution puis à s’en éloigner au hasard pour arriver à une configuration choisie pour ne pas être trop facile à résoudre. C’est le principe du bonneteau. On constitue une liste des coordonnées des lampes à allumer, puis on boucle sur cette liste : Tant qu’il y reste une lampe à allumer, on en retire ses coordonnées de la liste et on l’allume : Pour cela on demande à jQuery la liste des lampes de sa ligne, et on applique à cette liste de lampes, un filtre ne renvoyant que celles qui ont aussi le bon numéro de colonne (normalement il n’y en a qu’une), et au résultat obtenu, on envoie le message addClass qui aura pour effet de l’allumer. Après cela, on se retrouve avec la solution du jeu, on va alors actionner un interrupteur horizontal et un interrupteur vertical choisis au hasard (fonction deuxCoups). Puis on recommence ces actions jusqu’à ce que la configuration ait l’air suffisamment difficile à résoudre :

shaker = () ->                                                          
    state = [[1,1],[1,4],[1,7],[1,10],[2,1],[2,5],[2,8],[3,1],[3,6],[3,9],[4,2],[4,4],[4,9],[5,2],[5,5],[5,7],[6,2],[6,6],[6,8],[6,10],[7,3],[7,4],[7,8],[8,3],[8,5],[8,9],[8,10],[9,3],[9,6],[9,7],[10,7],[10,8],[10,9],[10,10]]
    while state.length > 0    
        led = state.pop()   
        $(".ligne#{led[0]}").filter(".colonne#{led[1]}").addClass "allumé" 	
    for n in [0...16]                                                 				   
        deuxcoups()     
    while comptage() < 38                                           			       
        deuxcoups()
    affichage()

deuxcoups = ->
    inverserLigne dé 10
    inverserColonne dé 10

Les trois fonctions suivantes ne sont exécutées qu’après chargement de la page web dans le navigateur : Elles font appel à des éléments qui doivent avoir été créés auparavant, par exemple pendant le chargement de la page.

Pour commencer, la fonction qui remplit le tableau :

    $("#panneau").append "<tr id='ligne0'><th></th></tr>"
    for n in [1..10]
        $("#ligne0").append "<th><div class='intvert' id='vswitch#{n}'></div></th>"                                         
    for m in [1..10]
        $("#panneau").append "<tr id='ligne#{m}'><th><div class='inthoriz' id='hswitch#{m}'></div></th></tr>"
        for n in [1..10]
            $("#ligne#{m}").append "<td><div class='ligne#{m} colonne#{n} lumière'></div></td>"       

    shaker()                                                            

La première ligne s’adresse à l’élément d’identifiant « panneau » et lui demande de s’accrocher (comme une caravane à une voiture) un peu de code html. Ce code représente une rangée (« tr ») contenant pour l’instant une cellule vide (de type « th ») et possédant l’identifiant « ligne0 » : C’est la future ligne du haut.

Ensuite on rajoute dans cette rangée les 10 interrupteurs verticaux, en bouclant sur n, et à chaque passage dans la boucle, on ajoute dans la ligne 0, une cellule de type « th » qui contient une div d’identifiant « vswitch1 », « vswitch2 » etc. ; et à chaque fois on donne à la div créée, le type « intvert » qui en fera un interrupteur vertical.

Maintenant que la ligne 0 et ses 11 cellules sont créées, on crée les 10 lignes suivantes pour m allant de 1 à 10, en les nommant, les insérant dans le tableau (« append ») et en y mettant déjà une cellule de type « th » contenant une div de type « inthoriz » (ce qui en fera un interrupteur horizontal) et portant un nom comme « hswitch1 » « hswitch2 » etc. : Une fois créée et insérée dans le tableau, une ligne comporte déjà un interrupteur à sa gauche ; il ne reste alors qu’à insérer 10 lampes dans la ligne.

Ce qui se fait dans la boucle intérieure, d’indice n, en ajoutant à chaque fois, dans la ligne, une cellule de type « td » qui, à son tour, contient une div de type « lumière ». Par exemple, quand on est à la ligne 5 colonne 3, la lampe qui vient d’être ajoutée dans le tableau possède les classes Css suivantes :

• ligne5 ce qui permet de savoir qu’elle est dans la ligne 5 ;
• colonne3 ce qui permet de savoir qu’elle est dans la colonne 3 ;
• lumière ce qui permet de savoir que c’est une lumière.

Les deux premières classes sont ce qui permet de manipuler les lignes entières et les colonnes entières ci-dessus, et donc simplifient énormément le travail de programmation. Une fois le tableau constitué, un appel à la fonction shaker est immédiatement effectué pour « mélanger » le tableau et ne pas trop laisser le temps de voir la solution.

A ce stade la page html est complète mais on ne peut pas encore jouer. Pourquoi ? Parce que les interrupteurs ne sont pour l’instant que des coques vides dans lesquelles il reste à décrire leur comportement. Un interrupteur est un curseur n’ayant que deux valeurs, il faut donc

• dire que c’est un curseur (« slider ») ;
• l’orienter convenablement (verticalement si c’est un interrupteur vertical) ;
• définir les deux valeurs extrêmes 0 et 1 pour que ce soit un interrupteur ;
• lui donner une valeur par défaut ;
• et dire comment il doit se comporter quand il est actionné :

    $(".intvert").slider                                                
        orientation: "vertical"
        min: 0
        max: 1
        value: 0
        change: (evt,ui) -> 
            n = ($(this).attr 'id')[7..]                                          
            inverserColonne n
            verdict()

Il reste à décrire ce qui se passe quand l’état de l’interrupteur a changé :

• on calcule un entier n en enlevant les 7 premiers caractères du nom (« id ») de l’interrupteur : Par exemple si ce nom est « vswitch8 » il ne reste plus que « 8 » qui est bien un entier.
• on inverse l’état allumé/éteint de toutes les lampes de la colonne n
• on regarde si le jeu est fini et on affiche le résultat.

La définition des interrupteurs horizontaux est très similaire, on ne la met ici que pour l’intégralité du code source :

    $(".inthoriz").slider                                               
        min: 0
        max: 1
        value: 0
        change: (evt,ui) -> 
            n = ($(this).attr 'id')[7..]
            inverserLigne n
            verdict()

Remarque historique

En testant ce jeu, on doit faire attention à ne pas abuser de ces matrices clignotantes. Témoin cette étrange ancêtre de la mémoire vive qu’est le tube de Williams : Un écran converti en mémoire de travail pour le processeur, et choisi dans un projet réaliste parce que modeste : La Small-Scale Experimental Machine. Pendant un calcul, des motifs apparemment aléatoires apparaissaient sur cet écran luminescent [1] :

Alan Turing, qui avait contribué à ce projet, semblait capable de comprendre ces motifs et disait même voir les bogues sur l’écran. Les autres membres de l’équipe le surnommaient « prof »...

Un autre jeu de lampes

Antérieur au jeu de Berlekamp, le Nimrod (ordinateur) avait été testé par Turing au début des années 1950. Il s’agissait d’éteindre des lampes dans la version « classique » du jeu de Nim (à 3 tas), telle que théorisée en 1901 par Charles Bouton (qui a donné le nom de Nim à ce jeu à trois tas). Ici on éteint des lampes dans 5 tas contenant initialement des nombres impairs de diodes, comme dans le jeu de Marienbad.

Ce jeu fait grandement usage de l’excellente bibliothèque underscore.js qui permet de compter les éléments d’un tableau satisfaisant un critère, de choisir un élément au hasard dans le tableau etc.

Pour ne pas se faire battre trop souvent par la machine, lire cet article...

Plus récent que le Nimrod, mais plus ressemblant au jeu de Berlekamp, il y a le jeu dit « lights out » (qui se jouait sur une vraie petite console) :