Menos ajedrez y más Tetris

En su ciudad se va a celebrar un congreso de adictos al Tetris, con 400 participantes, y usted es el encargado de alojar a 100 de ellos en el hotel Uqbar (los demás tendrán que buscarse la vida en otros hoteles). Como es sabido, el hotel Uqbar sólo tiene 50 habitaciones, así que los 100 elegidos tendrán que acomodarse dos a dos. Hasta ahí, bien. Pero, cuidado, porque los adictos al Tetris son a veces muy correosos, y el organizador del congreso le ha dado una amplia lista de parejas incompatibles. "Debemos intentar que todo el mundo esté contento", le dice el organizador. "Presénteme mañana todas las soluciones posibles, y yo elegiré la mejor".

Usted se sienta en su despacho con aire profesional, pero veinte horas después se da cuenta de que algo va mal. No hay ninguna fórmula simple que pueda generar el conjunto de soluciones posibles. Mejor dicho, sólo hay una, y consiste en hacerlo a lo bestia: probando todas las posibles listas de 100 adictos, agrupándolos dos a dos de todas las formas imaginables y viendo si el resultado viola la ley de incompatibilidades. Pero eso también es horrible, porque el número de posibles formas de seleccionar 100 adictos del grupo de 400 es mayor que el número de átomos en el Universo conocido. Maldito congreso, ¿por qué no me quedaría yo en el pueblo jugando al ajedrez?

El rompecabezas del hotel Uqbar es un ejemplo de problema NP, que se puede definir como una pregunta tal que cada respuesta tentativa es fácil de confirmar o descartar (déle una solución concreta al organizador del congreso, y él verá enseguida si es válida o no), pero que no puede resolverse de forma sistemática en un tiempo razonable, ni siquiera con el más potente ordenador. Un puzle sirve como metáfora intuitiva de problema NP: resolverlo lleva mucho tiempo, pero comprobar si alguien lo ha resuelto no cuesta ni un segundo. Tal vez los problemas NP no existan, y no sean más que un reflejo de la torpeza de nuestros matemáticos actuales. Si usted logra demostrar eso, o lo contrario (que los problemas NP sí existen), el Instituto de Matemáticas Clay le dará un millón de dólares.

Un adicto que asegura estar rehabilitado, Erik Demaine, del Massachusetts Institute of Technology (MIT), ha demostrado que el Tetris es un problema NP. Esto quiere decir que no hay forma de programar un ordenador para que juegue al Tetris de manera rápida y eficaz, como un jugador humano experto. El único programa posible sería el de la fuerza bruta: en cada momento, considerar todas las posibles piezas que pueden caer desde arriba, y evaluarlas en todas las posiciones, rotaciones y combinaciones imaginables hasta decidir cuál es la mejor. Eso lleva tanto tiempo que no es viable.

Que el Tetris sea un problema NP también implica que los jugadores humanos, por muy expertos que sean, tienen que jugar cada vez de verdad, sin posibilidad de aplicar estrategias simples y generales de probada eficacia. Ésta es la razón de que genere adicción. "Cuando juegas al Tetris, estás resolviendo problemas realmente duros", explica Demaine. "El juego es horriblemente adictivo porque supone un gran desafío intelectual".

Peores tiempos corren para el ajedrez. Michael Atherton, Xiangchuan Chen y sus colegas han analizado a varios jugadores de ajedrez mediante resonancia magnética, una técnica que permite ver qué circuitos cerebrales se activan mientras el jugador está planeando su siguiente jugada (Cognitive Brain Research, marzo de 2003). El resultado es francamente embarazoso: allí se activan áreas cerebrales relacionadas con la atención, la percepción espacial y la rotación mental de objetos, pero las implicadas en el análisis inteligente de problemas, situadas en el lóbulo frontal, parecen estar durmiendo el sueño de los justos. Jaque mate, troncos. ¿Hay por ahí algún ajedrecista que quiera echar una partida de Tetris?