Skip to content

Shredder Challenge : un puzzle tellement compliqué…

  • by

Fans de puzzle ? La défense américaine propose de gagner jusque 50 000$ pour trouver une méthode permettant de reconstituer les puzzles les plus compliqués du monde : des documents passés dans une déchiqueteuse. L’Université de Californie à San Diego a alors développé un programme mettant ainsi à profit le crowdsourcing pour le renseignement militaire.

Un puzzle bien particulier

Wikipedia prétend qu’un document découpé en bandelettes de 4 à 5 mm ne prend que quelques minutes à reconstituer. Mais la reconstitution des documents récupérés chez l’ennemi en temps de guerre paraît autrement plus complexe, au point que l’armée américaine n’a pas réussi à mettre au point de programme pour les reconstituer.

La Défense américaine, par l’intermédiaire de la DARPA, a donc lancé un concours pour trouver une méthode de reconstitution de ces documents déchiquetés proche des concours de challenge.gov dont nous vous parlions il y a quelques temps. Pour cela elle met à disposition de tout le monde 5 puzzles : les deux premiers avec 224 et 373 pièces peuvent être reconstitués par un seul individu, mais les suivant en ont beaucoup plus pour finir avec le puzzle 5 à six milles pièces. 5 000 équipes se sont mises en compétition pour ce challenge, mais seules 16 ont fini le premier.

L’équipe du Dr. Manuel Cebrian de l’Université de Californie à San Diego a décidé de se faire aider de l’ensemble des internautes pour y trouver la solution.

L’équipe de l’USCD pour le Shredder Challenge

L’USCD cheche donc la réponse donc au concours de la DARPA, mais pas toute seule ! Elle a mis au point un programme permettant à n’importe qui de prendre part à cette résolution. En étudiant les méthodes de résolution des participants, elle espère mettre au point un algorithme qui permettra d’interragir avec le participant pour reconstituer ces documents plus rapidement. Cet algorithme se perfectionnera avec les actions des participants de façon à rendre automatique de plus en plus de tâches.

Le programme développé fait en sorte que les internautes connectés simultanément travaillent tous sur exactement le même puzzle, les déplacements faits par l’un deux sont visibles des autres.

Soucieux de mettre à contribution le plus grand nombre possible de personnes, le programme de l’USCD insiste sur la viralisation : l’équipe qui a développé le programme ne touchera pas un cent des 50 000$ offerts par la DARPA. Si l’USCD remporte ce concours, la somme sera intégralement redistribuée entre les participants : toute pièce qui a trouvé sa place dans le puzzle rapportera 1$ à celui qui l’aura bien placé, la personne qui aura recruté cette personne touchera 0,50$, et la personne qui a recruté cette seconde personne touchera à 0,25$…

Nous sommes donc là face à deux niveaux de crowdsourcing : l’un compétitif de la part de la DARPA où les équipes sont en compétition pour remporter un prix, et un second entièrement collaboratif et visant la viralisation et qui redistribuera le prix si l’équipe remporte le premier concours.

Le Dr. Cebrian avait déjà remporté un des concours de la DARPA où il s’agissait de trouver 10 énormes ballons rouges dispersés à travers les Etats-Unis avec des méthodes similaires de viralisation et de crowdsourcing. Reste à voir si les mécaniques mises en place dans ces contextes peuvent être reconstituées par l’informatique. Une chose est sûre, les gamers sont capables de grandes choses, ils ont récemment aidé à la reconstitution d’une molécule entrant en jeu dans le lutte contre le SIDA.