martes, 19 de abril de 2011

El Puzzle Interminable

Era verano del 2007 cuando navegando entre tetas y locuras por Yonkis me encontré una entrada que anunciaba un puzzle en el cual se podían ganar 2.000.000$ para la primera persona que lo resolviera. Como soy adicto a comerme el coco simplemente por entretenimiento y en esta ocasión había una suculenta recompensa de $2m realicé un repentino cambio de verbo pasando de mirar cocos a romper cocos en un periquete. Yonkis enlazaba a Microsiervos y fue allí donde obtuve la primera información sobre este puzzle cuyo nombre es Eternity II, un juego comercializado por Tomy.


Eternity II puzzle

Lanzamiento (Julio 2007)
Gracias a Microsiervos me puse al día en la historia de este puzzle enterándome de que ya había existido un puzzle precursor llamado Eternity del mismo creador Christopher Monckton. El puzzle Eternity II es tan fácil de entender como difícil de resolver, muy resumido consiste en un tablero de 16 por 16 casillas en las cuales hay que colocar las 256 piezas de forma que los 4 lados de cada una de las piezas coincidan en su dibujo con el de sus piezas adyacentes, en total son 480 lados a emparejar. -Sencillo, sólo algo más complejo que enlazar todas las piezas del domi...nó ¿no? -No.

Quedaba poco más de un mes para su lanzamiento, me puse a analizar la forma de resolverlo, deducir algunas estrategias probando una versión reducida del mismo que estaba disponible en la web oficial de Eternity II que pusieron a modo de Demo para mostrar cual sería el funcionamiento del puzzle. Tras unos cuantos folios con ideas y garabatos, unas cuantas horas de análisis, me puse a implementar un programa que intentase resolverlo. Unas semanas después ya salió a la venta y lo compré, he aquí una foto del susodicho.






Primer escrutinio (Diciembre 2008)
Durante ese año y como ya habían publicado desde sus inicios en las instrucciones del concurso, pusieron a la venta dos puzzles pista (Pista 1 y 2), los cuales eran del estilo Eternity II pero más pequeños y muchísimo más fáciles de resolver, una vez los resolvías y enviabas la solución, por cada puzzle pista te suministraban la posición correcta de una de las piezas del Eternity II.
Analicé la opción de desarrollar un programa multi-hilo (multithread) para dividir el trabajo y aprovechar el número de cores de los procesadores actuales, pero en este tipo de problemas no es fácil dividirlo ni tiene porqué ser más ventajoso, así que opté por un programa monohilo pero pensado para poder ejecutar varias instancias del mismo simultáneamente y configurados con distintas zonas de exploración. Al final de este apartado dejo una imagen de la última versión del software donde ha resuelto ambos puzzles pista de forma instantánea, uno en 0 y el otro en 32 milisegundos, a mano se pueden resolver en pocas horas.

A finales del año hubo el primer escrutinio y nadie había conseguido resolver Eternity II pero entregaron un premio (de consolación y motivación) no anunciado previamente de 10.000$ al que había enviado la solución con más lados emparejados.



Segundo escrutinio (Diciembre 2009)
Al no haber sido resuelto, el concurso se prorrogaba un año más. Lo había dejado bastante abandonado a mitad del año anterior (muchas horas ya dedicadas) pero al conocer que nadie lo había conseguido me animé a rehacer una nueva versión muy mejorada y mucho más configurable del programa. Buscando algún socio intenté motivar a gente para que se apuntase a resolverlo pero no pasaron de unas semanas de calentón y lo dejaron, eso los pocos que lo empezaron. Sólo mi hermano desde el principio se apuntó al reto conmigo, colaborando con ideas, testeando el software, y probando diferentes configuraciones.

Durante este año salieron a la venta los puzzle pista 3 y 4, los cuales ya no se distribuyeron a España, y tras varios intentos fallidos de adquirirlos contacté con un paisano vía el grupo Eternity 2 de Yahoo, un tipo majo que me envió por mail las soluciones, las cuales él tuvo que pagar por ellas y comprarlas en eBay (mercado negro) por la misma razón de no poder conseguir estos puzzles de forma legal. A partir de este momento disponía de 5 piezas en su posición correcta (4 de las pistas + 1 que venía impuesta en el juego) de las 256 piezas totales y el (d)efecto de pensar que era más fácil conseguirlo. Podéis ver aquí debajo el fichero de configuración del programa para haceros una idea de la cantidad y del tipo de parámetros que implementé.

