Búscalo aquí:

Poda Alfa-Beta y Búsqueda Quiescense para el Ajedrez

En esta entrada se presentarán algunos conceptos básicos que permitirán construir un ajedrez inteligente que sea capaz de responder de manera acertada a cada jugada.

1. Introducción

El ajedrez es un juego que permite retar la habilidad y destreza de los oponentes. Casi gran parte de la capacidad de juego le atribuyen a la rapidez mental de sus jugadores y además la alta capacidad analítica en ese lapso de tiempo para decidir una jugada correcta que además permita poner en aprietos al rival.



Teniendo en cuenta los factores que definen el éxito en cada jugada como: la rapidez mental y la alta capacidad analítica, entonces, ¿acaso las máquinas podrían jugar el ajedrez?

Esto es una cuestión que ha sido analizada incluso desde que se crearon las primeras máquinas, en la década de 1940. Turing y Shanon comentaron sobre las posibilidades de las máquinas de poder competir con un ser humano. Éste último logró concebir las primeras bases sobre funciones de evaluación para efectuar la mejor jugada, además de parámetros más complejos que iban definiendo un comportamiento de juego, para la máquina, más sofisticado. Entre ellos, Shanon también definió que el comportamiento de las piezas al inicio de juego, no es el mismo que a la mitad de juego y al final. Un claro ejemplo es cuando el rey al inicio de juego no tiene mayor acción, sin embargo, al final de juego, el rey participa activamente matando u obstruyendo las últimas piezas enemigas del juego, además de tratar de no ser capturado.

Un inconveniente sobre este tema, es la relación entre la capacidad analítica del humano y la capacidad analítica de la máquina. Mientras que un ser humano puede deducir heurísticamente las posiciones más importantes del juego, la máquina tiene que efectuar una búsqueda completa de todas las posibles soluciones para poder decidir cuál de ellas, es la más apropiada; esto es lo que se denomina búsqueda de fuerza bruta.

No dudamos que la máquina pueda efectuar procesos muy rápidos,, más ahora que se cuenta con una gran capacidad de procesamiento, sin embargo el ajedrez trae más de un obstáculo.

2. Representación del Tablero
En el proceso de programar un juego de ajedrez que responda de manera inteligente , el primer problema con el que nos topamos es la representación del tablero.

La representacion correcta del tablero es muy fundamental, pues de ella dependerán la mayoria de las siguientes funciones que necesitemos implementar debido a qué en el tablero se encuentra toda la información que se refiere al juego como lo es conocer nuestras propias piezas y las de nuestro rival, conocer sus respectivas posiciones y saber cual es más valiosa que otra, etcétera.

Para un ser humano ésta es una tarea sencilla y se hace de manera tan automática que nos basta con darle un vistazo al tablero para abstraer toda ésta información. Sin embargo, para las máquinas las cosas no son tan sencillas, por lo que tenemos que optar una manera de representar ésta realidad compleja a una manera que le permita entender a la máquina. De ésta manera optamos por representar el tablero con una matriz de 8 filas por 8 columnas, que nos representarán las 64 casillas del tablero.

Cada elemento de la matriz tendrá asignado un valor el cual representará a una determinada pieza: 0 es una casilla vacía, 1 es un peon, 2 es un caballo, 3 un alfil, 4 torre, 5 es una dama y 6 un rey. Los valores positivos de las piezas es para las fichas blancas y sus contrapartes (fichas negras) se representarán con valores negativos. En la siguiente figura podemos observar la representación descrita.

3. Respondiendo con jugadas inteligentes: Poda Alfa-BetaEl objetivo de todo juego entre humano-máquina es qué, esta última responda eficientemente y "logre poner en aprietos" a su contricante y aún más "logre ganarle".

Pero, ¿cómo logramos que una máquina pueda jugar al ajedrez?, y más aún, ¿cómo logramos que una máquina pueda jugar inteligentemente al ajedrez?. Ésta última pregunta nos podría hacer pensar en que podría tratarse de una labor sumamente dificil, sin embargo, por experiencia propia podríamos decir que teniendo las herramientas y la representación adecuadas, y con un poco de esfuerzo, la tarea simplemente se hace un tanto ardua pero que trae consigo muchas satisfacciones.

