Page 1 of 3

Mise à jour interface pour gagner le trésor du Wumpus (v3)

Unread postPosted: 01 Nov 2013, 02:58
by critor
Plus que quelques jours pour remporter le trésor du Wumpus avec entre autres une TI-Nspire CX CAS compatible Ndless, une TI-84 Plus C Silver Edition couleur, et une TI-83 Plus.fr USB.
2627 2572 2573 2571 637 2343 2373


L'interface avec laquelle vous deviez travailler pour développer et rendre votre IA (Intelligence Artificielle) vient d'être mise à jour et est téléchargeable ci-dessous.

Il y a eu d'une part correction d'un bug qui faisait que les salles piégées n'étaient pas signalées dans certains cas. Un grand merci à Extra44 et oakwood pour le signalement, l'explication et la proposition de correction! :bj:
Image




D'autre part maintenant que votre IA (intelligence artificielle) ne risque plus de tomber par erreur dans une oubliette non signalée, nous avons pu remarquer que certaines des IA soumises se mettaient parfois à errer éternellement sans but dans le labygraphe, ne terminant donc jamais la partie.

Cela arrive en effet lorsqu'il n'y a pas de solution au problème. L'IA qui finit par déduire que la situation est sans espoir n'a que deux solutions:
  • se suicider
  • continuer d'errer éternellement dans le labyrinthe

Mais comment est-ce possible alors que l'énoncé du concours vous garantit qu'il y a toujours une solution au problème?

Regardez un petit peu l'exemple ci-contre.
A partir de l'entrée du labygraphe (salle n°1) il est bien possible de rallier la salle du trésor (salle n°8), mais uniquement à condition de réussir à passer la salle du Wumpus (salle n°10).
  • Partant de la salle n°1, notre IA n'a donc que le choix de rallier la seule salle voisine, la n°9.
  • Dès son arrivée en salle n°9, l'IA sent un Wumpus. Le monstre se trouve donc dans une salle voisine non explorée, ce qui ne laisse le choix qu'entre les n°5, 7 et 10. Comme il n'y a rien d'autre à explorer sur ce labygraphe il n'y a pas le choix: il va falloir se confronter au Wumpus.
  • L'IA peut alors soit décider de la jouer quitte ou double, et de visiter au hasard l'une des salles n°5, 7 ou 10. Mais elle peut aussi plus sagement tirer son unique flèche dans une des salles n°5, 7 ou 10 pour tenter de tuer le Wumpus, ou à défaut d'en déduire sa position. Supposons que l'IA tire au hasard dans la salle n°7.
  • L'IA se rend alors compte que ça sent toujours autant le Wumpus, que ce dernier est donc toujours vivant et ne se trouvait donc pas en salle n°7. Il est donc soit dans la salle n°5, soit dans la salle n°10. Même situation à nouveau: il n'y a toujours pas de salle sûre à explorer.
  • Sauf que là, l'IA n'a plus sa flèche. La seule possibilité qui lui reste est d'aller dans une des salles n°5 ou 10. Supposons que l'IA aille au hasard dans la salle n°5.
  • L'IA se rend compte qu'elle est toujours vivante et déduit donc que le Wumpus est en salle n°10.
Sauf que sur cet exemple de labygraphe, avoir déduit la position du Wumpus ne nous aidera pas à gagner, puisque nous n'avons plus notre flèche pour le tuer, et qu'il n'y a pas d'autre chemin permettant de le contourner pour se rendre dans la salle du trésor.
L'IA a-t-elle donc eu tort? Non, elle a parfaitement bien raisonné sur cet exemple - c'est exactement ce qu'il fallait faire.

La situation est donc désespérée. Et ce cas n'ayant pas été mentionné au règlement, vous n'avez ni obligation ni interdiction. Vous avez aussi bien le droit de suicider votre IA que de la faire errer éternellement dans les salles sûres du labygraphe, et nous ne devons pas faire de différence dans l'évaluation.

