1.4 Factor de ramificación [Inteligencia Artificial]

La respuesta del ejercicio anterior

---

Número máximo de nodos visitados

Hasta ahora hemos trabajado con un tablero de aislamiento con solo cinco movimientos posibles.
Se busca poner fin al juego, esto causo enormes árboles que son difíciles de mostrar en la pantalla.
¿Qué tan malo va a ser con un tablero de juego normal?
Bueno vamos a regresar el tablero cinco por cinco.


¿Cuantos nodos diferentes de ramificaciones podemos esperar?
En el primer movimiento, "O" puede poner su pieza en cualquiera de los 25 lugares.
En el siguiente movimiento "X" puede poner su pieza en cualquiera de los 24 lugares.
Después hay 23 lugares vacíos, seguido por 22 lugares y así sucesivamente.
Ahora todos esto puntos son siempre posibles movimientos, por lo que sabemos que tiene que haber menos nodos que 25 x 24 x 23 y así sucesivamente. Por lo menos 25 nodos factoriales.
10^25
Si se utiliza un procesador multi-nucleo que trabaje a gigahercios moderado que pueda hacer las operaciones de 9° por segundo, se tardara 10^16 para buscar en todo el juego.


De acuerdo, cada hora es de 3600 segundos y cada día es de 24 horas y cada año tiene 365 días. Eso significa que más de 300 millones de años.
Exactamente 317, 097, 920 años
No creo que tengamos tiempo para esperar mucho.
Me acaba de dar una estimación rápida del límite superior del número de nodos, en realidad no es tan malo.

Vamos a ver si podemos hacer una mejor estimación.
No hay mucho que podamos hacer los primeros movimientos.
Realmente hay 25 x 24 potenciales primeros movimientos.
Pero después de eso, cada pieza se mueve con una reina y hay menos movimientos.
¿Cuál es el número máximo de movimientos posibles en el tercer movimiento de juego?

La posición central es el primer movimiento que permite ir a una de las 16 posiciones diferentes en su siguiente turno. Claro esto asumiendo que los movimientos del oponente no obstruyan.


Suponiendo que el oponente no está en el camino, la posición central tiene un máximo potencial ya que se mueve con 16 posibilidades.

El factor de ramificación

Mientras que la posición central tiene 16 espacios en los que se puede mover, la mayoría de las otras posiciones tienen 12 o menos.
A medida que el juego se desarrolla, tendremos cada vez menos espacios para que nuestro jugador pueda moverse.
Eso significa que podemos hacer una mejor estimación de la cantidad de nodos que tenemos.
Sabemos que no podemos tener más de 25 movimientos en un juego.
Esa es la profundidad máxima que nuestro árbol va a tener.
Y sabemos cuántos movimientos se pueden hacer en un principio,
Lo que deja 23 se mueve a la izquierda.

Sabemos que cada movimiento después de los dos primeros va a tener por lo general 12 o un menor número de movimientos disponibles. Vamos a llamar a esto el factor de ramificación.
En el peor de los casos vamos a esperar 25 veces 24 veces 12 a la 23n nodos en nuestro árbol de juego. Esto da más de 10^27.

Tal vez podemos mejorar nuestra estimación más.
Sabemos que al final del el juego hay que ser progresivamente menos movimientos disponibles.
Hay cero movimientos al final, antes de un movimiento que un máximo de dos antes de que tres antes de eso, y así sucesivamente.

Así que para los últimos movimientos, suponiendo un factor de ramificación de 12 es demasiado.
Eso sería alrededor del 10 a los 13 nodos
Pero el máximo que podría ser es 12 factorial, o aproximadamente 5 veces 10 a la octava.
Supongo que podríamos hacer de nuevo nuestra estimación como 25 veces 24 veces 13 12s en una fila, 5 veces 10 a la octava eso es aproximadamente igual a 3 veces 10^23. Eso es mejor que 10^25, o 10^27, pero parece que hubiera sido un grave sobreestimar como con la mayoría de las ramas tendrán mucho menor que el máximo factor de ramificación.

---