En las últimas semanas, he estado trabajando en un artículo matemático que estudia la complejidad computacional del Marvel Champions. En concreto, mi pregunta es cómo de difícil es el problema de saber si se puede ganar a partir de una posición dada. Y resulta que es bastante difícil en general.
Lo que he demostrado es que, a menos que P=NP (algo que matemáticamente se considera muy, muy, muy improbable), no existe un algoritmo eficiente que resuelva correctamente el problema de saber si a partir de una cierta situación de partida hay alguna forma de alcanzar la victoria, incluso aún sabiendo las cartas que van a salir y las "decisiones" que va a tomar el villano.
Este tipo de cuestión ya la había planteado, medio en broma medio en serio, en una charla que di hace un par de años cuando estuve como investigador visitante en la Universidad de Harvard (podéis observar el histórico momento inmortalizado en la foto que acompaña a este post). Así que me siento muy orgulloso y muy contento de poder darle una respuesta a través del teorema que he demostrado.
Como la mayor parte de los resultados matemáticos de este estilo, las construcciones que uso son muy artificiales y es muy improbable que se den en una partida real, pero al menos demuestran que el peor caso que uno se puede encontrar es difícil computacionalmente hablando. Además, eso no descarta que haya otras posiciones que también tengan la misma (o mayor) complejidad y que se den de forma natural. Eso merecería un estudio adicional.
Moraleja: ¡jugad al Marvel Champions! No solo es un juego tremendamente divertido, sino que además también es matemática y computacionalmente muy interesante.
PD: Si tenéis curiosidad o sufrís de insomnio recalcitrante, podéis echarle un vistazo al artículo y descargarlo de forma totalmente libre y gratuita en https://zenodo.org/records/24052102
No hay comentarios:
Publicar un comentario