L'IA ci-dessus a notamment fait le choix d'errer éternellement à travers les mêmes cinq corridors et six salles du labygraphe, et en est déjà à son 111ème déplacement.



Mais pour évaluer votre IA, il nous faudra réaliser un grand nombre de parties, et donc pouvoir passer à la partie suivante.
  • D'une part, nous rajoutons donc une touche 'f' qui permet de déclarer forfait et de passer à la partie suivante si vous estimez que votre IA est coincée.
  • D'autre part, pour avoir des statistiques sur un grand nombre de parties en évitant de devoir venir vérifier toutes les deux minutes si votre IA ne s'est pas coincée, nous instaurons un nombre de coups maximal par partie. Rien d'effrayant: nous l'avons fixé pour le moment à n*d, soit 200 coups sur l'exemple ci-dessus avec n=10 et d=20. C'est très largement plus qu'il n'en faut pour explorer et ressortir d'un tel labygraphe. En effet, cela correspond au nombre de coups théoriques pas juste pour visiter toutes les salles, mais pour les visiter de toutes les façons possibles en empruntant tous les corridors deux fois (aller et retour). Comme en pratique il n'est jamais nécessaire d'emprunter tous les corridors sauf si le labygraphe se résume à une unique ligne brisée avec le trésor au bout, cela ne gênera jamais votre IA, tout en permettant à notre interface de passer à la partie suivante après quelques secondes d'errements sans fin.
Dans les deux cas, cela est compté par l'interface exactement comme une partie perdue. Elle ne fait aucune différence et conformément au règlement il n'y a donc strictement aucune autre pénalité, surtout que le nombre de coups moyen n'est calculé qu'à partir des parties gagnantes. :bj:



Bonne chance! ;)




Lien : Présentation et énoncé complets du concours

Téléchargements:
La nouvelle version du fichier TI-Nspire à modifier/compléter et à rendre:
LabyGraph - Wumpus

Pour éditer le script Lua et le compléter avec vos fonctions:
Logiciel TI-Nspire 3.2 enseignant (pour PC - gratuit pendant 90 jours)
Logiciel TI-Nspire 3.2 enseignant (pour Mac - gratuit pendant 90 jours)
Logiciel TI-Nspire 3.2 étudiant (pour PC - gratuit pendant 30 jours)
Logiciel TI-Nspire 3.2 étudiant (pour Mac - gratuit pendant 30 jours)

