Poda alfa-beta

Poda alfa-beta

Poda alfa-beta

Ejemplo de poda alfa-beta

La poda alfa beta es una técnica de búsqueda que reduce el número de nodos evaluados en un árbol de juego por el algoritmo Minimax. Se trata de una técnica muy utilizada en programas de juegos entre adversarios como el ajedrez, el tres en raya o el Go.

Entre los pioneros en el uso de esta técnica encontramos a Arthur Samuel, D.J Edwards y T.P. Hart,[1] Alan Kotok,[2] Alexander Brudno[3] , Donald Knuth y Ronald W. Moore[4]

El problema de la búsqueda Minimax es que el número de estados a explorar es exponencial al número de movimientos. Partiendo de este hecho, la técnica de poda alfa-beta trata de eliminar partes grandes del árbol, aplicándolo a un árbol Minimax estándar, de forma que se devuelva el mismo movimiento que devolvería este, gracias a que la poda de dichas ramas no influye en la decisión final.

Contenido

Desarrollo del algoritmo

La búsqueda minimax es primero en profundidad, por ello en cualquier momento sólo se deben considerar los nodos a lo largo de un camino en el árbol.

La poda alfa-beta toma dicho nombre de la utilización de dos parámetros que describen los límites sobre los valores hacia atrás que aparecen a lo largo de cada camino.

  • α es el valor de la mejor opción hasta el momento a lo largo del camino para MAX, esto implicará por lo tanto la elección del valor más alto
  • β es el valor de la mejor opción hasta el momento a lo largo del camino para MIN, esto implicará por lo tanto la elección del valor más bajo.

Esta búsqueda alfa-beta va actualizando el valor de los parámetros según se recorre el árbol. El método realizará la poda de las ramas restantes cuando el valor actual que se está examinando sea peor que el valor actual de α o β para MAX o MIN, respectivamente.

El desarrollo del algoritmo en pseudocódigo será el siguiente:

función alfabeta(nodo, profundidad, α, β)         
    si nodo es un nodo terminal o profundidad = 0
        devolver el valor heurístico del nodo
    para cada hijo de nodo
        α := max(α, -alfabeta(hijo, profundidad-1, -β, -α))     
        si β≤α
            break
    devolver α

(* Llamada inicial *)
alfabeta(origen, profundidad, -infinito, +infinito)

Ejemplo de poda alfa-beta

La figura muestra un ejemplo de la poda alfa-beta. Cada nivel representa la jugada de los jugadores MAX y MIN, que tendrán que definir un valor α o β respectivamente.

A continuación se presenta un ejemplo de aplicación del algoritmo para el árbol de la figura. En ella los nodos podados al aplicar el algoritmo se presentan sombreados en gris.

Comenzamos con la búsqueda de primero en profundidad. El padre de los nodos hoja más a la izquierda, etiquetados con 5 y 6 respectivamente, deberá escoger un valor β al tratarse de un nivel MIN, esto implica que deberá escoger el valor mínimo entre dichos nodos, es decir 5.

Siguiendo el desarrollo, se expandirán el resto de sucesores del padre. En este caso se expande el camino que conduce a los nodos hoja 7 y, buscando un valor β menor, el nodo etiquetado con 4. En este momento el valor momentáneo de β en ese nivel es 4 (el mínimo entre 7 y 4). Esto implica que en este momento en el nivel superior, el padre del nodo que etiquetamos anteriormente con β igual a 5, y de este β igual a 4 momentáneo, debe decidir el mejor valor, el más alto al encontrarse en un nivel MAX), si siguiéramos expandiendo hijos del nodo MIN padre de 7 y 4, sólo podríamos conseguir valores menores a 4, lo que seguiría implicando una elección de la jugada izquierda en el nivel MAX, por lo tanto, podemos podar el resto de hijos, tal y como se muestra en la Figura.

El resto del desarrollo del árbol se seguiría utilizando los criterios mencionados con anterioridad.

Eficacia de la poda alfa-beta

La eficacia de la poda alfabeta depende del orden en el que se examinan los sucesores, es decir, el algoritmo se comportará de forma más eficiente si examinamos primero los sucesores que probablemente serán los mejores.

Si esto pudiera hacerse, implicaría que alfa-beta sólo tendría que examinar O(bd / 2) en lugar de los O(bd) de Minimax. Esto implica que el factor de ramificación eficaz será de \sqrt{b} en lugar de b. En otras palabras, alfa-beta podría mirar hacia delante aproximadamente dos veces más que Minimax en la misma cantidad de tiempo.

Si se recurre a una ordenación aleatoria en lugar de primero el mejor en los sucesores, el número aproximado de nodos examinados sería de O(b3d / 4) para un valor moderado de b. En ajedrez se puede realizar una función de ordenación sencilla teniendo en cuenta primero capturas de fichas, después amenazas, movimientos hacia delante y por último movimientos hacia detrás, esto conseguiría aproximadamente un factor de dos del resultado O(bd / 2) del mejor caso. La inclusión de esquemas dinámicos para ordenar movimientos, basados en experiencia podrían acercarse al límite teórico.[5]

Referencias

  1. Richards, D.J. and Hart, T.P. (4 December 1961 to 28 October 1963). «The Alpha-Beta Heuristic (AIM-030)». Massachusetts Institute of Technology. Consultado el 2006-12-21.
  2. Kotok, Alan (XHTML 3 December 2004). «MIT Artificial Intelligence Memo 41». Consultado el 2006-07-01.
  3. Marsland, T.A. (May de 1987). «Computer Chess Methods (PDF) from Encyclopedia of Artificial Intelligence. S. Shapiro (editor)» (PDF) págs. 159-171. J. Wiley & Sons. Consultado el 2006-12-21.
  4. Knuth, D. E., and Moore, R. W. (1975). «An Analysis of Alpha-Beta Pruning» Artificial Intelligence Vol. 6, No. 4. pp. 293–326.
  5. Russell, S.J; Norving, P. (2004). Inteligencia Artificial. Un enfoque moderno. Pearson Educación. ISBN 84-205-4003-Z.

Obtenido de "Poda alfa-beta"

Wikimedia foundation. 2010.

Игры ⚽ Поможем сделать НИР

Mira otros diccionarios:

  • Negascout — es una variante del algoritmo Minimax, es un algoritmo que combina la relación matemática del Negamax y el uso de ventana nula. También llamado búsqueda de la variante principal este algoritmo puede ofrecer rendimientos incluso mayores a la poda… …   Wikipedia Español

  • Houdini (ajedrez) — Houdini es un motor de ajedrez UCI gratuito para Windows escrito por el belga Robert Houdart.[1] Está escrito en C++. Según el autor el nombre Houdini se debe a la tenacidad que tiene el programa y en su habilidad de defenderse testarudamente en… …   Wikipedia Español

  • Minimax — Para otros usos de este término, véase Minimax (infantil). En teoría de juegos, Minimax es un método de decisión para minimizar la pérdida máxima esperada en juegos con adversario y con información perfecta. Minimax es un algoritmo recursivo. El… …   Wikipedia Español

  • Función de evaluación — La función de evaluación, también conocida como función de evaluación heurística, es una algoritmo usado generalmente por programas que saben jugar juegos de estrategia como el Ajedrez (denominados motores de ajedrez), Go entre otros para estimar …   Wikipedia Español

  • Ajedrez por computadora — GNU Chess 5.07 en interface WinBoard 4.2.7. En el siglo XVIII empezó a difundirse la idea de crear una computadora capaz de jugar al ajedrez. En el año 1769, un jugador de ajedrez autómata llamado El Turco[1] …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”