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.

Medidas de la complejidad de un juego

• La complejidad del estado-espacio de un juego es el número de posiciones legales del juego accesibles desde la posición inicial del juego.^[1]​

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.

• El tamaño del árbol del juego es el número total de las instancias posibles que puedan ser aplicadas al juego, es decir, es el número de los nodos hoja en el árbol del juego cuya raíz es la posición inicial.El árbol del juego es sumamente más grande que la complejidad del estado-espacio porque las mismas posiciones pueden ocurrir en muchas instancias del juego, haciendo movimientos en diverso orden (por ejemplo, en una partida del Tres en raya con dos X y un O en el tablero, esta posición se habría podido alcanzar de dos maneras diferentes, dependiendo de dónde fue puesto el primer X). Un límite superior para el tamaño del árbol del juego puede ser computado a veces, simplificando el juego de manera que aumente sólo el tamaño del árbol del juego (por ejemplo, permitiendo movimientos ilegales) hasta que llega a ser manejable.

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).

• La complejidad de decisión de un juego es el número de nodos hoja en el árbol de decisión más pequeño que establece el valor de la posición inicial. Todo árbol incluye todas las posibles decisiones para el jugador que mueve en segundo lugar, pero solo una

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

• La complejidad del juego-árbol de un juego es el número de nodos hoja del árbol de decisión completo en anchura que establece un valor en la posición inicial.^[1]​ (Un árbol completo en anchura incluye todos los nodos de todos los niveles). Ésta es una estimación del número de posiciones que podríamos tener que evaluar en una búsqueda usando el algoritmo minimax para determinar el valor de la posición inicial. Es difícil estimar la complejidad del juego-árbol, pero para algunos juegos un límite inferior razonable puede darse elevando el número de hijos medio de cada nodo al número de turnos que hay en el juego medio.

• El coste computacional de un juego describe la dificultad asintótica de un juego que crece de manera arbitraria, expresada en notación de cota superior o como miembro de una clase de complejidad. Este concepto no es aplicable a juegos concretos, pero si a juegos que han sido formalizados para que puedan ser aleatoriamente grandes, generalmente jugándolos en un tablero de n por n. (Desde el punto de vista de la complejidad computacional de un juego en un tablero de tamaño fijo, es un problema finito que se puede resolver en O(1), por ejemplo, con una tabla de búsqueda de posiciones en el mejor movimiento en cada posición).

Ejemplo: Tres en raya

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]​

Complejidad de algunos juegos conocidos

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.

Véase también

• Juego resuelto
• Lista de juegos y rompecabezas NP-completos
• Lista de juegos y rompecabezas PSPACE-completos

Notas y referencias

Enlaces externos

• David Eppstein's Computational Complexity of Games and Puzzles

1. Complejidad (desambiguación)
2. Teoría de la complejidad computacional
3. Complejidad (álbum)
4. Complejidad
5. Ley de complejidad-conciencia
6. Juego generalizado
7. Complejidad temporal
8. PSPACE-completo
9. Juego abstracto
10. Teoría de juegos
11. Diseñador de juegos
12. Complejidad social
13. Minijuego
14. Juego secuencial
15. Juego de cartas coleccionables
16. Juegos Panamericanos
17. Teoría de juegos combinatorios
18. Juegos tradicionales
19. Juego
20. Juego de mayoría ponderada