En informática , estructuras de datos de árbol y teoría de juegos , el factor de ramificación es el número de hijos en cada nodo , el grado externo . Si este valor no es uniforme, se puede calcular un factor de ramificación promedio .
Por ejemplo, en el ajedrez , si un "nodo" se considera una posición legal, se ha dicho que el factor de ramificación promedio es de aproximadamente 35, [1] [2] y un análisis estadístico de más de 2.5 millones de juegos reveló un promedio de 31. [3] Esto significa que, en promedio, un jugador tiene alrededor de 31 a 35 movimientos legales a su disposición en cada turno. En comparación, el factor de ramificación promedio para el juego Go es 250. [1]
Los factores de ramificación más altos hacen que los algoritmos que siguen cada rama en cada nodo, como las búsquedas exhaustivas de fuerza bruta , sean computacionalmente más costosos debido al número de nodos que aumenta exponencialmente , lo que lleva a una explosión combinatoria .
Por ejemplo, si el factor de ramificación es 10, habrá 10 nodos un nivel hacia abajo desde la posición actual, 10 2 (o 100) nodos dos niveles hacia abajo, 10 3 (o 1,000) nodos tres niveles hacia abajo, y así sucesivamente. Cuanto mayor sea el factor de ramificación, más rápido se producirá esta "explosión". El factor de ramificación se puede reducir mediante un algoritmo de poda .
El factor de ramificación promedio se puede calcular rápidamente como el número de nodos no raíz (el tamaño del árbol, menos uno; o el número de bordes) dividido por el número de nodos no hoja (el número de nodos con hijos).
Ver también
Referencias
- ↑ a b Levinovitz, Alan (12 de mayo de 2014). "El misterio de Go, el antiguo juego que las computadoras aún no pueden ganar" . Cableado . Consultado el 2 de junio de 2014 .
La velocidad a la que aumentan las posibles posiciones está directamente relacionada con el "factor de ramificación" de un juego, o el número medio de movimientos disponibles en un turno determinado. El factor de ramificación del ajedrez es 35. Go's es 250. Los juegos con factores de ramificación altos hacen que los algoritmos de búsqueda clásicos como minimax sean extremadamente costosos.
- ^ Laramée, François Dominic (6 de agosto de 2000). "Programación de ajedrez Parte IV: Búsqueda básica" . GameDev.net . Consultado el 1 de mayo de 2007 .
- ^ Barnes, David. "¿Cuál es el número promedio de movimientos legales por turno?" . Intercambio de pila de ajedrez . Consultado el 1 de junio de 2019 .