3.1 Alfa-Beta [Inteligencia Artificial]

Alfa-Beta es una técnica que nos permite ignorar las secciones enteras de el árbol de juego, pero aun así obtener la misma respuesta que con Minimax. Ósea que Alfa-Beta nunca cambia la respuesta pero es más eficiente que Minimax.

Vamos a ver el árbol Minimax.
En el nivel tres de la junta de aislamiento de cinco movimientos.


Vamos a suponer que nuestro jugador de la computadora está evaluando el árbol de juego de izquierda a derecha.
Tenemos cinco sub árboles que vamos a tener en cuenta. En cuanto más a la izquierda este uno, la primera rama tiene solo dos nodos con valores de 1 y 2 respectivamente. Es el nivel máximo, elegir los dos y propagar el resultado hasta el nivel medio.

Desde el oponente "X" elegirá una rama que minimiza el valor, sabemos que este sub árbol tendrá un valor de 2 o menos. Por lo que significa que cualquiera de las ramas restantes, tan pronto como vemos a 2 o más, podríamos ignorar el resto de los nodos, ya que nunca serán seleccionados.

Y tenemos 2s en el nodo más a la izquierda de estas tres ramas. Lo que significa que podemos dejar de lado 6 de estos 11 nodos. Eso va a ahorrar algo de tiempo.


Se puede hacer aún mejor, veamos el siguiente sub árbol más.
Tan pronto como llegamos a dos en la rama izquierda, sabemos que todo este sub árbol va a devolver un 2 o menos.


Pero ya sabemos que tenemos un 2 partir del primer sub árbol. Así en el nodo más alto, ya sabemos que vamos a obtener un 2 o más.
Eso significa que podemos ignorar todas las ramas restantes del segundo sub árbol.


Pasando al árbol medio, que de nuevo obtenemos un dos en el nodo más a la izquierda.


Así que seguimos explorando y conseguimos otro 2, ningún otro movimiento valido es posible, por lo que este nodo devuelve un máximo de 2.
Ahora, el nodo de arriba es un nodo de minimización, por lo que debe devolver un 2 o menos.


Por lo tanto, por que ya sabemos que la mayor parte del nivel superior ya tiene una rama con un 2 que puede pasar por alto todo el resto de los nodos en este sub árbol.


¿Se observa un patrón aquí?
Con el cuarto sub árbol, también se obtiene un 2 desde el principio, que significa que podemos ignorar la mayor parte de los nodos de este sub árbol también.


Y lo mismo sucede en el último sub árbol.


Espera este sub árbol es uno de los malos movimientos. Su valor es en realidad 1.
No queremos que nuestro jugador de computadora siga esta rama. Mientras siga la rama correcta está bien. Aunque no tenemos que preocuparnos por eso ya que como nuestro ordenador seleccionara la rama más a la izquierda. Asumiendo que así sea.

Si estamos asumiendo que nuestro objetivo era jugar el juego, no mantenga una lista de todos los movimientos en un nivel dado, en cuanto al árbol, parece que no es necesario mirar la mayoría de los nodos.
Tan solo hay que mirar a 29 de los 78 nodos en todo el árbol. Esto ahorrara mucho tiempo.

Mientras nuestro algoritmo se ejecuta en B a la hora d, minimax con Alfa-Beta puede ejecutar b al d de más de dos tiempos di los nodos se ordenan de forma óptima con las mejores jugadas para ser el primero.

Incluso con movimiento aleatorio de pedidos, Alfa-Beta reduce la espera del tiempo de ejecución que es b a las tres cuartas partes d.

---

Rellene los valores de este árbol Minimax, recuerde, el nodo raíz es el nivel máximo.

---