El misterio de Candy Crush

Escrito por Toby Walsh el . Publicado en Muy interesante

0
0
0
s2sdefault

Las intrigantes matemáticas de Candy Crush. Tras este juego de apariencia simple se esconden algunos de los problemas de cómputo más difíciles que se conocen. Tal vez por eso resulte tan adictivo.

Se ha dicho que, en una ciudad, uno nunca está a más de unos pocos palmos de una rata. Pero hoy en día tal vez deberíamos decir que nunca estamos a más de unos palmos de alguien jugando a Candy Crush Saga. En estos momentos es el juego más popular en Facebook. Se ha descargado e instalado en móviles, tabletas y ordenadores más de quinientos millones de veces. Gracias a ese éxito, su desarrollador, Global King, irrumpió hace poco en la Bolsa de Nueva York con una oferta pública inicial que valoró la compañía en miles de millones de dólares. Nada mal para un pasatiempo consistente en intercambiar la posición de unos caramelos para formar cadenas de tres o más golosinas idénticas.

Gran parte de la atracción de Candy Crush se debe a que, a pesar de su aparente simplicidad, se apoya en bases muy complejas. Sorprendentemente, el juego también ha despertado gran interés entre los investigadores, ya que pone en perspectiva uno de los problemas abiertos más importantes de la matemática y de la seguridad en los sistemas informáticos.

En un trabajo reciente, demostré que Candy Crush constituye un rompecabezas matemático muy difícil de resolver. Para ello recurrí a uno de los conceptos más importantes y bellos de las ciencias de la computación: la reducción de un problema, consistente en transformar un problema en otro o, como gusta decir a los informáticos, «reducir» un problema a otro. En el fondo, la idea emana de la versatilidad del código informático: el mismo código puede emplearse para resolver más de un problema, incluso si las variables diieren. Si comenzamos con un problema difícil y lo reducimos, el problema que obtendremos será, por lo menos, tan complejo como el original. La versión transformada no puede resultar más sencilla, ya que se supone que somos capaces de solucionar el primer problema con un programa de ordenador que puede resolver también el segundo. Y, si lo pensamos al revés —es decir, que el segundo problema también puede reducirse al primero—, llegaremos a la conclusión de que, en cierto sentido, ambos revisten una diicultad semejante, por lo que tardaremos tiempos similares en solucionarlos.

Determinar la diicultad de un problema constituye una cuestión fundamental en matemáticas. No se trata de un mero aspecto semántico. Si podemos clasiicar un problema por lo difícil que resultará resolverlo, sabremos qué potencia de cómputo necesitaremos e incluso si vale la pena intentarlo. De modo que, al menos para los matemáticos, considerar Candy Crush como un problema matemático puede ser tan adictivo como jugarlo.

SOLUCIONES DIFÍCILES, COMPROBACIONES FÁCILES

Al analizar Candy Crush junto con mis colaboradores, comenzamos por considerar la clase más famosa de problemas complejos de cómputo. Estos reciben el nombre de NP, por «tiempo polinómico no determinista» en inglés. Aquí el término «tiempo» hace referencia a cuánto tardaremos en resolver el problema en cuestión. La clase NP incluye todos aquellos problemas para los que, si alguien nos da la solución, podremos veriicar con rapidez que es correcta; es decir, hacerlo nos llevará un tiempo que solo será una función polinómica del tamaño del problema. No obstante, hallar la solución partiendo de cero plantea todo un reto computacional. Un gran número de problemas matemáticos bien conocidos, como determinar si una fórmula lógica compleja puede ser satisfecha o no, o si podemos colorear un grafo de forma que los nodos vecinos muestren siempre colores distintos, pertenecen a esta clase de problemas computacionales difíciles.

En lo que respecta a su complejidad, por debajo de la clase NP tenemos los problemas de cómputo «fáciles», o de clase P. En este caso, la P solo indica «polinómico». Este grupo incluye problemas como ordenar una lista o encontrar un registro en una base de datos. Un programa informático eiciente tardará poco en resolverlos, incluso en el peor de los casos. Desde un punto de vista matemático, el tiempo de resolución crece de manera polinómica con el tamaño del problema. Por ejemplo, un conocido algoritmo para ordenar listas, llamado ordenación de burbuja o método de intercambio directo, intercambia los elementos consecutivos de una lista si están en orden equivocado (lo que hace que algunos datos se «eleven» a lo largo de la lista, como si fueran burbujas). Esta manera de proceder permite concluir la tarea en un tiempo que aumenta como el cuadrado del tamaño de la lista que deseemos ordenar. Si doblamos el número de elementos, el algoritmo tardará, en el peor de los casos, cuatro veces más. El caso más desfavorable se da cuando la lista inicial se encuentra justo en el orden inverso al de la lista ordenada, lo que obliga al algoritmo a elevar cada elemento. Si partimos de otra situación, el algoritmo concluirá antes.