Re: Mise à jour interface pour gagner le trésor du Wumpus (v

Unread postPosted: 01 Nov 2013, 07:41
by Extra44
Bonjour,

Suite à cela (topic) :
critor wrote:Le n, est normalement passé en paramètre de tes fonctions Lua et tu peux donc le mémoriser.

Que voudrais-tu faire avec 'd' et 'p' par contre ?


Maintenant qu'on connait n mais pas d, et on pourrait en avoir besoin pour savoir si on peut continuer à explorer (maxcoups = d*n), ou pour voir si on tente les salles/"suicide"...

Le question se repose : Pourrait-on accéder à la variable 'd' (ou a maxcoups) ... ??

Extra44

PS : @critor : peut-on modifier notre IA et te renvoyer une nouvelle version de notre tns avec une nouvelle IA suite à cette news..

Re: Mise à jour interface pour gagner le trésor du Wumpus (v

Unread postPosted: 01 Nov 2013, 08:24
by Lionel Debroux
PS : @critor : peut-on modifier notre IA et te renvoyer une nouvelle version de notre tns avec une nouvelle IA suite à cette news..

Bien sûr, ceux qui ont déjà envoyé une ou plusieurs versions peuvent envoyer une ou plusieurs (enfin, pas trop quand même ^^) nouvelles versions d'ici dimanche soir :)

Re: Mise à jour interface pour gagner le trésor du Wumpus (v

Unread postPosted: 01 Nov 2013, 11:27
by critor
Extra44 wrote:Bonjour,

Suite à cela (topic) :
critor wrote:Le n, est normalement passé en paramètre de tes fonctions Lua et tu peux donc le mémoriser.

Que voudrais-tu faire avec 'd' et 'p' par contre ?


Maintenant qu'on connait n mais pas d, et on pourrait en avoir besoin pour savoir si on peut continuer à explorer (maxcoups = d*n), ou pour voir si on tente les salles/"suicide"...

Le question se repose : Pourrait-on accéder à la variable 'd' (ou a maxcoups) ... ??


Non, votre IA n'a pas à connaître d ou maxcoups, ni à tenter de les récupérer puisque ce sont des variables de l'interface.

maxcoups est juste là pour débloquer les IA coincées.
Aucune IA n'a besoin de 200 coups pour résoudre un labygraphe 10/20/20.

Pour savoir si il faut continuer à explorer c'est autrement qu'il faut s'y prendre.
J'ai bien dit que le problème de blocage arrivait avec certaines IA, et uniquement lorsque la situation devenait sans espoir. C'est donc cet espoir qui est à coder.

Extra44 wrote:PS : @critor : peut-on modifier notre IA et te renvoyer une nouvelle version de notre tns avec une nouvelle IA suite à cette news..


Il n'y a normalement pas besoin de modifier votre IA, puisque comme promis au règlement, la modification de l'interface ne perturbe pas son comportement, bien au contraire:
  • votre IA évite maintenant certaines salles piégées qui n'étaient pas annoncées
  • certaines versions d'IA soumises peuvent se bloquer (ce n'est pas le cas de toutes les IA soumises), mais comme expliqué nous avons résolu le problème sans les pénaliser - le blocage étant tout simplement considéré comme une partie perdue

Conformément au règlement, vous pouvez continuer de soumettre ou mettre à jour votre participation par simple email, seul le dernier email reçu étant pris en compte.
Vous êtes libres de continuer de soumettre votre code dans les interfaces v1 ou v2 - de toutes façons nous en extrairons le code de l'IA et le copierons dans une interface commune qui devrait à ce jour être la v3.

Re: Mise à jour interface pour gagner le trésor du Wumpus (v

Unread postPosted: 01 Nov 2013, 12:06
by AnToX98
J'avais vu aussi le bug du piège non détécté mais je ne savais pas si c'était vraiment un bug.

Re: Mise à jour interface pour gagner le trésor du Wumpus (v

Unread postPosted: 01 Nov 2013, 15:02
by mdr1
À propos, l'ordre des lots correspond-il obligatoirement au classement, ou bien si on est devant, on peut décider de choisir son lot avant le suivant ? Je pense en effet qu'il serait par exemple envisageable de préférer le 6e au 5e prix (et ça aurait tendance à être mon cas).

Re: Mise à jour interface pour gagner le trésor du Wumpus (v

Unread postPosted: 01 Nov 2013, 16:07
by critor
Pour ce concours il s'agit bien d'un classement.

Re: Mise à jour interface pour gagner le trésor du Wumpus (v

Unread postPosted: 01 Nov 2013, 16:11
by mdr1
C'est-à-dire que pour avoir un autre lot, il faut faire exprès de rendre son IA moins bonne ?

Re: Mise à jour interface pour gagner le trésor du Wumpus (v

Unread postPosted: 01 Nov 2013, 16:14
by critor
Tu peux voir les choses comme ça, mais c'est un pari risqué.

Re: Mise à jour interface pour gagner le trésor du Wumpus (v

Unread postPosted: 01 Nov 2013, 16:18
by mdr1
Franchement, je ne comprends pas très bien pour quelle raison ça fonctionne comme cela. Il me paraît évident que quelqu'un qui a de meilleurs résultats puisse choisir en premier le lot qu'il préfère, plutôt qu'il envie le lot de quelqu'un qui a fourni une IA avec de moins bons résultats. Donc bien que le pari soit risqué, je pense effectivement le prendre.