Author Topic: TI-Planet summer 2013 contest: the treasure of Knossos  (Read 2826 times)

0 Members and 1 Guest are viewing this topic.

Offline critor

  • Editor
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2079
  • Rating: +439/-13
    • View Profile
    • TI-Planet
TI-Planet summer 2013 contest: the treasure of Knossos
« on: August 16, 2013, 12:25:25 pm »
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%.



Expected production and rules:
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
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
Terms of participation:
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
Prizes to win:
  • 1se prize: 1 TI-Nspire CX CAS with its software and licence + 2 TI-Planet stickers
  • 2nd prize: 1 TI-84 Plus C Silver Edition (new color calculator for back to school 2013) with its USB charger + 2 TI-Planet stickers
  • 3rd prize: 1 TI-83 Plus.fr USB (equivalent to a TI-84 Plus Silver Edition) + 2 TI-Planet stickers
  • 4th prize: 1 TI-82 Stats.fr + 2 TI-Planet stickers
  • 5th prize: 1 Texas Instruments calculator poster (model of your choice, if available) + 2 TI-Planet stickers
  • 6th prize: 1 Texas Instruments USB pen + 2 TI-Planet stickers
  • 7th prize: 1 Texas Instruments notebook + 2 TI-Planet stickers
  • 8th prize: 4 TI-Planet stickers



Downloads:
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 ;)


Legal notices:
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
« Last Edit: August 16, 2013, 12:31:41 pm by critor »
TI-Planet co-admin.

Offline ElementCoder

  • LV7 Elite (Next: 700)
  • *******
  • Posts: 611
  • Rating: +42/-2
    • View Profile
Re: TI-Planet summer 2013 contest: the treasure of Knossos
« Reply #1 on: August 16, 2013, 01:49:25 pm »
* ElementCoder wants that 84PCSE
so I guess I'll have to give this contest a shot, no more excuses to skip Lua :p Best of luck to everyone entering the contest :)

Some people need a high five in the face... with a chair.
~EC

Offline TheNlightenedOne

  • LV6 Super Member (Next: 500)
  • ******
  • Posts: 427
  • Rating: +16/-1
    • View Profile
Re: TI-Planet summer 2013 contest: the treasure of Knossos
« Reply #2 on: August 16, 2013, 04:12:24 pm »
Hm, I might participate. Should be fun.
"Eris" (Ndless 3.1)
"Keto" (Ndless 3.1)
"Luna" (AMS 3.10, HW4)
"Aurora" (2.55MP)

Offline critor

  • Editor
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2079
  • Rating: +439/-13
    • View Profile
    • TI-Planet
Re: TI-Planet summer 2013 contest: the treasure of Knossos
« Reply #3 on: October 25, 2013, 05:07:36 pm »
2 entries received so far - so it's easy to win! :P

Remember the contest ends on the 3rd of november (next sunday) at midnight in Paris. ;)


The default AI provided with the TI-Nspire file performs around 30%.

Here is my own unreleased test-AI which performs at 88.9% after more than 132000 games.


I've developped it in just a day - it's not too late to submit something and to design a better AI ;)
« Last Edit: October 25, 2013, 05:29:52 pm by critor »
TI-Planet co-admin.