B- CODAGE

Le concepteur est un moteur  puissant qui est utilisé sur Actilud dans les énigmes “Jogging”, “Cerf-volant”, “Défile de mode”, “Char à voiles”, “Verger”. Il permet de créer des énigmes aléatoires, différentes, plus ou moins difficiles selon sa programmation.

Il faut donc le programmer avec des instructions qui sont présentes dans le sélecteur de gauche, qui en propose 9.

Une fois la programmation effectuée, le concepteur exécute les instructions et génère une énigme sous  la forme d’énoncés formels. Cette énigme est déjà jouable, mais pour être lisible par tous, il faut encore traduire les énoncés formels en un texte compréhensible par tous.

Pour entrer dans la partie codage, cliquez sur l’icône Menu dans la barre d’outils et, dans la fenêtre de dialogue qui s’ouvre, choisissez le bouton Coder.

On obtient alors la fenêtre de travail suivante :

Le collecteur contient et organise les instructions puisées dans le sélecteur. On peut déplacer les instructions à l’intérieur du collecteur pour les organiser à sa guise.

Pour instancier une instruction, rendez-vous sur son icône dans le sélecteur, cliquez ou pointez sans lâcher; l’instruction apparaît. Il suffit de la glisser dans le collecteur. Seules les instructions présentes dans le collecteur seront prises en compte pendant l’exécution.

Un programme minimum

Lançons-nous ! Nous allons créer un programme minimum formé d’une seule instruction qui va générer une énigme complète.

Les données de l’intégramme sont celles de l’exemple prédéfini : des coureurs arrivent dans un ordre déterminé, portent un maillot de couleur différente et boivent chacun, à l’arrivée, un jus de fruit différent.

Au démarrage du programme: bouton utiliser un exemple pré-défini;

Ou cliquer sur l’icône menu dans la barre d’outils, planifier, bouton utiliser un exemple pré-défini.

Nous allons utiliser l’instruction PLACER : L’icône de l’instruction PLACER est le premier dans la liste. Les instructions déployées se présentent sous la forme d’une bande.

Lorsque l’on clique sur le crayon, le conseiller affiche une description de l’instruction et permet de la paramétrer. Les changements se répercutent sur l’affichage dès que l’on valide la saisie.

Comme son nom l’indique, l’instruction va placer un signe vrai ou faux à un endroit vide et propice choisi aléatoirement sur les grilles.

Choix aléatoire

Nous allons laisser le programme choisir lui-même s’il va placer un signe vrai ou un signe faux. Pour cela, dans le champ Choix du signe, on choisit aléatoire.

Si on valide à ce stade, la bande change d’aspect :

Nombre de répétitions

Nous ne serions pas très avancés si notre concepteur se contentait d’afficher un seul signe. Notre intégramme d’exemple comporte 6 grilles 5×5, soit 150 cases. Il faut donc que les 150 cases soient remplies à l’issue du travail du concepteur. C’est le rôle du champ Maximum. Nous allons donc changer le nombre maximum de répétitions.

C’est un maximum mais il ne sera pas forcément atteint. Pour ma part, lorsque je veux boucler sur une instruction jusqu’à la fin, je tape 1000, quelle que soit la taille de l’intégramme.

Tapez donc 1000 dans le champ Maximum et validez.

Comme on peut le constater, la modification est répercutée immédiatement après la validation.

Si le maximum est trop faible, le concepteur va multiplier les tentatives de créations mais n’arrivera jamais à créer une énigme complète. Il faut alors interrompre l’exécution et modifier le programme.

À la recherche de solitude ?

Si on coche la case Isolé, les cases choisies aléatoirement seront à une intersection dont la ligne et la colonne sont complètement vides: pas de signe faux, pas de booléen et évidemment pas de signe vrai. Cocher isolé peut être utile si on souhaite rendre l’énigme un peu plus intéressante mais le temps de calcul sera allongé.

