Complejidad del juego - Game complexity
La teoría de juegos combinatorios tiene varias formas de medir la complejidad del juego . Este artículo describe cinco de ellos: complejidad del espacio de estados, tamaño del árbol del juego, complejidad de decisiones, complejidad del árbol del juego y complejidad computacional.
Medidas de complejidad del juego
Complejidad del espacio de estados
La complejidad del espacio de estado de un juego es el número de posiciones de juego legales accesibles desde la posición inicial del juego.
Cuando esto es demasiado difícil de calcular, un límite superior a menudo se puede calcular contando también (algunas) posiciones ilegales, es decir, posiciones que nunca pueden surgir en el transcurso de un juego.
Tamaño del árbol de juego
El tamaño del árbol del juego es el número total de juegos posibles que se pueden jugar: el número de nodos hoja en el árbol del juego enraizados en la posición inicial del juego.
El árbol del juego suele ser mucho más grande que el espacio de estado porque las mismas posiciones pueden ocurrir en muchos juegos al hacer movimientos en un orden diferente (por ejemplo, en un juego de tic-tac-toe con dos X y una O en el tablero, esto posición podría haberse alcanzado de dos formas diferentes dependiendo de dónde se colocó la primera X). Un límite superior para el tamaño del árbol del juego a veces se puede calcular simplificando el juego de una manera que solo aumente el tamaño del árbol del juego (por ejemplo, permitiendo movimientos ilegales) hasta que se vuelva manejable.
Para los juegos en los que el número de movimientos no está limitado (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 generalmente infinito.
Árboles de decisión
Las siguientes dos medidas usan la idea de un árbol de decisiones , que es un subárbol del árbol del juego, con cada posición etiquetada con "el jugador A gana", "el jugador B gana" o "empatado", si se puede demostrar que esa posición tiene ese valor (asumiendo el mejor juego de ambos lados) examinando solo otras posiciones en el gráfico. (Las posiciones terminales se pueden etiquetar directamente; una posición en la que el jugador A debe moverse se puede etiquetar como "el jugador A gana" si cualquier posición del sucesor es una victoria para A, o se puede etiquetar como "el jugador B gana" si todas las posiciones del sucesor son victorias para B, o etiquetado como "empate" si todas las posiciones sucesoras son empatadas o gana para B. Y, en consecuencia, para las posiciones con B para moverse).
Complejidad de decisiones
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.
Complejidad del árbol de juegos
La complejidad del árbol de juego de un juego es el número de nodos hoja en el árbol de decisión de ancho completo más pequeño que establece el valor de la posición inicial. Un árbol de ancho completo incluye todos los nodos en cada profundidad.
Esta es una estimación del número de posiciones que uno tendría que evaluar en una búsqueda minimax para determinar el valor de la posición inicial.
Incluso es difícil estimar la complejidad del árbol del juego, pero para algunos juegos se puede dar una aproximación elevando el factor de ramificación promedio b del juego a la potencia del número de capas d en un juego promedio, o:
.
Complejidad computacional
La complejidad computacional de un juego describe la dificultad asintótica de un juego a medida que crece arbitrariamente, expresada en notación O grande o como pertenencia a una clase de complejidad . Este concepto no se aplica a juegos en particular, sino más bien a los juegos que han sido generalizadas para que puedan hacerse arbitrariamente grande, típicamente por jugar con ellos en un n -by- n bordo. (Desde el punto de vista de la complejidad computacional, un juego en un tablero de tamaño fijo es un problema finito que se puede resolver en O (1), por ejemplo, mediante una tabla de consulta desde las posiciones hasta la mejor jugada en cada posición).
La complejidad asintótica se define por el algoritmo más eficiente (en términos de cualquier recurso computacional que se esté considerando) para resolver el juego; la medida de complejidad más común ( tiempo de cálculo ) siempre está limitada por el logaritmo de la complejidad asintótica del espacio de estados, ya que un algoritmo de solución debe funcionar para todos los estados posibles del juego. Estará limitado por la complejidad de cualquier algoritmo particular que funcione para la familia de juegos. Se aplican observaciones similares a la segunda medida de complejidad más utilizada, la cantidad de espacio o memoria de computadora utilizada por el cálculo. No es obvio que exista un límite inferior en la complejidad del espacio para un juego típico, porque el algoritmo no necesita almacenar estados del juego; sin embargo, se sabe que muchos juegos de interés son PSPACE-hard , y se deduce que su complejidad espacial también estará limitada por el logaritmo de la complejidad asintótica del espacio de estados (técnicamente, el límite es solo un polinomio en esta cantidad; pero generalmente se sabe que es lineal).
- La estrategia minimax de profundidad primero utilizará el tiempo de cálculo proporcional a la complejidad del árbol del juego, ya que debe explorar el árbol completo y una cantidad de polinomio de memoria en el logaritmo de la complejidad del árbol, ya que el algoritmo siempre debe almacenar un nodo de la complejidad del árbol. árbol en cada posible profundidad de movimiento, y el número de nodos en la mayor profundidad de movimiento es precisamente la complejidad del árbol.
- La inducción hacia atrás utilizará tanto la memoria como el tiempo proporcionalmente a la complejidad del espacio de estado, ya que debe calcular y registrar el movimiento correcto para cada posición posible.
Ejemplo: tic-tac-toe (ceros y cruces)
Para tic-tac-toe , un límite superior simple para el tamaño del espacio de estados es 3 9 = 19,683. (Hay tres estados para cada celda y nueve celdas). Este recuento incluye muchas posiciones ilegales, como una posición con cinco cruces y sin ceros, o una posición en la que ambos jugadores tienen una fila de tres. Un recuento más cuidadoso, eliminando estas posiciones ilegales, da 5.478. Y cuando las rotaciones y reflexiones de posiciones se consideran idénticas, solo hay 765 posiciones esencialmente diferentes.
Para delimitar el árbol del juego, hay 9 posibles movimientos iniciales, 8 posibles respuestas, y así sucesivamente, ¡de modo que hay como máximo 9! o 362,880 juegos en total. Sin embargo, los juegos pueden tardar menos de 9 movimientos en resolverse, y una enumeración exacta da 255,168 juegos posibles. Cuando las rotaciones y reflejos de posiciones se consideran iguales, solo hay 26.830 juegos posibles.
La complejidad computacional del tic-tac-toe depende de cómo se generalice . Una generalización natural es m , n , k -juegos : se juega en un tablero de m por n y el ganador es el primer jugador en obtener k seguidos. Inmediatamente queda claro que este juego se puede resolver en DSPACE ( mn ) buscando en todo el árbol del juego. Esto lo coloca en la clase de complejidad importante PSPACE . Con un poco más de trabajo, se puede demostrar que está completo en PSPACE .
Complejidades de algunos juegos conocidos
Debido al gran tamaño de las complejidades del juego, esta tabla da el techo de su logaritmo a base 10. (En otras palabras, el número de dígitos). Todos los siguientes números deben considerarse con precaución: cambios aparentemente menores en las reglas de un juego pueden cambiar los números (que a menudo son estimaciones aproximadas de todos modos) por factores tremendos, que fácilmente podrían ser mucho mayores que los números mostrados.
Nota: ordenado por tamaño de árbol de juego
Juego | Tamaño de la placa
(posiciones) |
Complejidad del espacio de estados
(como logaritmo a base 10) |
Complejidad del árbol de juegos
(como logaritmo a base 10) |
Duración media del juego
( pliegues ) |
Factor de ramificación | Árbitro | Clase de complejidad del juego generalizado adecuado |
---|---|---|---|---|---|---|---|
Tic-tac-toe | 9 | 3 | 5 | 9 | 4 | PSPACE-completo | |
Sim | 15 | 3 | 8 | 14 | 3,7 | PSPACE-completo | |
Pentominós | 64 | 12 | 18 | 10 | 75 | ?, pero en PSPACE | |
Kalah | 14 | 13 | 18 | 50 | La generalización no está clara | ||
Conectar cuatro | 42 | 13 | 21 | 36 | 4 | ?, pero en PSPACE | |
Dominante (8 × 8) | 64 | 15 | 27 | 30 | 8 | ?, pero en PSPACE ; en P para determinadas dimensiones | |
Congkak | 14 | 15 | 33 | ||||
Borradores en inglés (8x8) (damas) | 32 | 20 o 18 | 40 | 70 | 2.8 | EXPTIME-complete | |
Awari | 12 | 12 | 32 | 60 | 3,5 | La generalización no está clara | |
Qubic | 64 | 30 | 34 | 20 | 54,2 | PSPACE-completo | |
Puente falso doble | (52) | <17 | <40 | 52 | 5,6 | PSPACE-completo | |
Fanorona | 45 | 21 | 46 | 44 | 11 | ?, pero en EXPTIME | |
Morris de nueve hombres | 24 | 10 | 50 | 50 | 10 | ?, pero en EXPTIME | |
Tablut | 81 | 27 | |||||
Borradores internacionales (10x10) | 50 | 30 | 54 | 90 | 4 | EXPTIME-complete | |
Damas chinas (2 juegos) | 121 | 23 | 180 | EXPTIME -completo | |||
Damas chinas (6 juegos) | 121 | 78 | 600 | EXPTIME -completo | |||
Reversi (Otelo) | 64 | 28 | 58 | 58 | 10 | PSPACE-completo | |
OnTop (juego base 2p) | 72 | 88 | 62 | 31 | 23,77 | ||
Líneas de acción | 64 | 23 | 64 | 44 | 29 | ?, pero en EXPTIME | |
Gomoku (15x15, estilo libre) | 225 | 105 | 70 | 30 | 210 | PSPACE-completo | |
Hexagonal (11x11) | 121 | 57 | 98 | 50 | 96 | PSPACE-completo | |
Ajedrez | 64 | 44 | 123 | 70 | 35 | EXPTIME-complete (sin regla de dibujo de 50 movimientos ) | |
Bejeweled y Candy Crush (8x8) | 64 | <50 | 70 | NP-duro | |||
GIPF | 37 | 25 | 132 | 90 | 29,3 | ||
Conectar6 | 361 | 172 | 140 | 30 | 46000 | PSPACE-completo | |
Chaquete | 28 | 20 | 144 | 55 | 250 | La generalización no está clara | |
Xiangqi | 90 | 40 | 150 | 95 | 38 | ?, se cree que es EXPTIME-complete | |
Abulón | 61 | 25 | 154 | 87 | 60 | PSPACE-hard , y en EXPTIME | |
Havannah | 271 | 127 | 157 | 66 | 240 | PSPACE-completo | |
Twixt | 572 | 140 | 159 | 60 | 452 | ||
Janggi | 90 | 44 | 160 | 100 | 40 | ?, se cree que es EXPTIME-complete | |
Quoridor | 81 | 42 | 162 | 91 | 60 | ?, pero en PSPACE | |
Carcassonne (juego base 2p) | 72 | > 40 | 195 | 71 | 55 | La generalización no está clara | |
Amazonas (10x10) | 100 | 40 | 212 | 84 | 374 o 299 | PSPACE-completo | |
Shogi | 81 | 71 | 226 | 115 | 92 | EXPTIME-complete | |
Thurn y Taxis (2 j.) | 33 | 66 | 240 | 56 | 879 | ||
Ir (19x19) | 361 | 170 | 360 | 150 | 250 | EXPTIME-complete | |
Arimaa | 64 | 43 | 402 | 92 | 17281 | ?, pero en EXPTIME | |
Stratego | 92 | 115 | 535 | 381 | 21.739 | ||
Ajedrez infinito | infinito | infinito | infinito | infinito | infinito | Desconocido, pero mate-in-n es decidible | |
Magia: el encuentro | Infinito | Ilimitado | Ilimitado | infinito | infinito | AH-duro |
Notas
Referencias
Ver también
- Ir y matemáticas
- Juego resuelto
- Resolviendo ajedrez
- Número de Shannon
- lista de juegos y rompecabezas NP-complete
- lista de juegos y rompecabezas completos de PSPACE