INTRODUCCIÓN
Poda alfa-beta surgió como mejora del algoritmo minimax. Este
algoritmo es capaz de reducir significativamente el número de nodos evaluados
en un árbol de juegos y es una técnica muy usada en juegos entre adversarios
como por ejemplo: el ajedrez, tres en raya y otros.
DESARROLLO
¿QUÉ ES PODA ALFA-BETA?
El poda alfa-beta es una mejora del algoritmo minimax, y
se puede calcular una decisión mínima correcta y es posible aplicarlo a arboles
de cualquier profundidad. Emplea la búsqueda primero en profundidad para
considerar los nodos que se encuentran a lo largo del camino.
Existen dos jugadores en:
·
Maximizador
·
Minimizador
Y existen dos valores que son:
·
Alfa
·
Beta
Estos valores ayudan en la búsqueda, lo que mejora la búsqueda
y mejorando la velocidad sin que se pierda la información
CARACTERÍSTICAS
DE LA PODA ALFA-BETA
·
Omite la expansión de
nodos donde los valores no son los mejores.
·
La búsqueda se para
en algún nivel y se realizan evaluaciones heurísticas.
·
Si el valor del nodo
MAX es decir alfa, es menor que el más alto hasta este momento, entonces omitir
nodo.
·
Si el valor nodo MIN es
decir, beta es mayor que el nodo más bajo hasta el momento, entonces
omitir nodo.
·
El algoritmo
alfa-beta permite una búsqueda más completa.
·
En este algoritmo
solo importa el orden y no los valores exactos.
·
Poda alfa-beta nos
lleva al resultado final.
·
Alfa-beta es una
mejora del algoritmo Minimax que evita revisar aquellos nodos donde la
información no es útil en la jugada.
La búsqueda se realiza en profundidad y avanza de forma
ordenada y usa la información para podar las ramas.
ESTRUCTURAS DE DATOS
Dos variables que
se deben ser recordadas durante la búsqueda:
·
Alfa: limite inferior encontrando hasta ese momento.
·
Beta: limite superior.
·
En los niveles maximizantes MAX, se usa beta para podar.
·
En los niveles MIN, se usa alfa para podar.
·
Alfa-beta es muy usado para busqueda en árboles de juegos.
CONCLUSIÓN
Poda alfa beta es una mejora del algoritmo minimax que
evita recorrer todos los nodos del árbol lo cual mejora la velocidad y no se
pierde la información. El poda alfa-beta usa dos valores para obtener sus propósitos:
alfa y beta.
BIBLIOGRAFÍA
López, B. 2009. Poda Alfa-Beta. (En
línea). ME. Consultado, 20 de NOV. 2015. Formato PDF. Disponible en: http://www.itnuevolaredo.edu.mx/takeyas/
Solano, R. 2008. Poda Alfa-Beta. (En
línea). EC. Consultado, 20 de nov. 2015. Formato PDF. Disponible en: http://es.slideshare.net/rfsolano/
poda-alfa-beta
No hay comentarios:
Publicar un comentario