Grand concours TI-Planet été 2013 - "Le trésor de Knossos"

[critor]

Selon la mythologie grecque se trouverait sous les ruines de la cité de Knossos en Crète un gigantesque labyrinthe, le labyrinthe du Minotaure.
Outre ce monstre, le labyrinthe renfermerait nombre de pièges mortels mais aussi un fabuleux trésor...

According to Greek mythology, under the ruins of the Knossos city in Crete, there's a huge labyrinth, known as the Minotaur's labyrinth.
Besides the huge monster, the labyrinth contains many deadly traps, but also a fantastic treasure...

Ce mythe du labyrinthe dissimulant un trésor gardé par un monstre a été repris dès le début de l'aventure du jeu vidéo. On peut citer Gregory Yob qui dès 1972 sort "Chasse au Wumpus", un jeu texte programmé en langage BASIC.
Il faudra attendre 1980 pour que Texas Instruments sorte la première version graphique du jeu sous la forme d'une cartouche ROM pour son ordinateur familial TI-99/4A.

This myth of a labyrinth containing a treasure guarded by a monster was transposed to video games early in the history of video games. Gregory Yob released "Hunt for Wumpus", a BASIC game, as early as 1972.
We over the first graphical version of such a game to Texas Instruments, under the form of a ROM cartridge for the TI-99/4A family-oriented computer, several years later, in 1980.

Toutefois, le labyrinthe choisi par Texas Instruments pour son jeu obéissait à diverses contraintes, dont celle pour chaque salle de d'avoir toujours 4 salles voisines, ni plus ni moins. Cela permettait d'une part des déplacements intuitifs via les touches fléchées du clavier, et d'autre part une représentation plane facile, sous la forme d'une grille ou un quadrillage.

However, the labyrinth chosen by TI had several constraints, such as having exactly 4 (no more, no less) neighbour rooms for any given room. This enabled intuitive moves across rooms through keyboard direction keys, and an easy planar representation, under the form of a grid.

Le labyrinthe de Knossos est bien plus complexe que cela avec des niveaux sur plusieurs étages, et nous allons donc le représenter sur TI-Nspire sous une forme bien connue des Terminales ES spécialité Mathématiques, un graphe:

The Knossos labyrinth is much more complex than that, with levels on multiple floors. Let's therefore represent it on the Nspire platform through a graph, a form which should sound familiar to some French students:

Le labygraphe présenté ici comporte donc n=10 salles, numérotées de 1 à 10.
La salle n°1 est l'entrée du labyrinthe, et elle permet de rallier directement les salles n°2, 3 et 7.
Le trésor est ici en salle n°4 et le monstre-Wumpus en salle n°9.
La salle n°2 est ici piégée avec une trappe.

Il peut y avoir plusieurs trappes ou même aucune, mais il y aura toujours 1 seul trésor et 1 seul Wumpus qui ne bougera pas.

La densité des connexions entre salles est ici réglée à d=20%.
Et la probabilité (fréquence théorique) des trappes à p=10%.

The labygraph shown here has n=10 rooms, numbered from 1 to 10.
Room #1 is the labyrinth's entrance, it communicates directly with rooms #2, #3 and #7.
The treasure is here in room #4, the monster is in room #9.
There's a trap in room #2.

There can be zero, one or multiple traps, but a single treasure and a single monster. The monster does not move.

The room connectivity density is set to d=20%.
The probability (theoretical frequency) of traps is set to p=10%.

Production attendue et règles:

Expected production and rules:

L'exploration du labyrinthe de Knossos étant trop dangereuse, on décide d'y envoyer un robot muni de quelques capteurs sensoriels et d'une intelligence artificielle que tu vas programmer sur TI-Nspire dans le langage de ton choix.

Exploring the labyrinth of Knossos being too dangerous, we decided to send a robot with some touch sensors and an artificial intelligence program you're going to develop on TI-Nspire in the language of your choice.

Tout a été fait pour te faciliter la tâche, et tu pourras notamment télécharger ci-dessous le fichier TI-Nspire te permettant de générer automatiquement des labygraphes et d'exécuter pas à pas ton intelligence artificielle tout en la visualisant.

Everything has been done to facilitate you the task, and you can download below the TI-Nspire file allowing you to automatically generate labygraphs and run and view your AI step by step.