Existen problemas incluso más difíciles que los de tipo NP. De hecho, hay problemas para los que nuestros estándares de computación, aquellos por los que se rigen nuestros ordenadores, no sirven en absoluto. En tales casos no existe ningún programa informático que garantice una respuesta en un tiempo inito. Estos pertenecen a la clase de problemas indecidibles, la cual incluye cuestiones como determinar si un programa dado terminará en algún momento o si, por el contrario, caerá en una especie de bucle sin in; lo que los teóricos de la computación conocen como el problema de la detención. Alan Turing, uno de los padres de la computación, demostró que el problema de la detención es indecidible: no puede existir ningún programa informático que, para todos los programas posibles, incluido él mismo, sea capaz de determinar si se pararán o no.

La clase NP se ubica en la frontera que separa los problemas fáciles de los difíciles. Dentro de NP existen multitud de problemas que constituyen verdaderos retos; entre ellos, determinar las rutas óptimas para camiones de reparto, organizar turnos de personal o concertar el horario de clases en un colegio. Candy Crash pertenece a esta categoría de problemas NP difíciles. Cualquiera de ellos puede reducirse a cualquier otro, por lo que, en este sentido, resultan igualmente complejos.

Por desgracia, los mejores programas informáticos de los que disponemos requieren tiempos de ejecución que crecen drásticamente conforme aumentamos el tamaño de un problema de tipo NP. En mi ordenador tengo un programa que tarda pocas horas en encontrar la ruta óptima para diez camiones y demostrar que se trata de la mejor solución posible. Pero, para cien camiones, el mismo programa tardaría más que la edad del universo. Ello se debe a que el tiempo de ejecución de dicho programa crece exponencialmente con el tamaño del problema.

Las funciones exponenciales crecen muy rápido. Así lo ilustra la conocida fábula del visir al que un sultán le concede como premio cualquier cosa que pida. El visir le pregunta si le otorgaría un grano de trigo por el primer escaque de un tablero de ajedrez y, en cada uno de los siguientes, el doble que en el anterior. El sultán razona que, puesto que se trata de un grano de trigo en el primer escaque, dos en el segundo, cuatro en el tercero, y así sucesivamente, no parece un gran premio. Pero comete un error colosal, ya que, en el escaque 64, el último del tablero, se alcanza el número 18.446.744.073.709.551.615: más de 18 trillones de granos, lo que equivaldría a la cantidad de trigo producida en todo el planeta durante cientos de años. Las exponenciales superan nuestra intuición de una manera asombrosa.

Aunque la mayoría de los teóricos de la computación estarían de acuerdo con que los problemas NP se sitúan en la frontera entre lo fácil y lo muy difícil, dado un problema especíico, no hay forma de saber con seguridad en qué lado se encontrará. Los mejores algoritmos a nuestra disposición tardan un tiempo exponencial en resolver problemas NP. Pero no sabemos si habrá algún algoritmo exótico aún por descubrir capaz de concluir en tiempo polinómico. Los matemáticos abrevian esta cuestión con la pregunta de si P = NP. Hoy por hoy, esta constituye una de las cuestiones abiertas más importantes de la matemática. Tanto es así que el Instituto Clay ha prometido un millón de dólares a quien encuentre la respuesta. Y aunque la oferta está en pie desde el año 2000, el premio sigue desierto.

En la última encuesta entre especialistas acerca de si P = NP, el 83 por ciento respondió que no creía en la igualdad entre ambas clases de problemas. Eso signiica que piensan que no existen algoritmos eicientes para resolver problemas NP y que nunca los habrá. Ante la pregunta sobre cómo llamar a los problemas que, pertenezcan o no a NP, resultan al menos tan difíciles como los de tipo NP, acabaron decantándose por un prosaico «NP-difícil» (NP-hard). Con todo, este segundo sondeo reveló un curioso sentido del humor. Algunas propuestas alternativas fueron «NP-irrealizables» (NP-impractical), «NP-enrevesados» (NP-tricky) y «NP-tocanarices» (NP-hard-ass).

