Le cas énigmatique d’Enigma

mardi 5 janvier 2010
par  Alain BUSSER

Le principe du jeu Enigma est enfantin : Le joueur déplace une boule noire sur l’écran, avec la souris, jusqu’à ce que la boule noire en question ait touché dans le bon ordre des pierres de couleur. On dirait un jeu de mémoire pour les 3-4 ans. Pourtant le nombre d’adultes accros à ce jeu est suffisant pour qu’il continue à évoluer...

Il est difficile de montrer de façon statique comment fonctionne un jeu vidéo, par essence dynamique. Des vidéos peuvent être visionnées en suivant ce lien. Sinon rien ne vaut l’expérience de jouer à Enigma, les premiers niveaux de ce jeu ayant été conçus pour des digital natives qui ne lisent rien, et pouvant donc se découvrir sans lire la doc du jeu.

Au début

Sur la capture d’écran ci-dessous, on aperçoit le héros du jeu, surnommé « Blackball », qui au départ était à gauche, et a été déplacé jusqu’à ce qu’il touche la pierre bleue.

Celle-ci avait initialement l’aspect des autres pierres bleues appelées « oxydes » et donc surmontées de pyramides. Mais au contact de Blackball, la pyramide s’est ouverte, révélant un carré bleu clignotant (on ne voit pas le clignotement sur la capture ci-dessus). On comprend alors qu’il s’agit pour Blackball d’aller toucher les autres oxydes pour les ouvrir, par exemple à droite :

Cette fois-ci, la pierre est rouge, et en s’ouvrant elle a fermé l’oxyde précédente : Une seule oxyde à la fois peut être ouverte. Comment alors peut-on les ouvrir toutes ?

On voit ci-dessus une exception à la règle précédente : C’est parce que la deuxième oxyde est rouge aussi que Blackball, en les activant toutes les deux, a établi une sorte de lien télépathique entre ces deux oxydes et qu’elles restent ouvertes définitivement.

On découvre alors une autre règle d’Enigma : Les oxydes sont toujours en nombre pair, et le but du jeu est de les ouvrir en séquence jusqu’à ce qu’elles soient toutes ouvertes, ce qui nécessite de la mémoire à court terme.

Une caractéristique qu’Enigma a hérité de son ancêtre Oxyd est l’aspect atextuel du jeu : D’abord on cherche à comprendre ce qu’on doit faire, ensuite à comprendre comment on va le faire.

Le titre de cet article fait allusion à un mystère : Comment un jeu aussi simple peut-il avoir autant de fans ? C’est que dans l’exemple ci-dessus, Blackball peut rouler sur l’herbe dans tout l’écran, sauf aux bords qui sont fermés par des pierres, et que rien ne gêne son accessibilité aux oxydes. Il est possible pour les concepteurs de ce jeu de disposer sur le terrain des obstacles, et aucune limite ne semble exister pour la complexité des niveaux d’Enigma...

Planification

Ce paysage est très aquatique : Blackball est naufragé sur un îlot de forme rectangulaire, avec pour toute richesse 4 caisses de bois, et voit 3 oxydes (un nombre impair : C’est un indice, il y en donc forcément une autre quelque part, invisible sur l’écran), cette fois-ci sans leurs pyramides, mais l’une est en pleine mer et les autres sur des autres îlots :

Pour essayer d’atteindre celle du bas à gauche, Blackball essaye de nager vite vers l’îlot en question :

Le problème c’est que Blackball ne sait pas nager même sur une distance aussi courte, on ne voit plus de lui qu’un chapelet de bulles. Il va donc falloir essayer autre chose. Comme par exemple se taper la tête contre les murs, ou plutôt les caisses de bois :

La caisse a bougé ! On constate que Blackball a ressuscité mais qu’en bas, au lieu des deux vies supplémentaires dont il disposait au début, il ne lui en reste plus qu’une. En faisant le tour, il peut pousser la caisse vers le bas

puis dans l’eau :

(on constate que suite à une fausse manœuvre il s’est malencontreusement noyé à nouveau, et qu’il n’a maintenant plus de vie supplémentaire. En effet jouer à Enigma requiert parfois de l’habileté).

Il dispose maintenant d’un passage vers la première oxyde :

Comme il lui reste des caisses de bois pour fabriquer d’autres ponts, il peut maintenant accéder aux autres oxydes de l’écran et aux autres écrans (la quatrième oxyde, invisible ici, il faut bien qu’elle soit quelque part...).

Sokoban

