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.
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. [1]
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.
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.