next up previous
Next: 3.3.2 Análisis Up: 3.3 Alpha-Beta Previous: 3.3 Alpha-Beta

3.3.1 Algoritmo Alfa-Beta


Tabla 3.4: Algoritmo Alfa-Beta.
\begin{table}
\begin{tabbing}
\emph{set} $\alpha = -\infty$ \\
\emph{set} $\be...
...\emph{sino} \emph{set} $k \leftarrow k + 1$ y continua
\end{tabbing}\end{table}


Figura 3.3: Ejemplo sencillo de la estrategia Alfa-Beta.
\begin{figure}\vspace*{1cm}
\centerline{\hbox{
\psfig{figure=games4.ps,height=6cm}
}}\end{figure}

Se puede hacer una definición más concisa usando neg-max.

La eficiencia de alpha-beta depende del orden de los valores de los nodos terminales.

Si construimos un programa que pueda evaluar 1,000 posiciones por segundo, con 150 segundos por movida, podríamos ver 150,000 posiciones. Con un factor de arborescencia de 35 nuestro programa podría ver solo 3 o 4 tiradas (ply) adelante y jugaría a nivel de novato.

Si pudieramos ordenar los nodos terminales tendríamos que examinar $O(b^{d/2})$, por lo que el factor de arborescencia efectivo es de $\surd b$ en lugar de $b$, en ajedrez sería 6 en lugar de 35, por lo que ahora podríamos buscar hasta profundidad 8.

A veces se usan ordenamientos sencillos, como considerar primero las capturas, luego las amenazas, luego movimientos hacia adelante y finalmente movimientos hacia atrás.

Otra estrategia es usar una búsqueda de profundidad iterativa y usar los últimos valores para decidir qué explorar en la siguiente iteración.

En promedio $\alpha-\beta$ permite explorar un 33% mas que un simple minimax.


next up previous
Next: 3.3.2 Análisis Up: 3.3 Alpha-Beta Previous: 3.3 Alpha-Beta
Eduardo Morales Manzanares 2004-11-02