La idea de reducción de un problema desempeña un papel fundamental en la cuestión de si P = NP. Si encontrásemos un algoritmo eiciente para solucionar un problema de NP, entonces podríamos resolver todos ellos de manera eiciente. En tal caso, el mundo se convertiría en un lugar muy distinto del que conocemos. Las buenas noticias serían que aprovecharíamos mucho mejor el tiempo: nuestros camiones de reparto seguirían rutas óptimas, los vuelos se programarían de manera impecable y los turnos de personal serían perfectos. También ganaríamos siempre en Candy Crush. Sin embargo, nuestras contraseñas y cuentas bancarias dejarían de ser seguras, porque descifrarlas habría dejado de suponer un reto. La complejidad computacional puede ser tanto un inierno como una bendición. Queremos estar seguros de que los piratas informáticos lo tendrán muy difícil a la hora de descifrar un código; sin embargo, hemos de poder cifrarlos con rapidez.

El ejemplo anterior tal vez le traiga a la cabeza la deinición de problemas de tipo NP: aquellos cuya respuesta es fácil de veriicar pero difícil de encontrar. La criptografía consiste en poner barreras computacionales a los amigos de lo ajeno. Si tales impedimentos desaparecieran, el mundo moderno se vería en grandes apuros.

CARAMELOS Y CIRCUITOS

Para demostrar que Candy Crush equivale a un problema matemático de gran complejidad, podríamos reducirlo a cualquier problema NP. Para simpliicar las cosas, nuestra investigación partió del antepasado de todos los problemas NP: el problema de satisfacibilidad, o de encontrar la solución de una fórmula lógica. El lector se habrá enfrentado a esta clase de problemas si alguna vez ha intentado resolver un pasatiempo de lógica en el que debe decidirse qué proposiciones son verdaderas y cuáles falsas para satisfacer un conjunto de fórmulas lógicas: si el inglés vive en la casa roja, el español es el dueño del perro y el noruego vive junto a la casa azul, ¿es cierta o falsa la proposición de que el español es el dueño de la cebra?

Para reducir un rompecabezas lógico al juego de Candy Crush, podemos recurrir a la conocida relación entre lógica y circuitos eléctricos. Toda fórmula lógica puede representarse mediante un circuito; al in y al cabo, los ordenadores no son más que una gran colección de puertas lógicas (and, or y not) conectadas por cables. Por tanto, todo lo que necesitamos demostrar es que podemos construir un circuito eléctrico equivalente a Candy Crush.

En primer lugar, necesitamos una placa base sobre la que construir el circuito. Esta debe corresponder a una distribución neutral de caramelos, donde la disposición relativa de las golosinas permanezca estática y nunca pase nada. La que reproducimos en la igura de la derecha recuerda a las luces de los semáforos: en las columnas impares alternamos gominolas rojas y lágrimas de limón amarillas, y en las pares, pastillas naranjas y chicles verdes. Con este tablero de fondo, incluso si movemos las columnas hacia arriba o hacia abajo nunca obtendremos una cadena de tres caramelos idénticos.

Sobre ese marco insertaremos los componentes eléctricos, que en nuestro caso estarán formados por moras. Colocar una mora en una casilla no sustituye al caramelo que se encontraba allí, sino que lo desplaza junto con todos los siguientes. Ahora, el contacto entre moras crea un cableado que conduce señales a lo largo del circuito. Si situamos una mora en la entrada del cableado, a la izquierda, formaremos una cadena de tres de ellas. Según la regla básica del juego, esta desaparecerá, lo que hará caer los caramelos de las columnas afectadas y propagará la señal a lo largo del cableado. Al inal, aparecerá una mora en la salida, a la derecha. De esta manera, una señal se habrá transmitido por la placa base.

También necesitamos interruptores que permitan al usuario decidir qué conexiones están activas. Estos representan la elección sobre si una proposición de nuestra fórmula booleana se establece como verdadera o falsa. En la igura, el usuario puede desplazar la mora central hacia arriba o hacia abajo, movimientos que transmitirán la señal hacia la derecha o hacia la izquierda.