En plus des oxydes de ce jeu, il y a de fausses oxydes, en effet en touchant l’une des pierres qui délimitent le fort ci-dessus, blackball n’a réussi qu’à l’allumer en rouge foncé, sans révélation du motif coloré habituel. Les vraies oxydes doivent donc être inaccessibles, protégées par la douve visible en haut à droite.

Comme dans l’onglet précédent, on peut combler cette douve avec les trois caisses de bois, à condition de ne pas coincer celles-ci dans un coin (elles peuvent être poussées mais pas tirées) :

Il y a bien des oxydes tout au fond :

Au moment précis où on gagne l’écran ressemble à ceci :

Des explications sur le PAR figurent dans l’onglet « Algorithmique ».

Ce jeu est une légère variante de Sokoban (en effet dans Sokoban, l’ordre dans lequel on place les caisses sur leur emplacement n’a pas d’importance, alors qu’ici on est obligé de fabriquer le pont de bas en haut). Parmi le millier de niveaux d’Enigma actuellement disponibles, plus de 300 sont des Sokoban, en général importés de la collection libre de David Skinner.

Dans un registre analogue, plusieurs niveaux d’Enigma sont des puzzles à base de pentaminos, et leur nombre est destiné à s’agrandir énormément dans la version 1.10.

Équation

Dans ce niveau il n’y a ni oxydes ni Blackball. On aperçoit 4 creux dans les coins et 4 billes blanches qui suivent toutes les 4 les mouvements de la souris. On devine que le but du jeu est de caser chaque bille blanche dans un creux. Ce genre de niveau se réussit parfois très vite mais à condition de les jouer lentement, ce qui leur a valu le nom de « Meditation ». Celui-ci se trouve dans « Esprit ».

Ce niveau de méditation est particulier dans le sens où, ici, les billes blanches sont numérotées (par les colonnes de pierres qui les surplombent). Autour de chaque creux il y a des documents que les billes blanches peuvent ramasser tout simplement en roulant dessus. Par exemple si la bille numéro 1 roule sur un document en bas à gauche, en cliquant n’importe où, le texte du document défile en bas :

C’est une équation ! Celle-ci est de niveau collège, et demande quelle puissance de 2 est égale à 16. On en déduit que c’est la bille numéro 4 qui doit aller dans ce creux (encore un jeu de mémoire). Le creux en bas à droite dit ceci :

Cette fois-ci c’est une expression à calculer mais elle aussi est de niveau collège. Le creux en haut à gauche dit ceci

et le dernier

Pour finir ce niveau il ne reste plus qu’à se rappeler quelle bille va dans quel creux (c’est pour ça que dans les images ci-dessus on a pris soin de ne pas les mélanger) et dès que la dernière rentre dans son creux, elles disparaissent en même temps :

Quelques explications sur le PAR figurent dans l’onglet « algorithmique ».

  • Enignimm est un des jeux de Nim peu classiques.
  • Map it out est un labyrinthe bidimensionnel où les connections entre salles ne sont pas visibles, mais dans la version 1.10 d’Enigma il y aura un Map it out II où le labyrinthe est quadridimensionnel. Dans la même version il y aura des jeux basés sur les graphes, dont un où le but de jeu est précisément de colorier, au sens propre, un graphe. Il y aura aussi une version assez difficile du jeu des chiffres et des lettres.
  • Use The PIN est un labyrinthe basé sur une suite de chiffres bien connue...
  • Control Panel est basé sur l’écriture binaire des ombres entiers.
  • Sierpinski est basé sur l’exploration d’une approximation de la courbe de Koch quadratique, que Benoît Mandelbrot appelle flocon de Neige de Sierpinski.
  • Enigris est une implémentation du jeu Tetris en Enigma.
  • Laser splitting est un jeu dont le but est de construire une approximation finie d’une courbe de Peano.
  • The cube est un Rubik’s cube représenté sous forme d’un patron de cube.

Algorithmique

Le superbe niveau The Metapuzzle ressemble à de l’algorithmique parce qu’au lieu de le résoudre directement, on utilise une machine fabriquant des outils de son choix :

La grille d’interrupteurs à gauche est une matrice booléenne, chaque interrupteur allumé (position : en haut) déterminant une des pièces du puzzle fabriqué par la machine (d’où le titre du niveau). Par exemple, si on actionne les deux interrupteurs en haut à droite :

L’action de l’interrupteur du bas occasionne la création d’une pièce composée de deux carrés (si le motif n’est pas connexe ça ne marche pas) :