En este segundo escrutinio a finales del 2009 tampoco nadie había conseguido resolverlo, esto suponía un año más, el último, de prórroga para conseguirlo.





Tercer escrutinio (Diciembre 2010)
Comparando mis resultados con otros pienso que desarrollé un buen software a pesar de que usé mucho de lo que no aprendí en la universidad, mucho de lo que no debe hacer un buen programador, y cualquier otra cosa necesaria para conseguir la máxima velocidad de cálculo. El algoritmo se basa en un backtracking iterativo sin usar recursividad; con el mayor número de información y casos posibles precalculados una única vez al iniciarse; eliminando al máximo llamadas a funciones; simplificando las comprobaciones a realizar en cada nodo; reduciendo el número de ramas a explorar y detectando rápidamente las ramas sin solución; en definitiva un intento de solución por fuerza bruta “inteligente”, reducida y optimizada. En la primera versión que ejecuté tenía un rendimiento de 12.000 piezas/segundo y en la última versión (muchas horas después) de más de 14.000.000 piezas/segundo. Un poco más abajo veréis una captura del programa intentando encontrar la solución para Eternity II después de tan sólo 2 minutos en funcionamiento.
Lo que sí está claro es que conseguí lo mismo que cualquier persona de este planeta que lo intentó resolver: no conseguirlo. A principios de este presente año después del último escrutinio anunciaron que el premio quedaba desierto y el concurso finalizado. La polémica de este eterno puzzle es que no han querido mostrar la solución.





Esta entrada es casi tan eterna como el puzzle en cuestión, pero mi capacidad de síntesis no ha podido comprimir más la historia interminable de Eternity II que duró más de 3 años y medio. Si algún valiente la ha leído entera creo que merece dejar constancia de ello en un comentario, para que pueda además ascender su rango en el blog de castigado a castigado Pro.

Ver todos los castigos sobre Miss Celánea
Twitter: @dPunisher1337

