Complejidad en los juegos

La teoría de juegos combinatorios posee diversas maneras de medir la complejidad en los juegos. Este artículo describe cinco de ellas: complejidad estado-espacio, tamaño del árbol del juego, complejidad de las decisiones, complejidad del árbol del juego, y complejidad computacional.

Cuando esto es demasiado difícil de calcular, un límite superior puede ser computado a menudo incluyendo las posiciones ilegales o las posiciones que nunca pueden presentarse en el curso de un juego.

Sin embargo, para los juegos donde el número de movimientos no se limita (por ejemplo por el tamaño del tablero, o por una regla sobre la repetición de la posición) el árbol del juego es infinito. Las dos siguientes medidas usan un árbol de decisión. Un árbol de decisión es un subárbol del árbol del juego, con cada nodo etiquetado como “jugador A gana”, “jugador B gana” o “empate”, donde puede probarse que ese nodo tiene ese valor (asumiendo que ambos jugadores hacen el mejor movimiento) solo con examinar otros nodos del grafo. (Los nodos terminales pueden ser etiquetados directamente; un nodo en la que le toque mover al jugador A puede etiquetarse con “jugador A gana” si nodo sucesor es una victoria para A, o etiquetado con “jugador B gana” si todos los nodos sucesores, son victorias para B, o etiquetado como “empate” si todos los nodos sucesores son o empates o victoria para B. Y de manera análoga, para las posiciones en las que mueve B).

posibilidad para cada decisión del jugador que comienza la partida.

El juego de mesa de tres en raya mundialmente conocido se extendió bastante, entre otras cosas por su versatilidad. Es necesario realmente poco para lograr iniciar el juego allá donde uno prefiera. Exponer y usar de manera usual este juego con chicos y chicas va muchísimo más allá de ejercer un juego clásico.

Para el juego de Tres en raya podríamos tener un límite de 3⁹ = 19.683 maneras de rellenar el tablero (tres posibles estados para cada celda y nueve celdas). Esta cuenta incluye muchas posiciones ilegales tales como una posición con cinco cruces y sin ceros, o una posición en la que ambos jugadores tienen una fila de tres. Aplicando a estas restricciones, tenemos una cuenta mejorada, en la que eliminando estas posiciones ilegales, podríamos tener 5.478 combinaciones para rellenar. Aunque... son consideradas idénticas, hay solo 765 posiciones estrictamente diferentes. Si atendemos a la cota superior del árbol que genera el tablero, tenemos 9!=362.880 (9 posiciones para el primer movimiento, 8 para el segundo, y así sucesivamente). Esta cuenta incluye partidas y movimientos ilegales, ya que el juego puede haber terminado. Si refinamos entonces las combinaciones tenemos 255.168 posibles movimiento. Si además añadimos que las rotaciones de las posiciones son consideradas las mismas, tenemos sólo 26.830 lanzamientos. La complejidad computacional del tres en raya depende de la forma en que esté formalizado. Una formalización natural sería juegos m,n,k, que sería un tablero de m x n siendo el ganador el que consigue obtener k en raya. Es trivial que el juego puede ser resuelto DSPACE (mn) con la búsqueda del árbol del juego. Esto lo coloca en una clase de complejidad importante, PSPACE. Con un poco más de trabajo se puede demostrar que es PSPACE-completo.^[2]

Debido a la gran cantidad de complejidades en los juegos, esta tabla da la aproximación superior de su logaritmo en base 10. Los números mostrados a continuación deben ser considerados con precaución: cambios aparentemente pequeños en las reglas del juego pueden cambiar estos números (que no son estimaciones demasiado exactas) por tremendos factores, que pueden ser fácilmente mucho mayores que los datos ofrecidos.

(cells)

(como log en base 10)

(número de turnos)