Tous les labygraphes générés ont forcément une solution, car obéissant aux règles suivantes:

• il existe toujours un chemin sûr pour rallier le trésor à partir de l'entrée
• le Wumpus ne se trouve jamais dans la salle du trésor
• la salle du trésor n'est jamais piégée

Le fichier vient d'origine avec une intelligence artificielle qui ne pense pas et se contente bêtement d'aller au hasard dans une salle voisine.

All generated labygraphs necessarily have a solution, because obeying the following rules:

• there is always a safe way to rally the treasure from the entrance
• the Wumpus is never found in the treasure room
• the treasur room is never trapped

The file comes with an artificial intelligence that does not think and simply stupidly goes randomly into a neighboor room.

Comme vous le voyez ici, sur un labygraphe de paramètres n=10, d=10% et p=10%, l'IA arrive à ressortir vivante du labyrinthe avec le trésor dans environ 30% des cas, en 10,3 coups en moyenne.

As you can see here on a labygraph with parameters n=10, d=10% and p=10%, the AI ​​gets out alive of the maze with the treasure in about 30% of cases, with 10.3 steps in average.

Votre but est donc de modifier cette IA afin de la rendre moins stupide, et de ressortir du labyrinthe avec le trésor en un minimum de coups possible.

Your goal is enhance this stupid AI so that it will get out of the maze with the treasure in the fewest moves possible.

Pour cela, vous disposez au début du code Lua de ce script de 3 fonctions appelées par le script Lua, fonctions que vous êtres libres de compléter comme bon vous semble.
Vous avez le droit d'appeler des fonctions TI-Basic externes ou même Ndless si vous y arrivez.
Vous pouvez vous créer d'autres fonctions ou variables Lua si besoin.
La seule chose interdite sous peine de disqualification est d'utiliser/modifier les autres fonctions ou variables préfournies par le script.

To do this, you have at the beginning of the Lua script 3 called functions you are free to complete.
You have the right to call external TI-Basic functions and even Ndless functions if you manage to.
You can create other Lua functions or variables if necessary.
The only forbidden thing is to use / modify other functions or variables preincluded in the script.

init(n):

doit (ré)initialiser la mémoire de l'IA pour travailler sur un labygraphe de n salles dans lequel on entre par la salle n°1. Elle est appelée à tout début de nouvelle partie.

must (re)initialize the AI memory in order to work on a labygraph of n rooms entered by room #1. It's called at the beginning of each new game.

A chaque salle visitée, l'IA perçoit des sensations, doit réfléchir et prendre une décision.
Les sensations sont:

For each visited room, the AI perceives sensations, must think and make a decision.
Possible sensations are:

• "ça pue" -> le Wumpus est dans une salle voisine...
• "ça gèle" -> il y a une (ou plusieurs) trappes dans les salles voisines...
• "ça brille" -> le trésor est dans une salle voisine...

• "it stinks" -> the Wumpus is in a neighboor room...
• "it's freezing" -> there is at least one trap in the neighboor rooms ...
• "it's shining" -> the treasure is in a neighboor room...

La fonction think(n,ip,lv,lc) reçoit à cet effet:

• n, rappel du nombre de salles du labygraphe
• ip, rappel du numéro de salle dans laquelle se trouve actuellement l'IA
• lv, la liste des numéros de salles voisines à la salle courante
• lc, une liste de 4 sensations qui valent 1 lorsque ressenties et 0 sinon:

• "ça pue"
• "ça gêle"
• "ça brille"
• "je porte le trésor"

La fonction se doit donc d'intégrer les informations perçues à l'environnement mémoire de l'IA, et d'en faire des déductions sur les positions du Wumpus, des trappes et du trésor.

Une fois ces déductions faites, il faut donc prendre une décision. L'IA peut soit:

• décider d'aller dans une salle voisine
• lancer une flèche dans une salle voisine pour y tuer le Wumpus (1 seule flèche par partie)

Notons que tuer le Wumpus n'est pas une obligation, que c'est comptabilisé comme un coup supplémentaire, et que le Wumpus cesse de puer lorsqu'il meurt.

C'est la fonction action(n,ip,lv) qui s'en charge. Elle reçoit à cet effet:

• n, rappel du nombre de salles du labygraphe
• ip, rappel du numéro de salle dans laquelle se trouve actuellement l'IA
• lv, la liste des numéros de salles voisines à la salle courante

Elle se doit de retourner ce que décide de faire votre IA, c'est-à-dire:

• soit le numéro d'une salle voisine dans laquelle aller
• soit l'opposé du numéro d'une salle voisine dans laquelle tirer une flèche pour y tuer le Wumpus

The function think(n,ip,lv,lc) is given, for this purpose :

• n, number of rooms in the labygraphe
• ip, the room number where the wumus currently is
• lv, the list of room numbers that are next to the current room
• lc, a list of 4 feelings that equal 1 when felt and 0 otherwised :

• "it stinks"
• "it's freezing"
• "it's shining"
• "I'm holding the treasure"

[/list]
The function will have to integrate the appropriate feelings to the A.I.'s memory, and from that, to be able to infer the positions of : the Wumpus, the traps, and the treasure.

Once this is done, a decision has to be made. The A.I. can either :

• go to an adjacent room
• shoot an arrow to an adjacent room to kill the Wumpus(1 arrow only by game)

Note that killing the Wumpus isn't necessary. It however counts as an additional turn. The Wumpus stops strking once it's dead.

All this is done with the function action(n,ip,lv). Its arguments (given) are :

• n, number of rooms in the labygraphe
• ip, the room number where the wumus currently is
• lv, the list of room numbers that are next to the current room

The function shall return a number meaning what the AI will do :

• (positive number) the room number to go to.
• (negative number) the negative room number into which the AI shoots an arrow

Modalités d'évaluation:

Vos IA seront évaluées à l'aide des statistiques sur un grand nombre de parties dans de gros labygraphes, c'est-à-dire:

• le pourcentage de succès
• le nombre de coups moyen

Ces statistiques sont justement fournies par le classeur TI-Nspire et vous pouvez donc à tout moment vous faire une idée de la valeur de votre IA.

Le pourcentage de succès devrait normalement être très proche de 100%. Les seules cas où une bonne IA pourrait mourir sont en effet ceux des rares labygraphes où il n'a pas été possible de tout déduire et où l'IA a du s'en remettre à la chance.

Terms of grading:

Your AI will be graded from statistics acquired from a large number of tries in big labygraphes (mazes), with :

• The success percentage
• The average number of tries

Modalités de participation:

Il vous suffit d'envoyer un email à info@tiplanet.org avant le dimanche 3 novembre 2013 à 23h59, avec:

• vos nom, prénom et adresse complète
• le fichier TI-Nspire modifié avec votre IA
• une explication de comment marche votre IA

Terms of participation:

You'll have to send an email to info@tiplanet.org before November 3rd, 2013 at 23h59 (CEST), with:

• Your first and last name, as well as your postal address
• The modified TI-Nspire file with your AI.
• An explanation on how your AI works

Lots à gagner:

Prizes to win:

• 1^er prix: 1 TI-Nspire CX CAS avec son logiciel et sa licence + 2 stickers TI-Planet
  1^se prize: 1 TI-Nspire CX CAS with its software and licence + 2 TI-Planet stickers
• 2^ème prix: 1 TI-84 Plus C Silver Edition (nouveauté couleur rentrée 2013) avec son chargeur USB + 2 stickers TI-Planet
  2^nd prize: 1 TI-84 Plus C Silver Edition (new color calculator for back to school 2013) with its USB charger + 2 TI-Planet stickers
• 3^ème prix: 1 TI-83 Plus.fr 2013 (équivalente à une TI-84 Plus Silver Edition) + 2 stickers TI-Planet
  3^rd prize: 1 TI-83 Plus.fr (equivalent to a TI-84 Plus Silver Edition) + 2 TI-Planet stickers
• 4^ème prix: 1 TI-82 Stats.fr + 2 stickers TI-Planet
  4^th prize: 1 TI-82 Stats.fr + 2 TI-Planet stickers
• 5^ème prix: 1 poster de calculatrice Texas Instruments (modèle au choix, dans la limite des disponibilités) + 2 stickers TI-Planet
  5^th prize: 1 Texas Instruments calculator poster (model of your choice, if available) + 2 TI-Planet stickers
