Forces Especials

Hace unas cuantas semanas ya comenté por aquí de qué va el puzzle Eternity II. Finalmente me lo compré y verifiqué que efectivamente a mano es imposible de resolver. Me apunté a la lista de correo de yahoo relacionada y aprendí bastante con los mails que iba enviando la gente. Una de las cosas más interesantes que leí es que la teoría dice que se tardarían sobre 10^25 años en resolver el puzzle con backtracking (el algoritmo más básico, que va probando pieza a pieza, una por una, hasta encontrar la solución) en un PC típico a 3GHz. Si eso fuera cierto, emplear un millón de ordenadores para resolverlo, ¡¡¡ únicamente lo reduciría a 10^19 años !!! Eso creo que es bueno, no ganará el que mejor ordenador/rack-de-simulación tenga, sino el que mejor algoritmo consiga. La verdad es que me parecen demasiados años, pero he probado personalmente que en una semana no es posible resolverlo de esa forma. La clave está en el número de colores o lados distintos que tiene el puzzle. Como se puede observar en la siguiente gráfica (obtenida con mi super-algoritmo backtracking en C) el tiempo medio que se tarda en resolver el puzzle aumenta exponencialmente con dicho número de colores. Eternity II tiene únicamente 17 colores distintos, así que os podréis imaginar cuantos segundos saldrían en el eje vertical con mi algoritmo...

Debido al elevado coste computacional que requeriría resolver el puzzle con un algoritmo sencillo, se han creado diversas iniciativas que tratan de unir la capacidad de multiples ordenadores para tal fin (aunque como he comentado arriba, seguirá siendo igual de 'imposible'). Una de tales iniciativas es Eternity2.net y de ella quería hablar en este post, aunque me enrollado un poco para introduciros un poco en el tema. Dicha iniciativa se basa en el proyecto de computación distribuida BOINC. Para participar en Eternity2.net

• Te compras el puzzle
• Te bajas el programa BOINC (que no solo se usa para esto, sino también para proyectos de investigacion sobre temas tan variados como el cambio climático, el genoma humano o algoritmos de ajedrez) y lo instalas
• Introduces las piezas del puzzle codificadas en un txt según se explica en eternity2.net (la distribución de las piezas está prohibida y podría descalificarte del concurso)
  
• Pones el programa a ejecutarse cuando el PC esté inactivo.

Con ello, lo que consigues es que tu ordenador ejecute el algoritmo que ha programado el autor del sistema (Dave Clark), aunque no tengas ni idea de programar. La gracia está en que cada uno de los ordenadores adscrito al proyecto ejecutará una secuencia e búsqueda distinta para así entre todos intentar barrer el espectro de posibilidades cuanto antes. Lo malo es que el premio se dividiría en dos partes: por un lado 1000.000 de dolares para el tal Dave y otro 1000.000 de dólares para el dueño del PC que obtenga la solución.

Tengo mi PC ejecutando BOINC desde hace muucho tiempo y ha conseguido obtener una puntuación de 461 de 480 (con 480 consigues el premio gordo). Obtuve una puntuación de 459 en dos minutos, una de 460 en un par de dias y 461 en varias semanas. ¿Cuanto tardaré en llegar a 462? ¿Y a 480?

Bueno, pues parece que Dave también se está cansando del puzzle de los coj... y va a cerrar el chiringuito el próximo día 15 de diciembre. Ya veremos como lo resuelvo...