Resolver con ordenador un puzle pasado por una trituradora de documentos tiene premio

• El reto ha sido lanzado por el Departamento de Defensa norteamericano
• Busca avances en inteligencia artificial y reconocimiento de caracteres
• Hay que combinar la potencia de los ordenadores con ayuda humana
• El premio: 50.000 dólares

Una de las páginas trituradas que forman parte del reto lanzado por DARPA

Los aficionados a los puzles y a los retos informáticos están de enhorabuena: DARPA, la agencia de investigación del departamento de Defensa norteamericano, ha puesto en marcha un nuevo concurso en el que los más ingeniosos pueden ganar hasta 50.000 dólares.

La prueba a superar consiste en recomponer un gigantesco puzle en el que las piezas son trocitos de papel manuscrito pasados por una máquina trituradora de documentos. Toda la información está en una web creada a tal efecto: DARPA Shredder Challenge .

Este tipo de concursos o retos son habituales en diversos entornos, especialmente de investigación, para comprobar el avance de ciertas tecnologías y del ingenio humano cuando realmente se exprime al máximo. La zanahoria es un jugoso premio, en este caso más de 35.000 euros.

En el pasado ha habido pruebas similares para comprobar si alguien podía crear un coche que condujera de forma autónoma o incluso aviones y naves especiales.

Uno de los más curiosos fue localizar la posición precisa de diez grandes globos rojos situados en diez ubicaciones fijas repartidas por todo el país , algo técnicamente complicado pero que se resolvió con ingenio y la ayuda de las redes sociales. Pruebas como la del puzle de la trituradora también ha habido algunas.

La complicación del asunto de los documentos pasados por la destructora de documentos es que se trata de una forma de muy baja tecnología de conseguir una destrucción muy efectiva: incluso con las largas tiras de algunas máquinas es muy difícil reconocer y recomponer los originales cuando se han entremezclado lo suficiente; cuando se trituran en trozos más pequeños, como en este reto, se considera una misión casi imposible.

Pero parece ser que el Departamento de Defensa se encuentra con muchos de estos documentos en sus incursiones militares y no les vendría mal una ayuda, de ahí que hayan lanzado abiertamente el problema al público.

“La tarea crece exponencialmente a medida que aumenta el número de "piezas" a encajar“

Aunque un ordenador pueda comprobar millones de combinaciones de piezas distintas por segundo, la tarea crece exponencialmente a medida que aumenta el número de "piezas" a encajar. Y, por otro lado, no se trata de piezas fáciles de encajar: todas son muy parecidas, sus formas deben ser examinadas por sistemas de reconocimiento de imágenes y las tonalidades de las diversas zonas e incluso efectos como el corrimiento de la tinta pueden dar lugar a confusión.

Algunos de los puzles están en un solo color, otros en varios y la letra escrita a mano no es fácil de reconocer incluso por los mejores OCR (sistemas de reconocimiento óptico de caracteres).

Los expertos creen que lo mejor es combinar el trabajo de fuerza bruta de las máquinas con la ayuda e interpretación inteligente de un ser humano, que aproxime la solución, pero no está claro cuál es el mejor camino.

El reto del DARPA está dividido en cinco puzles de diversos tamaños, descargables desde su web , divididos en varias páginas: van desde unos pocos cientos de piezas a otros con miles de trocitos.

Aunque las imágenes están nítidamente escaneadas, al igual que si se tratara de un "escenario real" en algunos puede que falten piezas, estén mal recortadas o incluso que sobren trocitos que correspondan a otras páginas. Los equipos participantes van ganando puntos a medida que resuelven diversos pasos del puzle.

Estrategias colaborativas

Otra cuestión es que no está muy claro para los investigadores si para resolver un puzle de este tipo hay alguna estrategia colaborativa óptima que permite ganar tiempo dividiendo la tarea en otras menores o en grupos de trabajo.

Algunos equipos están probando a usar técnicas de computación distribuida, en las que las tareas de resolución del puzle se reparten entre cientos o miles de participantes que ayudan con la potencia de sus ordenadores desde casa, a través de Internet. Curiosamente, y al igual que en una situación real, ya se han dado caso de hackeos o intentos de manipulación entre unos equipos y otros, para poner trabas a la competencia.

“Grupos de trabajo colaboran en conjunto para desenmarañar los puzles“

Uno de los equipos participantes es el UCSD DARPA Shredder Challenge Team , en el que trabaja el investigador español Manuel Cebrián. Desde la Universidad de California en San Diego (UCSD) emplean algoritmos de visión artificial y de trabajo en crowdsourcing (grandes grupos de voluntarios) con el objetivo de desenmarañar los puzles, de los que ya han resuelto tres de los cinco.

La idea del equipo de la UCSD es repartir los 50.000 dólares del premio entre todas aquellas personas que hayan participado. Un reparto que también puede ser todo un reto en sí, debido a la gran cantidad de gente que se ha apuntado y al diverso grado de participación de cada "criptólogo aficionado".