PODA ALFA-BETA

Mejora del Algoritmo Minimax; aplicado en juegos de adversarios por turnos.

Se aplica en espacios de estados demasiado grandes como para analizar todos los nodos.

La información es imperfecta; es decir, no se conoce el estado del contrincante.

Por ejemplo: En juegos donde no se ve el tablero del adversario.

Características de la Poda Alfa-

Beta

• Omitir la expansión de nodos que por sus valores no pueden ser los mejores (peores).
• Interrumpe la búsqueda en algún nivel y aplica evaluaciones heurísticas a las hojas (profundidad limitada.
• Si el valor del nodo MAX (alfa) es menor que el más alto hasta este momento, entonces omitir nodo.
• SI el valor del nodo MIN (beta) es mayor que el nodo más bajo hasta el momento, entonces omitir nodo.
• Alfa-Beta permite búsqueda dos veces más profunda.
• Ordenamiento de los operadores, resultante del conocimiento o experiencia.
• Únicamente importa el orden y no los valores exactos.
• La poda no afecta al resultado final.
• Alfa-Beta es una mejora del algoritmo Minimax que evita revisar porciones dominadas del árbol, que no pueden proveer información útil sobre la jugada siguiente.

Alfa-Beta es un algoritmo de búsqueda en profundidad, rama y cota, que avanza por el árbol en un orden ya fijado (p.ej., de izquierda a derecha) y va usando la información de la valuación de los nodos hoja para podar ramas dominadas que no sirven para cambiar el valor Minimax del nodo inicio (la jugada inminente).