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...

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.

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.
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: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%.



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.

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.

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.
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.

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

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): 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.

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

• "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...

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"

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

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

You'll have to send an email to [email protected] 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

• 1^se prize: 1 TI-Nspire CX CAS with its software and licence + 2 TI-Planet stickers
  
• 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^rd prize: 1 TI-83 Plus.fr USB (equivalent to a TI-84 Plus Silver Edition) + 2 TI-Planet stickers
  
• 4^th prize: 1 TI-82 Stats.fr + 2 TI-Planet stickers
  
• 5^th prize: 1 Texas Instruments calculator poster (model of your choice, if available) + 2 TI-Planet stickers
  
• 6^th prize: 1 Texas Instruments USB pen + 2 TI-Planet stickers
  
• 7^th prize: 1 Texas Instruments notebook + 2 TI-Planet stickers
  
• 8^th prize: 4 TI-Planet stickers

The TI-Nspire file to modify for the contest:
LabyGraph - Wumpus
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.

In order to edit the Lua script and complete it with your functions :
TI-Nspire 3.2 teacher software (for PC - 90 days trial)
TI-Nspire 3.2 teacher software (for Mac - 90 days trial)
TI-Nspire 3.2 student software (for PC - 30 days trial)
TI-Nspire 3.2 student software (for Mac - 30 days trial)
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 ;)


The full rules are available here: http://tiplanet.org/forum/archives_voir.php?id=12093 or on UPECS
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.


TI-Planet contest topic:
http://tiplanet.org/forum/viewtopic.php?t=12532&lang=en

Hm, I might participate. Should be fun.