22 comentarios:

  1. Sólo puedo decir que el programa que hiciste hundía en la miseria en rendimiento a los de los demás que lo intentaron. Entre ellos yo!
    Great Job!

    Saludos!

    ResponderEliminar
  2. Bonito resumen de lo que yo vendría a llamar "el timo de la estampita" del siglo XXI jeje...Es broma, además ya sabes que yo no soy el más indicado para hablar después de mis fracasos buscando el santo grial de las quinielas de fútbol, de las casas de apuestas y últimamente de la inversión en bolsa.

    Tu y yo sabemos que lo importante es participar...por la recompensa en metálico.

    ResponderEliminar
  3. Lo he leido entero y me has dejado ojiplatico amigo. O_o

    ResponderEliminar
  4. Yo también lo he leido, aunque no estoy segura de haberlo entendido. Soy una auténtica masoca!!!
    Me acordaba de la historia y quería conocer el final.
    Que pena!!!! y que rabia no encontrar la solución, no?
    Ánimo con el Eternity III ;)

    ResponderEliminar
  5. Menudo parra estás hecho!!!!

    ¿¿¿Por que no hiciste un programa que calculara los números que van a salir en la primitiva???

    Es mucho mas fácil y puedes ganar mucho mas dinero.

    ¿No te equivocarías pensando que el Eternity tiene rodillos que giran ,verdad? xDDDD

    Un abrazo.

    ResponderEliminar
  6. Puni yo no me levanto de la cama para montar un friki puzzle por 2 milloncejos, casí que me quedo con las patas "pa arriba" rascandome la barriga, así te lo digo!!

    Tontas a parte eres en un ser especial, y friki como pocos...vamos como yo!

    Sigue castigandonos por favor que somos masocas totales.

    ResponderEliminar
  7. @Parasito Gracias! Aunque creo que había varios con buenos programas, mejores o peores es difícil saberlo. Lo más importante era intentarlo como hiciste tú, yo y muchos otros. Recuerdo que intentabas contactar conmigo por el puzzle y al final fue por Youtube. :)

    @Javier Los del primer Eternity también fueron unos timados pero se embolsaron el premio de $1m en 6 meses! Y por eso en este se les ha ido la mano en la complejidad. Al resto de tu comentario: LOOOOOL

    @Pi jajaja, también te he dejado casi sin palabras por el tamaño (no importa) del comment!? ;)

    @Lorena A ti te ofrecí ser socia y sólo se lo proponía a gente inteligente. Este peloteo es para que te animes si hay Eternity III!

    @KIT-KAT Con un software no puedo hacer lo que propones de la Primitiva, tendría que crear un hardware... llamado Máquina del tiempo y es todavía más complejo que el puzzle! ;)

    @JaviG jajaja por 2 milloncejos de nada que además eran en dólares y brutos para que mover un dedo no? Aprecio que aprecies los posts al precio recio... y buen apreciador será. buff

    ResponderEliminar
  8. Uff !!! Yo creo que eso no tenia solución pero aun así vaya currada para poder acabarlo
    , acabarías viendo piezas del puzzle por todos los sitios.

    ResponderEliminar
  9. Eres un fiera, por cierto.. no se si te lo habia dicho, eres un fiera jajaj

    el problema de no poder resolverlo con el programa que diseñaste cual es exactamente? que no tienes hardware suficiente para tanto calculo?

    ultimamente se usa un algoritmo (hay varios en realidad) para sacar por fuerza bruta el codigo de liberacion de la serie SL3 de nokia. Lo que se usa para ello es un quad crossfire de 5970 (ahora de 6990, pero va mal por los drivers) que a dia de hoy es lo mas potente para estos menesteres en relacion potencia/coste.

    A lo mejor podias adaptar el software para usar los procesadores graficos. incluso, es posible q nos llevemos una sorpresa...

    ResponderEliminar
  10. @Fernando Yo pienso que sí tiene solución de todas formas deberían haberla mostrado para despejar dudas. Jeje sí más de una vez tuve pesadillas con las piezas, y alguna vez levantarme de madrugada para escribir una idea.

    @Rafa El problema es que no tenía HW para resolverlo en un tiempo finito, ni seguramente con todos los ordenadores del planeta trabajando! Hubo un tío que hizo su soft para computación distribuida (repartía el premio al 50% con el ordenador que encontrase la solución) y nada, unos cuantos había conectados y no consiguió ni el récord de lados emparejados.

    Sobre el tema de usar las gráficas, sí se me pasó por la cabeza hacer una versión del programa para GPGPU pero por aquellos tiempos tanto Stream de ATI, como CUDA de nVIDIA estaban algo verdes, y OpenCL ni existía. Ahora hay APIs para facilitar la programación para GPGPU, antes era muy rudimentario y si sumamos que no tenía experiencia en esa programación lo descarté.

    De todas formas no tengo claro que el rendimiento final en GPGPU fuera muy bueno por el tipo de problema que es el puzzle. El uso óptimo de un algoritmo usando el HW gráfico son problemas muy paralelizables, divisibles en subproblemas independientes, y con estructuras de datos no muy complejas. El problema del Eternity II es opuesto a todo esto.

    ResponderEliminar
  11. no tengo ni idea del tema la verdad, no se que diferencia hay entre ambos procesadores (cpu y gpu)

    como ultimamente se hace esto q comentaba con las gpus por eso lo comente, pero veo q lo tienes superado :D

    yo de programacion lo justo, tengo un ciclo superior de diseño de aplicaciones.. vamos, que apenas se programar. Encima mi tiempo es limitadisimo y lo q me sobra lo empleo en otros asuntos :D

    ResponderEliminar
  12. Bueno ya imaginas que el diseño de ambos (CPU y GPU) es muy distinto por estar orientados a tareas muy distintas. De todas formas ya es correcto lo que dices de la tendencia de usar la GPU como procesador de uso general, y sobretodo para una serie de tareas específicas y cálculos es sin duda mucho más idónea y potente que la CPU; como por ejemplo el caso que has citado de fuerza bruta para reventar una clave.

    El tiempo muy limitado es un familiar mío también. ;)


    Por cierto quién quiera probar el puzzle en la web de Tomy sigue estando la Demo con el tablero de 4x4. Una vez pilléis como funciona no debería llevaros más de 3 minutos en resolverlo.
    http://www.tomy.co.uk/playzone/eternityii/

    ResponderEliminar
  13. Hi.He estado leyendo sobre el puzzle. En un segundo mi mente, ludópata de nacimiento, ha fotografíado tablero y piezas. Más de matemáticas que de máquinas empiezo a pensar en permutaciones, muchas, tantas como pasta me gustaría tener. A ver si me regalo tiempo y lo pruebo. Si no lo con/seguimos ¿tendremos premio de consolación?. Que ganas! Por cierto, gracias por tus desinteresados pero interesantes castigos. Ibas para teleformador...

    ResponderEliminar
  14. @Yoflu el concurso está cerrado pero el honor de resolverlo sigue abierto. Anímate con las permutaciones y perturbaciones mentales a ver si consigues algo. Los 2 milloncejos eran lo de menos lo interesante es el reto ¬¬
    Iba para teleformador y he llegado a túdeformador.

    ResponderEliminar
  15. Em trec el barret davant el repte que has portat a terme. Només en el planteig que has fet, ja proporciona un gran creixement intel·lectual i personal.

    Per la meva banda, jo tinc altres puzzles x resoldre...

    ResponderEliminar
  16. @Hanimal Gracias! La verdad que fue un reto muy interesante y divertido; siempre me quedará la espina de no haberlo resuelto pero el orgullo de haberlo intentado ;)
    Si sale el Eternity III anímate!

    ResponderEliminar
  17. Impresinante la capacidad de adaptacion que demostraste, lastima que no hallars la solución.
    Mira el lado bueno, hay que tener alguna derrota para saborear las victorias.

    ResponderEliminar
  18. tclever Fue una experiencia muy divertida, ordeñar las neuronas para intentar sacar lo máximo.

    El consuelo es que nadie en el mundo lo ha resuelto, todavía hay gente intentándolo, y yo sigo con ese gusanillo pero no gastaré más horas, ya fueron muchas. Si sale un Eternity III quizás vuelva a las andadas.

    Lo peor de no haberlo resuelto no son los 2 millones de dolares que no gané sino el orgullo, el orgullo de poder haberme jubilado joven. ;)

    ResponderEliminar
  19. Coincido en todo lo que dices, yo no entiendo de programas ni calculos, solo se que aun ahora enero 2012 sigo intentandolo, llego como muestra la imagen a 3 lineas del final y ahi quedo. Me llama mucho la atencion que no muestren la solucion final, eso no habla bien de todo esto no?. por lo pronto sigo intentandolo, y esperando el eternity III si es que lo habrá....

    ResponderEliminar
    Respuestas
    1. ¿Entonces lo estás intentando resolver a mano?
      Eres como yo de los que estás con el puzzle desde sus inicios o lo descubriste tiempo después?

      Yo le he dedicado muchas horas como intento explicar y transmitir en este post pero ya lo he abandonado de forma activa, aunque la espina clavada sigue allí. Cada vez que renuevo el PC pruebo ejecutar mi programa para resolver Eternity II, sólo para ver el aumento de velocidad de cálculo, en el reciente PC lo tengo pendiente, pero lo dejo sólo un rato como puro benchmark.

      Es muy sucio que no hayan mostrado la solución, a mí me ha enfadado bastante, pienso que sí tiene solución y no se trata de una estafa, pero aún así quiero verla, el concurso finalizó, y debían mostrarla. Nada de milongas que si sacarán una versión electrónica del mismo y por eso no la muestran, esto era un concurso y terminó, ahora deberían demostrar su solución.

      Tengo ganas de un posible Eternity III pero la forma en que han cerrado este me motivaría a no comprarles un sucesor.

      Eliminar
    2. Amigo, he echado una buena carcajada cuando leí "Tras unos cuantos folios con ideas y garabatos, unas cuantas horas de análisis, me puse a implementar un programa que intentase resolverlo". Esto fue leyendo me imaginé que comenzarías a resolverlo normalmente, y jamás se me pasé por la mente que harías un programa. :D. Cuando disponga del suficiente tiempo libre, echaré una ojeada más profunda al juego y veré que tal se me da intentar hacer un programa también... :D

      Eliminar
    3. Buenas Alfonso, me alegro que te hayas echado unas risas con la lectura eso siempre es positivo. ;)

      Inténtalo es un buen y divertido (sobre todo si eres masoca) reto, yo aunque dediqué excesivas horas para no conseguir resolverlo, me lo pasé muy bien intentándolo y no me arrepiento. Tenía aventuras que contar sobre el puzzle para llenar otro post. Si lo intentas me cuentas tus progresos.

      En parte quiero que salga un Eternity 3 y en parte no, porque si me pico serían demasiadas horas y por otro lado no me parece bien lo que hicieron con el final de Eternity 2.

      Eliminar