Tetris presenta problemas matemáticos que incluso las computadoras no pueden resolver

Los problemas imposibles escondidos en un simple juego de Tetris

Por Manon Bischoff editado por Daisy Yuhas

Cuando era niño de la década de 1990, no podía evitar el juego Tetris de juego más vendido. Lanzado en 1984 por el programador ruso Alexey Pajitnov, Tetris se convirtió rápidamente en un éxito de taquilla y ha tenido cientos de millones de jugadores a lo largo de los años. Yo mismo pasé horas en mi niño tratando de colocar los ladrillos que caen para que llenen el campo de juego lo más completamente posible. En el transcurso de un juego, esos bloques cayeron cada vez más rápido, y mis pulgares apenas podían mantenerse al día con los controles.

En principio, todos los juegos, incluso aquellos tan variados como Candy Crush saga, Magia: la reunión y Lana—Se puede ser examinado desde una perspectiva matemática. Pero Tetris tiene muchas conexiones especiales con las matemáticas. Por ejemplo, el objetivo del juego fuertemente se asemeja a los problemas de parquet de la geometríaen el que determina si puede cubrir un área con un conjunto infinitamente grande de mosaicos sin huecos.

Pero Tetris es especialmente intrigante para los matemáticos en términos de su complejidad. Más específicamente, los investigadores se han preguntado sobre el poder informático que se necesita para determinar cómo o si alguien realmente puede “resolver” tetris, suponiendo condiciones como un número finito de ladrillos y la capacidad de conocer el orden en que aparecerán varias formas. Resulta que ese encuadre particular coloca a Tetris entre los juegos más matemáticamente complejos.

Sobre el apoyo al periodismo científico

Si está disfrutando de este artículo, considere apoyar nuestro periodismo galardonado con suscripción. Al comprar una suscripción, está ayudando a garantizar el futuro de las historias impactantes sobre los descubrimientos e ideas que dan forma a nuestro mundo hoy.

Definición de la complejidad

En el campo de la teoría de la complejidad, los matemáticos y los informáticos buscan caracterizar la dificultad involucrada en la resolución de problemas. Han definido múltiples clases de complejidad o categorías, incluidos los problemas de P y NP. En pocas palabras, los problemas de P son fáciles de resolver para las computadoras convencionales, mientras que los problemas de NP son más difíciles, pero, en caso de que tenga una solución posible, fácil de verificar. (Los problemas de NP pueden considerarse como un rompecabezas de Sudoku: puede llevar horas llenar los campos, pero solo lleva unos minutos ver si la solución es correcta).

Para determinar la complejidad de una tarea, uno debe comparar diferentes problemas entre sí. Si cada algoritmo que resuelve la tarea A También puede resolver la tarea B, Por ejemplo, entonces A es más complejo que B. O como lo expresaron los matemáticos: B es “reducible” a A. Eso significa que al comparar Tetris con otro problema de P o NP conocido, se puede determinar su complejidad.

Entonces, ¿cómo elegimos un buen punto de comparación? Los informáticos pueden recurrir a los llamados problemas completos de NP, a los que se pueden reducir todos los demás problemas de NP. Uno de estos es el problema de tres partes.

El problema de tres partes se ocupa de la cuestión de si un conjunto dado de enteros, por ejemplo {1, 2, 5, 6, 7, 9}, puede dividirse en subconjuntos con tres elementos cada uno tal que la suma de los números en los subconjuntos siempre es igual. Para {1, 2, 5, 6, 7, 9}, una división sería {1, 5, 9} y {2, 6, 7}. El contenido de cada subconjunto suma 15. Tal división no es posible para cada conjunto dado. Descubrir si esto existe o no resulta extremadamente difícil: el problema de tres partes es NP complete.

En 2003, los científicos informáticos del Instituto de Tecnología de Massachusetts demostraron que la cuestión de si un tablero de Tetris puede ser autorizado en una situación de juego determinada. se puede mapear al problema de tres partes. Para hacer esto, los investigadores equipararon los huecos en el juego Tetris con los subconjuntos del problema y los ladrillos que caen con los números que deben dividirse.

De esta manera, los científicos mostraron que si el conjunto de números se puede dividir en subconjuntos de tres elementos con la misma suma, entonces el campo de juego de Tetris también se puede vaciar por completo. Al hacerlo, demostraron que las preguntas “¿Se pueden dividir un set en una tres partes?” y “¿Se puede vaciar el campo de juego Tetris?” son idénticos desde un punto de vista matemático.

Esta idea significa que el rompecabezas de si los ladrillos dados se pueden organizar apropiadamente cae en la categoría de problemas completos de NP, lo que hace que Tetris sea un juego altamente complejo. Cuanto más larga sea la secuencia de ladrillos que contiene el juego, más lento es para una computadora determinar la solvabilidad. Y, de hecho, las computadoras convencionales se verán abrumadas muy rápidamente: no hay un algoritmo que pueda resolver el problema de manera eficiente.

Tetris alcanza los límites de la computabilidad

Tetris tiene propiedades aún más complejas, Como mostraron los informáticos científicos Hendrik Jan Hoogeboom y Walter Kosters, ambos en la Universidad de Leiden en los Países Bajos. en un artículo de 2004. Miraron una pregunta ligeramente diferente. Supongamos que observas un juego de Tetris que solo presenta el ladrillo alargado en forma de I. Si te diera un número predeterminado de formas para, por ejemplo, 40 mosaicos en forma de I para caer sobre un tablero de tetris vacío, ¿podrías decidir si, entre esas ocho formas, hay una para la cual el tablero termina vacío?

Hoogeboom y Kosters demostraron que esta pregunta es, de hecho, indecidible, incluso con una cantidad infinita de potencia informática. Esto se debe a que la pregunta antes mencionada se puede asignar a un problema que se relaciona con los infames teoremas incompletos de Kurt Gödel. Estos afirman que siempre habrá declaraciones en matemáticas que pueden Ninguno de los dos ni refutado.

Por supuesto, estas preguntas probablemente no tienen ningún efecto en su éxito en Tetris. Con la velocidad a la que caen las piezas, casi no hay tiempo para pensar en los problemas matemáticos.

Aún así, es notable que después de más de 40 años, la apreciación de Tetris continúe creciendo y evolucionando, incluso cuando el juego permanece esencialmente sin cambios. Por ejemplo, una técnica de juego conocida como “rodar” (que permite realizar entradas muy rápidas) ha hecho posible avanzar más allá de nunca antes. En el pasado, el nivel 29 se vio como un límite insuperable. Pero en 2023, un joven de 13 años rompió todos los récords anteriores al rodar hasta el nivel 157haciendo que el juego se estrellen. Solo podemos esperar y ver qué sorpresas tiene Tetris en el futuro.

Este artículo apareció originalmente en Spektrum der Wissenschaft y fue reproducido con permiso.