Dans certains cas l’utilisation de isolé rend les calculs impossibles; c’est le cas ici si vous mettez Choix du signe à faux et isolé à vrai. Avec cette seule instruction ainsi paramétrée le solveur ne pourra jamais créer une énigme.

Exécution !

Cliquez sur le bouton propositions formelles du conseiller. S’il n’apparaît pas, cliquez sur l’icône en forme de crayon de l’instruction en cours d’édition, dans le collecteur.

Le conseiller propose deux niveaux de difficulté. Laissez le niveau standard. Vérifiez que le champ Nombre maximum de tentatives avant reprise contient 10000 (dix-mille) et validez. Après quelques secondes de travail, le résultat devrait apparaître :

Voilà une liste de propositions formelles. Elles sont déjà utilisables par le solveur.

C’est ma liste ! La vôtre est forcément différente, puisque tout ceci est aléatoire !

Utilisez le bouton Autocompléter puis cliquez sur une proposition pour la matérialiser dans la grille.

Explication de texte

Mais que veut dire la ligne :

Blanc ∩ Pomme = Vrai

L’intersection de la ligne blanc et de la colonne pomme contient un signe vrai.

De plus il n’y a pas de confusion possible. Si jamais il y a un risque de confusion avec deux items identiques (comme la couleur orange d’un maillot, qui peut se confondre avec le jus d’orange), le concepteur indiquera systématiquement l’en-tête correspondant :

Maillot Orange ∩ Jus de fruit Orange = Faux

Bis repetita placent

Que signifie le champ Nombre maximum de tentatives avant reprise  du conseiller, dans lequel nous avons mis la valeur de 10000 ?

Le concepteur a un fonctionnement récursif. Il peut arriver qu’il se fourvoie dans un calcul sans issue. Le nombre indiqué est le nombre maximum d’évaluations que l’on veut bien tolérer pour une configuration avant que le concepteur ne recommence le programme – il fait une nouvelle tentative.

On le voit quand le compteur de tentatives augmente.

Si vous mettez une valeur trop faible, le concepteur n’aura pas la possibilité de faire toutes les évaluations nécessaires pour trouver une énigme viable.

Donc, si vous voyez le nombre de tentatives augmenter trop rapidement, c’est que le nombre d’évaluations alloué est trop faible. Interrompez le processus et augmentez la valeur.

À l’inverse,si la valeur est trop élevée, le concepteur peut se perdre dans ses calculs. Diminuez la valeur.

Tout dépend bien sûr du programme.

Pour notre programme simple, la valeur de 10000 est parfaite car il faut beaucoup d’évaluations mais le risque de se fourvoyer est faible. Mais pour un programme plus complexe, il faudra sans doute baisser cette valeur. Souvent la valeur 1000 est un bon compromis pour les programmes un peu sophistiqués.

Donc, le nombre maximum de tentatives permet de régler le concepteur :

• on diminue la valeur si les calculs sont trop longs;
• on augmente la valeur si le nombre de tentatives explose !

Standard ou expert ?

Pour le moment, l’éditeur n’offre que deux choix de fonctionnement : standard ou expert.

Mode standard

Adapté aux énigmes simples.

• les instructions faisant apparaître les signes vrai sont privilégiées;
• les techniques avancées, comme la recherche de l’invariance ou de l’implication, ne sont pas utilisées.

Pour une programmation donnée, les énigmes produites seront assez courtes.

Mode expert

Adapté aux énigmes difficiles. On produit en général des énigmes plus longues.

• le concepteur essaye de maintenir les booléens le plus longtemps possible : les solutions rapides sont donc rejetées;
• les techniques de résolution avancées sont effectuées;
• l’énigme doit  être résolue avec au moins un appel à une de ces techniques avancées; sans quoi elle est rejetée et considérée comme “trop simple”.

Dans notre exemple l’utilisation du mode expert est possible si on place uniquement des signes faux;  mais il faut en général attendre assez longtemps : les  techniques de résolution avancée sont peu disponibles car ici, notre programmation (une seule instruction toute simple que l’on répète) est basique. En mode expert le concepteur multiplie les tentatives et refuse celles considérées comme trop faciles. Mais si vous patientez suffisamment il finira par trouver une solution… qui sera très longue.