Entonces, respondiendo a la pregunta planteada, tenemos que la respuesta es: mediante la exploración de un espacio de jugadas y la búsqueda (y por ende la aplicación) de la mejor de ellas. Ésta exploración se realiza mediante un algoritmo de búsqueda llamado minimax, el cual será el motor de nuestro juego, generando todos los movimientos posibles para una determinada jugada.

Este minimax construye un árbol de variantes y elige de entre todas sus ramas la más beneficiosa para el programa. Sin embargo, como ya se mencionó, la cantidad de movidas que se puede realizar en una determinada jugada es grandísima y el sólo hecho de generarlas y evaluarlas todas representaría un altísimo coste computacional y por ende significaría un bajo rendimiento de nuestro juego. Para solucionar éste inconveniente se hace uso de la poda alfa-beta, el cual, como su mismo nombre lo dice, aplica una poda al árbol generado permitiendonos acelerar muchisimo la búsqueda.

Este algoritmo de poda alfa-beta suele usar dos límites, uno para los niveles maximizadores y otro para los niveles minimizadores, alos cuales se les suele llamar alfa y beta, de ahí su nombre. Sin el uso de ésta técnica de poda las máquinas con grandes recursos computacionales apenas podrían realizar una búsqueda en una pequeña profundidad para poder responder en tiempos razonables.

3.1. MVV/LVA
El hacer uso de la poda alfa-beta es fundamental en la implementación de un ajedrez, sin embargo, para mejorar aún más el desepeño de la misma poda maximizando el número de ramas podadas es ordenando la lista de jugadas generadas.

Una manera muy sencilla y eficaz usada para el ordenamiento de jugadas es el conocido como MVV/LVA o Most Valuable Victim/Least Valuable Atacker, el cual consiste en colocar primero en la lista las jugadas que capturan las piezas más valiosas de su adversario. Para lograr esto se asigna un valor a cada captura según el resultado de la compración de los valores del atacante y el atacado, estos valores son ajustados de la siguiente forma:
  • Capturas Buenas: Cuando el atacante vle menos que el atacado
  • Capturas Normales: Capturas equivalentes entre el atacante y el atacado
  • Capturas Malas: El atacante vale menos que el atacado.
Despues de encontrar los valores de captura para cada jugada, simplemente debemos ordenar eficientemente la lista de jugadas generadas respecto a este valor, de ésta manera tndremos la certeza que el árbol de poda alfa-beta evaluará primero la mejor jugada, la cual tendrá mayor posibilidad de ser la jugada que se ejecutará.

3.2. Estructura del Nodo del árbol de poda Alfa-BetaLa estructura del nodo mantiene la información del tablero actual, de la ficha que se esta moviendo así como de su posición origen y destino, la profundidad máxima hasta la cual se debe explorar, el valor heurístico (que será asignado en el nodo hoja por la función de evaluación) y el tipo de evaluación al que será sometido (maximizador o minimizador).
En la figura se puede observar la estructura de un nodo del árbol de poda alfa-beta que usamos en nuestra implementación.

4. La Función de EvaluaciónLa función de evaluación es una de las partes más importantes del juego. La función de evaluación permite medir cuantitativamente las partes positivas y negativas de cierta jugada, es decir, es un indicador de que tan buena o mala es una jugada.

Mientras más sofisticada sea la función de evaluación para poder dar una “respuesta inteligente”, mayor será también el costo de procesamiento. Esto ha llevado a establecer diversas opciones para funciones de evaluación. En nuestro caso hemos tomado ciertos criterios para poder evaluar nuestras jugadas, las cuales son:
  • Evaluación de Balance Material
  • Evaluación Táctica
  • Evaluación de Movimientos
De donde obtendremos que:

Funcion_evaluacion = fed + fem + fet

5. Efecto Horizonte y Búsqueda Quiescense
El efecto horizonte se puede entender como la incertidumbre de saber, con qué nos podemos encontrar más alla de nuestro horizonte de búsqueda. Normalmente, durante la poda alfa-beta, llegamos hasta un cierto nivel de profundidad en donde paramos de hacer las búsquedas y comenzamos a determinar cual será la jugada con el que nuestro juego responderá al humano, pero, ¿qué ocurre si una aparente buena jugada en nuestro último nivel n nos lleva a perder a nuestra dama o peor aún a entrar en un jaque en el nivel n+1?