Por ultimo, podemos construir puertas logicas como and, or y not usando las moras como componentes basicos. Despues solo habremos de conectar interruptores a estas puertas logicas con conexiones lo suicientemente largas para obtener un circuito electrico que simula nuestra formula logica. Este tendra un bit de salida, el cual representara la verdad de la formula logica.

ASOCIAR PROBLEMAS

En terminos de circuitos logicos como el que hemos descrito, el objetivo de Candy Crush consiste en decidir que interruptores debemos activar para que las puertas logicas disparen adecuadamente y el bit de salida cambie a verdadero. De esta forma, reducimos el problema de satisfacer una formula logica al de resolver un tablero en Candy Crush. Y, dado que satisfacer una formula logica es un problema dificil, tambien lo sera Candy Crush.

Tambien podemos demostrar el inverso: que un problema en Candy Crush puede reducirse al de satisfacer una formula logica. Solo necesitamos escribir una secuencia o formula que represente el tablero de Candy Crush. En esencia, semejante descripcion logica de Candy Crush se encuentra en cualquier programa capaz de jugarlo.

Por tanto, Candy Crush no es mas dificil, pero si tan dificil como cualquier otro problema de tipo NP. Si hallasemos un metodo eiciente para resolver tableros de Candy Crush, habriamos encontrado una manera eiciente de planiicar rutas de camiones, turnos de personal y horarios lectivos. De igual modo, si algun dia descubriesemos un algoritmo rapido para resolver cualquiera de estos problemas, tendriamos una forma eiciente de jugar a Candy Crush. En ello reside la potencia de la reduccion de problemas.

La proxima vez que no consiga resolver un tablero de Candy Crush en el numero de movimientos asignado, tal vez le consuele pensar que se ha enfrentado a un problema matematico de gran complejidad. Puede que eso explique por que este juego provoca tanta adiccion. Si hubiese una estrategia sencilla para ganar, como ocurre con el tres en raya, jamas seria tan cautivador.

Gracias a la reduccion de problemas, los teoricos de la computacion han logrado reducir una gran cantidad de cuestiones posibles a un pequeno numero de clases fundamentales, como P y NP, que los expertos han apodado ázoo de la complejidad â. Hoy este zoo cuenta con unas 500 clases de problemas, algunas con nombres tan exoticos como D2P, LogFew, NEEE o P-cerrado .por si aun no lo habia notado, los teoricos de la computacion adoran los acronimos.

En el caso poco probable de que se demuestre que P = NP, el numero de clases del zoo se reduciria de manera drastica. Muchas de las que hoy creemos distintas resultarian ser equivalentes. En cambio, si P ‚ NP, como creen numerosos expertos, ello querria decir que realmente existen multiples clases de problemas. En cualquier caso, este particular bestiario continua creciendo. Hace poco, se han identiicado nuevas clases para describir la complejidad de aquellos problemas que podria resolver un ordenador cuantico.

La reduccion de problemas ofrece una intrigante posibilidad para los adictos a Candy Crush. .Seria posible aprovechar los millones de horas que los humanos invertimos en alinear caramelos? Tal vez la reduccion de problemas pueda explotarse para redirigir la resolucion de tableros de Candy Crush a otros problemas de computo. La idea no es nueva. Cada vez que entramos en una pagina web y demostramos que somos una persona y no un bot resolviendo un CAPTCHA (las imagenes distorsionadas de una palabra o un numero que debemos teclear), nuestra respuesta ayuda a Google a digitalizar todo tipo de documentos, desde periodicos hasta manuscritos antiguos. Tal vez podriamos aprovechar los tableros de Candy Crush para usos similares.

Nuestras investigaciones sobre Candy Crush nos han hecho respetar profundamente este pasatiempo de apariencia inocua. Su funcionamiento arroja luz sobre una de las cuestiones abiertas mas importantes de la matematica, cuyas implicaciones se extienden a todo tipo de aplicaciones, como los algoritmos de cifrado que permiten mantener a salvo nuestras cuentas bancarias. Tal vez quiera explicarselo a su jefe la proxima vez que este le sorprenda intentando llegar "solo al siguiente nivel".

Toby Walsh - American Scientist Magazine - Investigación y Ciencia

Escribir un comentario

Código de seguridad
Refescar

UK betting sites, view full information www.gbetting.co.uk bookamkers