Mode personnalisé ?

C’est prévu. Pour plus tard…

Un programme simple à partir de 8 ans

Avec un peu d’aide et des explications, un enfant de 8 ans devrait y arriver. L’intérêt pédagogique, outre le codage, est surtout de l’amener à rédiger des énoncés de logique.

Notre nouveau programme contient deux instructions: l’instruction PLACER, que nous venons de voir, et l’instruction suivante, SEUIL.

L’instruction SEUIL doit être placée en premier.

Comme nous utilisons l’exemple prédéfini, cette instruction portera uniquement sur la série Classement, qui est la seule à posséder une relation d’ordre.

Que fait l’instruction SEUIL ? Elle introduit une limite dans une série, pour un item donné. En voici un exemple :

Alice est arrivée avant le 3ème.

Cette proposition place trois signes faux, à l’intersection d’Alice et de 3ème, de quatrième et de cinquième.

Réglages conseillés :

SEUIL :

• isolé: vrai
• nombre maximum de répétitions : 10

PLACER:

• choix du signe : aléatoire
• isolé : faux
• nombre maximum de répétitions : 1000

En fait, comme nous demandons l’isolation pour SEUIL, il n’y aura jamais 10 répétitions. Mais peu importe si ce maximum  n’est jamais atteint, ce que nous voulons c’est obtenir un grand nombre de propositions formelles pour cette instruction.

Voici comment se présente notre programme avant son exécution :

Pour terminer un programme, il est recommandé de mettre une instruction destinée à “boucher les trous”. Ici nous utilisons PLACER “aléatoire”, mais, dans des programmes plus sophistiqués, un PLACER “faux” répété 1000 fois est recommandé.

Les réglages sont standard et le nombre maximum de tentatives est de 10000.

On devrait obtenir un énoncé formel avec une quinzaine de propositions,comme l’exemple ci-dessous.

Raisin > 3

La personne qui boit du jus de raisin est arrivée après la troisième place.

Comment travaille le concepteur ?

Pour les curieux, voici comment ça marche.

Soit un programme formé par une série P=(i₁, i₂, i₃, …. i_n) d’instructions élémentaires. Une instruction élémentaire est une instruction qui ne s’exécute qu’une seule fois. Lorsqu’une instruction est répétée n fois par le programme, cela signifie qu’il y a n instructions élémentaires à la suite qui vont s’exécuter.

Chaque instruction, une fois exécutée, produit une occurrence tirée au hasard parmi toutes celles possibles. Par exemple, pour l’instruction PLACER faux, il y a, en gros, 150 occurrences possibles puisqu’il y a 150 cases dans notre grille (en fait il y en a moins puisqu’il y a des inférences calculées : lorsqu’on place un signe “vrai” il y a automatiquement 8 cases à faux).

Le concepteur lance une occurrence de i₁. Si elle réussit, il lance une occurrence de i₂, puis de i₃, et ainsi de suite.

Si, arrivé à l’occurrence i_p, il y a un échec (impossible de résoudre l’intégramme car il y a des contradictions), le concepteur essaye une autre occurrence de i_p, choisie parmi toutes celles qui restent disponibles. Si aucune ne réussit, le concepteur conserve la série (i1, i2, … i_p-2) et  calcule une nouvelle occurrence de  i_p-1 (puisque “sous” l’occurrence précédente i_p-1 aucun i_p ne passe), puis il continue avec i_p.

Voilà pourquoi certains calculs peuvent prendre un temps énorme. Dans ce cas, il faut limiter le nombre d’évaluations. Le hasard faisant bien les choses, on finit toujours par trouver une solution acceptable en re-tentant de nouveaux calculs depuis le début, plutôt qu’en s’acharnant à finir des calculs titanesques qui pourraient demander des millénaires.