Instruction to the Travelling Snakesman Test Version 3 (as of June, 17, 2018)
This page is current as of June, 17, 12:15 CEST

This game uses an iML algorithm for computations in the background. We try to measure, if human interaction with this algorithm leads to better solutions than the algorithm running automatically without any interaction.

  • 0) Click on the link below
  • 1) Enter a name (deactivate music)
  • 2) Play all three levels, start with level 1 (1 = easy, 3=difficult)
  • 3) Press “Play!” With your mouse/touch you direct the snake and your goal is to eat all apples as fast as possible!

Test Version please use this link:

https://iml.hci-kdd.org/TravellingSnakesmanWS

In the main menu you can open the highscores, open a help window, quit the game and of course: play the game! Before you can hit the “play” button you need to enter a name and select the level, with which one you want to start. After you have started the game you can control a snake with simply clicking or tapping on the screen.

The goal is to eat all apples as fast as possible!

The time you needed for eating all the apples in a certain level shows up in the highscores!

On the top left you can see a red, yellow or green square. This square notifies, if your contribution is actually better than the algorithm computation itself (see next section). If you finish a level, you can start the next one or go back to the main menu! With the back or ESC button you have also the opportunity to pause the game. The highscore is showing the best scores of all time, the week and the day.

The algorithm background

Immediately after the gameplay starts the algorithm (MinMaxAntSystem algorithm) runs “number of apples * 5” iterations. After the computation you have full control over a snake. Every time you eat an apple the previous mentioned algorithm runs 5 iterations, with doubled amount of pheromones on the traveled edge. So if you travel from one apple to another, your choice will be considered for the algorithm computations, we can say, the player interacts with the algorithm in the background and has an influence of the outcome.

So f.e. after you have eaten the third apple the algorithm has computed 15 iterations, with a higher chance to choose edges you have traveled on eating those apples.

After you have eaten all the apples we save following scores on our server:

  • the first algorithm computation (without human help)
  • the best route of the algorithm computation
  • the best iteration of the algorithm computation
  • the second algorithm computation (algorithm with human help)
  • the best route of the algorithm + human computation
  • the best iteration of the algorithm + human help computation
  • the time of the gameplay (for the highscores)
  • the name of the player (for the highscores)
  • all pheromones at any time (work in progress)

The scientific goal of this game is solving the question “Do we have a better algorithm performance with human interaction?”, which leads to the main hypothesis H1: “Human interaction enhances the overall performance of the automatic algorithm”.

Links

Algorithm description: https://goo.gl/Ajz9pH

Travelling Salesman problem: https://goo.gl/HpbVEN

Browser Game: http://iml.hci-kdd.org/TravellingSnakesman

Android Game: https://goo.gl/oCbQwV

Scientific Background: Interactive Machine Learning (iML) can be defined as “algorithms that can interact with agents and can optimize their learning behavior through these interactions, where the agents can also be human [1], [2].” A “human-in-the-loop” can be beneficial in solving computationally hard problems [3]. This is due to the fact that humans have excellent problem solving abilities, intuition and instantaneous gut-feeling, which can be helpful to reduce a huge search space through heuristic selection of samples. Consequently, a human in the loop can be help to contribute to solve NP-hard problems – at least in the lower dimensions.

Experiment: In this two on-line games we evaluate the effectiveness of the iML-”human-in-the-loop” approach by enabling a human to directly manipulating and interacting with an algorithm. For this purpose, we selected the Ant Colony Optimization (ACO) framework, and apply it on the Traveling Salesman Problem (TSP) [4], [5] which is an NP-complete problem and is of highest importance in solving many practical problems in health informatics, e.g. in the study of proteins etc.

References:

[1] Holzinger, A. 2016. Interactive Machine Learning for Health Informatics: When do we need the human-in-the-loop? Springer Brain Informatics (BRIN), 3, (2), 119-131, doi:10.1007/s40708-016-0042-6.

[2] Holzinger, A. 2016. Interactive Machine Learning (iML). Informatik Spektrum, 39, (1), 64-68, doi:10.1007/s00287-015-0941-6.

[3] Dossier: Interactive Machine Learning for Health Informatics

[4] Wikipedia: Travelling salesman problem (last visited: 18.4.2018)

[5] Papadimitriou, C.H. 1977. The Euclidean travelling salesman problem is NP-complete. Theoretical computer science, 4, (3), 237-244, doi:10.1016/0304-3975(77)90012-3.