Investigadores de la Universidad de San Andrés han lanzado un reto a los programadores, para hallar una solución a un “sencillo” problema de ajedrez que podría, de hecho, tomar miles de años poder resolver. Como premio, quien resuelva el acertijo recibirá 1 millón de dólares.
El profesor de ciencias de la computación, Ian Gent y sus colegas en la mencionada universidad, creen que cualquier programa capaz de resolver el famosos “acertijo de las reinas” eficientemente podría ser capaz de resolver tareas que se consideran hoy día imposibles, como descifrar la seguridad más sólida en internet.
En un artículo publicado en el Journal of Artificial Intelligence Research, el equipo concluye que la recompensa por hacer este programa podría ser inmensa, no sólo en términos financieros, sino con firmas que estarían dispuestas a pagar por esta solución tecnológica. Esto -desde luego- aparte del millón de dólares ofrecido por el Clay Mathematics Institute in America.
El problema de las reinas parece ser se origino en 1850, en donde se reta a un jugador a colocar 8 reinas en un tablero de ajedrez estándar, en donde ninguna reina ataque a otras. Esto significa que no puede haber dos o más reinas en la misma fila o columna o diagonal. La solución completa contiene, a todo esto, 92 posibles soluciones (23 realmente, porque las restantes se obtienen de imágenes especulares). Aunque el problema lo puede resolver un ser humano casi a prueba y error, una vez que se hace crecer el tablero de ajedrez, no hay computadora que pueda resolverlo, según indican los investigadores.
El profesor Gent y colegas, entre los que se encuentran el Dr. Peter Nightingale el Dr. Christopher Jefferson, todos de la escuela de ciencias de la computación en la universidad, fueron los primeros en ser atraídos por el acertijo después de que un amigo retó al profesor Gent a resolverlo en Facebook.
Cuando el tablero de ajedrez alcanza 1000 x 1000 casillas, los programas no pueden lidiar con el número de opciones que se les presentan y caen en un ciclo de cálculos del cual no parecen poder salir, dicen los investigadores. Gent dice que: “si usted puede escribir un programa de computadora que pueda resolver este problema realmente rápido, podría ser adaptado para poder resolver muchos de los problemas importantes que nos afectan diariamente”. Y agrega: “Esto incluye tareas triviales como trabajar con un grupo de personas en Facebook aunque no se conozcan o algunos más importantes, como romper los códigos que mantienen nuestras transacciones seguras”, indicó el investigador.
La razón por la cual estos problemas son tan difíciles para las computadoras, es que hay demasiadas opciones a considerar, las cuales pueden tomar años. Esto es debido al proceso de “backtracking” -un algoritmo usado en programación en donde cada opción posible es considerada y en donde entonces “se va hacia atrás” si falla algo hasta que se da con la solución correcta. En otras palabras, mediante el backtrack se analiza todo el espacio de búsqueda sin excepciones y eso puede llevar mucho, pero mucho tiempo.
El Dr. Nightingale dijo: “Sin embargo, todo esto es teórico. En la práctica nadie ha llegado a escribir un programa que pueda resolver este problema rápidamente. Sin embargo, lo que nuestra investigación ha mostrado es que, para todos los propósitos prácticos, se puede hacer un programa de esta naturaleza”.
El Dr. Jefferson añade: “Hay un millón de dólares de premio para aquel que pueda probar si el problema de las reinas se puede resolver rápidamente o no. La recompensa es alta”.
Referencias: Phys.org