Candy Crush Saga y el Problema P=NP

Esta entrada es una inocentada.

 Hace 4 años, un grupo de matemáticos del King College de Londres se propusieron atacar uno de los problemas más interesantes de la Matemática moderna y por el que podrían ganar, si lo resolvían, 1 millón de dólares (y, probablemente, la Medalla Fields -al menos para los menores de 40 años del grupo-).

Hace poco más de 2 años, lanzaron una beta de una aplicación que les ayudaría a resolver dicho problema. Y según han confirmado hoy a través de la IMU, parece que el trabajo comienza a dar sus frutos

El pasado 12 de noviembre se cumplió 1 año desde que saliera a los Markets de todas las plataformas móviles uno de los juegos más adictivos de las últimas décadas, un juego que, en  muchos aspectos, recuerda al famoso TETRIS. Me refiero al Candy Crush Saga.

¿Y qué tiene que ver este juego con la King College de Londres? Pues muy sencillo. ¿Cómo se llama la empresa que lanza este juego?
Sí, en efecto: KING. Y no es casualidad.

No es casualidad pues el Candy Crush Saga es, en realidad, la aplicación de la que hablaba en la introducción de este post. Una aplicación creada por el grupo KING del King College de Londres para tratar de refutar el problema P=NP.

La idea inicial era, al igual que sucediera con el Tetris en la década de los 90, crear un juego que fuese NP y tratar de demostrar, posteriormente, que era imposible crear una estrategia ganadora en tiempo algorítmicamente polinomial.

El proceso era sencillo: lanzaron el juego en beta entre los alumnos del King College para comprobar si realmente era suficientemente difícil. Sin embargo la cosa se les fue de las manos y pronto el juego adquirió una fama que trascendió las fronteras del campus.Así que no tuvieron más remedio que lanzar una aplicación a nivel global, antes de poder hacer los papers oportunos.

A día de hoy, aunque no de la forma esperada, el proyecto comienza a dar sus frutos. Gracias a sofisticados programas informáticos, han logrado crear un sistema ternario que, dado un nivel cualquiera de Candy Crush y fijado un , el programa es capaz de crear un nuevo nivel de dificultad mayor que el anterior.

Este programa no se aplica a niveles en concreto, sino que, en realidad, la rutina se ejecuta en paralelo (y gracias a los procesadores Intel Quantum de reciente creación) a todos los niveles de un mismo "mundo" para así conseguir una nueva gama de niveles.

La forma de atacar el problema es poco ortodoxa, pero no es nueva. De hecho, está basada en la idea de colaboración colectiva a través de terminales ideada en su día por el Proyecto SETI: SETI at HOME.

En concreto, cada vez que uno de nosotros jugamos a un nivel de Candy Crush, en realidad estamos enviando información sobre la estrategia (consciente o inconsciente) que llevamos a la hora de resolver cada pantalla. A este respecto, los primeros resultados obtenidos es que la curva de dificultad del juego no es continua sino que presenta discontnuidades de salto finito arbitrariamente localizadas en el tiempo.

Es esta característica la que llevó al programa creado por estos matemáticos a introducir las diferentes habilidades extras (martillos-piruletas, tiempos extras, etc...). Además, recientemente se ha descubierto una discontinuidad esencial en la curva de crecimiento, lo que ha provocado la aparición de la famosa Ruleta.

Según el comunicado aparecido en la última IMU-letter del año, los artículos científicos (5 en total), están siendo sometidos a revisión en varias revistas: Acta Mathematica Sinica, Journal of the Pan-American Mathematical Society y Comptes Rende-Vouz de la Academia de Ciencias de París.

Tanto es el éxito que parece que están teniendo que, recientemente, han lanzado una actualización de la Aplicación Candy Crush en la que, a los jugadores, les aparece un mundo de Ensueño alternativo.

El Proyecto Búho (como se le conoce entre los expertos), es en realidad una nueva línea de investigación en la que intentan resolver la Conjetura de Riemman. Si os fijáis, en los nuevos niveles es importantísimo mantener el equilibrio entre dos de los colores/carmelos para que no haya uno de ellos que se utilicen más que el otro. Esto tiene que venr con la famosa propiedad de universalidad de la Función Zeta de Riemman y que impide que los ceros no triviales estén arbitrariamente localizados.

Sin emnargo, por ahora la rutina no es capaz de crear niveles lo suficientemente complicados para que lso jugadores ayuden en la búsqueda de ceros no triviales. Pero dada la notoriedad de este grupo, la cosa promete.


Pues sí, queridos lectores, si alguna vez tu señora esposa o tu novio de toda la vida te dice que no le prestas suficiente atención por estar jugando todo el día a los caramelitos, desde hoy puedes decir con orgullo que

Jugar al Candy Crush ayuda en el adecuado avance de la investigación matemática.

Tito Eliatron Dixit