COMPUTACIÓN

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.

• Walsh, Toby

Menear

inCompartir8

CORTESÍA DE GLOBAL KING

En síntesis

Los problemas computacionales pueden agruparse en distintas categorías atendiendo al tiempo que necesitará un ordenador para resolverlos. Dos grandes clases de problemas son los de tipo P, o «fáciles», y los de tipo NP, o «difíciles».

Un trabajo reciente ha analizado la complejidad computacional de Candy Crush. Al describir el juego en términos de un circuito con puertas lógicas, el autor ha demostrado que pertenece a la clase de problemas más difíciles dentro de NP.

Al igual que los populares captchas ayudan a Google a digitalizar manuscritos, tal vez los millones de horas que los humanos dedican a resolver tableros de Candy Crush puedan «reutilizarse» para abordar otros problemas igualmente complejos.

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 difieren. 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 dificultad semejante, por lo que tardaremos tiempos similares en solucionarlos.