Un millón de dólares para quien logre resolver el «‘Rompecabeza de las reinas»
Infovzla.net
El profesor de Ciencias de la Computación Ian Gent y sus colegas de la Universidad de St. Andrews creen que cualquier programa capaz de resolver eficazmente el famoso ‘Rompecabezas de las Reínas’ sería tan poderoso que sería capaz de resolver tareas actualmente consideradas imposibles, como descifrar las mayores medidas de seguridad en Internet.
En un artículo publicado en Journal of Artificial Intelligence Research, el equipo concluye que las recompensas para ser cosechadas por este programa serían inmensas, no sólo en términos financieros con empresas que se apresuren a utilizarlo para ofrecer soluciones tecnológicas, sino también por el premio de un millón de dólares ofrecido por el Clay Mathematics Institute en América.
Diseñado originalmente en 1850, el ‘Queens Puzzle’ desafió originalmente a un jugador a colocar ocho reinas en un tablero de ajedrez estándar para que ninguna reina se atacara entre sí. Esto significa poner una reina en cada fila, de modo que no hay dos reinas en la misma columna, y no hay dos reinas en la misma diagonal. Aunque el problema original ha sido resuelto por los seres humanos, una vez que el tablero de ajedrez aumenta a un tamaño grande ningún programa de ordenador puede solucionarlo.
El profesor Gent y sus colegas, el investigador Peter Nightingale y el lector Dr. Christopher Jefferson, todos de la Escuela de Ciencias de la Computación de la Universidad, se sintieron intrigados por el rompecabezas después de que un amigo desafió al profesor Gent a resolverlo en Facebook.
El equipo encontró que una vez que el tablero de ajedrez alcanzó 1.000 por 1.000 cuadrados, los progamas de ordenador ya no podían hacer frente a la gran cantidad de opciones y se hundieron en una lucha potencialmente eterna similar al superordenador ficticio Deep Thought en la obra Hitchhiker’s Guide to the Galaxy de Douglas Adams, que tardó siete millones y medio de años en dar una respuesta al significado de todo.
El profesor Gent dijo en un comunicado: “Si pudieras escribir un programa de ordenador que pudiera resolver el problema realmente rápido, podrías adaptarlo para resolver muchos de los problemas más importantes que nos afectan todos a diario”.
“Esto incluye desafíos triviales como trabajar con el grupo más grande de tus amigos de Facebook que no se conocen, o muy importantes como romper los códigos que mantienen todas nuestras transacciones en línea seguras”.
La razón de que estos problemas sean tan difíciles para los programas de computadora, es que hay tantas opciones a considerar que puede tomar muchos años. Esto se debe a un proceso de “backtracking” – un algoritmo utilizado en la programación donde se considera cada opción posible y luego se “retrocede” hasta que se encuentra la solución correcta.
Nightingale dijo: “Sin embargo, todo esto es teórico. En la práctica, nadie ha llegado a escribir un programa que pueda resolver el problema rápidamente. En consecuencia, lo que nuestra investigación ha demostrado es que – a todos los efectos prácticos – no puede hacerse”.
Jefferson agregó: “Hay un premio de un millón de dólares para cualquier persona que pueda probar si el Problema de las Ocho Reinas puede ser resuelto rápidamente, por lo que las recompensas son altas”.
El ajedrez ha sido durante mucho tiempo la fuente de rompecabezas como la tradicional fábula del sirviente que, cuando le pidieron que escogiera una recompensa por su rey, pidió que un grano de arroz fuera colocado en el primer cuadrado de un tablero de ajedrez estándar de 8×8, doblándolo sucesivamente en cada cuadro hasta que se encontró que no había bastante arroz en el mundo entero.
La fábula indica los grandes números involucrados cuando se usa un tablero de ajedrez de tamaño estándar. Cuando el tamaño del tablero aumenta, los números se vuelven enormes.
Sin embargo, aunque el premio es indudablemente jugoso, es posible que ese millón de dólares espere indefinidamente sin ser adoptado. La razón de que estos problemas sean tan difíciles para los programas de computadora es que hay tantas opciones a considerar que generar una respuesta puede tardar muchos años. Esto se debe a un proceso de vuelta atrás (en inglés backtracking), un algoritmo utilizado en la programación donde se considera cada opción posible y luego se retrocede hasta que se encuentra la solución correcta.
