Algoritmo alfa beta

xd2

1. IMPLEMENTACIÓN DEL ALGORITMO ALFA-BETA EDWIN VEGA 4-807-1261 INTELIGENCIA ARTIFICIAL

2. PODA ALFA-BETA Es una implementación o mejora para el algoritmo MiniMax . Soluciona el problema de la búsqueda MiniMax : el número de estados que tiene que examinar es exponencial con el número de movimientos. El exponente no se puede eliminar, pero se puede dividir en la mitad. Es posible calcular la decisión MiniMax correcta sin mirar todos los nodos en el árbol. La poda Alfa-Beta permite eliminar partes grandes del árbol, sin influir en la decisión final.

3. PODA ALFA-BETA Los dos parámetros alfa y beta describen los límites sobre los valores que aparecen a lo largo del camino: α = el valor de la mejor opción (el más alto) que se ha encontrado hasta el momento en cualquier punto del camino, para MAX. β = el valor de la mejor opción (el más bajo) que se ha encontrado hasta el momento en cualquier punto del camino, para MIN. La búsqueda Alfa-Beta actualiza el valor de α y β según se va recorriendo el árbol y termina la recursión cuando encuentra un nodo peor que el actual valor α o β correspondiente.

4. EJEMPLO DE PODA ALFA-BETA

5. EJEMPLO DE PODA ALFA-BETA

6. EJEMPLO DE PODA ALFA-BETA

7. ALGORITMO ALFA-BETA El desarrollo del algoritmo sería el siguiente:

8. ALGORITMO ALFA-BETA Tenemos la creación de la función para nuestro algoritmo “alfa-beta”. Se pregunta si el valor del nodo es una hoja, si lo es se devuelve su valor para comparar. Luego se pregunta cual de los jugadores esta jugando, para elegir si realizar la comparación Max para Alfa ó Min para Beta, dependiendo si está jugando el oponente (humano) o el mismo (computador).

9. ALGORITMO ALFA-BETA Aquí vemos el algoritmo a la hora de realizar el recorrido Max para Alfa. En la que Alfa va a contener siempre el mejor valor del recorrido de los nodos para Max. Pero luego, se pregunta si Beta es menor o igual a Alfa, o bien, si Alfa es mayor que Beta se procede inmediatamente a podar los demás nodos Beta. De esta manera esto nodos no se recorrerán, compararán o visitarán innecesariamente. Y luego, se establece el valor de Alfa como el mejor valor del nodo Max.

10. ALGORITMO ALFA-BETA Aquí vemos el mismo caso que el anterior solo que para el recorrido de nodos Min para Beta. Igualmente se pregunta si Alfa es mayor que Beta se procede a podar esta vez los nodos Alfa que quedan, ya que estamos analizando un nodo Min. Y finalmente, se establece el valor de Beta como el mejor valor del nodo Min.

11. CÓDIGO DEL ALGORITMO EN C++

12. CÓDIGO DEL ALGORITMO EN C++

13. CÓDIGO DEL ALGORITMO EN C++

14. EJECUCIÓN DEL ALGORITMO EN C++ Aquí vemos que de un conjunto de valores o nodos en forma de árbol, se realiza la búsqueda por medio del algoritmo Alfa-Beta. Se encuentra que el valor más óptimo de esos ocho valores de los nodos es el valor 5, en este caso por ejemplo.

15. MUCHAS GRACIAS 2020