1.5 Factor de ramificación II [Inteligencia Artificial]

Cuantos nodos cree que el algoritmo Minimax tendrá que visitar en el árbol de juego.

Si se dio cuenta podemos aproximar el número de nodos de Minimax utilizando la formula b^d.
Donde "b" es el factor de ramificación promedio, y "d" es la profundidad media.

El factor de ramificación promedio parece ser alrededor de 8. Así que ahora obtendremos una estimación de 8 a 25 de los nodos.
Eso es aproximadamente de 10 a 22 de los nodos.
Eso significa que solo tenemos que esperar alrededor de 1,2 millones de años para obtener una respuesta.
Eso significa que tenemos que ser más inteligentes acerca de cómo hacer un jugador de computadora para jugar aislamiento.

El crecimiento exponencial del árbol de juego significa que no podemos hacer fuerza bruta, el problema y la búsqueda del final del juego con facilidad.
En general, los juegos más interesantes no se podrán buscar hasta el final.
O bien el factor de ramificación es demasiado grande, o la profundidad, o ambas.

Cuando el número de nodos, el cual se puede estimar por el factor de ramificación de la potencial profundidad, comienza a ser comparable con el número de segundos restantes en una vida del universo. Sabemos que estamos en problemas.

Esperar un jugador en un juego de ordenador para hacer un movimiento no es divertido
Después de dos segundos de espera un jugador humano es probable que empieza a pensar en otras cosas.


Realmente necesitamos una manera de elegir un movimiento rápido.
Vamos a suponer que una vez más podemos buscar diez a la novena nodos por segundo.


Así que en dos segundos en realidad podemos buscar dos veces diez a la novena nodos.
Así que tenemos que resolver la ecuación de ocho a la X es menos que dos veces diez a la novena.


Podemos hacer esto tomando logaritmo en base ocho en ambos lados.
Logaritmo en base ocho es bastante molesto.
Si, es tiempo para llevar a cabo algunas habilidades matemáticas.
Sabemos que el log de X es igual al log b^x sobre el log de b^a.


Así que podemos usar esa fórmula para resolver nuestro problema.
Vamos a utilizar logaritmo en base diez aquí por conveniencia.
Así que terminamos con X es menor que logaritmo en base diez de dos veces diez a la novena sobre logaritmo en base diez de ocho.


Y terminamos siendo X menos de 10,3

¿Asi que debemos estar bien si solo buscamos diez niveles de profundidad?
Siempre que nuestra estimación de un factor de ramificación de ocho años en promedio es bueno.
Para estar seguros vamos solo con la profundidad de nueve.
Esta idea no solo va tan lejos como pensamos que podemos para cumplir con seguridad nuestro plazo, se llama una búsqueda limitada de profundidad.


Muy bien pero ¿Que hacemos cuando lleguemos a nivel nueve de nuestro árbol de Minimax?
Aquí es cuando las cosas se ponen interesantes.
Queremos evaluar la bondad de un nodo en el nivel nueve sobre la base de lo mucho que esperamos que lleve a una victoria para nuestro jugador de la computadora.

Podemos crear una función de evaluación que toma en cada tablero de juego que genero el nivel nueve de nuestro árbol de juego de Minimax, devolver un número que podemos utilizar para comparar ese nodo para todos los otros nodos a ese nivel.
Sabemos que la única manera de ganar es saber si nuestro jugador de la computadora tiene movimiento a la izquierda al final del juego.

Puede que nuestro jugador de la computadora no debe maximizar el número de movimientos que tiene.
Queremos una función de evaluación que devuelva un número mayor dependiendo de qué tan buena es la jugada para nuestro jugador de la computadora.
Con una función de evaluación simplemente contando el número de movimientos de nuestro jugador de la computadora que tiene disponible en un nodo dado, el jugador seleccionara ramas en el árbol Minimax, que conduce a espacios en los que un jugador tiene más opciones.
Vamos a llamar a la función de evaluación, numero de mis movimientos para mayor comodidad.


Ejercicio

A manera de práctica, colocar junto a cada tabla, el número de movimientos dependiendo la posición de cada uno, ya sea 1 o 2.

---