Et on peut pousser ce motif en le heurtant suffisamment fort avec la boule noire :

En le poussant suffisamment loin, on arrive à l’écran de droite, où on peut apercevoir des outils à ramasser : Un ressort pour bondir, et un marteau qui sert à casser les pierres fissurées qui empêchent l’accès aux oxydes. Mais tout ça est inaccessible à cause de l’abîme (en noir) qui a le même effet que l’eau : Impossible de le traverser :

Blackball ne peut traverser la zone noire (il tombe dans un vide sans fin) mais la pièce de puzzle, elle, peut combler ce vide :

Encore une poussée, et

En répétant l’opération, on peut accéder au marteau, puis au ressort, et à l’autre côté. Mais ce n’est pas si facile, le mieux est encore de jouer à ce niveau pour découvrir pourquoi...

Le plus intéressant de ce niveau du point de vue algorithmique, c’est sa métadescription, en l’occurence le code source de ce niveau, lisible ici, avec une belle coloration syntaxique : La partie en rouge est une carte du niveau, et la fabrication des pièces de puzzle est effectuée par la fonction finalize_puzzle qui construit une chaîne de caractères (la concaténation de chaînes se fait avec deux points « .. ») décrivant la pièce de puzzle puis ajoute le résultat dans le tableau des objets du jeu. Autrement dit, c’est un programme Enigma qui construit un programme Enigma...

  • Enigmastermind est une implantation du jeu de Mastermind en Enigma.
  • Puzzling controls est un jeu où le joueur doit programmer une sorte de tortue LOGO invisible pour qu’elle aille aux bons endroits.
  • The Turtle aussi, à ceci près que la tortue est visible. Ce jeu peut donc lui aussi être considéré comme une introduction à l’algorithmique.
  • Khun Phan est une implémentation de l’âne rouge en Enigma.
  • The life Game est un jeu basé sur le jeu de la vie de John Conway.
  • et surtout, le jeu Print23 consiste pour le joueur à écrire un programme dans le langage de programmation Brainfuck, un langage ne connaissant que 7 instructions (plus une instruction d’entrée non utilisée ici), lequel programme est chargé d’écrire 23. Ce niveau d’Enigma est donc un interpréteur Brainfuck complet :

Les instructions du langage sont choisies avec les 7 interrupteurs de gauche, les deux autres servant respectivement à effacer la dernière instruction entrée, et à exécuter le programme. Le programme s’affiche dans la fenêtre du bas (et est donc limité à 28 instructions).

Par exemple, le programme

++++>++

met 4 dans la première variable, puis 2 dans la deuxième :

ce que confirme l’affichage du débogueur de l’interpréteur.

La multiplication de 8 par 7 se fait avec le programme

>+++++++[<++++++++>-]

(on commence par aller à la deuxième variable, que l’on rend égale à 7 ; puis on effectue une boucle, 7 fois donc, où on recule vers la première variable, que l’on incrémente 8 fois, et on retourne à la deuxième variable que l’on décrémente ; comme on quitte la boucle lorsque la deuxième variable est nulle, on l’effectue bien 7 fois).

Le message de débogage confirme bien que la première variable est égale à 56 et la deuxième est nulle à la fin du programme :

Ceci dit ce jeu est loin d’être simple, parce que non seulement 23 est premier, mais pour l’afficher il faut utiliser le code ASCII qui consiste à additionner 48 à chacun de ses chiffres ; c’est donc un 50 et un 51 que doivent contenir les deux variables...

Et pour ce qui est de l’utilisation de ce langage pour l’apprentissage de l’algorithmique, elle est peu recommandée vu que le langage est peu lisible et utilise les tableaux et les pointeurs, hors programme.

Le calcul du PAR (pour Professional Average Rating), un terme hérité du golf, donne lui aussi un exemple de démarche algorithmique : Le PAR se calcule à partir des durées des joueurs dit « professionnels », c’est-à-dire ceux qui ont enregistré auprès du site d’Enigma plus d’une centaine de niveaux réussis ; ce sont ceux qui ont un « handicap ». Or bien qu’average signifie moyenne, ce n’est pas la moyenne des durées qui est calculée mais la moyenne harmonique de celles-ci : En effet plus la durée est courte et plus le joueur est bon. Un paramètre plus pertinent que la durée pour classer les joueurs est donc l’inverse de celle-ci, d’où la moyenne harmonique. Celle-ci est décrite dans le manuel d’Enigma comme une moyenne coefficientée donnant plus de poids aux bons joueurs qu’aux moins bons :