• 6^ème prix: 1 stylo USB Texas Instruments + 2 stickers TI-Planet
  6^th prize: 1 Texas Instruments USB pen + 2 TI-Planet stickers
• 7^ème prix: 1 bloc-notes Texas Instruments + 2 stickers TI-Planet
  7^th prize: 1 Texas Instruments notebook + 2 TI-Planet stickers
• 8^ème prix: 4 stickers TI-Planet
  8^th prize: 4 TI-Planet stickers

Téléchargements:

Downloads:

Le fichier TI-Nspire du concours à modifier/compléter et à rendre:

The TI-Nspire file to modify for the contest:

LabyGraph - Wumpus

Remarque: Le fichier pourra faire l'objet d'améliorations/corrections pendant la période du concours notamment au niveau de l'interface, mais cela n'interférera en aucune façon avec le fonctionnement de votre IA si elle suit bien les règles ci-dessus.

Note:The file can be improved / fixes during the contest period especially for the interface, but this won't interfere in any way with the operation of your IA if it follows the above rules.

Pour éditer le script Lua et le compléter avec vos fonctions:

In order to edit the Lua script and complete it with your functions :

Logiciel TI-Nspire 3.2 enseignant (pour PC - gratuit pendant 90 jours)

TI-Nspire 3.2 teacher software (for PC - 90 days trial)

Logiciel TI-Nspire 3.2 enseignant (pour Mac - gratuit pendant 90 jours)

TI-Nspire 3.2 teacher software (for Mac - 90 days trial)

Logiciel TI-Nspire 3.2 étudiant (pour PC - gratuit pendant 30 jours)

TI-Nspire 3.2 student software (for PC - 30 days trial)

Logiciel TI-Nspire 3.2 étudiant (pour Mac - gratuit pendant 30 jours)

TI-Nspire 3.2 student software (for Mac - 30 days trial)

Remarque: Installer la version étudiant après avoir épuisé les 90 jours de la version enseignant ou inversement, vous permettra de cumuler 120 jours d'utilisation ce qui devrait être suffisant pour le concours

Note: installing the student version after having gone over the 90 days trial of the teacher version or vice versa, will get you 120 more trial days which should be enough for the contest

Mentions légales:

Legal notices:

Le règlement complet de ce concours, déposé légalement chez huissier, est disponible à cette adresse : archives_voir.php?id=12093 ou sur UPECS.

The full rules are available here: archives_voir.php?id=12093 or on UPECS

Les données personnelles récoltées font l'objet d'une déclaration CNIL et sont protégées selon la loi du 6 janvier 1978. Vous disposez à tout moment d'un droit d'accès, de modification et de suppression.

Personal data collection is declared to the CNIL and is protected under the law of January 6, 1978. You have at any time the right to access, modify or delete your personal data.

[Persalteas]

Hum, j'espère que j'aurai le 2e prix Je participe bien sur !

Super concours encore une fois, bravo pour l'imagination !!

Et en effet, avec 8 lots, nous sommes bichonés !

Merci !!

[Excale]

Bonne chance à tous.

PS: Si il y a des gens motivés pour le faire en C/C++ avec Ndless, regardez le dossier "luaext" dans les exemples.

[AnToX98]

8 lots, bon je vais faire de mon mieux mais pas la première place par contre hein

[mdr1]

Encore un concours TI-Planet super original, bravo et merci !
Excale : Je suis plutôt motivé pour le C++.

[matref]

Pffffffrlt alors là ... Super imagination mais comptez pas sur moi pour faire un truc acceptable >_> moi etl les AI ça fait 42.

J'ai le droit d'adapter le code Lua en C pour qu'il fasse exactement la même chose et rien d'autre (à part les fonctions que j'ai le droit de modifier) ? Parce que j'ai jamais fait de Lua.

[critor]

Pourquoi?
Seulement 2-3 lignes de ta part produiraient déjà une amélioration énorme.

L'interface de test est déjà faite.

[matref]

J'ai édité.

[critor]

J'ai le droit d'adapter le code Lua en C pour qu'il fasse exactement la même chose et rien d'autre (à part les fonctions que j'ai le droit de modifier) ? Parce que j'ai jamais fait de Lua.

Bonne question.
On te répond demain

Personnellement ça ne me dérange pas.

[matref]

Une autre solution serait d'apprendre le Lua en mode ninja. Mais bon.