Siempre me pregunte como se programaban los juegos tales como el ajedrez, damas, etc... ¿tenían las jugadas "preprogramadas"? ¿sabían todas las posibles mejores soluciones?...pues no.
El programa realmente "piensa" o mejor dicho tiene:
- Una parte dedicada a "valorar" la "posición" (situación de las piezas en el tablero, nº de piezas, dominio del centro del tablero, protección del rey, protección del rey contrario, etc... ), y le da un valor a dicha situación. Ha habido hasta ajedrecista de primera categoría, que han ayudado a los programadores en esta fase.
- Crea un árbol de posibles jugadas y respuestas a esas jugadas (varios niveles de profundidad). Cuanto mayor profundidad mejor juega. Esta fase es muy importante el ordenador que tengamos. (no es lo mismo un anticuado 8086 a un superordenador que realiza billones de cálculos por segundos)
- Y finalmente, mediante un algoritmo llamado Poda Alfa Beta (variante del algoritmo MiniMax), elige la jugada que más le convenga...
Por supuesto este algoritmo se puede aplicar a todos los juegos de tablero por turnos (en principio de 2 jugadores), solamente hace falta cambiar la forma de "valorar" la "posición" de la partida, dependiendo de las reglas del juego.
Bueno os dejo un artículo que he encontrado en San Google sobre este algoritmo y su aplicación a juegos (3 en raya y al ajedrez).
APLICACIÓN DEL ALGORITMO PODA ALPHA-BETA PARA LA
IMPLEMENTACION DEL JUEGO “AJEDREZ”
Jorge Edilberto Alvarado Valderrama, Lesly Rodríguez Pinillos
jorgealvarado@seccperu.org,
leslyrp@hotmail.com
Universidad Nacional de Trujillo
Facultad de Ciencias Físicas y Matemáticas
Escuela Académico Profesional de Informática
Resumen:
El siguiente trabajo de investigación, tiene como propósito mostrar la implementación de juegos basados en computadoras, aplicando el campo de la Inteligencia Artificial, mediante la implementación del algoritmo Poda Apha-Beta. Para mostrar la aplicación de un juego de dos adversarios, hemos seleccionado el juego del “Ajedrez”, que tiene un alto grado de complejidad
computacional, el cual describiremos las técnicas usadas para implementarlo.
Palabras Claves: Inteligencia Artificial, Teoría de Juegos, MiniMax, Poda Alpha-Beta, Ajedrez.
1. Introducción
La inteligencia Artificial, es una campo de que ha tomado gran interés en los últimos tiempos debido a su capacidad de poder resolver soluciones imitando el razonamiento lógico de las personas y hasta el mecanismo de cómo ellas la resuelven.
Un tema interesante a tratar a lo que concierne a la IA son los juegos. Así por ejemplo, el juego del ajedrez es un juego de mesa para dos contrincantes y es uno de los juegos mas mencionados dentro de la teoría de juegos de la
Inteligencia Artificial, por lo que tiene bien definida su meta (el Mate) y sus acciones (conjunto de movimientos de cada una de las piezas que la conforman), las cuales, por cierto, hacen del juego algo complicado de
programarlo, pero no imposible. Este juego fue estudiado por Claude Shanon y hasta el mismo Alan Turing, los cuales sugirieron algunas formas de representarlos en un ordenador.
Existen, pues, varias técnicas de búsqueda para el desarrollo de este juego. Dentro de las técnicas de búsqueda que hemos estudiado, hemos considerado utilizar la búsqueda de Poda Alfa Beta, la cual es muy eficiente en la búsqueda de una solución en un 30% comparada con la Búsqueda de MiniMax. Sin embargo la elección de una heurística apropiada es lo que define mejor la solución del juego. Para este trabajo consideramos tres heurísticas las cuales explicaremos mas adelante.
Para este trabajo, empezaremos definiendo algo de la teoría de juegos; luego antes de entrar el desarrollo del algoritmo Poda Alpha – Beta, analizaremos la técnica del Minimax, para luego explicar las heurísticas que hemos utilizado para obtener la utilidad, elemento necesario para definir una adecuada jugada.
2. Teoria de Juegos
Los juegos han sido estudiados a lo largo de la historia formulándose incluso modelos matemáticos que permitiesen desarrollarlos.
En un principio, estos juegos fueron estudiados por una rama de la ciencia denominada Investigación Operativa (IO), la cual proporcionaba técnicas que solo podrían ser aplicables si existía un procedimiento finito [1]. Con el surgimiento de la Inteligencia Artificial se crean nuevos algoritmos de búsquedas que permiten
desarrollar soluciones dentro de procedimientos no finitos.
Uno de estos algoritmos es el algoritmo de Poda Alpha-Beta que es muy usado en la teoría de Juegos y que permite encontrar soluciones dentro de un campo de búsquedas infinito. Sin embargo para poder entender mejor esta técnica, es necesario y conveniente primero
entender la técnica de búsqueda Minimax, que es una técnica que se centra en la resolución de problemas de búsquedas, basadas en la alternación de dos entes o agentes a los cuales se les denominan Min y Max[2].
3. Estrategia MiniMax
La estrategia minimax es una estrategia de búsqueda exhaustiva mediante un árbol de búsqueda. Este algoritmo considera el caso de 2 participantes a los que se les denomina Max y Min[1].
El que inicia el juego es Max y existe una alternancia en la participación del juego. Por lo tanto lo que tiene que hacer Max, es determinar la secuencia de jugadas que conduzca a un estado Terminal ganador o favorecedor.
La figura 1 muestra parte del árbol generado para la búsqueda por la técnica de Minimax para el juego del tres en raya [5].
Sin embargo, esta búsqueda muchas veces tiene que evaluar ramas innecesarias que no le traerán beneficio alguno para obtener el mejor resultado. Por lo tanto, es aquí donde se plantea la solución mediante la poda de esas ramas que no beneficiaran en nada a la mejor jugada: La técnica de Poda Alpha-Beta.
El algoritmo 1 muestra la implementación de la técnica de Minimax en forma recursiva [3].
Algoritmo 1: Algoritmo recursivo de la técnica de Minimax
Entrada:
- Nodo N.
Salida:
- Valor de utilidad de N
-------------------------------------------------------------------------------------------------------------
Si N es nodo Hoja
ValorUtilidad<-función de utilidad
De lo contrario
Para cada nodoHijo Hi de
valorUtilidadi<-MiniMaxR(Hi)
Fin para
Si N es max
valorUtilidad<- max(H1,H2,...Hn)
De lo contrario
valorUtilidad<- min(H1,H2,...Hn)
Devolver (valorUtilidad)
4. Poda Alpha-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 [2].
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.
En el algoritmo 2, 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 2. 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
-----------------------------------------------------------------------------------------------------------
5. Juego del Ajedrez.
El juego del ajedrez es un juego adecuado para tratarlo mediante técnicas de IA debido a que tiene claramente definidos el objetivo que se quiere alcanzar
(meta) y los medios para llegar (movimientos permitidos) [1].
En este juego, el programa en todo momento debe conocer la configuración del tablero para la maquina poder tomar la decisión adecuada (jugada), que le permita ganar. Para ello necesita de gran capacidad de almacenamiento de
información, utilizando estructuras que le permitan llegar a conclusiones coherentes.
El juego se desarrolla sobre un tablero de 8 filas y 8 columnas, sobre las cuales se colocan fichas de 2 colores que simbolizan a los 2 oponentes, estos colores son generalmente: Blanco y Negro. Este juego además posee un sin numero de fichas, de diferente tipo y movimiento.
Así pues tenemos:
• Peón
• Torre
• Alfil
• Caballo
• Reina
• Rey
La Tabla 1 ilustra los movimientos permitidos para las diferentes fichas en un juego de ajedrez.
- La primera fila indica el tipo de movimiento, ya sea horizontal, vertical, diagonal o en forma de L.
- La segunda fila indica la dirección hacia donde puede moverse:
Arriba (Arr) o Abajo (Aba).
- El resto de filas indican las fichas del ajedrez: Peon (P), Alfil (A), Torre (T), Caballo (C), Dama (D) y Rey (R).
-El número indicado en las casillas indican la cantidad de casillas que se pueden mover, así: 1 significa que solo puede moverse una sola posición,
mientras que n significa que puede moverse mas de 1 posición dentro del límite del tablero del ajedrez.
Cada jugador al inicio de cada jugada posee 16 elementos, mostrados en la figura 3. Sin embargo, la configuración de cada movimiento que se pueda generar y las posibles acciones que estas puedan sugerir, hacen de este juego algo interesante, motivo por el cual se ha tomado énfasis en estudiar este juego empezando el uso de búsquedas sistemáticas para diseñar programas por ordenador.
Las complicaciones que presenta diseñar una búsqueda adecuada para este juego son bastantes, dentro de las cuales la mas principal es la complejidad espacial en un ordenador, motivo por el cual muchas veces se utiliza una determinada profundidad hasta donde se puede llegar a evaluar.
6. Estructura de Datos Utilizada.
La estructura del node que se ha utilizado, tiene la siguiente estrucutra:
Id | IdPadre | Tipo (Max o Min) | Estado (config. Del tablero) | Funcion de utilidad | Mejor accion | Prof. |
Id: El primer campo indica el ident del nodo que se esta generando.
IdPadre: El siguiente dato, corresponde al padre que lo generó.
El
tipo hace referencia a que nodo se esta analizando: si es Max o es Min. En caso de ser Max, el algoritmo tratará de obtener la jugada de mayor utilidad,pues genera beneficio para Max; sin embargo cuando es Min, la maquina elegirá la menor utilidad posible, perjudicando al oponente.
El
estado, es la configuración del tablero, es decir, corresponde al ambiente que será analizado por la maquina.
La
función de utilidad corresponde a la utilidad calculada por la heurística explicada posteriormente [2].
La
mejor acción es una variable que me va recolectando el camino que se genera con la mejor jugada posible, para esto debe basarse en la utilidad.
Y finalmente la
profundidad, indica, que tan profundo se va a analizar las jugadas, es decir, si se escoge una profundidad de 4, esto indicaría que se va analizar 2 turnos para ambos jugadores y de allí se extraerá el mejor camino.
7. Aplicación
Hemos aplicado una heurística en la que se
considera un peso para cada pieza según el color:
• Piezas Blancas
- Peón : 1
- Caballo : 3
- Alfil : 3
- Torre : 5
- Reina : 10
- Rey : 50
• Piezas Negras
- Peón : -1
- Caballo : -3
- Alfil : -3
- Torre : -5
- Reina : -10
- Rey : -50
Las Heurística para la función de Utilidad que logramos analizar son las siguientes:
1º Capturar Posición del Rey Blanco: xRB, yRB
2º Capturar Posición del Rey Negro: xRN, yRN
3º Sumar N° de piezas Blancas: sumaB
4º Sumar N° de piezas Negras: sumaN
5º Calcular que tan protegido esta el rey blanco de las piezas negras: BRP
6° Calcular que tan Protegido esta el rey Negro de las piezas blancas: NRP
7° Calcular que tan cerca están las piezas negras del rey Blanco: BAR
8° Calcular que tan cerca están las piezas blancas del rey Negro: NAR
Finalmente se obtendrá la Utilidad con la siguiente ecuación:
La primera división, mide que tanta es la diferencia de fichas entre los dos oponentes. Si uno de ellos tiene una cantidad de pesos mayor en fichas,
probablemente pueda tener más ventajas sobre el otro, por lo tanto pueda ganar.
La segunda división, es una probabilidad que hemos considerado y mide que tan protegido esta un rey. Si un rey tiene mas cerca a sus piezas, entonces la
probabilidad que sea comido es menor, por lo tanto menos oportunidad de ser atacado directamente.
La tercera división mide la probabilidad de que un rey sea atacado por el oponente. Si un rey tiene mas fichas enemigas cerca, entonces la probabilidad de ser atacado aumenta, y por lo tanto pueda ejecutarse el mate.
Por lo tanto, la ecuación presentada, mide que tanta ventaja tiene un oponente sobre el otro.
8. RESULTADOS
Para la aplicación, hemos considerado varias profundidades, que determinaban el nivel de juego:
Profundidad 3 -> Nivel Principiante
Profundidad 4 -> Nivel Intermedio
Profundidad 5 -> Nivel Avanzado
Estas profundidades mostraron tener óptimos resultados, demorando en el último, a lo mas 30 segundos de ejecución, tiempo razonable debido a la gran cantidad de nodos que se tenían que evaluar.
9. CONCLUSIONES
9.1 El algoritmo de Poda Alfa-Beta, es un algoritmo eficaz en cuanto a la búsqueda de una solución, si bien no comparamos en este trabajo la diferencia
con el otro algoritmo estudiado, MiniMax, hemos probado que la poda por cierto camino que no aportara nada a la decisión aumenta en un 30% la
eficiencia de la búsqueda.
9.2. Las limitaciones que encontramos para este trabajo es trabajar con respecto a la profundidad. Esto se debe a que trabajamos con una profundidad no tan alta, como 5 en el trabajo presentado, teniendo una respuesta de menos de 1 minuto en la búsqueda de la solución.
9.3. En el trabajo presentado, hemos considerado dos heurísticas que hemos creído conveniente considerar: una basada en el ataque a un rey y otra basada en la defensa de un rey. Estas dos técnicas nos han permitido tener un mejor resultado en la toma de una decisión, mejorando la búsqueda sin llegar a una profundidad muy alta.
10. Referencia Bibliográfica
[1] Francisco Astudillo Pacheco, Daniel Borrajo Millan, Carmen Tarta Alcalde y Irma Trueba Valle, “Informática Aplicada: Juegos Inteligentes en
Microordenadores”, Ediciones Siglo Cultural, España, 1986.
[2] Stuart Russell and Peter Norvig, “Inteligencia Artificial: Un Enfoque Moderno”, Edición Prentice Hall, ISBN 0-13-10385-2, 1996.
[3] Francisco Jose Ribadas Pena, “Busqueda en Espacio
de Estados”
[4] “Juegos y MiniMax: Poda Alpha Beta”, [en linea], Formato PDF,
2006,Disponible en:
http://arantxa.ii.uam.es/~ia/p4/p4.pdf
[5] José Ignacio Nuñez Varela, “Introducción a la Inteligencia Artificial”, [en línea], Universidad Autónoma de Juan Luis Potosí, Formato PPT, 2007,
Disponible en:
www.itnuevolaredo.edu.mx
[6] “Inteligencia Artificial: Algoritmo Poda Alpha- Beta”
[7] “Definición de una Poda Alpha-Beta”, [en línea], Disponible en:
http://www.lania.mx/~asanchez/IA/minimax3.html
-------------------------------------------------------------------------------------------------------------------------
Documento:http://www.lania.mx/~asanchez/IA/minimax3.htmlDefinición de una Poda Alpha Beta
Queda claro que el arbol empieza a crecer, y en un juego de ajedrez el nivel de expertez del juego se mide por que tantas jugadas adelante vel el minimax, normalmente de va desde 1 ply hasta 6 plys completos. por esto es necesario podar un tanto el arbol, para esto se tiene varios métodos entre ellos la poda Alfaa Beta y la poda de Crash Cut
PODA Alfa Beta Asumiendo que un jugador Alfa tiene que maximizar lo que el otro jugador Beta tiene que minimizar, podemos almacenar la información que van obteniendo los dos y retroalimentarla.
Veamos esto en un ejemplo, en el algoritmo basico de MINIMAX a dos niveles se tiene que
- 1. Abrir el arbol
- 1.1 Todas mis jugadas
- 1.2 Todas sus jugadas
- 2. Aplicar la evaluación en todos sus hijos
- 3. Minimizar por nodo en sus jugadas ( beta )
- 4. Maximizar en todo mis jugadas
- 5. Seleccionar la mejor ( alpha )
Asi por ejemplo vemos la apliacación en la figura 
Sin embargo el numero de tiradas puede crecer, con la poda alfa beta podemos eliminar con el conocimiento que se va procesando si dejamos hasta el final la evaluación de los nodos, veamos la figura siguiente:
En la figura observamos que una vez que minizo el primer nodo el valor beta = 3 indica al jugador alfa que cuando menos ya podra obtener un valor >=3 por lo que no tiene caso evaluar jugadas menores a 3 para el nodo siguiente, asi vemos que cuando el jugador beta minimiza el segundo nodo, se nota que una vez encontrado el valor 1 como su trabajo es minimizar el nodo que subira sera unicamente <=1 y por ende el jugador alpha no va a usarlo, por lo que en algoritmo minimax resulta posible no evaluar las jugadas marcadas con x, con el correspondiente ahorro de tiempo ( el ahorro se puede dar en tres modos : la creacion de la jugadas, el recorrido del arbol y la evaluación ) . Sin embargo para el caso del tercer nodo el jugador beta tendra despues de encontrar el tablero con valor 8 tiene que continuar evaluado, ya que 8 es mayor 3 y el jugador alfa si lo tomaria, por lo que el beta debe buscar una tirada menor, la cual encuentra con la jugada de valor 2. Quedando el algoritmo como sigue:
- 1. Abrir la siguiente jugada mia generando un nodo para el con alfa = valor pequeño
- 1.1 Si ya no hay mas jugadas : me voy a 4.
- 2. Abrir la siguiente jugada de él con beta = valor grande
- 2.1 Si ya no hay mas jugadas y Si beta > alfa : alfa = beta y salto al paso 1
- 3. Evaluo su jugada
- 3.1. Si la jugada de él es mayor que beta me salto al paso 1
- 3.2. Si la jugada de él es menor que beta : beta = evaluacion y me salto al paso 2
- 4. Tomo la jugada que me dio el último alfa y termino
Este ahorro permite generar mas hijos en jugadas posteriores para esto es necesario modificar el algoritmo para hacerlo recursivo, lo que se logra con modificar el paso 3 - 0. numtiradas = profundidad
- 1. Abrir la siguiente jugada mia generando un nodo para el con alfa = valor pequeño
- 1.1 Si ya no hay mas jugadas : me voy a 4.
- 2. Abrir la siguiente jugada de él con beta = valor grande ;
- 2.1 Si ya no hay mas jugadas y Si beta > alfa : alfa = beta y salto al paso 1
- 3 Evaluación
- 3.1.1 Si numerotiradas = profundidad : Evaluo la jugada
- 3.1.2 Si numerotiradas < produndidad : numerotiradas = numerotiradas + 1 ;voy( recursivamente ) a paso 1
- 3.2.1 Si la jugada de él es mayor que beta me salto al paso 1
- 3.2.2 Si la jugada de él es menor que beta : beta = evaluacion y me salto al paso 2
- 4. Tomo como valor la jugada que me dio el último alpha y regreso a quien me llamo ( recursivamente )
Pseudo Código para una poda Alfa Beta en Minimax
import java.awt.*;
import java.applet.Applet;
public class alfabeta extends Applet
// Inicializa variables
int[] TIRADA = new TIRADA[2] // TIRADA[1] es el tablero TIRADA[2] es el valor del tablero
int[] POSIBLE = new POSIBLE[2] ; int[] MinTirada = new MinTirada[2] ;
int[] MaxTirada = new MaxTirada[2] ;
int Jugada, numtir, procrece ; // variables que defiene el numero de tablero y la profundidad deseada
// Procedimiento maximizacion y minimizacion recursivamente
public void init()
{ numtir = profundidad ;
Juego = "en Proceso"; Jugada = 0; tiro= 0;
while (Juego <> "en Proceso")
{ procrece = 1;
TIRADA = Maximiza(Jugada, alfa, beta, procrece);
Grafica(TIRADA[1]); Jugada = TIRADA[1] ;
Juego = EvaluaTerminacion(TIRADA); } ;
};
// Procedimiento para la Maximizacion
int Maximiza(Jugada,alfa,beta,procrece)
{ alfa = -infinito; for ( j= 1; j <= Njugadas ; j=j+1 )
{ MaxTirada[1] = SiguienteTab(j,Jugada); POSIBLE = Minimiza(MaxTirada[1],alfa,beta,procrece);
if ( beta > alfa ) alfa = beta;
if alfa >= POSIBLE[2] then TIRADA = POSIBLE };
return TIRADA ; }
// Procedimiento para la Minimizacion
int Minimiza(Jugada,alfa,beta,procrece)
{ procrece = procrece +1; Poda = "enproceso" ; beta = + infinito ;
for ( j = 1; j <= Njugadas AND poda = "enproceso" ; j=j+1 )
{ MinTirada[1] = SiguienteTab(j, Jugada);
if ( procrece = numtir ) POSIBLEMIN[2] = Evalua(MinTirada[1])
else POSIBLEMIN = Maximiza(MinTirada[1], alfa, beta, procrece); }
if ( MinTirada[2] <= beta )
{ TIRADA = POSIBLEMIN ; beta = MinTirada[2] ;
if (beta <= alfa) Poda = "hecha" ; }
}
Return TIRADA }
// Procedimiento para la Evaluacion
int Evalua(Jugada)
// Procedimiento para la Graficacion
int Grafica(Jugada)
// Procedimiento para la determinacion de la siguiente jugada
int SiguienteTab(j, Jugada)
} // end class Alfabeta
Este ahorro permite generar mas hijos hacia adelante sin un crecimiento exponencial como se muestra en la gráfica
La Figura muestra adicionalmente una poda denomida de corte agresivo, la cual tiene como objetivo eliminar completamente de la evaluacion toda una zona de un arbol en caso de que se considere que dicha zona contiene una jugada que de antemando se perdibe mala, aunque al final se pudiera ganar por esa ruta, este es el caso para el caso del ajedrez, de decidir no evaluar tableros que asuma la perdida de una pieza clave como la reina, que aunque resulte factible, el programa no quiere considerarlas. A esta poda se le denomina Corte agresivo o Crash Cut. El pseudocódigo para dicha poda se ve reflejado en el metodo de maximizacion
// Procedimiento para la Maximizacion
int Maximiza(Jugada,alfa,beta,procrece)
{ alfa = -infinito;
for ( j= 1; j <= Njugadas ; j=j+1 )
{ MaxTirada[1] = SiguienteTab(j,Jugada);
If (NotCut(MaxTirada[1]) // la funcion NotCut regresa verdad si no hay un corte agresivo en la jugada considerada
{ POSIBLE = Minimiza(MaxTirada[1],alfa,beta,procrece);
if ( beta > alfa ) alfa = beta;
if alfa >= POSIBLE[2] then TIRADA = POSIBLE }
};
return TIRADA ; }
, donde cada término 
equivale a la diferencia de ángulos entre dos radios consecutivos (grafico 5). 
radianes). El signo a considerar será: positivo, si el sentido de crecimiento del ángulo es antihorario, y negativo en caso contrario, o viceversa.
1) al ángulo comprendido entre V1 y V2, (
por debajo de pi deberán corisiderarse 0, y aquellos que estén por encima de ese valor, deberán tomarse como 2
)
