Resolver el juego Candy Crush Saga es un problema NP-duro

Por Francisco R. Villatoro, el 13 abril, 2014. Categoría(s): Ciencia • Informática • Noticias • Science ✎ 2

Dibujo20140413 candy crush saga - bejeweled - shariki - arxiv org

Juntar caramelos no parece muy divertido. Pero Candy Crush Saga es uno de los juegos para móvil más populares. Como en el caso de Tetris, un juego demasiado simple tiene un éxito arrollador. Quizás la razón es que el algoritmo para su resolución es NP-duro según la teoría de la complejidad computacional. La demostración de que Bejeweled (y como consecuencia también Candy Crush Saga) es NP-duro requiere abstraer las reglas del juego (juega a la versión abstracta) y reducirlo a un problema problema que ya se sepa que es NP-duro, en este caso 1in3PSAT (1-in-3 positive 3SAT). Los detalles en Luciano Gualà, Stefano Leucci, Emanuele Natale, «Bejeweled, Candy Crush and other Match-Three Games are (NP-)Hard,» arXiv:1403.5830 [cs.CC], 24 Mar 2014.

Dibujo20140413 The genealogy of Bejeweled from tetris 1985 to da vinci code 2006 - arxiv org

Además, algunos problemas particulares son NP-completos, como: ¿Hay alguna secuencia de movimientos que permita a un jugador hacer que aparezca un «caramelo» concreto? ¿Puede un jugador obtener una puntuación de al menos x? ¿Puede un jugador obtener una puntuación de al menos x en al menos k movimientos?

Para los profesores de teoría de la complejidad algorítmica, poder elegir juegos de móvil populares como ejemplos de problemas NP-completos y NP-duros puede ser una motivación adicional para sus alumnos.

Dibujo20140413 candy crush saga - photo PR

PS: Gracias a César Tomé @EDocet me he enterado del artículo «This is what Candy Crush Saga does to your brain,» Notes&Theories, The Guardian Blogs, 1 Apr 2014. Quizás parezca un chiste de April’s Fool, pero nos informa que la compañía autora del juego Candy Crush Saga tiene un valor en Wall Street de 7,1 miles de millones de dólares, con un beneficio diario de 0,8 millones de dólares y unos 93 millones de jugadores diarios.

El psicólogo Steve Sharman (Universidad de Cambridge) está investigando la adicción a este juego. Como en la ludopatía asociada a las máquinas tragaperras, «la ilusión de control es un elemento crucial en la adicción a este juego … [ya que] infunde un sentimiento de control [sobre] el resultado del juego.»

Investigadores de la Universidad de Harvard y de la Universidad de British Columbia consideran que la clave es el efecto llamado adaptación hedónica, un mecanismo psicológico mediante el cual, una vez saciado un deseo, otra necesidad ocupa su lugar y nos mantiene tan insatisfechos como antes. Parece que la privación hace que la recompensa que mucho más dulce al final. El artículo técnico es Jordi Quoidbach, Elizabeth W. Dunn, «Give It Up. A Strategy for Combating Hedonic Adaptation,» Social Psychological and Personality Science 4: 563-568, Sep 2013.

Más información (gracias a @EDocet) en Jamie Madigan, «Why You Don’t Burn Out on Candy Crush Saga,» The Psychology of Video Games, 7 Oct 2013, y Edge Staff, «The Psychology Of: free-to-play,» Edge online, 18 Sep 2012.



2 Comentarios

  1. JAJA! La math paga!

    Mira tú, he estado resolviendo problemas NP durante buena parte de mi vida, y recién ahora me vengo a enterar 😀

    ¿Qué hay de Plants vs Zombies? Intuyo que ha de estar basado en lo mismo, pero con mayor número de variables. Los ingresos de PopCap Games tampoco han de ser despreciables 😉

Deja un comentario