PODA ALFA - BETA

Este algoritmo es el más utilizado en las aplicaciones referidas a juegos, dada su excepcional utilidad en el aumento de la velocidad de la búsqueda sin producir pérdida de la información. Es una extensión en particular del algoritmo de Búsqueda Minimax en juegos de dos contrincantes.

Cada vez que se evalúa un nodo u hoja, el algoritmo determina s los nuevos hijos generados pueden generar una mejor utilidad de la que ya posee el nodo estudiado y si afecta al nodo padre. De no ser así, eso significa que seguir analizando esa rama es desperdiciara recursos como tiempo y espacio, por lo cual no se sigue generando y simplemente se le poda, de allí el nombre.

El algoritmo 2, muestra como es el desarrollo para una búsqueda por medio de la Poda Alpha –Beta. Se detalla las entradas. Para ingresar al algoritmo, se necesita ingresar el nodo a ser evaluado, del que se obtendrá su utilidad, así como la utilidad del padre para evaluar si es que la nueva utilidad afecta o no al nodo padre. De no ser así, se procederá a podar la rama [6].

Una vez podada la rama, la nueva utilidad será la última en ser registrada o actualizada. Esto se da mediante la variable fNodo, que contiene la función de utilidad del nodo ingresado [7].

Algoritmo Poda Alpha–Beta

Entrada:
- Nodo, fNodoP
Salida:
- fNodo
----------------------------------------------------------------------------------------
Si nodo es MAX
     fNodo <- -inf
De lo contrario
     fNodo <- inf
fin si
Si nodo es hoja
 fNodo <- utilidadNodo(nodo)
de lo contrario
   para cada ficha fi que se pueda mover
      para cada accion aj de fi
          nodoH <- crear nodo con ai
          nodoH <- PodaAb(nodoH,fNodo)
          si nodo es MAX
                si fHijo> fNodo
                            fNodo<- fHijo
                            si fNodo>=fNodoP
                                    eliminar fNodo
                                    retorna null;
                             fin si
                fin si
           fin si
           si nodo es MIN
                    si fHijo < fNodo
                           fNodo<- fHijo
                           si fNodo=<fNodoP
                                 eliminar fNodo
                                 retornar null;
                            fin si
                    fin si
           fin si
      fin para
  fin para
retorna nodo;
fin si