However, for the PAR calculation, we take into account only scores from users who have solved more than a certain percentage of levels (currently about 10% of the levels). For every level, we calculate the harmonic average of the scores of these ‘professionals’. We take professionals who did not solve a level into account with the 10-fold world record score. The harmonic average calculates as

harm.avg. = N / (sum_[j=1..N] 1/score_j) )

It weights small (short) times with a greater weight than large (long) solution times.

(extrait du manuel de référence d’Enigma)

Lua

Le jeu Enigma est écrit dans le langage de programmation Lua, qui ressemble un peu au défunt Pascal, mais avec des objets. En Lua, une boucle s’écrit « for i=1,10 do ... end » et un test « if x==2 then ... else ... end » ce qui rend ce langage assez lisible pour toute personne ayant des rudiments d’Anglais. Pourtant, le langage Lua est brésilien. Un interpréteur en ligne est ici.

Lua est d’ailleurs un des langages favoris des amateurs de jeux, surtout les jeux de rôles et les jeux sur console. Ce qui évidemment lui donne un attrait immense auprès des élèves de Seconde...

La création d’un jeu sous Enigma est donc assez facile en mode texte, et d’ailleurs ce faisant, on s’amuse encore plus qu’en jouant à Enigma (ceci est un témoignage personnel...) ! Et avec le logiciel BlackBall Editor il suffit de dessiner le jeu avec la souris pour concevoir celui-ci !


Il se trouve que justement, la conception de jeux vidéos soulève des problèmes d’algorithmique intéressants (et pas toujours simples), comme par exemple le comptage des jeux de Nim.

Des exemples propres à Enigma :

  • Comme les objets d’Enigma (à part Blackball) ont des coordonnées entières, la recherche des voisins les plus proches d’un objet donné utilise la distance de Manhattan.
  • Les calculs de coordonnées et les tests sont utiles en Enigma ; par exemple pour savoir si Blackball est au point de coordonnées (3,5) on écrit
    if Blackball.x == 3 and Blackball.y == 5
  • Un bon moyen de trouver un arbre de poids minimum est l’algorithme de Kruskal. Nat Pryce a réussi à le convertir en un générateur automatique de labyrinthes, les labyrinthes étant des objets importants dans Enigma. Cet algorithme, récursif, fonctionne par décomposition et recomposition, avec une réunion de sous-labyrinthes :

(extrait de la bibliothèque « natmaze » en Lua). Un exemple de labyrinthe engendré automatiquement peut se voir ici.

  • De même, des objets de type « puzzle » peuvent être engendrés automatiquement par une biliothèque Lua qui assure que, après permutations, le puzzle obtenu est connexe. Les manipulations de ces objets, comme le Rubik’s cube, utilisent beaucoup des conjugaisons dans le groupe des permutations. Un exemple d’utilisation de cet algorithme est ici.
  • Enigma possède des objets qui interagissent comme le « trigger » qui réagit lorsque Blackball roule dessus (on en voit à droite dans Metapuzzle dans l’onglet précédent), ou les interrupteurs. Ceux-ci communiquent avec d’autres objets (allumage d’un laser ou ouverture d’une porte par exemple). C’est une manière originale de présenter les notions de programmation objet ou de sous-programme (l’action d’un interrupteur appelant le sous-programme).

Commentaires

jeudi 10 février 2011 à 22h16

........
SOKOBAN ET ENIGMA Je crois qu’il n’y aucun rapport , le labirynthe n’est aucunement du jeu ; mais bon il reste egnimatique c’est vrai à quelle but et qu’elle interet à commencer une partie de enigma ? que cache vraiment ce jeux une question à chaque , decouverte ?

Annonces

Prochains rendez-vous de l’IREM

Séminaire EDIM-IREM

- Mercredi 14 juin 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
- Mercredi 21 juin 2017, 14h-18h, 146 route de Grand-Coude, Saint-Joseph


Brèves

Décès de Roger Mohr

mardi 27 juin

On sait bien que Nicolas Bourbaki n’était pas le nom d’une personne mais le pseudonyme d’un groupe. L’équivalent en informatique théorique est Claude Livercy, auteur de la théorie des programmes. Roger Mohr était un des membres de Claude Livercy.

À travers les labyrinthes : algorithmes et fourmis

dimanche 1er septembre 2013

Quand les chercheurs mettent au point des modèles d’optimisation et de recherche de plus court chemin qui s’inspirent du comportement de masse de colonies de fourmis...
À écouter : Sur les Épaules de Darwin, émission diffusée sur France Inter samedi 31 août 2013.