Esto nos lleva a entender que una jugada de tipo captura es buena para un determinado jugador pero sólo en ese momento, por que no sabe exactamente que es lo que se puede venir después. Observemos por ejemplo la siguiente figura:

Aquí podemos observar que una jugada buena aplicando simplemente la poda alfa-beta nos indicaría mover la torre blanca de la posicion c2 por el peon negro de la posicion a2, que para la máquina sería una buena jugada. Sin embargo, si vemos más alla del horizonte notaremos que, después de éste movimiento, la torre negra de a4 cmería a la torre blanca que ahora se encuentraría en a2, luego la torre blanca de d2 respondería al ataque comiendo nuevamente a la torre negra y ubicandose nuevamente en a2, para que, finalmente, la torre negra de a5 nos dé la estocada final y coma a nuestra última torre blanca, quedándonos en gran desventaja pues hemos perdido nuestras dos torres blancas, mientras que las fichas negras aún tienen una, con la que, nos pueden causar serios problemas.De ésta manera podemos definir:

Posición Estable: Es aquella en la que no existen jugadas de tipo captura en el tablero, o mediante un corte después de recorrer cierta profundidad en una búsqueda quiescense.

Entonces, resolveremos y minimizaremos el efecto horizonte mediante la búsqueda quiescense, la cual se encargará de hacer la búsqueda de jugadas de tipo captura a partir de los nodo hoja del árbol de poda alfa-beta y se desarrollará hasta una determinada profundidad (establecido para la búsqueda quiescense ) o hasta llegar a una posición estable.

La búsqueda quiescense puede añadir un poco de complejidad al juego, sin embargo, nos permite mejorar el desempeño del juego y lograr que éste realice mejores jugadas.

5. Aplicación
Se ha implementado el juego del ajedrez siguiendo las consideraciones presentadas y planteando diferentes niveles de juego, los cuales, realizan busquedas de soluciones a diferentes niveles de profundidad en el árbol de poda alfa beta, de esta manera, cuando se juega en nivel básico se usa una profundidad de 4, en el nivel intermedio se usa una profundidad de 6, mientras que el avanzado usa una profundidad de 8. Además en los tres niveles se hace una búsqueda quiescense de profundidad máxima de 3.

A continuación se presentan la captura de pantalla de la interface del juego.

Los autores del trabajo realizado en una unidad del curso de Inteligencia Artificial son Pedro Shiguihara Juárez, Juan Grados Vásquez y mi persona. En este trabajo solo se presentan las nociones básicas de un ajedrez inteligente, faltán muchas cuestiones que permitan mejorar aún más las respuestas de la máquina. También es obvio que la implementación de los algoritmos necesarios en el ajedrez deberán de ser óptimos para lograr una respuesta rápida.

Desde aqui pueden bajar un breve informe preparado en el que se detallan los puntos presentados arriba y que nos dan las nociones para hacer o programar un juego de ajedrez en la computadora. Espero les sea de alguna utilidad, saludos.


Quieres leer más post como éste???...suscribete aquí!!!

3 comentarios:

  1. Este es un gran trabajo, la función de evaluación es sólo un factor que permite darle mayor capacidad a la computadora de 'pensar', ya que también la búsqueda quiescense permite darle mayor robustez en la toma de decisiones, y la búsqueda poda alfa beta permite recorrer una cantidad limitada de posibles movimientos a diferentes niveles de profundidad. Usando procesamiento paralelo se puede mejorar el rendimiento al momento de analizar los movimientos, de todas maneras (Y).

    ResponderEliminar
  2. muy bien elaborado (Y) con todos los detalles explicados en el post se puede lograr programar un ajedrez inteligente, sin embargo creo que todo esto hace notar que se necesitará de mucho código y más que eso, se necesitará de mucho procesamiento, y teniendo en cuenta que lo que se espera es rápidez en cada jugada se tendria que encontrar alguna manera de simplificar todo eso

    ResponderEliminar
  3. ya no estan disponibles las descargas.... ai si podiras publicarlos nuevamente te lo agradeceria mucho,....


    saludos!!

    ResponderEliminar

Bienvenido a jcGeorge's Blog!!!

Por favor deja tu comentario, consulta o sugerencia, procura mantener habilitado tu perfil de Blogger o deja un enlace a tu blog o web.

Gracias por leer este blog!!!

Related Posts Plugin for WordPress, Blogger...