211service.com
… Y Scrabble probado como PSPACE-Complete
Scrabble, que se inventó en los EE. UU. A mediados del siglo XX, ahora está disponible en docenas de idiomas y se vende en cantidades que se miden en cientos de millones. Eso lo convierte en uno de los juegos más populares del mundo.
Eso, naturalmente, ha despertado el interés de los teóricos de los juegos. Dado que Scrabble es un juego tan exitoso, se convierte en una cuestión natural determinar la complejidad computacional de encontrar un juego óptimo, dicen Michael Lampis del Real Instituto de Tecnología de KTH en Suecia y algunos amigos.
La misma pregunta se ha formulado con éxito en muchos juegos de mesa, como el ajedrez, Go y Othello, que tienden a ser PSPACE o EXPTIME-complete. Pero Scrabble es más complicado porque los jugadores no saben el orden en el que se dibujarán las fichas, lo que significa que el azar juega un papel más importante.
La pregunta que Lampis y compañía intentan responder es la siguiente: dada una posición de Scrabble, ¿qué tan difícil es determinar la mejor estrategia de juego?
Señalan que en cualquier ronda, un jugador de Scrabble se enfrenta a dos tareas: decidir qué palabra formar y decidir dónde colocarla en el tablero. Estas tareas están relacionadas porque las palabras que se pueden formar dependen de la posición de las letras en el tablero.
Pero, ¿cuál de estas tareas es la que dificulta el Scrabble? Lo que Lampis y compañía muestran es que ambos son duros y dan pruebas de cada uno para respaldar su afirmación. Eso es impresionante porque nos permite 'ver' por qué Scrabble es difícil.
Establecemos que durante el transcurso de un juego, los jugadores de Scrabble deben realizar no una, sino dos tareas computacionalmente difíciles, que es probablemente la razón por la que Scrabble es tan divertido de jugar, escriben.
Eso no quiere decir que los teóricos de la complejidad computacional hayan terminado y espolvoreados con Scrabble. Su próxima tarea es descubrir si existe un algoritmo de tiempo polinomial para determinar el movimiento que maximizaría la puntuación lograda en esta ronda.
¡Eso sería útil!
Ref: arxiv.org/abs/1201.5298 : Scrabble es PSPACE-Complete