Rencontres Mondiales du Logiciel Libre à St-Joseph

mardi 20 août 2013

Les RMLLd se dérouleront pour la 2e fois à Saint-Joseph du 22 au 25 août.
C’est une opportunité pour les élèves qui suivent la spécialité ISN et les passionnés d’informatique.

Voici pour le samedi et le dimanche quelques interventions choisies :
- http://2013.d.rmll.info/Raspberry-votre-ordinateur-au-format-carte-de-credit?lang=fr
- http://2013.d.rmll.info/Materiel-libre-et-DIY?lang=fr
- http://2013.d.rmll.info/Arduino-de-l-electronique-libre?lang=fr

Noter aussi les conférences Art et Culture du dimanche, ainsi qu’une conférence plus engagée.

Le programme complet se trouve ici. Une radio sera ouverte pour l’occasion.
Des plaquettes à distribuer se trouvent ici.

Hyper-vidéos pour l’algorithmique au lycée

dimanche 19 août 2012

Olivier Roizès, à la demande de l’ADIREM, a réalisé une collection d’hyper-vidéos de présentation de logiciels et environnements de programmation. Ces hyper-vidéos, c’est-à-dire des vidéos contenant des éléments clicables, devraient être utiles aux enseignants désireux de se familiariser avec Python, CaRMetal, R, Rurple, Scilab ou Xcas.

Ouverture du SILO

mardi 1er novembre 2011

Le SILO (Science Informatique au Lycée : Oui !) est un espace collaboratif documentaire de partage et de formation collégiale, à destination des professeurs appelés à enseigner l’informatique au lycée.

Une initiative du CNDP, de l’INRIA et de Pasc@line, à laquelle se sont associés SPECIF, fuscia, EPI et ePrep.

Sur le Web : Site du SILO

Introduction à la science informatique

lundi 12 septembre 2011

Le CRDP de Paris publie le premier ouvrage destiné aux professeurs chargés d’enseigner la nouvelle spécialité « Informatique et sciences du numérique » en Terminale S à la rentrée 2012. Cet ouvrage a été coordonné par Gilles Dowek, directeur de recherche à l’INRIA.

Sur la création de la spécialité ISN, on pourra également consulter l’interview donnée au Café pédagogique par l’inspecteur général Robert Cabanne.

Sur le Web : CRDP de Paris

Deux publications sur l’algorithmique

samedi 17 octobre 2009

L’IREM d’Aix-Marseille publie une brochure de 73 pages, téléchargeable librement, intitulée Algorithmes et logique au lycée. Ces notions sont illustrées et déclinées sur des exercices du programme de spécialité mathématique en série L, mais sont adaptables aux programmes à venir.

Le hors série thématique n° 37 du magazine Tangente, disponible actuellement en kiosque, s’intitule « Les algorithmes. Au cœur du raisonnement structuré ». Extrait de l’éditorial : « La rédaction de Tangente a conçu la quasi-totalité de ce hors série thématique pour qu’il puisse être lu par des élèves de Seconde ».

Une carte mentale pour l’algorithmique

jeudi 10 septembre 2009

Sur son site, Jean-Jacques Dhénin a publié une carte mentale géante qui renvoie vers plus de 30 documents en ligne sur l’algorithmique. Tout ce qu’il faut — et même davantage — pour faire face au nouveau programme de Seconde !

Un catalogue libre d’algorithmes pour le lycée

dimanche 30 août 2009

Guillaume Connan, de l’IREM de Nantes, publie un catalogue libre de 119 pages d’algorithmes pour le lycée. Sur son site très riche, on trouvera d’autres documents en rapport avec l’algorithmique, notamment sur l’utilisation des langages fonctionnels au lycée et sur la comparaison programmation fonctionnelle/programmation impérative.

L’algorithmique à l’IREM de Lille

vendredi 26 juin 2009

Le groupe AMECMI de l’IREM de Lille vient de mettre en ligne des ressources importantes au service des professeurs de Seconde :

- Algorithmique et programmation (Emmanuel Ostenne)
- Bibliographie amoureuse de l’algorithmique (Alain Juhel)

Statistiques

Dernière mise à jour

lundi 24 juillet 2017

Publication

759 Articles
Aucun album photo
133 Brèves
11 Sites Web
132 Auteurs

Visites

5 aujourd'hui
427 hier
2064385 depuis le début
8 visiteurs actuellement connectés